Zodiac—128算法的多維零相關(guān)線性分析

程璐

摘 要 分組密碼算法Zodiac支持3種密鑰長(zhǎng)度，分別為Zodiac-128、Zodiac-192、Zodiac-256。該文首次利用零相關(guān)線性分析方法評(píng)估了Zodiac算法的安全性，首先根據(jù)算法的結(jié)構(gòu)特性，構(gòu)造了一些關(guān)于Zodiac算法的10輪零相關(guān)線性逼近，然后對(duì)14輪Zodiac-128進(jìn)行了多維零相關(guān)分析。其結(jié)果顯示：攻擊過(guò)程中一共恢復(fù)了10個(gè)字節(jié)的密鑰，大體需要2123.04個(gè)明密文對(duì)，計(jì)算復(fù)雜度為2109.19次14輪加密。由此可得：14輪128比特密鑰的Zodiac算法（Zodiac-128）對(duì)于零相關(guān)線性分析方法是不安全的。

【關(guān)鍵詞】分組密碼 Zodiac密碼算法 線性掩碼 線性逼近 零相關(guān)線性分析

1 預(yù)備知識(shí)

1.1 Zodiac算法簡(jiǎn)介

Zodiac算法的主體結(jié)構(gòu)采用Feistel結(jié)構(gòu)，共16輪迭代。在第一輪迭代之前有一個(gè)初始置換T，在最后一輪迭代之后有一個(gè)末置換T，并且在迭代前后分別異或于一個(gè)白化密鑰，其中：K0，K17為64bit的白化密鑰，為第i輪的輪密鑰，F(xiàn)為輪函數(shù)。每一輪變換分別由密鑰加K、線性變換P、非線性變換S構(gòu)成。輪函數(shù)的定義為：，其中X為64bit，可按字節(jié)表示為，P為線性變換，S為非線性變換。

2 Zodiac算法10輪零相關(guān)線性逼近

本文主要通過(guò)以下的方式來(lái)構(gòu)造零相關(guān)線性逼近：在相關(guān)系數(shù)非零條件下線性掩碼從前和從后兩個(gè)方向向中間傳播，最后在中間某個(gè)位置相遇，并且產(chǎn)生相關(guān)系數(shù)為零的矛盾狀態(tài)。在非零相關(guān)系數(shù)條件下線性掩碼在分組密碼各組件中有如下傳播規(guī)律。

證明 設(shè)定"0"表示零掩碼；表示非零掩碼；"？"表示不確定是零或非零的掩碼。從加密方向，若第r輪的輸入掩碼為，向加密方向經(jīng)過(guò)5輪迭代，在非零相關(guān)系數(shù)條件下第r+4輪左側(cè)輸出掩碼為，則其第8個(gè)字節(jié)為0掩碼；若第r+9輪的輸出掩碼為，向解密方向經(jīng)過(guò)5輪，在非零相關(guān)系數(shù)條件下第r+5輪右側(cè)輸入掩碼為，則其第8個(gè)字節(jié)為非0掩碼，與第r+4輪的狀態(tài)相矛盾。證畢。

3 14輪Zodiac-128的多維零相關(guān)分析

本章主要利用構(gòu)造的10輪（第3輪-第12輪）零相關(guān)線性逼近，并且往前擴(kuò)展2輪往后擴(kuò)展2輪，對(duì)14輪Zodiac-128作多維零相關(guān)線性分析，分析過(guò)程中不考慮初始置換和末置換以及白化密鑰的影響。

3.1 攻擊過(guò)程

（1）首先，取，則x0共有280種狀態(tài)，對(duì)每一種狀態(tài)建立一個(gè)48bit計(jì)數(shù)器，且全部初始化為零。收集N個(gè)明文及對(duì)應(yīng)的密文，并計(jì)算這些明密文對(duì)中滿足每個(gè)狀態(tài)的對(duì)數(shù)，相應(yīng)的計(jì)數(shù)器加1，此步驟大致需要N次內(nèi)存讀取。

（2）取，則x1共有264種狀態(tài)，對(duì)每一種狀態(tài)建立一個(gè)16bit計(jì)數(shù)器，且全部初始化為零。窮舉24bit輪子密鑰，計(jì)算并更新；；然后累加計(jì)數(shù)器。此步驟大致需要次內(nèi)存訪問(wèn)。

（3）取，則x2共有248種狀態(tài)，對(duì)每一種狀態(tài)建立一個(gè)16bit計(jì)數(shù)器，且全部初始化為零。窮舉16bit輪子密鑰，計(jì)算并更新，然后累加計(jì)數(shù)器。此步驟大致需要次內(nèi)存訪問(wèn)。

（4）取，則x3共有232種狀態(tài)，對(duì)每一種狀態(tài)建立一個(gè)16bit計(jì)數(shù)器，且全部初始化為零。窮舉24bit輪子密鑰，計(jì)算并更新；，然后累加計(jì)數(shù)器。此步驟大致需要次內(nèi)存訪問(wèn)。

（5）取，則x4共有216種狀態(tài)，對(duì)每一種狀態(tài)建立一個(gè)16bit計(jì)數(shù)器，且全部初始化為零。窮舉16bit輪子密鑰，計(jì)算并更新，然后累加計(jì)數(shù)器。此步驟大致需要次內(nèi)存訪問(wèn)。

（6）是16bit向量，為每一個(gè)可能的建立一個(gè)16bit計(jì)數(shù)器，且全部初始化為零。對(duì)于16個(gè)長(zhǎng)度為16bit的基礎(chǔ)向量，即1是第i+1個(gè)比特為1，其他比特為0的向量。計(jì)算，，并且計(jì)算，然后累加計(jì)數(shù)器。根據(jù)式（2），計(jì)算統(tǒng)計(jì)量T。

（7）如果，則所猜測(cè)的輪子密鑰可能為正確密鑰，窮盡搜索所有可能的正確密鑰。

4 結(jié)語(yǔ)

本文主要評(píng)估了Zodiac密碼算法關(guān)于多維零相關(guān)線性分析方法的安全性。首先利用Zodiac算法結(jié)構(gòu)特點(diǎn)，構(gòu)造了10輪零相關(guān)線性逼近，之后對(duì)14輪的Zodiac-128進(jìn)行了多維零相關(guān)線性分析。整個(gè)攻擊過(guò)程中共恢復(fù)了10個(gè)字節(jié)的密鑰，所以，14輪Zodiac-128對(duì)多維零相關(guān)線性分析是不安全的。進(jìn)一步的研究方向就是通過(guò)分析算法的結(jié)構(gòu)特點(diǎn)、密鑰擴(kuò)展算法等來(lái)降低其數(shù)據(jù)復(fù)雜度。

參考文獻(xiàn)

[1]LEE C，JUN K，and JUNG M，et al.Zodiac version1.0（revised） architecture and specification Standardization Workshop on Information Security Technology， Korean Contribution on MP18033，ISO/IEC JTC1/SC27 N2563，2000.http：//www.kisa.or.k ndex.html.

[2]BOGDANOV A，RIJMEN V.Linear hulls with correlation zero and linear cryptanalysis of block ciphers [J].Designs，Codes and Cryptography，2014，70（03）：369-383.

[3]BOGDANOV A，WANG M.Zero correlation linear cryptanalysis with reduced data complexity[C].FSE 2012， Washington，DC，USA，2012：29-48.

[4]BOGDANOV A，LEANDER G，NYBERG K，et al.Integral and multidimensional linear distinguishers with correlation zero [C]// Proceedings of the ASIACRYPT 2012，Beijing， China，2012：244-261.

作者單位

武警工程大學(xué) 陜西省西安市 710086endprint