新しいフォルダー（１）

メモです。よろしくおねがいします。

[暗号] Sボックス

暗号

ITC Advent Calendar ６日目.

今日はSボックスについてです.

誰も興味ないとか知らねーです.

Sボックス

Sボックス(subscription box, S-box)とは, 平文と暗号文の相関(線形性)を壊すための仕組みとして利用される関数のことである.

Sボックスは, mビットの入力をnビットに変換して出力する関数であり, 2mのルックアップテーブルによって実装される.

DESなどの多くのブロック暗号では固定のテーブルが使用されるが, BlowfishやTwofishなどのように鍵によって動的にテーブルが生成されることもある.

1970年代に設計されたDESでは６bitの入力から４bitを出力するSボックスを８種類使用しているが, 2000年代に設計されたAESでは８bit入出力のSボックスを１種類, Camelliaでは８bit入出力のSボックスを４種類(それぞれのSボックスは１つ目のSボックスを単純に変換したもの)使用したものとなっている.

これは, ソフトウェアやハードウェアでの実装時に, スピードだけでなくサイズ縮小も優先させた実装も考慮したためである.

ちなみに, DESのSボックスは設計時にIBMの大型コンピュータを数ヶ月使ったほど難しいと言われている.

これは, DESの基となった暗号であるLuciferのSボックスが弱く, 40個の選択平文で破られたため, DESには差分解読法への耐性を持つことを設計方針にしていたためである.

また, 1980年代末に差分解読法が一般に発表(IBM内ではすでに知られていた), 1990年代前半に線形解読法が発見され, これらの解読法に対して耐性を持つことが安全なSボックスの必要条件と認識された.

証明はされていないが, nビット入出力のSボックスの場合, 2の拡大体GF(2m)での逆変換が差分解読法と線形解読法に対して最も強いテーブルだと考えられている.

このとき, 差分確率及び線形確率は, nが奇数の場合は2-n + 1, 偶数の場合は2-n + 2となる.

AESやCamelliaではそれを線形変換されたものが採用されており, 差分確率及び線形確率は2-6である.

近年では, 実装サイズの縮小を目的に小さいSボックスを複数組み合わせて大きなSボックスを構成する方法が取られることがある.

この場合, 上述したような最善の最大差分確率, 最大線形確率は持たないが, 暗号全体で十分な最大特性差分確率, 最大特性線形確率を持つように設計される.

DESにおけるSボックス

DESの６bit入力４bit出力の８つのSボックスのテーブルを以下に示す.

S1 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
00 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
01 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
10 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
11 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
S2 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
00 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
01 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
10 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
11 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
S3 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
00 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
01 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
10 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
11 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 121
S4 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
00 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
01 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
10 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
11 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
S5 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
00 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14|9
01 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8|6
10 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0|14
11 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5|3
S6 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
00 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
01 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
10 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
11 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
S7 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
00 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
01 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
10 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
11 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
S8 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
00 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
01 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
10 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
11 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11

例えば, S5に011011が入力された場合, １bit目と６bit目を合わせた01と中間４bitである1101に分割され, テーブル中でそれぞれが交わる9, つまり1001が出力される.

DESの規格が公開された際, Sボックスについての設計方針が公開されなかったため, 設計者だけが知っているバックドアが仕組まれているのではないかという点について多年に渡る研究がなされた.

それにより差分解読法が発見され(IBM内ではすでに知られていた), 線形解読法によるDESの解読実験が成功した1944年になり, ようやくSボックスの設計方針が公開された.

このことから, DESは差分解読法に対する耐性を有するように注意深く設計されていたが, 線形解読法に対しては考慮がされていないということが明らかになった.