1 /* ====================================================================
2 * Copyright (c) 2014 The OpenSSL Project. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in
13 * the documentation and/or other materials provided with the
16 * 3. All advertising materials mentioning features or use of this
17 * software must display the following acknowledgment:
18 * "This product includes software developed by the OpenSSL Project
19 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
21 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
22 * endorse or promote products derived from this software without
23 * prior written permission. For written permission, please contact
24 * openssl-core@openssl.org.
26 * 5. Products derived from this software may not be called "OpenSSL"
27 * nor may "OpenSSL" appear in their names without prior written
28 * permission of the OpenSSL Project.
30 * 6. Redistributions of any form whatsoever must retain the following
32 * "This product includes software developed by the OpenSSL Project
33 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
35 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
36 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
37 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
38 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
39 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
41 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
42 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
43 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
44 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
45 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
46 * OF THE POSSIBILITY OF SUCH DAMAGE.
47 * ====================================================================
51 #include <openssl/crypto.h>
52 #include "modes_lcl.h"
54 #ifndef OPENSSL_NO_OCB
57 unsigned char *chrblk;
62 * Calculate the number of binary trailing zero's in any given number
64 static u32 ocb_ntz(u64 n)
69 * We do a right-to-left simple sequential search. This is surprisingly
70 * efficient as the distribution of trailing zeros is not uniform,
71 * e.g. the number of possible inputs with no trailing zeros is equal to
72 * the number with 1 or more; the number with exactly 1 is equal to the
73 * number with 2 or more, etc. Checking the last two bits covers 75% of
74 * all numbers. Checking the last three covers 87.5%
84 * Shift a block of 16 bytes left by shift bits
86 static void ocb_block_lshift(OCB_BLOCK *in, size_t shift, OCB_BLOCK *out)
88 unsigned char shift_mask;
90 unsigned char mask[15];
98 shift_mask <<= (8 - shift);
99 for (i = 15; i >= 0; i--) {
101 mask[i - 1] = locin.chrblk[i] & shift_mask;
102 mask[i - 1] >>= 8 - shift;
104 locout.chrblk[i] = locin.chrblk[i] << shift;
107 locout.chrblk[i] ^= mask[i];
113 * Perform a "double" operation as per OCB spec
115 static void ocb_double(OCB_BLOCK *in, OCB_BLOCK *out)
125 * Calculate the mask based on the most significant bit. There are more
126 * efficient ways to do this - but this way is constant time
128 mask = locin.chrblk[0] & 0x80;
132 ocb_block_lshift(in, 1, out);
134 locout.chrblk[15] ^= mask;
138 * Perform an xor on in1 and in2 - each of len bytes. Store result in out
140 static void ocb_block_xor(const unsigned char *in1,
141 const unsigned char *in2, size_t len,
145 for (i = 0; i < len; i++) {
146 out[i] = in1[i] ^ in2[i];
151 * Lookup L_index in our lookup table. If we haven't already got it we need to
154 static OCB_BLOCK *ocb_lookup_l(OCB128_CONTEXT *ctx, size_t idx)
156 size_t l_index = ctx->l_index;
158 if (idx <= l_index) {
162 /* We don't have it - so calculate it */
163 if (idx >= ctx->max_l_index) {
165 * Each additional entry allows to process almost double as
166 * much data, so that in linear world the table will need to
167 * be expanded with smaller and smaller increments. Originally
168 * it was doubling in size, which was a waste. Growing it
169 * linearly is not formally optimal, but is simpler to implement.
170 * We grow table by minimally required 4*n that would accommodate
173 ctx->max_l_index += (idx - ctx->max_l_index + 4) & ~3;
175 OPENSSL_realloc(ctx->l, ctx->max_l_index * sizeof(OCB_BLOCK));
179 while (l_index <= idx) {
180 ocb_double(ctx->l + l_index, ctx->l + l_index + 1);
183 ctx->l_index = l_index;
189 * Encrypt a block from |in| and store the result in |out|
191 static void ocb_encrypt(OCB128_CONTEXT *ctx, OCB_BLOCK *in, OCB_BLOCK *out,
200 ctx->encrypt(locin.chrblk, locout.chrblk, keyenc);
204 * Decrypt a block from |in| and store the result in |out|
206 static void ocb_decrypt(OCB128_CONTEXT *ctx, OCB_BLOCK *in, OCB_BLOCK *out,
215 ctx->decrypt(locin.chrblk, locout.chrblk, keydec);
219 * Create a new OCB128_CONTEXT
221 OCB128_CONTEXT *CRYPTO_ocb128_new(void *keyenc, void *keydec,
222 block128_f encrypt, block128_f decrypt)
224 OCB128_CONTEXT *octx;
227 if ((octx = OPENSSL_malloc(sizeof(*octx))) != NULL) {
228 ret = CRYPTO_ocb128_init(octx, keyenc, keydec, encrypt, decrypt);
238 * Initialise an existing OCB128_CONTEXT
240 int CRYPTO_ocb128_init(OCB128_CONTEXT *ctx, void *keyenc, void *keydec,
241 block128_f encrypt, block128_f decrypt)
243 memset(ctx, 0, sizeof(*ctx));
245 ctx->max_l_index = 5;
246 ctx->l = OPENSSL_malloc(ctx->max_l_index * 16);
251 * We set both the encryption and decryption key schedules - decryption
252 * needs both. Don't really need decryption schedule if only doing
253 * encryption - but it simplifies things to take it anyway
255 ctx->encrypt = encrypt;
256 ctx->decrypt = decrypt;
257 ctx->keyenc = keyenc;
258 ctx->keydec = keydec;
260 /* L_* = ENCIPHER(K, zeros(128)) */
261 ocb_encrypt(ctx, &ctx->l_star, &ctx->l_star, ctx->keyenc);
263 /* L_$ = double(L_*) */
264 ocb_double(&ctx->l_star, &ctx->l_dollar);
266 /* L_0 = double(L_$) */
267 ocb_double(&ctx->l_dollar, ctx->l);
269 /* L_{i} = double(L_{i-1}) */
270 ocb_double(ctx->l, ctx->l+1);
271 ocb_double(ctx->l+1, ctx->l+2);
272 ocb_double(ctx->l+2, ctx->l+3);
273 ocb_double(ctx->l+3, ctx->l+4);
274 ctx->l_index = 4; /* enough to process up to 496 bytes */
280 * Copy an OCB128_CONTEXT object
282 int CRYPTO_ocb128_copy_ctx(OCB128_CONTEXT *dest, OCB128_CONTEXT *src,
283 void *keyenc, void *keydec)
285 memcpy(dest, src, sizeof(OCB128_CONTEXT));
287 dest->keyenc = keyenc;
289 dest->keydec = keydec;
291 dest->l = OPENSSL_malloc(src->max_l_index * 16);
294 memcpy(dest->l, src->l, (src->l_index + 1) * 16);
300 * Set the IV to be used for this operation. Must be 1 - 15 bytes.
302 int CRYPTO_ocb128_setiv(OCB128_CONTEXT *ctx, const unsigned char *iv,
303 size_t len, size_t taglen)
305 unsigned char ktop[16], tmp[16], mask;
306 unsigned char stretch[24], nonce[16];
307 size_t bottom, shift;
310 offset.ocbblk = &ctx->offset;
313 * Spec says IV is 120 bits or fewer - it allows non byte aligned lengths.
314 * We don't support this at this stage
316 if ((len > 15) || (len < 1) || (taglen > 16) || (taglen < 1)) {
320 /* Nonce = num2str(TAGLEN mod 128,7) || zeros(120-bitlen(N)) || 1 || N */
321 nonce[0] = ((taglen * 8) % 128) << 1;
322 memset(nonce + 1, 0, 15);
323 memcpy(nonce + 16 - len, iv, len);
324 nonce[15 - len] |= 1;
326 /* Ktop = ENCIPHER(K, Nonce[1..122] || zeros(6)) */
327 memcpy(tmp, nonce, 16);
329 ctx->encrypt(tmp, ktop, ctx->keyenc);
331 /* Stretch = Ktop || (Ktop[1..64] xor Ktop[9..72]) */
332 memcpy(stretch, ktop, 16);
333 ocb_block_xor(ktop, ktop + 1, 8, stretch + 16);
335 /* bottom = str2num(Nonce[123..128]) */
336 bottom = nonce[15] & 0x3f;
338 /* Offset_0 = Stretch[1+bottom..128+bottom] */
340 ocb_block_lshift((OCB_BLOCK *)(stretch + (bottom / 8)), shift,
345 (*(stretch + (bottom / 8) + 16) & mask) >> (8 - shift);
351 * Provide any AAD. This can be called multiple times. Only the final time can
352 * have a partial block
354 int CRYPTO_ocb128_aad(OCB128_CONTEXT *ctx, const unsigned char *aad,
357 u64 all_num_blocks, num_blocks;
363 /* Calculate the number of blocks of AAD provided now, and so far */
364 num_blocks = len / 16;
365 all_num_blocks = num_blocks + ctx->blocks_hashed;
367 /* Loop through all full blocks of AAD */
368 for (i = ctx->blocks_hashed + 1; i <= all_num_blocks; i++) {
370 OCB_BLOCK *aad_block;
372 /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
373 lookup = ocb_lookup_l(ctx, ocb_ntz(i));
376 ocb_block16_xor(&ctx->offset_aad, lookup, &ctx->offset_aad);
378 /* Sum_i = Sum_{i-1} xor ENCIPHER(K, A_i xor Offset_i) */
379 aad_block = (OCB_BLOCK *)(aad + ((i - ctx->blocks_hashed - 1) * 16));
380 ocb_block16_xor(&ctx->offset_aad, aad_block, &tmp1);
381 ocb_encrypt(ctx, &tmp1, &tmp2, ctx->keyenc);
382 ocb_block16_xor(&ctx->sum, &tmp2, &ctx->sum);
386 * Check if we have any partial blocks left over. This is only valid in the
387 * last call to this function
392 /* Offset_* = Offset_m xor L_* */
393 ocb_block16_xor(&ctx->offset_aad, &ctx->l_star, &ctx->offset_aad);
395 /* CipherInput = (A_* || 1 || zeros(127-bitlen(A_*))) xor Offset_* */
396 memset(&tmp1, 0, 16);
397 memcpy(&tmp1, aad + (num_blocks * 16), last_len);
398 ((unsigned char *)&tmp1)[last_len] = 0x80;
399 ocb_block16_xor(&ctx->offset_aad, &tmp1, &tmp2);
401 /* Sum = Sum_m xor ENCIPHER(K, CipherInput) */
402 ocb_encrypt(ctx, &tmp2, &tmp1, ctx->keyenc);
403 ocb_block16_xor(&ctx->sum, &tmp1, &ctx->sum);
406 ctx->blocks_hashed = all_num_blocks;
412 * Provide any data to be encrypted. This can be called multiple times. Only
413 * the final time can have a partial block
415 int CRYPTO_ocb128_encrypt(OCB128_CONTEXT *ctx,
416 const unsigned char *in, unsigned char *out,
420 u64 all_num_blocks, num_blocks;
427 * Calculate the number of blocks of data to be encrypted provided now, and
430 num_blocks = len / 16;
431 all_num_blocks = num_blocks + ctx->blocks_processed;
433 /* Loop through all full blocks to be encrypted */
434 for (i = ctx->blocks_processed + 1; i <= all_num_blocks; i++) {
439 /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
440 lookup = ocb_lookup_l(ctx, ocb_ntz(i));
443 ocb_block16_xor(&ctx->offset, lookup, &ctx->offset);
445 /* C_i = Offset_i xor ENCIPHER(K, P_i xor Offset_i) */
446 inblock = (OCB_BLOCK *)(in + ((i - ctx->blocks_processed - 1) * 16));
447 ocb_block16_xor(&ctx->offset, inblock, &tmp1);
448 /* Checksum_i = Checksum_{i-1} xor P_i */
449 ocb_block16_xor(&ctx->checksum, inblock, &ctx->checksum);
450 ocb_encrypt(ctx, &tmp1, &tmp2, ctx->keyenc);
452 (OCB_BLOCK *)(out + ((i - ctx->blocks_processed - 1) * 16));
453 ocb_block16_xor(&ctx->offset, &tmp2, outblock);
458 * Check if we have any partial blocks left over. This is only valid in the
459 * last call to this function
464 /* Offset_* = Offset_m xor L_* */
465 ocb_block16_xor(&ctx->offset, &ctx->l_star, &ctx->offset);
467 /* Pad = ENCIPHER(K, Offset_*) */
468 ocb_encrypt(ctx, &ctx->offset, &pad, ctx->keyenc);
470 /* C_* = P_* xor Pad[1..bitlen(P_*)] */
471 ocb_block_xor(in + (len / 16) * 16, (unsigned char *)&pad, last_len,
472 out + (num_blocks * 16));
474 /* Checksum_* = Checksum_m xor (P_* || 1 || zeros(127-bitlen(P_*))) */
475 memset(&tmp1, 0, 16);
476 memcpy(&tmp1, in + (len / 16) * 16, last_len);
477 ((unsigned char *)(&tmp1))[last_len] = 0x80;
478 ocb_block16_xor(&ctx->checksum, &tmp1, &ctx->checksum);
481 ctx->blocks_processed = all_num_blocks;
487 * Provide any data to be decrypted. This can be called multiple times. Only
488 * the final time can have a partial block
490 int CRYPTO_ocb128_decrypt(OCB128_CONTEXT *ctx,
491 const unsigned char *in, unsigned char *out,
495 u64 all_num_blocks, num_blocks;
501 * Calculate the number of blocks of data to be decrypted provided now, and
504 num_blocks = len / 16;
505 all_num_blocks = num_blocks + ctx->blocks_processed;
507 /* Loop through all full blocks to be decrypted */
508 for (i = ctx->blocks_processed + 1; i <= all_num_blocks; i++) {
512 /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
513 OCB_BLOCK *lookup = ocb_lookup_l(ctx, ocb_ntz(i));
516 ocb_block16_xor(&ctx->offset, lookup, &ctx->offset);
518 /* P_i = Offset_i xor DECIPHER(K, C_i xor Offset_i) */
519 inblock = (OCB_BLOCK *)(in + ((i - ctx->blocks_processed - 1) * 16));
520 ocb_block16_xor(&ctx->offset, inblock, &tmp1);
521 ocb_decrypt(ctx, &tmp1, &tmp2, ctx->keydec);
523 (OCB_BLOCK *)(out + ((i - ctx->blocks_processed - 1) * 16));
524 ocb_block16_xor(&ctx->offset, &tmp2, outblock);
526 /* Checksum_i = Checksum_{i-1} xor P_i */
527 ocb_block16_xor(&ctx->checksum, outblock, &ctx->checksum);
531 * Check if we have any partial blocks left over. This is only valid in the
532 * last call to this function
537 /* Offset_* = Offset_m xor L_* */
538 ocb_block16_xor(&ctx->offset, &ctx->l_star, &ctx->offset);
540 /* Pad = ENCIPHER(K, Offset_*) */
541 ocb_encrypt(ctx, &ctx->offset, &pad, ctx->keyenc);
543 /* P_* = C_* xor Pad[1..bitlen(C_*)] */
544 ocb_block_xor(in + (len / 16) * 16, (unsigned char *)&pad, last_len,
545 out + (num_blocks * 16));
547 /* Checksum_* = Checksum_m xor (P_* || 1 || zeros(127-bitlen(P_*))) */
548 memset(&tmp1, 0, 16);
549 memcpy(&tmp1, out + (len / 16) * 16, last_len);
550 ((unsigned char *)(&tmp1))[last_len] = 0x80;
551 ocb_block16_xor(&ctx->checksum, &tmp1, &ctx->checksum);
554 ctx->blocks_processed = all_num_blocks;
560 * Calculate the tag and verify it against the supplied tag
562 int CRYPTO_ocb128_finish(OCB128_CONTEXT *ctx, const unsigned char *tag,
565 OCB_BLOCK tmp1, tmp2;
568 * Tag = ENCIPHER(K, Checksum_* xor Offset_* xor L_$) xor HASH(K,A)
570 ocb_block16_xor(&ctx->checksum, &ctx->offset, &tmp1);
571 ocb_block16_xor(&tmp1, &ctx->l_dollar, &tmp2);
572 ocb_encrypt(ctx, &tmp2, &tmp1, ctx->keyenc);
573 ocb_block16_xor(&tmp1, &ctx->sum, &ctx->tag);
575 if (len > 16 || len < 1) {
579 /* Compare the tag if we've been given one */
581 return CRYPTO_memcmp(&ctx->tag, tag, len);
587 * Retrieve the calculated tag
589 int CRYPTO_ocb128_tag(OCB128_CONTEXT *ctx, unsigned char *tag, size_t len)
591 if (len > 16 || len < 1) {
595 /* Calculate the tag */
596 CRYPTO_ocb128_finish(ctx, NULL, 0);
598 /* Copy the tag into the supplied buffer */
599 memcpy(tag, &ctx->tag, len);
605 * Release all resources
607 void CRYPTO_ocb128_cleanup(OCB128_CONTEXT *ctx)
610 OPENSSL_clear_free(ctx->l, ctx->max_l_index * 16);
611 OPENSSL_cleanse(ctx, sizeof(*ctx));
615 #endif /* OPENSSL_NO_OCB */