NeoQUEST-2016のオンラインステージのタスクを引き続き分析し、全員を招待する「 対立 」に備えています。 興味深いレポート、攻撃のデモ、コンテスト、賞品などが待っています！
まれなハッククエストは暗号化なしで行われ、NeoQUEST-2016も例外ではありませんでした！ オンライン段階のタスクでは、RSA暗号システムを選択しました。RSA暗号システムのセキュリティについては、長い間議論されています。 教育目的および教育目的で、RSAで最も人気のある攻撃ではなく、Hastad攻撃を行いました。
さらに、タスクの初期データを（一見）提供せずに、参加者を整然と混乱させました。 私たちは、どこを見るべきか、見つかったものをどうするか、そしてハスタッド攻撃を実装する方法について読んでいます-カットの下で！
タスクはどこにありますか？
...参加者はこの質問にsupport@neoquest.ruで回答しました。 彼らは理解することができた：両方の伝説のテキストは本当に何も言わなかった。
透明なヒントの後、参加者はサイトのメインページのマップを思い出し、調査に行きました。
ジョブのソースデータを見つける方法はいくつかありました。 非常に慎重な幸運な人々は、マウスカーソルをマップ上に移動すると、いくつかのポイント（または3つ！）でカーソルが手に変わることに気付きました。これは通常、リンクにカーソルを合わせると表示されます。 ファイルをクリックすると、.asn1ファイルがダウンロードされました。
他の参加者は目を痛めないことを決定し、「インスペクター」によってサイトを見て、すぐに著作権の下で同じ3つの隠しファイルを見つけました：cert1_f2ad1569.asn1、cert2_512243c0.asn1、cert3_126ec46b.asn1。
Parsim ASN.1
ASN.1は、暗号化など、広く使用されているコーディング情報の標準です。 Habré （明確な言語で書かれた詳細な記事）とサードパーティのリソース（ こことそこ ）の両方で、標準に関する詳細を読むことができます。 ASN.1のデータは、「タグ-長さ-値」のシーケンスとして表されます。 この場合、「タグ」はデータ型を決定し、「長さ」は次のフィールド「値」のサイズを設定します。
これら3つの.asn1ファイルに含まれる情報の種類を調べるには、それらを解析する必要があります。 ASN.1 JavaScriptデコーダーまたはdumpasn1コマンドラインアプリケーションなど、これに使用できるプログラムは多数あります 。
dumpasn1を使用して、3つのファイルすべてを順番に開きます。次のように表示されます。
3つのファイルすべての構造は同じです; 3つのファイルすべてのOBJECT IDENTIFIER rsaEncryption行はRSAを明確に示しています。 各ファイルには、明らかに3つのRSAパラメーターが含まれており、3つのファイルすべての1つのパラメーターは3と同じです。RSA（ Wikiなど ）に対する攻撃の可能性の調査を開始し、パラメーター3は他の2つのパラメーターに比べて著しく小さい、これはオープン指数eにすぎないという考えを示唆しています！ したがって、Hastadの攻撃を実装できます。
Hastadの攻撃を実装します
初期攻撃データ
Hastadの攻撃について詳しくは、 こちらをご覧ください 。 攻撃を実装するための条件は次のとおりです。ユーザーAは暗号化されたメッセージmを複数のユーザーに送信します。 この場合、3（ファイルの数による）：P 1 、P 2 、P 3 。 各ユーザーは、「モジュールオープン指数」（n i 、e i ）とM <n 1 、n 2 、n 3のペアで表される独自のキーを持っています。 3人のユーザーごとに、Aは対応する公開鍵でメッセージを暗号化し、その結果を宛先に送信します。
攻撃者は、メッセージの傍受を認識し、送信された暗号文（C 1 、C 2 、C 3として表記）を収集して、元のメッセージMを復元します。.asn1ファイルを注意深く見てください。最初のパラメーター、明らかに、RSA nモジュール、2番目、すでにわかっています-開いた指数、つまり3番目のパラメーターは暗号文です。 そのため、利用可能な3つの暗号文を使用して、メッセージを復元する必要があります。これはどちらかのキーになります。 または、タスクのキーを探す場所に関するヒントを提供します。
なぜ正確に実装できるのですか？
ご存じのとおり、RSAスキームによるメッセージの暗号化は次のとおりです。C= M e mod n。 3に等しいオープン指数の場合、暗号文の取得は次のようになります。
C 1 = M 3 mod n 1
C 2 = M 3 mod n 2
C 3 = M 3 mod n 3
n 1 、n 2 、n 3は相互に単純であることがわかっているため、 中国の剰余定理を暗号文に適用できます。
結果として、いくつかのC 'を取得します。その立方根は、目的のメッセージMを提供します。
C ' = M 3 mod n 1 n 2 n 13
Mは3つのモジュールn iのそれぞれよりも小さいことを思い出してください。これは、等式が成り立つことを意味します。
C ' = M 3
したがって、目的のメッセージMが見つかります。
Hastad攻撃のソフトウェア実装
参加者の1人がPythonスクリプトを実装しました。詳細な記述はここにありますが、そこからスクリプトコードのみを提供します。
import math c_flag1 = 258166178649724503599487742934802526287669691117141193813325965154020153722514921601647187648221919500612597559946901707669147251080002815987547531468665467566717005154808254718275802205355468913739057891997227 N1=770208589881542620069464504676753940863383387375206105769618980879024439269509554947844785478530186900134626128158103023729084548188699148790609927825292033592633940440572111772824335381678715673885064259498347 c_flag2 = 82342298625679176036356883676775402119977430710726682485896193234656155980362739001985197966750770180888029807855818454089816725548543443170829318551678199285146042967925331334056196451472012024481821115035402 N2=106029085775257663206752546375038215862082305275547745288123714455124823687650121623933685907396184977471397594827179834728616028018749658416501123200018793097004318016219287128691152925005220998650615458757301 c_flag3 = 22930648200320670438709812150490964905599922007583385162042233495430878700029124482085825428033535726942144974904739350649202042807155611342972937745074828452371571955451553963306102347454278380033279926425450 N3=982308372262755389818559610780064346354778261071556063666893379698883592369924570665565343844555904810263378627630061263713965527697379617881447335759744375543004650980257156437858044538492769168139674955430611 def chinese_remainder(n, a): sum = 0 prod = reduce(lambda a, b: a*b, n) for n_i, a_i in zip(n, a): p = prod / n_i sum += a_i * mul_inv(p, n_i) * p return sum % prod def mul_inv(a, b): b0 = b x0, x1 = 0, 1 if b == 1: return 1 while a > 1: q = a / b a, b = b, a%b x0, x1 = x1 - q * x0, x0 if x1 < 0: x1 += b0 return x1 def find_invpow(x,n): """Finds the integer component of the n'th root of x, an integer such that y ** n <= x < (y + 1) ** n. """ high = 1 while high ** n < x: high *= 2 low = high/2 while low < high: mid = (low + high) // 2 if low < mid and mid**n < x: low = mid elif high > mid and mid**n > x: high = mid else: return mid return mid + 1 flag_cubed = chinese_remainder( [N1, N2, N3], [c_flag1, c_flag2, c_flag3] ) flag=find_invpow(flag_cubed,3) print hex(flag)[ 2 : -1 ].decode("hex")
コードからわかるように、パラメーターn iおよびC iは最初にファイルから取得され、HEX形式から大きな整数に変換されました。 次に、中国の剰余定理が実装され、最終的に、希望するメッセージを取得するために立方根が抽出されました。
キー= bff149a0b87f5b0e00d9dd364e9ddaa0
受信したメッセージにはキーが含まれ、タスクは完了しました！
結論として
参加者がRSAスキームの実装でエラーを見つけるか、モジュール分解に対する攻撃（ ここでのタスクの分析）を実行する必要があった前年のNeoQUESTタスクに続き、 Wiener攻撃を実装しました。これは、分解に基づいていないHastad攻撃が選択されました。
サポートするNeoQUEST-2016のオンラインステージの参加者の魅力の統計が示したように、彼らにとっての主な問題は、割り当てと隠されたソースデータのわかりにくい表現でした。 ただし、ファイル形式も参加者の一部を困らせています。
オンラインフェーズの最高の参加者は、7月7日にサンクトペテルブルクで開催される「対決」で間もなく開催されます。 そして、情報セキュリティ企業の専門家、ハッカーやオタク、IT専門の志願者や学生など、誰もがレポートに耳を傾け、コンテストに参加している間、参加している人たちが仕事をしている間、素晴らしい時間を過ごしてください！ 入場は無料です。 サイトに登録するだけです。 NeoQUESTは、この夏にサンクトペテルブルクを訪れるもう1つの理由です！