Zodiac—128算法的多維零相關線性分析

程璐

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

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

1 預備知識

1.1 Zodiac算法簡介

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

2 Zodiac算法10輪零相關線性逼近

本文主要通過以下的方式來構造零相關線性逼近：在相關系數非零條件下線性掩碼從前和從后兩個方向向中間傳播，最后在中間某個位置相遇，并且產生相關系數為零的矛盾狀態。在非零相關系數條件下線性掩碼在分組密碼各組件中有如下傳播規律。

證明 設定"0"表示零掩碼；表示非零掩碼；"？"表示不確定是零或非零的掩碼。從加密方向，若第r輪的輸入掩碼為，向加密方向經過5輪迭代，在非零相關系數條件下第r+4輪左側輸出掩碼為，則其第8個字節為0掩碼；若第r+9輪的輸出掩碼為，向解密方向經過5輪，在非零相關系數條件下第r+5輪右側輸入掩碼為，則其第8個字節為非0掩碼，與第r+4輪的狀態相矛盾。證畢。

3 14輪Zodiac-128的多維零相關分析

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

3.1 攻擊過程

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

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

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

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

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

（6）是16bit向量，為每一個可能的建立一個16bit計數器，且全部初始化為零。對于16個長度為16bit的基礎向量，即1是第i+1個比特為1，其他比特為0的向量。計算，，并且計算，然后累加計數器。根據式（2），計算統計量T。

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

4 結語

本文主要評估了Zodiac密碼算法關于多維零相關線性分析方法的安全性。首先利用Zodiac算法結構特點，構造了10輪零相關線性逼近，之后對14輪的Zodiac-128進行了多維零相關線性分析。整個攻擊過程中共恢復了10個字節的密鑰，所以，14輪Zodiac-128對多維零相關線性分析是不安全的。進一步的研究方向就是通過分析算法的結構特點、密鑰擴展算法等來降低其數據復雜度。

參考文獻

[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.

作者單位

武警工程大學 陜西省西安市 710086endprint