共通ブロック暗号 CIPHERUNICORN-A の安全性に関する詳細調査報告書

2001 年 度

東京理科大学金子 敏信

共通鍵ブロック暗号  の安全性に関する詳細調査報告

概 要
本資料は、共通鍵ブロック暗号   の安全性に関する詳細報告書である。本暗号の差分攻撃及び線形攻撃に対する耐性について詳細に検討した。それぞれの攻撃法に対する安全性に関する結果は、以下のようにまとめられる。
差分攻撃
提案者による  関数近似は、安全側への評価であるという意味で、適切な近似であることを確認した。しかし 、トランケート差分探索による最大差分特性確率は、  となり、 ビットブロック暗号に期待される確率を上回る。よって、
 関数を用いたトランケート差分評価では   の差分攻撃に対する安全性を示すことはできなかった。
線形攻撃
提案者による  関数近似は、安全側への評価であるという意味で、適切な近似であることを確認した。また、最大線形特性確率は   となり、自己評価書とは異なる値を得たが、 ビットブロック暗号に期待される確率を下回っているため線形攻撃に対する安全性という面では問題はない。

 はじめに   において、 は「安全性について、今のところ問題は見つかっていない。複雑な構造のため、正確な評価が難しく、継続的な評価が必要である。」とされている。そのため本稿では、  関数近似の妥当性に着目し、 の差分攻撃及び線形攻撃に対する再評価を実施した。
第２章では、自己評価書の問題点と本報告書の評価手法について述べる。第３章では、差分攻撃に対する耐性について述べ、第４章では線形攻撃に対する耐性について述べる。そして第５章で、上記の結果をまとめ結論として示す。



問題点の指摘と本報告書の評価手法

自己評価書における問題点 は  関数内部において  ビット鍵加算、 ビット定数乗算等の算術演算を用いていることから、従来の方法で差分確率及び線形確率を導出することは困難であるため、自己評価書において提案者は  関数を近似した
 関数を定義し 、それを用いて安全性評価を行っている。しかしながらその近似について  関数の近似の妥当性
  関数の最大差分確率あるいは最大線形確率の妥当性
 連接する  関数の独立性が評価上の問題点として指摘されている 。ここでは各問題点について考察を行い、本稿での評価手法を述べる。



解析に当たっての近似とその妥当性

本暗号は、 関数（ 図  ）内部の演算において  ビット鍵加算、 ビット定数乗算等の算術演算を用いていることから、従来から知られている手法では厳密に差分確率や線形確率を求めることは計算量的に困難である。提案者による安全性
解析では、 関数に対して次のような近似を行った関数 （図  ）を定義し 、 関数を用いた  型ブロック暗号の安全性を評価している。

! 算術加算は、排他的論理和に置き換える。
0xfe21464b0x7e167289

SKa
temporary key
generation
mechanism

T1

T1

T0

T0

T0T0

SKb>>20x3^^0x7e1672890x30xfe21464b
0x7e167289 FKaXlYl
mainstream

Tk

Tk

T3

T3

T2

T2 T1

T1 T0

T0A302341FKbYr

Xr
0xfe21464b

図

 関数

A3図

 関数

! 定数乗算は、 ビットデータの上位１バイトへ入力ビットを集める処理、すなわち下位３バイトを上位１バイトへ排他的論理和する処理とする。
!  関数は、ローテイトシフト数を考慮し 、バイト全体に差分値が入る場合とそうでない場合の場合分けを行う。
（ 差分攻撃時）!  関数は、  関数以降の本流処理と一時鍵生成部処理においてど ちらも入力マスク値が "  の場合には、  関数への入力マスク値を  とする。
（ 線形攻撃時）
さらに、変形した  関数ついて #$%&' (% 探索を用いてアクティブとなる  関数をカウントし 、 関数の各確率の乗算により最大差分特性確率、及び最大線形特性確率を求めている。
上記のように近似された暗号の強度評価結果を根拠として、もとの暗号の安全性を示そうとする場合、暗号の安全性が増すような変形操作や攻撃者に不利となる仮定が必要となってはならない。このような立場から、上記の近似に関する正当性について考察する。

算術加算の近似の妥当性

算術加算における最大差分確率及び最大線形確率は  である。また排他的論理和における最大差分確率及び最大線形確率は  である。従って少なくともこの近似は、差分確率及び線形確率を減少させる変形ではない。以上から提案者の用いた近似は妥当であると考える。よって、本稿でも同じ近似を使用する。

定数乗算の近似の妥当性

定数乗算の出力は、実際には  バイトの経路を伝って ヶ所の  関数入力に影響を及ぼす。これに対し 、上位バイトへ入力ビットを集めるというこの近似は 、処理直後の  関数に値を波及させる効果を表している。この近似は排他的論理和の線形回路で表され 、確率  で差分パス（ 線形パス) が伝わる形に評価しており、安全側の近似と考える。よって、本稿でも同じ近似を使用する。

差分攻撃時の  関数近似の妥当性

自己評価書の記述だけでは正確に意味を読みとることができなかったため、その妥当性は議論できない。本稿では、  関数の差分伝搬をビット単位で解析し 、その差分伝播をトランケート差分で表現することとした。なお、  関数に繋がる暗号系の各部分においてはトランケート差分で接続を考えているため、全体として攻撃者にとって有利な仮定であると考える。



線形攻撃時の  関数近似の妥当性

 関数以降の本流処理と一時鍵生成部処理においてど ちらも入力マスク値が"  の場合には、  関数への入力マスク値を  とするというのは、暗号系全体の特性確率を高めるという点で攻撃者にとって有利な仮定であると考える。本稿においては、  関数のトランケートパスの接続条件は、任意の接続が在り得るという条件設定で探索を行った。

 関数における連結した換字テーブル最大差分確率の妥当性

自己評価書において、提案者は連結した換字テーブルの最大差分確率を一つの換字テーブルの差分確率と等しく   としている。しかし 、差分確率の定義

 *+ +) " ,     *)  *  +) " +       に対して * ) " *  * )   * )   * )  * )) 、つまり  ビット入力、 ビット出力と見なして差分確率を計算したところ、最大差分確率は   となる。本稿における最大差分特性確率の計算は、この最大差分確率を用いて導出する。

最大線形確率の妥当性

自己評価書において、提案者は連結した換字テーブルの最大線形確率を求めている。本稿において再度計算を試みたところ、表  に示すとおり自己評価書と同様の値を得た。よって本稿における最大線形特性確率の計算は、この最大線形確率を用いて導出する。

 関数の独立性

提案者は最大差分特性確率または最大線形特性確率を求める際に 、  関数中のアクティブな  関数をカウントし 、最大差分確率または最大線形確率の乗算によって  関数の最大差分特性確率または最大線形特性確率を導出している。しかし 、アクティブな  関数が独立であるかという議論が欠けているため、これらの導出法には疑問が残る。この  関数の独立性に関しては、後述する。

-

表  換字テーブルの最大線形確率
連結状態

入力マスク " ０の場合

入力マスク＝０の場合



                                                                           







差分攻撃





提案者による自己評価 探索による  関数の最大差分特性確率

提案者は、自己評価書において  関数に対し入力差分値をバイト単位の . として全パターンを代入し 、通過した換字テーブルを調べた結果、図  のケースが差分特性確率
 を最大にし 、その値は " *  ) "   であると報告している。一般に、 関数の差分近似の出力差分値が  でない場合、その差分確率を としたときの  段の差分確率は最大で  となることから、/段において最終段の  関数出力を推定するための最大差分特性確率は、

   " であると報告している。

/"   A3

図  差分特性確率が最大になるケース（ 自己評価書）



本報告での評価

本稿では、  関数の入力側にバイト単位の . ですべてのパターンを代入し 、その時  関数の出力となりうるすべてのパターンを本流部 *下半分) に代入することにより通過した換字テーブルが最小となる入力パターンを探索した。この際、
 関数は、差分伝搬をビット単位で解析し 、その出力値をトランケート差分に置き換えることとした。ただし 、ここでは通過した  関数はそれぞれ独立であると仮定した。その結果、図  とは異なる最大差分特性確率が最大となるケースが存在した。新たに発見したケースを図 *&) 及び図 -*&) に示す。また、  関数での入出力において、この差分伝播が存在し得ることを確認した。そのようなビット列の一例を図 *0) 及び図 -*0) に示す。いずれのケースにおいても通過した  関数は  つとなり、同様のトランケート入出力差分 *100) が存在した。
このケースが新たに発見されたのは、排他的論理和演算の取扱いに起因することが一つの要因と考えられる。図 *&) における２カ所の排他的論理和演算（ 及び 2 部分）に着目し 、抽出したものを図 / に示す。 及び 2 における入出力は、

 "      "   と表せる。提案者は、どちらも単純な排他的論理和演算ととらえているため、 ""  はあり得ないとしている 。しかし 、 におい "  "  のときには  "ては定数乗算を近似した処理であるため、本稿では安全側への評価として  " を満足する が存在するものとした。本近似で使われている定数乗算におけるパターンの伝播は図 3 である。これら全てのパターンに対し 、実際に繋がることを

 提案者との議論により確認。

3

BAA3

 ルート  関数における入出力の例

図  差分特性確率が最大になるケース１（ 新たに見出したもの）



A
3

 ルート  関数における入出力の例

図 - 差分特性確率が最大になるケース２（ 新たに見出したもの）

4

A

Bx3x2x1x0yAx3x2x1x0yB

図 / 排他的論理和演算確認している。しかし 、残念ながら計算量の関係で繋がる確率を見出すまでにはいたっていない。
図  、- のケースにおける  関数の最大差分特性確率は、４並列換字テーブルの差分確率の最大値が   であることから

 " *  ) "   となる 。また、/ 段構成において最終段の  関数出力を推定するための最大差分特性確率は、出力差分値が  でないため

  " "   となる。これは提案者による自己評価書の結果と大きく異なる。

新たに見出した経路における  関数の独立性新たに見出した差分特性確率が最大になるケースにおいて、アクティブとなる
 関数は  つである。よって、この  関数は独立である。

耐差分攻撃についてのまとめ再探索の結果、トランケート差分の立場で自己評価書で報告されているよりも高い最大差分特性確率を得た。これは  ビットブロック暗号に期待される確率を上回っているため、  関数を用いたトランケート差分評価では  の差分攻撃に対する安全性を示すことはできなかった。
なお、トランケート差分について、どのような経路も定数乗算に対し認めた場合、図 で、 の最大差分パスが多数見出された。

以外

0x7e167289

0x7e167289

 パターン１

 パターン２0xfe21464b0x7e167289,0xfe21464b

  パターン３

  パターン４

0x7e167289,0xfe21464b
  パターン５

図 3 定数乗算のパターン



線形攻撃





提案者による自己評価 探索による  関数の最大線形特性確率

提案者は、自己評価書において  関数に対し線形マスク値をバイト単位の .
として全パターンを代入し 、通過した換字テーブルを調べた結果、図  のケースが線形特性確率
 を最大にし 、その値は







" **       ) で入力マスク " )
**       ) で入力マスク " )
**     ) で入力マスク " )"         "   であると報告している。一般に、 関数の入力マスク値が  の場合、その最大線形特性確率を としたときの  段の線形特性確率は最大で  となることから、/段において最終段の  関数出力を推定するための最大線形特性確率は、

" 

"   であると報告している。

本報告での評価

本稿では、  関数に対し線形マスク値をバイト単位の . として全パターンを代入し 、通過した換字テーブルを再度探索した。その際、すべての  関数は独立であると仮定した! この仮定に関する考察は後述する。その結果、図  とは異なる最大線形特性確率が最大となるケースが存在した。新たに発見したケースの一例を図 4 及び図  に示す。これらのケースが新たに発見されたのは、自己評価書の分岐におけるマスク値の流れを適切に評価していない可能性が一つの要因として考えられる。図  と図 4 及び図  の違いは、１次鍵生成部におけるアクティブな 関数における換字テーブルの連接数であり、３並列から４並列になった分、最大線形特性確率が上昇している。
図 4 のケースにおける  関数の最大線形特性確率は、

" **       ) で入力マスク " )
**       ) で入力マスク " )"      "   





A
3

図  線形特性確率が最大になるケース（ 自己評価書）となる。また、/ 段構成における最終段の  関数出力を推定するための最大線形特性確率は、入力マスク値が  なので" となる。

"   

A3

図 4 線形特性確率が最大になるケース１（ 新たに見出したもの）

A
3

図  線形特性確率が最大になるケース２（ 新たに見出したもの）





新たに見出した経路における  関数の独立性

新たに見出した線形特性確率が最大になるケースにおいて、アクティブな  関数はいずれも  つである。ケース１及びケース２において、図  及び図  の 、2 、 及び 5 で示した  関数の独立性は明らかではない。ケース  におけるこれらの  関数について考察を行う。また、ケース  でも同様である。

 

ここでは、. . の算術加算は排他的論理和で近似する。  関数
本流部
は排他的論理和加算に対し線形性を有し 、図  に示す等価鍵変形を行うことができる。図  の本流部について と 2 の独立性にかかわる部分を抜粋し 、このような等価鍵変形を行ったものが図  である。 6 の最上位バイトを 7 、 6 の最下位バイトを 7 とする。換字テーブルは全単射であることから、鍵 7.7 が全通り均等に発生したとき、 における  関数と 2 における  関数の入力は独立な値をとる。



一時鍵生成部図 - のように、算術加算鍵は等価変形で定数乗算の後に移動可能である。移動後の等価鍵加算を排他的論理和加算で近似する。図  の一時鍵生成部について、このような等価鍵変形を行ったものが図 / である。等価鍵 6の上位から  バイト目を 7 とする。拡大鍵の最上位バイトを 7 とする。換字テーブルは全単射であることから、鍵 7.7 が全通り均等に発生した時、 における  関数と 5 における  関数の入力は独立な値をとる。



以上の考察から 、ケース  及びケース  のいずれの経路においてもアクティブな  関数は独立であることから、前節における導出法で線形特性確率を見積もることができる。

-

C

DA3BA

図  考察する  関数部 *ケース )

CDA3BA図  考察する  関数部 *ケース )/A3 FKaFKb~ A3FKa~FKb
図  本流部におけるの等価鍵変形

K1~

A3FKaAB~

K2FKb

図  等価鍵変形を行ったケース  の本流部 *抜粋)

3C

SKa~

CSKa

図 - 一時鍵生成部における等価鍵変形

K3~

SKaC

DK4SKb図 / 等価鍵変形を行ったケース  の一時鍵生成部



耐線形攻撃についてのまとめ

 関数における再探索の結果、自己評価書よりも大きい線形特性確率を与えるケースを得ることができたが、  の段数が / 段であることを考慮すれば 、線形解読法に対して安全であると考えてよい。

結論

提案者による  関数近似は、安全側への評価であるという意味で、適切な近似であることを確認した。しかし 、トランケート差分探索による最大差分特性確率は、  となり、 ビットブロック暗号に期待される確率を上回る。よって、
 関数を用いたトランケート差分評価では   の差分攻撃に対する安全性を示すことはできなかった。そのため、可能な計算量で安全性を評価できるような別の  関数近似を提案者が示すことを望む。
一方、最大線形特性確率は   となり、自己評価書とは異なる値を得たが 、
 ビットブロック暗号に期待される確率を下回っているため線形攻撃に対する安全性という面では問題はないと言える。

参考文献
 日本電気株式会社. 8暗号技術応募書9暗号技術仕様書   8 日本電気株式会社. 8暗号技術応募書9自己評価書   8 情報処理振興事業協会セキュリティセンター. 8暗号技術評価報告書  8 ＮＴＴコミュニケーションズ供給. 8共通鍵ブロック暗号  の安全性に関する詳細調査報告8

4