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

2001 年 度

東京理科大学金子 敏信

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

概要
本資料は共通鍵ブロック暗号    の安全性に関する詳細報告書である。本暗号の差分攻撃及び線形攻撃に対する耐性について詳細に検討した結果、   の安全性について解読に結びつくような問題点は導かれなかった。それぞれの攻撃法に対する安全性に関する結果は、以下の様にまとめられる。
差分攻撃
提案者による 関数近似よりもより攻撃者に有利な近似を施した 関数を用いて探索した。その結果、最大差分確率は   となり、自己評価書とは異なる値を得たが  ビットブロック暗号に期待される確率を下回っているため差分攻撃に対する安全性という面では問題はない。
線形攻撃
提案者による 関数近似よりもより攻撃者に有利な近似を施した 関数を用いて探索した。その結果、最大差分確率は   となり、自己評価書とは異なる値を得たが  ビットブロック暗号に期待される確率を下回っているため差分攻撃に対する安全性という面では問題はない。

 はじめに   において    は「安全性について、今のところ問題は見つかっていない。複雑な構造のため、正確な評価が難しく、継続的な評価が必要である。」とされている 。そこで特に問題とされている差分解読および線形解読に対する耐性を検討した。第  節では自己評価書の記述に対して指摘された問題点を列挙し 、その問題点に対する対処について述べる。第  節では差分解読についての再検討を行う。第  節では線形解読についての再検討を行う。第  節ではそれぞれの検討の結果をまとめ結論として示す。



自己評価書の問題点と本報告書の評価手法

自己評価書における問題点   は  関数内部において  算術加算を用いており、従来の方法で差分確率及び線形確率を導出することは困難であることから、自己評価書において提案者が  関数を近似したラウンド 関数、  関数を定義し安全性評価を行っている。しかしながらその近似について  関数の近似の妥当性
  関数の最大差分確率あるいは最大線形確率
 連続した  関数の独立性
 ! 関数を考慮した評価が評価上の問題点として指摘されている 。ここでは各問題点について考察を行う。

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

本暗号は  関数内部の演算において  ビット鍵算術加算及び  ビットシフト
加算 " 関数# 、さらにデータ依存の換字テーブル等を用いていることから、従来から知られている手法では厳密に差分確率や線形確率を求めることは、計算量的に困難である。設計者による安全性解析では、 関数に対して次の様な変更を行った関数  を定義し 、  関数を用いた $% 型ブロック暗号の差分攻撃に対する安全性を評価している。

& 算術加算は排他的論理和に置き換える。
& 関数については、 ビットデータの上位  バイトへ入力ビットを集める処理、すなわち下位  バイトの排他的論理和を上位  バイトへ排他的論理和する処理とする。
上記の様に変更された暗号の強度評価結果を根拠として、もとの暗号の安全性を示そうとする場合、暗号の安全性が増す様な近似操作や、攻撃者に不利となる仮定が必要となってはならない。



算術加算の近似の妥当性

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

 関数の近似の妥当性

関数の近似には疑問点が残る。自己評価書には 関数の近似をどのように選んでだのかと言う点には触れられていない。提案者の用いた 関数近似は入力差分値及びマスク値に対し 、出力差分値及びマスク値が限定性を持ったものとなっている。したがって実際の 関数においては近似した 関数では示せない差分値もしくはマスク値が存在する可能性を捨てきれない。



本報告所の  関数の取り扱い

前項における疑問点を解決するために本報告所のパス探索においては内の 関数を以下のように取り扱う。

& 関数関数は任意の入力差分値及びマスク値に対し 、攻撃者に有利となる任意の出力差分値及びマスク値が存在する関数であるとする。

この取り扱いはもっとも攻撃者に有利な仮定であることを根拠とする。
この 関数で近似して '()*+ ,) 探索で最大差分特性確率および最大線形特性確率を求め評価する。



 関数における連結した換字テーブル



最大差分確率の妥当性

自己評価書において、提案者は連結した換字テーブルの最大差分確率を一つの換字テーブルの差分確率と等しく   としている。しかし 、実際は  関数は  つの - 関数の並列関数であるため、. 入力、 出力の関数とみなした場合必ずしも差分確率は   とならない。差分確率の定義

 "/ /# 0 1     "#  "  /# 0 /       に対して " # 0 "  " #  " #  " #  " ## として差分確率を計算したならば 、最大差分確率は   となる。本稿における '()*+ ,) 探索における差分特性
確率の評価はこの最大差分確率を用いて行う。

最大線形確率の妥当性

自己評価書において、提案者は連結した換字テーブルの最大線形確率を求めているが、  から  までの全ての換字テーブルに等しい値が入力されているにもかかわらず、  は独立しているものと考え、連結した換字テーブルの最大線形確率を求めている。しかし 、全ての換字テーブルを並列であると見なして、  から までの全ての連結パターンの最大線形確率を求めると違う結果となる。自己評価書との対比を表 2 に示す。例えば 、図  のように入力マスク 0
  で、  、  、 にマスクが入力した場合、自己評価書における  関数の最大線形確率 3 は、   0 "  # で入力マスク 0  × で入力マスク 0 

0   ×  0   となるが 、我々が求めた  関数の最大線形確率 3¼ は、

 ¼ 0 "    # で入力マスク 0 

0   となり、 関数ひとつでも異なる。本稿における '()*+ ,) 探索における線形特性確率の評価はこの最大線形確率を用いて行う。

  図  "# 関数- -
- -- -
---図  マスクが入力マスク 0  の場合

      22 に入力した場合

入力マスク 0  の場合

        表  連結した換字テーブルの最大線形確率（ 自己評価書）- -- -- -- -- -- -- - -
- - -
- - -
- - -
- - --

入力マスク 0  の場合

  
  
  
              


入力マスク 0  の場合

                      

表  連結した換字テーブルの最大線形確率（ 新たに算出）

関数中の  関数の独立性に関する考察

提案者は最大差分特性確率または最大線形特性確率を求める際に 、  関数中のアクティブな  関数をカウントし 、最大差分確率または最大線形確率の乗算によって  関数の最大差分特性確率または最大線形特性確率を導出している。しかし 、アクティブな  関数が独立であるかという議論が必要である。
この疑問点の考察のため  関数を図  のように等価変形する。図中の 4! 5の部分について、 関数はそれぞれバイトごとに独立な拡大鍵 5 が入力されるため、すべての  関数は独立となる。4! 5 の部分については 4! 5 と同様に拡大鍵 5 によって、 関数はすべて独立となる。4! 5 の部分は 6関数の直前に拡大鍵 -52-5 の下位  バイトを移動できる。5 関数は  関数の内で換字テーブルを通過するバイトへ、一次鍵生成部のデータを排他的論理和する関数であることから、4! 5 の  関数はすべて独立であることがわかる。また、4! 5 の  関数は独立な拡大鍵 -5 、-5 の上位２バイトが排他的倫理和されていることから、すべて独立であることがわかる。
以上の考察から  関数中のすべての  関数は独立となることがわかる。よって、少なくとも  関数の差分特性確率の導出法については、提案者の用いた評価法は妥当であると考える。
BLOCK4(SK3[1](SK3[0](SK2[1]SK1[1]
SK0[1]
3

321 0(SK2[0]SK1[0]SK0[0]21 0

321 0(SK3[0]SK3[1])FK[0]SK2[1])

FK[1](SK2[0]33321 021 0

321 0
3

321 0 KK

2 1 021 021 0

321 021 03BA

BLOCK33AD C B

BLOCK1BLOCK2

図  拡大鍵を移動した

21 03

 関数

関数を考慮した場合の最大差分特性確率、最大線形特性確率

自己評価書においてラウンド 数  における最大差分特性確率、最大線形特性確率の計算方法は、

"# ラウンド 関数の出力差分 / 0  、ラウンド 関数の入力マスク 7 0  の時、ラウンド 関数最大差分確率をとし 、ラウンド 関数最大線形確率を

 
 





とすると、"#"#となる。
"# ラウンド 関数の出力差分 / 0  、ラウンド 関数の入力マスク 7 0
  の時、ラウンド 関数最大差分確率を とし 、ラウンド 関数最大線形確率を とすると、

    "#"#となる。
しかし 、! 関数を考慮した場合、図  のような差分値およびマスク値の伝搬が考えられる。この場合、ラウンド 関数の出力差分 / 0  、ラウンド 関数の入力マス
ク7 0
  の時、ラウンド 関数最大差分確率を とし 、ラウンド 関数最大線形確率を とすると、






    

"#"#と計算できる。! 関数の内部で図  のようなパスが存在することは確認済みである。









図  最大差分特性確率、最大線形特性確率をあたえる差分値および 、マスク値の通り方8

差分攻撃



   探索による、関数の差分特性確率

上記の考察より 関数をブラックボックスとして見なした  関数を採用する。
 関数はすべての処理がバイト単位となるため、差分値をバイト単位の 2 です
べてのパターンを代入して通過した - 9 を調べ、  関数の最大差分特性確率を見積もった。-: テーブルによって構造が変化する部分については全てのパターンを場合分けして調査した。結果、提案者が主張するパス以外にも  関数を  回通過するパスが複数存在した。図  に提案者が主張するパスと同じパスを、図  に探索の結果判明したパスを示す。いずれの場合も出力差分は  である。出力差分値が  の場合、ラウンド 関数の差分特性確率をｐとした時、 段での差分特性確率は式 "# と計算できる。したがって  段での  関数の最大差分特性確率 ; は、

  0   ¢  0  "8#となり、&& 小節で述べた  関数  つの最大差分確率の分だけ確率は下がっている。
                    

  


  

  図  ラウンド 数  における最大差分特性確率が最大になるケース（自己評価書と同じパス）.

                          図  ラウンド 数  における最大差分特性確率が最大になるケース（ 新たに発見）

耐差分攻撃についてのまとめ探索結果により自己評価書と異なる最大差分特性確率を得たが、 
 の段数が  段であることを考慮すれば 、差分解読法に対して安全であると考えてよい。

<

線形攻撃   探索による関数の最大線形特性確率

差分解読法と同様に、自己評価書では  関数において '()*+ ,) 探索を利用して、ラウンド 関数の最大線形特性確率が   、 段での最大線形特性確率の上界が   であると評価している。自己評価書におけるラウンド 数が である場合の、最大線形特性確率が最大になるケースを図 8 に示す。
今回我々は、& 節で述べた ! 関数の効果を考慮した上で自己評価書と同じ '()*+ ,) 探索を利用して最大線形特性確率が最も大きくなるパスを探した。その際、 関数における換字テーブルに入力されるマスク値が  であるか否かで、表 の様に確率が変わることを配慮している。  関数は全ての処理がバイト単位になるので、線形マスク値をバイトごとの 2 で全てのパターンを代入して、通過した換字テーブルを調べ、-: テーブルで構造が変化する処理については全てのパターンを場合わけして調査した。ラウンド 数  における最大線形特性確率が最も大きくなるケースを図 . に示す。ラウンド 関数最大特性線形確率を求めると、

0   ¢   ¢    ¢   ¢  ¢    ¢0   となる。図 . では入力マスク値 0  であるが & 節で述べた ! 関数の効果を考えると、 段構成において最終段  関数出力を推定するための最大線形特性確率は、

   0 

0   となる。なお，図 . のマスクパターンが図  の様に ! 関数を通過することは確認ずみである。自己評価書との比較を表  に示す。
自己評価書
ラウンド 関数の最大特性線形確率 段での最大線形特性確率    本報告書

    

表  自己評価書との最大線形特性確率の比較          


  


              



図 8 ラウンド 数  における最大線形特性確率が最大になるケース（ 自己評価書）



  

            

  



      

  

  





図 . ラウンド 数  における最大線形特性確率が最大になるケース（ 新たに発見）

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

探索結果により自己評価書よりも大きい最大線形確率を得ることができたが 、   の段数が  段であることを考慮すれば 、線形解読法に対して安全であると考えてよい。また、提案者による変形は線形攻撃に対して弱くなるような変形であり適切であるという結論に至った。

結論

適切な近似を施した    は差分攻撃及び線形攻撃に対して耐性があった。提案された    は差分攻撃及び線形攻撃に対して耐性があるという結論に至った。

参考文献
 日本電気株式会社2 =暗号技術応募書>暗号技術仕様書    日本電気株式会社2 =暗号技術応募書>自己評価書   
 =暗号技術評価報告書    =2 情報処理振興事業協会セキュリティセンター

 =共通鍵ブロック暗号    の安全性に関する詳細調査報告=2
 コミュニケーションズ 供給