Hierocrypt-L1 の安全性詳細評価報告
要旨:
本報告では、Hierocrypt-L1 の安全性について弊社による評価の報告を行う。結果として Hierocrypt-L1 について、評価者が限られた時間内で安全性評価を行う限りでは、致命的な安全性の問題点は発見されなかった。
今回の評価を含めても、Hierocrypt-L1 が安全性の評価が十分なされた暗号ブロック
暗号ではなく、今後の安全性評価も必要であるが 、現時点では、期待される安全性を備えると考えるための根拠を与える。

Abstract:
In this report, we address our security evaluation of Hierocrypt-L1.
As a result, we found no critical security ﬂaw during the limited period available forsecurity evaluation.
Hierocrypt-L1has not yet been evaluated enough even with our evaluation. Further evaluation results are necessary. We however show some evidences to consider
Hierocrypt-L1to provide expected security at this moment.

1

1

はじめに

本報告は、弊社が IPA より委託された業務として行った詳細評価、及び Hierocrypt-L1 の安全性に関する収集した情報のまとめを行う。
Hierocrypt-L1 は 2000 年に大熊らによって開発されたブ ロック暗号アルゴ リズムである。
Hierocrypt-L1 の安全性に関する文献のうち、評価者が知るものは設計者らによる自己評価書のみである。このなかでは暗号の安全性について質の高い評価を行っている。この文献では従来の解読法のうち、特に Hierocrypt-L1 に対して有効であると考えられる攻撃法に対しての評価が中心である。また、Hierocrypt-L1 向けに考えられた攻撃法による安全性評価は行われていない。
本報告書では評価者が行った Hierocrypt-L1 の安全性に関する詳細評価について、詳細に報告を行う。報告は安全性評価の結果のみならず、評価者が検討した評価方針やその過程についてもなるべく実験結果など を多く掲載し 、第三者が本報告の信憑性を検証できるようにした。
この結果、評価者による詳細評価では Hierocrypt-L1 の安全性について欠陥となる性質を見付けることはできなかった。

2

Hierocrypt-L1 評価方針

この章では、主に評価方針について述べる。その前に、評価者が最終的な評価方針に至るまでに考慮した Hierocrypt-L1 の特徴についてまず説明する。
Hierocrypt-L1 は鍵スケジュール部とデータ撹拌部分を持つブロック暗号である。データ撹拌
部分は、典型的な SPN 構造によるものである。このうち S(ubstitution:非線形変換) の役割となる S ボックスは (評価者の知る限り) オリジナルの S ボックスを使っている。S ボックスのサイズは 8 ビット入力/出力であり、単射である。
これに対し 、P(ermutation:線形変換) の役割となる変換は、二種類の線形変換を用いている。
これらは MDS (maximum distance separation) となるものが用いられている。
これら Hierocrypt-L1 のデータ撹拌部分はバイト (8 ビット ) 単位の処理でほぼ構成されているという特徴がある。
以上の特徴は、近年提案、評価されてきたブロック暗号 Square, CRYPTON, Rijndael に似た構造となっており、特に新しい構造をしたアルゴ リズム設計ではない。
特に AES の選定で注目されいくつかの評価結果が知られる Rijndael との相違点に注目すると次のようになる。

• 全体構造に関するもの
1. 64 ビットブロック暗号であること
2. 異なる鍵スケジュール部を使っていること
3. ブロック全体の撹拌が (より複雑であるものの) S ボックス層二回に一度であること• 構成部分
1. 線形変換に用いる行列 (局所的な MDSL 、全体的な MDSH)
2. S ボックス
3. 段数

2本評価の大きな目標として、等価鍵や DES のビット反転特性など 明らかな暗号の欠陥の特性がないことを重点的に確認することを第一の目標とした。そして第二の目標として、探索など の解析的な評価を伴う安全性の評価をできる限り行うこととした。
第一の目標は主に鍵スケジュール部の評価が中心となる。鍵スケジュール部に関するさまざまな特徴について最初に示す。
第二の目標については 、データ撹拌部分の評価が主となる。評価者は第二の目標を達成するために構成要素中、最も重要と考えられる S ボックスへの集中的な評価に着手した。これは、差分解読法、線形解読法で用いた統計値のように、解析した性質がその他のデータ撹拌部分である MDSL, MDSH により保存されるものを中心に考える。さらにこの中でもさまざまな面から S
ボックスの評価を行うよう努力した。
その結果、評価に許された限られた時間では、探索項目の検討や、探索プログラムの効率化など で不十分であり、暗号の安全性を保証するほど 十分に網羅的な探索とは言えない。しかし 、暗号を攻撃側から評価する立場という考え方から 、なるべく多くの実験を行い、有効なものをひとつでも見付ける、という方針で評価を進めた。
以下の章では、これらについて別々に評価報告を行ってゆく。

3

有限体上の演算について

本稿では、頻繁に有限体 GF(2k ) 上の乗算を扱うが 、本報告を通してその定義は次のとおりである。k ビットの値 (もしくは 10 進数で与えられているならばその整数の二進数表記) を上位
から b1 , . . . , bk とするとこの整数に体して次の多項式を対応づける、f (x) = ki=1 bixk−i 。これはk − 1 次以下の多項式で、係数は GF(2) の元である。これをある既約多項式 (拡大次数 k により定義される、本稿では表 1を用いる) による多項式の剰余環の要素として考えたときこの剰余環は体構造をなす。したがって、本稿で考える有限体 GF(2k ) 上の演算は表 1で定義される多項式環の演算に基づく。

表 1: 本報告で用いる GF(2n ) を定義する既約多項式
n
P (x)
n
P (x)
2 x2 + x + 1 6 x6 + x + 1
3 x3 + x + 1 7 x7 + x + 1
4 x4 + x + 1 8 x8 + x6 + x5 + x + 1
5 x5 + x2 + 1 9 x9 + x4 + 1

4

鍵スケジュール部
まず鍵スケジュール部の評価にあたり、一点確認をし ておく。

3

暗号文側拡大鍵生成について(t)

応募仕様書 [1](日本語 pp.10、右コラム、[拡大鍵生成 (暗号文側)] (5 ≤ t ≤ 7)) 中の K3(32) の定義式において、
(t)
(t−1)
(t)
K3(32) = W2(32) ⊕ V(32)
を

(t)

(t)

(t)

K3(32) = W2(32) ⊕ V(32)であるとして扱う。


この記述は行列のサイズが 異なるなど 1 の自明な誤りではなく、この変更を行わずとも暗号化、復号化を行うことはできる。評価者は仕様とおりの表記で暗号を実装しテストベクトルの整合/不整合を確認したわけではない。しかし 、関連する文献 [4] や同一の設計者でありアルゴ リ
ズムとして酷似した Hierocrypt-3 の仕様 [2] など から、後者のような仕様であり、表記は誤りであるとして理解するのが設計者の意図にそぐ うと考え、これらの状況判断より、評価者が勝手に訂正したものを評価した。 Hierocrypt-L1 の鍵スケジュール部は次の二つの部分からなる。

1. マスター鍵から各段の中間鍵の生成
2. 各段の中間鍵から拡大鍵への変換
評価者は、これらについて独立に評価を行った。その内容と結果について以下で述べてゆく。

4.1

中間鍵の生成部

ここで注目すべきは上記 1. である。中間鍵の生成はまず秘密鍵 128 ビットを 4 分割し 、上位半分を典型的な Feistel 構造として更新し 、Feistel 構造の鍵にあたる値を残りの下位半分より供給する。下位半分の更新は単なる線形変換として実現されている。また、中間鍵の更新は 4 段まで行い、それ以降はこれまで作った中間鍵を再利用する。
より具体的に中間鍵生成を見てゆく。Z (−1) = K とすると：

Z (0) = σ0(Z (−1) , G(0))
Z (1) = σ(Z (0) , G(1))
Z (2) = σ(Z (1) , G(2))
Z (3) = σ(Z (2) , G(3))
Z (4) = σ(Z (3) , G(4))
さらに、それ以降の中間鍵は：Z (5) = Z (8−5) = Z (3)Z (6) = Z (8−6) = Z (2)Z (7) = Z (8−7) = Z (1)
1

(t)

(t)

−1

(t)

(t)

−1

3.2.6 節最後の行の数式、Z3(32) ||Z4(32) = P (32) (W1(32) ||W2(32) ) は変数のサイズから P (16)とは明らか。

4の誤りであるこ

である。
各中間鍵の更新関数 σ を見てゆくと、
(t−1)

(Z1

(t−1)

, Z2

(t)

(t−1)

, Z3

(t)

(t−1)

, Z4
(t)

) := Z (t−1)(t)(Z1 , Z2 , Z3 , Z4 ) := Z (t)
(t−1)

(W1

(t)

(t−1)

, W2

(t−1)

Z3

= M5 (W1Z4= MB (W2

(t)

(t)
Z1
(t)
Z2

=
=

(t−1)

) := P (Z3

(t−1)

, Z4

)

) ⊕ G(t)

(t−1)

)

(t−1)
Z2
(t−1)
(t−1)
(t)
Z1
⊕ Fσ (Z2⊕ Z3 )

この中間鍵更新関数を図示したものを図 1に示す。また、暗号全体の鍵スケジュールに展開したものを図 2に示す。ここで関数 Fσ は S ボックスと線形関数を組み合わせた単射かつ非線形な変Z1(t-1)Z2(t-1)Z3(t-1)Z4(t-1)P
W1(t-1)
V(t)

Z1(t)

Z2(t)

W2(t-1)

M5
G(t)

M5-1

Z3(t)

Z4(t)

図 1: Intermediate keys’ generation (partial)

換であり、M5 、MB はバイト単位の排他的論理和から構成される単射な線形変換であり、P は
16 ビット単位の排他的論理和から構成される単射な線形変換である。よって、各 σ 、σ0 が単射であることは自明である。よって任意の t 段目の中間鍵を固定したとき Z t について一意に秘密
鍵 K 、同時に他の段の中間鍵 Z も一意に決めることができる。
考察 4.1:は省略) 。

すべての Z3 、Z4 は鍵の下位半分 (と段毎の定数) のみに依存する (自明なので証明

これらの導出はバイト単位の排他的論理和と定数加算 (GF(28 )) である。まず、中間鍵の下半分
Z3 と Z4 、及び 、拡大鍵導出に用いる中間値 W1 , W2 を、鍵と定数の排他的論理和を使って書き表すと以下のようになる。ここで Ki:j は 、128 ビットの秘密鍵 K を四分割した 32 ビットワードのうち、上位 i 番目ワード の中のさらに上位から第 j 番目バイトを示す。すなわち

K1:1 ||K1:2 ||K1:3 || . . . ||K4:8 := K128

Z(−1)3:1 = K3:1
Z(−1)3:2 = K3:2
5

Z(−1)3:3 = K3:3
Z(−1)3:4 = K3:4
Z(−1)4:1 = K4:1
Z(−1)4:2 = K4:2
Z(−1)4:3 = K4:3
Z(−1)4:4 = K4:4
Z(0)3,1 = K3:1 ⊕ K3:3
⊕ G0:1
Z(0)3,2 = K3:1 ⊕ K3:2 ⊕ K3:4
⊕ G0:2
Z(0)3,3 = K3:1 ⊕ K3:2 ⊕ K3:3
⊕ G0:3Z(0)3,4 = K3:2 ⊕ K3:4
⊕ G0:4Z(0)4,1 = K4:2 ⊕ K4:4
Z(0)4,2 = K4:1 ⊕ K4:3
Z(0)4,3 = K4:1 ⊕ K4:2 ⊕ K4:4
Z(0)4,4 = K4:1 ⊕ K4:3 ⊕ K4:4
Z(1)3,1 = K3:2 ⊕ K4:1
⊕ G0:1 ⊕ G0:3 ⊕ G1:1
Z(1)3,2 = K3:3 ⊕ K4:2
⊕ G0:1 ⊕ G0:2 ⊕ G0:4 ⊕ G1:2
Z(1)3,3 = K3:1 ⊕ K3:4 ⊕ K4:3
⊕ G0:1 ⊕ G0:2 ⊕ G0:3 ⊕ G1:3
Z(1)3,4 = K3:1 ⊕ K4:4
⊕ G0:2 ⊕ G0:4 ⊕ G1:4
Z(1)4,1 = K3:1
⊕ G0:2 ⊕ G0:4
Z(1)4,2 = K3:2
⊕ G0:1 ⊕ G0:3
Z(1)4,3 = K3:2 ⊕ K3:3 ⊕ K4:1
⊕ G0:2 ⊕ G0:3 ⊕ G0:4
Z(1)4,4 = K3:1 ⊕ K3:4 ⊕ K4:4
⊕ G0:1 ⊕ G0:2 ⊕ G0:3
W (1)(= W (7))1,1 = K3:1 ⊕ K3:2 ⊕ K4:1
⊕ G0:1 ⊕ G0:2 ⊕ G0:3 ⊕ G0:4 ⊕ G1:1
W (1)(= W (7))1,2 = K3:2 ⊕ K3:3 ⊕ K4:2
6

⊕ G0:2 ⊕ G0:3 ⊕ G0:4 ⊕ G1:2
W (1)(= W (7))1,3 = K3:1 ⊕ K3:2 ⊕ K3:3 ⊕ K3:4 ⊕ K4:1 ⊕ K4:3
⊕ G0:1 ⊕ G0:4 ⊕ G1:3
W (1)(= W (7))1,4 = K3:4
⊕ G0:1 ⊕ G0:3 ⊕ G0:4 ⊕ G1:4
W (1)(= W (7))2,1 = K3:2 ⊕ K3:3 ⊕ K3:4 ⊕ K4:1 ⊕ K4:3
⊕ G0:1 ⊕ G0:2 ⊕ G1:3
W (1)(= W (7))2,2 = K3:2 ⊕ K3:4
⊕ G0:4 ⊕ G1:4
W (1)(= W (7))2,3 = K3:1 ⊕ K3:3
⊕ G0:1 ⊕ G1:1
W (1)(= W (7))2,4 = K3:1 ⊕ K3:2 ⊕ K3:3 ⊕ K3:4 ⊕ K4:2 ⊕ K4:4
⊕ G0:1 ⊕ G0:4 ⊕ G1:2
Z(2)3,1 = K3:3 ⊕ K3:4 ⊕ K4:3
⊕ G0:2 ⊕ G0:3 ⊕ G1:1 ⊕ G1:3 ⊕ G2:1
3,2

= K3:1 ⊕ K3:3 ⊕ K3:4 ⊕ K4:1 ⊕ K4:2
⊕ G0:3 ⊕ G0:4 ⊕ G1:1 ⊕ G1:2 ⊕ G1:4 ⊕ G2:2

3,3

= K3:2 ⊕ K3:4 ⊕ K4:2 ⊕ K4:3
⊕ G0:4 ⊕ G1:1 ⊕ G1:2 ⊕ G1:3 ⊕ G2:3

3,4

= K3:2 ⊕ K3:3 ⊕ K3:4 ⊕ K4:2
⊕ G0:1 ⊕ G0:2 ⊕ G1:2 ⊕ G1:4 ⊕ G2:4

4,1

= K3:1 ⊕ K3:3 ⊕ K4:2 ⊕ K4:4
⊕ G0:1 ⊕ G1:2 ⊕ G1:4

4,2

= K3:1 ⊕ K3:2 ⊕ K3:4 ⊕ K4:1 ⊕ K4:3
⊕ G0:2 ⊕ G1:1 ⊕ G1:3

4,3

= K3:1 ⊕ K3:2 ⊕ K3:4 ⊕ K4:1 ⊕ K4:2 ⊕ K4:3 ⊕ K4:4
⊕ G0:2 ⊕ G1:2 ⊕ G1:3 ⊕ G1:4

4,4

= K3:3 ⊕ K4:1 ⊕ K4:2 ⊕ K4:3 ⊕ K4:4
⊕ G0:1 ⊕ G0:2 ⊕ G0:4 ⊕ G1:1 ⊕ G1:2 ⊕ G1:3

W (2)(= W (6))3,1 = K3:1 ⊕ K3:4 ⊕ K4:2 ⊕ K4:3 ⊕ K4:4
⊕ G0:1 ⊕ G0:2 ⊕ G0:3 ⊕ G1:1 ⊕ G1:2 ⊕ G1:3 ⊕ G1:4 ⊕ G2:1
3,2

= K3:2 ⊕ K3:3 ⊕ K4:2 ⊕ K4:3
⊕ G0:2 ⊕ G0:3 ⊕ G0:4 ⊕ G1:2 ⊕ G1:3 ⊕ G1:4 ⊕ G2:2

3,3

= K3:1 ⊕ K4:1 ⊕ K4:4
⊕ G0:2 ⊕ G0:4 ⊕ G1:1 ⊕ G1:4 ⊕ G2:3

3,4

= K3:2 ⊕ K3:4 ⊕ K4:1 ⊕ K4:3 ⊕ K4:4
⊕ G0:4 ⊕ G1:1 ⊕ G1:3 ⊕ G1:4 ⊕ G2:4
7

4,1

= K3:3 ⊕ K4:1 ⊕ K4:2
⊕ G0:1 ⊕ G0:2 ⊕ G0:4 ⊕ G1:1 ⊕ G1:2 ⊕ G2:3

4,2

= K3:1 ⊕ K4:4
⊕ G0:2 ⊕ G0:4 ⊕ G1:4 ⊕ G2:4

4,3

= K3:2 ⊕ K4:1
⊕ G0:1 ⊕ G0:3 ⊕ G1:1 ⊕ G2:1

4,4

= K3:2 ⊕ K4:1 ⊕ K4:4
⊕ G0:1 ⊕ G0:3 ⊕ G1:1 ⊕ G1:4 ⊕ G2:2

Z(3)3,1 = K3:4 ⊕ K4:1 ⊕ K4:2 ⊕ K4:3
⊕ G0:1 ⊕ G0:3 ⊕ G0:4 ⊕ G1:2 ⊕ G1:3 ⊕ G2:1 ⊕ G2:3 ⊕ G3:1
3,2

= K3:1 ⊕ K3:3 ⊕ K4:1 ⊕ K4:3
⊕ G0:1 ⊕ G1:3 ⊕ G1:4 ⊕ G2:1 ⊕ G2:2 ⊕ G2:4 ⊕ G3:2

3,3

= K3:2 ⊕ K3:3 ⊕ K3:4 ⊕ K4:1
⊕ G0:1 ⊕ G0:2 ⊕ G1:4 ⊕ G2:1 ⊕ G2:2 ⊕ G2:3 ⊕ G3:3

3,4

= K3:3 ⊕ K3:4 ⊕ K4:1 ⊕ K4:2 ⊕ K4:4
⊕ G0:2 ⊕ G0:3 ⊕ G1:1 ⊕ G1:2 ⊕ G2:2 ⊕ G2:4 ⊕ G3:4

4,1

= K3:1 ⊕ K3:2 ⊕ K4:1
⊕ G0:1 ⊕ G0:2 ⊕ G0:3 ⊕ G0:4 ⊕ G1:1 ⊕ G2:2 ⊕ G2:4

4,2

= K3:2 ⊕ K3:3 ⊕ K4:2
⊕ G0:2 ⊕ G0:3 ⊕ G0:4 ⊕ G1:2 ⊕ G2:1 ⊕ G2:3

4,3

= K3:1 ⊕ K3:2 ⊕ K3:3 ⊕ K4:2
⊕ G0:3 ⊕ G1:2 ⊕ G2:2 ⊕ G2:3 ⊕ G2:4

4,4

= K3:3 ⊕ K4:1 ⊕ K4:2 ⊕ K4:4
⊕ G0:1 ⊕ G0:2 ⊕ G0:4 ⊕ G1:1 ⊕ G1:2 ⊕ G1:4 ⊕ G2:1 ⊕ G2:2 ⊕ G2:3

W (3)(= W (5))3,1 = K3:1 ⊕ K3:2 ⊕ K3:4 ⊕ K4:2 ⊕ K4:3
⊕ G0:2 ⊕ G1:1 ⊕ G1:2 ⊕ G1:3 ⊕ G2:1 ⊕ G2:2 ⊕ G2:3 ⊕ G2:4 ⊕ G3:1
3,2

= K3:1 ⊕ K3:2 ⊕ K4:1 ⊕ K4:2 ⊕ K4:3
⊕ G0:1 ⊕ G0:2 ⊕ G0:3 ⊕ G0:4 ⊕ G1:2 ⊕ G1:3 ⊕ G1:4 ⊕ G2:2 ⊕ G2:3 ⊕ G2:4 ⊕ G3:2

3,3

= K3:1 ⊕ K3:4 ⊕ K4:1 ⊕ K4:2
⊕ G0:1 ⊕ G0:2 ⊕ G0:3 ⊕ G1:2 ⊕ G1:4 ⊕ G2:1 ⊕ G2:4 ⊕ G3:3

3,4

= K3:4⊕ G0:1 ⊕ G0:3 ⊕ G0:4 ⊕ G1:4 ⊕ G2:1 ⊕ G2:3 ⊕ G2:4 ⊕ G3:4

4,1

= K3:2 ⊕ K3:4 ⊕ K4:2
⊕ G0:4 ⊕ G1:1 ⊕ G1:2 ⊕ G1:4 ⊕ G2:1 ⊕ G2:2 ⊕ G3:3

4,2

= K3:2 ⊕ K3:3 ⊕ K3:4 ⊕ K4:2
⊕ G0:1 ⊕ G0:2 ⊕ G1:2 ⊕ G1:4 ⊕ G2:4 ⊕ G3:4

4,3

= K3:3 ⊕ K3:4 ⊕ K4:3
8

⊕ G0:2 ⊕ G0:3 ⊕ G1:1 ⊕ G1:3 ⊕ G2:1 ⊕ G3:1
4,4

= K3:1 ⊕ K3:2 ⊕ K3:3 ⊕ K4:3 ⊕ K4:4
⊕ G0:3 ⊕ G1:1 ⊕ G1:3 ⊕ G2:1 ⊕ G2:4 ⊕ G3:2

Z(4)3,1 = K3:2 ⊕ K4:1 ⊕ K4:3
⊕ G0:1 ⊕ G0:3 ⊕ G1:1 ⊕ G1:3 ⊕ G1:4 ⊕ G2:2 ⊕ G2:3 ⊕ G3:1 ⊕ G3:3 ⊕ G4:1
3,2

= K4:1⊕ G1:1 ⊕ G2:3 ⊕ G2:4 ⊕ G3:1 ⊕ G3:2 ⊕ G3:4 ⊕ G4:2

3,3

= K3:1 ⊕ K4:2
⊕ G0:2 ⊕ G0:4 ⊕ G1:1 ⊕ G1:2 ⊕ G2:4 ⊕ G3:1 ⊕ G3:2 ⊕ G3:3 ⊕ G4:3

3,4

= K3:1 ⊕ K3:2 ⊕ K3:4 ⊕ K4:1 ⊕ K4:2 ⊕ K4:3
⊕ G0:2 ⊕ G1:2 ⊕ G1:3 ⊕ G2:1 ⊕ G2:2 ⊕ G3:2 ⊕ G3:4 ⊕ G4:4

4,1

= K3:1 ⊕ K3:4 ⊕ K4:2 ⊕ K4:3 ⊕ K4:4
⊕ G0:1 ⊕ G0:2 ⊕ G0:3 ⊕ G1:1 ⊕ G1:2 ⊕ G1:3 ⊕ G1:4 ⊕ G2:1 ⊕ G3:2 ⊕ G3:4

4,2

= K3:2 ⊕ K3:3 ⊕ K4:2 ⊕ K4:3
⊕ G0:2 ⊕ G0:3 ⊕ G0:4 ⊕ G1:2 ⊕ G1:3 ⊕ G1:4 ⊕ G2:2 ⊕ G3:1 ⊕ G3:3

4,3

= K3:1 ⊕ K3:2 ⊕ K4:3 ⊕ K4:4
⊕ G0:1 ⊕ G0:2 ⊕ G0:3 ⊕ G0:4 ⊕ G1:3 ⊕ G2:2 ⊕ G3:2 ⊕ G3:3 ⊕ G3:4

4,4

= K3:1 ⊕ K4:2 ⊕ K4:4
⊕ G0:2 ⊕ G0:4 ⊕ G1:1 ⊕ G1:2 ⊕ G1:4 ⊕ G2:1 ⊕ G2:2 ⊕ G2:4 ⊕ G3:1 ⊕ G3:2 ⊕ G3:3

4.2

拡大鍵の生成アルゴ リズムの設計者の指針では、中間値から拡大鍵の生成には平文側の規則と暗号文側の規則を変化することで、(1) 平文側と暗号文側で同じ 拡大鍵が生成されることを避ける、(2) 単
純な依存関係によって弱い鍵となることがないようにする、ことを目標としている。
Hierocrypt-L1 のほとんど のアルゴ リズム設計では、その手法と方針が示されているが 、この拡大鍵生成部分については、平文側と暗号文側を異なるものとしたこと以外は、ほとんど 述べられていない。
評価者は拡大鍵生成についてさらに重点的に解析を行い、生成される拡大鍵の性質について評価を行った。
拡大鍵生成の単射性について
定理 4.2:

平文側の各段の拡大鍵生成 (K (1) , K (2), K (3), K (4) ) は秘密鍵に対して単射である。

証明：秘密鍵から一意に中間鍵 Z が生成されることは仕様から自明、またこれら中間鍵 Z から一意に拡大鍵が生成されることも明らか。
逆にある段 t の拡大鍵 K (t) , 1 ≤ t ≤ 4 を固定したとき、以下に示すように一意に 128 ビットの中間値 Z (t) を決定することができる、すなわち任意の t, 1 ≤ t ≤ 4 段目の拡大鍵に対して一意

9

に秘密鍵が決定される。
(t)

(t)

(t)

V (t) = Fσ (K2 ⊕ K3 ⊕ K4 )
(t)

(t)

(t)

Z1

= K3 ⊕ K4 ⊕ V (t)

Z2

= K1

Z3

= K2 ⊕ V (t)Z4= K3 ⊕ V (t)

(t)
(t)
(t)

(t)
(t)
(t)



観察 4.3:られる。

暗号文側の各段の拡大鍵生成 (K (5), K (6) , K (7)) は秘密鍵に対して単射でないと考え

根拠：これまでの評価より任意の秘密鍵と Z (t−1) , 5 ≤ t ≤ 8 は単射である。以下では 、Z (t−1) と拡大鍵 K (t) が単射でないと考えられ る根拠を示す。
まず、拡大鍵 K (t) を Z (t−1) のみを使って表記すると以下のようになる。
(t)

K1

(t)
K2
(t)
K3
(t)
K4

(t−1)

= Z3
=
=
=

(t−1)

⊕ Z2

(t−1)

⊕ Fσ (Z1

(t−1)

⊕ Z3

)

(1)

(t−1)
(t−1)
(t−1)
M5 (G(t−1) ⊕ Z3 ) ⊕ Fσ (Z1
⊕ Z3
)
(t−1)
(t−1)
(t−1)
MB (Z4 ) ⊕ Fσ (Z1
⊕ Z3
)
(t−1)
(t−1)
Z1
⊕ MB (Z4 )

(2)
(3)
(4)

ここで媒介変数 x を用いて Y (t−1) を以下のように定義する。
(t−1)

(t)

Y4

= MB−1 (K4 ⊕ x)

Y3

= M5−1 (x ⊕ M5(G(t−1)) ⊕ K2 ⊕ K3 ⊕ K4 )Y2

= x ⊕ Y3 ⊕ K 1 ⊕ K 3 ⊕ K 4 )

Y1

= x

(t−1)
(t−1)
(t−1)

(t)

(t)

(t)

(t)

(t)

(t)

Y (t−1) は固定した拡大鍵 K (t) と x に対して一意に決定されるが 、x が異なると、異なる Y (t−1)
が決定されることに注意する。Z (t−1) = Y (t−1) が式 (1)〜(4) を同時に満たすためには(t−1)

Fσ (Y1

(t−1)

⊕ Y3

(t−1)

) = Y1(t)(t)⊕ K3 ⊕ K4が成り立つような Y である必要がある。このような Y の個数は、関数 Fσ の性質に依存するが 、(1)Fσ は非線形で複雑な関数であること、(2)x から Y の生成が Fσ に依存しない 、線形な変換のみで行われること、の二点から、式 (1)〜(4) を満たす Z は 1 個以上存在する場合があると強く予想される。


拡大鍵生成の段間の相関について
多くのブロック暗号では拡大鍵について、異なる段の間で相関のある場合は多い。DES では、
ビットレベルで同じビットを 16 段のうち 13〜14 回繰り返し使っている。MISTY1 では、16 ビットデータを 5 回、または 4 回繰り返し用いている。

10

これらの使用では、拡大鍵の使用法が適切であったため、弱点として指摘されることはなかったが 、その他の暗号では弱点となった例がある。SAFER+の 256 ビット鍵スケジュールでは、同じ 拡大鍵データを繰り返し 用いたことによる中間値一致攻撃が (minor ﬂaw ではあるが ) 指摘されている [5]。また、Magenta では明らかな拡大鍵の繰り返し使用で同じく中間値一致攻撃的な攻撃が指摘されている [6]。また、極端な例で毎段同じ鍵を用いることでスライド 攻撃 [7] など を適用する条件を生む要素となる。
Hierocrypt-L1 では、中間鍵が段数の約半分だけしか生成されないため、評価者としては平文側、暗号文側で同じ中間値に対応する拡大鍵の生成に注目するべきである。具体的には、アルゴ リズム設計者の記述から
Z (t) = Z (8−t) , 5 ≤ t ≤ 7
かつ K (t) , 1 ≤ t ≤ 4 は主に Z (t−1) , Z (t) で簡単に表記され 、K (t) , 5 ≤ t ≤ 7 は主に Z (t−1) , Z (t) で簡単に表記されることから、

K (t) ←→ K (8−t)
K (t) ←→ K (9−t)の相関に着目した。この評価にあたり、拡大鍵を生成する際に用いられる変数 V (t) についての以下の補題を示しておく。
補題 1:

V (t) = V (9−t) , 5 ≤ t ≤ 7

自明なので、証明は与えない。
この補題を用いることで以下の定理を示すことができる。
定理 4.4:

(t)

(9−t)

K1 = K1

(9−t)

⊕ K2

,5 ≤ t ≤ 7

証明：平文側の拡大鍵導出の式から (5 ≤ t ≤ 7)
(9−t)

K1

(9−t)

⊕ K2

(9−t−1)

= Z1

(9−t)

⊕ Z3

(8−(9−t−1))= Z1(8−(9−t))

⊕ Z3

(t)

(t−1)

(t)

(t−1)

= Z1 ⊕ Z3

さらに暗号文側の拡大鍵導出の式から(t)

K1= Z1 ⊕ Z3


次に平文側のみの線形相関として以下のものが導かれる。
定理 4.5:

(t)

(t)

(t−1)

K1 ⊕ K2 ⊕ K4

(t)

(t−1)

= Z3 ⊕ Z4,2 ≤ t ≤ 411

証明：平文側の拡大鍵導出の式から (2 ≤ t ≤ 4)
(t)

K1

(t)

K2

(t)

K4

(t−1)

= Z1

⊕ V (t)

(t)

= Z2

(t)

= Z3 ⊕ V (t)
(t)

(t)

(t−1)

(t−1)

⊕ Z4

= Z3 ⊕ Z2 ⊕ Z1
= Z2

(t)

(t)

(t)

= Z1 ⊕ Z4
これらより
(t−1)

(t)

(t)

K4

(t−1)

K1 ⊕ K2 ⊕ K4

(t−1)

= Z1

(t)

(t−1)

⊕ Z4
(t)

(t)

(t−1)

= Z2 ⊕ Z3 ⊕ Z2 ⊕ Z1
(t)

(t−1)

(t−1)

⊕ Z1

(t−1)

⊕ Z4

= Z3 ⊕ Z4
ここで、Z3 、Z4 は鍵と定数による線形変換であったことを思い出す。これらの鍵と定数を使った表記は以下のようになる。
(2)

(1)

(Z3 ⊕ Z4 )1 = K3:1 ⊕ K3:3 ⊕ K3:4 ⊕ K4:3
⊕ G0:3 ⊕ G0:4 ⊕ G1:1 ⊕ G1:3 ⊕ G2:1
(2)
(1)
(Z3 ⊕ Z4 )2= K3:1 ⊕ K3:2 ⊕ K3:3 ⊕ K3:4 ⊕ K4:1 ⊕ K4:2
⊕ G0:1 ⊕ G0:4 ⊕ G1:1 ⊕ G1:2 ⊕ G1:4 ⊕ G2:2

(2)
(1)
(Z3 ⊕ Z4 )3= K3:3 ⊕ K3:4 ⊕ K4:1 ⊕ K4:2 ⊕ K4:3
⊕ G0:2 ⊕ G0:3 ⊕ G1:1 ⊕ G1:2 ⊕ G1:3 ⊕ G2:3

(2)
(1)
(Z3 ⊕ Z4 )4= K3:1 ⊕ K3:2 ⊕ K3:3 ⊕ K4:2 ⊕ K4:4
⊕ G0:3 ⊕ G1:2 ⊕ G1:4 ⊕ G2:4

(3)
(2)
(Z3 ⊕ Z4 )1= K3:1 ⊕ K3:3 ⊕ K3:4 ⊕ K4:1 ⊕ K4:3 ⊕ K4:4
⊕ G0:3 ⊕ G0:4 ⊕ G1:3 ⊕ G1:4 ⊕ G2:1 ⊕ G2:3 ⊕ G3:1

(3)
(2)
(Z3 ⊕ Z4 )2= K3:2 ⊕ K3:3 ⊕ K3:4
⊕ G0:1 ⊕ G0:2 ⊕ G1:1 ⊕ G1:4 ⊕ G2:1 ⊕ G2:2 ⊕ G2:4 ⊕ G3:2

(3)
(2)
(Z3 ⊕ Z4 )3= K3:1 ⊕ K3:3 ⊕ K4:2 ⊕ K4:3 ⊕ K4:4
⊕ G0:1 ⊕ G1:2 ⊕ G1:3 ⊕ G2:1 ⊕ G2:2 ⊕ G2:3 ⊕ G3:3

(3)
(2)
(Z3 ⊕ Z4 )4= K3:4 ⊕ K4:3
⊕ G0:1 ⊕ G0:3 ⊕ G0:4 ⊕ G1:3 ⊕ G2:2 ⊕ G2:4 ⊕ G3:4

(4)
(3)
(Z3 ⊕ Z4 )1= K3:1 ⊕ K4:3
⊕ G0:2 ⊕ G0:4 ⊕ G1:3 ⊕ G1:4 ⊕ G2:3 ⊕ G2:4 ⊕ G3:1 ⊕ G3:3 ⊕ G4:1

(4)

(3)

(Z3 ⊕ Z4 )2 = K3:2 ⊕ K3:3 ⊕ K4:1 ⊕ K4:2
⊕ G0:2 ⊕ G0:3 ⊕ G0:4 ⊕ G1:1 ⊕ G1:2 ⊕ G2:1 ⊕ G2:4 ⊕ G3:1 ⊕ G3:2 ⊕ G3:4 ⊕ G4:2
(4)
(3)
(Z3 ⊕ Z4 )3= K3:2 ⊕ K3:3
12

⊕ G0:2 ⊕ G0:3 ⊕ G0:4 ⊕ G1:1 ⊕ G2:2 ⊕ G2:3 ⊕ G3:1 ⊕ G3:2 ⊕ G3:3 ⊕ G4:3
(4)
(3)
(Z3 ⊕ Z4 )4= K3:1 ⊕ K3:2 ⊕ K3:3 ⊕ K3:4 ⊕ K4:3 ⊕ K4:4
⊕ G0:1 ⊕ G0:4 ⊕ G1:1 ⊕ G1:3 ⊕ G1:4 ⊕ G2:3 ⊕ G3:2 ⊕ G3:4 ⊕ G4:4

これらは 、上記で示した拡大鍵の排他的論理和が 、秘密鍵と定数の排他論理和で表現できることを示している。
異なる秘密鍵間の拡大鍵の相関について
上記で示したように、平文側の拡大鍵生成について、t 段目の拡大鍵と秘密鍵は単射であったことから 、異なる秘密鍵は異なる拡大鍵を生成する。これにより、鍵スケジュール部に起因する等価鍵は起こらないと強く考えられる。
また、データ撹拌部分の構造が SPN 構造であり、複数の反転した拡大鍵間の (反転の) キャ
ンセルアウトによる F 関数入力の固定は起こり得ず、LOKI89 のような (データ撹拌部分と鍵ス
ケジュール部の相互作用による) 等価鍵 [8] も存在しにくい。
DES の反転特性 [9] のような、平文の反転と拡大鍵の反転のキャンセルアウトによる自明な特性については、以下のように考察することで、Hierocrypt-L1 には起こりにくいと考える。
DES の反転特性は、非線形な関数である F 関数へのすべての入力を (異なる平文、鍵入力に対して) 固定することで得られる。Hierocrypt-L1 では、平文は第 1 段目の拡大鍵との排他的論(1)(1)
理和が行われる。よって、異なる平文 PA , PB と第一段拡大鍵 KA , KB の差分のキャンセルア(1)(1)
ウト (すなわち PA ⊕ KA = PB ⊕ KB ) により、最初の S ボックスへの入力が固定されることは(t)(t)
ある。しかし 、そのあとの拡大鍵 (KA , KB ) は異なりながらも 、データ撹拌部分の (鍵加算前の) 中間値が同じであることから、鍵加算により中間値に差分が生じ S ボックスで差分が拡散されてし まう。よって、秘密鍵と平文側の拡大鍵が単射であることと、データ撹拌部分が SPN 構
造であることから、DES のような反転特性は生じないと強く予想される。
ただし 、中間鍵には DES 構造全体で起こる反転特性のような、F 関数の入力を固定するものは存在することを注意しておく。
(1)

(1)

以下に示す差分関係にある二つの中間鍵 ZA , ZB は、これから生成されるすべての定理 4.6:(t)(t)
中間鍵 ZA , ZB , 2 ≤ t ≤ 4 についても自明な差分が生まれる (表記：ただし 、x はあるバイト差
分値 (任意) 、0 はバイトの 0 差分を示す) 。
Case 1:(一段繰り返し )∆Z (0) = 000x, 000x, 000x, x0x0
∆Z (1) = 000x, 000x, 000x, x0x0
∆Z (2) = 000x, 000x, 000x, x0x0
∆Z (3) = 000x, 000x, 000x, x0x0
∆Z (4) = 000x, 000x, 000x, x0x0
Case 2:(二段繰り返し )∆Z (0) = 0000, 000x, 0000, x0xx
∆Z (1) = 000x, 0000, 000x, 000x13∆Z (2) = 0000, 000x, 0000, x0xx
∆Z (3) = 000x, 0000, 000x, 000x∆Z (4) = 0000, 000x, 0000, x0xx
Case 3:(二段繰り返し 、Case 2 の逆)∆Z (0) = 000x, 0000, 000x, 000x
∆Z (1) = 0000, 000x, 0000, x0xx
∆Z (2) = 000x, 0000, 000x, 000x∆Z (3) = 0000, 000x, 0000, x0xx
∆Z (4) = 000x, 0000, 000x, 000x

5

データ撹拌部の解析

この章では、Hierocrypt-L1 のデータ撹拌部分について安全性の詳細評価の結果をまとめる。
Hierocrypt-L1 は SPN 構造に基づいたデータ撹拌部分の設計であり、バイトオリエンティッド な構造である。
このような構造をもつブロック暗号には、Square[10]、Rijndael[11]、CRYPTON [12] がある。これらのブロック暗号に対する有効な安全性評価としては、同様にバイト単位の特性に着目した Square 攻撃 [10] 、truncated-diﬀerential[13] などが一般的かつ効果的であると考えられる。
これに対して Hierocrypt-L1 の設計者はアルゴ リズムの提案時に、評価書中の安全性評価の項で、これら解読法に対する詳細な安全性評価結果を示している。これらの信憑性は高いものと評価者は考え、一般的に有効と考えられ る Square 攻撃や truncated-diﬀerential については今回の詳細評価では言及しない。しかし 、Hierocrypt-L1 に適用可能なバイトオリエンティッド な特徴は安全性評価の観点から重要視する必要がある。
データ撹拌部分を構成する四つの部分関数をまとめると：

1. 鍵加算 (排他的論理和)
2. S ボックス (8 ビット単位の非線形変換)
3. MDSL(GF(28 ) 上の乗算と加算)
4. MDSH(バイト単位の排他的論理和)
ここで S ボックス以外のすべての演算は有限体 GF(28 ) 上の演算として簡単に表現される。しかし 、設計者はこれを懸念し 、S ボックスの設計では S ボックスと MDSL との組み合わせが最も複雑となる (より具体的には重み付き項数による評価の最大となる) S ボックス、ならびに MDSLを設計している。つまり単純な代数補間についても設計者により評価済みである。
評価者は、まず S ボックスについて詳細な評価を行い発見した性質について (暗号全体の安全性の議論への影響はほぼ関係なく) 列挙する。

5.1

Hierocrypt-L1 の S ボックス評価

評価を行った S ボックスを表 2に示す。

14

S ボックスの設計について
設計者は S ボックスの導出について Hierocrypt-L1 の仕様書にて記述している。ここでは S
ボックスはs(x) = Add(P ower(P erm(x)))のように、ビット並び替え P erm() 、有限体 GF(28 ) 上のべき乗演算 P ower() 、それに排他的論
理和 Add() の合成関数として表現されている。このうち排他論理和 Add は定数 0x11 を加算することになっているが 、x = 0 のときの S ボックスの出力は 7 であり矛盾している。
また、実際に s(P erm−1(x)) を多項式により近似してみたとき 、その結果は x247 + 7(これらはすべて GF(28 ) 上の要素、および 演算) であった。

S ボックスの代数的性質
上記の S ボックスを x8 + x6 + x5 + x + 1 の既約多項式で決定される有限体 GF(28 ) 上の関数として表すと以下のようになる。ここで係数は 10 進数表記であるが 、GF(28 ) の元への対応は表記の項で示した通りである。

F (x) = 7×x0 +198×x1 +233×x2 +39×x3 +186×x4 +205×x5 +92×x6 +197×x7+ 239×x8 +90×x9 +175×x10 +107×x11 +142×x12 +91×x14 +179×x15+ 255×x16 +66×x17 +172×x18 +12×x19 +196×x20 +114×x21 +219×x22 +42×x23+ 181×x24 +162×x25 +71×x26 +227×x27 +86×x28 +213×x29 +15×x30 +141×x31+ 68×x32 +37×x33 +220×x34 +144×x35 +96×x36 +130×x37 +107×x38 +47×x39+ 192×x40 +107×x41 +89×x42 +161×x43 +157×x44 +186×x45 +135×x46 +159×x47+ 141×x48 +93×x49 +245×x50 +96×x51 +103×x52 +113×x53 +145×x54 +189×x55+ 92×x56 +76×x57 +141×x58 +244×x59 +205×x60 +22×x61 +79×x62 +253×x63+ 202×x64 +205×x65 +140×x66 +195×x67 +74×x68 +226×x69 +220×x70 +171×x71+ 182×x72 +116×x73 +182×x74 +57×x75 +177×x76 +105×x77 +240×x78 +45×x79+ 106×x80 +94×x81 +241×x82 +124×x83 +215×x84 +168×x85 +193×x86 +16×x87+ 137×x88 +39×x89 +50×x90 +116×x91 +78×x92 +55×x93 +201×x94 +5×x95+ 119×x96 +70×x97 +91×x98 +10×x99 +165×x100 +117×x101 +194×x102 +155×x103+ 191×x104 +230×x105 +252×x106 +151×x107 +181×x108 +203×x109 +21×x110 +29×x111+ 178×x112 +104×x113 +86×x114 +101×x115 +71×x116 +108×x117 +168×x118 +96×x119+ 211×x120 +160×x121 +2×x122 +117×x123 +255×x124 +135×x125 +60×x126 +151×x127+ 46×x128 +130×x129 +58×x130 +54×x131 +105×x132 +157×x133 +156×x134 +28×x135+ 24×x136 +242×x137 +67×x138 +79×x139 +149×x140 +214×x141 +126×x142 +109×x143+ 81×x144 +129×x145 +202×x146 +67×x147 +69×x148 +207×x149 +117×x150 +236×x151+ 172×x152 +144×x153 +73×x154 +160×x155 +26×x156 +214×x157 +62×x158 +51×x159+ 40×x160 +54×x161 +132×x162 +173×x163 +191×x164 +240×x165 +13×x166 +252×x167+ 177×x168 +58×x169 +23×x170 +104×x171 +122×x172 +85×x173 +36×x174 +187×x175+ 119×x176 +76×x177 +17×x178 +227×x179 +92×x180 +180×x181 +216×x182 +230×x183+ 139×x184 +8×x185 +171×x186 +37×x187 +120×x188 +231×x189 +55×x190 +244×x191
15

+ 195×x192 +214×x193 +169×x194 +62×x195 +183×x196 +113×x197 +121×x198 +63×x199+ 92×x200 +106×x201 +204×x202 +29×x203 +78×x204 +180×x205 +233×x206 +115×x207+ 214×x208 +214×x209 +211×x210 +24×x211 +49×x212 +62×x213 +153×x214 +218×x215+ 214×x216 +76×x217 +67×x218 +212×x219 +52×x220 +152×x221 +159×x222 +185×x223+ 198×x224 +90×x225 +105×x226 +19×x227 +147×x228 +142×x229 +58×x230 +141×x231+ 48×x232 +103×x233 +238×x234 +114×x235 +29×x236 +92×x237 +146×x238 +63×x239+ 135×x240 +97×x241 +16×x242 +94×x243 +127×x244 +181×x245 +52×x246 +78×x247+ 30×x248 +116×x249 +124×x250 +88×x251 +137×x252 +173×x253 +188×x254
この構造は、補間攻撃を避けるのに十分、複雑な構造となっている。
しかし 、その他の構造 (鍵加算、MDSH 、MDSL) が GF(28 ) で簡単に表記できるようなものであるため、以降、S ボックスについて GF(2k ) 上の性質について詳細に評価した結果を示す。

GF(2k ) 上の近似の概要
ここでは、S ボックスの GF(2k ),k < 8 上の近似について考える。S ボックスの入出力サイズ
が 8 ビットであって，GF(2k ) への近似を考える場合，入出力の値 x ∈(GF2)8 を y ∈GF(2k ) へ変換する写像 φ をまず探索する．暗号の解析の場合には S ボックスの入力に用いる写像と出力に用いる写像が異なったものについても探索可能であるが，本稿では入出力に対する写像は同じものを考えた．
探索した φ は， n ビットの偶数パリティ値の組み合わせを考える．すなわち

φ : x → y = (yk−1yk−2 . . . y0 )yi = parity(x, maski)となる φ であり，maski は一次独立であるものを考える．
ある写像 φ については，d 次のすべての GF(2k ) 上の関数
(ただし ，d 次の係数は非ゼロ ) について確率評価を行う．GF(2k ) 上の関数 f に対する確率評価の定義は以下の通り．

bias(φ,f) = #{x|f (φ(x)) = φ(S(x))} − 28 /2k(5)

GF(22 ) 上の近似
上記で考えたような 8 ビット値から GF(22 ) への写像の取り方は、0 でない異なるマスク値
mask0, mask1 の組み合わせであるので 255 × 254 とおり存在する。これらについてすべてのマスクの組み合わせを探索し 、GF(22 ) 上の d 次関数による近似の確率を評価した。この結果を次に示す。
一次式による近似
一次式の近似で、最も確率の高かったもの (近似確率 88/256=24/256+1/4、よって bias =24/256)9 例を以下に示す。ここで第三者が容易に検証できるように、φ(x) と φ(S(x)) の分布 dist

16

も一緒に示す。これは 4 × 4 の二次元配列として考え、dist[a][b] は φ(x) = a かつ φ(s(x)) = b となる入力 x の個数を示している。

mask = (7, 233), f (x) = x + 3
dist = {10, 16, 10, 28, 12, 18, 24, 10, 24, 18, 12, 10, 18, 12, 18, 16)
mask = (7, 233), f (x) = 2x + 3
dist = {10, 16, 10, 28, 12, 18, 24, 10, 24, 18, 12, 10, 18, 12, 18, 16)
mask = (7, 238), f (x) = x + 1
dist = {10, 28, 10, 16, 18, 16, 18, 12, 24, 10, 12, 18, 12, 10, 24, 18)
mask = (7, 238), f (x) = 3x + 1
dist = {10, 28, 10, 16, 18, 16, 18, 12, 24, 10, 12, 18, 12, 10, 24, 18)
mask = (121, 129), f (x) = x + 3
dist = {12, 12, 12, 28, 14, 18, 20, 12, 16, 18, 16, 14, 22, 16, 16, 10)
mask = (121, 248), f (x) = x + 1
dist = {12, 28, 12, 12, 22, 10, 16, 16, 16, 14, 16, 18, 14, 12, 20, 18)
mask = (129, 248), f (x) = x + 1
dist = {12, 28, 12, 12, 22, 10, 16, 16, 14, 12, 18, 20, 16, 14, 18, 16)
mask = (233, 238), f (x) = x + 1
dist = {10, 28, 16, 10, 18, 16, 12, 18, 12, 10, 18, 24, 24, 10, 18, 12)mask = (233, 238), f (x) = 2x + 1
dist = {10, 28, 16, 10, 18, 16, 12, 18, 12, 10, 18, 24, 24, 10, 18, 12)
二次式による近似
二次式の近似で、最も確率の高かったもの (近似確率 88/256=24/256+1/4)6 例を以下に示す。

mask = (7, 233), f (x) = x2 + 3
dist = (10, 16, 10, 28, 12, 18, 24, 10, 24, 18, 12, 10, 18, 12, 18, 16)
mask = (7, 238), f (x) = 2x2 + 1
dist = (10, 28, 10, 16, 18, 16, 18, 12, 24, 10, 12, 18, 12, 10, 24, 18)17

mask = (86, 147), f (x) = x2
dist = (24, 12, 14, 14, 12, 24, 14, 14, 14, 14, 16, 20, 14, 14, 20, 16)
mask = (86, 197), f (x) = 2x2
dist = (24, 14, 14, 12, 14, 16, 20, 14, 14, 20, 16, 14, 12, 14, 14, 24)
mask = (147, 197), f (x) = 3x2
dist = (24, 14, 12, 14, 14, 16, 14, 20, 12, 14, 24, 14, 14, 20, 14, 16)
mask = (233, 238), f (x) = 3x2 + 1
dist = (10, 28, 16, 10, 18, 16, 12, 18, 12, 10, 18, 24, 24, 10, 18, 12)
三次式による近似
三次式の近似で、最も確率の高かったもの (近似確率 94/256=30/256+1/4)6 例を以下に示す。

mask = (7, 233, ), f (x) = x3 + 2x2 + 2x + 3
dist = (10, 16, 10, 28, 12, 18, 24, 10, 24, 18, 12, 10, 18, 12, 18, 16)
mask = (7, 233, ), f (x) = 3x3 + 3x2 + 1x + 3
dist = (10, 16, 10, 28, 12, 18, 24, 10, 24, 18, 12, 10, 18, 12, 18, 16)
mask = (7, 238, ), f (x) = x3 + 3x2 + x + 1
dist = (10, 28, 10, 16, 18, 16, 18, 12, 24, 10, 12, 18, 12, 10, 24, 18)
mask = (7, 238, ), f (x) = 3x3 + x2 + 3x + 1
dist = (10, 28, 10, 16, 18, 16, 18, 12, 24, 10, 12, 18, 12, 10, 24, 18)
mask = (233, 238, ), f (x) = x3 + 2x2 + x + 1
dist = (10, 28, 16, 10, 18, 16, 12, 18, 12, 10, 18, 24, 24, 10, 18, 12)mask = (233, 238, ), f (x) = 2x3 + x2 + 2x + 1
dist = (10, 28, 16, 10, 18, 16, 12, 18, 12, 10, 18, 24, 24, 10, 18, 12)
GF(23 ) 上の近似
8 ビット値から GF(23 ) への写像の取り方は、0 でない異なるマスク値 mask0, mask1, mask2の組み合わせであるので 255 × 254 × 253 とおり存在する。このうち三つのマスク値が一次独立であるもののみを探索したので実際に探索したマスク値の組み合わせは 255 × 254 × 253 よりわ
ずかに少ない。マスクの組み合わせについて探索し 、GF(23 ) 上の d 次関数による近似の確率を評価した。この結果を次に示す。
18

一次式による近似
一次式の近似で、最も確率の高かったもの (近似確率 57/256=25/256+1/8)7 例を以下に示す。

mask = (40, 99, 215), f (x) = 2x + 7
mask = (61, 83, 185), f (x) = 3x + 4
mask = (61, 185, 234), f (x) = 5x + 6
mask = (83, 110, 234), f (x) = 7x + 4
mask = (99, 180, 255), f (x) = 2x + 1
mask = (110, 132, 185), f (x) = 7x + 6
mask = (132, 215, 234), f (x) = 3x + 7
二次式による近似
二次式の近似で、最も確率の高かったもの (近似確率 58/256=26/256+1/8)2 例を以下に示す。

mask = (1, 7, 222), f (x) = 4x2 + 3
mask = (7, 217, 223), f (x) = x2 + 7
三次式による近似
三次式の近似で、最も確率の高かったもの (近似確率 66/256=34/256+1/8)5 例を以下に示す。

mask = (7, 27, 238), f (x) = 7x3 + 5x2 + x + 3
mask = (7, 238, 245), f (x) = 3x3 + 7x2 + x + 5
mask = (27, 28, 245), f (x) = 6x3 + 4x2 + x + 5
mask = (28, 233, 238), f (x) = x3 + x2 + x + 2
mask = (233, 242, 245), f (x) = 5x3 + 3x2 + x + 5
四次式以上による近似
ここの近似は探索が終了しておらず、上記の確率を上回る確率近似が見付かっていない。参考までに見付かった近似のいくつかを示す。

65/256 : mask = (7, 117, 238), f (x) = 7x4 + 2x3 + 6x2 + 6x + 1
62/256 : mask = (1, 54, 239), f (x) = 7x5 + 6x4 + 6x3 + 2x2 + 3x + 5
62/256 : mask = (1, 55, 238), f (x) = 3x5 + 2x4 + 4x3 + 5x2 + 4x + 3
62/256 : mask = (1, 60, 185), f (x) = x5 + 4x3 + x2 + 7x + 7
62/256 : mask = (1, 61, 185), f (x) = 6x5 + 2x4 + x3 + 4x + 5

MDSL 、MDSH への評価
Hierocrypt-L1 では二種類の線形関数、MDSL と MDSH 、を用いている。MDSL では主にビッ
ト毎の撹拌と隣接する 4 つの S ボックスとの撹拌を行っている。これとは対照的に MDSH では
バイト単位による撹拌で、データブロック全体的な撹拌を目的とする。
19

このため、上記で評価を行った S ボックスの代数近似を暗号全体への評価に拡張するときには 、各マスク値を線形撹拌層に応じて伝播させて、各段のマスク値 (すなわち φ) を決定する必要がある。
MDSH はバイト毎の排他論理和であるため、上記の S ボックスの代数近似は出力多項式の和として表現することができる。したがって、(鍵加算)-(S ボックス)-(MDSH)-(鍵加算)-(S ボックス) の部分は効率的に近似が可能であるが、MDSL については (MDS のため) 複雑なビット単位の演算が含まれ 、上記の近似ではうまく表現できない。ゆえに 、暗号全体での近似もうまく表現できないと考えられる。

5.2

Hierocrypt-L1 の S ボックスの部分補間

これまで Hierocrypt-L1 のデータ撹拌部分は S ボックスを除いた、鍵加算、MDSH 、HDSLのどれもが x8 + x6 + x5 + x + 1 により定義される有限体上の演算上で簡単に表記することができる。
S ボックスの完全な補間については上でも示したように次数、項数ともに十分大きな値となっている。しかし 、部分的な補間 (すなわち入力空間 256 ではなくそのうちの一部) を行った補間をすることで次数や項数が減ることは自明である。ただし 、この場合、暗号全体の代数近似の確率がより小さくなるため必要な既知平文数が増加すると考えられる。したがって、効率的な攻撃を考える場合、近似の確率と近似の項数および 次数のトレード オフを考えて S ボックスを近似する必要があるが 、このトレード オフは以下の (自明な) 定理以上の評価についてはあまり知られていない。

S ボックスの 256 個の入力のうち n 個の入力に対して補間を行った場合、n − 1 次定理 5.1:
以下の多項式により近似が可能でその場合の項数は n 項以下である。
以下では、部分的な S ボックスの補間を行った実験結果についてまとめる。
部分補間の探索
評価者による部分空間に対する補間の探索では、以下の手順を繰り返して、いくつかの t について探索を行った。

1. t 個の入力からなる部分空間を選択
2. 補間式適用
3. 入力全体に対して、いくつの入力を補間たことになっているか計測
この結果を表 3に示す。係数は GF(28 ) 上の元であるが 、10 進数表記をしている。点も 10 進数表記である。t = 2, 3, 4 の場合については探索を終了したが 、5 以上については現時点で見付かったもののうちもっとも補間した点の多いものを示している。
その他 S ボックスの解析
暗号の安全性には全く言及できない性質であるが 、S ボックスの解析結果として以下のものを列挙しておく。

20

S ボックスの固定点:S(6716 ) = 6716
S ボックスを OFB 的に用いたときの周期: 周期 30738=109 × 47 × 2 × 3
個々の要素の周期 (要素は 16 進数表記):
周期が 109( 素数) のもの
00 → 07 → 4e → ec → 8d → 58 → 94 → 6b → b6 → 26 → 3d → 3e → f9 → cb → 14 → 9d
→ f0 → ea → db → 40 → 21 → 9b → 33 → c9 → 8a → 4a → 57 → b1 → d4 → 93 → f8 → 8f
→ 0a → ce → 35 → ed → dc → cd → cf → 45 → 0d → e9 → 4c → bd → a6 → e3 → 76 → b7
→ 2b → f7 → 1d → 5f → 0f → 80 → 06 → 84 → 1b → a4 → 0e → 5d → c0 → ad → 5c → fb
→ 4f → 1e → 19 → 7a → 7d → b0 → 49 → 01 → fc → 16 → f5 → 0c → 02 → 55 → 09 → 75
→ 23 → d3 → 74 → 12 → 78 → d0 → 50 → 37 → 27 → 6f → df → a3 → 63 → 56 → f1 → 15
→ 2e → ac → 38 → 69 → 03 → 70 → d6 → da → e4 → 36 → de → 97 → b8 → 00
周期が 141(= 3 × 47) のもの
04 → 98 → 22 → 9c → e7 → 3a → 72 → cc → 6e → 9e → 71 → 83 → c5 → c7 → f2 → dd
→ ba → 90 → 2c → 8c → ef → 2a → 4d → 85 → 79 → 39 → 30 → 3c → 95 → e6 → 28 → b9
→ 86 → 4b → e5 → 32 → 41 → 8b → c4 → eb → d9 → 53 → 9a → b3 → f3 → c2 → a1 → 89
→ 88 → bf → 05 → 8e → 3f → d8 → a9 → 64 → 96 → 20 → 0b → 18 → c6 → e2 → 25 → 77
→ 65 → 13 → 42 → 44 → 11 → 60 → 61 → 7f → 1f → 87 → 66 → c1 → 68 → 99 → 43 → d7
→ ae → f4 → a5 → 6d → fa → b4 → bb → ﬀ → a0 → 52 → b5 → 54 → 7c → d5 → e1 → 31
→ 5a → 82 → 34 → 29 → 2d → a7 → be → 7b → 3b → a8 → 59 → 81 → c8 → 46 → 48 → 6a
→ 5e → 51 → 9f → 7e → af → 5b → 08 → bc → fe → aa → ee → 62 → 1a → 2f → 17 → e8
→ 24 → c3 → 10 → 1c → b2 → e0 → 91 → 73 → a2 → 47 → fd → ab → f6 → 04
周期が 1 のもの
67 → 67
周期が 2 のもの
6c → ca → 6c
周期が 3 のもの
92 → d1 → d2 → 92

6

まとめHierocrypt-L1 は、新しい構造の鍵スケジュールと、SPN 構造に基づくデータ撹拌部分からなるブロック暗号アルゴ リズムである。
評価者は、Hierocrypt-L1 に対していくつかの限られた方向からの安全性評価を行い、いく
つかの考察を述べた。
自明な欠点の発見を目的とした注意深い鍵スケジュール部の解析では 、拡大鍵間の簡単な依存関係のいくつかを示したが 、これらは暗号全体の安全性にはまったく影響がないと考えられる。
データ撹拌部分では、特にバイトオリエンティッド な構造に着目して限られた種類の S ボックスの解析を示したが 、いずれも Hierocrypt-L1 の安全性を言及するに及ばない性質である。しかし 、バイト単位の処理がすべてであり、これについては特に代数的な性質に注意を払う必要がある。
今回の詳細評価は Hierocrypt-L1 の安全性の保証には足りない内容であり、今後、特にバイト単位の処理に着目した安全性評価を期待したい。

21

参考文献
[1] 暗 号 技 術 仕 様 書:
Hierocrypt-L1,
security/hierocrypt/.

availableat

http://www.toshiba.co.jp/rdc/[2] 暗 号 技 術 仕 様 書:
Hierocrypt-3,
security/hierocrypt/.

availableat

http://www.toshiba.co.jp/rdc/[3] Speciﬁcation on a Block Cipher: Hierocrypt-L1, available at http://www.toshiba.co.jp/
rdc/security/hierocrypt/.
[4] 大熊建司, 村谷博文, 佐野文彦, 本山雅彦, 川村信一, 「ブロック暗号 Hierocrypt-3 およびHierocrypt-L1 に対する強度/性能評価」, 信学技報 ISEC2000-71, 電子情報通信学会, 2000.
[5] J. Kelsey, B. Schneier, “Key Schedule Weakness in SAFER+,” Second AES Candidate Conference, 1999, available at http://www.counterpane.com/safer.html[6] E. Biham, A. Biryukov, N. Ferguson, L. Knudsen, B. Schneier, A. Shamir, “Cryptanalysis of Magenta,” Second AES Candidate Conference, 1999, available at http://
www.counterpane.com/magenta-cryptanalysis.html.
[7] A. Biryukov, D. Wagner, “Slide Attacks,” Fast Software Encryption, 6th International Workshop, FSE’99, Proceedings, Lecture Notes in Computer Science Vol. 1636, Springer-Verlag,
1999.
[8] L. Knudsen, “Cryptanalysis of LOKI,” Advances in Cryptology, –ASIACRYPT’91, Lecture
Notes in Computer Science Vol. 739, Springer-Verlag, 1991.
[9] C. H. Meyer, S. M. Matyas, Cryptography: A New Dimension in Coputer Data Security,
New York: John Wiley & Sons, 1982.
[10] J. Daemen, L. Knudsen, V. Rijmen, “The Block Cipher Square,” Fast Software Encryption,
4th International Workshop, FSE’97, Proceedings, Lecture Notes in Computer Science Vol.
1267, Springer-Verlag, 1997.
[11] J. Daemen, V. Rijmen, “AES Proposal: Rijndael,” available at http://www.esat.
kuleuven.ac.be/~rijmen/rijndael/index.html[12] C. H. Lim, “A Revised Version of Crypton -Crypton V1.0,” Fast Software Encryption,
6th International Workshop, FSE’99, Proceedings, Lecture Notes in Computer Science Vol.
1636, Springer-Verlag, 1999.
[13] L. Knudsen, T. Berson, “Truncated Diﬀerentials of SAFER,” Fast Software Encryption,
third International Workshop, Proceedings, Lecture Notes in Computer Science Vol. 1039,
Springer-Verlag, 1999.

22Z1(-1)Z2(-1)

Z3(-1)

V(0)

Z1(0)

Z4(-1)

M5
MB
G(0)
Z2(0)

Z3(0)

Z4(0)

Note: M5 = MB

-1

P
W1(0)
V(1)

Z1(1)

W2(0)
M5
MB
G(1)

Z2(1)

Z3(1)

Z4(1)

Z1(7)

Z2(7)

Z3(7)

P -1

P
W1(1)
V(2)

Z1(2)

W2(1)

W1(7)

M5
MB
G(2)
Z2(2)

Z3(2)

V(7)

Z4(2)

Z1(6)

W2(7)
MB
M5
G(6)

Z2(6)

Z3(6)

V(3)

Z1(3)

W2(2)

W1(6)

M5
MB
G(3)
Z2(3)

Z3(3)

V(6)

Z4(3)

Z1(5)

W2(6)
MB
M5
G(5)

Z2(5)

Z3(5)

V(4)

Z1(4)

W2(3)

W1(5)

M5
MB
G(4)
Z2(4)

Z3(4)

Z4(5)
P -1

P
W1(3)

Z4(6)
P -1

P
W1(2)

Z4(7)

V(5)

Z4(4)

Z1(4)

MB
M5
G(4)
Z2(4)

図 2: Intermediate keys’ generation (whole structure)

23

W2(5)

Z3(4)

Z4(4)

0x07,
0xBC,
0x1C,
0xC6,
0x0B,
0xB9,
0x3C,
0x69,
0x21,
0x6A,
0x37,
0x94,
0x61,
0x99,
0xD6,
0xD0,
0x06,
0xBF,
0x2C,
0x22,
0x52,
0x59,
0x49,
0x00,
0xAD,
0x46,
0x50,
0xA9,
0x91,
0x24,
0xEA,
0x8F,

表 2: Evaluated S box (Hierocrypt-L1)
0xFC, 0x55, 0x70, 0x98, 0x8E, 0x84,
0x75, 0xCE, 0x18, 0x02, 0xE9, 0x5D,
0x60, 0x78, 0x42, 0x9D, 0x2E, 0xF5,
0x7A, 0x2F, 0xA4, 0xB2, 0x5F, 0x19,
0x9B, 0x9C, 0xD3, 0xC3, 0x77, 0x3D,
0x2D, 0x4D, 0xF7, 0x8C, 0xA7, 0xAC,
0x5A, 0x41, 0xC9, 0x29, 0xED, 0xDE,
0x30, 0x72, 0xA8, 0x95, 0x3E, 0xF9,
0x8B, 0x44, 0xD7, 0x11, 0x0D, 0x48,
0x01, 0x57, 0xE5, 0xBD, 0x85, 0xEC,
0x9F, 0xB5, 0x9A, 0x7C, 0x09, 0xF1,
0x81, 0x82, 0x08, 0xFB, 0xC0, 0x51,
0x7F, 0x1A, 0x56, 0x96, 0x13, 0xC1,
0x03, 0x5E, 0xB6, 0xCA, 0xFA, 0x9E,
0x83, 0xCC, 0xA2, 0x12, 0x23, 0xB7,
0x39, 0x7D, 0x3B, 0xD5, 0xB0, 0xAF,
0xC8, 0x34, 0xC5, 0x1B, 0x79, 0x4B,
0x88, 0x4A, 0xC4, 0xEF, 0x58, 0x3F,
0x73, 0xD1, 0xF8, 0x6B, 0xE6, 0x20,
0x43, 0xB3, 0x33, 0xE7, 0xF0, 0x71,
0x89, 0x47, 0x63, 0x0E, 0x6D, 0xE3,
0x64, 0xEE, 0xF6, 0x38, 0x5C, 0xF4,
0xD4, 0xE0, 0xF3, 0xBB, 0x54, 0x26,
0x86, 0x90, 0xFF, 0xFE, 0xA6, 0x7B,
0x68, 0xA1, 0x10, 0xEB, 0xC7, 0xE2,
0x8A, 0x6C, 0x14, 0x6E, 0xCF, 0x35,
0xD2, 0x92, 0x74, 0x93, 0xE1, 0xDA,
0x53, 0xE4, 0x40, 0xCD, 0xBA, 0x97,
0x31, 0x25, 0x76, 0x36, 0x32, 0x28,
0x4C, 0xDB, 0xD9, 0x8D, 0xDC, 0x62,
0x15, 0xDD, 0xC2, 0xA5, 0x0C, 0x04,
0xCB, 0xB4, 0x4F, 0x16, 0xAB, 0xAA,

24

0x4E
0x80
0xE8
0x87
0x6F
0x17
0x27
0xD8
0xFD
0x1E
0xB1
0x0F
0x67
0xDF
0x65
0x1F
0x66
0x0A
0xB8
0x7E
0xBE
0x5B
0x2B
0x05
0xF2
0x45
0xAE
0xA3
0x3A
0x2A
0x1D
0xA0

表 3: Partial interpolations of the S box

terms/deg/points
2 1
8
3 2
9
3 2
9
3 2
9
3 2
9
3 2
9
3 2
9
3 2
9
3 2
9
3 2
9
3 2
9
3 2
9
3 2
9
3 2
9
4 3
13

equation
237+59×x
142+147×x+81×x2
103+219×x+191×x2
101+216×x+239×x2
98+196×x+34×x2
206+36×x+205×x2
3+114×x+139×x2
77+119×x+33×x2
192+112×x+124×x2
187+94×x+61×x2
89+72×x+16×x2
10+143×x+109×x2
212+236×x+211×x2
46+183×x+148×x2
65+190×x+101×x2 +171×x3

25

points(56, 92, 93, 106, 158, 172, 227, 241)(4, 38, 107, 136, 165, 176, 209, 241, 255)
(11, 14, 42, 62, 70, 100, 233, 243, 245)
(13, 40, 53, 55, 174, 232, 235, 249, 255)
(15, 122, 143, 170, 175, 210, 211, 219, 226)
(21, 44, 98, 117, 175, 196, 228, 238, 247)
(23, 63, 73, 122, 124, 131, 139, 150, 214)
(24, 75, 99, 107, 111, 134, 150, 201, 231)
(26, 60, 68, 113, 123, 133, 154, 199, 206)
(32, 46, 111, 153, 188, 200, 209, 217, 245)
(36, 53, 69, 78, 103, 120, 170, 242, 250)
(40, 63, 92, 94, 96, 150, 175, 186, 192)
(41, 71, 78, 121, 141, 143, 158, 171, 248)
(65, 73, 77, 79, 112, 143, 153, 194, 225)
(21, 33, 35, 61, 77, 82, 90, 104, 171, 173,
190, 213, 246)