1 // Copyright (c) 2017 Martijn Rijkeboer <mrr@sru-systems.com>
2 //
3 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
4 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
5 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
6 // option. This file may not be copied, modified, or distributed
7 // except according to those terms.
8
9 use crate::block::Block;
10 use crate::common;
11 use crate::context::Context;
12 use crate::memory::Memory;
13 use crate::variant::Variant;
14 use crate::version::Version;
15 use blake2b_simd::Params;
16 #[cfg(feature = "crossbeam-utils")]
17 use crossbeam_utils::thread::scope;
18
19 /// Position of the block currently being operated on.
20 #[derive(Clone, Debug)]
21 struct Position {
22 pass: u32,
23 lane: u32,
24 slice: u32,
25 index: u32,
26 }
27
28 /// Initializes the memory.
initialize(context: &Context, memory: &mut Memory)29 pub fn initialize(context: &Context, memory: &mut Memory) {
30 fill_first_blocks(context, memory, &mut h0(context));
31 }
32
33 /// Fills all the memory blocks.
fill_memory_blocks(context: &Context, memory: &mut Memory)34 pub fn fill_memory_blocks(context: &Context, memory: &mut Memory) {
35 if context.config.uses_sequential() {
36 fill_memory_blocks_st(context, memory);
37 } else {
38 fill_memory_blocks_mt(context, memory);
39 }
40 }
41
42 /// Calculates the final hash and returns it.
finalize(context: &Context, memory: &Memory) -> Vec<u8>43 pub fn finalize(context: &Context, memory: &Memory) -> Vec<u8> {
44 let mut blockhash = memory[context.lane_length - 1].clone();
45 for l in 1..context.config.lanes {
46 let last_block_in_lane = l * context.lane_length + (context.lane_length - 1);
47 blockhash ^= &memory[last_block_in_lane];
48 }
49
50 let mut hash = vec![0u8; context.config.hash_length as usize];
51 hprime(hash.as_mut_slice(), blockhash.as_u8());
52 hash
53 }
54
blake2b(out: &mut [u8], input: &[&[u8]])55 fn blake2b(out: &mut [u8], input: &[&[u8]]) {
56 let mut blake = Params::new().hash_length(out.len()).to_state();
57 for slice in input {
58 blake.update(slice);
59 }
60 out.copy_from_slice(blake.finalize().as_bytes());
61 }
62
f_bla_mka(x: u64, y: u64) -> u6463 fn f_bla_mka(x: u64, y: u64) -> u64 {
64 let m = 0xFFFF_FFFFu64;
65 let xy = (x & m) * (y & m);
66 x.wrapping_add(y.wrapping_add(xy.wrapping_add(xy)))
67 }
68
fill_block(prev_block: &Block, ref_block: &Block, next_block: &mut Block, with_xor: bool)69 fn fill_block(prev_block: &Block, ref_block: &Block, next_block: &mut Block, with_xor: bool) {
70 let mut block_r = ref_block.clone();
71 block_r ^= prev_block;
72 let mut block_tmp = block_r.clone();
73
74 // Now block_r = ref_block + prev_block and block_tmp = ref_block + prev_block
75 if with_xor {
76 // Saving the next block contents for XOR over
77 block_tmp ^= next_block;
78 // Now block_r = ref_block + prev_block and
79 // block_tmp = ref_block + prev_block + next_block
80 }
81
82 // Apply Blake2 on columns of 64-bit words: (0,1,...,15) , then
83 // (16,17,..31)... finally (112,113,...127)
84 for i in 0..8 {
85 let mut v0 = block_r[16 * i];
86 let mut v1 = block_r[16 * i + 1];
87 let mut v2 = block_r[16 * i + 2];
88 let mut v3 = block_r[16 * i + 3];
89 let mut v4 = block_r[16 * i + 4];
90 let mut v5 = block_r[16 * i + 5];
91 let mut v6 = block_r[16 * i + 6];
92 let mut v7 = block_r[16 * i + 7];
93 let mut v8 = block_r[16 * i + 8];
94 let mut v9 = block_r[16 * i + 9];
95 let mut v10 = block_r[16 * i + 10];
96 let mut v11 = block_r[16 * i + 11];
97 let mut v12 = block_r[16 * i + 12];
98 let mut v13 = block_r[16 * i + 13];
99 let mut v14 = block_r[16 * i + 14];
100 let mut v15 = block_r[16 * i + 15];
101
102 p(
103 &mut v0, &mut v1, &mut v2, &mut v3, &mut v4, &mut v5, &mut v6, &mut v7, &mut v8,
104 &mut v9, &mut v10, &mut v11, &mut v12, &mut v13, &mut v14, &mut v15,
105 );
106
107 block_r[16 * i] = v0;
108 block_r[16 * i + 1] = v1;
109 block_r[16 * i + 2] = v2;
110 block_r[16 * i + 3] = v3;
111 block_r[16 * i + 4] = v4;
112 block_r[16 * i + 5] = v5;
113 block_r[16 * i + 6] = v6;
114 block_r[16 * i + 7] = v7;
115 block_r[16 * i + 8] = v8;
116 block_r[16 * i + 9] = v9;
117 block_r[16 * i + 10] = v10;
118 block_r[16 * i + 11] = v11;
119 block_r[16 * i + 12] = v12;
120 block_r[16 * i + 13] = v13;
121 block_r[16 * i + 14] = v14;
122 block_r[16 * i + 15] = v15;
123 }
124
125 // Apply Blake2 on rows of 64-bit words: (0,1,16,17,...112,113), then
126 // (2,3,18,19,...,114,115).. finally (14,15,30,31,...,126,127)
127 for i in 0..8 {
128 let mut v0 = block_r[2 * i];
129 let mut v1 = block_r[2 * i + 1];
130 let mut v2 = block_r[2 * i + 16];
131 let mut v3 = block_r[2 * i + 17];
132 let mut v4 = block_r[2 * i + 32];
133 let mut v5 = block_r[2 * i + 33];
134 let mut v6 = block_r[2 * i + 48];
135 let mut v7 = block_r[2 * i + 49];
136 let mut v8 = block_r[2 * i + 64];
137 let mut v9 = block_r[2 * i + 65];
138 let mut v10 = block_r[2 * i + 80];
139 let mut v11 = block_r[2 * i + 81];
140 let mut v12 = block_r[2 * i + 96];
141 let mut v13 = block_r[2 * i + 97];
142 let mut v14 = block_r[2 * i + 112];
143 let mut v15 = block_r[2 * i + 113];
144
145 p(
146 &mut v0, &mut v1, &mut v2, &mut v3, &mut v4, &mut v5, &mut v6, &mut v7, &mut v8,
147 &mut v9, &mut v10, &mut v11, &mut v12, &mut v13, &mut v14, &mut v15,
148 );
149
150 block_r[2 * i] = v0;
151 block_r[2 * i + 1] = v1;
152 block_r[2 * i + 16] = v2;
153 block_r[2 * i + 17] = v3;
154 block_r[2 * i + 32] = v4;
155 block_r[2 * i + 33] = v5;
156 block_r[2 * i + 48] = v6;
157 block_r[2 * i + 49] = v7;
158 block_r[2 * i + 64] = v8;
159 block_r[2 * i + 65] = v9;
160 block_r[2 * i + 80] = v10;
161 block_r[2 * i + 81] = v11;
162 block_r[2 * i + 96] = v12;
163 block_r[2 * i + 97] = v13;
164 block_r[2 * i + 112] = v14;
165 block_r[2 * i + 113] = v15;
166 }
167
168 block_tmp.copy_to(next_block);
169 *next_block ^= &block_r;
170 }
171
fill_first_blocks(context: &Context, memory: &mut Memory, h0: &mut [u8])172 fn fill_first_blocks(context: &Context, memory: &mut Memory, h0: &mut [u8]) {
173 for lane in 0..context.config.lanes {
174 let start = common::PREHASH_DIGEST_LENGTH;
175 // H'(H0||0||i)
176 h0[start..(start + 4)].clone_from_slice(&u32::to_le_bytes(0));
177 h0[(start + 4)..(start + 8)].clone_from_slice(&u32::to_le_bytes(lane));
178 hprime(memory[(lane, 0)].as_u8_mut(), &h0);
179
180 // H'(H0||1||i)
181 h0[start..(start + 4)].clone_from_slice(&u32::to_le_bytes(1));
182 hprime(memory[(lane, 1)].as_u8_mut(), &h0);
183 }
184 }
185
186 #[cfg(feature = "crossbeam-utils")]
fill_memory_blocks_mt(context: &Context, memory: &mut Memory)187 fn fill_memory_blocks_mt(context: &Context, memory: &mut Memory) {
188 for p in 0..context.config.time_cost {
189 for s in 0..common::SYNC_POINTS {
190 let _ = scope(|scoped| {
191 for (l, mem) in (0..context.config.lanes).zip(memory.as_lanes_mut()) {
192 let position = Position {
193 pass: p,
194 lane: l,
195 slice: s,
196 index: 0,
197 };
198 scoped.spawn(move |_| {
199 fill_segment(context, &position, mem);
200 });
201 }
202 });
203 }
204 }
205 }
206
207 #[cfg(not(feature = "crossbeam-utils"))]
fill_memory_blocks_mt(_: &Context, _: &mut Memory)208 fn fill_memory_blocks_mt(_: &Context, _: &mut Memory) {
209 unimplemented!()
210 }
211
fill_memory_blocks_st(context: &Context, memory: &mut Memory)212 fn fill_memory_blocks_st(context: &Context, memory: &mut Memory) {
213 for p in 0..context.config.time_cost {
214 for s in 0..common::SYNC_POINTS {
215 for l in 0..context.config.lanes {
216 let position = Position {
217 pass: p,
218 lane: l,
219 slice: s,
220 index: 0,
221 };
222 fill_segment(context, &position, memory);
223 }
224 }
225 }
226 }
227
fill_segment(context: &Context, position: &Position, memory: &mut Memory)228 fn fill_segment(context: &Context, position: &Position, memory: &mut Memory) {
229 let mut position = position.clone();
230 let data_independent_addressing = (context.config.variant == Variant::Argon2i)
231 || (context.config.variant == Variant::Argon2id && position.pass == 0)
232 && (position.slice < (common::SYNC_POINTS / 2));
233 let zero_block = Block::zero();
234 let mut input_block = Block::zero();
235 let mut address_block = Block::zero();
236
237 if data_independent_addressing {
238 input_block[0] = position.pass as u64;
239 input_block[1] = position.lane as u64;
240 input_block[2] = position.slice as u64;
241 input_block[3] = context.memory_blocks as u64;
242 input_block[4] = context.config.time_cost as u64;
243 input_block[5] = context.config.variant.as_u64();
244 }
245
246 let mut starting_index = 0u32;
247
248 if position.pass == 0 && position.slice == 0 {
249 starting_index = 2;
250
251 // Don't forget to generate the first block of addresses:
252 if data_independent_addressing {
253 next_addresses(&mut address_block, &mut input_block, &zero_block);
254 }
255 }
256
257 let mut curr_offset = (position.lane * context.lane_length)
258 + (position.slice * context.segment_length)
259 + starting_index;
260
261 let mut prev_offset = if curr_offset % context.lane_length == 0 {
262 // Last block in this lane
263 curr_offset + context.lane_length - 1
264 } else {
265 curr_offset - 1
266 };
267
268 let mut pseudo_rand;
269 for i in starting_index..context.segment_length {
270 // 1.1 Rotating prev_offset if needed
271 if curr_offset % context.lane_length == 1 {
272 prev_offset = curr_offset - 1;
273 }
274
275 // 1.2 Computing the index of the reference block
276 // 1.2.1 Taking pseudo-random value from the previous block
277 if data_independent_addressing {
278 if i % common::ADDRESSES_IN_BLOCK == 0 {
279 next_addresses(&mut address_block, &mut input_block, &zero_block);
280 }
281 pseudo_rand = address_block[(i % common::ADDRESSES_IN_BLOCK) as usize];
282 } else {
283 pseudo_rand = memory[(prev_offset)][0];
284 }
285
286 // 1.2.2 Computing the lane of the reference block
287 // If (position.pass == 0) && (position.slice == 0): can not reference other lanes yet
288 let ref_lane = if (position.pass == 0) && (position.slice == 0) {
289 position.lane as u64
290 } else {
291 (pseudo_rand >> 32) % context.config.lanes as u64
292 };
293
294 // 1.2.3 Computing the number of possible reference block within the lane.
295 position.index = i;
296 let pseudo_rand_u32 = (pseudo_rand & 0xFFFF_FFFF) as u32;
297 let same_lane = ref_lane == (position.lane as u64);
298 let ref_index = index_alpha(context, &position, pseudo_rand_u32, same_lane);
299
300 // 2 Creating a new block
301 let index = context.lane_length as u64 * ref_lane + ref_index as u64;
302 let mut curr_block = memory[curr_offset].clone();
303 {
304 let prev_block = &memory[prev_offset];
305 let ref_block = &memory[index];
306 if context.config.version == Version::Version10 || position.pass == 0 {
307 fill_block(prev_block, ref_block, &mut curr_block, false);
308 } else {
309 fill_block(prev_block, ref_block, &mut curr_block, true);
310 }
311 }
312
313 memory[curr_offset] = curr_block;
314 curr_offset += 1;
315 prev_offset += 1;
316 }
317 }
318
g(a: &mut u64, b: &mut u64, c: &mut u64, d: &mut u64)319 fn g(a: &mut u64, b: &mut u64, c: &mut u64, d: &mut u64) {
320 *a = f_bla_mka(*a, *b);
321 *d = rotr64(*d ^ *a, 32);
322 *c = f_bla_mka(*c, *d);
323 *b = rotr64(*b ^ *c, 24);
324 *a = f_bla_mka(*a, *b);
325 *d = rotr64(*d ^ *a, 16);
326 *c = f_bla_mka(*c, *d);
327 *b = rotr64(*b ^ *c, 63);
328 }
329
h0(context: &Context) -> [u8; common::PREHASH_SEED_LENGTH]330 fn h0(context: &Context) -> [u8; common::PREHASH_SEED_LENGTH] {
331 let input = [
332 &u32::to_le_bytes(context.config.lanes),
333 &u32::to_le_bytes(context.config.hash_length),
334 &u32::to_le_bytes(context.config.mem_cost),
335 &u32::to_le_bytes(context.config.time_cost),
336 &u32::to_le_bytes(context.config.version.as_u32()),
337 &u32::to_le_bytes(context.config.variant.as_u32()),
338 &len_as_32le(context.pwd),
339 context.pwd,
340 &len_as_32le(context.salt),
341 context.salt,
342 &len_as_32le(context.config.secret),
343 context.config.secret,
344 &len_as_32le(context.config.ad),
345 context.config.ad,
346 ];
347 let mut out = [0u8; common::PREHASH_SEED_LENGTH];
348 blake2b(&mut out[0..common::PREHASH_DIGEST_LENGTH], &input);
349 out
350 }
351
hprime(out: &mut [u8], input: &[u8])352 fn hprime(out: &mut [u8], input: &[u8]) {
353 let out_len = out.len();
354 if out_len <= common::BLAKE2B_OUT_LENGTH {
355 blake2b(out, &[&u32::to_le_bytes(out_len as u32), input]);
356 } else {
357 let ai_len = 32;
358 let mut out_buffer = [0u8; common::BLAKE2B_OUT_LENGTH];
359 let mut in_buffer = [0u8; common::BLAKE2B_OUT_LENGTH];
360 blake2b(&mut out_buffer, &[&u32::to_le_bytes(out_len as u32), input]);
361 out[0..ai_len].clone_from_slice(&out_buffer[0..ai_len]);
362 let mut out_pos = ai_len;
363 let mut to_produce = out_len - ai_len;
364
365 while to_produce > common::BLAKE2B_OUT_LENGTH {
366 in_buffer.clone_from_slice(&out_buffer);
367 blake2b(&mut out_buffer, &[&in_buffer]);
368 out[out_pos..out_pos + ai_len].clone_from_slice(&out_buffer[0..ai_len]);
369 out_pos += ai_len;
370 to_produce -= ai_len;
371 }
372 blake2b(&mut out[out_pos..out_len], &[&out_buffer]);
373 }
374 }
375
index_alpha(context: &Context, position: &Position, pseudo_rand: u32, same_lane: bool) -> u32376 fn index_alpha(context: &Context, position: &Position, pseudo_rand: u32, same_lane: bool) -> u32 {
377 // Pass 0:
378 // - This lane: all already finished segments plus already constructed blocks in this segment
379 // - Other lanes: all already finished segments
380 // Pass 1+:
381 // - This lane: (SYNC_POINTS - 1) last segments plus already constructed blocks in this segment
382 // - Other lanes : (SYNC_POINTS - 1) last segments
383 let reference_area_size: u32 = if position.pass == 0 {
384 // First pass
385 if position.slice == 0 {
386 // First slice
387 position.index - 1
388 } else if same_lane {
389 // The same lane => add current segment
390 position.slice * context.segment_length + position.index - 1
391 } else if position.index == 0 {
392 position.slice * context.segment_length - 1
393 } else {
394 position.slice * context.segment_length
395 }
396 } else {
397 // Second pass
398 if same_lane {
399 context.lane_length - context.segment_length + position.index - 1
400 } else if position.index == 0 {
401 context.lane_length - context.segment_length - 1
402 } else {
403 context.lane_length - context.segment_length
404 }
405 };
406 let reference_area_size = reference_area_size as u64;
407 let mut relative_position = pseudo_rand as u64;
408 relative_position = (relative_position * relative_position) >> 32;
409 relative_position = reference_area_size - 1 - ((reference_area_size * relative_position) >> 32);
410
411 // 1.2.5 Computing starting position
412 let start_position: u32 = if position.pass != 0 {
413 if position.slice == common::SYNC_POINTS - 1 {
414 0u32
415 } else {
416 (position.slice + 1) * context.segment_length
417 }
418 } else {
419 0u32
420 };
421 let start_position = start_position as u64;
422
423 // 1.2.6. Computing absolute position
424 ((start_position + relative_position) % context.lane_length as u64) as u32
425 }
426
len_as_32le(slice: &[u8]) -> [u8; 4]427 fn len_as_32le(slice: &[u8]) -> [u8; 4] {
428 u32::to_le_bytes(slice.len() as u32)
429 }
430
next_addresses(address_block: &mut Block, input_block: &mut Block, zero_block: &Block)431 fn next_addresses(address_block: &mut Block, input_block: &mut Block, zero_block: &Block) {
432 input_block[6] += 1;
433 fill_block(zero_block, input_block, address_block, false);
434 fill_block(zero_block, &address_block.clone(), address_block, false);
435 }
436
p( v0: &mut u64, v1: &mut u64, v2: &mut u64, v3: &mut u64, v4: &mut u64, v5: &mut u64, v6: &mut u64, v7: &mut u64, v8: &mut u64, v9: &mut u64, v10: &mut u64, v11: &mut u64, v12: &mut u64, v13: &mut u64, v14: &mut u64, v15: &mut u64, )437 fn p(
438 v0: &mut u64,
439 v1: &mut u64,
440 v2: &mut u64,
441 v3: &mut u64,
442 v4: &mut u64,
443 v5: &mut u64,
444 v6: &mut u64,
445 v7: &mut u64,
446 v8: &mut u64,
447 v9: &mut u64,
448 v10: &mut u64,
449 v11: &mut u64,
450 v12: &mut u64,
451 v13: &mut u64,
452 v14: &mut u64,
453 v15: &mut u64,
454 ) {
455 g(v0, v4, v8, v12);
456 g(v1, v5, v9, v13);
457 g(v2, v6, v10, v14);
458 g(v3, v7, v11, v15);
459 g(v0, v5, v10, v15);
460 g(v1, v6, v11, v12);
461 g(v2, v7, v8, v13);
462 g(v3, v4, v9, v14);
463 }
464
rotr64(w: u64, c: u32) -> u64465 fn rotr64(w: u64, c: u32) -> u64 {
466 (w >> c) | (w << (64 - c))
467 }
468