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