modes/ocb128.c: ocb_lookup_l to allow non-contiguous lookup
[openssl.git] / crypto / modes / ocb128.c
1 /* ====================================================================
2  * Copyright (c) 2014 The OpenSSL Project.  All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  *
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
14  *    distribution.
15  *
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/)"
20  *
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.
25  *
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.
29  *
30  * 6. Redistributions of any form whatsoever must retain the following
31  *    acknowledgment:
32  *    "This product includes software developed by the OpenSSL Project
33  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
34  *
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  * ====================================================================
48  */
49
50 #include <string.h>
51 #include <openssl/crypto.h>
52 #include "modes_lcl.h"
53
54 #ifndef OPENSSL_NO_OCB
55
56 union ublock {
57     unsigned char *chrblk;
58     OCB_BLOCK *ocbblk;
59 };
60
61 /*
62  * Calculate the number of binary trailing zero's in any given number
63  */
64 static u32 ocb_ntz(u64 n)
65 {
66     u32 cnt = 0;
67
68     /*
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%
75      */
76     while (!(n & 1)) {
77         n >>= 1;
78         cnt++;
79     }
80     return cnt;
81 }
82
83 /*
84  * Shift a block of 16 bytes left by shift bits
85  */
86 static void ocb_block_lshift(OCB_BLOCK *in, size_t shift, OCB_BLOCK *out)
87 {
88     unsigned char shift_mask;
89     int i;
90     unsigned char mask[15];
91     union ublock locin;
92     union ublock locout;
93
94     locin.ocbblk = in;
95     locout.ocbblk = out;
96
97     shift_mask = 0xff;
98     shift_mask <<= (8 - shift);
99     for (i = 15; i >= 0; i--) {
100         if (i > 0) {
101             mask[i - 1] = locin.chrblk[i] & shift_mask;
102             mask[i - 1] >>= 8 - shift;
103         }
104         locout.chrblk[i] = locin.chrblk[i] << shift;
105
106         if (i != 15) {
107             locout.chrblk[i] ^= mask[i];
108         }
109     }
110 }
111
112 /*
113  * Perform a "double" operation as per OCB spec
114  */
115 static void ocb_double(OCB_BLOCK *in, OCB_BLOCK *out)
116 {
117     unsigned char mask;
118     union ublock locin;
119     union ublock locout;
120
121     locin.ocbblk = in;
122     locout.ocbblk = out;
123
124     /*
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
127      */
128     mask = locin.chrblk[0] & 0x80;
129     mask >>= 7;
130     mask *= 135;
131
132     ocb_block_lshift(in, 1, out);
133
134     locout.chrblk[15] ^= mask;
135 }
136
137 /*
138  * Perform an xor on in1 and in2 - each of len bytes. Store result in out
139  */
140 static void ocb_block_xor(const unsigned char *in1,
141                           const unsigned char *in2, size_t len,
142                           unsigned char *out)
143 {
144     size_t i;
145     for (i = 0; i < len; i++) {
146         out[i] = in1[i] ^ in2[i];
147     }
148 }
149
150 /*
151  * Lookup L_index in our lookup table. If we haven't already got it we need to
152  * calculate it
153  */
154 static OCB_BLOCK *ocb_lookup_l(OCB128_CONTEXT *ctx, size_t idx)
155 {
156     size_t l_index = ctx->l_index;
157
158     if (idx <= l_index) {
159         return ctx->l + idx;
160     }
161
162     /* We don't have it - so calculate it */
163     if (idx >= ctx->max_l_index) {
164         /*
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
171          * the index.
172          */
173         ctx->max_l_index += (idx - ctx->max_l_index + 4) & ~3;
174         ctx->l =
175             OPENSSL_realloc(ctx->l, ctx->max_l_index * sizeof(OCB_BLOCK));
176         if (!ctx->l)
177             return NULL;
178     }
179     while (l_index <= idx) {
180         ocb_double(ctx->l + l_index, ctx->l + l_index + 1);
181         l_index++;
182     }
183     ctx->l_index = l_index;
184
185     return ctx->l + idx;
186 }
187
188 /*
189  * Encrypt a block from |in| and store the result in |out|
190  */
191 static void ocb_encrypt(OCB128_CONTEXT *ctx, OCB_BLOCK *in, OCB_BLOCK *out,
192                         void *keyenc)
193 {
194     union ublock locin;
195     union ublock locout;
196
197     locin.ocbblk = in;
198     locout.ocbblk = out;
199
200     ctx->encrypt(locin.chrblk, locout.chrblk, keyenc);
201 }
202
203 /*
204  * Decrypt a block from |in| and store the result in |out|
205  */
206 static void ocb_decrypt(OCB128_CONTEXT *ctx, OCB_BLOCK *in, OCB_BLOCK *out,
207                         void *keydec)
208 {
209     union ublock locin;
210     union ublock locout;
211
212     locin.ocbblk = in;
213     locout.ocbblk = out;
214
215     ctx->decrypt(locin.chrblk, locout.chrblk, keydec);
216 }
217
218 /*
219  * Create a new OCB128_CONTEXT
220  */
221 OCB128_CONTEXT *CRYPTO_ocb128_new(void *keyenc, void *keydec,
222                                   block128_f encrypt, block128_f decrypt)
223 {
224     OCB128_CONTEXT *octx;
225     int ret;
226
227     if ((octx = OPENSSL_malloc(sizeof(*octx))) != NULL) {
228         ret = CRYPTO_ocb128_init(octx, keyenc, keydec, encrypt, decrypt);
229         if (ret)
230             return octx;
231         OPENSSL_free(octx);
232     }
233
234     return NULL;
235 }
236
237 /*
238  * Initialise an existing OCB128_CONTEXT
239  */
240 int CRYPTO_ocb128_init(OCB128_CONTEXT *ctx, void *keyenc, void *keydec,
241                        block128_f encrypt, block128_f decrypt)
242 {
243     memset(ctx, 0, sizeof(*ctx));
244     ctx->l_index = 0;
245     ctx->max_l_index = 5;
246     ctx->l = OPENSSL_malloc(ctx->max_l_index * 16);
247     if (ctx->l == NULL)
248         return 0;
249
250     /*
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
254      */
255     ctx->encrypt = encrypt;
256     ctx->decrypt = decrypt;
257     ctx->keyenc = keyenc;
258     ctx->keydec = keydec;
259
260     /* L_* = ENCIPHER(K, zeros(128)) */
261     ocb_encrypt(ctx, &ctx->l_star, &ctx->l_star, ctx->keyenc);
262
263     /* L_$ = double(L_*) */
264     ocb_double(&ctx->l_star, &ctx->l_dollar);
265
266     /* L_0 = double(L_$) */
267     ocb_double(&ctx->l_dollar, ctx->l);
268
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 */
275
276     return 1;
277 }
278
279 /*
280  * Copy an OCB128_CONTEXT object
281  */
282 int CRYPTO_ocb128_copy_ctx(OCB128_CONTEXT *dest, OCB128_CONTEXT *src,
283                            void *keyenc, void *keydec)
284 {
285     memcpy(dest, src, sizeof(OCB128_CONTEXT));
286     if (keyenc)
287         dest->keyenc = keyenc;
288     if (keydec)
289         dest->keydec = keydec;
290     if (src->l) {
291         dest->l = OPENSSL_malloc(src->max_l_index * 16);
292         if (dest->l == NULL)
293             return 0;
294         memcpy(dest->l, src->l, (src->l_index + 1) * 16);
295     }
296     return 1;
297 }
298
299 /*
300  * Set the IV to be used for this operation. Must be 1 - 15 bytes.
301  */
302 int CRYPTO_ocb128_setiv(OCB128_CONTEXT *ctx, const unsigned char *iv,
303                         size_t len, size_t taglen)
304 {
305     unsigned char ktop[16], tmp[16], mask;
306     unsigned char stretch[24], nonce[16];
307     size_t bottom, shift;
308     union ublock offset;
309
310     offset.ocbblk = &ctx->offset;
311
312     /*
313      * Spec says IV is 120 bits or fewer - it allows non byte aligned lengths.
314      * We don't support  this at this stage
315      */
316     if ((len > 15) || (len < 1) || (taglen > 16) || (taglen < 1)) {
317         return -1;
318     }
319
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;
325
326     /* Ktop = ENCIPHER(K, Nonce[1..122] || zeros(6)) */
327     memcpy(tmp, nonce, 16);
328     tmp[15] &= 0xc0;
329     ctx->encrypt(tmp, ktop, ctx->keyenc);
330
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);
334
335     /* bottom = str2num(Nonce[123..128]) */
336     bottom = nonce[15] & 0x3f;
337
338     /* Offset_0 = Stretch[1+bottom..128+bottom] */
339     shift = bottom % 8;
340     ocb_block_lshift((OCB_BLOCK *)(stretch + (bottom / 8)), shift,
341                      &ctx->offset);
342     mask = 0xff;
343     mask <<= 8 - shift;
344     offset.chrblk[15] |=
345         (*(stretch + (bottom / 8) + 16) & mask) >> (8 - shift);
346
347     return 1;
348 }
349
350 /*
351  * Provide any AAD. This can be called multiple times. Only the final time can
352  * have a partial block
353  */
354 int CRYPTO_ocb128_aad(OCB128_CONTEXT *ctx, const unsigned char *aad,
355                       size_t len)
356 {
357     u64 all_num_blocks, num_blocks;
358     u64 i;
359     OCB_BLOCK tmp1;
360     OCB_BLOCK tmp2;
361     int last_len;
362
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;
366
367     /* Loop through all full blocks of AAD */
368     for (i = ctx->blocks_hashed + 1; i <= all_num_blocks; i++) {
369         OCB_BLOCK *lookup;
370         OCB_BLOCK *aad_block;
371
372         /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
373         lookup = ocb_lookup_l(ctx, ocb_ntz(i));
374         if (!lookup)
375             return 0;
376         ocb_block16_xor(&ctx->offset_aad, lookup, &ctx->offset_aad);
377
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);
383     }
384
385     /*
386      * Check if we have any partial blocks left over. This is only valid in the
387      * last call to this function
388      */
389     last_len = len % 16;
390
391     if (last_len > 0) {
392         /* Offset_* = Offset_m xor L_* */
393         ocb_block16_xor(&ctx->offset_aad, &ctx->l_star, &ctx->offset_aad);
394
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);
400
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);
404     }
405
406     ctx->blocks_hashed = all_num_blocks;
407
408     return 1;
409 }
410
411 /*
412  * Provide any data to be encrypted. This can be called multiple times. Only
413  * the final time can have a partial block
414  */
415 int CRYPTO_ocb128_encrypt(OCB128_CONTEXT *ctx,
416                           const unsigned char *in, unsigned char *out,
417                           size_t len)
418 {
419     u64 i;
420     u64 all_num_blocks, num_blocks;
421     OCB_BLOCK tmp1;
422     OCB_BLOCK tmp2;
423     OCB_BLOCK pad;
424     int last_len;
425
426     /*
427      * Calculate the number of blocks of data to be encrypted provided now, and
428      * so far
429      */
430     num_blocks = len / 16;
431     all_num_blocks = num_blocks + ctx->blocks_processed;
432
433     /* Loop through all full blocks to be encrypted */
434     for (i = ctx->blocks_processed + 1; i <= all_num_blocks; i++) {
435         OCB_BLOCK *lookup;
436         OCB_BLOCK *inblock;
437         OCB_BLOCK *outblock;
438
439         /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
440         lookup = ocb_lookup_l(ctx, ocb_ntz(i));
441         if (!lookup)
442             return 0;
443         ocb_block16_xor(&ctx->offset, lookup, &ctx->offset);
444
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);
451         outblock =
452             (OCB_BLOCK *)(out + ((i - ctx->blocks_processed - 1) * 16));
453         ocb_block16_xor(&ctx->offset, &tmp2, outblock);
454
455     }
456
457     /*
458      * Check if we have any partial blocks left over. This is only valid in the
459      * last call to this function
460      */
461     last_len = len % 16;
462
463     if (last_len > 0) {
464         /* Offset_* = Offset_m xor L_* */
465         ocb_block16_xor(&ctx->offset, &ctx->l_star, &ctx->offset);
466
467         /* Pad = ENCIPHER(K, Offset_*) */
468         ocb_encrypt(ctx, &ctx->offset, &pad, ctx->keyenc);
469
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));
473
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);
479     }
480
481     ctx->blocks_processed = all_num_blocks;
482
483     return 1;
484 }
485
486 /*
487  * Provide any data to be decrypted. This can be called multiple times. Only
488  * the final time can have a partial block
489  */
490 int CRYPTO_ocb128_decrypt(OCB128_CONTEXT *ctx,
491                           const unsigned char *in, unsigned char *out,
492                           size_t len)
493 {
494     u64 i;
495     u64 all_num_blocks, num_blocks;
496     OCB_BLOCK tmp1;
497     OCB_BLOCK tmp2;
498     OCB_BLOCK pad;
499     int last_len;
500     /*
501      * Calculate the number of blocks of data to be decrypted provided now, and
502      * so far
503      */
504     num_blocks = len / 16;
505     all_num_blocks = num_blocks + ctx->blocks_processed;
506
507     /* Loop through all full blocks to be decrypted */
508     for (i = ctx->blocks_processed + 1; i <= all_num_blocks; i++) {
509         OCB_BLOCK *inblock;
510         OCB_BLOCK *outblock;
511
512         /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
513         OCB_BLOCK *lookup = ocb_lookup_l(ctx, ocb_ntz(i));
514         if (!lookup)
515             return 0;
516         ocb_block16_xor(&ctx->offset, lookup, &ctx->offset);
517
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);
522         outblock =
523             (OCB_BLOCK *)(out + ((i - ctx->blocks_processed - 1) * 16));
524         ocb_block16_xor(&ctx->offset, &tmp2, outblock);
525
526         /* Checksum_i = Checksum_{i-1} xor P_i */
527         ocb_block16_xor(&ctx->checksum, outblock, &ctx->checksum);
528     }
529
530     /*
531      * Check if we have any partial blocks left over. This is only valid in the
532      * last call to this function
533      */
534     last_len = len % 16;
535
536     if (last_len > 0) {
537         /* Offset_* = Offset_m xor L_* */
538         ocb_block16_xor(&ctx->offset, &ctx->l_star, &ctx->offset);
539
540         /* Pad = ENCIPHER(K, Offset_*) */
541         ocb_encrypt(ctx, &ctx->offset, &pad, ctx->keyenc);
542
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));
546
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);
552     }
553
554     ctx->blocks_processed = all_num_blocks;
555
556     return 1;
557 }
558
559 /*
560  * Calculate the tag and verify it against the supplied tag
561  */
562 int CRYPTO_ocb128_finish(OCB128_CONTEXT *ctx, const unsigned char *tag,
563                          size_t len)
564 {
565     OCB_BLOCK tmp1, tmp2;
566
567     /*
568      * Tag = ENCIPHER(K, Checksum_* xor Offset_* xor L_$) xor HASH(K,A)
569      */
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);
574
575     if (len > 16 || len < 1) {
576         return -1;
577     }
578
579     /* Compare the tag if we've been given one */
580     if (tag)
581         return CRYPTO_memcmp(&ctx->tag, tag, len);
582     else
583         return -1;
584 }
585
586 /*
587  * Retrieve the calculated tag
588  */
589 int CRYPTO_ocb128_tag(OCB128_CONTEXT *ctx, unsigned char *tag, size_t len)
590 {
591     if (len > 16 || len < 1) {
592         return -1;
593     }
594
595     /* Calculate the tag */
596     CRYPTO_ocb128_finish(ctx, NULL, 0);
597
598     /* Copy the tag into the supplied buffer */
599     memcpy(tag, &ctx->tag, len);
600
601     return 1;
602 }
603
604 /*
605  * Release all resources
606  */
607 void CRYPTO_ocb128_cleanup(OCB128_CONTEXT *ctx)
608 {
609     if (ctx) {
610         OPENSSL_clear_free(ctx->l, ctx->max_l_index * 16);
611         OPENSSL_cleanse(ctx, sizeof(*ctx));
612     }
613 }
614
615 #endif                          /* OPENSSL_NO_OCB */