LoginSignup
11
7

More than 1 year has passed since last update.

@taiyaki8926

CRC32の逆演算Pythonコード

Last updated at Posted at 2019-10-22

はじめに

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

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

CRCとは

Cyclic Redundancy Check, 巡回冗長検査とも言われる誤り検出符号の一種です.
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次の生成多項式1による剰余計算をしていることになるので, コード内に現れる変数crcは常に32bit(つまり0xffffffff)以下になります. この点だけ押さえておいてください.

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

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文からわかるので, バイト列を分割/結合しても問題ありません.

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

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

チェックサムの巻き戻し

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

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

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

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

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

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文をとっただけ2ですので問題ないでしょう. 心配性の人は

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より大きいかどうかで場合分けしつつ, 巻き戻しのコードを書くと以下のようになります.

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がきちんと得られました. あとは一般のバイト列入力に拡張します.

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に対して

end = binascii.crc32(data, start)

とすると

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'のチェックサムを考えます.

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

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

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'を生成します.

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の値を求めます.

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'を生成します.

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

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

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

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

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'を介して

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

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

binascii.crc32(b'\x46\xa9\xd3\x0c', 0xcd3a946) == 0x2144df1c
crc32_rewind(b'\x46\xa9\xd3\x0c', 0x2144df1c) == 0xcd3a946

の繋がりが, またマジックナンバー0x2144df1cと'123'のチェックサム0x884863d2には

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

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

binascii.crc32(b'????', 0x884863d2) == 0xf73eae91
crc32_rewind(b'????', 0xf73eae91) == 0x884863d2

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

余談

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

参考記事

こちらを元に作成させて頂きました.

  1. コード内の0xEDB88320が生成多項式に相当します. ↩

  2. 厳密には, crc32のfor文内の変数cはint型なので, crc32_1byteの方はbyteをint型に変換するためにbyte[0]と変更しています. ↩

11
7
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
11
7