1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
/* 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 <time.h>
#include <zlib.h>
int
main (int argc, char **argv)
{
struct timespec start = { 0 };
struct timespec end = { 0 };
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;
double delta;
clock_gettime (CLOCK_MONOTONIC, &start);
/* 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;
}
}
clock_gettime (CLOCK_MONOTONIC, &end);
delta = end.tv_sec - start.tv_sec + (end.tv_nsec - start.tv_nsec) / 1e9;
printf ("QVM file %s generated in %.2f seconds\n", argv[2], delta);
return 0;
}
|
