セキュリティ研究者は暗号アルゴリズムの実装上の問題の発見に定期的に取り組んでいるが、数学的なバックドアの探索には十分な努力が払われていないと、2人の暗号学教授が主張している。
政府や諜報機関は、データや通信の暗号保護を制御し、回避しようと努めています。暗号アルゴリズムにバックドアを仕掛けることは、暗号制御を強化する最良の方法と考えられています。
暗号学を擁護する研究者たちは、安全な情報交換と電子商取引を支える技術の検証に着手した。運用暗号学・ウイルス学研究所(ESIEA)の研究責任者であるエリック・フィリオル氏は、一般的に実装上のバックドア(プロトコル/実装/管理レベル)のみが考慮されていると主張した。数学的なバックドアや設計上のバックドアの発見には十分な努力が払われていないと彼は主張する。
先週のBlack Hat Europeでの「暗号化システムの設計上のバックドア - 外部の暗号化アルゴリズムは信頼できるか?」と題したプレゼンテーションで、Filiol氏と同僚のArnaud Bannier氏は、数学的なバックドアを設計できる仕組みについて説明した。
RSA:NSAの暗号アルゴリズムを製品に組み込んでいる?使用をやめろ
続きを読む
プレゼンテーションで、2人の研究者はBEA-1を紹介した。これはAESに類似したブロック暗号アルゴリズムで、実用的かつ効果的な暗号解読を可能にする数学的なバックドアを備えている。「我々のバックドアの存在を知らなくても、BEA-1はNISTとNSAが暗号の検証に公式に考慮するすべての統計テストと暗号解析に合格しています」と、フランスの暗号専門家たちは説明する。「特に、BEA-1アルゴリズム(ブロックサイズ80ビット、鍵120ビット、ラウンド数11)は、線形暗号解読と差分暗号解読に耐えられるように設計されています。我々のアルゴリズムは2017年2月に公開されましたが、バックドアが容易に検出可能であることを証明した者も、その悪用方法を示した者もいません。」
彼らがそれをどうやってやったか
ブラックハットでの講演で、フィリオル氏とバニエ氏は、意図的に仕掛けたバックドアの詳細と、それを悪用してわずか600KBのデータ(平文300KBと対応する暗号文300KB)で120ビットの鍵を約10秒で復元する方法を明かした。これは概念実証であり、より複雑なバックドアが構築される可能性もあると彼らは付け加えた。
「アルゴリズムにバックドアを挿入すること(私たちが行ったことは、少なくとも計算の観点からは実現可能かつ容易であるはずだった)と、その存在を証明し、バックドアを検出して抽出できることの間には、(数学的観点から)強い非対称性があります」とフィリオル氏はエル・レグ紙に語った。「ある意味で、私たちは何らかの概念的な一方向関数を作成する必要があるのです。」
この研究者は長年にわたり、暗号アルゴリズムにおける数学的なバックドアというテーマを研究してきました。彼の過去の研究には、今年初めに発表されたブロック暗号化アルゴリズムの潜在的な問題を調査した論文が含まれています。
なぜ、これらの界隈でも数学はクールではないのか
「数学的なバックドアの研究は(数学的な意味で)はるかに難しく、流行のテーマについて迅速かつ定期的に論文を発表する必要がある研究者の関心を惹きつけません」とフィリオル氏は付け加えた。「だからこそ、この種の研究は基本的に諜報機関(GCHQ、NSAなど)の研究開発ラボで行われており、バックドアの検出よりも設計に重点を置いているのです。」
元NSAシステム管理者のエドワード・スノーデン氏がリークした文書によると、NSAはRSAセキュリティに1,000万ドルを支払って、脆弱なDual_EC_DRBG技術を暗号ツールセットにデフォルトで採用させていたことが明らかになった。これは、数学的あるいは設計上のバックドアに関する懸念が理論上のものではないことを示している。フィリオル氏によると、Dual_EC_DRBGの例は特異なものではないという。
「例はたくさんあるが、知られているのはほんのわずかだ」とフィリオル氏は述べた。「まさにこれが、私のスライド[PDF]の『歴史』の部分の目的だった」
輸出用暗号化システムには、何らかの形でバックドアが仕込まれていると確信しています。これはワッセナー合意の直接的な制約です。この点で、Crypto AG社やその他の企業(ハンス・ビューラー事件で明らかになった)は最たる例です。他にもあまり知られていない[例]があります。
「この文脈とさまざまな文書を分析すると、Dual_EC_DRBGの標準化プロセスはまさに既知ではあるが確実なケースです」と彼は付け加えた。
数学的なバックドアはいくつあるのでしょうか?
Filiol 氏は、実装バックドア (プロトコル/実装/管理レベル) と数学的バックドアの普及と重要性の組み合わせを把握したり、ある程度把握したりすることは難しいと認めました。
「これは答えるのが難しい質問です。バックドアが存在する可能性があることを証明するのは、数学的に解決困難な問題だからです」とフィリオル氏は答えた。「国際規制を分析すれば、少なくとも輸出版にはバックドアが含まれていることは明らかです。」
「さらに懸念されるのは、人口レベルや大規模な監視という文脈において、国内での使用にも[これが]当てはまるのではないかと懸念しなければならないことだ。」
査読プロセスによって数学的な裏口が排除されたかどうかを問われ、フィリオル氏は改革の必要性を主張した。
「(安全性の証明を)擁護することは、(安全性の不確実性を証明すること)攻撃することよりもはるかに難しい」とフィリオル氏は述べた。「そして大きな問題は、(安全性に関する)学術的な無知が、結果として、安全性の不確実性の証明がないことを安全性の証明とみなしてしまうことにある」
NSAの数学者と否定の証明
「攻撃者があらゆる攻撃手法を公開するわけではない世界(特に諜報機関の活動が依然として活発な暗号技術の世界)に私たちはいます。そのため、専門家や学者は既知の攻撃手法を参考資料として扱うことしかできません。NSA(約40年にわたり活躍した最も優秀な数学者300名)が何を生み出したか想像してみてください。数学的知識の集積です。」
Filiol 氏は、反証となる証拠を手元に持っていないにもかかわらず、業界標準で広く検討されている AES アルゴリズムが必ずしも安全であるとは考えていません。
「AESにバックドアがあることを証明できないなら、バックドアがないことを証明できる人は誰もいない」とフィリオル氏はエル・レグ紙に語った。「正直なところ、アメリカがいかなる制御もなしに、極めて安全な軍事レベルの暗号化アルゴリズムを提供するなどと考えるほど、頭がおかしい人がいるだろうか?」
彼はさらにこう付け加えた。「私はそうは思いません。AESコンテストはNISTがNSAの技術支援を受けて主催したものです(これは周知の事実です)。テロの脅威が増大する時代に、アメリカが通常兵器によるいわゆる『対抗手段』を講じなかったとは、本当に愚かな行為だったと言えるでしょうか? 真剣な国(アメリカ、イギリス、ドイツ、フランス)は、高度なセキュリティを必要とする際に外国のアルゴリズムを使うことはありません。彼らは(アルゴリズムから実装に至るまで)国産の製品と標準規格を義務的に使用しなければなりません」と彼は付け加えた。
フィリオル氏は、暗号アルゴリズムの選択、分析、標準化の方法に改革が必要だと結論付けた。「これは、オープン暗号コミュニティが主導する、完全にオープンなプロセスであるべきだ」と彼は主張する。®