International Data Encryption Algorithm

IDEA
	IDEAの暗号化ラウンド
一般
設計者	来学嘉、James Massey
派生元	PES
後継	MMB, MESH, Akelarre, ; IDEA NXT (FOX)
暗号詳細
鍵長	128 bits
ブロック長	64 bits
構造	en:Lai-Massey scheme
ラウンド数	8.5
最良の暗号解読法
	高階の差分線形解読法で6ラウンドのIDEAを破るには、264-252の選択平文を用意し、2126.8の計算を要する(Biham et al., 2007)。

International Data Encryption Algorithm (IDEA) はチューリッヒ工科大学の James Massey と来学嘉が設計し、1991年に発表したブロック暗号。DESの代替を意図したアルゴリズムである。IDEAは PES (Proposed Encryption Standard) を若干手直しした暗号であり、元々は IPES (Improved PES) と呼ばれていた。

この暗号は Hasler Foundation（後に Ascom-Tech AG に吸収された）との研究契約の下で設計された。多数の国で特許を取得しているが、非商用利用については自由に使うことが容認されていた。"IDEA" という名称は商標でもある。アメリカにおける特許の有効期限が2012年1月をもって失効したことで、全世界で自由に使うことができるようになった。

IDEAは Pretty Good Privacy (PGP) v2.0 で使われていた。これは、v1.0で使われていたBassOmaticが安全でないと判明したために導入されたものである^[1]。IDEAはOpenPGP規格ではオプションのアルゴリズムとされている。GNU Privacy Guard (GnuPG)では、特許の失効を受けて1.4.13/2.0.20から限定的にIDEAをサポートするようになった。

操作

IDEAのブロック長は64ビットで、128ビットの鍵を使う。ラウンドと呼ばれる同じ操作を8回行い、最後に出力段の変換（ハーフラウンド）を行う。暗号化と復号の工程はよく似ている。代数学的にある意味で「非互換」とも言える異なる群からの操作（加算や乗算の合同式、ビット単位の排他的論理和 (XOR) など）を次々に行うことで、IDEAのセキュリティが生じている。演算をより詳細に述べると、すべて16ビット単位に以下のような操作を行う。

ビット単位の排他的論理和（図では青い丸に十字で示している ⊕）
加算結果を 2¹⁶ を法として合同にしたもの（緑色の四角に十字 ⊞）
乗算結果を 2¹⁶+1 を法として合同にしたもの。全てゼロのワード (0x0000) は2¹⁶と解釈する。（赤い丸にドット ⊙）

図にあるラウンドを8回繰り返した後、ハーフラウンドを最後に1回行う。ラウンドの出力は16ビットが4つ並んでいるが、このうち2番目と3番目を入れ替え、右から順に以下の操作を行う。

K1との乗算結果を 2¹⁶+1 を法として合同にする。
K2との加算結果を 2¹⁶ を法として合同にする。
K3との加算結果を 2¹⁶ を法として合同にする。
K4との乗算結果を 2¹⁶+1 を法として合同にする。

鍵スケジュール

各ラウンドでは6個の16ビット部分鍵を使い、ハーフラウンドでは4つの部分鍵を使う。8.5ラウンドの合計で52個の部分鍵を使うことになる。最初の8個の部分鍵は元の鍵から直接取り出す。すなわち、第1ラウンドのK1は元の鍵の下位16ビットで、K2はそれに隣接する16ビットというふうに128ビットの鍵から8個の鍵を取り出す。次に元の鍵を左に25ビットローテートさせて、同じように8個の鍵を取り出す。平均するとラウンドあたりのローテート回数は1より小さくなり、全体で6回ローテートすることになる。

セキュリティ

設計者らはIDEAを差分解読法への耐性を考慮して設計し、ある前提の下では安全であると結論付けた。線形または代数的な脆弱性は報告されていない。2007年現在、全ての鍵を解読できる最善の攻撃法でも6ラウンドのIDEAでないと破れない（本来のIDEAは8.5ラウンド）^[2]。なお、ここで「破る」と言っているのは、2¹²⁸未満の操作回数で攻撃が完了することを意味し、6ラウンドのIDEAへの攻撃には2⁶⁴の既知平文と2^126.8の操作を必要とする。

ブルース・シュナイアーは1996年にIDEAについて詳しく調査し、「私の意見では、現時点で一般に入手できる最良のブロック暗号アルゴリズムだ」と述べている (Applied Cryptography, 2nd ed.)。しかし1999年になると暗号解読技術が進歩したことと特許問題から、シュナイアーもIDEAを推奨しなくなった^[3]。

弱い鍵

鍵スケジュールが非常に単純であるため、IDEAには弱い鍵が存在するという問題がある。0のビットが極端に多い鍵で暗号化すると暗号文が弱くなる^[4]。しかし、鍵を無作為に生成する場合、0のビットがあまりにも多くなるということはほとんどないため、実際上あまり問題にはならない。単純な回避策としては、個々の部分鍵を使う前に 0x0DAE のような16ビット定数とXORすればよい^[4]^[5]。

2002年にはもっと大きなクラスの弱い鍵が発見された^[6]。無作為に鍵を生成する場合、これも大きな問題とはならず、定数のXORによって一部は回避できるが、この論文では全ての問題がそれで回避できるかについて確信がないとしている。このため、IDEAの鍵スケジュールを根本的に再設計したほうがよいと提案している^[6]。

入手可能性

IDEAは、オーストリア、フランス、ドイツ、イタリア、オランダ、スペイン、スウェーデン、スイス、イギリス（欧州特許番号 0482154、2011年5月16日をもって失効）、アメリカ合衆国（アメリカ合衆国特許第 5,214,703号、1993年5月25日発効、2012年1月7日をもって失効）、日本（特許第3225440号、2011年5月16日をもって失効）で特許化されている。これらの特許は2012年1月までにすべて失効しており、それ以降は自由に用いることができる。

MediaCryptはIDEAの後継として新たな暗号 IDEA NXT に注力している。IDEA NXT は以前は FOX と呼ばれ、2005年5月に公式リリースとなった。

なお、Transport Layer Security (TLS) においてもIDEAを利用可能であったが、実運用でほぼ使われていないことを理由として、TLS 1.2で削除されている (RFC 5469) 。

脚注・出典

^ Garfinkel, Simson (December 1, 1994). PGP: Pretty Good Privacy. O'Reilly Media. pp. 101–102. ISBN 978-1565920989
^ Biham, E.; Dunkelman, O.; Keller, N.. “A New Attack on 6-Round IDEA”. Springer-Verlag
^ Crypto Guru Bruce Schneier Answers Slashdot、1999年10月29日
^ ^a ^b Daemen, Joan; Govaerts, Rene; Vandewalle, Joos (1993), “Weak Keys for IDEA”, Advances in Cryptology, CRYPTO 93 Proceedings: 224–231
^ Nakahara, Jorge Jr.; Preneel, Bart; Vandewalle, Joos (2002), A note on Weak Keys of PES, IDEA and some Extended Variants
^ ^a ^b Biryukov, Alex; Nakahara, Jorge Jr.; Preneel, Bart; Vandewalle, Joos, “New Weak-Key Classes of IDEA”, Information and Communications Security, 4th International Conference, ICICS 2002, Lecture Notes in Computer Science 2513: 315–326, "While the zero-one weak keys problem of IDEA can be corrected just by XORing a fixed constant to all the keys (one such constant may be 0DAE_x as suggested in [4]) the problem with the runs of ones may still remain and will require complete redesign of the IDEA key schedule."

参考文献

Hüseyin Demirci, Erkan Türe, Ali Aydin Selçuk, A New Meet in the Middle Attack on The IDEA Block Cipher, 10th Annual Workshop on Selected Areas in Cryptography, 2004.
Xuejia Lai and James L. Massey, A Proposal for a New Block Encryption Standard, EUROCRYPT 1990, pp389–404
Xuejia Lai and James L. Massey and S. Murphy, Markov ciphers and differential cryptanalysis, Advances in Cryptology — Eurocrypt '91, Springer-Verlag (1992), pp17–38.

外部リンク

[1] Garfinkel, Simson (December 1, 1994). PGP: Pretty Good Privacy. O'Reilly Media. pp. 101–102. ISBN 978-1565920989

[idea-cryptanalysis-2] Biham, E.; Dunkelman, O.; Keller, N.. “A New Attack on 6-Round IDEA”. Springer-Verlag

[3] Crypto Guru Bruce Schneier Answers Slashdot、1999年10月29日

[weak-4] Daemen, Joan; Govaerts, Rene; Vandewalle, Joos (1993), “Weak Keys for IDEA”, Advances in Cryptology, CRYPTO 93 Proceedings: 224–231

[5] Nakahara, Jorge Jr.; Preneel, Bart; Vandewalle, Joos (2002), A note on Weak Keys of PES, IDEA and some Extended Variants

[weak2-6] Biryukov, Alex; Nakahara, Jorge Jr.; Preneel, Bart; Vandewalle, Joos, “New Weak-Key Classes of IDEA”, Information and Communications Security, 4th International Conference, ICICS 2002, Lecture Notes in Computer Science 2513: 315–326, "While the zero-one weak keys problem of IDEA can be corrected just by XORing a fixed constant to all the keys (one such constant may be 0DAE_x as suggested in [4]) the problem with the runs of ones may still remain and will require complete redesign of the IDEA key schedule."

[1]

[2]

[3]

[4]

[5]

[6]