暗号理論 における種も仕掛けもない数 (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" とはマジシャン がマジックを行う前に袖を開いて何も隠していないことを示すときに使うフレーズである。
例
異なる例
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
直接的に関係のある話ではないが、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 . https://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115 .
^ 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 1321 Sec. 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時点におけるアーカイブ。. https://web.archive.org/web/20230802045902/https://eprint.iacr.org/2016/071 2019年3月26日 閲覧。 .
^ Perlroth, Nicole (September 10, 2013). “Government Announces Steps to Restore Confidence on Encryption Standards” . The New York Times . オリジナル のApril 23, 2015時点におけるアーカイブ。. https://web.archive.org/web/20150423131626/http://bits.blogs.nytimes.com/2013/09/10/government-announces-steps-to-restore-confidence-on-encryption-standards/?src=twrhp&_r=1& 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.