TOYOCRYPT-HR1

評価報告書

1. はじめに ................................................................................................................... 1
2. アルゴリズム .......................... エラー! ブックマークが定義されていません。
3. 評価結果 ................................................................................................................... 1
3.1. 周期..................................................................................................................... 1
3.2. 統計的性質......................................................................................................... 2
3.2.1. 1/0 等頻度性 ................................................................................................ 2
3.2.2. 数値的な検証 .............................................................................................. 2
3.2.3. 自己相関性 .................................................................................................. 4
3.3. AVALANCHE 性 ..................................................................................................... 4
3.4. 入力空間のサイズ............................................................................................. 5
3.5. 推測可能性......................................................................................................... 5
4. まとめ ....................................................................................................................... 55. 参考文献 ................................................................................................................... 5記号本稿では、以下の記号・略称・用語を説明無しに用いる。
LFSRLC
固定鍵ストリーム鍵⊕⊗
・F2n：線形フィードバックシフトレジスタ：線形複雑度：LFSR の状態遷移関数を定義するパラメータ：LFSR の初期内部状態を定義するパラメータ：排他的論理和：論理積：内積：2n 個の元からなる有限体

1. はじめに
本稿は、政府調達暗号公募に対して応募された擬似乱数生成器 TOYOCRYPT-HR1 の安全性について評価を行ったものである。検討項目は、周期、線形複雑度、およびその他の統計的な性質である。検討の結果、ビット出力の等頻度性、周期について提案者の行っている解析は妥当であることが検証された。また、統計的な性質について、いくつかの実験的な検証評価を行ったが、特に問題は見つからなかった。

2. アルゴリズム概略
TOYOCRYPT-HR1 の内部状態をX = x127 || x126 || ... || x0= x127 || x126 || Xh
XL = x125 || x124 || ... || x63
XR = x62 || x61 || ... || x0とし、特に時刻 t を明記する必要がある場合には、xi(t)と記述する。
TOYOCRYPT-HR1 の乱数生成部は、レジスタ長 128 のフィルター型生成器である。出力フィルターf は、f ( X ) = x127 ⊕ h( X h )= x127 ⊕ ( X L • π ( X R ) ⊕ g ( X R ))で与えられる。ここで、πは 63 ビットの置換、g は 64 次 3 項のブール多項式である。
固定鍵は状態遷移関数が M 系列を出力するように定め、ストリーム鍵は 0 以外の値を取る。また、初期化として、ストリーム鍵をレジスタにロードした後、256 回の状態遷移を行う。

3. 評価結果
本章では、TOYOCRYPT-HR1 の安全性について理論的、数値的な検証を行った結果について述べる。
擬似乱数生成器の出力する列は、• (1) 鍵長に見合う長い周期を持つこと• (2) いくつかの統計的性質(0/1 等頻度性、自己相関性)で偏りが小さいこと• (3) 大きな線形複雑度を持つことを満たすことが求められる。以下、節ごとにそれぞれの項目について論じる。

3.1. 周期TOYOCRYPT-HR1 では、LFSR が M 系列を生成するように固定鍵を選ぶので、LFSR部の周期は 2128-1 である。LFSR 部の周期の中で 1 の出現する回数は1∑ f ( X ) = ∑ h( X ) ⊕ x

127hx∈128
2x∈F2128= 2 ∑ ((h( X h ) ⊕ 0) + (h( X h ) ⊕ 1))
X h∈F2126= 2 ⋅ 2126 = 2127となる。固定鍵 C、ストリーム鍵 S に対する TOYOCRYPT-HR1 の出力列の周期を Per(C,S)とおけば、k ⋅ Per (C , S ) = 2 128 − 1を満たす自然数 k が存在する。Per(C, S)の間に出力される 0、1 の出現数をそれぞれ N0、N1 とすれば、k ⋅ N 0 = 2 127 − 1
k ⋅ N 1 = 2127が成り立つので、k=1 となる。すなわち、Per(C, S)=2128-1 である。

3.2. 統計的性質
3.2.1.

1/0 等頻度性

3.1.で述べたように、TOYOCRYPT-HR1 の周期中に 1 が出力される回数は 2127 回である。
すなわち、TOYOCRYPT-HR1 の出力列は 0/1 を理想的な頻度で出力する。

3.2.2.

数値的な検証線形フィードバックシフトレジスタ自体は理想的な乱数を出力するが、非線形フィルターによる影響を理論的に完全に検証することは困難である。ここでは、いくつかの乱数性指標について、実験的に検証した結果について述べる。
FIPS 140-1[1]では、乱数列が最低限満たすべき性質として、1 ビット、4 ビットの頻度検定、および連の検定に合格することが挙げられている。今回は、FIPS 140-1 にもとづき、これらの検定を TOYOCRYPT-HR1 の出力列(4K〜16M バイト)に対して実施した。検定にはχ2 検定を用いた。
また、固定鍵、ストリーム鍵は C 言語標準ライブラリの rand 関数を用いてランダムに与えた。
1 ビットの頻度検定(mono-bit test)
0/1 の出現頻度は、自由度 1 のχ2 分布を用いて検定することができる。表 3.1に自由度 1のχ2 値の代表的な値を挙げる。
表3.1 自由度 1 のχ2 分布の値
χ2 値
3.86.610.8

棄却率0.05
0.010.001

2検定は、4K, 64K, 1M, 16M バイトの乱数列それぞれ 256 個に対して行った。表 3.2の値は、これらの列に対し、0/1 頻度のχ2 統計量を計算し、棄却率 0.05, 0.01, 0.001 を超えたものの数である。
表 3.2 1 ビットの頻度検定
列の長さ0.050.010.001
4K バイト8/2562/2560/256
64K バイト10/2566/2560/256
1M バイト5/2561/2560/256
16M バイト9/2562/2560/256
実験の結果、いずれの長さの乱数列についても、χ2 値が極端に大きくなることはなかった。また、出力列が｢真の乱数ではない｣となる頻度についても許容できる範囲である。
4 ビットの頻度検定(poker test)
0/1 の出現頻度は、自由度 1 のχ2 分布を用いて検定することができる。表 3.3に自由度15 のχ2 値の代表的な値を挙げる。
表 3.3 自由度 15 のχ2 値
棄却率
χ2 値
0.05
25.00.01
30.60.001
37.7
検定は、4K, 64K, 1M, 16M バイトの乱数列それぞれ 256 個に対して行った。表 3.3は、これらの列に対し、4 ビット単位の出現頻度のχ2 統計量を計算し、棄却率 0.05, 0.01, 0.001を超えたものの数である。
表 3.4 4 ビットの頻度検定
列の長さ
0.050.010.001
4K バイト10/2562/2560/25664K バイト
7/2561/2560/256
1M バイト15/2560/2560/256
16M バイト17/2562/2562/2562
実験の結果、いずれの長さの乱数列についても、χ 値が極端に大きくなることはなかった。また、出力列が｢真の乱数ではない｣となる頻度についても許容できる範囲である。
連検定(run test)
連の検定では、有効な数値を取るため、出現頻度の低い長さの連を検定に用いない。ここでは、乱数列の長さを m ビットとしたとき、log2(m)-2 を検定を行う連の長さの下限とした。長い連は、出現する期待値が 1/256 以下のものとした。

3

表 3.5 連検定
列の長さ自由度
0.050.01
長い連(最長値)
4K バイト249/2563/2562(24)64K バイト329/2564/2563(26)1M バイト407/2564/2563(31)16M バイト4813/2564/2563(37)
実験の結果、いずれの長さの乱数列についても、χ2 値が極端に大きくなることはなかった。また、出力列が｢真の乱数ではない｣となる頻度についても許容できる範囲である。長い連が出現する確率は期待値に比べて多い傾向にあるが、問題となるほどではない(FIPSによる長すぎる連の定義は出現する期待値が 1/1000000 であり、このような連は観測されていない)。

3.2.3.

自己相関性

周期 N のビット列 s に対する自己相関関数を、で定義する。
N −1

A( s, t ) :=∑ (−1) si + si+t , 0 ≤ t ≤ N − 1i =0t≠0 ならば、A(s, t)の値は-1 であることが望ましい。しかし、非常に長い周期を持つ乱数列についてこれを検証することは困難である。ここでは、近似的に、出力列を t ビットシフトした列とを排他的論理和した列の 0/1 頻度検定を行った結果について述べる。表 3.6は、
TOYOCRYPT-HS1 の出力列の自己相関性をχ2 検定した結果で、各項目の数値は、256 個の固定鍵、ストリーム鍵のペアをランダムに与え、棄却率 0.01 を超えたものの数である。
表 3.6 シフト数 1〜10 の自己相関性
シフト数 t乱数列の長さ123456789104K バイト 4/256 4/256 3/256 3/256 4/256 2/256 2/256 1/256 1/256 3/25664K バイト 2/256 1/256 2/256 0/256 4/256 4/256 5/256 2/256 2/256 5/256
実験の結果、出力列が｢真の乱数ではない｣となる頻度は許容できる範囲であると言える。

3.3. avalanche 性
TOYOCRYPT-HR1 のフィルター関数 f は、f(X) = h(XL, XR) ⊕ x127で定義されるので、次の性質を持つ。
• f(x0, x1, ..., x126, x127) = f(x0, x1, ..., x126, x127)• f(x0, x1, ..., x126, x127) = f(x0, x1, ..., x126, x127)

一方、論理積において ab = ab, ab = ab となる確率はいずれも 1/2 であるから、レジスタ内部のビットのうち、x126, x127 以外のビットが反転している場合には出力ビットが反転するかどうかを知ることはできない。
ストリーム鍵 S のある 1 ビットを反転したものを S’とし、それぞれの出力列を s(t), s’(t)と置く。TOYOCRYPT-HR1 の状態遷移関数は線形写像であるから、差分の列 s(t)⊕s’(t)もまた M 系列となる。

4

以上の考察から、ストリーム鍵の任意の 1 ビットを反転した場合、出力列のあるビットが反転するか否かを推定することは困難である。

3.4. 入力空間のサイズ
LFSR の状態遷移は拡大体の指数演算+トレースで表現できる。このため、スクリーニン
グ評価の際に付されたコメントにもあるように、固定鍵 C を固定した場合、264 個所の内部状態 X(0), X(264), ..., X((264-1)264)を初期値とした一定長の出力を事前に計算しておき、このデータと実際の出力系列との衝突を測定すれば、264 ビット程度の出力列で衝突が起こることになる(これは、すべてのフィルター型生成器に言えることである)。この事実がただちに攻撃に結びつくわけではないが、攻撃者に固定鍵の情報が漏れれば、264 程度の計算量でストリーム鍵を決定することができるため、TOYOCRYPT-HR1 を乱数生成に用いる場合には、264 ビット程度を出力するごとに固定鍵を取りかえることが望ましい。

3.5. 推測可能性
LFSR の場合、入力情報の一部が漏れたとしても、256 ラウンド後のレジスタの内部状態を推定することは困難であり、入手情報以上の情報量を手に入れることはできない。
一方、TOYOCRYPT-HR1 はシードの選択以外は確定的なアルゴリズムであるため、シードが漏れた場合には、出力列を完全に確定することができる。このため、シードは予測不可能な値を取る必要がある。したがって、付記情報にあるような、キータイピング情報やネットワークのトラフィック情報など、攻撃者が取得可能と思われる情報をシードに使うことは望ましくない。

4.

まとめ

評価内容からは実用上問題となるような点は見つからなかった。しかし、近年の暗号技術評価では、提案されているアルゴリズムが｢現実的に解読可能か？｣ではなく、｢鍵の全数探索より効率的な攻撃法はあるか？｣ということを検討する傾向にある。このような観点か
ら見ると、TOYOCRYPT-HR1 は H/W での実装を軽量にするために、セキュリティマージンをほとんどとっていない設計である。また、レジスタ幅を鍵長ぎりぎりのサイズにとっているため、3.4に述べたような攻撃法が存在し得る。

5. 参考文献[1] FIPS 140-1, Security Requirements for Cryptographic Modules, Federal
Information Processing Statndard(FIPS), Publication 140-1, National Institute ofStandards adn Technology, US Department of Commerce, Washington D.C.,
January 1994,

http://www.itl.nist.gov/fipspubs/index.htm.
[2] Menezes, Alfred J., van Oorschot, Paul C., Vanstone, Scott A., HANDBOOK of
APPLIED CRYPTOGRAPHY, CRC Press, 1997.
[3] R. A. Rueppel, Analysis and Design of Stream Ciphers, Springer-Verlag, 1986.

5