1 | /* |
2 | * Copyright 2014-2018 The OpenSSL Project Authors. All Rights Reserved. |
3 | * |
4 | * Licensed under the Apache License 2.0 (the "License"). You may not use |
5 | * this file except in compliance with the License. You can obtain a copy |
6 | * in the file LICENSE in the source distribution or at |
7 | * https://www.openssl.org/source/license.html |
8 | */ |
9 | |
10 | #include <string.h> |
11 | #include <openssl/crypto.h> |
12 | #include <openssl/err.h> |
13 | #include "crypto/modes.h" |
14 | |
15 | #ifndef OPENSSL_NO_OCB |
16 | |
17 | /* |
18 | * Calculate the number of binary trailing zero's in any given number |
19 | */ |
20 | static u32 ocb_ntz(u64 n) |
21 | { |
22 | u32 cnt = 0; |
23 | |
24 | /* |
25 | * We do a right-to-left simple sequential search. This is surprisingly |
26 | * efficient as the distribution of trailing zeros is not uniform, |
27 | * e.g. the number of possible inputs with no trailing zeros is equal to |
28 | * the number with 1 or more; the number with exactly 1 is equal to the |
29 | * number with 2 or more, etc. Checking the last two bits covers 75% of |
30 | * all numbers. Checking the last three covers 87.5% |
31 | */ |
32 | while (!(n & 1)) { |
33 | n >>= 1; |
34 | cnt++; |
35 | } |
36 | return cnt; |
37 | } |
38 | |
39 | /* |
40 | * Shift a block of 16 bytes left by shift bits |
41 | */ |
42 | static void ocb_block_lshift(const unsigned char *in, size_t shift, |
43 | unsigned char *out) |
44 | { |
45 | int i; |
46 | unsigned char carry = 0, carry_next; |
47 | |
48 | for (i = 15; i >= 0; i--) { |
49 | carry_next = in[i] >> (8 - shift); |
50 | out[i] = (in[i] << shift) | carry; |
51 | carry = carry_next; |
52 | } |
53 | } |
54 | |
55 | /* |
56 | * Perform a "double" operation as per OCB spec |
57 | */ |
58 | static void ocb_double(OCB_BLOCK *in, OCB_BLOCK *out) |
59 | { |
60 | unsigned char mask; |
61 | |
62 | /* |
63 | * Calculate the mask based on the most significant bit. There are more |
64 | * efficient ways to do this - but this way is constant time |
65 | */ |
66 | mask = in->c[0] & 0x80; |
67 | mask >>= 7; |
68 | mask = (0 - mask) & 0x87; |
69 | |
70 | ocb_block_lshift(in->c, 1, out->c); |
71 | |
72 | out->c[15] ^= mask; |
73 | } |
74 | |
75 | /* |
76 | * Perform an xor on in1 and in2 - each of len bytes. Store result in out |
77 | */ |
78 | static void ocb_block_xor(const unsigned char *in1, |
79 | const unsigned char *in2, size_t len, |
80 | unsigned char *out) |
81 | { |
82 | size_t i; |
83 | for (i = 0; i < len; i++) { |
84 | out[i] = in1[i] ^ in2[i]; |
85 | } |
86 | } |
87 | |
88 | /* |
89 | * Lookup L_index in our lookup table. If we haven't already got it we need to |
90 | * calculate it |
91 | */ |
92 | static OCB_BLOCK *ocb_lookup_l(OCB128_CONTEXT *ctx, size_t idx) |
93 | { |
94 | size_t l_index = ctx->l_index; |
95 | |
96 | if (idx <= l_index) { |
97 | return ctx->l + idx; |
98 | } |
99 | |
100 | /* We don't have it - so calculate it */ |
101 | if (idx >= ctx->max_l_index) { |
102 | void *tmp_ptr; |
103 | /* |
104 | * Each additional entry allows to process almost double as |
105 | * much data, so that in linear world the table will need to |
106 | * be expanded with smaller and smaller increments. Originally |
107 | * it was doubling in size, which was a waste. Growing it |
108 | * linearly is not formally optimal, but is simpler to implement. |
109 | * We grow table by minimally required 4*n that would accommodate |
110 | * the index. |
111 | */ |
112 | ctx->max_l_index += (idx - ctx->max_l_index + 4) & ~3; |
113 | tmp_ptr = OPENSSL_realloc(ctx->l, ctx->max_l_index * sizeof(OCB_BLOCK)); |
114 | if (tmp_ptr == NULL) /* prevent ctx->l from being clobbered */ |
115 | return NULL; |
116 | ctx->l = tmp_ptr; |
117 | } |
118 | while (l_index < idx) { |
119 | ocb_double(ctx->l + l_index, ctx->l + l_index + 1); |
120 | l_index++; |
121 | } |
122 | ctx->l_index = l_index; |
123 | |
124 | return ctx->l + idx; |
125 | } |
126 | |
127 | /* |
128 | * Create a new OCB128_CONTEXT |
129 | */ |
130 | OCB128_CONTEXT *CRYPTO_ocb128_new(void *keyenc, void *keydec, |
131 | block128_f encrypt, block128_f decrypt, |
132 | ocb128_f stream) |
133 | { |
134 | OCB128_CONTEXT *octx; |
135 | int ret; |
136 | |
137 | if ((octx = OPENSSL_malloc(sizeof(*octx))) != NULL) { |
138 | ret = CRYPTO_ocb128_init(octx, keyenc, keydec, encrypt, decrypt, |
139 | stream); |
140 | if (ret) |
141 | return octx; |
142 | OPENSSL_free(octx); |
143 | } |
144 | |
145 | return NULL; |
146 | } |
147 | |
148 | /* |
149 | * Initialise an existing OCB128_CONTEXT |
150 | */ |
151 | int CRYPTO_ocb128_init(OCB128_CONTEXT *ctx, void *keyenc, void *keydec, |
152 | block128_f encrypt, block128_f decrypt, |
153 | ocb128_f stream) |
154 | { |
155 | memset(ctx, 0, sizeof(*ctx)); |
156 | ctx->l_index = 0; |
157 | ctx->max_l_index = 5; |
158 | if ((ctx->l = OPENSSL_malloc(ctx->max_l_index * 16)) == NULL) { |
159 | CRYPTOerr(CRYPTO_F_CRYPTO_OCB128_INIT, ERR_R_MALLOC_FAILURE); |
160 | return 0; |
161 | } |
162 | |
163 | /* |
164 | * We set both the encryption and decryption key schedules - decryption |
165 | * needs both. Don't really need decryption schedule if only doing |
166 | * encryption - but it simplifies things to take it anyway |
167 | */ |
168 | ctx->encrypt = encrypt; |
169 | ctx->decrypt = decrypt; |
170 | ctx->stream = stream; |
171 | ctx->keyenc = keyenc; |
172 | ctx->keydec = keydec; |
173 | |
174 | /* L_* = ENCIPHER(K, zeros(128)) */ |
175 | ctx->encrypt(ctx->l_star.c, ctx->l_star.c, ctx->keyenc); |
176 | |
177 | /* L_$ = double(L_*) */ |
178 | ocb_double(&ctx->l_star, &ctx->l_dollar); |
179 | |
180 | /* L_0 = double(L_$) */ |
181 | ocb_double(&ctx->l_dollar, ctx->l); |
182 | |
183 | /* L_{i} = double(L_{i-1}) */ |
184 | ocb_double(ctx->l, ctx->l+1); |
185 | ocb_double(ctx->l+1, ctx->l+2); |
186 | ocb_double(ctx->l+2, ctx->l+3); |
187 | ocb_double(ctx->l+3, ctx->l+4); |
188 | ctx->l_index = 4; /* enough to process up to 496 bytes */ |
189 | |
190 | return 1; |
191 | } |
192 | |
193 | /* |
194 | * Copy an OCB128_CONTEXT object |
195 | */ |
196 | int CRYPTO_ocb128_copy_ctx(OCB128_CONTEXT *dest, OCB128_CONTEXT *src, |
197 | void *keyenc, void *keydec) |
198 | { |
199 | memcpy(dest, src, sizeof(OCB128_CONTEXT)); |
200 | if (keyenc) |
201 | dest->keyenc = keyenc; |
202 | if (keydec) |
203 | dest->keydec = keydec; |
204 | if (src->l) { |
205 | if ((dest->l = OPENSSL_malloc(src->max_l_index * 16)) == NULL) { |
206 | CRYPTOerr(CRYPTO_F_CRYPTO_OCB128_COPY_CTX, ERR_R_MALLOC_FAILURE); |
207 | return 0; |
208 | } |
209 | memcpy(dest->l, src->l, (src->l_index + 1) * 16); |
210 | } |
211 | return 1; |
212 | } |
213 | |
214 | /* |
215 | * Set the IV to be used for this operation. Must be 1 - 15 bytes. |
216 | */ |
217 | int CRYPTO_ocb128_setiv(OCB128_CONTEXT *ctx, const unsigned char *iv, |
218 | size_t len, size_t taglen) |
219 | { |
220 | unsigned char ktop[16], tmp[16], mask; |
221 | unsigned char stretch[24], nonce[16]; |
222 | size_t bottom, shift; |
223 | |
224 | /* |
225 | * Spec says IV is 120 bits or fewer - it allows non byte aligned lengths. |
226 | * We don't support this at this stage |
227 | */ |
228 | if ((len > 15) || (len < 1) || (taglen > 16) || (taglen < 1)) { |
229 | return -1; |
230 | } |
231 | |
232 | /* Reset nonce-dependent variables */ |
233 | memset(&ctx->sess, 0, sizeof(ctx->sess)); |
234 | |
235 | /* Nonce = num2str(TAGLEN mod 128,7) || zeros(120-bitlen(N)) || 1 || N */ |
236 | nonce[0] = ((taglen * 8) % 128) << 1; |
237 | memset(nonce + 1, 0, 15); |
238 | memcpy(nonce + 16 - len, iv, len); |
239 | nonce[15 - len] |= 1; |
240 | |
241 | /* Ktop = ENCIPHER(K, Nonce[1..122] || zeros(6)) */ |
242 | memcpy(tmp, nonce, 16); |
243 | tmp[15] &= 0xc0; |
244 | ctx->encrypt(tmp, ktop, ctx->keyenc); |
245 | |
246 | /* Stretch = Ktop || (Ktop[1..64] xor Ktop[9..72]) */ |
247 | memcpy(stretch, ktop, 16); |
248 | ocb_block_xor(ktop, ktop + 1, 8, stretch + 16); |
249 | |
250 | /* bottom = str2num(Nonce[123..128]) */ |
251 | bottom = nonce[15] & 0x3f; |
252 | |
253 | /* Offset_0 = Stretch[1+bottom..128+bottom] */ |
254 | shift = bottom % 8; |
255 | ocb_block_lshift(stretch + (bottom / 8), shift, ctx->sess.offset.c); |
256 | mask = 0xff; |
257 | mask <<= 8 - shift; |
258 | ctx->sess.offset.c[15] |= |
259 | (*(stretch + (bottom / 8) + 16) & mask) >> (8 - shift); |
260 | |
261 | return 1; |
262 | } |
263 | |
264 | /* |
265 | * Provide any AAD. This can be called multiple times. Only the final time can |
266 | * have a partial block |
267 | */ |
268 | int CRYPTO_ocb128_aad(OCB128_CONTEXT *ctx, const unsigned char *aad, |
269 | size_t len) |
270 | { |
271 | u64 i, all_num_blocks; |
272 | size_t num_blocks, last_len; |
273 | OCB_BLOCK tmp; |
274 | |
275 | /* Calculate the number of blocks of AAD provided now, and so far */ |
276 | num_blocks = len / 16; |
277 | all_num_blocks = num_blocks + ctx->sess.blocks_hashed; |
278 | |
279 | /* Loop through all full blocks of AAD */ |
280 | for (i = ctx->sess.blocks_hashed + 1; i <= all_num_blocks; i++) { |
281 | OCB_BLOCK *lookup; |
282 | |
283 | /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */ |
284 | lookup = ocb_lookup_l(ctx, ocb_ntz(i)); |
285 | if (lookup == NULL) |
286 | return 0; |
287 | ocb_block16_xor(&ctx->sess.offset_aad, lookup, &ctx->sess.offset_aad); |
288 | |
289 | memcpy(tmp.c, aad, 16); |
290 | aad += 16; |
291 | |
292 | /* Sum_i = Sum_{i-1} xor ENCIPHER(K, A_i xor Offset_i) */ |
293 | ocb_block16_xor(&ctx->sess.offset_aad, &tmp, &tmp); |
294 | ctx->encrypt(tmp.c, tmp.c, ctx->keyenc); |
295 | ocb_block16_xor(&tmp, &ctx->sess.sum, &ctx->sess.sum); |
296 | } |
297 | |
298 | /* |
299 | * Check if we have any partial blocks left over. This is only valid in the |
300 | * last call to this function |
301 | */ |
302 | last_len = len % 16; |
303 | |
304 | if (last_len > 0) { |
305 | /* Offset_* = Offset_m xor L_* */ |
306 | ocb_block16_xor(&ctx->sess.offset_aad, &ctx->l_star, |
307 | &ctx->sess.offset_aad); |
308 | |
309 | /* CipherInput = (A_* || 1 || zeros(127-bitlen(A_*))) xor Offset_* */ |
310 | memset(tmp.c, 0, 16); |
311 | memcpy(tmp.c, aad, last_len); |
312 | tmp.c[last_len] = 0x80; |
313 | ocb_block16_xor(&ctx->sess.offset_aad, &tmp, &tmp); |
314 | |
315 | /* Sum = Sum_m xor ENCIPHER(K, CipherInput) */ |
316 | ctx->encrypt(tmp.c, tmp.c, ctx->keyenc); |
317 | ocb_block16_xor(&tmp, &ctx->sess.sum, &ctx->sess.sum); |
318 | } |
319 | |
320 | ctx->sess.blocks_hashed = all_num_blocks; |
321 | |
322 | return 1; |
323 | } |
324 | |
325 | /* |
326 | * Provide any data to be encrypted. This can be called multiple times. Only |
327 | * the final time can have a partial block |
328 | */ |
329 | int CRYPTO_ocb128_encrypt(OCB128_CONTEXT *ctx, |
330 | const unsigned char *in, unsigned char *out, |
331 | size_t len) |
332 | { |
333 | u64 i, all_num_blocks; |
334 | size_t num_blocks, last_len; |
335 | |
336 | /* |
337 | * Calculate the number of blocks of data to be encrypted provided now, and |
338 | * so far |
339 | */ |
340 | num_blocks = len / 16; |
341 | all_num_blocks = num_blocks + ctx->sess.blocks_processed; |
342 | |
343 | if (num_blocks && all_num_blocks == (size_t)all_num_blocks |
344 | && ctx->stream != NULL) { |
345 | size_t max_idx = 0, top = (size_t)all_num_blocks; |
346 | |
347 | /* |
348 | * See how many L_{i} entries we need to process data at hand |
349 | * and pre-compute missing entries in the table [if any]... |
350 | */ |
351 | while (top >>= 1) |
352 | max_idx++; |
353 | if (ocb_lookup_l(ctx, max_idx) == NULL) |
354 | return 0; |
355 | |
356 | ctx->stream(in, out, num_blocks, ctx->keyenc, |
357 | (size_t)ctx->sess.blocks_processed + 1, ctx->sess.offset.c, |
358 | (const unsigned char (*)[16])ctx->l, ctx->sess.checksum.c); |
359 | } else { |
360 | /* Loop through all full blocks to be encrypted */ |
361 | for (i = ctx->sess.blocks_processed + 1; i <= all_num_blocks; i++) { |
362 | OCB_BLOCK *lookup; |
363 | OCB_BLOCK tmp; |
364 | |
365 | /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */ |
366 | lookup = ocb_lookup_l(ctx, ocb_ntz(i)); |
367 | if (lookup == NULL) |
368 | return 0; |
369 | ocb_block16_xor(&ctx->sess.offset, lookup, &ctx->sess.offset); |
370 | |
371 | memcpy(tmp.c, in, 16); |
372 | in += 16; |
373 | |
374 | /* Checksum_i = Checksum_{i-1} xor P_i */ |
375 | ocb_block16_xor(&tmp, &ctx->sess.checksum, &ctx->sess.checksum); |
376 | |
377 | /* C_i = Offset_i xor ENCIPHER(K, P_i xor Offset_i) */ |
378 | ocb_block16_xor(&ctx->sess.offset, &tmp, &tmp); |
379 | ctx->encrypt(tmp.c, tmp.c, ctx->keyenc); |
380 | ocb_block16_xor(&ctx->sess.offset, &tmp, &tmp); |
381 | |
382 | memcpy(out, tmp.c, 16); |
383 | out += 16; |
384 | } |
385 | } |
386 | |
387 | /* |
388 | * Check if we have any partial blocks left over. This is only valid in the |
389 | * last call to this function |
390 | */ |
391 | last_len = len % 16; |
392 | |
393 | if (last_len > 0) { |
394 | OCB_BLOCK pad; |
395 | |
396 | /* Offset_* = Offset_m xor L_* */ |
397 | ocb_block16_xor(&ctx->sess.offset, &ctx->l_star, &ctx->sess.offset); |
398 | |
399 | /* Pad = ENCIPHER(K, Offset_*) */ |
400 | ctx->encrypt(ctx->sess.offset.c, pad.c, ctx->keyenc); |
401 | |
402 | /* C_* = P_* xor Pad[1..bitlen(P_*)] */ |
403 | ocb_block_xor(in, pad.c, last_len, out); |
404 | |
405 | /* Checksum_* = Checksum_m xor (P_* || 1 || zeros(127-bitlen(P_*))) */ |
406 | memset(pad.c, 0, 16); /* borrow pad */ |
407 | memcpy(pad.c, in, last_len); |
408 | pad.c[last_len] = 0x80; |
409 | ocb_block16_xor(&pad, &ctx->sess.checksum, &ctx->sess.checksum); |
410 | } |
411 | |
412 | ctx->sess.blocks_processed = all_num_blocks; |
413 | |
414 | return 1; |
415 | } |
416 | |
417 | /* |
418 | * Provide any data to be decrypted. This can be called multiple times. Only |
419 | * the final time can have a partial block |
420 | */ |
421 | int CRYPTO_ocb128_decrypt(OCB128_CONTEXT *ctx, |
422 | const unsigned char *in, unsigned char *out, |
423 | size_t len) |
424 | { |
425 | u64 i, all_num_blocks; |
426 | size_t num_blocks, last_len; |
427 | |
428 | /* |
429 | * Calculate the number of blocks of data to be decrypted provided now, and |
430 | * so far |
431 | */ |
432 | num_blocks = len / 16; |
433 | all_num_blocks = num_blocks + ctx->sess.blocks_processed; |
434 | |
435 | if (num_blocks && all_num_blocks == (size_t)all_num_blocks |
436 | && ctx->stream != NULL) { |
437 | size_t max_idx = 0, top = (size_t)all_num_blocks; |
438 | |
439 | /* |
440 | * See how many L_{i} entries we need to process data at hand |
441 | * and pre-compute missing entries in the table [if any]... |
442 | */ |
443 | while (top >>= 1) |
444 | max_idx++; |
445 | if (ocb_lookup_l(ctx, max_idx) == NULL) |
446 | return 0; |
447 | |
448 | ctx->stream(in, out, num_blocks, ctx->keydec, |
449 | (size_t)ctx->sess.blocks_processed + 1, ctx->sess.offset.c, |
450 | (const unsigned char (*)[16])ctx->l, ctx->sess.checksum.c); |
451 | } else { |
452 | OCB_BLOCK tmp; |
453 | |
454 | /* Loop through all full blocks to be decrypted */ |
455 | for (i = ctx->sess.blocks_processed + 1; i <= all_num_blocks; i++) { |
456 | |
457 | /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */ |
458 | OCB_BLOCK *lookup = ocb_lookup_l(ctx, ocb_ntz(i)); |
459 | if (lookup == NULL) |
460 | return 0; |
461 | ocb_block16_xor(&ctx->sess.offset, lookup, &ctx->sess.offset); |
462 | |
463 | memcpy(tmp.c, in, 16); |
464 | in += 16; |
465 | |
466 | /* P_i = Offset_i xor DECIPHER(K, C_i xor Offset_i) */ |
467 | ocb_block16_xor(&ctx->sess.offset, &tmp, &tmp); |
468 | ctx->decrypt(tmp.c, tmp.c, ctx->keydec); |
469 | ocb_block16_xor(&ctx->sess.offset, &tmp, &tmp); |
470 | |
471 | /* Checksum_i = Checksum_{i-1} xor P_i */ |
472 | ocb_block16_xor(&tmp, &ctx->sess.checksum, &ctx->sess.checksum); |
473 | |
474 | memcpy(out, tmp.c, 16); |
475 | out += 16; |
476 | } |
477 | } |
478 | |
479 | /* |
480 | * Check if we have any partial blocks left over. This is only valid in the |
481 | * last call to this function |
482 | */ |
483 | last_len = len % 16; |
484 | |
485 | if (last_len > 0) { |
486 | OCB_BLOCK pad; |
487 | |
488 | /* Offset_* = Offset_m xor L_* */ |
489 | ocb_block16_xor(&ctx->sess.offset, &ctx->l_star, &ctx->sess.offset); |
490 | |
491 | /* Pad = ENCIPHER(K, Offset_*) */ |
492 | ctx->encrypt(ctx->sess.offset.c, pad.c, ctx->keyenc); |
493 | |
494 | /* P_* = C_* xor Pad[1..bitlen(C_*)] */ |
495 | ocb_block_xor(in, pad.c, last_len, out); |
496 | |
497 | /* Checksum_* = Checksum_m xor (P_* || 1 || zeros(127-bitlen(P_*))) */ |
498 | memset(pad.c, 0, 16); /* borrow pad */ |
499 | memcpy(pad.c, out, last_len); |
500 | pad.c[last_len] = 0x80; |
501 | ocb_block16_xor(&pad, &ctx->sess.checksum, &ctx->sess.checksum); |
502 | } |
503 | |
504 | ctx->sess.blocks_processed = all_num_blocks; |
505 | |
506 | return 1; |
507 | } |
508 | |
509 | static int ocb_finish(OCB128_CONTEXT *ctx, unsigned char *tag, size_t len, |
510 | int write) |
511 | { |
512 | OCB_BLOCK tmp; |
513 | |
514 | if (len > 16 || len < 1) { |
515 | return -1; |
516 | } |
517 | |
518 | /* |
519 | * Tag = ENCIPHER(K, Checksum_* xor Offset_* xor L_$) xor HASH(K,A) |
520 | */ |
521 | ocb_block16_xor(&ctx->sess.checksum, &ctx->sess.offset, &tmp); |
522 | ocb_block16_xor(&ctx->l_dollar, &tmp, &tmp); |
523 | ctx->encrypt(tmp.c, tmp.c, ctx->keyenc); |
524 | ocb_block16_xor(&tmp, &ctx->sess.sum, &tmp); |
525 | |
526 | if (write) { |
527 | memcpy(tag, &tmp, len); |
528 | return 1; |
529 | } else { |
530 | return CRYPTO_memcmp(&tmp, tag, len); |
531 | } |
532 | } |
533 | |
534 | /* |
535 | * Calculate the tag and verify it against the supplied tag |
536 | */ |
537 | int CRYPTO_ocb128_finish(OCB128_CONTEXT *ctx, const unsigned char *tag, |
538 | size_t len) |
539 | { |
540 | return ocb_finish(ctx, (unsigned char*)tag, len, 0); |
541 | } |
542 | |
543 | /* |
544 | * Retrieve the calculated tag |
545 | */ |
546 | int CRYPTO_ocb128_tag(OCB128_CONTEXT *ctx, unsigned char *tag, size_t len) |
547 | { |
548 | return ocb_finish(ctx, tag, len, 1); |
549 | } |
550 | |
551 | /* |
552 | * Release all resources |
553 | */ |
554 | void CRYPTO_ocb128_cleanup(OCB128_CONTEXT *ctx) |
555 | { |
556 | if (ctx) { |
557 | OPENSSL_clear_free(ctx->l, ctx->max_l_index * 16); |
558 | OPENSSL_cleanse(ctx, sizeof(*ctx)); |
559 | } |
560 | } |
561 | |
562 | #endif /* OPENSSL_NO_OCB */ |
563 | |