GRANULE算法的不可能差分分析

引用本文

石淑英, 何骏. GRANULE算法的不可能差分分析[J]. 计算机工程, 2019, 45(10), 134-138. DOI: 10.19678/j.issn.1000-3428.0052520.

SHI Shuying, HE Jun. Impossible Differential Cryptanalysis of GRANULE Algorithm[J]. Computer Engineering, 2019, 45(10), 134-138. DOI: 10.19678/j.issn.1000-3428.0052520.

基金项目

信息保障技术重点实验室开放基金（KJ-17-003）

作者简介

石淑英(1980-), 女, 工程师, 主研方向为物联网信息安全、移动互联网;
何骏, 高级工程师

文章历史

收稿日期：2018-08-30
修回日期：2018-10-09

Contents Abstract Full text Figures/Tables PDF

GRANULE算法的不可能差分分析

石淑英 , 何骏

郑州信大捷安移动信息安全关键技术国家地方联合工程实验室, 郑州 450004

收稿日期：2018-08-30；修回日期：2018-10-09

基金项目：信息保障技术重点实验室开放基金（KJ-17-003）

作者简介：石淑英(1980-), 女, 工程师, 主研方向为物联网信息安全、移动互联网; 何骏, 高级工程师.

E-mail: ssy@xdja.com

摘要：GRANULE算法是一个超轻量分组密码算法，有着较好的软硬件实现性能，但目前尚没有该算法在不可能差分分析下的安全性评估结果。为此，利用中间相错技术，找到GRANULE64算法多条5轮不可能差分区分器，并基于得到的区分器，向上、下分别扩展3轮，给出对GRANULE64/80算法的11轮不可能差分分析。通过该算法可以恢复80-bit主密钥，时间复杂度为2^73.3次11轮GRANULE64算法加密，数据复杂度为2⁶⁴个选择明文。

Impossible Differential Cryptanalysis of GRANULE Algorithm

SHI Shuying , HE Jun

Xindajiean National-Local Joint Engineering Laboratory of Mobile Information Security, Zhengzhou 450004, China

Abstract: The GRANULE algorithm is an ultra-lightweight block cipher algorithm with good hardware and software implementation performance, but now the algorithm lacks security estimation result under impossible differential analysis.Therefore, using middle error technology, the multiple 5 round impossible differential distinguishers are found.Based on the obtained distinguisher, the impossible differential analysis on 11 round GRANULE64/80 is presented by adding three rounds upward and three rounds downward.The algorithm can recover the 80-bit master key with time complexity of 2^73.3 11-round encryptions, and a data complexity of 2⁶⁴ chosen-plaintexts.

0 概述

轻量级分组密码算法由于其密钥关系简单、使用的硬件资源少、加密速度优于一般的分组密码算法而被广泛用于资源受限的环境。随着物联网的兴起及智能卡的大量应用, 适用于资源有限环境中的轻量级分组密码成为研究的热点。典型的轻量级算法有PRESENT^[1]、LED^2]、LBlock^[3]、SPECK^[4]、SIMON^[4]等。

GRANULE算法^[5]是2018年由印度学者提出的超轻量分组密码算法, 其采用典型Feistel结构, 有着较好的软硬件实现性能。该算法轮函数由P置换、S盒、循环移位、异或4种运算组成, 其中, S盒是主要非线性运算。研究人员评估了GRANULE算法在差分分析、线性分析、Biclique攻击、零相关线性分析、代数攻击、碰撞攻击等分析下的安全性。但目前还没有GRANULE算法不可能差分分析结果。不可能差分分析, 其基本思想是排除那些导致概率为0的区分器(或特征)的猜测密钥。该技术由Knudsen^[6]和Biham^[7]分别独立提出, 是目前常用的密码分析方法。假如加密方向差分路径α→γ₁以概率为1成立, 解密方向差分路径γ₂←β也以概率为1成立, 但γ₁≠γ₂, 因此α→β是一条不可能差分区分器。对于一条概率为0的差分路径, 当用正确密钥解密密文对时, 不能得到符合该路径的差分。

如果用猜测密钥解密密文对, 得到符合该路径的差分, 该密钥猜测值是错误的, 那么筛去所有的错误密钥猜测值, 剩下需要恢复的正确密钥。不可能差分分析方法在诸多算法中均取得了较优的分析结果, 例如AES算法^[8]、CLEFIA算法^[9]、Camellia算法^[10]、LBlock算法^[11]、SPECK算法^[12]、SIMON算法^[13]、SIMECK算法、ARIA算法^[14]与Crypton算法^[15]等。

本文对GRANULE算法在不可能差分分析下的安全性进行研究, 对GRANULE算法进行具体介绍; 给出GRANULE算法的5轮不可能差分区分器, 以及11轮不可能差分分析。

1 GRANULE算法介绍

本节主要对本文出现的符号进行说明, 并介绍GRANULE算法的基本知识。首先给出符号说明如下:

1) L_i表示第i+1轮输入的左半分组;

2) R_i表示第i+1轮输入的右半分组;

3)ΔL_i表示2个输入L_i和L′_i的差分;

4)ΔR_i表示2个输入R_i和R′_i的差分;

5)>>>α表示循环右移α bits;

6) <<<β表示循环左移β bits;

7) K_i表示第i+1轮子密钥;

8) K_n^j-i表示第n+1轮子密钥的i bits到j bits;

9) s_i表示表示S·P(L_i);

10) r_i表示S·P(L_i)<<<2⊕S·P(L_i)>>>7。

GRANULE算法是最近提出的超轻量分组密码算法, 采用典型Feistel结构, 迭代轮数为32轮。该算法轮函数分别由P置换、S盒、循环移位、异或4种运算组成。其轮函数如图 1所示。

	Download: JPG larger image
图 1 GRANULE算法轮函数

GRANULE算法分组规模为64 bit, 密钥规模分为80 bit和128 bit 2种。算法中的非线性变换S盒、P置换及密钥编排算法的具体介绍如下:

1) 非线性变换S盒:GRANULE算法中使用4 bit S盒, 即S:{0, 1}⁴→{0, 1}⁴。S的具体变换以十六进制表示形式给出, 如表 1所示。

下载CSV 表 1 GRANULE算法中使用的S盒

2) P置换:将分组的左半部分分为8个0.5 Byte。经P置换将8个0.5 Byte的顺序进行重新排列, 其具体变换如表 2所示。

下载CSV 表 2 GRANULE算法的P置换

3) 密钥编排算法:GRANULE算法密钥规模分为80-bit和128-bit 2种, 其密钥扩展设计与PRESENT算法类似。密钥规模为80-bit和128-bit 2种版本的密钥编排算法类似, 仅主密钥规模不同。本文以密钥规模为80-bit为例, 详细介绍其密码编排算法。主密钥K=K₇₉K₇₈…K₁K₀存入密钥寄存器, 每一轮取寄存器最右端32 bits作为子密钥。扩展算法可表述为:

K = K₇₉K₇₈…K₁K₀

RK_i = K₃₁K₃₀…K₁K₀

在得到第i轮子密钥RK_i后, 按如下操作更新密钥寄存器:

1) K <<< 31;

2) [K₃K₂K₁K₀]←S[K₃K₂K₁K₀];

3) [K₇K₆K₅K₄]←S[K₇K₆K₅K₄];

4)[K₇₀K₆₉K₆₈K₆₇K₆₆]←[K₇₀K₆₉K₆₈K₆₇K₆₆]⊕[i]²。

2 GRANULE算法的5轮不可能差分区分器

定理1 对于GRANULE64算法, 当初始输入状态差分满足(ΔL₁, ΔR₁)=(0000 0000 0000 0000 0000 0000 0000 0000, 0000 0000 0000 0000 0000 0000 0000 0001)。经5轮GRANULE64算法加密后不存在满足(ΔL₆, ΔR₆)=(0000 0000 0001 0000 0000 0000 0000 0000, 0000 0000 0000 0000 0000 0000 0000 0000)的输出状态差分。

证明当初始输入状态差分满足(ΔL₁, ΔR₁)=(0000 0000 0000 0000 0000 0000 0000 0000, 0000 0000 0000 0000 0000 0000 0000 0001)时, 在第1轮中输出差分Δs₂(0000 0000 0000 a₁a₂a₃a₄ 0000 0000 0000 0000), 由S盒的性质可知a₁, a₂、a₃、a₄必不全为0。满足差分条件的(L₁, R₁)经三轮GRANULE加密算法后输出差分ΔR₄=(0000 0000 00a₁a₂ a₃a₄00 000a₁ a₂a₃a₄0 0000 0000)以概率1成立。

而当输出状态满足(ΔL₆, ΔR₆)=ΔL₆(0000 0000 0001 0000 0000 0000 0000 0000, 0000 0000 0000 0000 0000 0000 0000 0000)时, 初始状态(L₆, R₆)经两轮GRANULE算法解密后输出差分ΔR₄=(0000 0000 0000 0000 00a₁a₂ a₃a₄00 000a₁ a₂a₃a₄0)同样以概率1成立。

但由于a₁、a₂、a₃、a₄不全为0, 即(0000 0000 00a₁a₂ a₃a₄00 000a₁ a₂a₃a₄0 0000 0000)≠(0000 0000 0000 0000 00a₁a₂ a₃a₄00 000a₁ a₂a₃a₄0), 因此, 产生矛盾, 该结论成立。

定理1所描述的结构, 具体形式如图 2所示。

	Download: JPG larger image
图 2 GRANULE64算法的5轮不可能差分区分器

按照同样的构造思想, 除定理1给出的不可能差分区分器外, 还可以构造出GRANULE64算法如下8条5轮不可能差分区分器, 限于篇幅, 下文只给出具体的不可能差分对应, 不再给出相应的证明描述。

(00…0, 0000 0000 0000 0000 0000 0000 0001 0000)→(0000 0000 0001 0000 0000 0000 0000 0000, 00…0)

(00…0, 0000 0000 0000 0001 0000 0000 0000 0000)→(0000 0000 0001 0000 0000 0000 0000 0000, 00…0)

(00…0, 0000 0001 0000 0000 0000 0000 0000 0000)→(0000 0000 0001 0000 0000 0000 0000 0000, 00…0)

(00…0, 0001 0000 0000 0000 0000 0000 0000 0000)→(0000 0000 0001 0000 0000 0000 0000 0000, 00…0)

(00…0, 0000 0000 0000 0000 0000 0000 0000 0001)→(0000 0000 0000 0000 0000 0000 0001 0000, 00…0)

(00…0, 0000 0000 0000 0000 0000 0000 0000 0001)→(0000 0000 0000 0000 0001 0000 0000 0000, 00…0)

(00…0, 0000 0000 0000 0000 0000 0000 0000 0001)→(0000 0000 0000 0001 0000 0000 0000 0000, 00…0)

(00…0, 0000 0000 0000 0000 0000 0000 0000 0001)→(0000 0001 0000 0000 0000 0000 0000 0000, 00…0)

3 GRANULE64/80算法11轮不可能差分分析

利用图 2给出的5轮不可能差分区分器, 向上扩展3轮、向下扩展3轮得到11轮不可能差分路径。由于第1轮和最后一轮没有轮密钥的参与, 因此可以直接将这2轮算法剥离, 将11轮的攻击直接转化为9轮的攻击, 如图 3所示, 其中, 第1轮和最后一轮已剥离。

	Download: JPG larger image
图 3 GRANULE64算法的11轮不可能差分路径

本文结合密钥分割攻击及并行多条不可能差分区分器, 给出GRANULE64/80算法的11轮不可能差分攻击。

算法1 GRANULE64/80算法的11轮不可能差分攻击算法

算法步骤如下:

步骤1 选择的差分满足ΔL₀=(0000 0000 00a₁a₂a₃a₄00 000a₁ a₂a₃a₄0 0000 0000)ΔR₀=(b₁₄b₁₅b₁⊕b₁₆b₂ b₃b₄00 000b₁ b₂b₃b₄⊕b₅b₆ b₇b₈b₉b₁₀ b₁₁b₁₂b₁₃b₁₄⊕b₅ b₁₅⊕b₆b₁₆⊕b₇b₈b₉00 b₁₀b₁₁b₁₂b₁₃⊕1)的明文对, 其中, a₁、a₂、a₃、a₄不全为0, b₁、b₂、b₃、b₄、b₅、b₆、b₇、b₈、b₉、b₁₀、b₁₁、b₁₂、b₁₃、b₁₄、b₁₅、b₁₆也不全为0。则攻击的选择明文量为2ⁿ⁺²⁰, 可以构造2³⁹⁺ⁿ个明文对。

步骤2 首先筛选密文对。筛选出满足如下差分的密文对:

ΔL₉(d₁₀b₁₁b₁₂b₁₃ b₁₄b₁₅b₁₆0 00d₁b₂⊕1 b₃b₄b₅b₆ b₇b₈0b₁ b₂b₃b₄⊕b₉b₅⊕b₁₀ b₆⊕b₁₁b₇⊕b₁₂b₈⊕b₁₃b₁₄ b₁₅b₁₆0b₉) ΔR₉(0000 0000 0000 0000 00c₁c₂ c₃c₄00 000c₁ c₂c₃c₄0), 其中, c₁、c₂、c₃、c₄不全为0, d₁, b₂, …, b₁₆不全为0。经该步筛选后平均剩余2ⁿ⁺³⁹×2^－44=2^n－5个数据对。

步骤3 猜测子密钥K₁₀^15－0。对于剩余2^n－5个数据对, 筛选出满足ΔR₈(0000 0000 0001 0000 0000 0000 0000 0000)的数据对。经该步筛选后平均剩余2^n－5×2^－16=2^n－21个数据对, 计算复杂度大约为2^n－5×2¹⁶×2=2ⁿ⁺¹²次一轮加密运算。

步骤4 猜测子密钥K₉^23－20。对于剩余2^n－21个明文对, 筛选出满足ΔR₇(0000 0000 0000 0000 0000 0000 0000 0000)的数据对。经这一步筛选后平均剩余2^n－21×2^－4=2^n－25个数据对, 计算复杂度大约为2^n－21×2¹⁶×2⁴×2=2ⁿ次一轮加密运算。

步骤5 猜测子密钥K₀^23－8。对于剩余2^n－25个明文对, 筛选出满足ΔL₁(0000 0000 0000 0000 0000 0000 0000 0001)的数据对。经这一步筛选后平均剩余2^n－25×2^－16=2^n－41个数据对, 计算复杂度大约为2^n－25×2¹⁶×2⁴×2¹⁶×2=2ⁿ⁺¹²次一轮加密运算。

步骤6 猜测子密钥K₁^3－0。对于剩余的数据对, 筛选出差分满足ΔL₂(0000 0000 0000 0000 0000 0000 0000 0000)的数据对。经这一轮加密以2^－4的概率得到不可能差分区分器的输入, 此时所猜测的密钥K₁₀^15－0、K₉^23－20、K₀^23－8、K₁^3－0是错误密钥。这一步计算复杂度约为2^n－41×2¹⁶×2⁴×2¹⁶×2⁴×2=2ⁿ次一轮加密运算。

定理2 利用5轮不可能差分区分器对11轮GRANULE64/80算法进行不可能差分分析, 恢复80 bit主密钥, 其时间复杂度为2^73.3次11轮GRANULE64算法加密, 数据复杂度为2⁶⁴个选择明文。

证明在上述的攻击过程中, 算法1的选择明文量为2ⁿ⁺²⁰, 时间复杂度主要由第3步决定。

由密钥编排算法可知, 总共猜测40 bits密钥, 经步骤6排除错误密钥后大约剩余ε=2⁴⁰×(1－2^－4)^{2^n－41}个候选密钥, 若同时使用9条不可能差分区分器, 则ε=2⁴⁰×(1－2^－4)^{2^n－41×9}。再对候选密钥和剩余40 bits密钥进行穷举, 恢复密钥的时间复杂度为ε×2⁴⁰。

当n=44时, 算法1的选择明文量为2ⁿ⁺²⁰=2⁶⁴, 即数据复杂度为2⁶⁴个选择明文。算法1的总时间复杂度为2ⁿ⁺¹²×9/11+ε×2⁴⁰=2⁵⁶×9/11+2⁸⁰×(1－2^－4)^2³×9≈2^73.3次11轮GRANULE64算法加密, 即时间复杂度为2^73.3次11轮GRANULE64算法加密。

4 结束语

本文主要分析GRANULE64算法在不可能差分分析下的安全性。在算法5轮不可能差分区分器的基础上, 向加密方向与解密方向分别扩展3轮, 给出了对GRANULE64/80算法的11轮不可能差分分析。利用上述攻击算法可以恢复GRANULE64/80算法的主密钥, 时间复杂度为2^73.3次11轮GRANULE64算法加密, 数据复杂度为2⁶⁴个选择明文。但目前仍没有GRANULE64/128算法不可能差分分析的相关结果, 将有待进一步研究。

参考文献

[1]	BOGDANOV A, KNUDSEN L R, LEANDER G, et al.PRESENT: an ultra-lightweight block cipher[C]//Proceedings of CHES'07.Berlin, Germany: Springer, 2007: 450-466. (0)
[2]	GUO Jian, PEYRIN T, POSCHMANN A, et al.The LED block cipher[C]//Proceedings of CHES'11.Berlin, Germany: Springer, 2011: 326-341. (0)
[3]	WU Wenliang ZHANG Lei.LBlock: a lightweight block cipher[C]//Proceedings of International Conference on Applied Cryptography and Network Security.Berlin, Germany: Springer, 2011: 327-344. (0)
[4]	BEAULIEU R, SHORS D, SMITH J, et al.The SIMON and SPECK families of lightweight block ciphers[EB/OL].[2018-07-20].https://eprint.iacr.org/2013/404.pdf. (0)
[5]	BANSOD G, PISHAROTY N, PATIL A.GRANULE: an ultra lightweight cipher designfor embedded security[EB/OL].[2018-07-20].https://eprint.iacr.org/2013/404.pdf. (0)
[6]	KNUDSEN L.DEAL A 128 bit block cipher[D].Bergen, Norway: University of Bergen, 1998. (0)
[7]	BIHAM E, BIRVUKOV A, SHAMIR A. Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials[J]. Journal of Cryptology, 2005, 18(4): 291-311. DOI:10.1007/s00145-005-0129-3 (0)
[8]	MALA H, DAKHILALIAN M, RIJMEN V, et al.Improved impossible differential cryptanalysis of 7-Round AES-128[C]//Proceedings of INDOCRYPT'10.Berlin, Germany: Springer, 2010: 282-291. (0)
[9]	TEZCAN C, SELCAK A A. Improved improbable differential attacks on ISO standard CLEFIA:expansion technique revisited[J]. Information Processing Letters, 2016, 116(2): 136-143. DOI:10.1016/j.ipl.2015.09.010 (0)
[10]	BOURA C, NAYA-PLASENCIA M, SUDER V.Scrutinizing and improving impossible differential attacks: applications to CLEFIA, camellia, LBlock and Simon[C]//Proceedings of IEEE ASIACRYPT'14.Washington D.C., USA: IEEE Press, 2014: 179-199. (0)
[11]	KARAKOC F, DEMIRCI H, HARMANC A E.Impossible differential cryptanalysis of reduced-round LBlock[C]//Proceedings of IEEE WISTP'12.Washington D.C., USA: IEEE Press, 2012: 179-188. (0)
[12]	LEE H C, KANG H C, HONG D, et al.New impossible differential characteristic of SPECK64 using MILP[EB/OL].[2018-07-20].http://eprint.iacr.org/2016/1137.pdf. (0)
[13]	KONDO K, SASAKI Y, IWATA T.On the design rationale of Simon block cipher: integral attacks and impossible differential attacks against Simon variants[C]//Proceedings of IEEE ACNS'16.Washington D.C., USA: IEEE Press, 2016: 518-536. (0)
[14]	谢高淇, 卫宏儒. ARIA分组密码算法的不可能差分攻击[J]. 计算机研究与发展, 2018, 55(6): 1201-1210. (0)
[15]	崔竞一, 郭建胜, 刘翼鹏. Crypton算法的不可能差分分析[J]. 计算机研究与发展, 2017, 54(7): 1525-1536. (0)