Sボックス

暗号技術において、Sボックス (substitution box or S-box) とは、共通鍵暗号の基本部品の一つである関数のことである。典型的にはブロック暗号で、平文と暗号文の相関（線形性）を壊すための仕組みとして使用され、暗号解読に耐性を有するように注意深く選択する必要がある部品である。

概要[編集]

S-boxは、m ビットの入力を n ビット出力に変換する関数であり、2^m のルックアップテーブルによって実装できる。

通常は、DESのように固定テーブルとして定義されるが、暗号によっては鍵によってテーブルを動的に生成して使用するものもある。動的に生成する例として、BlowfishやTwofish がある。

1970年代に設計されたDESでは6ビット入力 4ビット出力の S-box を8種類使用しているが、2000年代に設計されたAESやCamelliaでは8ビット入出力のS-boxを1種類使用している（Camelliaでは4種の S-box を持つが、三つのS-boxは一つのS-boxの単純な変換となっている）。これはソフトウェアやハードウェアでの実装時に、スピード優先だけではなく、サイズ縮小を優先させた実装も考慮したためである。

S-boxの設計は、DES作成時にはIBM大型コンピュータを何ヶ月か使ったほど設計は難しい、と言われている。Lucifer暗号はSボックスがとても弱いため、40個の選択平文で破れた。DESは設計時に差分解読法への耐性を持つことを設計方針にしていたことが後に公開された。

1990年代前半に差分解読法・線形解読法が見つかり、これらの解読法に耐性を持つことが安全なS-boxの必要条件と認識された。（証明されていないが）nビット入出力のS-boxの場合、2の拡大体 GF(2^m)での逆変換が差分・線形解読に対して最も強いテーブルと考えられている。このとき、差分確率及び線形確率は、 n が奇数の場合 2^-n+1 、偶数の場合 2^-n+2 となる。AESやCamelliaではそれを線形変換したものが採用されており、差分確率及び線形確率は、 2^-6 である。

近年では、実装サイズの縮小を目的に小さいS-Boxを複数組み合わせて大きなS-Boxを構成する方法がとられることがある。この場合上記のような最善の最大差分(あるいは線形)確率を持たないが、暗号全体で十分な最大特性差分(あるいは線形)確率を持つように設計される。

DESのS-box[編集]

具体例としてDESの 6ビット入力 4ビット出力の S-box の一つ S₅ を示す:

S₅		入力の中間4ビット
S₅		0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
MSBLSB	00	0010	1100	0100	0001	0111	1010	1011	0110	1000	0101	0011	1111	1101	0000	1110	1001
	01	1110	1011	0010	1100	0100	0111	1101	0001	0101	0000	1111	1010	0011	1001	1000	0110
	10	0100	0010	0001	1011	1010	1101	0111	1000	1111	1001	1100	0101	0110	0011	0000	1110
	11	1011	1000	1100	0111	0001	1110	0010	1101	0110	1111	0000	1001	1010	0100	0101	0011

入力6ビットを中間の4ビットと、MSB,LSBの2ビットに分けて、行・列を選択して、出力4ビットを得る。例えば、入力 "011011" のとき、MSB,LSBは "01" で、中間の4ビットは "1101" である。そして出力として選択される4ビットは "1001" となる。

DESは、規格作成時に8個あるS-boxの設計方針が公開されなかったため、設計者だけが知っているバックドアが仕組まれているのではないかという点について多年に渡る研究がなされた。そして、差分解読法が(再)発見され、線形解読法によるDESの解読実験が成功した1994年になってS-boxの設計方針について公開された。それによるとS-boxは差分解読について耐性を有するように注意深く設計されていたが、線形解読法に対しては考慮されていなかった。

参考文献[編集]

Coppersmith, Don. (1994). The data encryption standard (DES) and its strength against attacks. IBM Journal of Research and Development, 38(3), 243–250. [1]
S. Mister and C. Adams, "Practical S-Box Design," Workshop on Selected Areas in Cryptography (SAC '96) Workshop Record, Queens University, 1996, pp. 61–76
B.SCHNEIER "Applied Cryptography" p.296-298

外部リンク[編集]

A literature survey on S-box design
John Savard's "Questions of S-Box Design"
Practical S-Box Design by S. Mister and C. Adams (PDF)

概要[編集]

DESのS-box[編集]

参考文献[編集]

関連項目[編集]

外部リンク[編集]