CRC32の逆演算Pythonコード

# はじめに

SECCON CTF 2019のCrypto3問目はCRC32チェックサムの問題でしたが, あれこれと試行錯誤しているうちに, 指定されたチェックサムを与えるバイト列の生成コード(いわゆる逆演算器のようなもの)ができました.
Writeupではありませんので悪しからず.

(2023/02/19 追記)
なんと2022 SECCON Finalでも出題されました. 多項式環で考えてみるver.も作成中です. 

# CRCとは
Cyclic Redundancy Check, 巡回冗長検査とも言われる誤り検出符号の一種です.
Python3では以下のようなコードになります.

```Python3:crc32.py
def crc32(data, crc):
    crc = 0xffffffff ^ crc
    for c in data:
        crc = crc ^ c
        for i in range(8):
            crc = (crc >> 1) ^ (0xedb88320 * (crc & 1))
    return 0xffffffff ^ crc


crc32(b'hello_world', 0)
# -> 4148080273
crc32(b'hello_world', 100)
# -> 389237547
```

ここではGalois体などの数学的な話はナシにしましょう.
ただ, CRC32は32次の生成多項式[^2]による剰余計算をしていることになるので, コード内に現れる変数`crc`は常に32bit(つまり`0xffffffff`)以下になります. この点だけ押さえておいてください. 

なお, このようなコードを書かなくとも, Python3には`binascii`モジュール内にCRC32チェックサムを計算する関数が存在します. 第2パラメータに初期値を設定しない場合は0とみなされます.

```Python3
import binascii

binascii.crc32(b'hello_world', 0)
# -> 4148080273
binascii.crc32(b'hello_world')
# -> 4148080273
binascii.crc32(b'hello_world', 100)
# -> 389237547
```

さて, CRC32は入力したbyte列の先頭から順に1byteずつ取り出して処理していることがfor文からわかるので, バイト列を分割/結合しても問題ありません.

```Python3
binascii.crc32(b'hello_world', 0)
# -> 4148080273

c = binascii.crc32(b'hello_', 0)
binascii.crc32(b'world', c)
# -> 4148080273
```

# チェックサムの巻き戻し

CRC32は単射ではないですが, ハッシュ関数のような不可逆性はありません. ここではCRC32の逆演算について考えていくことにします.

まず, 以下のように値を設定します. 当然c2は`'hello_world'`のチェックサムです.

```Python3
c0 = 0
c1 = binascii.crc32(b'hello_worl', c0)
# c1 = 1402191062
c2 = binascii.crc32(b'd', c1)
# c2 = 4148080273
```

以下, c2と文字`'d'`からc1を求めます.

まずは, 入力が1byteの時のCRC32の挙動について考えます.

```Python3:crc32_1byte.py
def crc32_1byte(byte, crc):
    crc = 0xffffffff ^ crc
    crc = crc ^ byte[0]
    for i in range(8):
        crc = (crc >> 1) ^ (0xedb88320 * (crc & 1))
    return 0xffffffff ^ crc
``` 

`crc32`関数のfor文をとっただけ[^1]ですので問題ないでしょう. 心配性の人は

```Python3
crc32_1byte(b'a', 123) == binascii.crc32(b'a', 123)
```
などと入力して確かめると良いでしょう.

さて, このfor文の中身は, crcの下1bitの値(つまり偶奇)によって場合分けされ, 
$$\begin{cases}
crc' \leftarrow crc >> 1 & ({\rm when}\ crc\ {\rm is\ even}) \\\\
crc' \leftarrow (crc >> 1)\ \oplus \ {\rm 0xedb88320} & ({\rm when}\ crc\ {\rm is\ odd})
\end{cases}$$
となっています. この復元は
$$\begin{cases}
{\rm (i)}\ \ crc \leftarrow crc' << 1 \\\\
{\rm (ii)}\ \ crc \leftarrow ((crc'\ \oplus \ {\rm 0xedb88320}) << 1) + 1
\end{cases}$$
のどちらかです. 2行目の$+1$は, crc'生成時に右にビットシフトして切り捨てられた1を補完してcrcを奇数にするためです. 
さて, 残念ながらこの条件だけからはcrc'が与えられた際にcrcが偶数か奇数かを判別することはできません.

ここで生きてくるのが, 前述した「crcは常に32bit以下になる」という条件です. つまり33bit以上になると即アウトです. 

1. crc'が31bit以下なら手法(i)をとる. 手法(ii)だと, crc'(31bit)と0xedb88320(32bit)とのXORを取った時点で32bitになり, 左にビットシフトすると33bitになってしまい不適.

2. crc'が32bitなら手法(ii)をとる. 手法(i)は明らかに不適で, 手法(ii)だとcrc'(32bit)と0xedb88320(32bit)とのXORで31bit以下になり, 左にビットシフトしても高々32bitなので問題なし. 

以上を踏まえて, crc'が32bitより大きいかどうかで場合分けしつつ, 巻き戻しのコードを書くと以下のようになります.

```Python3:crc32_1byte_rewind.py
def crc32_1byte_rewind(byte, crc):
    crc = 0xffffffff ^ crc
    for i in range(8):
        # 手法(i)
        if crc <= 0x7fffffff:
            crc = crc << 1
        # 手法(ii)
        else:
            crc = ((crc ^ 0xedb88320) << 1) + 1
    crc = crc ^ byte[0]
    return 0xffffffff ^ crc

c2 = 4148080273
crc32_1byte_rewind(b'd', c2)
# -> 1402191062
```

これでc1がきちんと得られました. あとは一般のバイト列入力に拡張します.

```Python3:crc32_rewind.py
def crc32_rewind(data, crc):
    crc = 0xffffffff ^ crc
    for c in data[::-1]:
        for i in range(8):
            if crc <= 0x7fffffff:
                crc = crc << 1
            else:
                crc = ((crc ^ 0xedb88320) << 1) + 1
        crc = crc ^ c
    return 0xffffffff ^ crc

c2 = 4148080273
crc32_rewind(b'hello_world', c2)
# -> 0
```
これにて, 任意の入力バイト列`data`, CRC初期値`start`に対して

```Python3
end = binascii.crc32(data, start)
```
とすると

```Python3
start = crc32_rewind(data, end)
```
で巻き戻し可能になりました.

# 特定のチェックサムを与えるバイト列の生成
以下, CRC初期値は0とし, チェックサムは全て16進数で表記します.

先ほども述べた通り, CRCは単射ではないので, 2つのバイト列のチェックサムが等しい可能性もゼロではありません.
さて, `'hello_world'`のCRC32チェックサムは0xf73eae91( = 4148080273)でした. 
では, `'123????'`のCRC32チェックサムが0xf73eae1になるような`????`は何か, というのがこの記事のメイントピックになります. 
32bit(約42億)の総当たりをすれば求まりますが, エレガントとは言えません.
ここでは違うアプローチをとってみます. 

# CRC32のマジックナンバー
`'hello_world'`のチェックサム0xf73eae91を2桁ごとに区切り, 4つの1バイト文字`\xf7`, `\x3e`, `\xae`, `\x91`を生成します.
これらを逆順にして`'hello_world'`の末尾にくっつけた`'hello_world\x91\xae\x3e\xf7'`のチェックサムを考えます.

```Python3
hex(binascii.crc32(b'hello_world\x91\xae\x3e\xf7'))
# -> '0x2144df1c'
```

違うバイト列でも試してみます.

```Python3
hex(binascii.crc32(b'123'))
# -> '0x884863d2'
hex(binascii.crc32(b'123\xd2\x63\x48\x88'))
# -> '0x2144df1c'
```

やはり同じ結果が得られました. 詳しい説明は割愛しますが, これは偶然ではなく必ず0x2144df1cとなります. この数字をCRC32のマジックナンバーと言います. 


# ????の特定
さて, 本題に戻ります. まずは結論から先に記します.

step 1.
先ほどと同様に`'123'`のチェックサム0x884863d2を2桁ごとに区切り, 逆順で結合したバイト列`'\xd2\x63\x48\x88'`を生成します.

```Python3:
import codecs

c = binascii.crc32(b'123')
# c = 0x884863d2
codecs.decode(('%x' % c), 'hex_codec')[::-1]
# -> b'\xd2cH\x88'
```
一部, ASCIIコードの関係により`'\x63\x48'`が`'cH'`に変換されていますが問題ありません.

step 2.
`crc32_rewind`を用いて, バイト列`'\xd2\x63\x48\x88'`に対するチェックサムが0xf73eae91(`'hello_world'`のチェックサム)となるようなCRCの値を求めます.

```Python3:
hex(crc32_rewind(b'\xd2\x63\x48\x88', 0xf73eae91))
# -> '0xcd3a946'
# つまり, binascii.crc32(b'\xd2\x63\x48\x88', 0xcd3a946) == binascii.crc32(b'hello_world')
```
step 3.
これにより得られた0xcd3a946を2桁ごとに区切り(7桁なので, 最上位の桁にはゼロを補完しています), 逆順で結合したバイト列`'\x46\xa9\xd3\x0c'`を生成します.

```Python3:
codecs.decode(('0' + '%x' % 0xcd3a946 ), 'hex_codec')[::-1]
# -> b'F\xa9\xd3\x0c'
```

ここも同様にASCIIコードによって`'\x46'`が`'F'`になっていますが大丈夫です.
さて, これにより得られた`'\x46\xa9\xd3\x0c'`が????の正体です. 実際に確かめてみましょう.

```Python3:
binascii.crc32(b'123\x46\xa9\xd3\x0c') == binascii.crc32(b'hello_world')
# -> True
```

一般化すると以下のコードのようになります. 
`'hello_world'`に対応する変数を`genuine`, `'123'`に対応する変数を`fake`とおきます. 
また, ここまではCRCの初期値を0としましたが, 任意の値に対応できるよう引数`crc_init`を導入しました.

```Python3:crc32_rev.py
import codecs

def crc32_rev(genuine, fake, crc_init):
    # step 1.
    genuine_crc = binascii.crc32(genuine, crc_init)
    fake_crc = binascii.crc32(fake, crc_init)
    # 16進数で8桁未満になった場合にゼロでパディング
    crc_pad = 8 - len('%x' % fake_crc)
    byte = codecs.decode('0' * crc_pad + ('%x' % fake_crc), 'hex_codec')[::-1]
    # step 2.
    ans_rev = crc32_rewind(byte, genuine_crc)
    # step 3.
    ans_pad = 8 - len('%x' % ans_rev)
    ans = codecs.decode(('0' * ans_pad + '%x' % ans_rev), 'hex_codec')[::-1]
    print('binascii.crc32({}, {}) == binascii.crc32({}, {})'.format(genuine, crc_init, (fake + ans), crc_init))
    return ans

crc32_rev(b'hello_world', b'123', 0)
# -> binascii.crc32(b'hello_world', 0) == binascii.crc32(b'123F\xa9\xd3\x0c', 0)
# -> b'F\xa9\xd3\x0c'
```

# 簡単に仕組みを解説
それぞれの繋がりを順に見ていきましょう. 

step 2.における`'hello_world'`のチェックサム0xf73eae91と0xcd3a946は, バイト列`'\xd2\x63\x48\x88'`を介して

```Python3
binascii.crc32(b'\xd2\x63\x48\x88', 0xcd3a946) == 0xf73eae91
crc32_rewind(b'\xd2\x63\x48\x88', 0xf73eae91) == 0xcd3a946
```

の繋がりがあります. 次に, 0xcd3a946とマジックナンバー0x2144df1cには

```Python3
binascii.crc32(b'\x46\xa9\xd3\x0c', 0xcd3a946) == 0x2144df1c
crc32_rewind(b'\x46\xa9\xd3\x0c', 0x2144df1c) == 0xcd3a946
```
の繋がりが, またマジックナンバー0x2144df1cと`'123'`のチェックサム0x884863d2には

```Python3
binascii.crc32(b'\xd2\x63\x48\x88', 0x884863d2) == 0x2144df1c
crc32_rewind(b'\xd2\x63\x48\x88', 0x2144df1c) == 0x884863d2
```

の繋がりがあります. これら3ステップを組み合わせることで, `'hello_world'`のチェックサム0xf73eae91と`'123'`のチェックサム0x884863d2との, `????`を介した

```Python3
binascii.crc32(b'????', 0x884863d2) == 0xf73eae91
crc32_rewind(b'????', 0xf73eae91) == 0x884863d2
```
という橋渡しを実現していることになります.
ではなぜ, 途中に出てくる0xcd3a946という数がそのまま????になるか, というのは, マジックナンバーが必ず定数になる事とも関わってくるのでまた別の機会に. 

# 余談
CRC32という技術はzipファイルにも使われています.
実際に, マジックナンバー0x2144df1cをビット反転させた(0xffffffffとのXORをとった)値0xdebb20e3が[zipファイルの仕様書](https://pkware.cachefly.net/webdocs/casestudies/APPNOTE.TXT)の4.4.7節に書かれていることも確認できます.
なお, CRC32に関する情報はzipファイルヘッダの15~18バイト目に書かれます. 興味がある人はhexdumpで覗いてみても面白いと思います. 


# 参考記事
[こちら](https://qiita.com/dearblue/items/669e2ce2fae57baf1e90)を元に作成させて頂きました. 


[^1]: 厳密には, `crc32`のfor文内の変数`c`はint型なので, `crc32_1byte`の方は`byte`をint型に変換するために`byte[0]`と変更しています.
[^2]: コード内の`0xEDB88320`が生成多項式に相当します.