SIMECK密码的差分中间相遇攻击改进OA

Boura等人在CRYPTO 2023上提出的差分中间相遇分析(Differential Meet-in-the-middle Cryptanalysis,DMC)是一种基于中间相遇思想实施差分攻击的新型密码分析方法。凭借概率扩展(Probabilistic Extension,PE)、限制条件(Imposed Condition,IC)与并行分割(Parallel Partition,PP)技术在降低时间、数据复杂性与扩展攻击轮数上的优势,差分中间相遇攻击已在多个采用线性密钥生成算法的分组密码上取得了显著效果。然而,目前的DMC还存在两点不足:一是概率扩展后的差分区分器概率为2-p′经常小于22-n(n是密码的分组规模),会导致限制条件技术失效而无法将攻击的数据复杂性维持在非全码本(全码本攻击通常被认为是无效攻击)。虽然已有工作使用明文结构缓解这个问题,但其并没有与并行分割技术很好地结合。二是受SIMECK密码中非线性密钥生成算法的影响,近期关于此密码的DMC无法有效恢复主密钥。具体来说,这些工作只恢复了轮次分散的子密钥,导致进一步推导主密钥的代价超出上界。围绕上述两个问题,本文提出了基于尾接技术的DMC模型。此模型不再按照密码算法头尾来分割待恢复的密钥,而是将尾部的部分密钥视作头部密钥,使攻击中头部轮数减少而尾部轮数增加,从而获得三重优势:一是头部轮数减少会导致差分扩散不充分,便于使用明文结构降低攻击的数据复杂性;二是将更多的被分割密钥集中在密码算法尾部的连续轮,显著降低了推导主密钥的代价;三是利用尾部相邻子密钥间更清晰的制约关系提前排除掉不可能的密钥穷举值。基于上述模型,本文能够有效结合明文结构与并行分割技术,不仅解决了原有攻击在n-1>p′>n-2时无法实现非全码本复杂性的问题,还提升了DMC对于采用非线性密钥生成算法的密码的分析能力。作为应用,本文分别提出了对23轮SIMECK32、31轮SIMECK48和41轮SIMECK64的主密钥恢复攻击。据我们所知,在所有能够恢复主密钥的差分攻击中,本文对SIMECK三个版本的攻击均是轮数最长的攻击。