種も仕掛けもない数 (暗号)

暗号理論における種も仕掛けもない数 (Nothing-up-my-sleeve number) とは、なんらかの性質が隠されていないことが自明であるように作られた数を指す。こういった数は暗号学的ハッシュ関数やテンプレート:日本語版にない記事リンクといった暗号学的関数を設計する際に用いられる。これらのアルゴリズムはしばしばデータを初期化したりデータに加え入れたりするための適当な定数を必要とするが、暗号設計者はこれらの定数が悪意ある目的（例えばバックドアを仕込むなど）で選ばれたものでないことを明示したい場合がある。このようなときには調節の余地が少ないよう作られた数を使うことができる。例えば円周率の最初の何桁かを定数として採用するなどである。一方で「円周率の小数点以下何桁も後ろの方」などは、暗号設計者が後で悪用するための秘密の脆弱性を仕込むことを目的として作為的にその位置を選んだ可能性があるので、信頼できるとはみなされない。

円周率、ネイピア数、代数的無理数などの実数を位取り記数法で表記したときの桁は均等に出現すると予想されている（正規数を参照）。これらの数は一見ランダムではあるものの情報量は非常に低いので、コルモゴロフ複雑性の観点からは乱数ではない。こういった数を用いることは 1975 年アメリカ合衆国政府から発表された Data Encryption Standard (DES) に関する初期の論争が動機づけとなった。DES は S ボックスで用いている定数に対する説明がないことで批判を受けていたのである（実際には現在でいうところの差分解読法を防ぐため注意深く選択された定数であったことがのちに判明したが）。こういった事情から、暗号に用いる定数を生成するためのより透明性の高い方法の必要性が感じられていた。

袖に隠されたカード

「種も仕掛けもない数」は英語では "nothing-up-my-sleeve number" というが、"nothing up my sleeve" とはマジシャンがマジックを行う前に袖を開いて何も隠していないことを示すときに使うフレーズである。

例

• ロナルド・リベストは今日広く使われている MD5 ハッシュにおいて正弦関数を定数の生成に用いた。
• アメリカ国家安全保障局 (Nasional Security Agency, NSA) は Secure Hash Algorithm のうち SHA-1 と SHA-2 において、最初の 8 個の素数の平方根を定数の生成に用いた。また SHA-1 はハッシュ計算の初期値として 0x0123456789ABCDEFFEDCBA9876543210F0E1D2C3 を用いている。
• Blowfish 暗号はテンプレート:仮リンクの初期化に円周率の二進表記（最初の 3 は除く）を用いている。
• テンプレート:IETF RFCは internet key exchange に用いられる素数（それ自体も円周率から生成されたもの）について記述している。
• テンプレート:仮リンク の S ボックス はアメリカ独立宣言を基に作られた。
• Advanced Encryption Standard の候補だった テンプレート:仮リンク で用いられているすべての任意定数（S ボックス内のすべてのエントリを含む）はネイピア数の二進表記から作られた。
• ARIA は 1/テンプレート:Pi の二進表記を鍵スケジュールに用いている。
• RC5 の鍵スケジュールはネイピア数と黄金数の二進表記を鍵スケジュールに用いている。
• テンプレート:仮リンク や テンプレート:仮リンク などの複数の暗号が用いている 0x9e3779b9（十進法では 2654435769）は $\lfloor 2^{32}/\varphi \rfloor$ である（$\varphi$ は黄金数）。
• SHA-3 の最終候補だった BLAKE は 16 個の定数を用いており、それらは円周率の二進表記における小数部分の先頭 512 ビットおよび 1024 ビットになっている。
• KASUMI の鍵スケジュールは鍵の変形に 0x123456789ABCDEFFEDCBA9876543210 を用いる。
• Salsa20 ファミリーの暗号は文字列 "expand 32-byte k" を ASCII コードで表現したものをブロックの初期化に用いる。
• Bcrypt は "OrpheanBeholderScryDoubt" を初期化文字列として用いる。

異なる例

• テンプレート:仮リンク ハッシュの S ボックスはランダムに生成されたものだと主張されていた。しかし解析の結果、実際にはアルゴリズム的に生成されたものであり、いくつかの「難解な」弱点を有することが判明した。
• DES は NSA により指定された定数を含んでいた。実際にはランダムからは程遠かったことが判明したものの、それらの定数は当時まだ公には知られていなかった差分解読法への耐性を強めていた。
• アメリカ国立標準技術研究所が推奨していた暗号論的擬似乱数生成器 テンプレート:仮リンク において使用が推奨されていた定数は、過去の出力履歴からその先の出力を開発者が予測できるようにするために選択されたものであった可能性があるとして、2007 年に批判を受けた。2013 年 9 月、The New York Times は「元 NSA の請負人であったエドワード・スノーデンによる内部情報リークによると、NSA が開発し NIST standard 2006 (Dual EC DRBG standard) に使用されていた疑似乱数生成機は NSA のためのバックドアを持っていた」と報じた。
• 楕円曲線暗号に用いるため NSA により標準化された楕円曲線 P curve の係数は、特に説明のないテンプレート:仮リンクから計算されたハッシュ値であった。以下はその表である。
  • P-224: bd713447 99d5c7fc dc45b59f a3b9ab8f 6a948bc5
  • P-256: c49d3608 86e70493 6a6678e1 139d26b7 819f7e90
  • P-384: a335926a a319a27a 1d00896a 6773a482 7acdac73

直接的に関係のある話ではないが、Dual_EC_DRBG のバックドアが暴かれて以降、NIST による P curve の定数に対する疑念は、NSA が秘密鍵を割り出しやすくするためにそれらの定数を定めたのではないかという懸念につながった。それ以降、多くのプロトコルやプログラムは NIST P-256 の代わりに Curve25519 を使い始めた。

限界

バーンスタイン及びその共著者たちは、楕円曲線などの暗号オブジェクトを生成する複雑な手続きの開始点として「種も仕掛けもない数」を用いることはバックドアが仕込まれることを防ぐには十分ではない可能性を示した。例えば円周率、ネイピア数、オイラーの定数、√2, √3, √5, √7, log(2), 黄金数、ζ(3), ζ(5), sin(1), sin(2), cos(1), cos(2), tan(1), tan(2) などの一見すると無害で「興味をひかない」簡単な数学定数であっても、バイナリにおける表現方法は多数ある。またこれらの定数をシードとして用いるとき、SHA-1, SHA-256, SHA-384, SHA-512, SHA-512/256, SHA3-256, SHA3-384 など数多くのハッシュ関数を採用することができる。

暗号オブジェクトの選定において調節可能なパラメータが十分に多くある場合、組み合わせ爆発によって暗号化手法と一見簡単な数学定数の組み合わせは非常に大きくなる。したがって、機械的な探索によって所望のバックドアを持つオブジェクトを作ることが可能となってしまう。

参照

• Bruce Schneier. Applied Cryptography, second edition. John Wiley and Sons, 1996.
• テンプレート:仮リンク, Adi Shamir, (1990). Differential Cryptanalysis of DES-like Cryptosystems. Advances in Cryptology – CRYPTO '90. Springer-Verlag. 2–21.