序列密碼立方攻擊研究進(jìn)展綜述*

田 甜, 戚文峰

信息工程大學(xué), 鄭州 450001

1 引言

2000 年前后, 相關(guān)攻擊和代數(shù)攻擊的發(fā)展對基于線性反饋移位寄存器(LFSR) 的序列密碼算法的安全性構(gòu)成嚴(yán)重威脅.2004–2008 年, ECRYPT 啟動了序列密碼征集項(xiàng)目eSTREAM, 出現(xiàn)了一批基于非線性序列源的序列密碼算法.特別地, 非線性反饋移位寄存器(NFSR) 廣泛用于面向硬件實(shí)現(xiàn)的序列密碼算法, 例如eSTREAM 項(xiàng)目面向硬件實(shí)現(xiàn)的勝選算法Trivium 以及Trivium 的128 比特密鑰版本Kreyvium、Grain 系列算法等都是典型的基于NFSR 的序列密碼算法.采用NFSR 作為序列源, 可以有效抵抗針對基于LFSR 序列密碼算法的相關(guān)攻擊和代數(shù)攻擊.近十年, 立方攻擊是針對基于NFSR 序列密碼算法的重要攻擊方法, 在Trivium、Kreyvium、Grain 系列算法的安全性分析方面不斷取得新的進(jìn)展.目前, 在立方攻擊基礎(chǔ)上發(fā)展的攻擊方法有: 實(shí)驗(yàn)立方攻擊、基于可分性的立方攻擊、動態(tài)立方攻擊、相關(guān)立方攻擊等.

立方攻擊由Dinur 和Shamir 在2009 年歐密會上首次提出[1], 是一種高階差分攻擊和代數(shù)攻擊.立方攻擊的基本思想是通過對序列密碼的初始化向量(IV) 進(jìn)行差分, 獲得關(guān)于密鑰的低次方程組.在立方攻擊中, 每個立方集(cube) 對應(yīng)了一個關(guān)于密鑰的多項(xiàng)式, 稱為關(guān)于該立方集的超多項(xiàng)式(superpoly),其中立方集一般是IV 的一個仿射子空間.由于基于NFSR 的序列密碼是迭代型密碼算法, 經(jīng)過初始化算法后, 輸出密鑰流比特關(guān)于密鑰和IV 的代數(shù)正規(guī)型是未知的并且規(guī)模很大, 在文獻(xiàn)[1] 中, 自然將輸出密鑰流比特看作密鑰和IV 的黑盒布爾函數(shù), 通過線性檢測的方法……