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