安全与密码学2016eprint.iacr.org编辑精选
Scrypt 是最大程度内存困难（memory-hard）的
Scrypt is Maximally Memory-Hard
专业 · 约 90 分钟读完前置知识：内存困难函数（MHF）概念、scrypt 算法结构、时间-内存权衡（TMTO）攻击
导读
这篇论文对 scrypt 这一内存困难哈希函数（MHF）给出理论分析，论证其在内存难度上达到了理论上限（maximally memory-hard），即任何哈希算法的内存复杂度下界都不会超过 scrypt。scrypt 的设计初衷是让密码验证的成本主要由内存开销主导，从而削弱 ASIC 等专用硬件对攻击者的优势。
HN 关注点：这一结果是因为它似乎与已知事实相矛盾——scrypt 存在时间-内存权衡（TMTO）攻击，而 Argon2 正是为解决该问题而设计的；若 scrypt 已是最优，意味着 Argon2 也可能存在类似攻击，因此讨论焦点集中在对该结论的质疑与解读上。
后来怎么样
该论文为 scrypt 的内存难度提供了理论刻画，其结论与 Argon2（Password Hashing Competition 胜出方案）的设计动机形成对照，推动了关于 MHF 理论上限与 TMTO 攻击的后续讨论。
HN 评论精选
这几条评论里：质疑 1 补充 2 亲历 1
质疑质疑论文结论与已知的 scrypt TMTO 攻击及 Argon2 的设计动机相矛盾
等一下，scrypt 存在时间-内存权衡攻击，Argon2 正是为了解决这个问题而开发的。现在却有证明说 scrypt 是任何人能做到的最好结果？这意味着 Argon2 也应该存在类似攻击，只是我们还没找到。这听起来是个重大结论，所以我现在有点怀疑——也许论文的意思并不是我以为的那样？
loup-vaillant查看英文原文
Wait a minute, there's a time memory tradeoff attack for scrypt. Argon2 was developed precisely to remedy that problem. And now there's a proof Scrypt is the best anyone can do? This would mean a similar attack is possible on Argon2 as well, even if we haven't found it yet. This sounds like a significant result, so I'm a bit skeptical right now. Perhaps the paper doesn't mean what I think it means?
亲历解释 scrypt 的防御原理，并推销一种基于海量随机数据池的新方案
scrypt 的要点是最大化利用商用硬件：商用硬件在单位成本下能提供大量内存 IO，而同样的钱在 ASIC 上无法获得 100 倍的 IO，但对 SHA256 这类哈希却可以快 100 倍以上。scrypt 利用内存 IO，让你在 Intel CPU 上跑 100ms 就物有所值。这是老派的防御思路：给每次密码验证尝试强加运行时成本，防御者每次登录都要付出，攻击者每次猜测也要付出。新方法（我有立场，因为我创办了做这个的公司）是加入一次性的、无上限且不增加运行时延迟的成本：用大量随机数据（数 TB 甚至 PB 级），盐化哈希与数据池以简单 API 纠缠在一起，攻击者必须偷走整个数据池才能发起离线攻击；只偷到一部分则连简单密码也破解不了。数据池越大，防御越容易，系统越快、支持的哈希率越高。
zaroth查看英文原文
The point of scrypt is to utilize the commodity hardware to the max. Commodity hardware gives you a lot of memory IO for the buck. You can't spend the same dollars and get 100x more IO on an ASIC. But you can spend the same dollars and get 100x (actually even more) faster at typical hashes like SHA256. The point is to cut down on an attacker's possible advantage by using specialized hardware. Scrypt uses memory IO so that you can "get your money's worth" by running it for 100ms on an Intel CPU. This is old-school thinking and a defensive play at trying to prevent offline attacks. The idea is impose a run-time cost on each attempt to verify a password. Defender spends it every time they try to log someone in. Attacker spends it for every guess at trying to crack a password. The new approach (well I'm quite biased since I founded a company that does this) is to add a one-time cost which is unbounded and does not impose run-time latency. We do this with a large amount of random data. Many TBs or perhaps as much as a PB. The salted hashes are entangled with the data pool with a simple API, in such a way that an attacker would need to steal the entire data pool to run an offline attack. Stealing only part of the data pool does not let you crack any passwords, even if they are trivially simple. The bigger the data pool, the easier it is to defend, and the faster the system runs and more hashes/second it supports. So, is essence it's high performance scalable security that actually stops offline attacks even after the site is breached. You use this new approach as an additive layer on top of the existing scrypt hashing that you are already doing.
补充补充：scrypt 验证成本高，不适合 PoW，Equihash 是为解决此问题的替代方案
值得注意的是，scrypt 用于工作量证明加密货币时有个问题：验证成本很高。理想的问题应该是求解时内存困难、但验证很便宜。Equihash（Zcash 使用）就试图做到这一点，不过证明其内存难度比 scrypt 的情况要困难得多。
murbard2查看英文原文
It's worth noting that an issue with scrypt for proof-of-work cryptocurrencies is that is is expensive to check. The ideal problem is memory hard to solve but can be checked cheaply. This is what equihash (used by zcash, (https://www.internetsociety.org/sites/default/files/blogs-media/equihash-asymmetric-proof-of-work-based-generalized-birthday-problem.pdf) attempts to do, though proving the memory hardness seems more harduous than in the case of scrypt.
补充澄清术语：memory-hard 指求值成本由内存成本主导，而非 NP 难意义上的困难
我们说'计算困难'时通常指 NP 难问题。我猜这里的'memory-hard'是指没有其他哈希算法的内存复杂度下界能超过 scrypt，对吗？编辑：重读后发现答案就在文中：'内存困难函数（MHF）是求值成本由内存成本主导的哈希算法。'
todd-davies查看英文原文
When we talk about the term 'computationally hard', we usually mean an NP-hard problem. I assume that here, 'memory-hard' means that no other hashing algorithm can have a greater lower bound on its memory complexity than Scrypt. Is that correct? Edit: After a re-read, I realised that the answer is in the text: "Memory-hard functions (MHFs) are hash algorithms whose evaluation cost is dominated by memory cost."
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2016Hacker News 讨论帖147 分 · 74 评
同领域还值得读
如何入侵一台已关机的电脑：在 Intel ME 中运行未签名代码
How to hack a turned-off computer, or running unsigned code in Intel ME
这篇 Black Hat 2017 白皮书讨论 Intel Management Engine（ME）的安全问题：如何在 ME 中运行未签名代码，以及攻破处于关机状态的电脑的相关…
安全与密码学2017 · 543 分 · 107 评专业 · 约 40 分钟编辑精选比特币：一种点对点的电子现金系统（2008）
Bitcoin: A Peer-to-Peer Electronic Cash System (2008)
中本聪 2008 年发表的比特币白皮书，提出了无需可信第三方的点对点电子现金系统。
安全与密码学2017 · 536 分 · 394 评入门 · 约 45 分钟编辑精选GPRS 加密算法 GEA-1 的密码分析表明存在故意弱点
Cryptanalysis of GPRS Encryption Algorithms GEA-1 suggest intentional weakness
首次公开了对 GPRS 加密算法 GEA-1 和 GEA-2 的密码分析攻击。
安全与密码学2021 · 487 分 · 107 评专业 · 约 90 分钟编辑精选Signal 消息协议的形式化安全分析
A Formal Security Analysis of the Signal Messaging Protocol
用形式化方法分析 Signal 消息协议（TextSecure）的安全性：作者在多阶段密钥交换模型下，借助自动化证明工具对协议的密钥协商与 Double Ratchet 密钥更新…
安全与密码学2016 · 353 分 · 230 评专业 · 约 120 分钟编辑精选A2：模拟恶意硬件
A2: Analog Malicious Hardware
论文研究如何在芯片设计阶段植入模拟电路形式的恶意硬件后门，使其难以被常规检测发现。
安全与密码学2016 · 315 分 · 94 评专业 · 约 75 分钟编辑精选