概要

S-Box（substitution box）は、現代の暗号学における基本的な部品である。とくに対称鍵アルゴリズム、なかでもブロック暗号で多用され、鍵と暗号文の関係を分かりにくくするための非線形性を与える。この混合の働きは、シャノンが述べた混乱の概念の中心であり、S-Boxは暗号解析に要する手間を増やす目的で選ばれる。

機能と基本形

S-Boxは、mビットの入力をnビットの出力へ写像する。簡単にいえば、2m個の項目を持つ表として直接参照できる m×n の写像であり、各項目にはnビットの値が入る。入力ビットと対応する出力をそのまま扱うのが基本的な見方だが、実装ではしばしばルックアップテーブルや小規模な代数回路が用いられる。古典的な設計の多くは固定表を使い、たとえばデータ暗号化標準がその例である。一方で、秘密鍵から表を生成する暗号もあり、そのようなものは鍵依存のS-Boxと呼ばれる。

例：DESのS-Box

DES系には、よく知られた6×4のS-Boxが8個あり、一般的な設計上の考え方を示している。各6ビット入力は4ビット出力を選び、外側の2ビットで行を、内側の4ビットで小さな表の列を指定する。たとえば6ビット入力「011011」は、外側のビット「01」と内側のビット「1101」として解釈され、対応する4ビット結果を選ぶ。DESのS-Boxは、わずかな変更で暗号の安全性が大きく変わりうるため集中的に分析された。意図的に弱められた設計ではないかという懸念もあり、なぜその表が有効だったのかが公開研究の対象となった。

設計目標と評価基準

優れたS-Boxは、しばしば相反する複数の性質を満たすように設計される。代表的な目標は次のとおりである。

  • 高い非線形性：線形近似や代数的攻撃の成功率を下げる。
  • 厳密なアバランシェ効果とビット独立性：1つの入力ビットを反転させると、多くの出力ビットが予測不能に変化するようにする。
  • 出力のバランス：各出力ビットが0と1にほぼ同じ頻度で現れ、偏りを避ける。
  • 高い代数次数と低相関：代数的攻撃や相関攻撃に対抗する。
  • 差分攻撃への耐性：攻撃者に有用な入力差分パターンを最小化する。これは差分解読の発見と研究の後、とくに重視されるようになった。

歴史、論争、分析

S-Boxの選択は、ブロック暗号研究を大きく左右してきた。DESが登場した当初、S-Boxは秘密にされており、あとになって研究者たちは、隠れた弱点によって鍵なしで平文を復元できるのではないかと懸念したため、議論が起こった。差分解読のような暗号解析技術が公表されると、元の設計者たちは自分たちが用いた理論的根拠と基準を明らかにし、それらの攻撃に耐えるよう意図的に調整していたことを示した。この出来事は、S-Boxに求められる条件への理解を深め、より安全な構成のための形式的基準を促した。

変種、用途、実務上の考慮点

すべてのS-Boxが固定のルックアップテーブルであるわけではない。BlowfishやTwofishのように、初期設定時に鍵依存のS-Boxを構築する暗号もある。また、IDEAのような暗号の一部の操作は、代数的な置換手順として見ることもできる。設計者はソフトウェアとハードウェアのトレードオフを考慮しなければならない。S-Boxを大きくすると安全性が向上する場合がある一方で、メモリ使用量や実装コストは増える。さらに、S-Boxの振る舞いは、置換層や混合層など他の暗号要素、さらにはサイドチャネル漏えいのような実践的な攻撃問題とも関係する。S-BoxをP-Boxと区別し、いつ双射的（可逆）写像が必要なのかを理解することは、暗号の設計と分析では基本事項である。

S-Boxは、単純な代数的処理を難しくする非線形性を提供するため、設計者と暗号解析者の双方にとって中心的な関心事であり続けている。S-Boxの構成、分析、実装における進歩は、これからも対称暗号の安全性を形づくっていく。