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 use crossbeam_utils::thread::scope;
17 use std::mem;
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_as_32le(0));
177 h0[(start + 4)..(start + 8)].clone_from_slice(&u32_as_32le(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_as_32le(1));
182 hprime(memory[(lane, 1)].as_u8_mut(), &h0);
183 }
184 }
185
fill_memory_blocks_mt(context: &Context, memory: &mut Memory)186 fn fill_memory_blocks_mt(context: &Context, memory: &mut Memory) {
187 for p in 0..context.config.time_cost {
188 for s in 0..common::SYNC_POINTS {
189 let _ = scope(|scoped| {
190 for (l, mem) in (0..context.config.lanes).zip(memory.as_lanes_mut()) {
191 let position = Position {
192 pass: p,
193 lane: l,
194 slice: s,
195 index: 0,
196 };
197 scoped.spawn(move |_| {
198 fill_segment(context, &position, mem);
199 });
200 }
201 });
202 }
203 }
204 }
205
fill_memory_blocks_st(context: &Context, memory: &mut Memory)206 fn fill_memory_blocks_st(context: &Context, memory: &mut Memory) {
207 for p in 0..context.config.time_cost {
208 for s in 0..common::SYNC_POINTS {
209 for l in 0..context.config.lanes {
210 let position = Position {
211 pass: p,
212 lane: l,
213 slice: s,
214 index: 0,
215 };
216 fill_segment(context, &position, memory);
217 }
218 }
219 }
220 }
221
fill_segment(context: &Context, position: &Position, memory: &mut Memory)222 fn fill_segment(context: &Context, position: &Position, memory: &mut Memory) {
223 let mut position = position.clone();
224 let data_independent_addressing = (context.config.variant == Variant::Argon2i)
225 || (context.config.variant == Variant::Argon2id && position.pass == 0)
226 && (position.slice < (common::SYNC_POINTS / 2));
227 let zero_block = Block::zero();
228 let mut input_block = Block::zero();
229 let mut address_block = Block::zero();
230
231 if data_independent_addressing {
232 input_block[0] = position.pass as u64;
233 input_block[1] = position.lane as u64;
234 input_block[2] = position.slice as u64;
235 input_block[3] = context.memory_blocks as u64;
236 input_block[4] = context.config.time_cost as u64;
237 input_block[5] = context.config.variant.as_u64();
238 }
239
240 let mut starting_index = 0u32;
241
242 if position.pass == 0 && position.slice == 0 {
243 starting_index = 2;
244
245 // Don't forget to generate the first block of addresses:
246 if data_independent_addressing {
247 next_addresses(&mut address_block, &mut input_block, &zero_block);
248 }
249 }
250
251 let mut curr_offset = (position.lane * context.lane_length)
252 + (position.slice * context.segment_length)
253 + starting_index;
254
255 let mut prev_offset = if curr_offset % context.lane_length == 0 {
256 // Last block in this lane
257 curr_offset + context.lane_length - 1
258 } else {
259 curr_offset - 1
260 };
261
262 let mut pseudo_rand;
263 for i in starting_index..context.segment_length {
264 // 1.1 Rotating prev_offset if needed
265 if curr_offset % context.lane_length == 1 {
266 prev_offset = curr_offset - 1;
267 }
268
269 // 1.2 Computing the index of the reference block
270 // 1.2.1 Taking pseudo-random value from the previous block
271 if data_independent_addressing {
272 if i % common::ADDRESSES_IN_BLOCK == 0 {
273 next_addresses(&mut address_block, &mut input_block, &zero_block);
274 }
275 pseudo_rand = address_block[(i % common::ADDRESSES_IN_BLOCK) as usize];
276 } else {
277 pseudo_rand = memory[(prev_offset)][0];
278 }
279
280 // 1.2.2 Computing the lane of the reference block
281 // If (position.pass == 0) && (position.slice == 0): can not reference other lanes yet
282 let ref_lane = if (position.pass == 0) && (position.slice == 0) { position.lane as u64 } else { (pseudo_rand >> 32) % context.config.lanes as u64 };
283
284 // 1.2.3 Computing the number of possible reference block within the lane.
285 position.index = i;
286 let pseudo_rand_u32 = (pseudo_rand & 0xFFFF_FFFF) as u32;
287 let same_lane = ref_lane == (position.lane as u64);
288 let ref_index = index_alpha(context, &position, pseudo_rand_u32, same_lane);
289
290 // 2 Creating a new block
291 let index = context.lane_length as u64 * ref_lane + ref_index as u64;
292 let mut curr_block = memory[curr_offset].clone();
293 {
294 let prev_block = &memory[prev_offset];
295 let ref_block = &memory[index];
296 if context.config.version == Version::Version10 || position.pass == 0 {
297 fill_block(prev_block, ref_block, &mut curr_block, false);
298 } else {
299 fill_block(prev_block, ref_block, &mut curr_block, true);
300 }
301 }
302
303 memory[curr_offset] = curr_block;
304 curr_offset += 1;
305 prev_offset += 1;
306 }
307 }
308
g(a: &mut u64, b: &mut u64, c: &mut u64, d: &mut u64)309 fn g(a: &mut u64, b: &mut u64, c: &mut u64, d: &mut u64) {
310 *a = f_bla_mka(*a, *b);
311 *d = rotr64(*d ^ *a, 32);
312 *c = f_bla_mka(*c, *d);
313 *b = rotr64(*b ^ *c, 24);
314 *a = f_bla_mka(*a, *b);
315 *d = rotr64(*d ^ *a, 16);
316 *c = f_bla_mka(*c, *d);
317 *b = rotr64(*b ^ *c, 63);
318 }
319
h0(context: &Context) -> [u8; common::PREHASH_SEED_LENGTH]320 fn h0(context: &Context) -> [u8; common::PREHASH_SEED_LENGTH] {
321 let input = [
322 &u32_as_32le(context.config.lanes),
323 &u32_as_32le(context.config.hash_length),
324 &u32_as_32le(context.config.mem_cost),
325 &u32_as_32le(context.config.time_cost),
326 &u32_as_32le(context.config.version.as_u32()),
327 &u32_as_32le(context.config.variant.as_u32()),
328 &len_as_32le(context.pwd),
329 context.pwd,
330 &len_as_32le(context.salt),
331 context.salt,
332 &len_as_32le(context.config.secret),
333 context.config.secret,
334 &len_as_32le(context.config.ad),
335 context.config.ad,
336 ];
337 let mut out = [0u8; common::PREHASH_SEED_LENGTH];
338 blake2b(&mut out[0..common::PREHASH_DIGEST_LENGTH], &input);
339 out
340 }
341
hprime(out: &mut [u8], input: &[u8])342 fn hprime(out: &mut [u8], input: &[u8]) {
343 let out_len = out.len();
344 if out_len <= common::BLAKE2B_OUT_LENGTH {
345 blake2b(out, &[&u32_as_32le(out_len as u32), input]);
346 } else {
347 let ai_len = 32;
348 let mut out_buffer = [0u8; common::BLAKE2B_OUT_LENGTH];
349 let mut in_buffer = [0u8; common::BLAKE2B_OUT_LENGTH];
350 blake2b(&mut out_buffer, &[&u32_as_32le(out_len as u32), input]);
351 out[0..ai_len].clone_from_slice(&out_buffer[0..ai_len]);
352 let mut out_pos = ai_len;
353 let mut to_produce = out_len - ai_len;
354
355 while to_produce > common::BLAKE2B_OUT_LENGTH {
356 in_buffer.clone_from_slice(&out_buffer);
357 blake2b(&mut out_buffer, &[&in_buffer]);
358 out[out_pos..out_pos + ai_len].clone_from_slice(&out_buffer[0..ai_len]);
359 out_pos += ai_len;
360 to_produce -= ai_len;
361 }
362 blake2b(&mut out[out_pos..out_len], &[&out_buffer]);
363 }
364 }
365
index_alpha(context: &Context, position: &Position, pseudo_rand: u32, same_lane: bool) -> u32366 fn index_alpha(context: &Context, position: &Position, pseudo_rand: u32, same_lane: bool) -> u32 {
367 // Pass 0:
368 // - This lane: all already finished segments plus already constructed blocks in this segment
369 // - Other lanes: all already finished segments
370 // Pass 1+:
371 // - This lane: (SYNC_POINTS - 1) last segments plus already constructed blocks in this segment
372 // - Other lanes : (SYNC_POINTS - 1) last segments
373 let reference_area_size: u32 = if position.pass == 0 {
374 // First pass
375 if position.slice == 0 {
376 // First slice
377 position.index - 1
378 } else if same_lane {
379 // The same lane => add current segment
380 position.slice * context.segment_length + position.index - 1
381 } else if position.index == 0 {
382 position.slice * context.segment_length - 1
383 } else {
384 position.slice * context.segment_length
385 }
386 } else {
387 // Second pass
388 if same_lane {
389 context.lane_length - context.segment_length + position.index - 1
390 } else if position.index == 0 {
391 context.lane_length - context.segment_length - 1
392 } else {
393 context.lane_length - context.segment_length
394 }
395 };
396 let reference_area_size = reference_area_size as u64;
397 let mut relative_position = pseudo_rand as u64;
398 relative_position = (relative_position * relative_position) >> 32;
399 relative_position = reference_area_size - 1 - ((reference_area_size * relative_position) >> 32);
400
401 // 1.2.5 Computing starting position
402 let start_position: u32 = if position.pass != 0 {
403 if position.slice == common::SYNC_POINTS - 1 {
404 0u32
405 } else {
406 (position.slice + 1) * context.segment_length
407 }
408 } else {
409 0u32
410 };
411 let start_position = start_position as u64;
412
413 // 1.2.6. Computing absolute position
414 ((start_position + relative_position) % context.lane_length as u64) as u32
415 }
416
len_as_32le(slice: &[u8]) -> [u8; 4]417 fn len_as_32le(slice: &[u8]) -> [u8; 4] {
418 u32_as_32le(slice.len() as u32)
419 }
420
next_addresses(address_block: &mut Block, input_block: &mut Block, zero_block: &Block)421 fn next_addresses(address_block: &mut Block, input_block: &mut Block, zero_block: &Block) {
422 input_block[6] += 1;
423 fill_block(zero_block, input_block, address_block, false);
424 fill_block(zero_block, &address_block.clone(), address_block, false);
425 }
426
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, )427 fn p(
428 v0: &mut u64,
429 v1: &mut u64,
430 v2: &mut u64,
431 v3: &mut u64,
432 v4: &mut u64,
433 v5: &mut u64,
434 v6: &mut u64,
435 v7: &mut u64,
436 v8: &mut u64,
437 v9: &mut u64,
438 v10: &mut u64,
439 v11: &mut u64,
440 v12: &mut u64,
441 v13: &mut u64,
442 v14: &mut u64,
443 v15: &mut u64,
444 ) {
445 g(v0, v4, v8, v12);
446 g(v1, v5, v9, v13);
447 g(v2, v6, v10, v14);
448 g(v3, v7, v11, v15);
449 g(v0, v5, v10, v15);
450 g(v1, v6, v11, v12);
451 g(v2, v7, v8, v13);
452 g(v3, v4, v9, v14);
453 }
454
rotr64(w: u64, c: u32) -> u64455 fn rotr64(w: u64, c: u32) -> u64 {
456 (w >> c) | (w << (64 - c))
457 }
458
u32_as_32le(val: u32) -> [u8; 4]459 fn u32_as_32le(val: u32) -> [u8; 4] {
460 unsafe { mem::transmute(val.to_le()) }
461 }
462