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