🏢 👙 👆🏿 2 ^ 64操作でのテレグラム攻撃、およびスーパーヴィランがそれを必要としない理由 🔋 👨🏻‍⚖️ 🏖️

昨春、Juliano Rizzo（ @julianor ）と私はTelegramからの「秘密」のMTProtoチャットに対する暗号攻撃を思いつきました。これは約2 ^ 64の操作で実行できます。攻撃は、Telegramサーバーの中央にいる男性の位置から実行されます。

シークレットチャットの外部のユーザーに送信されたメッセージは、企業がメッセージの内容を表示して第三者に転送できるように、Telegramサーバーに保存されます。これは、会話がデバイス間（たとえば、電話とコンピューター間）で移動できる場合に常に発生します。これらのチャットは非公開ではありません。つまり、ユーザーは、秘密のチャットを含めずに誤って犯罪情報や写真を送信しないように非常に注意する必要があります。グループチャットでは、エンドツーエンドの暗号化もまったく使用しません。さらに、誰かがそのようなチャットに入ると、以前に送信された未分類のメッセージにすぐにアクセスできます。これについては少し後で説明します。

秘密のチャット

Telegramのスローガンには、「プライバシーの権利を取り戻す」という意味があり、エンドツーエンドの暗号化を使用した秘密のチャットを意味します。この部分は、サーバーによって発行されたXORキーを使用した最初のTelegram侵害競争中に簡単にハッキングされました。

本質的に、テレグラムのエンドツーエンド暗号化は、キーを選択し、修正されたAESスキームを使用して暗号化するためのDiffie-Hellmanプロトコルです。エンドツーエンドの暗号化の信頼性は、共有秘密キーの切り捨てられたSHA-1ハッシュに基づいており、これは指紋としてグラフィカルに表示されます。この印刷物は、何らかの形で視覚的に伝えて比較する必要があります。あなたが暗号作成者であるなら、私はあなたがこれを読まなければならなかったことを非常に残念に思います。私はそれが多くの開発や規範を苦しめ、矛盾することを理解しています。少なくとも、Telegramのエンジニアは、少なくともDiffie-Hellmanパラメーターの値に適切な推奨事項と要件を使用しています。

2人のユーザーが比較する必要があるフィンガープリントは、Diffie-Hellmanキーハッシュから取得されます。つまり、共有キーの値スペースは2 ^ 2048であり、SHA-1ハッシュ関数は160ビットのハッシュを生成します。 160ビットのハッシュは128ビットに切り捨てられ、指紋の取得に使用されます（図を参照）。

これは暗号の使いやすさの悪夢であることを理解することが重要です。 Telegramユーザーの1人に会うとき、秘密のチャット認証をどのように整理するかを尋ねます。そして、原則として、答えは失望だけをもたらします。通常、ユーザーは、インストールしようとしている秘密チャットを介して、指紋のスクリーンショットを直接送信するだけです。真ん中にいる攻撃者にとって、写真を指紋で自動的に置き換えることは完全に簡単な作業です。

攻撃2 ⁶⁴

さて、今あなたはすべてを正しく行っており、指紋を直接比較してみましょう。また、非常に注意しているため、比較するときに間違いを犯さないでください。

最初の観察は、共通の秘密が2048ビットの素数のスペースにあるという事実にもかかわらず、人が中間で攻撃されるのを防ぐ認証は視覚的に比較される128ビットの指紋のみを使用することです。 HHのパラメーターの効果的な列挙を実行できる場合、中央の人物が印刷物を偽造できます。

2番目の観察結果は、標準的なプロトコルの動作では、中央の人は少数のパラメーターのみで作業する必要があるということです。 2番目のユーザーは、結果の共有シークレットを制御する多くの方法はありません。

DXへの攻撃の古典的なシナリオでは、中間の人物がユーザーごとに個別の共有秘密を選択するだけです。

同時に、攻撃者がソーシャルエンジニアリングを使用して、2番目のユーザーが自分のイニシアチブで秘密のチャットを開始する場合、攻撃者ははるかに自由に行動できます。つまり、攻撃者は2つの公開キー（AとB）を選択するようになりました。中間の人は、異なる指数m1とm2を持つ2つの共有秘密M1AとM1Bを作成できますが、以前は最初のユーザーと共有秘密を選択する自由しかありませんでした。

これは攻撃です。攻撃者はm1とm2の値を列挙し、M1AとM2Aに同じ128ビットのフィンガープリントを提供します。異なる共有シークレットのm1とm2の両方の値を検索する機能により、「誕生日」の攻撃で衝突を検索できます。スペース2 ¹²⁸で検索する代わりに、攻撃者は「m1」の2 ⁶⁴値と「m2」の2 ⁶⁴値を超えて、成功率は約50％です。

複雑さの観点から、攻撃には約2 ^65の操作が必要です。 2015年、この複雑さは容認できないほど低くなりました。参考のため、NISTは2012年末にSHA-1を廃止すると宣言し、 SHA-256を代替品として使用することを推奨しました。 SHA-256に対する誕生日攻撃には、約^2,128の操作が必要です。したがって、高コストにもかかわらず、上記の攻撃は、十分な資金を持つ攻撃者によって完全に実行可能です。

実装の観点から見ると、一見したところ、攻撃には依然として非常に高いリソースが必要と思われます。

誤解の1つは、2048ビットの素数を公開する必要があるため、衝突の検索でこのような大きな値を公開することは計算的に難しいことです。実際、攻撃者は各ステップで2乗およびモジュロ除算を実行するだけで済みます。

別の誤解は2 ^64のメモリの複雑さです。これは、「誕生日」攻撃と並行してメモリ不足の攻撃があり、使用されるメモリと費やされる時間の間にさまざまな妥協戦略があるため、真実ではありません。 Pollardρアルゴリズムを使用して衝突を検索するコードを作成しました。衝突は大量のメモリを必要としません。

全体として、インフラストラクチャと電力に関して数千万ドルの範囲で完全な攻撃を評価し、妥当な時間内に完全な衝突を取得します。攻撃者は、ボットネットやスーパーコンピューターなどの既存のインフラストラクチャを盗んだりレンタルしたりすることもできます。言い換えれば、すべてがスーパーヴィランの予算に収まります。

2 ^60の操作に対する攻撃のコストの見積もり-www.schneier.com/blog/archives/2012/10/when_will_we_se.html

GPA SHAコンピューティングパフォーマンス-gist.github.com/epixoip/c0b92196a33b902ec5f3 www.geforce.com/hardware/desktop-gpus/geforce-gtx-980/buy-online

Telegramは、この攻撃の説明に対して、1兆ドルで攻撃を評価する記事で応答しました。

なぜスーパーヴィランはこの攻撃を必要としないのですか

もちろん、攻撃者はTelegramサーバーにアクセスするために多くのお金を費やし、攻撃を実行するためにさらに多くのお金を費やすことができますが、現実的には、はるかに単純ではるかに有益な攻撃があります。

すべての連絡先リストと通常のチャットは、多くのメタデータを備えたTelegramサーバー上にあり、電話番号と十分なチャットを保存して、頻繁に誰と通信します。攻撃者がTelegramサーバーにアクセスした場合、受信したデータはすでに非常に良好であり、秘密のチャットを盗聴する必要はありません。いいえ、真剣に、それはスーパーヴィランが探している種類の情報ではありませんか？

今、スーパーヴィランが本当に秘密のチャットを傍受したい場合、被害者が新しい秘密の接続を介して単に指紋を送信することを期待できます。残念ながら、多くのユーザーがそれを行っています。そして、私たちはスーパーヴィランについて話しているので、ユーザーが認証に使用しようとする他の通信チャネル（SMSなど）をインターセプトできます。ポイントは、ほとんどの顧客が指紋を読み取り可能な形式で表示しないため、視覚的な指紋を口頭で送信できないことです。 2つの指紋は単純に悪役に置き換えられ、次の個人的な会議まで、ユーザーは通信が傍受されたことを知ることはありません。

そしてもう一つ。人々が電話でプライベートメッセンジャーを使用して、通信事業者によって提供される脆弱な通信手段を回避するとします。ただし、Telegramの唯一の認証システムはSMSコードです。

SMSは十分に保護されておらず、攻撃者がSMSを非常に頻繁に使用することを知っています。 SMSは盗聴され、ハッキングされる可能性があり、ユーザーは偽の基地局に接続される可能性があり、オペレーターもハッキングされる（belgacomを思い出す）か、協力を強制される可能性があります。つまり、SMSが認証方法である場合、Telegramアカウントが盗まれることは明らかです。

SMS攻撃にも高度な技術は必要ありません。スーパーヴィランが敵を攻撃した場合（ 狂気は友人のふりをしている敵です;翻訳者のメモ ）、彼は単純に電話（または電話がパスワードで保護されている場合はSIMカード）を数分間貸してアカウントを盗むことができます。さらに、Telegramは古いメッセージを保存して表示します。盗まれたアカウントから、スーパー悪役はソーシャルエンジニアリングを使用して、連絡先に新しい秘密チャットを開始させ、秘密を伝えることができます。

電報を修正する方法

12月1日、Telegramは前方秘匿を発表しました。この機能は、インストールされたチャネル内でキーローテーションを追加します。しかし、これは、説明されている人間の攻撃を妨害しません。

Telegramにはいくつかの修正点がありますが、最も重要なもののリストを以下に示します。

まず、チャット（グループチャットを含む）には、デフォルトでエンドツーエンドの暗号化が必要です。これにより、人為的ミスや情報漏えいがなくなります。ところで、 ThreemaおよびTextSecureでは、エンドツーエンド暗号化はデフォルトですでに有効になっています。

第二に、エンドツーエンドの暗号化は、すべてのチャットでの認証から、ユーザーを識別する公開キーを使用した暗号化に移行する必要があります。セッションキーを使用して秘密のチャットを認証することは意味がありません。代わりに、各ユーザーはセッションキーを選択する1つ以上の公開キーを持っている必要があります。ユーザーはお互いに一度、すべてを確認します。ところで、ThreemaとTextSecureでは、これはすべて数年前に行われました。

第三に、ユーザー認証はプライベートメッセンジャーにとって非常に弱い保護であり、SMSを傍受する余裕がある攻撃者は簡単にアカウントを盗み、ソーシャルエンジニアリングを使用したり、通常のチャットを表示したりできます。別のアカウント認証スキームが必要です。できるだけ早く、2要素認証のパスワードも必要です。ところで、このベクトルは、Telegramサーバーをハッキングせずに実際の攻撃を行う可能性が最も高く、普通の悪役でさえこれを行うことができますが、スーパー悪役である必要はありません。

そして最後に、Telegramのプライバシーのために、Telegramを匿名で使用できるようにするには、アドレス帳と電話番号を必要とせずに通信を可能にする必要があります。これは現在不可能です。

@Serzhenkoは、2014年末に、Telegramにニックネームが登場したと述べています。 これにより、対話者の電話番号を知る必要がなくなりますが、同時に、電話番号によって認証が実行され、この情報はサーバーに保存されます。 翻訳者によるメモ。

電報競技

現時点では、エンドツーエンドの暗号化を破ったことに対して30万ドルの賞金を獲得する競争があります。説明した攻撃を使用できますか？事実は、競技自体が「中間者」のような攻撃を手配できないように組織されていることです。競技の条件が許せば、攻撃にはチャンスがあります。真実は、ほとんどの場合、計算には賞金以上の費用がかかるということです。もちろん、クラウドソーシングを使用できます。

読者の方は、MTProtoのバグと脆弱性をもっと探してください。少なくともあと2、3あるはずです。

プライバシーが必要なユーザーへの推奨事項

汎用メッセンジャーとして、Telegramは正常に見えます。しかし、プライバシーとプライバシーが必要な場合は、他の何かをお勧めします。たとえば、 ThreemaまたはTextSecureです。

謝辞

協力、アドバイス、サポートをしてくれた@odiumehと、この攻撃について耳を傾けた他の人々に感謝します。 Dhiru KholiaとMarsh Rayのフィードバックに感謝します。

便利なリンク

部分衝突の例

p = 0xc71caeb9c6b1c9048e6c522f70f13f73980d40238e3e21c14934d037563d930f48198a0aa7c14058229493d22530f4dbfa336f6e0ac925139543aed44cce7c3720fd51f69458705ac68cd4fe6b6b13abdc9746512969328454f18faf8c595f642477fe96bb2a941d5bcd1d4ac8cc49880708fa9b378e3c4f3a9060bee67cf9a4a4a695811051907e162753b56b0f6b410dba74d8a84b2a14b3144e0ef1284754fd17ed950d5965b4b9dd46582db1178d169c6bc465b0d6ff9ca3928fef5b9ae4e418fc15e83ebea0f87fa9ff5eed70050ded2849f47bf959d956850ce929851f0d8115f635b105ee2e4e15d04b2454bf6f4fadf034b10403119cd8e3b92fcc5b A = 31255283409627973717223000370765106922189476428506306750544086446550550889396 B = 112771494640069988074840580093805523312740220076402790935086113796930956685865 m1 = 1524456385 m2 = 2871128407 M1A = A2 * m1 mod p M2B = B2 * m2 mod p M1A = 0x894c450b654f0fba7eb0baf97f08cc0aa448a17a2773d5dfcd6827d119d5d910b9f8fa75e25cc23ad30aa819cdcae8e4b4a9f3551afbe37061f3a768b62507c1eb2d017a67d3433f69acec8a5cd2a73008c2f520c71a7cea269325dc8e5bf77778d6349d8db0ac64d7b362218d04bd0a0a0d2a8f8187c4df8f8aa2b177268a505fc8892bda722449a60fff1647601a505e0480af05b14ee5a613414ad3a4ea06d37c03d856e20c5156199bd382048f45e5c150321b8c354fb541946b501aeaf6af039acda9ecb871095f726cc20a920c4b3361cb5f40142fb6319e07667a0e587e49be5f0c7f13960fbc138c9b2c81ae0fff4364d041bfbbf66842d82aca7604 M2B = 0x6722b48e670f4d3c2a24019a9d18211ebbefa407fb94fa3e91bff416cf344d1a2e3bd62c43c92bb4b633586b8e11853faa609c2f474e92033bc0fc97e047e7ed4c2af54a75f7e4bbf08cf9854a478e485b358232aa886b701c5e5dc488335b757cfaf0eda87d5299b5385ca69bdbe758a0b99aa45d371bed4a576cfff4147d384e78ca245cd778d983168a3ebc55950c0203db61c67d903fe77b4879bc35e9529ff51dcbf24add97771a0538ed45d3ee7a269674ded42dc0c85546601485388b045f5196a18355d5a8579df69a06df1519f5bada66270691574b425b22cefa0f6d522394c60f6c5c568f3a16458c64d6dde8cea917cdacbc7fdf552dd7872ef7 SHA1(M1A) = 0xe20bf6722b0a44b7e0fca07bd6c55a74b378ad74 SHA1(M2B) = 0x5813a3521aa452a4a2fffc3ed6c55a74b378ad74 64-bits in common, d6c55a74b378ad74

更新する

O（）表記は人々を悩ませ、不適切でした。また、攻撃のコストに関するTelegramの回答へのリンクを追加しました。

翻訳者のメモ

翻訳の校正をしてくれたHoverHellに感謝します。

翻訳で見つかったすべてのエラーと不正確な点については、個人的にご記入ください。

2 ^ 64操作でのテレグラム攻撃、およびスーパーヴィランがそれを必要としない理由