Sボックス

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

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

通常は、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(2m)での逆変換が差分・線形解読に対して最も強いテーブルと考えられている。このとき、差分確率及び線形確率は、 n が奇数の場合 2-n+1 、偶数の場合 2-n+2 となる。AESやCamelliaではそれを線形変換したものが採用されており、差分確率及び線形確率は、 2-6 である。

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

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

S5入力の中間4ビット0000000100100011010001010110011110001001101010111100110111101111MSBLSB000010110001000001011110101011011010000101001111111101000011101001011110101100101100010001111101000101010000111110100011100110000110100100001000011011101011010111100011111001110001010110001100001110111011100011000111000111100010110101101111000010011010010001010011

入力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. 
 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)

Sほつくす