对轻量级分组密码PICO算法的差分攻击  

Differential Cryptanalysis on Ultra Lightweight Block Cipher PICO

作　　者：王彩冰 张志宇 胡磊[1,2] WANG Cai-Bing;ZHANG Zhi-Yu;HU Lei(State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China;School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100049,China)

机构地区：[1]中国科学院信息工程研究所信息安全国家重点实验室,北京100093 [2]中国科学院大学网络空间安全学院,北京100049

出　　处：《密码学报》2023年第4期685-701,共17页Journal of Cryptologic Research

基　　金：国家重点研发计划(2018YFA0704704,2022YFB2701900);国家自然科学基金(62172410,62202460);中央高校基本科研业务费专项资金。

摘　　要：PICO算法是一个SP结构的迭代型轻量级密码算法,目前对该算法的差分分析和相关密钥分析研究尚未完善.本文借助自动化搜索技术,设计了一套基于SAT方法搜索SP结构算法差分路径和差分闭包的自动化工具,构建了搜索约减轮PICO算法差分路径以及差分闭包的SAT模型,评估了PICO算法抵抗差分攻击的能力,提供了比之前分析结果更准确的安全评估.给出了1–22轮PICO算法的最优差分路径及其概率;搜索到概率为2−60.75的21轮差分闭包和概率为2−62.39的22轮差分闭包;实现了26轮PICO算法的密钥恢复攻击,攻击的时间复杂度为2101.106,数据复杂度为263,存储复杂度为263.研究了PICO算法抵抗相关密钥攻击的能力,发现PICO算法的密钥编排算法存在缺陷,构建了任意轮概率为1的相关密钥区分器,给出了全轮PICO算法的密钥恢复攻击.所提模型适用于其他轻量级密码算法,尤其是拥有更长的分组或者轮数更多的分组密码算法.PICO is an iterative lightweight block cipher with SP structure,whose differential and related-key cryptanalyses are insufficient.This paper designs an SAT-based tool to search for optimal differential trails and differentials of lightweight block ciphers with SP structure using the automatic searching method.This paper designs an SAT model to search for optimal differential trails and differentials of reduced-round PICO,evaluates the security of PICO against differential cryptanalysis and provides more accurate results.Optimal differential trails are designed,and the probabilities from round 1 to round 22 are presented.This paper shows that a 21-round differential distinguisher can be found with probability 2−60.75 and a 22-round differential distinguisher can be found with probability 2−62.39.A key-recovery attack on 26-round PICO can be formed with the time complexity 2101.11,data complexity 263 and memory complexity 263.Finally,the security of PICO in the related-key setting is studied and a weakness in its key schedule is found,resulting in the existence of related-key distinguishers for any round with probability 1.Based on the distinguisher,a key-recovery attack on full round PICO can be conducted in the related-key setting.The proposed model can be applied to other lightweight ciphers,especially block ciphers with larger block size or having many rounds.

关 键 词：PICO算法 SP结构 差分攻击 布尔可满足性问题 密钥恢复攻击 相关密钥攻击 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]