2002年のLotus NotesにおけるNSAバックドア鍵

 (cypherspace.org)
2 ポイント 投稿者 GN⁺ 2023-09-19 | 1件のコメント | WhatsAppで共有
  • 米国の暗号輸出規制が廃止される前、Lotus Notesの輸出版には differential cryptography と呼ばれるキーエスクロー／バックドア構造が含まれていた
  • この方式では64ビット暗号化のうち 24ビット をNSA公開鍵で暗号化することで輸出許可を取得しており、NSAは残りの40ビットだけを総当たりすれば平文にアクセスできた
  • リバースエンジニアリングの過程で、アプリケーション内部のNSA公開鍵識別子が O=MiniTruth CN=Big Brother として現れ、意図的なオーウェル的命名が明らかになった
  • 公開鍵データは数年後にメモから再構成されたものであるため、誤りの可能性 があり、モジュラスは little endian に見え、big endian 表現では e = 3、760ビットだった
  • PGP鍵形式の Director, NSA <dirnsa@nsa.gov> ユーザーIDは任意に作成されたもので、自己署名(self-signed) 鍵ではない

Lotus Notes輸出版のバックドア構造

  • 米国の暗号輸出規制が廃止される前、Lotus Notesの輸出版には キーエスクロー／バックドア 機能である differential cryptography が組み込まれていた
  • 中核となるアイデアは、64ビット暗号のうち 24ビット をNSA公開鍵で暗号化して輸出許可を得る構造だった
    • NSAは残る 40ビット だけを総当たりすれば平文を得られた
    • 一般ユーザーは64ビットの鍵空間を相手にしなければならなかったが、当時でもNSAがより高いコストをかけて総当たりする可能性は残っていた
  • アプリケーション内部のどこかにNSA秘密鍵に対応する NSA公開鍵 があるはずだという判断から、リバースエンジニアリングが行われた

発見された鍵識別子と公開鍵データ

  • デバッガでは、NSA公開鍵の組織名とコモンネームが次のように表示された
    • O=MiniTruth CN=Big Brother
  • MiniTruth と Big Brother は、George Orwellの小説 1984 に登場する表現と結び付く
    • Ministry of Truthは作中で宣伝と真実の抑圧を担う機関である
    • Big Brotherはその政府の邪悪な指導者として登場する
  • 公開鍵データはリバースエンジニアリングから数年後にメモをもとに整理されたものであり、誤りの可能性 がある
  • raw public key のモジュラスはデバッガから得た値で、trial and error の結果 little endian 形式だと判断された
    • big endian 表現では e = 3
    • モジュラスは 760ビット
  • 公開鍵はPGP鍵形式でも提示されている
    • pub 760/13629D8D 1998/10/25 Director, NSA <dirnsa@nsa.gov>
    • このユーザーIDは任意に作られたもので、自己署名鍵ではない
  • pgpacket の出力ではRSA公開鍵パケットであることが確認できる
    • Version Byte: 3
    • Key Created: 25 Oct 1998 01:12:02
    • Algorithm: 1 (RSA)
    • Key ID: 0xA703EFD313629D8D

関連記事

1件のコメント

 
GN⁺ 2023-09-19
Hacker News のコメント

  • この話題については、2013年の HN 議論に付いた Ray Ozzie（Lotus Notes の作者）のコメントを読む価値がある
    https://news.ycombinator.com/item?id=5846189
    ソフトウェアがリリースされる前に、Ray Ozzie と Kauffman は RSA Conference で自分たちが何をしているのかを公に説明していた。秘密のバックドアではなく、業界全体が対応しなければならなかった輸出規制への準拠だった。少し下にある barrkel のコメントも読む価値がある

    • おおむね37歳未満の人たちには、2000年以前の暗号技術、とりわけリリースされる商用製品内の暗号技術は、今とはかなり違う政府規制の下にあったことを思い出してほしい
      https://en.m.wikipedia.org/wiki/Crypto_Wars
      簡単に言うと、米国政府は国際配布される製品に強力な暗号を入れてリリースすることを事実上禁止していた。商用製品はおおむねすべて対象で、PGP のような強力な暗号のオープンソース実装がすでに存在していたにもかかわらずそうだった。今では望むだけ安全な暗号を入れて配布しても誰も気にしないが、当時は米国政府の法的手段が総動員されるかどうか五分五分という時代だった。本当に狂ったように矛盾した時代だった
    • 元 Microsoft 開発者が NSAkey をうまく分析している動画がある
      https://www.youtube.com/watch?v=vjkBAl84PJs
    • 興味深い時代だった。名前は忘れたが、ZIP の crc32 と暗号化アルゴリズムを実装した人と少し話したことがあり、彼はほとんど申し訳なさそうに、その暗号化は当時の法律に従って輸出可能になるよう設計されたものだと言っていた
      それでも破るのが完全に些細というわけではないが、現代の Office 文書でパスワードを1つ試す時間で、ZIP アーカイブのエントリには数百万個のパスワードを試せる
    • 秘密だったかどうかにかかわらず、悪用可能で、実際に悪用されたバックドアだった。今日の政府が技術企業に「秘密のバックドア」を要求しながら、その途方もないリスクを見ていないのは、実に奇妙な時代だ
    • これはまったく秘密ではなかった。90年代半ばに Lotus で働いていたが、Lotus Notes には米国向けと「International」というラベルの付いた版の2種類があった

  • (2002)
    タイトルに Lotus Notes が入っている過去の議論:
    4年前
    https://news.ycombinator.com/item?id=21859581
    8年前
    https://news.ycombinator.com/item?id=9291404
    10年前
    https://news.ycombinator.com/item?id=5846189

  • 懐かしき良き NOBUS。NSA のもっと面白い失敗例:
    https://en.wikipedia.org/wiki/Clipper_chip
    https://en.wikipedia.org/wiki/Dual_EC_DRBG

    • これと Clipper Chip は NOBUS ではない。NSA は、暗号システムに法執行機関アクセス機能があることを人々に知られたくない
      FBI は人々に知られてもあまり気にしない。彼らが狙う犯罪者は作戦保全（OPSEC）をきちんとしていないからだ

  • NSA の人たちには、これが Big Brother 的な行動だと認識できる程度の自己省察はあったのに、なぜそれが悪いのかは理解できなかったという点が驚きだ

    • それはおそらく、それを埋め込んだ Lotus エンジニアの皮肉だったのだと思う
    • 「Big Brother」自体は衝撃的ではない。しばらく前から知られていた内容なので、それでも少なくとも善意かもしれないと、ごくわずかには信じられる。悪い人々から私たちを守る、というように
      だが MiniTruth は……うわ、本当に驚きだ
      文脈上、『1984年』の小説における Ministry of Truth はプロパガンダ専門の機関で、社会全体がそのプロパガンダに浸っている。彼らの住む社会のすべてが嘘なのだ。これは、彼らに善意があり得るという最後の希望まで吹き飛ばす。彼らが仕えていると主張する人々をどれほど冷笑的に軽蔑しているか、そしてどれほど不注意かを示す例として最後に思い出すのは、FTX の内部チャットルーム名が「Wirefraud」だったことが明らかになった時だ

  • そもそもバックドアは、NSA が暗号技術を使おうとする企業に提供したコード例の中にあったのではなかったか？ サンプルのシードのようなものを渡し、ほとんどの企業が自前で素数を生成せずにそれをコピー＆ペーストしたため、NSA が非常に簡単に破れるようになった、というふうに記憶している
    記憶があいまいで、元の出典を見つけにくい

  • 1998年時点の RSA 760ビット公開鍵から秘密鍵を総当たりで見つけるのが、どれほど難しいのか気になる。分かる人いる？

    • https://en.wikipedia.org/wiki/Integer_factorization_records と https://en.wikipedia.org/wiki/RSA_numbers が手がかりになる。特に後者では、768ビット鍵は「2009年12月12日、2年をかけて」素因数分解され、CPU時間は「シングルコアの2.2GHz AMD Opteronベースのコンピュータでほぼ2000年計算したのとおおよそ同等だった」と説明している
      その後2019年には795ビット鍵が素因数分解され、CPU時間は「2.1GHz Intel Xeon Gold 6130 CPU換算で約900コア年」だったという。RSA-768の素因数分解と比べて、著者らは、より優れたアルゴリズムで計算が3〜4倍、より高速なコンピュータで1.25〜1.67倍高速化したと推定している
      したがって、改良されたアルゴリズムがより小さい数にも適用できるとすれば、それを扱える人なら、現代的なマシン数十台で数か月以内に可能そうだ。大きな数の素因数分解は、CADO-NFSを実行して数値とクラスタを指定するだけよりは、ずっと難しそうではある
      例えば、2本目の素因数分解論文に付随する「795ビットの計算は768ビットの計算より2.25倍難しいはずだ」という値を使うと、より小さい鍵を現代のソフトウェアで破るには、Xeon基準のCPUで900/2.25 = 400コア年が必要だと見なせる。このCPUも今では6年前のモデルだ。同等性能の64コアサーバー24台なら、3か月を少し超える程度で済むだろう。趣味で面白半分にやるには重いが、相応の金銭的利害がある会社なら、この作業を理解して再現できる人材がいるという前提で、十分に可能だ
    • 誰かが2018年にすでに素因数分解を試みている: http://factordb.com/index.php?query=444376527415060195687748...
    • いつも、手元にあるリソース、つまり計算資源と時間次第。可能ではあるが簡単ではない
      https://crypto.stackexchange.com/a/1982
    • 妙に具体的な質問だね。何か特に気になっていることでもある？

  • 今はクラウドがあるので、こういうものは全部不要になった。保存データに関する法律のせいで、6か月を過ぎたすべてのメールは好きに触れる対象になる

    • 調べてみたが、Googleのような会社が令状やNSLなしに政府機関へ保存データへのアクセスを提供しなければならない法律が何なのか、はっきりした結果は見つからなかった

  • 関連: https://github.com/goshacmd/nsa_panel