Sボックス

Sボックス（Substitution Box）とは

暗号技術において、Sボックス（Substitution Box、またはS-box）は、共通鍵[[暗号]]の基本的な構成要素の一つです。特にブロック[[暗号]]において、平文と暗号文の間の関係を複雑にする、つまり非線形性を導入するために使用されます。これにより、暗号解読に対する耐性を高める重要な役割を果たしています。

Sボックスの概要

Sボックスは、mビットの入力をnビットの出力に変換する関数です。この変換は、2^m個のエントリを持つルックアップテーブルとして実装されることが一般的です。初期の暗号では、DESのように固定されたテーブルが使われることが多かったですが、近年ではBlowfishやTwofishのように、鍵に基づいて動的にテーブルを生成する方式も採用されています。

例えば、1970年代に設計されたDESでは、6ビット入力を4ビット出力に変換するSボックスが8種類使用されていました。一方、2000年代に設計されたAESやCamelliaでは、8ビット入出力のSボックスが1種類（Camelliaでは4種ですが、実質的には1種の変換）使用されています。これは、ソフトウェアやハードウェアでの実装において、スピードだけでなくサイズ縮小を考慮したためです。

Sボックスの設計

Sボックスの設計は非常に複雑で、DESの開発時には、IBMの大型コンピュータを数ヶ月も使用したと言われています。Sボックスの設計が不十分だと、暗号が容易に解読される可能性があります。例えば、Lucifer暗号では、Sボックスが脆弱だったため、わずか40個の選択平文で解読されました。

DESの設計では、差分解読法に対する耐性が考慮されていました。しかし、1990年代初頭に差分解読法や線形解読法が発見され、これらの攻撃に耐性を持つことが安全なSボックスの必要条件と認識されました。

理論的には、nビット入出力のSボックスの場合、2の拡大体GF(2^n)での逆変換が差分攻撃や線形攻撃に対して最も強いと考えられています。この時、差分確率及び線形確率はnが奇数の場合2^(-n+1)、偶数の場合2^(-n+2)となります。AESやCamelliaでは、この逆変換に線形変換を施したものが使われています。その結果、差分確率と線形確率は2^(-6)となっています。

近年では、実装サイズの縮小を目的として、小さなSボックスを複数組み合わせて大きなSボックスを構成する手法が取られることがあります。この場合、最善の最大差分（または線形）確率を持つとは限りませんが、暗号全体で十分な最大特性差分（または線形）確率を持つように設計されます。

DESのSボックスの具体例

DESで使用されているSボックスの一つであるS5を例に見てみましょう。

S5は、6ビットの入力を受け取り、4ビットの出力を生成します。入力の6ビットは、中間の4ビットと、最上位ビット（MSB）と最下位ビット（LSB）の2ビットに分けられます。このMSBとLSBが、テーブルの行を決定し、中間の4ビットが列を決定します。例えば、入力が "011011" の場合、MSBとLSBは "01" で、中間の4ビットは "1101" です。したがって、S5はテーブルの特定の行と列を参照し、出力として "1001" を生成します。

DESのSボックスの設計と公開

DESの規格作成時には、8つのSボックスの設計方針は公開されませんでした。そのため、設計者だけが知っているバックドアが仕込まれているのではないかという疑念が長年にわたり持たれました。しかし、差分解読法が再発見され、線形解読法によるDESの解読実験が成功した1994年になって、Sボックスの設計方針が公開されました。それによると、Sボックスは差分解読に対して耐性を持つように注意深く設計されていましたが、線形解読法に対しては考慮されていませんでした。

参考文献

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)

もう一度検索