Sum Checksum の衝突 (2019)

ホーム | Matthew McPherrinについて 2019-11-23 Sum Checksum の衝突 sumコマンドラインツールは、BSDおよびGNU Coreutilsに含まれるシンプルなチェックサムユーティリティです。これは暗号学的に安全なハッシュではないため、私はファイルのsumを任意の値に設定するツールを作成しました。このツールと関連コードは、この投稿のgithubアカウントにあるsumcollリポジトリで見つけることができます。 使用法 Sumはコマンドラインでファイルを取り、1024バイトブロックの数と共に、10進数でチェックサム値を出力します。 $ echo abcdef > file $ sum file 33901 1 背景 数年前、課題の締め切り後にコードを変更していないことを確認するために、宿題のBSD sumを含めるように依頼されました。ファイルのsumは、授業で紙に提出された記述部分と共に含まれ、コードは後で採点されました。 セキュリティ このタスクに暗号学的に安全ではないハッシュを使用することは完全に安全ではありません。悪意のある学生は、紙の配布資料に記載されているものと同じチェックサムを持つ別のファイルを見つけることができます。そのために必要なプロパティは、セカンドプリイメージ耐性と呼ばれます。悪意のある学生は、締め切り前にm1を選択し、その後、hash(m1) = hash(m2)となるm2を見つけることができれば、検出されずにm2を提出できます。m2がより良い成績につながるかどうかは、学生への演習課題とします。使用されているアルゴリズムを知らなくても、安全ではないことがわかります。sumユーティリティの出力は16ビットの数値（通常は10進数で表示）と、入力に含まれる1024バイトブロックの数であることがわかります。出力がわずか16ビットであることは単純に十分ではなく、衝突を見つけるために総当たり攻撃を使用できます。2^16 + 1個のファイルをsumすると、衝突が見つかることが保証されます。これは、私たちが望む2番目のプリイメージではありませんが、小さなチェックサム値が暗号学的に安全でない方法を示しています。 アルゴリズム このアルゴリズムは非常にシンプルです。各バイトが16ビットカウンタに追加され、各加算の間にカウンタは右に回転します。または、Pythonでは次のようになります。 def rotate_right_16bit(data: int) -> int: return (data >> 1) | ((data & 1) << 15) for byte in data: sum = rotate_right_16bit(sum) + byte sum = sum & 0xffff # 16ビットにクランプする 後ろ向きに このアルゴリズムを見ると、最初に気づくのは、すべての操作が可逆であるということです。減算と左回転を行うことで、後ろ向きに進むことができます。これにより、ファイルの任意の時点の文字を追加または変更でき、最終目標値を得るために必要なチェックサムの中間値を簡単に見つけることができます。 def rotate_left_16bit(data: int) -> int: return (0xffff & (data << 1)) | (data >> 15) for byte in reversed(suffix): sum = rotate_left_16bit((sum - byte) & 0xffff) 変更を加える 私たちが書いているツールは、指定されたオフセットにバイトを挿入します。挿入された追加の文字は、コメント、文字列、または変更可能な場所に配置します。挿入ポイントまでのプレフィックスのsumを計算し、逆方向のsum計算を使用して反対側から同じポイントにアプローチします。私たちのタスクは、プレフィックスの後に挿入されたときに、その時点までのsumが逆方向のsumと等しくなるような文字のセットを見つけることです。これは総当たり攻撃で解決可能ですが、後ろ向きに進むことができるため、もう少し賢くできます。 ミートインザミドル 私たちのツールが採用する戦略は、可能なハッシュのセットが小さいという事実と、後ろ向きに進むことができるという事実を利用します。プレフィックスとサフィックスの文字列をそれぞれ1文字ずつ交互に拡張し、結果のハッシュが反対側のセットのいずれかにヒットしたかどうかを確認します。つまり、プレフィックスの末尾に文字を追加し、サフィックスのハッシュのいずれかにヒットしたかどうかを確認し、次にサフィックスの先頭に文字を追加して、プレフィックスのハッシュのいずれかにヒットしたかどうかを確認します。バースデーパラドックスとハッシュのセットがわずか2^16であるという事実により、この攻撃は私のコンピュータではほんの一瞬で実行されます。 文字セット 衝突を生成するコードはバイト文字列を入力として受け取り、その中のバイトのみを使用します。これは、たとえば、印刷可能な文字のみ、ASCII小文字のみ、またはファイルが破損しないように必要なものだけを供給できることを意味します。通常、これは、行末コメントスタイルのコメントが多い場合は、改行を含まない印刷可能な文字を必要とします。または、CSSのような/* */スタイルのコメントのみを使用する場合は、/を避けることができます。 ブロックサイズ 数バイトを挿入すると、入力のブロック数が変わる可能性があります。これについてはご自身で対処してください。新しいバイトを別の場所に挿入するか、他のバイトを先に削除してみてください。 結論 これは厳密には強化されたターゲットではないため、目新しいことは何もありませんが、これを達成する方法に関するドキュメントはどこにも見つかりませんでした。誰かがこれを必要とすると疑う余地はありませんが、sumツールと攻撃ツールの両方の実装がここにあります。このツールまたはこのブログ投稿に関するフィードバックがあれば、そこで問題を投稿するか、私にメールしてください。