The Curse of Small Domains: New Attacks on Format-Preserving Encryption
The Curse of Small Domains: New Attacks on Format-Preserving Encryption
复制标题
小域的诅咒：对格式保留加密的新攻击
DOI：
10.1007/978-3-319-96884-1_8
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Viet Tung Hoang, Stefano Tessaro
中科院分区：
文献类型：
--
作者：
Viet Tung Hoang, Stefano Tessaro
格式保留加密(FPE)产生与明文具有相同格式的密文。构建安全的FPE非常具有挑战性，最近的攻击(Bellare、Hoang、Tessaro、CCS‘16；Durak和Vaudenay，Crypto’17)突显了最近的NIST SP800-38G标准中的安全缺陷。这留下了一个悬而未决的问题，即是否存在高安全性的实际方案。在本文中，我们继续调查针对FPE方案的攻击。我们的第一个贡献是针对基于Feistel的FPE(例如来自NIST SP800-38G标准的FF1/FF3)的新的已知明文消息恢复攻击，该攻击在多目标场景下的摊销复杂性方面改进了以前的工作，其中多个密文要被解密。我们的攻击在质量上也更好，因为它们不假设要解密的目标与已知明文之间的相关性。我们还发现了一个特定于FF3的新漏洞以及它如何处理奇数长域，这导致我们的攻击速度大大加快。我们还展示了对非基于Feistel的FPE的第一次攻击。具体地说，我们展示了对FNR的强消息恢复攻击，FNR是由Cisco提出的一种构造，它遵循Naor和Reingold(Joc，‘99)的范式，用成对独立的排列取代Feistel构造中的两轮。我们还针对Bright twell和Smith的DTP构造的变体提供了一种仅针对密文的强攻击，该DTP构造是由Protigity在商业应用中部署的。我们的所有攻击都表明，现有的建筑没有达到理想的安全水平。对于Feistel和FNR方案，我们的攻击在较小的域上变得可行，例如，对于建议的轮数，8比特。我们对DTP构造的攻击即使对于大的域也是实用的。我们提供了我们的攻击的概念验证实现，以验证我们的理论发现。
Format-preserving encryption (FPE) produces ciphertexts which have the same format as the plaintexts. Building secure FPE is very challenging, and recent attacks (Bellare, Hoang, Tessaro, CCS ’16; Durak and Vaudenay, CRYPTO ’17) have highlighted security deficiencies in the recent NIST SP800-38G standard. This has left the question open of whether practical schemes with high security exist.In this paper, we continue the investigation of attacks against FPE schemes. Our first contribution are new known-plaintext message recovery attacks against Feistel-based FPEs (such as FF1/FF3 from the NIST SP800-38G standard) which improve upon previous work in terms of amortized complexity in multi-target scenarios, where multiple ciphertexts are to be decrypted. Our attacks are also qualitatively better in that they make no assumptions on the correlation between the targets to be decrypted and the known plaintexts. We also surface a new vulnerability specific to FF3 and how it handles odd length domains, which leads to a substantial speedup in our attacks.We also show the first attacks against non-Feistel based FPEs. Specifically, we show a strong message-recovery attack for FNR, a construction proposed by Cisco which replaces two rounds in the Feistel construction with a pairwise-independent permutation, following the paradigm by Naor and Reingold (JoC, ’99). We also provide a strong ciphertext-only attack against a variant of the DTP construction by Brightwell and Smith, which is deployed by Protegrity within commercial applications. All of our attacks show that existing constructions fall short of achieving desirable security levels. For Feistel and the FNR schemes, our attacks become feasible on small domains, e.g., 8 bits, for suggested round numbers. Our attack against the DTP construction is practical even for large domains. We provide proof-of-concept implementations of our attacks that verify our theoretical findings.
登录
查看更多内容
打破小域上的 FF3 格式保留加密标准
DOI：
10.1007/978-3-319-63715-0_23
发表时间：
2017
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
F. Durak;S. Vaudenay
通讯作者：
S. Vaudenay
FNR：任意长度小域分组密码提案
DOI：
10.1007/978-3-319-12060-7_10
发表时间：
2014
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Sashank Dara;S. Fluhrer
通讯作者：
S. Fluhrer
Mix-and-Cut Shuffle：针对 N 查询的小域加密
DOI：
10.1007/978-3-642-40041-4_22
发表时间：
2013
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Thomas Ristenpart;Scott Yilek
通讯作者：
Scott Yilek
DOI：
--
发表时间：
2010
期刊：
--
影响因子：
--
作者：
Thomas Peyrin;J. Stern
通讯作者：
Thomas Peyrin;J. Stern