任意の CRC 値となるデータをつくろう (三分ハッキング)
求めたい CRC 値を予め決めてから、総当りせずに逆算してデータを作成すると言うのがテーマです。
情報技術の分野で CRC と言えば巡回冗長性検査 (Cyclic Redundancy Check) ですよね。
で、これは主にデータの破損を検出するために用いられていることは、広く知られていることでしょう。
基本的に一方向性ではありますが、任意の CRC 値を持つデータを容易に作成することが可能です。
この怪文書は、CRC 値を好き勝手に決め打ちにして、そこからバイト列を作成しようという手順を示したものです。
あなたがこれを理解した時、このことを知らない人々を驚かせるデータファイルを作成できますよ (悪さしちゃいけません)。
この文書内で使われている擬似コードは、パブリックドメインに移管します。好き勝手に置き換えて利用することが可能です。
## ☀ おさらい
最初に CRC 値の計算手順をおさらいしましょう。処理を追っているだけで、正確な理論・説明はしません (理解できていない部分を説明することは出来ませんし)。
例として今回取り上げる CRC はビット数を短めにして、CRC-16-0x8005 reflect-input reflect-output initial-crc=0 xor-output=0 (一般的な CRC-16 のこと) とします。
生成多項式 0x8005 は、reflect-input の処理をするとき都合の良いように、ビット並びを逆にします。それぞれを P、Q とします。
P = 0x8005 = [[1000 0000 0000 0101]] /* 元の生成多項式の二進数表記 */
Q = 0xA001 = [[1010 0000 0000 0001]] /* ビットを逆順にした生成多項式の二進数表記 */
次にバイト列を用意します。
src = [0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39] /* 文字列にすると "123456789" */
内部状態を S とする時、初期状態は initial-crc XOR xor-output であり、0 となります。
S = initial_crc XOR xor_output = 0 = [[0000 0000 0000 0000]]
1. src の最初のバイト値を取り出し、下位ビットから順に処理していきます。
0x31 = [[0011 0001]]
2. 0x31 の最下位ビットである『1』と内部状態 S の最下位ビットとで、排他的論理和を求めます。
S = [[0000 0000 0000 0000]] XOR 1
S = [[0000 0000 0000 0001]]
3. S を右シフトします。
S = [[0000 0000 0000 0001]] >> 1
S = [[0000 0000 0000 0000]] /* 最下位ビット『1』があふれた */
4. あふれた最下位ビットが『1』であれば、S とビットを逆順にした生成多項式 Q とで排他的論理和を取ります。
S = S XOR Q = [[1010 0000 0000 0001]]
もし『0』であれば、S には何もしません。つまり、次のようにするわけです。
if (あふれた最下位ビット != 0) {
S = S XOR Q
}
5. 残ったビットを下位から順に繰り返します。
[[1010 0000 0000 0001]] /* 0x31 の LSB-0 (1) を処理した段階の S */
[[1111 0000 0000 0001]] /* 0x31 の LSB-1 (0) を処理した段階の S */
[[1101 1000 0000 0001]] /* 0x31 の LSB-2 (0) を処理した段階の S */
[[1100 1100 0000 0001]] /* 0x31 の LSB-3 (0) を処理した段階の S */
[[0110 0110 0000 0000]] /* 0x31 の LSB-4 (1) を処理した段階の S */
[[1001 0011 0000 0001]] /* 0x31 の LSB-5 (1) を処理した段階の S */
[[1110 1001 1000 0001]] /* 0x31 の LSB-6 (0) を処理した段階の S */
[[1101 0100 1100 0001]] /* 0x31 の LSB-7 (0) を処理した段階の S */
6. 残ったバイト値を同様に処理します。
7. 内部状態 S と xor-output とで排他的論理和を求めて終了。
crc = S XOR xor_output = 0xBB3D XOR 0x0000 = 0xBB3D
crc16("123456789") => 0xBB3D
ここまでが CRC 値の処理の流れとなります。
おさらいここまで。
## ☀ どうやって逆算しようか?
おさらいが終わったところで、欲しい CRC 値となるバイト列をどうやって求めるかについて考えてみましょう。
最初に思いつくのは総当り攻撃 (ブルートフォースアタック; brute force attack) ですが、テーマから外れるし話が終わってしまうのでポイします。
そうすると逆算できるのかどうかですが、結論から言うと前書き通り可能です。
まずは
* 内部状態と、同じビット幅の入力ビット列を置き換えても計算結果は変わらない (おさらいの (2) に着目)
* 右シフトするということは、最上位ビットに『0』を入力することと同じ (おさらいの (3) に着目)
あたりを考えてみましょう。
内部状態と入力ビット列を置き換えても計算結果が変わらないのかと言うことについては、排他的論理和だけを使い、両方とも最下位ビットから消費していくわけなので想像できると思います。
CRC 値を逆算すると言うことは、内部状態を右シフトではなく左シフトすると言うことになります。この時の最上位ビットが『0』になるようにすれば良いのではないか、と思いつきそうです (よね?)。
閃いた! 最終内部状態から逆に辿っていけば、望む CRC 血を持ったバイト列が求められそうだ!!
というわけで、さっそく取り掛かりましょう。
## ☀ CRC 値を逆算する!
用意する CRC モジュールは、おさらいで用いたものにしましょう。
CRC-16-0x8005 reflect-input,reflect-output initial_crc=0 xor_output=0
ビットを逆順にした生成多項式 Q も用意します。
Q = 0xA001 = [[1010 0000 0000 0001]] /* reversed polynomial */
例として、"1234567??" を crc16 したら 0xBB3D となるような、?? を求めることにしましょう。
1. 欲しい CRC 値の内部状態 W を求める。
W = 0xBB3D XOR xor_output = 0xBB3D
2. ?? の直前までの内部状態 S を求める。
S = crc16_state ("1234567") = 0x9D68 = [[1001 1101 0110 1000]]
3. 目的内部状態 W の最上位ビットが『1』であれば、W とビットを逆順にした生成多項式とで排他的論理和を求める。
『0』であれば何もしない。
W = [[1011 1011 0011 1101]] XOR Q = [[0001 1011 0011 1100]]
4. 目的内部状態 W を左シフトする。
W = [[0001 1011 0011 1100]] << 1 = [[0011 0110 0111 1000]]
5. (3) でビットを逆順にした生成多項式とで排他的論理和を求めた場合、目的内部状態 W と『0x01』とで排他的論理和を求める。
W = [[0011 0110 0111 1000]] XOR 0x01 = [[0011 0110 0111 1001]]
6. 内部状態 S から最上位ビット『1』を取り出して、目的内部状態 W の最下位ビットと排他的論理和を求める。
W = [[0011 0110 0111 1000]] XOR 0x01 = [[0011 0110 0111 1000]]
7. (3) に戻って、CRC のビット数分を繰り返す。
[[0011 0110 0111 1000]] /* S の MSB-0 (1) を処理した段階の W */
[[0110 1100 1111 0000]] /* S の MSB-1 (0) を処理した段階の W */
[[1101 1001 1110 0000]] /* S の MSB-2 (0) を処理した段階の W */
[[1111 0011 1100 0010]] /* S の MSB-3 (1) を処理した段階の W */
[[1010 0111 1000 0110]] /* S の MSB-4 (1) を処理した段階の W */
[[0000 1111 0000 1110]] /* S の MSB-5 (1) を処理した段階の W */
[[0001 1110 0001 1100]] /* S の MSB-6 (0) を処理した段階の W */
[[0011 1100 0011 1001]] /* S の MSB-7 (1) を処理した段階の W */
[[0111 1000 0111 0010]] /* S の MSB-8 (0) を処理した段階の W */
[[1111 0000 1110 0101]] /* S の MSB-9 (1) を処理した段階の W */
[[1010 0001 1100 1000]] /* S の MSB-10 (1) を処理した段階の W */
[[0000 0011 1001 0011]] /* S の MSB-11 (0) を処理した段階の W */
[[0000 0111 0010 0111]] /* S の MSB-12 (1) を処理した段階の W */
[[0000 1110 0100 1110]] /* S の MSB-13 (0) を処理した段階の W */
[[0001 1100 1001 1100]] /* S の MSB-14 (0) を処理した段階の W */
[[0011 1001 0011 1000]] /* S の MSB-15 (0) を処理した段階の W */
8. CRC 値を求める場合、下位バイトから入力することを考慮してバイト列を作る。この時のバイト列を R とする。
R = [W AND 0xFF, (W >> 8) AND 0xFF] = [0x38, 0x39] /* リトルエンディアンで格納 */
結果として、文字列にすると "89" を求めることが出来ました。
もしも、"1234??789" のように ?? の後ろにバイト列が続く場合はどうすれば良いのでしょうか。
内部状態と入力ビット列は、置き換えることが出来る (結果的に出来ることがわかった) と言うことを思い出して下さい。
つまり、"9" "8" "7" の順で 8 ビットづつ処理していき、続いて "1234" の CRC の内部状態である 16 ビットの値を処理していけば、"56" を求めることが出来ます。
## ☀ おわりに
今回取り上げたものは CRC-16 ですが、CRC-32 や CRC-64 でも考え方は変わりません。結果部分がそれぞれ 32 ビット、64 ビットになるだけです。
この例において損失した部分の修復をしたように見えますが、データの破損位置の検出をする必要があるし、1 バイト境界上に連続する 16 ビットまでの連続誤り一組にしか対応できません。
現実的にはハミング符号やリードソロモン符号など既存のものを用いた方が確実です。
CRC がデータの改ざん対策には全く意味を持たないと言われる理由を、垣間見ることが出来ましたでしょうか。
それでもデータの破損検出には必要十分な実力があるので、これからも幅広い使われ方をすることでしょう。
ここまでの内容がわかれば、CRC 値を好きにいじれるようになるわけですが、先にも書いたように悪さはしないように。
間違いや気が付いたところがあれば感想欄までお願いします。
それではこのへんで。Good Hack!!
