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