/* Attempt to find CRC-32 collisions for QVM files.
 *
 * Usage: qvmbrute.c DESIRED-CRC [OUTPUT-FILENAME [SUBDIRECTORY]]
 *
 * Copyright 2010 Simon McVittie <smcv@debian.org>
 * Copying and distribution of this file, with or without modification, are
 * permitted in any medium without royalty provided this notice is preserved.
 * This file is offered as-is, without any warranty.
 */

#include <arpa/inet.h>
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <zlib.h>

int
main (int argc, char **argv)
{
	u_int32_t i;
	unsigned char qvm[1024] = { 0 };
	u_int32_t target = strtoul (argv[1], NULL, 0);
	char *subdir = "";
	size_t fixed_len;
	u_int32_t crc;

	/* subdirectory to embed in the dummy file */
	if (argc > 3) {
		subdir = argv[3];
	}

	/* length of fixed part */
	fixed_len = strlen (subdir) + 8;

	/* The fixed part is "NTVE" + subdir + four reserved '\0' bytes
	 * (the first of which acts as '\0' termination for subdir).
	 *
	 * CCCC is replaced by the complement of the CRC-32 of the fixed part,
	 * yielding crc32 (fixed part + CCCC) = FFFFFFFF.
	 * XXXX is replaced by a brute-forced number such that
	 * crc32 (fixed part + CCCC + XXXX) is as desired. */
	snprintf ((char *) qvm, sizeof (qvm) - 1, "NTVE%s%c%c%c%cCCCCXXXX",
			subdir, 0, 0, 0, 0);

	/* calculate CRC of first fixed_len bytes */
	crc = crc32 (crc32 (0, NULL, 0), qvm, fixed_len);
	/* put the complement of it, in little-endian, in the next 4 */
	qvm[fixed_len + 0] = ~(crc & 0xFF);
	qvm[fixed_len + 1] = ~((crc >> 8) & 0xFF);
	qvm[fixed_len + 2] = ~((crc >> 16) & 0xFF);
	qvm[fixed_len + 3] = ~((crc >> 24) & 0xFF);
	/* by mathematical properties of CRC32, the CRC up to that point is
	 * 0xFFFFFFFF */
	crc = crc32 (crc32 (0, NULL, 0), qvm, fixed_len + 4);
	assert (crc == 0xFFFFFFFF);

	/* it's possible to do the last bit by mathematics, but brute force
	 * is fairly quick */
	printf ("searching for suffix that turns CRC32 from FFFFFFFF to 0x%.8x\n",
			target);

	for (i = 0; ; i++) {
		if (i % 0x10000 == 0) {
			printf ("%.8x\r", i);
		}

		if (crc32(0xFFFFFFFF, (const unsigned char *) &i, sizeof (i)) == target) {
			printf ("suffix found: 0x%.8x (in this machine's endianness)\n",
					i);
			break;
		}

		if (i == 0xFFFFFFFF) {
			printf ("collision not found within 4 bytes\n");
			return 1;
		}
	}

	/* check our working */
	memcpy (qvm + fixed_len + 4, &i, 4);
	crc = crc32 (crc32 (0, NULL, 0), qvm, fixed_len + 8);
	assert (crc == target);

	printf ("crc32(\"NTVE%s\" 00000000 %.8x %.8x) == 0x%.8x\n",
			subdir,
			ntohl(*((u_int32_t *) (qvm + fixed_len))),
			ntohl(*((u_int32_t *) (qvm + fixed_len + 4))),
			crc);

	if (argc > 2) {
		FILE *f;

		printf ("writing to file %s\n", argv[2]);
		f = fopen (argv[2], "w");

		if (f == NULL ||
				fwrite (qvm, fixed_len + 8, 1, f) < 1 ||
				fclose (f) < 0) {
			perror ("writing fake QVM");
			return 1;
		}
	}

	return 0;
}