Sum Checksum の衝突 (2019)

Sum チェックサムの衝突

2019-11-23

sum コマンドラインツールは、BSD および GNU Coreutils に含まれるシンプルなチェックサムユーティリティです。これは暗号学的に安全なハッシュではないため、私はファイルの sum を任意の С значениеに設定するツールを作成しました。

そのツールと関連コードは、私の GitHub アカウントの sumcoll リポジトリ で見つけることができます。

使用方法

Sum はコマンドラインでファイルを受け取り、1024バイトブロックのカウントと共に、10進数でチェックサム値を表示します。

$ echo abcdef > file
$ sum file
33901     1

背景

数年前、課題の締め切り後にコードを変更していないことを検証するために、宿題の BSD sum を含めるように依頼されました。ファイルの sum は、授業中に紙で提出された記述部分と共に含められ、コードは後で採点されました。

セキュリティ

このタスクに暗号学的に安全ではないハッシュを使用することは完全に安全ではありません。悪意のある学生は、紙の配布資料に提出されたものと同じチェックサムを持つ別のファイルを見つけることができるからです。それを防ぐために必要な特性は 第二原像耐性 (Second Preimage Resistance) と呼ばれます。悪意のある学生は、課題の締め切り前に m1 を選択し、その後 hash(m1) = hash(m2) となる m2 を見つけることができれば、検出されずに m2（第二原像）を提出できます。m2 がより高い評価を得られるかどうかは、学生への演習問題とします。

アルゴリズムに関する知識がなくても、安全ではないことがわかります。sum ユーティリティの出力は16ビットの数値（通常は10進数で表示）であり、入力に含まれる1024バイトブロックの数も表示されます。出力がわずか16ビットでは単純に大きさが足りず、総当たり攻撃で衝突を見つけることができます。2^16 + 1 個のファイルを sum すれば、衝突が見つかることが保証されます。これは私たちが望む第二原像そのものではありませんが、小さなチェックサム値が暗号学的に安全ではありえないことを示す例となります。

アルゴリズム

盲目的に総当たり攻撃をする必要はありません。sum がどのように機能するかを調べ、攻撃方法をより賢くすることができます。アルゴリズムは非常にシンプルです。各バイトは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 ツールと攻撃ツールの両方の実装がここにあります。そのツールやこのブログ投稿に関するフィードバックがあれば、そこで issue を投稿するか、私にメールでご連絡ください。