2685652d3fa0e089a92060b38cbe1e9879b4c66f
[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     if (idx <= ctx->l_index) {
157         return ctx->l + idx;
158     }
159
160     /* We don't have it - so calculate it */
161     ctx->l_index++;
162     if (ctx->l_index == ctx->max_l_index) {
163         ctx->max_l_index *= 2;
164         ctx->l =
165             OPENSSL_realloc(ctx->l, ctx->max_l_index * sizeof(OCB_BLOCK));
166         if (!ctx->l)
167             return NULL;
168     }
169     ocb_double(ctx->l + (idx - 1), ctx->l + idx);
170
171     return ctx->l + idx;
172 }
173
174 /*
175  * Encrypt a block from |in| and store the result in |out|
176  */
177 static void ocb_encrypt(OCB128_CONTEXT *ctx, OCB_BLOCK *in, OCB_BLOCK *out,
178                         void *keyenc)
179 {
180     union ublock locin;
181     union ublock locout;
182
183     locin.ocbblk = in;
184     locout.ocbblk = out;
185
186     ctx->encrypt(locin.chrblk, locout.chrblk, keyenc);
187 }
188
189 /*
190  * Decrypt a block from |in| and store the result in |out|
191  */
192 static void ocb_decrypt(OCB128_CONTEXT *ctx, OCB_BLOCK *in, OCB_BLOCK *out,
193                         void *keydec)
194 {
195     union ublock locin;
196     union ublock locout;
197
198     locin.ocbblk = in;
199     locout.ocbblk = out;
200
201     ctx->decrypt(locin.chrblk, locout.chrblk, keydec);
202 }
203
204 /*
205  * Create a new OCB128_CONTEXT
206  */
207 OCB128_CONTEXT *CRYPTO_ocb128_new(void *keyenc, void *keydec,
208                                   block128_f encrypt, block128_f decrypt)
209 {
210     OCB128_CONTEXT *octx;
211     int ret;
212
213     if ((octx = OPENSSL_malloc(sizeof(*octx))) != NULL) {
214         ret = CRYPTO_ocb128_init(octx, keyenc, keydec, encrypt, decrypt);
215         if (ret)
216             return octx;
217         OPENSSL_free(octx);
218     }
219
220     return NULL;
221 }
222
223 /*
224  * Initialise an existing OCB128_CONTEXT
225  */
226 int CRYPTO_ocb128_init(OCB128_CONTEXT *ctx, void *keyenc, void *keydec,
227                        block128_f encrypt, block128_f decrypt)
228 {
229     memset(ctx, 0, sizeof(*ctx));
230     ctx->l_index = 0;
231     ctx->max_l_index = 1;
232     ctx->l = OPENSSL_malloc(ctx->max_l_index * 16);
233     if (ctx->l == NULL)
234         return 0;
235
236     /*
237      * We set both the encryption and decryption key schedules - decryption
238      * needs both. Don't really need decryption schedule if only doing
239      * encryption - but it simplifies things to take it anyway
240      */
241     ctx->encrypt = encrypt;
242     ctx->decrypt = decrypt;
243     ctx->keyenc = keyenc;
244     ctx->keydec = keydec;
245
246     /* L_* = ENCIPHER(K, zeros(128)) */
247     ocb_encrypt(ctx, &ctx->l_star, &ctx->l_star, ctx->keyenc);
248
249     /* L_$ = double(L_*) */
250     ocb_double(&ctx->l_star, &ctx->l_dollar);
251
252     /* L_0 = double(L_$) */
253     ocb_double(&ctx->l_dollar, ctx->l);
254
255     return 1;
256 }
257
258 /*
259  * Copy an OCB128_CONTEXT object
260  */
261 int CRYPTO_ocb128_copy_ctx(OCB128_CONTEXT *dest, OCB128_CONTEXT *src,
262                            void *keyenc, void *keydec)
263 {
264     memcpy(dest, src, sizeof(OCB128_CONTEXT));
265     if (keyenc)
266         dest->keyenc = keyenc;
267     if (keydec)
268         dest->keydec = keydec;
269     if (src->l) {
270         dest->l = OPENSSL_malloc(src->max_l_index * 16);
271         if (dest->l == NULL)
272             return 0;
273         memcpy(dest->l, src->l, (src->l_index + 1) * 16);
274     }
275     return 1;
276 }
277
278 /*
279  * Set the IV to be used for this operation. Must be 1 - 15 bytes.
280  */
281 int CRYPTO_ocb128_setiv(OCB128_CONTEXT *ctx, const unsigned char *iv,
282                         size_t len, size_t taglen)
283 {
284     unsigned char ktop[16], tmp[16], mask;
285     unsigned char stretch[24], nonce[16];
286     size_t bottom, shift;
287     union ublock offset;
288
289     offset.ocbblk = &ctx->offset;
290
291     /*
292      * Spec says IV is 120 bits or fewer - it allows non byte aligned lengths.
293      * We don't support  this at this stage
294      */
295     if ((len > 15) || (len < 1) || (taglen > 16) || (taglen < 1)) {
296         return -1;
297     }
298
299     /* Nonce = num2str(TAGLEN mod 128,7) || zeros(120-bitlen(N)) || 1 || N */
300     nonce[0] = ((taglen * 8) % 128) << 1;
301     memset(nonce + 1, 0, 15);
302     memcpy(nonce + 16 - len, iv, len);
303     nonce[15 - len] |= 1;
304
305     /* Ktop = ENCIPHER(K, Nonce[1..122] || zeros(6)) */
306     memcpy(tmp, nonce, 16);
307     tmp[15] &= 0xc0;
308     ctx->encrypt(tmp, ktop, ctx->keyenc);
309
310     /* Stretch = Ktop || (Ktop[1..64] xor Ktop[9..72]) */
311     memcpy(stretch, ktop, 16);
312     ocb_block_xor(ktop, ktop + 1, 8, stretch + 16);
313
314     /* bottom = str2num(Nonce[123..128]) */
315     bottom = nonce[15] & 0x3f;
316
317     /* Offset_0 = Stretch[1+bottom..128+bottom] */
318     shift = bottom % 8;
319     ocb_block_lshift((OCB_BLOCK *)(stretch + (bottom / 8)), shift,
320                      &ctx->offset);
321     mask = 0xff;
322     mask <<= 8 - shift;
323     offset.chrblk[15] |=
324         (*(stretch + (bottom / 8) + 16) & mask) >> (8 - shift);
325
326     return 1;
327 }
328
329 /*
330  * Provide any AAD. This can be called multiple times. Only the final time can
331  * have a partial block
332  */
333 int CRYPTO_ocb128_aad(OCB128_CONTEXT *ctx, const unsigned char *aad,
334                       size_t len)
335 {
336     u64 all_num_blocks, num_blocks;
337     u64 i;
338     OCB_BLOCK tmp1;
339     OCB_BLOCK tmp2;
340     int last_len;
341
342     /* Calculate the number of blocks of AAD provided now, and so far */
343     num_blocks = len / 16;
344     all_num_blocks = num_blocks + ctx->blocks_hashed;
345
346     /* Loop through all full blocks of AAD */
347     for (i = ctx->blocks_hashed + 1; i <= all_num_blocks; i++) {
348         OCB_BLOCK *lookup;
349         OCB_BLOCK *aad_block;
350
351         /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
352         lookup = ocb_lookup_l(ctx, ocb_ntz(i));
353         if (!lookup)
354             return 0;
355         ocb_block16_xor(&ctx->offset_aad, lookup, &ctx->offset_aad);
356
357         /* Sum_i = Sum_{i-1} xor ENCIPHER(K, A_i xor Offset_i) */
358         aad_block = (OCB_BLOCK *)(aad + ((i - ctx->blocks_hashed - 1) * 16));
359         ocb_block16_xor(&ctx->offset_aad, aad_block, &tmp1);
360         ocb_encrypt(ctx, &tmp1, &tmp2, ctx->keyenc);
361         ocb_block16_xor(&ctx->sum, &tmp2, &ctx->sum);
362     }
363
364     /*
365      * Check if we have any partial blocks left over. This is only valid in the
366      * last call to this function
367      */
368     last_len = len % 16;
369
370     if (last_len > 0) {
371         /* Offset_* = Offset_m xor L_* */
372         ocb_block16_xor(&ctx->offset_aad, &ctx->l_star, &ctx->offset_aad);
373
374         /* CipherInput = (A_* || 1 || zeros(127-bitlen(A_*))) xor Offset_* */
375         memset(&tmp1, 0, 16);
376         memcpy(&tmp1, aad + (num_blocks * 16), last_len);
377         ((unsigned char *)&tmp1)[last_len] = 0x80;
378         ocb_block16_xor(&ctx->offset_aad, &tmp1, &tmp2);
379
380         /* Sum = Sum_m xor ENCIPHER(K, CipherInput) */
381         ocb_encrypt(ctx, &tmp2, &tmp1, ctx->keyenc);
382         ocb_block16_xor(&ctx->sum, &tmp1, &ctx->sum);
383     }
384
385     ctx->blocks_hashed = all_num_blocks;
386
387     return 1;
388 }
389
390 /*
391  * Provide any data to be encrypted. This can be called multiple times. Only
392  * the final time can have a partial block
393  */
394 int CRYPTO_ocb128_encrypt(OCB128_CONTEXT *ctx,
395                           const unsigned char *in, unsigned char *out,
396                           size_t len)
397 {
398     u64 i;
399     u64 all_num_blocks, num_blocks;
400     OCB_BLOCK tmp1;
401     OCB_BLOCK tmp2;
402     OCB_BLOCK pad;
403     int last_len;
404
405     /*
406      * Calculate the number of blocks of data to be encrypted provided now, and
407      * so far
408      */
409     num_blocks = len / 16;
410     all_num_blocks = num_blocks + ctx->blocks_processed;
411
412     /* Loop through all full blocks to be encrypted */
413     for (i = ctx->blocks_processed + 1; i <= all_num_blocks; i++) {
414         OCB_BLOCK *lookup;
415         OCB_BLOCK *inblock;
416         OCB_BLOCK *outblock;
417
418         /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
419         lookup = ocb_lookup_l(ctx, ocb_ntz(i));
420         if (!lookup)
421             return 0;
422         ocb_block16_xor(&ctx->offset, lookup, &ctx->offset);
423
424         /* C_i = Offset_i xor ENCIPHER(K, P_i xor Offset_i) */
425         inblock = (OCB_BLOCK *)(in + ((i - ctx->blocks_processed - 1) * 16));
426         ocb_block16_xor(&ctx->offset, inblock, &tmp1);
427         ocb_encrypt(ctx, &tmp1, &tmp2, ctx->keyenc);
428         outblock =
429             (OCB_BLOCK *)(out + ((i - ctx->blocks_processed - 1) * 16));
430         ocb_block16_xor(&ctx->offset, &tmp2, outblock);
431
432         /* Checksum_i = Checksum_{i-1} xor P_i */
433         ocb_block16_xor(&ctx->checksum, inblock, &ctx->checksum);
434     }
435
436     /*
437      * Check if we have any partial blocks left over. This is only valid in the
438      * last call to this function
439      */
440     last_len = len % 16;
441
442     if (last_len > 0) {
443         /* Offset_* = Offset_m xor L_* */
444         ocb_block16_xor(&ctx->offset, &ctx->l_star, &ctx->offset);
445
446         /* Pad = ENCIPHER(K, Offset_*) */
447         ocb_encrypt(ctx, &ctx->offset, &pad, ctx->keyenc);
448
449         /* C_* = P_* xor Pad[1..bitlen(P_*)] */
450         ocb_block_xor(in + (len / 16) * 16, (unsigned char *)&pad, last_len,
451                       out + (num_blocks * 16));
452
453         /* Checksum_* = Checksum_m xor (P_* || 1 || zeros(127-bitlen(P_*))) */
454         memset(&tmp1, 0, 16);
455         memcpy(&tmp1, in + (len / 16) * 16, last_len);
456         ((unsigned char *)(&tmp1))[last_len] = 0x80;
457         ocb_block16_xor(&ctx->checksum, &tmp1, &ctx->checksum);
458     }
459
460     ctx->blocks_processed = all_num_blocks;
461
462     return 1;
463 }
464
465 /*
466  * Provide any data to be decrypted. This can be called multiple times. Only
467  * the final time can have a partial block
468  */
469 int CRYPTO_ocb128_decrypt(OCB128_CONTEXT *ctx,
470                           const unsigned char *in, unsigned char *out,
471                           size_t len)
472 {
473     u64 i;
474     u64 all_num_blocks, num_blocks;
475     OCB_BLOCK tmp1;
476     OCB_BLOCK tmp2;
477     OCB_BLOCK pad;
478     int last_len;
479     /*
480      * Calculate the number of blocks of data to be decrypted provided now, and
481      * so far
482      */
483     num_blocks = len / 16;
484     all_num_blocks = num_blocks + ctx->blocks_processed;
485
486     /* Loop through all full blocks to be decrypted */
487     for (i = ctx->blocks_processed + 1; i <= all_num_blocks; i++) {
488         OCB_BLOCK *inblock;
489         OCB_BLOCK *outblock;
490
491         /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
492         OCB_BLOCK *lookup = ocb_lookup_l(ctx, ocb_ntz(i));
493         if (!lookup)
494             return 0;
495         ocb_block16_xor(&ctx->offset, lookup, &ctx->offset);
496
497         /* P_i = Offset_i xor DECIPHER(K, C_i xor Offset_i) */
498         inblock = (OCB_BLOCK *)(in + ((i - ctx->blocks_processed - 1) * 16));
499         ocb_block16_xor(&ctx->offset, inblock, &tmp1);
500         ocb_decrypt(ctx, &tmp1, &tmp2, ctx->keydec);
501         outblock =
502             (OCB_BLOCK *)(out + ((i - ctx->blocks_processed - 1) * 16));
503         ocb_block16_xor(&ctx->offset, &tmp2, outblock);
504
505         /* Checksum_i = Checksum_{i-1} xor P_i */
506         ocb_block16_xor(&ctx->checksum, outblock, &ctx->checksum);
507     }
508
509     /*
510      * Check if we have any partial blocks left over. This is only valid in the
511      * last call to this function
512      */
513     last_len = len % 16;
514
515     if (last_len > 0) {
516         /* Offset_* = Offset_m xor L_* */
517         ocb_block16_xor(&ctx->offset, &ctx->l_star, &ctx->offset);
518
519         /* Pad = ENCIPHER(K, Offset_*) */
520         ocb_encrypt(ctx, &ctx->offset, &pad, ctx->keyenc);
521
522         /* P_* = C_* xor Pad[1..bitlen(C_*)] */
523         ocb_block_xor(in + (len / 16) * 16, (unsigned char *)&pad, last_len,
524                       out + (num_blocks * 16));
525
526         /* Checksum_* = Checksum_m xor (P_* || 1 || zeros(127-bitlen(P_*))) */
527         memset(&tmp1, 0, 16);
528         memcpy(&tmp1, out + (len / 16) * 16, last_len);
529         ((unsigned char *)(&tmp1))[last_len] = 0x80;
530         ocb_block16_xor(&ctx->checksum, &tmp1, &ctx->checksum);
531     }
532
533     ctx->blocks_processed = all_num_blocks;
534
535     return 1;
536 }
537
538 /*
539  * Calculate the tag and verify it against the supplied tag
540  */
541 int CRYPTO_ocb128_finish(OCB128_CONTEXT *ctx, const unsigned char *tag,
542                          size_t len)
543 {
544     OCB_BLOCK tmp1, tmp2;
545
546     /*
547      * Tag = ENCIPHER(K, Checksum_* xor Offset_* xor L_$) xor HASH(K,A)
548      */
549     ocb_block16_xor(&ctx->checksum, &ctx->offset, &tmp1);
550     ocb_block16_xor(&tmp1, &ctx->l_dollar, &tmp2);
551     ocb_encrypt(ctx, &tmp2, &tmp1, ctx->keyenc);
552     ocb_block16_xor(&tmp1, &ctx->sum, &ctx->tag);
553
554     if (len > 16 || len < 1) {
555         return -1;
556     }
557
558     /* Compare the tag if we've been given one */
559     if (tag)
560         return CRYPTO_memcmp(&ctx->tag, tag, len);
561     else
562         return -1;
563 }
564
565 /*
566  * Retrieve the calculated tag
567  */
568 int CRYPTO_ocb128_tag(OCB128_CONTEXT *ctx, unsigned char *tag, size_t len)
569 {
570     if (len > 16 || len < 1) {
571         return -1;
572     }
573
574     /* Calculate the tag */
575     CRYPTO_ocb128_finish(ctx, NULL, 0);
576
577     /* Copy the tag into the supplied buffer */
578     memcpy(tag, &ctx->tag, len);
579
580     return 1;
581 }
582
583 /*
584  * Release all resources
585  */
586 void CRYPTO_ocb128_cleanup(OCB128_CONTEXT *ctx)
587 {
588     if (ctx) {
589         OPENSSL_clear_free(ctx->l, ctx->max_l_index * 16);
590         OPENSSL_cleanse(ctx, sizeof(*ctx));
591     }
592 }
593
594 #endif                          /* OPENSSL_NO_OCB */