Sボックス
概要
編集
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ビット | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 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)