1 module dcrypt.digests.blake;
2 
3 /// Implementation of the BLAKE SHA-3 proposal.
4 /// https://131002.net/blake/blake.pdf
5 
6 public import dcrypt.digest;
7 import dcrypt.bitmanip: ror, fromBigEndian, toBigEndian;
8 import dcrypt.util: wipe;
9 import std.conv: text;
10 
11 alias Blake!224 Blake224;
12 alias Blake!256 Blake256;
13 alias Blake!384 Blake384;
14 alias Blake!512 Blake512;
15 
16 alias WrapperDigest!Blake224 Blake224Digest;
17 alias WrapperDigest!Blake256 Blake256Digest;
18 alias WrapperDigest!Blake384 Blake384Digest;
19 alias WrapperDigest!Blake512 Blake512Digest;
20 
21 static assert(isDigest!Blake224, "Blake224 does not fullfill requirements of isDigest.");
22 static assert(isDigest!Blake256, "Blake256 does not fullfill requirements of isDigest.");
23 static assert(isDigest!Blake384, "Blake384 does not fullfill requirements of isDigest.");
24 static assert(isDigest!Blake512, "Blake512 does not fullfill requirements of isDigest.");
25 
26 @safe
27 struct Blake(uint bitLength)
28 if(bitLength == 224 || bitLength == 256 || bitLength == 384 || bitLength == 512) {
29 
30 	enum digestLength = bitLength / 8;
31 	enum name = text("Blake", bitLength);
32 	enum blockSize = 0;
33 
34 	private {
35 
36 		static if(bitLength <= 256) {
37 			alias uint Word;
38 		} else {
39 			alias ulong Word;
40 		}
41 
42 		// Set IV.
43 		static if(bitLength == 224) {
44 
45 			static immutable Word[8] iv = [
46 				0xC1059ED8, 0x367CD507, 0x3070DD17, 0xF70E5939,
47 				0xFFC00B31, 0x68581511, 0x64F98FA7, 0xBEFA4FA4
48 			];
49 
50 		} else static if(bitLength == 256) {
51 
52 			static immutable Word[8] iv = [
53 				0x6A09E667, 0xBB67AE85, 0x3C6EF372, 0xA54FF53A,
54 				0x510E527F, 0x9B05688C, 0x1F83D9AB, 0x5BE0CD19
55 			];
56 			
57 		} else static if(bitLength == 384) {
58 
59 			static immutable Word[8] iv = [
60 				0xcbbb9d5dc1059ed8, 0x629a292a367cd507, 0x9159015a3070dd17, 0x152fecd8f70e5939,
61 				0x67332667ffc00b31, 0x8eb44a8768581511, 0xdb0c2e0d64f98fa7, 0x47b5481dbefa4fa4
62 			];
63 
64 		} else static if(bitLength == 512) {
65 
66 			static immutable Word[8] iv = [
67 				0x6a09e667f3bcc908, 0xbb67ae8584caa73b, 0x3c6ef372fe94f82b, 0xa54ff53a5f1d36f1,
68 				0x510e527fade682d1, 0x9b05688c2b3e6c1f, 0x1f83d9abfb41bd6b, 0x5be0cd19137e2179
69 			];
70 
71 		} else {
72 			static assert(false, "Invalid bit length.");
73 		}
74 
75 		// Set constants and number of rounds.
76 		static if(bitLength == 224 || bitLength == 256) {
77 			
78 			enum rounds = 14;
79 
80 			static immutable Word[16] cst = [
81 				0x243F6A88, 0x85A308D3, 0x13198A2E, 0x03707344,
82 				0xA4093822, 0x299F31D0, 0x082EFA98, 0xEC4E6C89,
83 				0x452821E6, 0x38D01377, 0xBE5466CF, 0x34E90C6C,
84 				0xC0AC29B7, 0xC97C50DD, 0x3F84D5B5, 0xB5470917
85 			];
86 
87 		} else static if(bitLength == 384 || bitLength == 512) {
88 			
89 			enum rounds = 16;
90 
91 			static immutable Word[16] cst = [
92 				0x243F6A8885A308D3, 0x13198A2E03707344, 0xA4093822299F31D0, 0x082EFA98EC4E6C89,
93 				0x452821E638D01377, 0xBE5466CF34E90C6C, 0xC0AC29B7C97C50DD, 0x3F84D5B5B5470917,
94 				0x9216D5D98979FB1B, 0xD1310BA698DFB5AC, 0x2FFD72DBD01ADFB7, 0xB8E1AFED6A267E96,
95 				0xBA7C9045F12C7F99, 0x24A19947B3916CF7, 0x0801F2E2858EFC16, 0x636920D871574E69
96 			];
97 
98 		} else {
99 			static assert(false, "Invalid bit length.");
100 		}
101 		
102 		static immutable uint[16][16] perm = [
103 			[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],
104 			[14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3],
105 			[11, 8, 12, 0, 5, 2, 15, 13, 10, 14, 3, 6, 7, 1, 9, 4],
106 			[7, 9, 3, 1, 13, 12, 11, 14, 2, 6, 5, 10, 4, 0, 15, 8],
107 			[9, 0, 5, 7, 2, 4, 10, 15, 14, 1, 11, 12, 6, 8, 3, 13],
108 			[2, 12, 6, 10, 0, 11, 8, 3, 4, 13, 7, 5, 15, 14, 1, 9],
109 			[12, 5, 1, 15, 14, 13, 4, 10, 0, 7, 6, 3, 9, 2, 8, 11],
110 			[13, 11, 7, 14, 12, 1, 3, 9, 5, 0, 15, 4, 8, 6, 2, 10],
111 			[6, 15, 14, 9, 11, 3, 0, 8, 12, 2, 13, 7, 1, 4, 10, 5],
112 			[10, 2, 8, 4, 7, 6, 1, 5, 15, 11, 9, 14, 3, 12, 13, 0],
113 			
114 			[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],
115 			[14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3],
116 			[11, 8, 12, 0, 5, 2, 15, 13, 10, 14, 3, 6, 7, 1, 9, 4],
117 			[7, 9, 3, 1, 13, 12, 11, 14, 2, 6, 5, 10, 4, 0, 15, 8],
118 			[9, 0, 5, 7, 2, 4, 10, 15, 14, 1, 11, 12, 6, 8, 3, 13],
119 			[2, 12, 6, 10, 0, 11, 8, 3, 4, 13, 7, 5, 15, 14, 1, 9]
120 		];
121 
122 		Word[8] 	h = iv;
123 		Word[4]		salt = 0;
124 		Word[2]		counter = 0;
125 
126 		ubyte[Word.sizeof * 16] buf = 0;
127 		size_t bufPtr = 0;
128 	}
129 
130 	public void start() nothrow @nogc @safe {
131 		h = iv;
132 		salt[] = 0;
133 		counter[] = 0;
134 		buf[] = 0;
135 		bufPtr = 0;
136 	}
137 
138 	~this() {
139 		wipe(buf);
140 	}
141 
142 	invariant {
143 		assert(bufPtr <= buf.length, "bufPtr out of range.");
144 	}
145 
146 	public void put(const (ubyte)[] input...) nothrow @nogc @safe {
147 		// TODO optimize
148 		while(input.length >= buf.length-bufPtr) {
149 			buf[bufPtr..$] = input[0..buf.length-bufPtr];
150 			input = input[buf.length-bufPtr..$];
151 			absorb(buf.length*8);
152 		}
153 		if(input.length > 0) {
154 			assert(input.length < buf.length-bufPtr);
155 			buf[bufPtr..bufPtr+input.length] = input[];
156 			bufPtr += input.length;
157 		}
158 	}
159 
160 	public ubyte[digestLength] finish() nothrow @nogc @safe {
161 
162 		// pad to 447 bits (message || 1 || 0...0 || 1) 
163 		// at least 1 byte padding + 2*Word.sizeof bytes for length
164 
165 		enum counterSize = counter.length*Word.sizeof;
166 		enum requiredSpace = 1 + counterSize;
167 
168 		assert(bufPtr < buf.length, "There's not a single free byte in the buffer.");
169 
170 		buf[bufPtr] = 0b10000000;
171 
172 		if(buf.length-bufPtr < requiredSpace) {
173 			// must add a block
174 			buf[bufPtr+1..$] = 0;
175 			absorb(cast(uint) bufPtr*8);
176 			assert(bufPtr == 0);
177 		}
178 		assert(buf.length-bufPtr >= requiredSpace, "Whoops...");
179 		assert((buf[bufPtr] & 0b01111111) == 0, "Byte must be either 0 or 0x80");
180 
181 		buf[bufPtr+1..$] = 0;
182 
183 		static if(bitLength == 256 || bitLength == 512) {
184 			buf[$-requiredSpace] |= 0b1;
185 		} else {
186 			// This padding bit is 0 for 224 and 384 bits.
187 		}
188 
189 		incCounter(cast(uint) bufPtr*8);
190 
191 		toBigEndian(counter[1], buf[$-counterSize..$-Word.sizeof]);
192 		toBigEndian(counter[0], buf[$-Word.sizeof..$]);
193 
194 		// Set counter to zero if last block contains no message bit.
195 		counter[0] &= -cast(Word)(bufPtr != 0);
196 		counter[1] &= -cast(Word)(bufPtr != 0);
197 
198 		absorb();
199 
200 		ubyte[digestLength] hn;
201 		toBigEndian(h[0..digestLength/Word.sizeof], hn[]);
202 		start();
203 		return hn;
204 	}
205 
206 	private void absorb(in uint bits = 0) nothrow @nogc @safe {
207 		Word[16] msg;
208 		fromBigEndian(buf, msg);
209 
210 		incCounter(bits);
211 
212 		compress(h, msg, salt, counter);
213 
214 		bufPtr = 0;
215 		buf[] = 0;	// TODO: clear in finish() if necessary
216 	}
217 
218 	private void incCounter(in Word i) nothrow @nogc @safe {
219 		counter[0] += i;
220 		counter[1] += counter[0] < i; // detect carry
221 	}
222 
223 	// Test incCounter function.
224 	private unittest {
225 		immutable Word max = -1;
226 
227 		Blake!bitLength blake;
228 		assert(blake.counter == [0, 0]);
229 		blake.incCounter(0);
230 		assert(blake.counter == [0, 0]);
231 		blake.incCounter(1);
232 		assert(blake.counter == [1, 0]);
233 		blake.incCounter(2);
234 		assert(blake.counter == [3, 0]);
235 		blake.incCounter(4);
236 		assert(blake.counter == [7, 0]);
237 		blake.incCounter(max - 7 + 1);
238 		assert(blake.counter == [0, 1]);
239 		blake.incCounter(max);
240 		assert(blake.counter == [max, 1]);
241 		blake.incCounter(1);
242 		assert(blake.counter == [0, 2]);
243 		blake.incCounter(max);
244 		assert(blake.counter == [max, 2]);
245 		blake.incCounter(43);
246 		assert(blake.counter == [42, 3]);
247 	}
248 
249 	private static void compress(ref Word[8] h, in ref Word[16] m, in ref Word[4] salt, in ref Word[2] ctr) pure nothrow @nogc @safe {
250 		Word[16] state;
251 
252 		// initialize
253 		state[0..8] = h;
254 		state[8..16] = cst[0..8];
255 		state[8..12] ^= salt[];
256 		state[12..14] ^= ctr[0];
257 		state[14..16] ^= ctr[1];
258 
259 		foreach(r; 0..rounds) {
260 			round(r, m, state);
261 		}
262 
263 		// finalize
264 		h[] ^= state[0..8];
265 		h[] ^= state[8..16];
266 		h[0..4] ^= salt[];
267 		h[4..8] ^= salt[];
268 	}
269 
270 	private static void round(in size_t r, in ref Word[16] m, ref Word[16] state) pure nothrow @nogc @safe {
271 		G!0(r, m, state[0], state[4], state[8], state[12]);
272 		G!1(r, m, state[1], state[5], state[9], state[13]);
273 		G!2(r, m, state[2], state[6], state[10], state[14]);
274 		G!3(r, m, state[3], state[7], state[11], state[15]);
275 		
276 		G!4(r, m, state[0], state[5], state[10], state[15]);
277 		G!5(r, m, state[1], state[6], state[11], state[12]);
278 		G!6(r, m, state[2], state[7], state[8], state[13]);
279 		G!7(r, m, state[3], state[4], state[9], state[14]);
280 	}
281 
282 	private static void G(uint i)(in size_t r, in ref Word[16] msg, ref Word a, ref Word b, ref Word c, ref Word d) pure nothrow @nogc @safe {
283 
284 		static if(Word.sizeof == 4) {
285 			// rotation distances for Blake224 and Blake256
286 			enum r0 = 16, r1 = 12, r2 = 8, r3 = 7;
287 		} else static if (Word.sizeof == 8) {
288 			// rotation distances for Blake384 and Blake512
289 			enum r0 = 32, r1 = 25, r2 = 16, r3 = 11;
290 		} else {
291 			static assert(false, "Word consist of 4 or 8 bytes.");
292 		}
293 
294 		a += b + (msg[perm[r][2*i]] ^ cst[perm[r][2*i+1]]); 
295 		d = ror(d^a, r0);
296 		c += d; 
297 		b = ror(b^c, r1);
298 		a += b + (msg[perm[r][2*i+1]] ^ cst[perm[r][2*i]]);
299 		d = ror(d^a, r2);
300 		c += d; 
301 		b = ror(b^c, r3);
302 	}
303 
304 	
305 }
306 
307 /// Test BLAKE round function.
308 private unittest {
309 	alias uint Word;
310 
311 	Word[16] msg;
312 	fromBigEndian!Word(cast(const ubyte[]) x"
313 			00800000  00000000  00000000  00000000  00000000  00000000  00000000  00000000
314 			00000000  00000000  00000000  00000000  00000000  00000001  00000000  00000008", 
315 		msg
316 		);
317 
318 	Word[16] v0;
319 	fromBigEndian!Word(cast(const ubyte[]) x"
320 			6A09E667  BB67AE85  3C6EF372  A54FF53A  510E527F  9B05688C  1F83D9AB  5BE0CD19
321 			243F6A88  85A308D3  13198A2E  03707344  A409382A  299F31D8  082EFA98  EC4E6C89", 
322 		v0
323 		);
324 
325 	Word[16] expected1;
326 	fromBigEndian!Word(cast(const ubyte[]) x"
327 			E78B8DFE  150054E7  CABC8992  D15E8984  0669DF2A  084E66E3  A516C4B3  339DED5B
328 			26051FB7  09D18B27  3A2E8FA8  488C6059  13E513E6  B37ED53E  16CAC7B9  75AF6DF6", 
329 		expected1
330 		);
331 
332 	Word[16] expected2;
333 	fromBigEndian!Word(cast(const ubyte[]) x"
334 			9DE875FD  8286272E  ADD20174  F1B0F1B7  37A1A6D3  CF90583A  B67E00D2  943A1F4F
335 			E5294126  43BD06BF  B81ECBA2  6AF5CEAF  4FEB3A1F  0D6CA73C  5EE50B3E  DC88DF91", 
336 		expected2
337 		);
338 
339 	Word[16] v = v0;
340 
341 	Blake!256.round(0, msg, v);
342 	assert(v== expected1, "BLAKE round failed!");
343 
344 	Blake!256.round(1, msg, v);
345 	assert(v== expected2, "BLAKE round failed!");
346 
347 	Word[4] salt;
348 	Word[2] counter = [0x00000008, 0x00000000];
349 	Word[8] h = Blake!256.iv;
350 
351 	Blake!256.compress(h, msg, salt, counter);
352 
353 	Word[8] expectedH;
354 	fromBigEndian!Word(cast(const ubyte[]) x"
355 			0CE8D4EF 4DD7CD8D 62DFDED9 D4EDB0A7 74AE6A41 929A74DA 23109E8F 11139C87", 
356 		expectedH
357 		);
358 
359 	assert(h == expectedH, "BLAKE round failed!");
360 }
361 
362 
363 
364 unittest {
365 	Blake!224 blake;
366 	
367 	ubyte[576/8] msg;
368 	
369 	blake.put(msg);
370 	auto hash = blake.finish();
371 	assert(hash == x"f5aa00dd1cb847e3140372af7b5c46b4888d82c8c0a917913cfb5d04");
372 }
373 
374 
375 unittest {
376 	Blake!256 blake;
377 
378 	ubyte[576/8] msg;
379 
380 	blake.put(msg);
381 	auto hash = blake.finish();
382 	assert(hash == x"d419bad32d504fb7d44d460c42c5593fe544fa4c135dec31e21bd9abdcc22d41");
383 }
384 
385 unittest {
386 	Blake!384 blake;
387 	
388 	ubyte[1152/8] msg;
389 	
390 	blake.put(msg);
391 	auto hash = blake.finish();
392 	assert(hash == x"
393 		0B9845DD429566CD  AB772BA195D271EF  FE2D0211F16991D7  66BA749447C5CDE5
394 		69780B2DAA66C4B2  24A2EC2E5D09174C"
395 		);
396 }
397 
398 
399 unittest {
400 	Blake!512 blake;
401 	
402 	ubyte[1152/8] msg;
403 	
404 	blake.put(msg);
405 	auto hash = blake.finish();
406 	assert(hash == x"
407 		313717D608E9CF75  8DCB1EB0F0C3CF9F  C150B2D500FB33F5  1C52AFC99D358A2F
408 		1374B8A38BBA7974  E7F6EF79CAB16F22  CE1E649D6E01AD95  89C213045D545DDE"
409 		);
410 }
411 
412 unittest {
413 	
414 	immutable string[] plaintexts = [
415 		x"",
416 		x"00"
417 	];
418 	
419 	immutable string[] hashes = [
420 		x"7dc5313b1c04512a174bd6503b89607aecbee0903d40a8a569c94eed",
421 		x"4504cb0314fb2a4f7a692e696e487912fe3f2468fe312c73a5278ec5"
422 	];
423 	
424 	testDigest(new Blake224Digest, plaintexts, hashes);
425 }
426 
427 unittest {
428 	
429 	immutable string[] plaintexts = [
430 		x"00",
431 		"The quick brown fox jumps over the lazy dog",
432 		// 54 zeros
433 		x"0000000000000000000000000000000000000000000000000000000000000000
434 		00000000000000000000000000000000000000000000",
435 		// 55 zeros
436 		x"0000000000000000000000000000000000000000000000000000000000000000
437 		0000000000000000000000000000000000000000000000",
438 		// 56 zeros
439 		x"0000000000000000000000000000000000000000000000000000000000000000
440 		000000000000000000000000000000000000000000000000",
441 		// 57 zeros
442 		x"0000000000000000000000000000000000000000000000000000000000000000
443 		00000000000000000000000000000000000000000000000000",
444 		// 63 zeros
445 		x"0000000000000000000000000000000000000000000000000000000000000000
446 		00000000000000000000000000000000000000000000000000000000000000",
447 		// 64 zeros
448 		x"0000000000000000000000000000000000000000000000000000000000000000
449 		0000000000000000000000000000000000000000000000000000000000000000",
450 	];
451 	
452 	immutable string[] hashes = [
453 		x"0ce8d4ef4dd7cd8d62dfded9d4edb0a774ae6a41929a74da23109e8f11139c87",
454 		x"7576698EE9CAD30173080678E5965916ADBB11CB5245D386BF1FFDA1CB26C9D7",
455 		x"8b7b134b0450f2ee19935dc82df3e4fa7f990b320b1a9afbf1e40914c6fb67cc",
456 		x"dc980544f4181cc43505318e317cdfd4334dab81ae035a28818308867ce23060",
457 		x"26ae7c289ebb79c9f3af2285023ab1037a9a6db63f0d6b6c6bbd199ab1627508",
458 		x"363446fac666e859deae9e81c458662371b6fdd0793712735911071c2be9456b",
459 		x"254b522be8c966d8a2c44a2bffce8469f8223ea3371e14e6387d60fc790361f1",
460 		x"6d994042954f8dc5633626cd50b2bc66d733a313d67fd9702c5a8149a8028c98"
461 	];
462 	
463 	testDigest(new Blake256Digest, plaintexts, hashes);
464 }
465 
466 unittest {
467 	
468 	immutable string[] plaintexts = [
469 		x"",
470 		x"00",
471 		// 127 zeros
472 		x"0000000000000000000000000000000000000000000000000000000000000000
473 		0000000000000000000000000000000000000000000000000000000000000000
474 		0000000000000000000000000000000000000000000000000000000000000000
475 		00000000000000000000000000000000000000000000000000000000000000"
476 	];
477 	
478 	immutable string[] hashes = [
479 		x"c6cbd89c926ab525c242e6621f2f5fa73aa4afe3d9e24aed727faaadd6af38b620bdb623dd2b4788b1c8086984af8706",
480 		x"10281f67e135e90ae8e882251a355510a719367ad70227b137343e1bc122015c29391e8545b5272d13a7c2879da3d807",
481 		x"980a24df8bfdfa1e2dfcd19c945f9ee8e7e64487bd0a3a63c44a5879a83b45622dc19b5e0f2c63c57a65f405e31c7f3f"
482 	];
483 	
484 	testDigest(new Blake384Digest, plaintexts, hashes);
485 }
486 
487 /// Test vectors generated with reference implementation.
488 /// 
489 /// Generate the reference hash:
490 /// ./blake512 <(perl -e 'print "\x00"x127')
491 /// 
492 /// Generate the input data as hex:
493 /// perl -e 'print "\x00"x127' | xxd -ps -c 32
494 /// 
495 unittest {
496 	
497 	immutable string[] plaintexts = [
498 		x"",
499 		x"00",
500 		"The quick brown fox jumps over the lazy dog",
501 		// 127 zeros
502 		x"0000000000000000000000000000000000000000000000000000000000000000
503 		0000000000000000000000000000000000000000000000000000000000000000
504 		0000000000000000000000000000000000000000000000000000000000000000
505 		00000000000000000000000000000000000000000000000000000000000000",
506 		// 128 zeros
507 		x"0000000000000000000000000000000000000000000000000000000000000000
508 		0000000000000000000000000000000000000000000000000000000000000000
509 		0000000000000000000000000000000000000000000000000000000000000000
510 		0000000000000000000000000000000000000000000000000000000000000000",
511 		// 129 zeros
512 		x"0000000000000000000000000000000000000000000000000000000000000000
513 		0000000000000000000000000000000000000000000000000000000000000000
514 		0000000000000000000000000000000000000000000000000000000000000000
515 		0000000000000000000000000000000000000000000000000000000000000000
516 		00"
517 	];
518 		
519 	immutable string[] hashes = [
520 		x"a8cfbbd73726062df0c6864dda65defe58ef0cc52a5625090fa17601e1eecd1b628e94f396ae402a00acc9eab77b4d4c2e852aaaa25a636d80af3fc7913ef5b8",
521 		x"97961587f6d970faba6d2478045de6d1fabd09b61ae50932054d52bc29d31be4ff9102b9f69e2bbdb83be13d4b9c06091e5fa0b48bd081b634058be0ec49beb3",
522 		x"1f7e26f63b6ad25a0896fd978fd050a1766391d2fd0471a77afb975e5034b7ad2d9ccf8dfb47abbbe656e1b82fbc634ba42ce186e8dc5e1ce09a885d41f43451",
523 		x"d6bd99cb8f201c5e777f25859cca7b21b4659fce0e19d04de85be6566cae87b9b15e4b82f9e80eea894aaaea15e26f08ce6cd2af9f0fef1a15486cdf9c8ca8df",
524 		x"0f6f3a3a91f752d37e3d37141d5459aca9a88ed2d5b88f71120fbe39387b635ecf6402a5bcb7b18f216ea9a8137d28954098e586014c4d435c979d8860d3a977",
525 		x"c75df1083f0cff9a4b423b0f5cdcee6526133513198f897c89901d0ab80995bf9cefe01c992563b5dd4a8f76f22f16859615c30b309efe329f7462eb280df34c"
526 	];
527 	
528 	testDigest(new Blake512Digest, plaintexts, hashes);
529 }