Renting the Cracking Machine with a Cost-and-Time Analysis of Exhaustive DES-56 Key Search in the Cloud
本論文は、一般的なAWS EC2インスタンスを用いて56ビットのDES鍵空間を全探索する場合、控えめな規模のフリートでは約120万ドルを要し、約21年かかることを示す一方で、資金力があり時間を金で買って完了させる能力を持つ攻撃者にとっては、最短1日で探索を完了させることが実質的に可能であり、さらに小規模な部分空間攻撃であれば無視できる程度のコストで実行可能であることを実証している。
原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 これは以下の論文のAI生成解説です。著者が執筆したものではありません。技術的な正確性については原論文を参照してください。 免責事項の全文を読む
デジタルな鍵と錠前が支配する世界を想像してみてください。そこでは、秘密のメッセージは、意図された受信者だけが読み取れるように、巧妙に暗号化されています。何十年もの間、「DES（データ暗号化標準）」と呼ばれる特定の錠前が、秘密を守るための黄金律でした。DESを、56個の数字が並んだダイヤルを持つ巨大なダイヤル錠だと考えてみてください。これを破るには、錠前がカチッと開くまで、あらゆる組み合わせをすべて試さなければなりません。数字の数が非常に多いため、かつては、スーパーコンピュータや、膨大な数の専用設計されたマシンを使わない限り、これほど速く全ての組み合わせを試すことは不可能だと考えられていました。しかし、世界は変わりました。今日、「クラウド」というものが存在します。これは、自分自身のコンピュータを購入する代わりに、分単位で巨大で見えないコンピュータの軍隊をレンタルするようなものです。研究者たちが問い続けてきた大きな疑問はこうです。「もしこの古い錠前を破りたいだけなら、その軍隊をレンタルするのにいくらかかり、どれくらいの待ち時間が発生するのか？」という問いです。もしコストが低く、待ち時間が短いのであれば、その古い錠前はもはや安全ではなく、私たちの古い秘密が実際にどれほど脆弱であるかを正確に知る必要があるからです。
この論文は、ゴンサロとロドリゴという二人の研究者が、DESの錠前を破るために実際にクラウドの軍隊をレンタルして答えを見つけ出そうとした、大胆な実験のようなものです。彼らは特別な機械を作ったわけではありません。単に、AmazonのAWSクラウド上で、クレジットカードさえあれば誰でも利用できる標準的なコンピュータを使用したのです。彼らは、37台のコンピュータからなるチームを編成し、それぞれが膨大な組み合わせの中から異なる区画をチェックするように設定しました。彼らはこの作業を、巨大なスカベンジャー・ハント（宝探し）のように扱いました。彼らは「宝物」（秘密の鍵）をスタート地点からさまざまな距離に隠し、それを見つけるまでにどれくらいの時間がかかったかを計測しました。
結果は、距離が近い場合には驚くほど速く、そして安価でした。宝物が近く（最初の1億組み合わせ以内）に隠されていたとき、コンピュータは作業を開始するための準備や起動にほとんどの時間を費やしていました。このようなケースでは、作業全体に約2分かかり、コストは50セント未満でした。それは、タクシー運転手に数ドル払って角の店まで行ってもらうようなものでした。ドライブ自体は一瞬でしたが、時間は主に運転手が到着するのを待つことに費やされていました。
しかし、宝物をさらに遠くに隠すと、物語は変わりました。探索を150億組み合わせまで押し広げると、実際に鍵を探している時間が主要な要因となりました。コンピュータは着実に稼働し、約87分間で、コストはおよそ18ドルで鍵を見つけ出しました。研究者たちは、コンピュータが極めて効率的であり、一台のコンピュータで毎秒300万近い組み合わせをチェックできることを発見しました。37台のコンピュータすべてを合わせると、彼らは毎秒1億個以上の鍵をチェックしていたことになります。
彼らの発見の中で最もエキサイティングな部分は、単に一部を破るのではなく、本当に「錠前全体」を破りたい場合に何が起こるかという点です。完全な錠前には、約72クアドリリオン（7200兆）もの組み合わせが存在します。現在の37台のコンピュータのセットアップでは、すべての組み合わせをチェックするのに約21年かかります。これは不可能に思えるかもしれません。しかし、研究者たちは、この作業は非常に分割しやすい性質を持っているため、お金を時間と交換できることを示しました。もし非常に深い懐（ふところ）を持ち、約14万台のコンピュータからなる巨大な艦隊をレンタルすれば、わずか一日で錠前全体を破ることができます。その膨大な努力にかかる総コストは約120万ドルです。
では、これは何を意味しているのでしょうか？ この論文は、古いDESの錠前が事実上、破られたことを証明しています。もし悪い奴が少額の資金を持っていれば、コーヒー一杯の値段で特定の限定的なコードを解読できてしまいます。もし彼らが多額の資金を持っていれば、たった一日でコード全体を解読できるのです。研究者たちはまた、コンピュータを用いた彼らのアプローチは高速であったものの、現代のグラフィックカード（ビデオゲームに使われる種類のもの）を使用すれば、これをさらに安く、より速くでき、おそらく時間をさらに100倍短縮し、コストをさらに削減できるだろうとも指摘しています。結論は明白です。56ビットの錠前はもはや障壁ではありません。それは、いかに多くの現金を投じてその錠前を壊すかという、単なる問題なのです。
自分の分野の論文に埋もれていませんか？
研究キーワードに一致する最新の論文のダイジェストを毎日受け取りましょう——技術要約付き、あなたの言語で。