💥

SHA-1衝突検出ライブラリを使ってみた

2021/09/23に公開

Security

hash

sha1

tech

以前書いた記事GitのオブジェクトID衝突時の挙動に頂いたコメントで、GitにSHA-1衝突攻撃検出のライブラリsha1collisiondetectionが組み込まれていることを知った。

OpenSSLと類似のインタフェースで使えるのを実際に試してみた。

テストデータ

ライブラリのソースをcloneしてくると、テストデータも含まれている。

~$ git clone https://github.com/cr-marcstevens/sha1collisiondetection.git
Cloning into 'sha1collisiondetection'...
remote: Enumerating objects: 892, done.
remote: Counting objects: 100% (3/3), done.
remote: Compressing objects: 100% (3/3), done.
remote: Total 892 (delta 0), reused 1 (delta 0), pack-reused 889
Receiving objects: 100% (892/892), 610.37 KiB | 3.07 MiB/s, done.
Resolving deltas: 100% (567/567), done.
~$ cd sha1collisiondetection/
~/sha1collisiondetection$ sha1sum test/*
a56374e1cf4c3746499bc7c0acb39498ad2ee185  test/sha1_reducedsha_coll.bin
8ac60ba76f1999a1ab70223f225aefdc78d4ddc0  test/sha-mbles-1.bin
8ac60ba76f1999a1ab70223f225aefdc78d4ddc0  test/sha-mbles-2.bin
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  test/shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  test/shattered-2.pdf

sha1sumの出力を見るとsha-mbles-1.binとsha-mbles-2.bin、shattered-1.pdfとshattered-2.pdfのSHA-1の値は一致しているが、sha256sumするとわかるように内容が異なるファイルである。

~/sha1collisiondetection$ sha256sum test/*
f238052907fa3ce28e550806a61f30a73b3394185e63c290439053bef45b3216  test/sha1_reducedsha_coll.bin
3ead211681cec93d265c8ac123dd062e105408cebf82fa6e2b126f4f40bcb88c  test/sha-mbles-1.bin
208feafe1c6a95c73f662514ac48761f25e1f3b74922521a98d9ce287f4a2197  test/sha-mbles-2.bin
2bb787a73e37352f92383abe7e2902936d1059ad9f1ba6daaa9c1e58ee6970d0  test/shattered-1.pdf
d4488775d29bdef7993367d541064dbdda50d383f89f0aa13a6ff2e0894ba5ff  test/shattered-2.pdf

OpenSSL

sha1collisiondetectionは、よく使われているOpenSSLと類似のインタフェースで使える。
比較のため、まずはOpenSSLを使ってSHA-1を計算してみよう。

sha1.c

#include <stdio.h>
#include <openssl/sha.h>

#define BUFSIZE 65536

int main(int argc, char *argv[])
{
	if (argc != 2) {
		fprintf(stderr, "usage: %s file\n", argv[0]);
		return 1;
	}
	FILE *fd = fopen(argv[1], "r");
	if (fd == NULL) {
		fprintf(stderr, "error: cannot open %s\n", argv[1]);
		return 1;
	}
	SHA_CTX ctx;
	int ret = SHA1_Init(&ctx);
	if (ret != 1) {
		fprintf(stderr, "error: SHA1_Init failed %d\n", ret);
		return 1;
	}
	while (1) {
		char buffer[BUFSIZE];
		size_t size = fread(buffer, 1, BUFSIZE, fd);

		ret = SHA1_Update(&ctx, buffer, size);
		if (ret != 1) {
			fprintf(stderr, "error: SHA1_Update failed %d\n", ret);
			return 1;
		}

		if (size < BUFSIZE) {
			break;
		}
	}
	fclose(fd);
	unsigned char sha1[20];
	ret = SHA1_Final(sha1, &ctx);
	if (ret != 1) {
		fprintf(stderr, "error: SHA1_Final failed %d\n", ret);
		return 1;
	}
	for (int i = 0; i < sizeof(sha1); i++) {
		printf("%02x", sha1[i]);
	}
	printf(" %s\n", argv[1]);
	return 0;
}

これをビルド、実行すると、sha1sumと同じ結果を確認できる。

~/sha1collisiondetection$ gcc sha1.c -o sha1 -lcrypto
~/sha1collisiondetection$ for f in test/*; do ./sha1 $f; done
a56374e1cf4c3746499bc7c0acb39498ad2ee185 test/sha1_reducedsha_coll.bin
8ac60ba76f1999a1ab70223f225aefdc78d4ddc0 test/sha-mbles-1.bin
8ac60ba76f1999a1ab70223f225aefdc78d4ddc0 test/sha-mbles-2.bin
38762cf7f55934b34d179ae6a4c80cadccbb7f0a test/shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a test/shattered-2.pdf

sha1collisiondetection

OpenSSLとのインタフェースの違いは、

Init, Update の戻り値がない
デフォルトでは衝突検出時にSHA-1を補正したロジックでハッシュ値を計算する
- SHA1DCSetSafeHash(ctx, 0) で無効化すればSHA-1ハッシュを計算する
Final の戻り値で衝突検出の有無がわかる(衝突検出したら0以外の値が返る)

OpenSSLを使ったコードを書き換えると以下のようになる。

sha1dc.c

#include <stdio.h>
#include "sha1.h"

#define BUFSIZE 65536

int main(int argc, char *argv[])
{
	if (argc != 2) {
		fprintf(stderr, "usage: %s file\n", argv[0]);
		return 1;
	}
	FILE *fd = fopen(argv[1], "r");
	if (fd == NULL) {
		fprintf(stderr, "error: cannot open %s\n", argv[1]);
		return 1;
	}
	SHA1_CTX ctx;
	SHA1DCInit(&ctx);
	SHA1DCSetSafeHash(&ctx, 0);
	while (1) {
		char buffer[BUFSIZE];
		size_t size = fread(buffer, 1, BUFSIZE, fd);

		SHA1DCUpdate(&ctx, buffer, size);

		if (size < BUFSIZE) {
			break;
		}
	}
	fclose(fd);
	unsigned char sha1[20];
	int ret = SHA1DCFinal(sha1, &ctx);
	if (ret != 0) {
		fprintf(stderr, "warning: collision detected\n");
	}
	for (int i = 0; i < sizeof(sha1); i++) {
		printf("%02x", sha1[i]);
	}
	printf(" %s\n", argv[1]);
	return ret;
}

ビルド、実行すると、SHA-1を正しく計算しつつ、sha-mbles-[12].bin、shattered-[12].pdf で衝突検出できている。

~/sha1collisiondetection$ gcc lib/{ubc_check,sha1}.c sha1dc.c -o sha1dc -Ilib
~/sha1collisiondetection$ for f in test/*; do ./sha1dc $f; done
a56374e1cf4c3746499bc7c0acb39498ad2ee185 test/sha1_reducedsha_coll.bin
warning: collision detected
8ac60ba76f1999a1ab70223f225aefdc78d4ddc0 test/sha-mbles-1.bin
warning: collision detected
8ac60ba76f1999a1ab70223f225aefdc78d4ddc0 test/sha-mbles-2.bin
warning: collision detected
38762cf7f55934b34d179ae6a4c80cadccbb7f0a test/shattered-1.pdf
warning: collision detected
38762cf7f55934b34d179ae6a4c80cadccbb7f0a test/shattered-2.pdf

sha1_reducedsha_coll.binでは衝突検出していないが、以下のようにすればこれも検出できる^[1]

--- sha1dc.c	2021-09-23 01:29:17.770385274 +0000
+++ sha1dc_partialcoll.c	2021-09-23 01:35:11.459153914 +0000
@@ -17,6 +17,7 @@
 	SHA1_CTX ctx;
 	SHA1DCInit(&ctx);
 	SHA1DCSetSafeHash(&ctx, 0);
+	SHA1DCSetDetectReducedRoundCollision(&ctx, 1);
 	while (1) {
 		char buffer[BUFSIZE];
 		size_t size = fread(buffer, 1, BUFSIZE, fd);

ビルド、実行すると、sha1_reducedsha_coll.binでも衝突検出する

~/sha1collisiondetection$ gcc lib/{ubc_check,sha1}.c sha1dc_partialcoll.c -o sha1dc_partialcoll -Ilib
~/sha1collisiondetection$ for f in test/*; do ./sha1dc_partialcoll $f; done
warning: collision detected
a56374e1cf4c3746499bc7c0acb39498ad2ee185 test/sha1_reducedsha_coll.bin
warning: collision detected
8ac60ba76f1999a1ab70223f225aefdc78d4ddc0 test/sha-mbles-1.bin
warning: collision detected
8ac60ba76f1999a1ab70223f225aefdc78d4ddc0 test/sha-mbles-2.bin
warning: collision detected
38762cf7f55934b34d179ae6a4c80cadccbb7f0a test/shattered-1.pdf
warning: collision detected
38762cf7f55934b34d179ae6a4c80cadccbb7f0a test/shattered-2.pdf

脚注

こちらはフルバージョンのSHA-1(80ラウンド)ではなく、ラウンド数を減らしたものでの衝突を検出するロジック。なのでGitでは有効にされてない。 ↩︎

テストデータ

OpenSSL

sha1collisiondetection

Discussion