对称加密的安全性可以直接使用密钥长度判断,如 128 位、256 位,只要密码学家同意算法本身是安全的。相比之下,衡量公钥加密的安全性则比较复杂:我们选择目前最高效的算法(如大步小步、Pollard rho 等)来攻击手中的问题(如椭圆曲线离散对数问题),估算攻击所需的资源的数量级,然后与对称加密的攻击相比较,得出其安全性“等效于 n 位对称加密”的结论。例如 NIST 认为:256 位有限域上的椭圆曲线公钥加密拥有”等效于 128 位对称加密“的安全性,因此推荐与 AES-128 配合使用。
但问题真的有那么简单吗?知名密码学家(兼信息安全界知名喷子与段子手) Daniel J. Bernstein 有不同意见。在口水战泛滥的”256 位还是 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(攻击更多密钥则需要更高的运算量)。而且攻击者也不太可能碰运气:降低搜索次数,成功率二次方递减。
因此得到几个结论:
- 同样被评估为“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.
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.
发表评论