在密码学应用中，究竟采用 128 位还是 256 位对称加密一直是个引起争论的问题。
“无聊”论证
由于这个话题的口水战实在是太多了，同一个问题被讨论 20 年之后，几乎所有人都早已感到十分厌烦了。其中最常见的“无聊”论证如下：
论证 1（未来风险规避）：虽然 128 位加密现在是安全的，但不能排除未来的密码分析或计算机技术出现不可预期的重大进展。而 256 位加密无论在轮数还是密钥长度上，都提供了安全余量。因此，256 位更加令人放心。例如，DES 加密算法到 90 年代末即被破解，而苏联的 GOST 28147-89 同样在 2011 年爆出严重设计缺陷。幸好它是一个 256 位算法，即使被攻破后依然有 178 位的安全性。
接下来口水战就会立刻爆发：一群人就会开始讨论地球里有多少硅原子，类似太阳的恒星有多少能量，量子力学的计算极限，以及能不能把太阳系转换成超级计算机等问题；另一群人则会指出所谓“不安全”的 DES 加密算法的弱点仅仅是故意人为限制了密钥长度，但它的数学结构（S 盒 与 Feistel 网络）在半个世纪来从未被真正破解，几乎不可能有“不可预期的重大进展”；还有一群人则会摆出 AES 安全分析的各类文献，说 AES-256 的密钥调度偷工减料，有相关密钥攻击，而 AES-128 的安全性至少和“广告”一样；而软件开发者则会和你讲一个加密字节要消耗多少个时钟周期，以及涉及安全的信息根本没那么高价值——最后，一位路过的黑客则会提醒所有人：讨论这个问题简直是浪费时间，你有时间讨论要不要使用 256 位加密，还不如对操作系统和应用程序进行安全审计。安全漏洞被利用的概率无限高于加密算法被破解的概率，而只要你有安全漏洞，再强的加密也等效于 1 位加密，我昨天刚刚发现了 CVE-2000-12450……众人惊呼，于是讨论结束，话题转移位编译器加固和形式化证明了……
上面的这个无聊论证，往往也是 2010 年之前的唯一论证，也是被大多数人认为不值得再讨论的。
“后量子”论证
但随着时代 2015 年的到来，256 位加密忽然意外多出了一批新的支持者。原因？量子计算机恐慌时代开始了。虽然人类还没有建造实用的数字量子计算机的能力，更别提建造能破解实际加密算法的大型量子计算机，但这一领域的研究工作还是不得不让人引起警惕。这就引出了 256 位加密的“后量子”论证。
论证 2（后量子密码学）：量子计算机能运行 Grover 算法，它可以将逆推一函数的复杂度从 n 降低到 sqrt(n)。这样，128 位加密就变成了 64 位。但幸运的是，大部分对称加密算法的内在数学结构也并没有被真正破解，不存在破解它们的高效算法。因此现有的对称算法都可以继续用（真正的麻烦是公钥加密），只需要将 128 位加密改为 256 位，就不怕量子计算机了。那么为何不今天就做好准备呢？
这个论述近年来吸引了不少支持者。例如，WireGuard 协议中，允许用户手工设置一个 256 位对称密钥，可防止流量被量子计算机破解。但是反对者会认为：公钥加密被量子计算机与 Shor 算法破解是确定无疑的。如果公钥加密要推倒重来，现在使用 256 位对称加密的益处是微乎其微的。此外就算是 256 位后量子加密的支持者也会认为，假如大型量子计算机永不问世，那么 256 位就是没有必要的，他们依然支持在前量子应用（即目前的所有应用）中使用 128 位加密。
但实际上，对于密钥长度问题而言，知名密码学家（兼信息安全界知名喷子与段子手） Daniel J. Bernstein 其实还存在一个许多读者都没有听说过的有趣论证，下面就来介绍一下。
DJB 的“多目标论证”
对称加密的安全性可以直接使用密钥长度判断，如 128 位、256 位，只要密码学家同意算法本身是安全的。相比之下，衡量公钥加密的安全性则比较复杂：我们选择目前最高效的算法（如大步小步、Pollard rho 等）来攻击手中的问题（如椭圆曲线离散对数问题），估算攻击所需的资源的数量级，然后与对称加密的攻击相比较，得出其安全性“等效于 n 位对称加密”的结论。例如 NIST 认为：256 位有限域上的椭圆曲线公钥加密拥有”等效于 128 位对称加密“的安全性，因此推荐与 AES-128 配合使用。
然而，破解 128 位对称加密（如 AES-128）所需的运算量约为 2^128 这个主张存在一个隐含前提：这个等级的运算量，是破解一个密钥与一个密文所需的运算量。如果攻击者能获得使用不同密钥加密的相同明文，那么它可以对使用不同密钥的大量用户（或连接）同时进行无差别攻击，而且这是一个可以完美并行化的问题。例如同时攻击 2^40 个密钥，能破解一个是一个，那么至少破解一个密钥的所需的运算量就降低为 2^88。这已经接近人类能想象的数字（2^80）。而且攻击者还可以碰运气：降低搜索次数，成功率线性递减。例如只搜索 25%，将运算量降低为 2^86。
随后，作者还设想了一台大规模并行密码破解机。机器具有 2^32 个芯片，攻击者进行 2^32 次运算（虽然极大，但是人类可以想象的），那么破解至少一个密钥的可能性就是 2^-24。虽然 0.00000006% 的概率可以忽略不计，但纯理论上讲，如此之低的安全性是许多密码学家不能接受的。
相比之下，破解 256 位的椭圆曲线（如 Curve25519，虽然严格意义是 255 位），攻击者必须至少解决一个椭圆曲线离散对数问题，破解多个密钥的难度不比破解一个密钥容易。无论同时破解多少个密钥，运算量都至少为 2^128（攻击更多密钥则需要更高的运算量）。而且攻击者也不太可能碰运气：降低搜索次数，成功率二次方递减。
DJB 后来还在论文“Non-uniform cracks in the concrete: the power of free precomputation”中，将这一思路从“多目标”攻击推广到了“预计算”攻击。如果通过一次预先计算，即可在事后以更低成本攻击多个目标，那么成本高昂的预计算就是“一本万利”的生意，主流安全性分析忽略这些攻击是不正确的。他认为 RSA-3072 和 NIST P-256 虽然安全，但都没有“广告”上说的那么安全。
值得一提的是，预计算安全性也是许多密码学家认为椭圆曲线优于离散对数、整数分解的原因。由于 NFS 算法存在，破解 DH 与 RSA 时可以通过大规模预计算加速——特别是 DH-1024，全互联网曾一度使用同一个标准群，正是人们怀疑 DH-1024 已经被 NSA 破解的原因。相比之下，椭圆曲线的预计算收益不大。
因此得到几个结论：
- 同样被评估为“128 位安全”，对称加密和公钥加密的安全性却有极大的差别。虽然在实践中可能没有什么影响，但有明显的理论意义。DJB 说——Bottom line: 128-bit AES keys are not comparable in security to 255-bit elliptic-curve keys. Is 2^255 – 19 big enough? Yes. Is 128-bit AES safe? Unclear.
- 在密码分析中，串行计算的性能和并行计算的性能不能盲目互换。如果条件合适，大规模并行攻击的成本可能比类似的串行攻击低上亿倍。
- 在这种意义上，将 256 位对称加密和“128 位安全的公钥加密”搭配并非是不合理的。这也是主张使用 256 位加密而不是 128 位加密的一个有趣理由。Daniel J. Bernstein 设计的 ChaCha20 只使用 256 位加密，可能就是这个原因。此外，这个攻击之所以可行，是因为不同的密钥被用来加密相同的明文：AES_k1(x), AES_k2(x), … 但如果不同的密钥总是加密不同的明文：AES_k1(x1), AES_k2(x2), …，无差别攻击就不再可行。有研究者建议提高 nonce 大小，例如将 nonce 提高到 128 位，然后随机选取，但这个方案比加长密钥复杂，而且有许多缺点。
当然，上述讨论不适用于量子计算机。等大型量子计算机问世，所有现在使用的公钥加密和 128 位的对称加密均可被破解，只有 256 位对称加密还算安全。
延伸阅读
- Is 2^{255}-19 big enough? (PDF)
竖版，强烈建议使用“幻灯片模式”或“全屏”阅读。
It is widely asserted that 128-bit AES and a strong 256-bit elliptic curve provide comparable security levels against known attacks. This assertion is false. Known attacks batch and scale much more effectively for 128-bit AES than they do for a strong 256-bit elliptic curve.
AES-128, the NIST P-256 elliptic curve, DSA-3072, RSA-3072, and various higher-level protocols are frequently conjectured to provide a security level of 2^128. Extensive cryptanalysis of these primitives appears to have stabilized sufficiently to support such conjectures.
In the literature on provable concrete security it is standard to define 2^b security as the nonexistence of high-probability attack algorithms taking time < 2^b. However, this paper provides overwhelming evidence for the existence of high-probability attack algorithms against AES-128, NIST P-256, DSA-3072, and RSA-3072 taking time considerably below 2^128, contradicting the standard security conjectures.
There is a widespread myth that parallelizing a computation cannot improve its price-performance ratio. The reality is that a parallel computer is often several orders of magnitude faster than a comparably priced serial computer.
发表回复