crypto/modes/ocb128.c

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