LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@mikecat_mixc

CRC32を逆算する

Posted at

今回の目的

  • CRC32の計算における「更新後の状態」と「更新に用いたバイトの値」から「更新前の状態」を求める
  • CRC32の計算における「更新前の状態」と「更新後の状態」から「更新に用いたバイト(列)」を求める

CRC32の計算方法 (復習)

PNGで使うCRC32を計算する #crc - Qiita

CRC32は、以下の方法で求めることができる。

  1. 状態を 0xFFFFFFFF で初期化する
  2. 入力の各バイトについて、以下のようにして状態を更新する
    1. 注目しているバイトの値を、状態の下位8ビットにXORする
    2. 以下を8回繰り返す
      1. 状態を1ビット右論理シフトする
      2. シフトによって押し出されたビットが 1 ならば、状態にマジックナンバー 0xEDB88320 をXORする (0 なら何もしない)
  3. 状態の各ビットを反転 (NOT) する

以下は、各バイトによる状態の更新のイメージである。

crc32-byte-step-20250209.excalidraw.png

更新前の状態を求める

通常のCRC32の計算では、「更新前の状態」と「バイトの値」から「更新後の状態」を求める。
今回は、これとは逆に、「更新後の状態」と「バイトの値」から「更新前の状態」を求める。

そのために、まずはシフトとマジックナンバーのXORの処理を逆回しする。
ここで行うシフトは右論理シフトなので、シフト後の最上位ビットは必ず 0 になる。
そして、XORするマジックナンバーの最上位ビットは 1 である。
よって、以下のことがわかる。

  • 処理後の状態の最上位ビットが 1 の場合、マジックナンバーをXORしたので、シフトによって押し出されたビットは 1 である
  • 処理後の状態の最上位ビットが 0 の場合、マジックナンバーをXORしていないので、シフトによって押し出されたビットは 0 である

シフトとマジックナンバーのXORの処理を逆回ししたら、最後に「更新に用いたバイトの値」を下位8ビットにXORすることで、「更新前の状態」を得ることができる。

#include <stdio.h>
#include <string.h>
#include <inttypes.h>

uint32_t crc32_inv(uint32_t status_after, uint8_t byte_value) {
	static const uint32_t MAGIC = UINT32_C(0xEDB88320);
	uint32_t status = status_after;

	// シフトとマジックナンバーのXORの処理を逆回しする
	for (int i = 0; i < 8; i++) {
		uint32_t msb = status & UINT32_C(0x80000000);
		if (msb) {
			status ^= MAGIC;
			status <<= 1;
			status |= 1;
		} else {
			status <<= 1;
		}
	}

	// 更新に用いたバイトの値をXORする
	status ^= byte_value;

	return status;
}

int main(void) {
	const char *data = "IEND";
	uint32_t status = UINT32_C(0xAE426082);
	printf("CRC32: 0x%08" PRIx32 "\n", status);
	status = ~status; // 最後に行ったビット反転を打ち消す
	for (int i = (int)strlen(data) - 1; i >= 0; i--) {
		printf("after data[%d] = 0x%02x : 0x%08" PRIx32 "\n", i, data[i], status);
		status = crc32_inv(status, data[i]);
	}
	printf("initial value: 0x%08" PRIx32 "\n", status);
	return 0;
}

このプログラムを実行すると、以下の出力が得られた。

CRC32: 0xae426082
after data[3] = 0x44 : 0x51bd9f7d
after data[2] = 0x4e : 0x639f4775
after data[1] = 0x45 : 0x992bac53
after data[0] = 0x49 : 0x22fde946
initial value: 0xffffffff

IEND のCRC32値から、CRC32の計算に用いる初期値の 0xffffffff を逆算できていることがわかる。

更新に用いたバイト(列)を求める

「更新前の状態を求める」では、シフトとマジックナンバーのXORの処理を逆回しした後、その結果に「更新に用いたバイトの値」をXORすることで「更新前の状態」を求めた。
逆に、逆回しの結果に「更新前の状態」をXORすると、「更新に用いたバイトの値」がわかるはずである。
ただし、「更新前の状態」をXORした結果の上位24ビットが0でない場合、エラー (条件を満たすバイトの値は無い) である。

さらに、これまでは1バイトずつ状態の更新を行っていたが、4バイトまで一気にXORし、バイト数分のシフトとXORをまとめて行うことでも、CRC32の計算を行うことができる。
逆に、逆回しの処理回数を変えることで、更新に用いた4バイトまでのバイト列を求めることができる。

#include <stdio.h>
#include <inttypes.h>

// 成功時1、失敗時0を返す
int crc32_bytes(uint8_t bytes_out[], int num_bytes, uint32_t status_before, uint32_t status_after) {
	static const uint32_t MAGIC = UINT32_C(0xEDB88320);
	uint32_t status = status_after;
	if (num_bytes < 0 || 4 < num_bytes) return 0;
	if (num_bytes == 0) return status_before == status_after;

	// シフトとマジックナンバーのXORの処理を逆回しする
	for (int i = 0; i < 8 * num_bytes; i++) {
		uint32_t msb = status & UINT32_C(0x80000000);
		if (msb) {
			status ^= MAGIC;
			status <<= 1;
			status |= 1;
		} else {
			status <<= 1;
		}
	}

	// 更新前の状態をXORする
	status ^= status_before;

	// 上位が0になっていることを確認する
	if (num_bytes < 4 && (status & (UINT32_C(0xFFFFFFFF) << 8 * num_bytes))) return 0;

	// バイト列を取り出す
	for (int i = 0; i < num_bytes; i++) {
		bytes_out[i] = status >> 8 * i;
	}

	return 1;
}

void test(uint32_t status_before, uint32_t status_after) {
	printf("0x%08" PRIx32 " -> 0x%08" PRIx32 "\n", status_before, status_after);
	for (int size = 1; size <= 4; size++) {
		uint8_t data[4];
		if (crc32_bytes(data, size, status_before, status_after)) {
			for (int i = 0; i < size; i++) {
				if (i > 0) putchar(' ');
				printf("%02x", (unsigned int)data[i]);
			}
			putchar('\n');
		}
	}
}

int main(void) {
	test(UINT32_C(0x992BAC53), UINT32_C(0x639F4775));
	test(UINT32_C(0x992BAC53), UINT32_C(0x51BD9F7D));
	test(UINT32_C(0x22FDE946), UINT32_C(0x51BD9F7D));
	test(UINT32_C(0xFFFFFFFF), UINT32_C(0x51BD9F7D));
	return 0;
}

このプログラムを実行すると、以下の出力が得られた。

0x992bac53 -> 0x639f4775
4e
8a 6a fb 27
0x992bac53 -> 0x51bd9f7d
4e 44
e5 16 9a 22
0x22fde946 -> 0x51bd9f7d
45 4e 44
f0 53 4c 99
0xffffffff -> 0x51bd9f7d
49 45 4e 44

正解のデータが4バイトの場合、今回はその4バイトの値のみが得られた。
しかし、データによっては、4バイト未満の値が誤検知される可能性がある。

正解のデータが4バイト未満の場合、正解のデータに加え、適当な4バイトの値も得られた。
これは、逆にこの4バイトの値が正解の場合、4バイト未満の値の誤検知が発生するということである。

求めたいデータのバイト数がわかっている場合、最初からそのバイト数のみで計算を行うのがよいだろう。

正解のデータは4バイトだと仮定したとき、0となるべき上位のビット数は0なので、必ず条件を満たす何らかのデータが得られる。

テーブルを用いて処理を行う

シフトとマジックナンバーのXORの処理を1バイト分逆回しする際、条件分岐に関係するのは入力の上位8ビットだけなので、CRC32の計算と同様にテーブルを用いて処理を行うことができる。

#include <stdio.h>
#include <string.h>
#include <inttypes.h>

uint32_t crc32_inv_shift(uint32_t status_after) {
	static uint32_t table[256], table_ready = 0;
	if (!table_ready) {
		static const uint32_t MAGIC = UINT32_C(0xEDB88320);
		for (int b = 0; b < 256; b++) {
			uint32_t status = (uint32_t)b << 24;
			for (int i = 0; i < 8; i++) {
				uint32_t msb = status & UINT32_C(0x80000000);
				if (msb) {
					status ^= MAGIC;
					status <<= 1;
					status |= 1;
				} else {
					status <<= 1;
				}
			}
			table[b] = status;
		}
		table_ready = 1;
	}
	return table[status_after >> 24] ^ (status_after << 8);
}

uint32_t crc32_inv(uint32_t status_after, uint8_t byte_value) {
	return crc32_inv_shift(status_after) ^ byte_value;
}

// 成功時1、失敗時0を返す
int crc32_bytes(uint8_t bytes_out[], int num_bytes, uint32_t status_before, uint32_t status_after) {
	uint32_t status = status_after;
	if (num_bytes < 0 || 4 < num_bytes) return 0;
	if (num_bytes == 0) return status_before == status_after;

	// シフトとマジックナンバーのXORの処理を逆回しする
	for (int i = 0; i < num_bytes; i++) {
		status = crc32_inv_shift(status);
	}

	// 更新前の状態をXORする
	status ^= status_before;

	// 上位が0になっていることを確認する
	if (num_bytes < 4 && (status & (UINT32_C(0xFFFFFFFF) << 8 * num_bytes))) return 0;

	// バイト列を取り出す
	for (int i = 0; i < num_bytes; i++) {
		bytes_out[i] = status >> 8 * i;
	}

	return 1;
}

void test(uint32_t status_before, uint32_t status_after) {
	printf("0x%08" PRIx32 " -> 0x%08" PRIx32 "\n", status_before, status_after);
	for (int size = 1; size <= 4; size++) {
		uint8_t data[4];
		if (crc32_bytes(data, size, status_before, status_after)) {
			for (int i = 0; i < size; i++) {
				if (i > 0) putchar(' ');
				printf("%02x", (unsigned int)data[i]);
			}
			putchar('\n');
		}
	}
}

int main(void) {
	const char *data = "IEND";
	uint32_t status = UINT32_C(0xAE426082);
	printf("CRC32: 0x%08" PRIx32 "\n", status);
	status = ~status; // 最後に行ったビット反転を打ち消す
	for (int i = (int)strlen(data) - 1; i >= 0; i--) {
		printf("after data[%d] = 0x%02x : 0x%08" PRIx32 "\n", i, data[i], status);
		status = crc32_inv(status, data[i]);
	}
	printf("initial value: 0x%08" PRIx32 "\n", status);

	putchar('\n');

	test(UINT32_C(0x992BAC53), UINT32_C(0x639F4775));
	test(UINT32_C(0x992BAC53), UINT32_C(0x51BD9F7D));
	test(UINT32_C(0x22FDE946), UINT32_C(0x51BD9F7D));
	test(UINT32_C(0xFFFFFFFF), UINT32_C(0x51BD9F7D));
	return 0;
}

このプログラムを実行すると、以下の出力が得られた。

CRC32: 0xae426082
after data[3] = 0x44 : 0x51bd9f7d
after data[2] = 0x4e : 0x639f4775
after data[1] = 0x45 : 0x992bac53
after data[0] = 0x49 : 0x22fde946
initial value: 0xffffffff

0x992bac53 -> 0x639f4775
4e
8a 6a fb 27
0x992bac53 -> 0x51bd9f7d
4e 44
e5 16 9a 22
0x22fde946 -> 0x51bd9f7d
45 4e 44
f0 53 4c 99
0xffffffff -> 0x51bd9f7d
49 45 4e 44

テーブルを使わないプログラムと同様の出力が得られていることがわかる。

まとめ

CRC32の計算はシフトとXORを用いて行うので、これらの操作を打ち消す操作を行うことで、もとの状態やバイト列を求めることができる。

ちなみに

通常の計算処理を行うことで、任意の4バイトのバイト列からそのCRC32値を求めることができる。

今回の逆算処理を行うことで、任意のCRC32値からそれに対応する4バイトのバイト列を求めることができる。

CRC32値は32ビットなので、4バイトのバイト列とちょうど同じ個数存在する。

もし仮にある異なる4バイトのバイト列2個のCRC32値が同じになるとすると、その分4バイトのバイト列に対応するCRC32値が少なくなり、4バイトのバイト列に対応しないCRC32値が存在することになる。
しかし、任意のCRC32値からそれに対応する4バイトのバイト列を求めることができるので、これは矛盾である。

よって、異なる4バイトのバイト列のCRC32値は必ず違うものになる。
同様に、異なるCRC32値に対応する4バイトのバイト列は必ず違うものになる。

ゆえに、4バイトのバイト列とCRC32値は1対1に対応する。

1
0
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
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?