葛欣欣，李智虎，王美琴，胡凱

LowMC實(shí)例的差分枚舉攻擊效果分析

葛欣欣1,2，李智虎3，王美琴1,2，胡凱1,2

（1. 山東大學(xué)網(wǎng)絡(luò)空間安全學(xué)院（研究院），山東 青島 266237；2. 山東大學(xué)密碼技術(shù)和信息安全教育部重點(diǎn)實(shí)驗(yàn)室，山東 青島 266237；3. 中國(guó)電力科學(xué)研究院有限公司，北京 100192）

LowMC是具有低乘法復(fù)雜度特征的算法。針對(duì)低數(shù)據(jù)量和少量S盒參數(shù)下的LowMC實(shí)例，差分枚舉攻擊被提出，理論上可以攻擊全輪LowMC算法?？紤]到這種攻擊是在線性層完全隨機(jī)的條件下給出的，對(duì)LowMC算法在真實(shí)的線性層下抵抗差分枚舉攻擊的強(qiáng)度進(jìn)行了研究。通過對(duì)關(guān)鍵起始輪數(shù)的研究發(fā)現(xiàn)，差分枚舉攻擊并非總是可以達(dá)到理論攻擊輪數(shù)。對(duì)于某一些關(guān)鍵起始輪數(shù)比理論值小的LowMC實(shí)例，差分枚舉攻擊甚至?xí)?。由于LowMC算法的輪數(shù)設(shè)置基于現(xiàn)有攻擊的效果，該分析對(duì)LowMC算法的輪數(shù)設(shè)計(jì)具有重要意義。

分組密碼；LowMC算法；差分枚舉攻擊；關(guān)鍵起始輪數(shù)

1 引言

Albrecht等[1]在2015年歐密會(huì)上提出了LowMC算法。LowMC算法基于SPN結(jié)構(gòu)，采用了部分非線性層和隨機(jī)線性層的設(shè)計(jì)，其乘法復(fù)雜度非常低。LowMC實(shí)例是通過改變分組長(zhǎng)度、密鑰長(zhǎng)度、每輪S盒的數(shù)量和數(shù)據(jù)復(fù)雜度的安全預(yù)期得到的。LowMC算法的低乘法復(fù)雜度特點(diǎn)使它在多方計(jì)算和全同態(tài)加密等場(chǎng)景下效率較高，自公開以后就受到了廣泛關(guān)注。

本文研究了差分枚舉攻擊對(duì)實(shí)例化后的LowMCv2算法的攻擊效果，發(fā)現(xiàn)對(duì)于某些參數(shù)的LowMC實(shí)例，差分枚舉攻擊的實(shí)際可攻擊輪數(shù)并不能達(dá)到理論計(jì)算值。差分枚舉攻擊的可攻擊輪數(shù)與LowMCv2算法的概率為1的差分路線（這條路線的輪數(shù)被稱為關(guān)鍵起始輪數(shù)）直接相關(guān)。為此，本文給出一種高效的計(jì)算LowMC算法概率為1的差分路線的方法。本文控制非線性層部分的差分狀態(tài)，保證S盒部分不引入差分、其他部分引入差分，建立差分傳播的線性方程組。之后通過高斯消元法[10]解方程組，可以得到概率為1的差分路線。實(shí)驗(yàn)發(fā)現(xiàn)，無論是在LowMC算法設(shè)計(jì)者推薦的線性矩陣下，還是任意隨機(jī)矩陣下，關(guān)鍵起始輪數(shù)都有很大概率無法達(dá)到理論值，也就是說，差分枚舉攻擊并不總是可以達(dá)到理論的攻擊輪數(shù)。對(duì)于某些特殊參數(shù)下的LowMC算法實(shí)例，差分枚舉攻擊甚至?xí)?。在LowMCv3算法中，考慮了差分枚舉攻擊的可攻擊輪數(shù)，重新定義LowMC算法的輪數(shù)。本文對(duì)差分枚舉攻擊的實(shí)際攻擊效果分析表明，LowMCv3算法的輪數(shù)可以適當(dāng)降低，以提升LowMCv3算法的實(shí)現(xiàn)效率。

2 差分枚舉攻擊及在LowMC算法的應(yīng)用

2.1 LowMC算法描述

由個(gè)3 bit S盒組成。非線性層中采用了具有低代數(shù)次數(shù)、低乘法復(fù)雜度等特點(diǎn)的S盒，S盒為 。此時(shí)要求和的關(guān)系滿足，當(dāng)時(shí)，剩余的位狀態(tài)直接進(jìn)入線性層。

Figure 1 The round function of LowMC

LowMC算法的分組長(zhǎng)度、密鑰長(zhǎng)度、每輪S盒的數(shù)量和可承受攻擊的數(shù)據(jù)復(fù)雜度是可以根據(jù)應(yīng)用場(chǎng)合改變的參數(shù)，被稱為可變參數(shù)。為了適用于多種應(yīng)用場(chǎng)合，可變參數(shù)調(diào)整得到不同的實(shí)例。對(duì)于不同的實(shí)例，LowMC算法輪數(shù)是根據(jù)可變參數(shù)現(xiàn)存的有效攻擊計(jì)算得到的，所以正確分析每個(gè)攻擊的可攻擊輪數(shù)，對(duì)于LowMC算法來說至關(guān)重要。LowMC算法線性層的特點(diǎn)是隨機(jī)選取且相互獨(dú)立的。在保證隨機(jī)性、可靠性、快速生成有效隨機(jī)位的前提下，設(shè)計(jì)者推薦用Grain算法中的線性反饋移位寄存器（LFSR, linear feedback shift register）[11]作為自收縮發(fā)生器[12]生成線性層，預(yù)期這樣可以得到盡可能隨機(jī)化的線性層?？紤]到使用LFSR生成的線性矩陣存儲(chǔ)空間和計(jì)算消耗比較大，將線性層優(yōu)化為等價(jià)線性層[13]可以在不增加非線性操作和不危及安全性的同時(shí)，減少線性代數(shù)復(fù)雜度。

2.2 差分枚舉攻擊在LowMC算法上的應(yīng)用

定義2 關(guān)鍵起始輪數(shù)。

關(guān)鍵起始輪數(shù)定義為，在部分非線性層中，通過選擇合適的輸入差分，得到傳播概率為1的差分路線的長(zhǎng)度。

圖2 差分枚舉在LowMC算法上的應(yīng)用

Figure 2 Application of difference enumeration in LowMC

3 差分枚舉攻擊對(duì)線性層實(shí)例化后的LowMC算法的攻擊效果分析

在對(duì)LowMC算法實(shí)施差分枚舉攻擊時(shí)，部分非線性層的特性導(dǎo)致攻擊可以分為兩部分，第一部分是概率為1的關(guān)鍵起始輪數(shù)，第二部分是具有差分概率的差分?jǐn)U散輪數(shù)。為了保證可攻擊的輪數(shù)最大，或者以最小的時(shí)間復(fù)雜度攻擊全輪數(shù)，關(guān)鍵起始輪數(shù)一定要取到最大值。線性層作為提供擴(kuò)散性的組件，不僅影響密碼算法實(shí)現(xiàn)效率，也影響密碼算法安全性[16]。在具體線性層下，實(shí)際的關(guān)鍵起始輪數(shù)有可能無法達(dá)到理論值，因此造成差分枚舉攻擊達(dá)不到理論的攻擊輪數(shù)。對(duì)于某些參數(shù)下的LowMC算法實(shí)例，甚至?xí)羰　?/p>

3.1 差分枚舉攻擊在特定線性層下的關(guān)鍵起始輪數(shù)

步驟2 利用高斯消元法求解線性方程組，并對(duì)自由變量進(jìn)行遍歷，得到符合條件的非零差分路線。

實(shí)例1 Grain算法中的LFSR作為自收縮發(fā)生器生成線性層。

實(shí)例2 2019年歐密會(huì)提出的LowMC算法的線性層。

LowMC算法為了減少乘法復(fù)雜度，采用了部分非線性層的設(shè)計(jì)，同時(shí)為了彌補(bǔ)部分非線性層帶來的混淆不充分，采用了高代數(shù)次數(shù)的隨機(jī)矩陣為線性層增強(qiáng)擴(kuò)散度，這給LowMC算法的實(shí)現(xiàn)帶來了負(fù)擔(dān)。Dinur等[13]在2019年歐密會(huì)上提出在每個(gè)LowMC實(shí)例等價(jià)類中存在線性等價(jià)性，可以在每個(gè)實(shí)例類中得到一個(gè)最優(yōu)線性層，并伴隨著加解密算法的優(yōu)化。針對(duì)這種優(yōu)化下的線性層，本文進(jìn)行了4差分下的關(guān)鍵起始輪數(shù)是否可達(dá)到理論值的判斷，結(jié)果是在4差分下不可達(dá)到理論的42輪關(guān)鍵起始輪數(shù)，實(shí)際關(guān)鍵起始輪數(shù)為41輪。等價(jià)線性層在4差分下不可達(dá)到理論關(guān)鍵起始輪數(shù)的這一結(jié)果和對(duì)Grain算法中LFSR生成的線性層測(cè)試得到的結(jié)果一致。

實(shí)例3 真隨機(jī)數(shù)生成的LowMC算法線性層。

本文使用C++語言中的random_device真隨機(jī)數(shù)生成庫，驗(yàn)證隨機(jī)生成的線性矩陣的實(shí)際關(guān)鍵起始輪數(shù)是否和其他特定選取算法下生成的線性矩陣的實(shí)際關(guān)鍵起始輪數(shù)相同。利用隨機(jī)數(shù)生成器生成20 000組LowMC實(shí)例的42輪線性矩陣，計(jì)算關(guān)鍵起始輪數(shù)可以達(dá)到42輪的差分路線個(gè)數(shù)，實(shí)驗(yàn)結(jié)果見表1。由表1可知，使差分路線個(gè)數(shù)達(dá)到7條的線性矩陣有4 416組，占總數(shù)的22.08%；使差分路線個(gè)數(shù)達(dá)到15條以上的線性矩陣有233組，占總數(shù)的1.17%；剩余的線性矩陣使差分路線個(gè)數(shù)為3條，占總數(shù)的76.75%，即隨機(jī)選取線性矩陣只有23.25%的概率可達(dá)到4差分理論關(guān)鍵起始輪數(shù)42輪。

利用上述計(jì)算實(shí)際關(guān)鍵起始輪數(shù)的步驟1～步驟4，可以計(jì)算實(shí)際關(guān)鍵起始輪數(shù)，從而確定非零差分路線個(gè)數(shù)和實(shí)際關(guān)鍵起始輪數(shù)的聯(lián)系。隨機(jī)選取3 000次LowMC線性矩陣，計(jì)算4差分下的最長(zhǎng)關(guān)鍵起始輪數(shù)，實(shí)驗(yàn)結(jié)果見表2。實(shí)際關(guān)鍵起始輪數(shù)等于理論關(guān)鍵起始輪數(shù)的線性矩陣有721次，概率為24.03%，所占比例與上面7條差分路線個(gè)數(shù)的比例基本相同；不可達(dá)到理論關(guān)鍵起始輪數(shù)的線性矩陣有2 277次，所占比例為75.9%，此外，實(shí)際關(guān)鍵起始輪數(shù)大于理論關(guān)鍵起始輪數(shù)的線性矩陣有2次，所占比例可忽略不計(jì)。由此，可以認(rèn)為在線性矩陣下，實(shí)際關(guān)鍵起始輪數(shù)的差分路線個(gè)數(shù)為7條及以上時(shí)，可攻擊輪數(shù)與理論關(guān)鍵起始輪數(shù)相等；小于7條時(shí)，不可達(dá)到理論關(guān)鍵起始輪數(shù)。

表1 隨機(jī)線性矩陣下的滿足理論關(guān)鍵起始輪數(shù)的差分路線數(shù)量注1

注1：線性矩陣由random_device庫生成，分組長(zhǎng)度為128 bit，每輪1個(gè)S盒，差分維度為4，理論關(guān)鍵起始輪數(shù)為42輪。

表2 隨機(jī)線性矩陣下的實(shí)際關(guān)鍵起始輪數(shù)注1

3.2 LowMC算法輪數(shù)設(shè)置分析

為了確定保證LowMC算法安全性下的最低輪數(shù)，對(duì)大部分標(biāo)準(zhǔn)攻擊進(jìn)行評(píng)估，得到第二版建議輪數(shù)。

LowMC算法的分組長(zhǎng)度、密鑰長(zhǎng)度、每輪S盒數(shù)量等參數(shù)是可變的，不同參數(shù)的加密算法特征和適用范圍有所不同。特別地，令每輪S盒數(shù)量和數(shù)據(jù)量都取較小值，這種少量S盒、低數(shù)據(jù)量參數(shù)下的LowMC實(shí)例可用于非交互式零知識(shí)證明的公鑰簽名方案的加密算法。針對(duì)這種參數(shù)下的LowMC實(shí)例提出的差分枚舉攻擊影響了第三版輪數(shù)的計(jì)算。經(jīng)過LowMCv2算法輪數(shù)和差分枚舉攻擊輪數(shù)計(jì)算，由Grain算法的LFSR生成線性矩陣，以128 bit分組長(zhǎng)度、1個(gè)S盒、差分維度取4為例，得到理論上不可抵抗差分枚舉攻擊，而實(shí)際可抵抗差分枚舉攻擊的參數(shù)見表3。由此實(shí)例可見，在實(shí)際的差分枚舉攻擊下，差分枚舉攻擊可能會(huì)失敗。為了抵抗差分枚舉攻擊，第三版LowMC算法（LowMCv3）更改了輪數(shù)計(jì)算方法。LowMCv3算法的輪數(shù)為差分攻擊、線性攻擊、飛去來器攻擊、插值攻擊、差分枚舉攻擊等一系列攻擊的最大輪數(shù)。由上述分析結(jié)果可知，在特定參數(shù)類型的部分LowMC實(shí)例下，差分枚舉攻擊并不總是可以達(dá)到理論攻擊輪數(shù)，因此，針對(duì)此類參數(shù)，LowMCv3算法的輪數(shù)可以適當(dāng)降低，進(jìn)一步提升實(shí)現(xiàn)效率。

表3 理論與實(shí)際差分枚舉攻擊對(duì)比注2

注2：線性矩陣由Grain算法的LFSR生成，分組長(zhǎng)度為128 bit，1個(gè)S盒，差分維度為4。

4 結(jié)束語

本文主要對(duì)少量S盒、低數(shù)據(jù)量參數(shù)下的LowMC實(shí)例的差分枚舉攻擊效果進(jìn)行分析，利用高斯消元法對(duì)加密過程中構(gòu)建的線性方程組進(jìn)行求解，得到差分枚舉攻擊的實(shí)際關(guān)鍵起始輪數(shù)。實(shí)驗(yàn)結(jié)果表明，對(duì)于某些LowMC算法實(shí)例，實(shí)際關(guān)鍵起始輪數(shù)往往小于其理論值。實(shí)際和理論的關(guān)鍵起始輪數(shù)的差異導(dǎo)致差分枚舉攻擊的實(shí)際攻擊效果達(dá)不到預(yù)期，通過改變LowMC算法的線性層，可以得到多個(gè)LowMC算法的實(shí)例。這些實(shí)例中，僅有23.25%的實(shí)例可以被差分枚舉攻擊成功攻破。對(duì)于剩余的LowMC實(shí)例，差分枚舉攻擊必須通過減少差分維度或關(guān)鍵起始輪數(shù)來保證攻擊可行性。由于LowMCv3部分實(shí)例的輪數(shù)主要考慮了差分枚舉攻擊的效果，這部分LowMCv3算法的實(shí)例可以適當(dāng)減少輪數(shù)以提升實(shí)現(xiàn)效率。

[1] ALBRECHT M R, RECHBERGER C, SCHNEIDER T, et al. Ciphers for MPC and FHE[C]//EUROCRYPT. 2015: 430-454.

[2] DINUR I, LIU Y W, MEIER W, et al. Optimized interpolation attacks on LowMC[C]//ASIACRYPT. 2015: 535-560.

[3] DOBRAUNIG C, EICHLSEDER M, MENDEL F. Higher-order cryptanalysis of LowMC[C]//ICISC. 2015: 87-101.

[4] CHASE M, DERLER D, GOLDFEDER S, et al. Post-quantum zero-knowledge and signatures from symmetric-key primitives[C]// ACM Conference on Computer and Communications Security. 2017.

[5] RECHBERGER C, SOLEIMANY H, TIESSEN T. Cryptanalysis of low-data instances of full LowMCv2[C]//IACR Trans Symmetric Cryptol. 2018: 163-181.

[6] DEMIRCI H, SEL?UK A A. A meet-in-the-middle attack on 8-round AES[C]//FSE. 2008: 116-126.

[7] DUNKELMAN O, KELLER N, SHAMIR A. Improved single-key attacks on 8-round AES-192 and AES-256[C]//ASIACRYPT. 2010: 158-176.

[8] 陳少真, 魯林真. 對(duì)8輪ARIA算法的差分枚舉攻擊[J]. 電子與信息學(xué)報(bào), 2011, 33(7): 1770-1774.

CHEN S Z, LU L Z. Differential enumeration attack on ARIA[J]. Journal of Electronics and Information Technology, 2011, 33(7): 1770-1774.

[9] 崔競(jìng)一. 基于中間相遇思想的攻擊方法研究[D]. 鄭州: 信息工程大學(xué), 2017.

CUI J Y. Research on cryptanalysis based on meet-in-the-middle[D]. Zhengzhou: Information Engineering University, 2017.

[10] 王萼芳, 石明生. 高等代數(shù)(第三版)[M]. 北京: 高等教育出版社, 2003.

WANG E F, SHI M S. Advanced algebra (third edition)[M]. Beijing: Higher Education Press, 2003.

[11] HELL M, OHANSSON T, MAXIMOV A, et al. The grain family of stream ciphers[J]. The?eSTREAM Finalists, 2008: 179-190.

[12] MEIER W, STAFFELBACH O. The self-shrinking generaTor[C]//EUROCRYPT. 1994: 205-214.

[13] DINUR I, KALES D, PROMITZER A, et al. Linear equivalence of block ciphers with partial non-linear layers: application to LowMC[C]//EUROCRYPT. 2019: 343-372.

[14] TIESSEN T. Polytopic cryptanalysis[C]//EUROCRYPT. 2016: 214-239.

[15] NYBERG K. Differentially uniform mappings for cryptography[C]//EUROCRYPT. 1993: 55-64

[16] 李鵬飛. 基于密碼結(jié)構(gòu)的擴(kuò)散層構(gòu)造[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 2017, 3(6): 65-76.

LI P F. Construction of diffusion layers based on cipher structures[J]. Chinese Journal of Network and Information Security, 2017, 3(6): 65-76.

Effect of the difference enumeration attack on LowMC instances

GEXinxin1,2, LI Zhihu3, WANGMeiqin1,2, HU Kai1,2

1.School of Cyber Science and Technology, Shandong University, Qingdao 266237, China 2. Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Qingdao 266237, China 3.China Electric Power Research Institute, Beijing 100192, China

The LowMC is an algorithm with low multiplicative complexities. For the parameter with limited data complexities and low number of S-boxes, the difference enumeration attack was proposed, which could theoretically attack all rounds of the LowMC. Considering that the original attack is based on the random linear layer,the strength of LowMC algorithm against differential enumeration attacks under a specific linear layer deserves more study. The difference enumeration attack cannot reach theoretical rounds through the research on the so-called key initial round. In terms of some LowMC instances, the key initial round is smaller than the theoretical value, which leads to the failure of the difference enumeration attack. Since the number of rounds of the LowMC is completely based on existing attacks, the analysis is of great significance to the rounds design of the LowMC.

block cipher, LowMC algorithm, difference enumeration attack, key initial round

TN918.1

A

10.11959/j.issn.2096?109x.2021046

2021?01?10；

2021?03?15

王美琴，mqwang@sdu.edu.cn

國(guó)家自然科學(xué)基金（62002201，62032014）；國(guó)家重點(diǎn)研發(fā)計(jì)劃（2018YFA0704702）；山東省重大科技創(chuàng)新項(xiàng)目（2019JZZY010133）；山東省自然科學(xué)基金重大基礎(chǔ)研究項(xiàng)目（ZR202010220025）

The National Natural Science Foundation of China (62002201, 62032014), The National Key R&D Program of China (2018YFA0704702), The Major Scientific and Technological Innovation Project of Shandong Province (2019JZZY010133), The Major Basic Research Project of Natural Science Foundation of Shandong Province, (ZR202010220025)

葛欣欣, 李智虎, 王美琴, 等. LowMC實(shí)例的差分枚舉攻擊效果分析[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 2021, 7(3):149-155.

GE X X, LI Z H, WANG M Q, et al. Effect of the difference enumeration attack on lowMC instances[J]. Chinese Journal of Network and Information Security, 2021, 7(3): 149-155.

葛欣欣（1997? ），女，吉林四平人，山東大學(xué)碩士生，主要研究方向?yàn)榉纸M密碼分析。

李智虎（1975? ），男，安徽望江人，中國(guó)電力科學(xué)研究院有限公司高級(jí)工程師，主要研究方向?yàn)槊艽a理論和密碼工程。

王美琴（1974? ），女，寧夏銀川人，山東大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)閷?duì)稱密碼算法的設(shè)計(jì)和分析。

胡凱（1992? ），男，山東臨沂人，山東大學(xué)博士生，主要研究方向?yàn)閷?duì)稱密碼的分析。