基于SAT的ARX不可能差分和零相关区分器的自动化搜索

作     者：任炯炯 张仕伟 李曼曼 陈少真 REN Jiong-jiong;ZHANG Shi-wei;LI Man-man;CHEN Shao-zhen

作者机构：战略支援部队信息工程大学 

出 版 物：《电子学报》 (Acta Electronica Sinica)

年 卷 期：2019年第47卷第12期

页      面：2524-2532页

核心收录：

学科分类：0808[工学-电气工程] 07[理学] 0809[工学-电子科学与技术（可授工学、理学学位）] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：国家密码发展基金(No.MMJJ20180203) 数学工程与先进计算国家重点实验室开放基金(No.2018A03) 信息保障技术重点实验室开放基金(No.KJ-17-002) 

主　　题：不可能差分区分器 零相关区分器 ARX Chaskey SPECK HIGHT SAT求解器 

摘      要：ARX(Addition,Rotation,Xor)算法基于模整数加,异或加和循环移位三种运算,便于软硬件的快速实现.不可能差分分析和零相关分析是攻击ARX的有效方法,攻击的关键是搜索更长轮数、更多数量的不可能差分和零相关区分器.目前很多的搜索方法都没有充分考虑非线性组件的性质,往往不能搜索得到更好、更准确的区分器.本文提出了基于SAT(Satisfiability)的ARX不可能差分和零相关区分器的自动化搜索算法.通过分析ARX算法组件的性质,特别是常规模加和密钥模加这两种非线性运算差分和线性传播的特性,给出了高效简单的SAT约束式.在此基础上,建立SAT模型进行区分器的搜索.作为应用,本文首次给出了Chaskey算法13条4轮不可能差分和1条4轮零相关区分器;首次给出了SPECK32算法10条6轮零相关区分器和SPECK48算法15条6轮零相关区分器;在较短的时间内,给出了HIGHT算法17轮的不可能差分和零相关区分器.与现有结果相比,无论是区分器的条数,还是搜索区分器的时间均有明显的提升.此外,通过重新封装求解器STP的输出接口,建立了自动化的SAT\\SMT分析模型,能够给出ARX算法在特殊输入输出差分和掩码集合下,不可能差分和零相关区分器轮数的上界.