任意の CRC 値になるバイト列を逆算してみよう #Ruby

例えばここに文字列 "123456789" があったとします。これを CRC-32 にかけると、0xCBF43926 が出てきます。

さらに続けて、CRC-32 に合わせて生成した4バイトのデータを喰わせて、最終的な CRC 値を任意の値にしてみよう、ただし総当り攻撃することなく、というのがテーマです。

CRC の算出のために実装方法さえわかっていればガロア体の理論が不要であるように、任意の CRC 値になるバイト列を求める方法もまたそんなに難しいことではありません。

当文書ではビット長が16である CRC-16 (生成多項式 0x8005、ビット反転入力、ビット反転出力、初期 CRC 値は 0、出力 XOR 値は 0) を用いて解説をしていきます。

当文書に含まれる疑似コード、ruby コードは、Creative Commons Zero License (CC0 / Public Domain) のもとで利用できます。

1ビット入力時の CRC-16 を算出するおさらい

まず初めは1ビットの入力値 I = 1 を通常の CRC-16 処理する場合の復習です。ただし、ガロア体 (有限体) からみっちり話すのではなく、実装の話のみです。

生成多項式をビット反転し P = 0xA001、いま現在の内部状態は S = 0xAAAA であるとします。

(1) 内部状態 S と入力値 I とで排他的論理和を取る
```
S' = S ^ I = 0xAAAA ^ 0x01 = 0xAAAB
```
(2) S' を1ビット右シフトする
```
S'' = S' >> 1 = 0xAAAB >> 1 = 0x5555
```
(3) S' の最下位ビットが 1 であれば、S'' と P とで排他的論理和を取る

最下位ビットが 0 であれば何もしません。
```
if (S' & 0x01 == 1)
  # 今回はこっち
  Sfinal = S'' ^ P = 0x5555 ^ 0xA001 = 0xF554
else
  Sfinal = S''
end
```

これで1ビットを入力した時の内部状態 Sfinal = 0xF554 が求まりました。

この値と XOR マスクとで排他的論理和を取り、CRC 値とするわけです。もっとも CRC-16 の場合は XOR マスクは 0 なので、今回は省いています。

ruby で実装した `update_in_bit`

ruby

REVERSED_POLYNOMIAL = 0xA001

def update_in_bit(input, state)
  state = state ^ input
  state2 = state >> 1

  if state & 0x01 == 0
    # 何もしない
  else
    state2 = state2 ^ REVERSED_POLYNOMIAL
  end

  return state2
end

p update_in_bit(1, 0xAAAA).to_s(16)
# => "f554"

CRC-16 における内部状態の巻き戻し

次に内部状態を巻き戻すことについて考えてみましょう。

単純に (1)、(2)、(3) で行った逆のことを辿ればどうにかなりそうです。鍵となるのは (2) (3) の部分です。

右シフトするということは、最上位ビットに 0 を差し込んでいると考えることが出来ます。なので、最上位ビットが 1 であれば、生成多項式で排他的論理和を取ってやるとうまく行きそう……ですね。

そして (3) を行うには、最下位ビットが 1 の時なので、1 を差し込みます。

処理の都合を考えると、(2) と (3) を入れ替えたほうがやりやすそうです。

内部状態 S = 0xF554、1ビットの入力値 I = 1 です。

(2') S を1ビット左シフトする
```
S' = S << 1 = 0xF554 << 1 = 0x1EAA8
```
(3') S' の溢れビットが 1 であれば、生成多項式を反転した P を1ビット左シフトして XOR し、さらに最下位ビットに 1 を差し込む
```
if (S' & 0x10000) != 0
  # 今回はこっち
  S'' = S' ^ ((P << 1) | 1) = 0x1EAA8 ^ ((0xA001 << 1) | 1) = 0x1EAA8 ^ 0x14003 = 0xAAAB
else
  S'' = S'
end
```
(1') S'' と入力値 I とで排他的論理和を取る
```
Sfinal = S'' ^ I = 0xAAAB ^ 0x01 = 0xAAAA
```

1ビットの入力を行う前の内部状態の値である Sfinal = 0xAAAA が出てきました。

だけど本当にこんな簡単なのか? と疑いたくもなりますが、本題で確認も兼ねることにしましょう。

ところで (3') のところでピンときた! という人は鋭いですね。

((P << 1) | 1) = 0x14003 を16ビットに切り詰めてビット反転してやると 0xC002 になります。ウィキペディアの巡回冗長検査の記事中に出てくる相反多項式の反転 (Reversed reciprocal) の値です。

まさかこんなところでお目にかかるとは。

ruby

def reversed_reciprocal(bitsize, polynomial)
  (polynomial | (1 << bitsize)) >> 1
end

p reversed_reciprocal(16, 0x8005).to_s(16)
# => "c002"

ruby で実装した `rewind_in_bit`

ruby

REVERSED_POLYNOMIAL = 0xA001

def rewind_in_bit(input, state)
  state = state << 1

  if state & 0x10000 == 0
    # 何もしない
  else
    state = state ^ (REVERSED_POLYNOMIAL << 1) | 1
  end

  return state ^ input
end

p rewind_in_bit(1, 0xF554).to_s(16)
# => "aaaa"

CRC が決まった値を返す?

CRC は、算出した値をバイト列に格納し、元のバイト列に追加してまとめて CRC を算出すると、常に一定の値 (魔法数 / マジックナンバー) が出てくることはよく知られています (dearblue は最近 (平成29年2月になってから) 知ったようです)。

CRC-16 であれば 0x0000、 CRC-32 であれば 0x2144DF1C といった値のことです。

試してみましょう。

バイト列 "123456789" がある時、この CRC-16 値を算出すると、0xBB3D になります。

これをリトルエンディアンで格納し追加したバイト列 "123456789\x3D\xBB" の CRC-16 値を算出すると 0x0000 になるわけです。

irb

# dearblue 拙作の CRC ライブラリが必要です。
# 試す場合は、gem install crc を行って下さい。
# もしくは、"digest-crc" ライブラリで適当に置き換えて下さい。

irb(main):001:0> require "crc"
=> true

irb(main):002:0> CRC::CRC16.hexdigest("123456789")
=> "BB3D"
irb(main):003:0> CRC::CRC16.hexdigest("123456789\x3D\xBB")
=> "0000"
irb(main):004:0> CRC::CRC16.hexdigest("123456789abcdefg")
=> "612E"
irb(main):005:0> CRC::CRC16.hexdigest("123456789abcdefg\x2E\x61")
=> "0000"

irb(main):006:0> CRC::CRC32.hexdigest("123456789")
=> "CBF43926"
irb(main):007:0> CRC::CRC32.hexdigest("123456789\x26\x39\xF4\xCB")
=> "2144DF1C"
irb(main):008:0> CRC::CRC32.hexdigest("123456789abcdefg")
=> "A2CAAFFF"
irb(main):009:0> CRC::CRC32.hexdigest("123456789abcdefg\xFF\xAF\xCA\xA2")
=> "2144DF1C"

# CRC-32-POSIX は順方向入力 (ビット反転しない) であるため、ビッグエンディアンで格納することに注意
irb(main):010:0> CRC::CRC32_POSIX.hexdigest("123456789")
=> "765E7680"
irb(main):011:0> CRC::CRC32_POSIX.hexdigest("123456789\x76\x5E\x76\x80")
=> "38FB2284"
irb(main):012:0> CRC::CRC32_POSIX.hexdigest("123456789abcdefg")
=> "6D984820"
irb(main):013:0> CRC::CRC32_POSIX.hexdigest("123456789abcdefg\x6D\x98\x48\x20")
=> "38FB2284"

CRC の逆算

ようやく本題です。

"123456789??" の CRC-16 値を算出して digest すると "OK" (16進数で 0x4F4B) と出るような、"??" を求める方法を考えてみましょう。

すでに内部状態の巻き戻しは見てきた通りです。

ここで問題なのは、巻き戻しのための入力値をどこから取得すればいいのかです。

目を細めてじーっと探ってみると、内部状態と入力値とで排他的論理和を取っているところ (1) (1') に目が止まります。

そして、"123456789" までの内部状態は 0xBB3D です。

入力値の代わりに、この内部状態の値を使えそうだとゴーストが囁きませんか?

なので、試しに目標となる内部状態 0x4F4B から巻き戻しのために、リトルエンディアンでバイト列に格納した [0x3D, 0xBB] が入力された事にしてみましょう。

状態を巻き戻すため、入力時とは逆順となる第2バイトの上位ビットから入力していきます。

ruby

def rewind_in_byte(input, state)
  input.reverse_each do |ch|
    8.times do
      state = rewind_in_bit((ch >> 7) & 0x01, state)
      ch <<= 1
    end
  end

  return state
end

p rewind_in_byte([0x3D, 0xBB], 0x4F4B).to_s(16)
# => "1026"

結果として、0x1026 が出てきました。これをリトルエンディアンでバイト列に格納、追加し、バイト列 "123456789\x26\x10" の CRC-16 値を算出してみましょう。

ruby

# dearblue 拙作の CRC ライブラリが必要です。
# 試す場合は、gem install crc を行って下さい。
# もしくは、"digest-crc" ライブラリで適当に置き換えて下さい。

require "crc"

p CRC::CRC16.digest("123456789\x26\x10")
# => "OK"

うまくいったようです。

今度は "123456789??123456789" の ?? に埋め込んで、"OK" にしてみましょう。

ruby

p rewind_in_byte([0x3D, 0xBB, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39], 0x4F4B).to_s(16)
# => "3a67"
p CRC::CRC16.digest("123456789\x67\x3A123456789")
# => "OK"

ちゃんと OK になりました。

応用

ビット長の異なる CRC であっても、考え方は変わりません。溢れ桁の位置や、格納バイト長を変更すれば可能です。ただし、バイト単位長に一致しない12ビット長や31ビット長などである場合は、桁合わせが必要となります。

また、入力が順方向である場合、内部状態値からバイト列へビッグエンディアンとして格納することになり、rewind_in_bit のシフト方向も逆にします。

さらに出力 XOR マスクが 0 以外であれば、CRC 値と内部状態の値とでそれぞれ変換するために XOR マスクと排他的論理和を取る必要があります。

このあたりの答え合わせは、https://github.com/dearblue/ruby-crc/blob/0.4.1/lib/crc/acrc.rb および https://github.com/dearblue/ruby-crc/blob/0.4.1/lib/crc/_shift.rb#L107 をご参照下さい (当文書で rewind となっているメソッドは、github 上では unshift となっているのでご注意下さい。ビット反転入力時のみに限定されますがテーブルを用いた実装も記述されており、当文書で説明したものよりも高速です)。

irb

# dearblue 拙作の CRC ライブラリが必要です。
# 試す場合は、gem install crc を行って下さい。

irb(main):001:0> require "crc/acrc"
=> true
irb(main):002:0> prefix = "123456789"
=> "123456789"
irb(main):003:0> postfix = "abcdefg"
=> "abcdefg"
irb(main):004:0> targetcrc = 0x64656172626c7565
=> 7234295520346010981
irb(main):005:0> code = CRC.crc64.acrc(prefix, postfix, targetcrc)
=> "\xB7\x15\x80\xB72t\xA1\xCE"
irb(main):006:0> CRC.crc64.digest(prefix + code + postfix)
=> "dearblue"

誤り訂正は可能といえば可能ですが、ハミング符号やリードソロモン符号などそれ向けの手法がいろいろ転がっているので、そっちを頼ったほうが良いでしょう。

最後に

あくまでもお遊びであり、データを CRC-64 にかけて digest を求めると常に文字列 "dearblue" になる! といったものを実現してニヤニヤするための機能です。

セキュリティにおけるデータ改竄を検出するために未だに CRC を使っているシステムを見つけても、興味本位で攻撃を仕掛けるのはおやめ下さい。マジで逮捕されますよ。

任意の CRC 値になるバイト列を逆算してみよう

1ビット入力時の CRC-16 を算出するおさらい

ruby で実装した update_in_bit

CRC-16 における内部状態の巻き戻し

ruby で実装した rewind_in_bit

CRC が決まった値を返す?

CRC の逆算

応用

最後に

ruby で実装した `update_in_bit`

ruby で実装した `rewind_in_bit`