種も仕掛けもない数 (暗号)
暗号理論における種も仕掛けもない数 (Nothing-up-my-sleeve number) とは、なんらかの性質が隠されていないことが自明であるように作られた数を指す。こういった数は暗号学的ハッシュ関数やサイファ[訳注 1]といった暗号学的関数を設計する際に用いられる。これらのアルゴリズムはしばしばデータを初期化したりデータに加え入れたりするための適当な定数を必要とするが、暗号設計者はこれらの定数が悪意ある目的（例えばバックドアを仕込むなど）で選ばれたものでないことを明示したい場合がある[1]。このようなときには調節の余地が少ないよう作られた数を使うことができる。例えば円周率の最初の何桁かを定数として採用するなどである[2]。一方で「円周率の小数点以下何桁も後ろの方」などは、暗号設計者が後で悪用するための秘密の脆弱性を仕込むことを目的として作為的にその位置を選んだ可能性があるので、信頼できるとはみなされない。
円周率、ネイピア数、代数的無理数などの実数を位取り記数法で表記したときの桁は均等に出現すると予想されている（正規数を参照）。これらの数は一見ランダムではあるものの情報量は非常に低いので、コルモゴロフ複雑性の観点からは乱数ではない。こういった数を用いることは 1975 年アメリカ合衆国政府から発表された Data Encryption Standard (DES) に関する初期の論争が動機づけとなった。DES は S ボックスで用いている定数に対する説明がないことで批判を受けていたのである（実際には現在でいうところの差分解読法を防ぐため注意深く選択された定数であったことがのちに判明したが）[3]。こういった事情から、暗号に用いる定数を生成するためのより透明性の高い方法の必要性が感じられていた。
「種も仕掛けもない数」は英語では "nothing-up-my-sleeve number" というが、"nothing up my sleeve" とはマジシャンがマジックを行う前に袖を開いて何も隠していないことを示すときに使うフレーズである。
例
[編集]- ロナルド・リベストは今日広く使われている MD5 ハッシュにおいて正弦関数を定数の生成に用いた[4]。
- アメリカ国家安全保障局 (Nasional Security Agency, NSA) は Secure Hash Algorithm のうち SHA-1 と SHA-2 において、最初の 8 個の素数の平方根を定数の生成に用いた[5]。また SHA-1 はハッシュ計算の初期値として 0x0123456789ABCDEFFEDCBA9876543210F0E1D2C3 を用いている。
- Blowfish 暗号は鍵スケジュールの初期化に円周率の二進表記（最初の 3 は除く）を用いている[2]。
- RFC 3526は internet key exchange に用いられる素数（それ自体も円周率から生成されたもの）について記述している。
- NewDES の S ボックス はアメリカ独立宣言を基に作られた[6]。
- Advanced Encryption Standard の候補だった DFC で用いられているすべての任意定数（S ボックス内のすべてのエントリを含む）はネイピア数の二進表記から作られた[7]。
- ARIA は 1/π の二進表記を鍵スケジュールに用いている[8]。
- RC5 の鍵スケジュールはネイピア数と黄金数の二進表記を鍵スケジュールに用いている[9]。
- Tiny Encryption Algorithm や Red Pike などの複数の暗号が用いている 0x9e3779b9（十進法では 2654435769）は である（ は黄金数）。
- SHA-3 の最終候補だった BLAKE は 16 個の定数を用いており、それらは円周率の二進表記における小数部分の先頭 512 ビットおよび 1024 ビットになっている。
- KASUMI の鍵スケジュールは鍵の変形に 0x123456789ABCDEFFEDCBA9876543210 を用いる。
- Salsa20 ファミリーの暗号は文字列 "expand 32-byte k" を ASCII コードで表現したものをブロックの初期化に用いる。
- Bcrypt は "OrpheanBeholderScryDoubt" を初期化文字列として用いる[10][11]。
異なる例
[編集]- Streebog ハッシュの S ボックスはランダムに生成されたものだと主張されていた。しかし解析の結果、実際にはアルゴリズム的に生成されたものであり、いくつかの「難解な」弱点を有することが判明した[12]。
- DES は NSA により指定された定数を含んでいた。実際にはランダムからは程遠かったことが判明したものの、それらの定数は当時まだ公には知られていなかった差分解読法への耐性を強めていた[3]。
- アメリカ国立標準技術研究所が推奨していた暗号論的擬似乱数生成器 Dual_EC_DRBG において使用が推奨されていた定数は、過去の出力履歴からその先の出力を開発者が予測できるようにするために選択されたものであった可能性があるとして、2007 年に批判を受けた[1]。2013 年 9 月、The New York Times は「元 NSA の請負人であったエドワード・スノーデンによる内部情報リークによると、NSA が開発し NIST standard 2006 (Dual EC DRBG standard) に使用されていた疑似乱数生成機は NSA のためのバックドアを持っていた」と報じた[13]。
- 楕円曲線暗号に用いるため NSA により標準化された楕円曲線 P curve の係数は、特に説明のないランダムなシードから計算されたハッシュ値であった。以下はその表である。
- P-224:
bd713447 99d5c7fc dc45b59f a3b9ab8f 6a948bc5 - P-256:
c49d3608 86e70493 6a6678e1 139d26b7 819f7e90 - P-384:
a335926a a319a27a 1d00896a 6773a482 7acdac73
- P-224:
直接的に関係のある話ではないが、Dual_EC_DRBG のバックドアが暴かれて以降、NIST による P curve の定数[14]に対する疑念は、NSA が秘密鍵を割り出しやすくする[15]ためにそれらの定数を定めたのではないかという懸念[16]につながった[17]。それ以降、多くのプロトコルやプログラムは 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 など数多くのハッシュ関数を採用することができる。
暗号オブジェクトの選定において調節可能なパラメータが十分に多くある場合、組み合わせ爆発によって暗号化手法と一見簡単な数学定数の組み合わせは非常に大きくなる。したがって、機械的な探索によって所望のバックドアを持つオブジェクトを作ることが可能となってしまう[18]。
脚注
[編集]出典
[編集]- ^ a b Bruce Schneier (2007-11-15). “Did NSA Put a Secret Backdoor in New Encryption Standard?”. Wired News.
- ^ a b “Blowfish Paper”. 2011年9月6日時点のオリジナルよりアーカイブ。2010年6月9日閲覧。
- ^ a b Bruce Schneier. Applied Cryptography, second edition, John Wiley and Sons, 1996, p. 247.
- ^ RFC 1321Sec. 3.4
- ^ FIPS 180-2: Secure Hash Standard (SHS) Archived 2012-03-12 at the Wayback Machine. (PDF, 236 kB) – Current version of the Secure Hash Standard (SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512), 1 August 2002, amended 25 February 2004
- ^ “Revision of NEWDES, Robert Scott, 1996”. 2012年11月8日時点のオリジナルよりアーカイブ。2010年6月9日閲覧。
- ^ “Decorrelated Fast Cipher: an AES candidate” (PDF/PostScript) (May 19, 1998). April 9, 2008時点のオリジナルよりアーカイブ。June 9, 2010閲覧。
- ^ A. Biryukov; C. De Cannière; J. Lano; B. Preneel; S. B. Örs (7 January 2004). Security and Performance Analysis of ARIA (PostScript) (Report). Version 1.2—Final Report. Katholieke Universiteit Leuven. 2011年7月16日時点のオリジナルよりアーカイブ。2010年6月9日閲覧。
- ^ Rivest, R. L. (1994). "The RC5 Encryption Algorithm" (PDF). Proceedings of the Second International Workshop on Fast Software Encryption (FSE) 1994e. pp. 86–96.
- ^ “src/lib/libc/crypt/bcrypt.c - diff - 1.3”. cvsweb.openbsd.org. 2022年7月5日時点のオリジナルよりアーカイブ。2022年7月5日閲覧。
- ^ “hash - Why is the BCrypt text "OrpheanBeholderScryDoubt"” (英語). Information Security Stack Exchange. 2023年7月10日時点のオリジナルよりアーカイブ。2022年7月5日閲覧。
- ^ Biryukov, Alex; Perrin, Léo; Udovenko, Aleksei (2016). “Reverse-Engineering the S-box of Streebog, Kuznyechik and STRIBOBr1 (Full Version)”. Iacr-Eurocrypt-2016. doi:10.1007/978-3-662-49890-3_15. オリジナルの2023-08-02時点におけるアーカイブ。 2019年3月26日閲覧。.
- ^ Perlroth, Nicole (September 10, 2013). “Government Announces Steps to Restore Confidence on Encryption Standards”. The New York Times. オリジナルのApril 23, 2015時点におけるアーカイブ。 September 11, 2013閲覧。
- ^ “SafeCurves: Introduction”. 2017年9月5日時点のオリジナルよりアーカイブ。2017年5月2日閲覧。
- ^ “SafeCurves: Rigidity”. safecurves.cr.yp.to. 2015年5月22日時点のオリジナルよりアーカイブ。2015年5月20日閲覧。
- ^ Maxwell, Gregory (September 8, 2013). “[tor-talk NIST approved crypto in Tor?]”. 2014年10月2日時点のオリジナルよりアーカイブ。2015年5月20日閲覧。
- ^ “The NSA Is Breaking Most Encryption on the Internet - Schneier on Security”. www.schneier.com. 2017年12月15日時点のオリジナルよりアーカイブ。2015年5月20日閲覧。
- ^ How to manipulate curve standards: a white paper for the black hat Archived 2016-03-08 at the Wayback Machine. Daniel J. Bernstein, Tung Chou, Chitchanok Chuengsatiansup, Andreas Hu ̈lsing, Eran Lambooij, Tanja Lange, Ruben Niederhagen, and Christine van Vredendaal, September 27, 2015, accessed June 4, 2016
訳注
[編集]- ^ 暗号には大きく分けて「コード」(code) と「サイファ」(cipher) の 2 種類があるが、前者は単語や文を別の単語や記号に置き換える方法を指し、後者は文字レベルでの置換や転置を行う方法を指す。
参照
[編集]- Bruce Schneier. Applied Cryptography, second edition. John Wiley and Sons, 1996.
- Eli Biham, Adi Shamir, (1990). Differential Cryptanalysis of DES-like Cryptosystems. Advances in Cryptology – CRYPTO '90. Springer-Verlag. 2–21.