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     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  */
  58 static 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  */
  78 static 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  */
  92 static 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  */
 130 OCB128_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  */
 151 int 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  */
 196 int 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  */
 217 int 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  */
 268 int 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  */
 329 int 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  */
 421 int 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
 509 static 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  */
 537 int 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  */
 546 int 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  */
 554 void 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 */