Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (12): 3839-3843.DOI: 10.11772/j.issn.1001-9081.2023121762

• Cyber security • Previous Articles     Next Articles

Differential and linear characteristic analysis of full-round Shadow algorithm

Yong XIANG1, Yanjun LI1,2(), Dingyun HUANG2, Yu CHEN1, Huiqin XIE2   

  1. 1.Information Industry Information Security Evaluation Center,The 15th Research Institute of China Electronics Technology Group Corporation,Beijing 100083,China
    2.Department of Cryptographic Science and Technology,Beijing Electronic Science and Technology Institute,Beijing 100070,China
  • Received:2023-12-22 Revised:2024-03-27 Accepted:2024-04-01 Online:2024-04-15 Published:2024-12-10
  • Contact: Yanjun LI
  • About author:XIANG Yong, born in 1978, M. S., senior engineer. His research interests include information security system evaluation.
    HUANG Dingyun, born in 2000, M. S. candidate. His research interests include implementation of block cipher, artificial intelligence.
    CHEN Yu, born in 1982, M. S., engineer. His research interests include network security system management.
    XIE Huiqin, born in 1992, Ph. D., lecturer. Her research interests include quantum cryptography, design and analysis of block cipher.
  • Supported by:
    Beijing Natural Science Foundation(4234084)

全轮Shadow算法的差分和线性特征分析

项勇1, 李艳俊1,2(), 黄丁韫2, 陈愚1, 谢惠琴2   

  1. 1.中国电子科技集团公司第十五研究所 信息产业信息安全测评中心,北京 100083
    2.北京电子科技学院 密码科学与技术系,北京 100070
  • 通讯作者: 李艳俊
  • 作者简介:项勇(1978—),男,江苏镇江人,高级工程师,硕士,主要研究方向:信息安全系统测评
    黄丁韫(2000—),男,江西宜春人,硕士研究生,主要研究方向:分组密码的实现、人工智能
    陈愚(1982—),男,山东莒县人,工程师,硕士,主要研究方向:信息安全系统管理
    谢惠琴(1992—),女,福建宁德人,讲师,博士,主要研究方向:量子密码、分组密码的设计与分析。
  • 基金资助:
    北京市自然科学基金资助项目(4234084)

Abstract:

As Radio Frequency IDentification (RFID) technology and wireless sensors become increasingly common, the need of secure data transmitted and processed by such devices with limited resources leads to the emergence and growth of lightweight ciphers. Characterized by their small key sizes and limited number of encryption rounds, precise security evaluation of lightweight ciphers is needed before putting into service. The differential and linear characteristics of full-round Shadow algorithm were analyzed for lightweight ciphers’ security requirements. Firstly, a concept of second difference was proposed to describe the differential characteristic more clearly, the existence of a full-round differential characteristic with probability 1 in the algorithm was proved, and the correctness of differential characteristic was verified through experiments. Secondly, a full-round linear characteristic was provided. It was proved that with giving a set of Shadow-32 (or Shadow-64) plain ciphertexts, it is possible to obtain 8 (or 16) bits of key information, and its correctness was experimentally verified. Thirdly, based on the linear equation relationship between plaintexts, ciphertexts and round keys, the number of equations and independent variables of the quadratic Boolean function were estimated. After that, the computational complexity of solving the initial key was calculated to be 263.4. Finally, the structural features of Shadow algorithm were summarized, and the focus of future research was provided. Besides, differential and linear characteristic analysis of full-round Shadow algorithm provides preference for the differential and linear analysis of other lightweight ciphers.

Key words: Shadow algorithm, lightweight block cipher, differential characteristic, linear characteristic, key recovery

摘要:

随着射频识别(RFID)技术、无线传感器的应用越来越广泛,为了保护这类资源受限设备存储和传输的数据,轻量级密码应运而生。轻量级密码的密钥长度较短、轮数较少,因此在正式投入使用前,有必要对轻量级密码进行精确的安全性分析。针对轻量级密码安全需求,分析全轮Shadow算法的差分和线性特征。首先,提出一种二次差分的概念,从而更清楚地刻画差分特征,证明该算法存在概率为1的全轮差分特征,并通过实验验证差分特征的正确性;其次,给出全轮线性特征,即证明给定一组Shadow-32(或Shadow-64)的明密文,可以获取8(或16)比特的密钥信息,并通过实验验证以上说法的正确性;再次,基于明文、密文和轮密钥之间的线性等式关系估计2次布尔函数的方程数和自变量数,再得到求解初始密钥的计算复杂度为263.4;最后,总结Shadow算法的结构特点,并提出下一步的研究重点。此外,全轮Shadow算法的差分和线性特征的分析工作对其他轻量级密码的差分和线性分析具有一定的借鉴作用。

关键词: Shadow 算法, 轻量级分组密码, 差分特征, 线性特征, 密钥恢复

CLC Number: