ARMv8 assembly pack: add Qualcomm Kryo results.
[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 tmp;
278
279     /* Calculate the number of blocks of AAD provided now, and so far */
280     num_blocks = len / 16;
281     all_num_blocks = num_blocks + ctx->blocks_hashed;
282
283     /* Loop through all full blocks of AAD */
284     for (i = ctx->blocks_hashed + 1; i <= all_num_blocks; i++) {
285         OCB_BLOCK *lookup;
286
287         /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
288         lookup = ocb_lookup_l(ctx, ocb_ntz(i));
289         if (lookup == NULL)
290             return 0;
291         ocb_block16_xor(&ctx->offset_aad, lookup, &ctx->offset_aad);
292
293         memcpy(tmp.c, aad, 16);
294         aad += 16;
295
296         /* Sum_i = Sum_{i-1} xor ENCIPHER(K, A_i xor Offset_i) */
297         ocb_block16_xor(&ctx->offset_aad, &tmp, &tmp);
298         ctx->encrypt(tmp.c, tmp.c, ctx->keyenc);
299         ocb_block16_xor(&tmp, &ctx->sum, &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(tmp.c, 0, 16);
314         memcpy(tmp.c, aad, last_len);
315         tmp.c[last_len] = 0x80;
316         ocb_block16_xor(&ctx->offset_aad, &tmp, &tmp);
317
318         /* Sum = Sum_m xor ENCIPHER(K, CipherInput) */
319         ctx->encrypt(tmp.c, tmp.c, ctx->keyenc);
320         ocb_block16_xor(&tmp, &ctx->sum, &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
339     /*
340      * Calculate the number of blocks of data to be encrypted provided now, and
341      * so far
342      */
343     num_blocks = len / 16;
344     all_num_blocks = num_blocks + ctx->blocks_processed;
345
346     if (num_blocks && all_num_blocks == (size_t)all_num_blocks
347         && ctx->stream != NULL) {
348         size_t max_idx = 0, top = (size_t)all_num_blocks;
349
350         /*
351          * See how many L_{i} entries we need to process data at hand
352          * and pre-compute missing entries in the table [if any]...
353          */
354         while (top >>= 1)
355             max_idx++;
356         if (ocb_lookup_l(ctx, max_idx) == NULL)
357             return 0;
358
359         ctx->stream(in, out, num_blocks, ctx->keyenc,
360                     (size_t)ctx->blocks_processed + 1, ctx->offset.c,
361                     (const unsigned char (*)[16])ctx->l, ctx->checksum.c);
362     } else {
363         /* Loop through all full blocks to be encrypted */
364         for (i = ctx->blocks_processed + 1; i <= all_num_blocks; i++) {
365             OCB_BLOCK *lookup;
366             OCB_BLOCK tmp;
367
368             /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
369             lookup = ocb_lookup_l(ctx, ocb_ntz(i));
370             if (lookup == NULL)
371                 return 0;
372             ocb_block16_xor(&ctx->offset, lookup, &ctx->offset);
373
374             memcpy(tmp.c, in, 16);
375             in += 16;
376
377             /* Checksum_i = Checksum_{i-1} xor P_i */
378             ocb_block16_xor(&tmp, &ctx->checksum, &ctx->checksum);
379
380             /* C_i = Offset_i xor ENCIPHER(K, P_i xor Offset_i) */
381             ocb_block16_xor(&ctx->offset, &tmp, &tmp);
382             ctx->encrypt(tmp.c, tmp.c, ctx->keyenc);
383             ocb_block16_xor(&ctx->offset, &tmp, &tmp);
384
385             memcpy(out, tmp.c, 16);
386             out += 16;
387         }
388     }
389
390     /*
391      * Check if we have any partial blocks left over. This is only valid in the
392      * last call to this function
393      */
394     last_len = len % 16;
395
396     if (last_len > 0) {
397         OCB_BLOCK pad;
398
399         /* Offset_* = Offset_m xor L_* */
400         ocb_block16_xor(&ctx->offset, &ctx->l_star, &ctx->offset);
401
402         /* Pad = ENCIPHER(K, Offset_*) */
403         ctx->encrypt(ctx->offset.c, pad.c, ctx->keyenc);
404
405         /* C_* = P_* xor Pad[1..bitlen(P_*)] */
406         ocb_block_xor(in, pad.c, last_len, out);
407
408         /* Checksum_* = Checksum_m xor (P_* || 1 || zeros(127-bitlen(P_*))) */
409         memset(pad.c, 0, 16);           /* borrow pad */
410         memcpy(pad.c, in, last_len);
411         pad.c[last_len] = 0x80;
412         ocb_block16_xor(&pad, &ctx->checksum, &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
431     /*
432      * Calculate the number of blocks of data to be decrypted provided now, and
433      * so far
434      */
435     num_blocks = len / 16;
436     all_num_blocks = num_blocks + ctx->blocks_processed;
437
438     if (num_blocks && all_num_blocks == (size_t)all_num_blocks
439         && ctx->stream != NULL) {
440         size_t max_idx = 0, top = (size_t)all_num_blocks;
441
442         /*
443          * See how many L_{i} entries we need to process data at hand
444          * and pre-compute missing entries in the table [if any]...
445          */
446         while (top >>= 1)
447             max_idx++;
448         if (ocb_lookup_l(ctx, max_idx) == NULL)
449             return 0;
450
451         ctx->stream(in, out, num_blocks, ctx->keydec,
452                     (size_t)ctx->blocks_processed + 1, ctx->offset.c,
453                     (const unsigned char (*)[16])ctx->l, ctx->checksum.c);
454     } else {
455         OCB_BLOCK tmp;
456
457         /* Loop through all full blocks to be decrypted */
458         for (i = ctx->blocks_processed + 1; i <= all_num_blocks; i++) {
459
460             /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
461             OCB_BLOCK *lookup = ocb_lookup_l(ctx, ocb_ntz(i));
462             if (lookup == NULL)
463                 return 0;
464             ocb_block16_xor(&ctx->offset, lookup, &ctx->offset);
465
466             memcpy(tmp.c, in, 16);
467             in += 16;
468
469             /* P_i = Offset_i xor DECIPHER(K, C_i xor Offset_i) */
470             ocb_block16_xor(&ctx->offset, &tmp, &tmp);
471             ctx->decrypt(tmp.c, tmp.c, ctx->keydec);
472             ocb_block16_xor(&ctx->offset, &tmp, &tmp);
473
474             /* Checksum_i = Checksum_{i-1} xor P_i */
475             ocb_block16_xor(&tmp, &ctx->checksum, &ctx->checksum);
476
477             memcpy(out, tmp.c, 16);
478             out += 16;
479         }
480     }
481
482     /*
483      * Check if we have any partial blocks left over. This is only valid in the
484      * last call to this function
485      */
486     last_len = len % 16;
487
488     if (last_len > 0) {
489         OCB_BLOCK pad;
490
491         /* Offset_* = Offset_m xor L_* */
492         ocb_block16_xor(&ctx->offset, &ctx->l_star, &ctx->offset);
493
494         /* Pad = ENCIPHER(K, Offset_*) */
495         ctx->encrypt(ctx->offset.c, pad.c, ctx->keyenc);
496
497         /* P_* = C_* xor Pad[1..bitlen(C_*)] */
498         ocb_block_xor(in, pad.c, last_len, out);
499
500         /* Checksum_* = Checksum_m xor (P_* || 1 || zeros(127-bitlen(P_*))) */
501         memset(pad.c, 0, 16);           /* borrow pad */
502         memcpy(pad.c, out, last_len);
503         pad.c[last_len] = 0x80;
504         ocb_block16_xor(&pad, &ctx->checksum, &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 tmp;
519
520     /*
521      * Tag = ENCIPHER(K, Checksum_* xor Offset_* xor L_$) xor HASH(K,A)
522      */
523     ocb_block16_xor(&ctx->checksum, &ctx->offset, &tmp);
524     ocb_block16_xor(&ctx->l_dollar, &tmp, &tmp);
525     ctx->encrypt(tmp.c, tmp.c, ctx->keyenc);
526     ocb_block16_xor(&tmp, &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.c, 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 */