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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
|
#include "../lib/lib.h"
#include "../lib/lib2.h"
#include "../lib/lib3.h"
#include "../lib/lib4.h"
#include "../lib/lib5.h"
#include "../lib/lib7.h"
/**
* MD-Hash implementation with AES-128. Outputs only 2^16 bits of the hash
**/
void md_hash_aes_128(char *input, int input_len, char *state, char *hash, int bytes, int print)
{
int blocksize = 16;
int i;
int pad_len;
char h[blocksize];
char key[blocksize];
char h_hex[32];
char *input_padded = __pkcs7_padding(input, input_len, 16, &pad_len);
// set the intial state
memset(h, 0, blocksize);
memcpy(h, state, bytes);
if(print == 1)
printf("input len is: %i, in blocks: %i\n", input_len, input_len/blocksize);
for(i=0;i<input_len/blocksize;i++) {
// only use the first bytes of the hash as state
// zero the others out
memset(key, 0, 16);
memcpy(key, h, bytes);
if(print == 1) {
hex_binary_to_string(h, h_hex, 16);
printf("%i: key is: 5s\n", i, h_hex);
memset(key, 0, 16);
memcpy(key, h, bytes);
}
aes_ecb(&input[i*blocksize], 16, h, key, blocksize, 1);
}
// output only bytes bytes
memcpy(hash, h, bytes);
free(input_padded);
}
void cascaded_md_hash_functions(char *input, int input_len, char *hash)
{
// F: cheap one: 2 bytes
// G: expensive: 16 bytes
char state[16];
memset(state, 0, 16);
md_hash_aes_128(input, input_len, state, hash, 2, 0);
md_hash_aes_128(input, input_len, state, &hash[2], 4, 0);
}
void add_one(unsigned char *s, int s_len)
{
if(s[s_len-1] == 255) {
s[s_len-1] = 0x00;
add_one(s, s_len-1);
}
else {
s[s_len-1] += 1;
}
}
int char_array_is_max(unsigned char *s, int s_len)
{
int i;
for(i=0;i<s_len;i++)
if(s[i] != 255)
return 0;
return 1;
}
int _2_collision_finding_machine(char *state, char *in1, char *in2, int bytes)
{
// find a collsion for the given state
char hash1[16];
char hash2[16];
char op_state[16];
memset(in1, 0, 16);
memset(in2, 0, 16);
do {
if(char_array_is_max(in2, 16) == 1) {
add_one(in1, 16);
memset(in2, 0, 16);
}
add_one(in2, 16);
memcpy(op_state, state, 16);
md_hash_aes_128(in1, 16, state, hash1, bytes, 0);
memcpy(op_state, state, 16);
md_hash_aes_128(in2, 16, state, hash2, bytes, 0);
} while(memcmp(hash1, hash2, bytes) != 0 && (memcmp(in1, in2, 16) != 0));
memcpy(state, hash1, bytes);
}
char **collisions = NULL;
unsigned int coll_numbers = 0;
void generate_collsions(char *prefix, int pref_len, char *coll1, char *coll2, int length)
{
if(length == 0) {
collisions[coll_numbers++] = prefix;
return;
}
char *print = malloc(pref_len+16);
memcpy(print, prefix, pref_len);
memcpy(&print[pref_len], coll1, 16);
generate_collsions(print, pref_len+16, &coll1[16], &coll2[16], length-1);
char *print2 = malloc(pref_len+16);
memcpy(print2, prefix, pref_len);
memcpy(&print2[pref_len], coll2, 16);
generate_collsions(print2, pref_len+16, &coll1[16], &coll2[16], length-1);
//free(print);
}
/**
* This functions computes 2^n collision for a MD-Hash function given
* an 2 collision finding machine
**/
int f(int n, int bytes)
{
int i;
char state[16];
char *block1 = malloc(n*16);
char *block2 = malloc(n*16);
char *hex_block = malloc(n*32);
memset(state, 0, 16);
printf("find collision blocks..\n");
for(i=0;i<n;i++) {
_2_collision_finding_machine(state, &block1[i*16], &block2[i*16], bytes);
}
printf("generating collsions out of the blocks\n");
generate_collsions("", 0, block1, block2, n);
free(block1);
free(block2);
}
void print_collisions(int coll_len, int bytes)
{
int i;
char *coll_hex = malloc(coll_len*2);
char hex_hash[32];
char hash[16];
char state[16];
for(i=0;i<coll_numbers;i++) {
printf("processing collision at %p\n", collisions[i]);
memset(state,0,16);
md_hash_aes_128(collisions[i], coll_len, state, hash, bytes, 0);
hex_binary_to_string(collisions[i], coll_hex, coll_len);
hex_binary_to_string(hash, hex_hash, bytes);
printf("data: %s:\t hash: %s\n", coll_hex, hex_hash);
}
// free(coll_hex);
}
/**
* find a collsion under both of the cascaded hash function
*
**/
void f_cascaded()
{
// generate 2^b/2 collsions with the cheap one
int i,j;
char state[16];
int found_collisions_expensive = 0;
int bytes_f = 2;
int bytes_g = 3;
int __collisions = 1;
int coll_controller = 12;
for(i=0;i<coll_controller;i++)
__collisions *= 2;
collisions = malloc(sizeof(char *)*__collisions);
printf("generate %i collisions\n", __collisions);
f(coll_controller, bytes_f);
char **hashes = malloc(sizeof(char *)*__collisions);
// check if one also collide in the not so cheap one
printf("check for collisions with the expensive hash function...\n");
for(i=0;i<coll_numbers;i++) {
hashes[i] = malloc(bytes_g);
memset(state, 0, 16);
md_hash_aes_128(collisions[i], coll_controller*16, state, hashes[i], bytes_g, 0);
for(j=0;j<i;j++) {
if(i != j && memcmp(hashes[j], hashes[i], bytes_g) == 0) {
char hex_hash[32];
char *coll_hex = malloc(coll_controller*32);
printf("collision in expensive hash function found: %i, %i ", i, j);
hex_binary_to_string(hashes[i], hex_hash, bytes_g);
printf("with hash: %s\n", hex_hash);
hex_binary_to_string(collisions[i], coll_hex, coll_controller*16);
printf("data %i: %s\n", i, coll_hex);
hex_binary_to_string(collisions[j], coll_hex, coll_controller*16);
printf("data %i: %s\n", j, coll_hex);
found_collisions_expensive++;
}
}
}
printf("found %i collisions in the expensive one out of %i collision candiate\n", found_collisions_expensive, coll_numbers);
}
int part1()
{
int i;
int n = 3;
int bytes = 2;
int __coll_numbers = 2;
for(i=1;i<n;i++)
__coll_numbers = __coll_numbers * 2;
printf("2^n is: %i\n", __coll_numbers);
collisions = malloc(sizeof(char *)*__coll_numbers);
f(n, bytes);
printf("found collision: %i\n", coll_numbers);
print_collisions(n*16, bytes);
}
int part2()
{
if(collisions != NULL)
free(collisions);
coll_numbers = 0;
f_cascaded();
}
int main()
{
srand(time(NULL));
part1();
printf("\n\npart2:\n\n");
part2();
}
|
