Automatic Verification of Differential Characteristics: Application to Reduced Gimli
Automatic Verification of Differential Characteristics: Application to Reduced Gimli
复制标题
DOI：
10.1007/978-3-030-56877-1_8
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
F. Liu;Takanori Isobe;W. Meier
中科院分区：
文献类型：
--
作者：
F. Liu;Takanori Isobe;W. Meier
自从Shakecak被选为SHA-3标准以来，越来越多的基于置换的原语被提出。与分组密码不同，基于置换的原语的底层置换中没有轮密钥。因此，当考虑不同轮上的差异转换的依赖性时，底层置换的差异特性变得不兼容的风险更高。然而，在大多数基于MILP或SAT的模型来搜索差分特征时，仅涉及差分转换，并且在不同轮中被视为独立的，这可能导致对于底层置换找到无效的转换。为了克服这一障碍，我们的动机是设计一个模型，自动避免不一致的差分特性的搜索。我们的技术是在构造的模型中同时涉及差异转换和值转换。这样的想法受到了Mendel等人在ASIACRYPT 2011中提出的查找SHA-2特征的算法的启发，其中同时搜索差分特征和一致消息对。作为第一次尝试，我们的新技术将应用于CHES 2017中提出的Gimli置换。其结果是，我们发现，一些现有的差分特性减少Gimli确实是不兼容的，其中之一是发现在Gimli文件。此外，由于在Gimli文档中仅分析了置换，因此我们将进行全面的研究，涵盖为Gimli指定的建议哈希方案和认证加密（AE）方案，该方案已成为NIST轻量级密码学标准化过程的第二轮候选方案。对于散列方案，半自由启动（SFS）碰撞攻击可以从中间轮开始达到多达8轮。对于AE方案，状态恢复攻击被证明可以实现多达9轮。应该强调的是，我们的分析并没有威胁到吉姆利的安全。
Since Keccak was selected as the SHA-3 standard, more and more permutation-based primitives have been proposed. Different from block ciphers, there is no round key in the underlying permutation for permutation-based primitives. Therefore, there is a higher risk for a differential characteristic of the underlying permutation to become incompatible when considering the dependency of difference transitions over different rounds. However, in most of the MILP or SAT based models to search for differential characteristics, only the difference transitions are involved and are treated as independent in different rounds, which may cause that an invalid one is found for the underlying permutation. To overcome this obstacle, we are motivated to design a model which automatically avoids the inconsistency in the search for differential characteristics. Our technique is to involve both the difference transitions and value transitions in the constructed model. Such an idea is inspired by the algorithm to find SHA-2 characteristics as proposed by Mendel et al. in ASIACRYPT 2011, where the differential characteristic and the conforming message pair are simultaneously searched. As a first attempt, our new technique will be applied to the Gimli permutation, which was proposed in CHES 2017. As a result, we reveal that some existing differential characteristics of reduced Gimli are indeed incompatible, one of which is found in the Gimli document. In addition, since only the permutation is analyzed in the Gimli document, we are lead to carry out a comprehensive study, covering the proposed hash scheme and the authenticated encryption (AE) scheme specified for Gimli, which has become a second round candidate of the NIST lightweight cryptography standardization process. For the hash scheme, a semi-free-start (SFS) collision attack can reach up to 8 rounds starting from an intermediate round. For the AE scheme, a state recovery attack is demonstrated to achieve up to 9 rounds. It should be emphasized that our analysis does not threaten the security of Gimli.