512ビットDKIMキーを8ドル未満のクラウド費用でクラックした方法
(dmarcchecker.app)- 上位100万Webサイトの調査で、1,024ビット未満のDKIM公開鍵が1,700件以上見つかり、この実験では redfin.com の 512ビットRSA DKIMキーが実際に悪用可能かを確認した
- DKIMレコードの
pタグをデコードして RSA モジュラスnと公開指数e=65537を取得し、その後 CADO-NFS でモジュラスを素因数分解した - Hetzner の 8 dedicated vCPU、32GB RAM サーバーで約86時間かけて
nを2つの素数p、qに分解し、これを基に RSA 秘密鍵を再構成した - 再構成した秘密鍵で
security@redfin.com発信メールに署名すると、Gmail・Outlook などは拒否したが、Yahoo Mail、Mailfence、Tuta はdkim=passを返した - redfin.com の
p=reject; pct=100DMARC ポリシーでは DKIM 通過が DMARC 通過につながるため、メールプロバイダーは 1,024ビット未満のRSA DKIM署名 を拒否すべきだ
512ビットDKIMキーが残っている問題
- 上位100万Webサイトの SPF、DKIM、DMARC レコード調査 で、長さが 1,024ビット未満 の公開DKIMキーが1,700件以上見つかった
- 1,024ビット未満のRSAキーは安全ではないと見なされており、DKIMでは2018年の RFC 8301 以降、廃止推奨の状態にある
- 実験対象は
key1._domainkey.redfin.comで見つかった 512ビットRSA公開鍵 だった - 目的は、公開鍵だけから秘密鍵を復元し、本来のドメイン送信者であるかのようにメールへ署名できるかを確認することだった
- Gmail、Outlook.com、Yahoo Mail のような主要メールプロバイダーが、短いキーで作られたDKIM署名を通してしまうかも併せて検証した
DKIM公開鍵からRSA構成要素を抽出
- DKIMレコードの
pタグには、公開鍵が ASN.1 DER形式 でエンコードされた後、さらに Base64 でエンコードされて格納されている - Python の
Crypto.PublicKey.RSA.import_keyで公開鍵を読み込み、RSA構成要素を抽出した- モジュラス
n:10709580243955269690347257968368575486652256021267387585731784527165077094358215924099792804326677548390607229176966588251215467367272433485332943072098119 - 公開指数
e:65537
- モジュラス
CADO-NFSでモジュラスを素因数分解
- RSA秘密鍵を作るには、モジュラス
nを2つの素数pとqの積に分解する必要がある - 素因数分解には CADO-NFS を使用した
- CADO-NFS は大きな整数の素因数分解に使われる Number Field Sieve(NFS) アルゴリズムの実装だ
- ローカルコンピューターを数日間占有しないよう、Hetzner のクラウドサーバーを借りた
- サーバースペックは 8 dedicated vCPU、AMD EPYC 7003 シリーズ、32GB RAM
- OS は Ubuntu
- 作業に十分なメモリを確保するため、32GB の swap を追加した
cado-nfs.pyにモジュラスnを入力して素因数分解を実行した- 全作業には 8-vCPU サーバーで約 86時間 かかり、
nは次の2つの素数に分解されたp = 97850895333751392558280999318309697780438485965134147739065017624372104720767q = 109447953515671602102748820944693252789237215829169932130613751100276125683257
- より強力なサーバーや複数システムでの分散実行を使えば時間を短縮でき、CADO-NFS は分散作業を簡単にする
RSA秘密鍵の再構成
p、q、eを確保した後、Python と PyCryptodome で RSA 秘密鍵を構成した- 計算には次の値と手順を使った
n = p * qphi = (p-1) * (q-1)d = inverse(e, phi)RSA.construct((n, e, d, p, q))
- 結果は PEM 形式の RSA 秘密鍵で、OpenDKIM の設定に統合してテストメール署名に使用した
メールプロバイダー別のDKIM検証結果
- 再構成した秘密鍵を OpenDKIM に入れ、
security@redfin.comの FROM アドレスでテストメールを複数のメールホスティングサービスに送信した - ほとんどのプロバイダーは 512ビットキーを安全でないと判断してDKIM署名を拒否したが、3社は
dkim=passを返した - プロバイダー別の結果は次のとおり
- Gmail: FAIL
- Outlook: FAIL
- Yahoo Mail: PASS
- Zoho: FAIL
- Fastmail: FAIL
- Proton Mail: FAIL
- Mailfence: PASS
- Tuta: PASS
- GMX: FAIL
- OnMail: FAIL
- redfin.com は
v=DMARC1;p=reject;pct=100;...形式の有効な DMARC レコード を持っている - redfin.com に対する DKIM 検証通過は DMARC 検証通過にもつながり、BIMI の要件も満たした
コストと運用上の対策
- 30年前には 512ビットRSA公開鍵を破ることはスーパーコンピューター級の作業だったが、現在ではクラウドサーバーで 8米ドル未満 で可能だ
- 16コア以上を備えた強力な家庭用コンピューターがあれば、さらに速く安価に実行できる可能性もある
- 512ビットや768ビットのDKIMキーを維持する理由はなく、メールプロバイダーは 1,024ビット未満のRSAキー で生成されたDKIM署名を自動的に拒否すべきだ
- Yahoo、Mailfence、Tuta には実験結果と勧告が伝えられた
- ドメイン所有者は DNS 設定内の古いDKIMレコードを点検すべきだ
- DKIMレコードの
pタグは Base64 の文字数を数えるだけで簡単に確認できる - 1,024ビットRSA公開鍵は Base64 ベースで最低 216文字 を持つ
- DKIMレコードの
1件のコメント
Hacker News の意見
14年前にも 512ビット DKIM RSA 鍵は破ることが可能だった: https://blog.jgc.org/2010/06/facebooks-dkim-rsa-key-should-b...
短い鍵なら DKIM 署名が長く証拠として残らず、後からどのメールが本物だったかを証明しにくくする 否認可能性を保てる、という理屈だった。
もちろん、ほとんどの企業が短い鍵を使っていた理由がそれだったという意味ではなく、短い鍵が完全に悪いだけではないという空気があったという意味。
DKIM の否認可能性は個人的に長く追っているテーマだが [1]、このような短い鍵は明らかに解決策ではない。ただ、DKIM をめぐる混乱した考え方と、すべてのメール署名方式が持つ含意を受け入れたがらなかったコミュニティの雰囲気の結果だと見ている。
[1] https://blog.cryptographyengineering.com/2020/11/16/ok-googl...
https://www.wired.com/2012/10/dkim-vulnerability-widespread/
ざっくり言えば、14年ほどの間に数週間から 8時間に短縮されたことになる。
面白半分で試したいなら、4096ビット DKIM 鍵を作ってみるとよい。
オンラインの DKIM/SPF チェッカーは DNS だけを見ると全部正常だと言うが、テストメールは失敗する。
だいたい
STATUS: Fail,DKIM: Pass,SPF: Passのような素晴らしい説明を表示してくれる。DKIM レコードに 2048ビットより大きい鍵を使うことは許可されており有効だが、検証器が 2048ビットより大きい鍵を必ず処理しなければならないわけではなかった。
これを身をもって学ぶのに、少し髪の毛を失った。
興味深いことに、サイト側は3項目すべてが正しく有効だと言うのに、メールは失敗扱いになる。
おそらく DNS レコード検査とメール検証を別々のソフトウェアが処理しているためだと思われる。
検証器は 512ビットから 2048ビットまでの鍵による署名を検証できなければならず、より大きな鍵も検証できる、とされている。
1年前にこのテーマで修士論文を書いたが、最近の主要メールプロバイダーはすべて 4096ビットをサポートしており、一部は 16384ビットまでサポートしていた。
なぜすべての暗号で全般的に 鍵サイズを大きく増やさないのか不思議に思う。
解決策ではないとしても、時間を稼ぐ手段にはなりそうだ。
計算性能は急速に伸び、量子コンピュータの話も出続けているのに、皆じっとしているように感じる。
もちろん大きな鍵は計算コストが増えるが、こちらの計算資源も増えているのだから、攻撃側だけに使わず防御にも使うべきではないかと思う。
クライアント側で TLS 1.2 ではなく TLS 1.3 を強制するという簡単なことでも壊れるものが多く、HN サイトも含まれる。
これらの数字はデバイス技術の水準ではなく、熱力学が許す最大値に関係している。
結論として、AES-256 や RSA-4096 を総当たりで破ることは物理的に不可能。
1024ビット鍵は複数の暗号システム全般で10年以上前から退場させられている。
一つの遅れている例外を除けばそうで、2048ビット鍵を脅かすのは量子コンピュータだけだが、それは RSA 自体を脅かす。
進歩は線形ではないので、1024 が弱くなったからといって 2048 も機械的にすぐ崩れる構造ではなく、1024 でさえ今日の実戦攻撃は容易ではない。
DKIM は例外の一つ。
DKIM では Ed25519 が広く採用されるのを待っており、そうなればさまざまな不便が解消されるはず。
たいていその痛みはサービス運営者ではなくユーザーに直接転嫁され、ユーザーが大きく不満を言って運営者が気にすることを期待する構図になる。
しかしユーザーは、セキュリティのような小さなことが売上を妨げないようにしてくれる競合へ移る可能性も高い。
実質的には「なぜ私たちはすでにやっていることをやらないのか」と聞いているようなもの。
CADO-NFS を使えば意外と簡単にできる。
数週間前、仕事の都合でデスクトップコンピュータで 512ビット RSA DKIM 鍵を因数分解したが、28時間しかかからなかった。
具体的には AMD Zen 5 9900X だった。
残念ながら 1024ビット鍵はまだ趣味レベルの努力では難しいが、2010年に 768ビット鍵を因数分解した規模の学術プロジェクトなら可能かもしれない: https://eprint.iacr.org/2010/006.pdf
昨日、Bank of America からアカウント設定の問題に関するメールを受け取った
新しいアカウントを作ったのは事実で、メールもその事実や会社名などを把握していた
リンクはなく、BofA のビジネス向け番号に電話するよう案内があるだけで、BofA の Web サイトで番号を確認したところ同じだったので電話した
ところが、なぜそのメールを受け取ったのか、アカウントに何の問題があるのか、誰も教えてくれず、担当者はこのメールの送信記録も見つけられなかった
このメールが Bank of America から来たことは 100% 確信している
フィッシング要素もなく、リンクも悪意ある電話番号もなかった
SPF、DKIM、DMARC はすべて Google の ARC-Authentication-Results でパスしており、DKIM キーも 2048 ビットだった
Bank of America に調査を依頼したところ、「フィッシングメッセージだったはず」として、フィッシングに注意する方法へのリンクを送ってきた
おそらく、アカウント作成中に何らかのシステムが整合性チェックを早すぎるタイミングで実行し、メールを生成してしまった単純なミスだった可能性が高い
しかし彼らが「フィッシング」だと言ったので、資料一式を添えて CTO 宛てに FedEx で送った
どちらかだ。DKIM キーが漏えいしたので直ちに公の警告を出すべきなのか、無能な従業員と IT システムが私をたらい回しにして 1 時間を無駄にさせたのか
いずれにせよ、徹底した調査と解決を求めている
一部の DNS プロバイダーはひどく、1024 ビット長のキーまでしか設定できない
たとえば wordpress.com がそう
参考までに、最後に破られた RSA 数は RSA-250、つまり 829 ビットで、2020 年に 2700 コア年を要した [1]
一方 RSA-155、つまり 512 ビットはすでに 1999 年に素因数分解されている
危険な状態ではない
[1]: https://sympa.inria.fr/sympa/arc/cado-nfs/2020-02/msg00001.h...
十分なセキュリティ水準を提供できないという理由から
NSA まで防げる水準ではないが、DKIM が複数の防御層のうちの一つであることを考えれば、スパマーを防ぐには十分に見える
TXT レコードのサイズに制限があるのか、それとも DKIM らしく見える TXT レコードをわざわざパースしようとして失敗し、追加を拒否しているのか気になる
良いデモのために 512 ビットキーを破ることは、すでに行われているとしても非常に価値あるセキュリティ研究だ
「まだ 512 ビットを使っているところの一覧がここにあるので移行すべきだ」と公開することも正当化できる
だが、実運用中の現実世界のキーを直接破るのは、個人的には倫理的な一線を越えているように感じて居心地が悪い
弁護士ではないが、犯罪である可能性もあるように見えるし、少し不要に思える
原文で
now no longer availableを探せばよい通常、オンラインシステムが脆弱であることを示すときは、善意で脆弱性を再現し、研究を文書化したうえでレビューを依頼する
暗号体系を破る場合でも、ロックされたゲーム機で任意コード実行を得る場合でも、投票機のデータを改ざんできることを証明する場合でも、Google Meet の Q&A コメントを編集できることを示す場合でも、プロセスは同じ
脆弱だと言うだけなら無視できるが、脆弱だと言って証明すれば無視しにくくなる
そこに業界標準の公開期限を設け、60 日ほど連絡を試みた後に脆弱性を公開すると伝えれば、無視する余地は事実上なくなる
それは単なる数学だ
その数学に依拠して詐欺や特定の管轄区域の法違反に当たるメールを送ることが違法なのだ
核心は数学ではなく、行動と意図である
誰かが愚かなことをしていると指摘することも違法ではないが、彼らがあなたの人生を面倒にしようとすることはあり得る
「バグが悪用可能であることを示すのはよいが、概念実証コードを書くのは一線を越えている」という具合だ
問題は、実際に可能であることを示さなければ、大半のセキュリティ研究は聞いてもらえないことだ
その代わり、DKIM RFC に正しく従っていなかった主要メールプロバイダー 10 社のうち 3 社、つまり Yahoo、Tuta、Mailfence は通知後に公開した
これが Hover で DNS 管理をやめざるを得なかった理由
255 文字より長い TXT レコードをサポートしておらず、Hover で分割レコードが動作したという事例も見つけられなかった
結局 Digital Ocean を使うことになった
こうした問題がさらに 10 年続くなら、楕円曲線暗号が標準になってほしい
「ほとんどのプロバイダーは 512 ビットキーを安全でないと正しく識別して DKIM 署名を拒否したが、3 つの主要プロバイダー — Yahoo Mail、Mailfence、Tuta — は dkim=pass を報告した」という部分について、Google は本当に DKIM 署名が安全でないために失敗したのか、それとも SPF 失敗のために失敗したのかが気になる
dkim=policy (weak key)の結果で失敗した「検証器は 1024 ビット未満の RSA キーを使用する署名を有効な署名と見なしてはならない」という要件そのものだ
512ビットという数値が大きいか小さいかは、共通鍵暗号か公開鍵暗号かによって異なる
公開鍵暗号は常に共通鍵暗号より8倍弱いと考えればよい
DKIMは公開鍵方式なので、512ビットDKIMは共通鍵ハッシュ基準では64ビットに相当し、すでにかなり以前に破られているレベル
160ビットのSHA-1でさえ破られたものと見なされている
512ビットSHA-3と同程度の強度のDKIMにするなら少なくとも4096ビットが必要で、それでもSHA-3のリプレイ攻撃緩和手法まで含むわけではない
メールヘッダーに署名を入れて検証する標準である
残念ながらDKIMは
rsa-sha1とrsa-sha256署名しかサポートしていない: https://datatracker.ietf.org/doc/html/rfc6376/#section-3.3DKIMが改訂され、Ed25519や類似の署名を許可するようになるとよい
たとえば224ビットECCは、おおよそ2048ビットRSAと同程度
どちらも公開鍵方式である
逆に、公開鍵方式の楕円曲線は共通鍵暗号であるAESと同程度の強度を持つ
もちろん量子コンピューターには脆弱である