crypto/modes/ocb128.c

   1 /* ====================================================================
   2  * Copyright (c) 2014 The OpenSSL Project.  All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  *
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in
  13  *    the documentation and/or other materials provided with the
  14  *    distribution.
  15  *
  16  * 3. All advertising materials mentioning features or use of this
  17  *    software must display the following acknowledgment:
  18  *    "This product includes software developed by the OpenSSL Project
  19  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  20  *
  21  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  22  *    endorse or promote products derived from this software without
  23  *    prior written permission. For written permission, please contact
  24  *    openssl-core@openssl.org.
  25  *
  26  * 5. Products derived from this software may not be called "OpenSSL"
  27  *    nor may "OpenSSL" appear in their names without prior written
  28  *    permission of the OpenSSL Project.
  29  *
  30  * 6. Redistributions of any form whatsoever must retain the following
  31  *    acknowledgment:
  32  *    "This product includes software developed by the OpenSSL Project
  33  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  34  *
  35  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  36  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  37  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  38  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  39  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  40  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  41  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  42  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  43  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  44  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  45  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  46  * OF THE POSSIBILITY OF SUCH DAMAGE.
  47  * ====================================================================
  48  */
  49
  50 #include <string.h>
  51 #include <openssl/crypto.h>
  52 #include "modes_lcl.h"
  53
  54 #ifndef OPENSSL_NO_OCB
  55
  56 union ublock {
  57     unsigned char *chrblk;
  58     OCB_BLOCK *ocbblk;
  59 };
  60
  61 /*
  62  * Calculate the number of binary trailing zero's in any given number
  63  */
  64 static u32 ocb_ntz(u64 n)
  65 {
  66     u32 cnt = 0;
  67
  68     /*
  69      * We do a right-to-left simple sequential search. This is surprisingly
  70      * efficient as the distribution of trailing zeros is not uniform,
  71      * e.g. the number of possible inputs with no trailing zeros is equal to
  72      * the number with 1 or more; the number with exactly 1 is equal to the
  73      * number with 2 or more, etc. Checking the last two bits covers 75% of
  74      * all numbers. Checking the last three covers 87.5%
  75      */
  76     while (!(n & 1)) {
  77         n >>= 1;
  78         cnt++;
  79     }
  80     return cnt;
  81 }
  82
  83 /*
  84  * Shift a block of 16 bytes left by shift bits
  85  */
  86 static void ocb_block_lshift(OCB_BLOCK *in, size_t shift, OCB_BLOCK *out)
  87 {
  88     unsigned char shift_mask;
  89     int i;
  90     unsigned char mask[15];
  91     union ublock locin;
  92     union ublock locout;
  93
  94     locin.ocbblk = in;
  95     locout.ocbblk = out;
  96
  97     shift_mask = 0xff;
  98     shift_mask <<= (8 - shift);
  99     for (i = 15; i >= 0; i--) {
 100         if (i > 0) {
 101             mask[i - 1] = locin.chrblk[i] & shift_mask;
 102             mask[i - 1] >>= 8 - shift;
 103         }
 104         locout.chrblk[i] = locin.chrblk[i] << shift;
 105
 106         if (i != 15) {
 107             locout.chrblk[i] ^= mask[i];
 108         }
 109     }
 110 }
 111
 112 /*
 113  * Perform a "double" operation as per OCB spec
 114  */
 115 static void ocb_double(OCB_BLOCK *in, OCB_BLOCK *out)
 116 {
 117     unsigned char mask;
 118     union ublock locin;
 119     union ublock locout;
 120
 121     locin.ocbblk = in;
 122     locout.ocbblk = out;
 123
 124     /*
 125      * Calculate the mask based on the most significant bit. There are more
 126      * efficient ways to do this - but this way is constant time
 127      */
 128     mask = locin.chrblk[0] & 0x80;
 129     mask >>= 7;
 130     mask *= 135;
 131
 132     ocb_block_lshift(in, 1, out);
 133
 134     locout.chrblk[15] ^= mask;
 135 }
 136
 137 /*
 138  * Perform an xor on in1 and in2 - each of len bytes. Store result in out
 139  */
 140 static void ocb_block_xor(const unsigned char *in1,
 141                           const unsigned char *in2, size_t len,
 142                           unsigned char *out)
 143 {
 144     size_t i;
 145     for (i = 0; i < len; i++) {
 146         out[i] = in1[i] ^ in2[i];
 147     }
 148 }
 149
 150 /*
 151  * Lookup L_index in our lookup table. If we haven't already got it we need to
 152  * calculate it
 153  */
 154 static OCB_BLOCK *ocb_lookup_l(OCB128_CONTEXT *ctx, size_t idx)
 155 {
 156     if (idx <= ctx->l_index) {
 157         return ctx->l + idx;
 158     }
 159
 160     /* We don't have it - so calculate it */
 161     ctx->l_index++;
 162     if (ctx->l_index == ctx->max_l_index) {
 163         ctx->max_l_index *= 2;
 164         ctx->l =
 165             OPENSSL_realloc(ctx->l, ctx->max_l_index * sizeof(OCB_BLOCK));
 166         if (!ctx->l)
 167             return NULL;
 168     }
 169     ocb_double(ctx->l + (idx - 1), ctx->l + idx);
 170
 171     return ctx->l + idx;
 172 }
 173
 174 /*
 175  * Encrypt a block from |in| and store the result in |out|
 176  */
 177 static void ocb_encrypt(OCB128_CONTEXT *ctx, OCB_BLOCK *in, OCB_BLOCK *out,
 178                         void *keyenc)
 179 {
 180     union ublock locin;
 181     union ublock locout;
 182
 183     locin.ocbblk = in;
 184     locout.ocbblk = out;
 185
 186     ctx->encrypt(locin.chrblk, locout.chrblk, keyenc);
 187 }
 188
 189 /*
 190  * Decrypt a block from |in| and store the result in |out|
 191  */
 192 static void ocb_decrypt(OCB128_CONTEXT *ctx, OCB_BLOCK *in, OCB_BLOCK *out,
 193                         void *keydec)
 194 {
 195     union ublock locin;
 196     union ublock locout;
 197
 198     locin.ocbblk = in;
 199     locout.ocbblk = out;
 200
 201     ctx->decrypt(locin.chrblk, locout.chrblk, keydec);
 202 }
 203
 204 /*
 205  * Create a new OCB128_CONTEXT
 206  */
 207 OCB128_CONTEXT *CRYPTO_ocb128_new(void *keyenc, void *keydec,
 208                                   block128_f encrypt, block128_f decrypt)
 209 {
 210     OCB128_CONTEXT *octx;
 211     int ret;
 212
 213     if ((octx = (OCB128_CONTEXT *)OPENSSL_malloc(sizeof(OCB128_CONTEXT)))) {
 214         ret = CRYPTO_ocb128_init(octx, keyenc, keydec, encrypt, decrypt);
 215         if (ret)
 216             return octx;
 217         OPENSSL_free(octx);
 218     }
 219
 220     return NULL;
 221 }
 222
 223 /*
 224  * Initialise an existing OCB128_CONTEXT
 225  */
 226 int CRYPTO_ocb128_init(OCB128_CONTEXT *ctx, void *keyenc, void *keydec,
 227                        block128_f encrypt, block128_f decrypt)
 228 {
 229     /* Clear everything to NULLs */
 230     memset(ctx, 0, sizeof(*ctx));
 231
 232     ctx->l_index = 0;
 233     ctx->max_l_index = 1;
 234     ctx->l = OPENSSL_malloc(ctx->max_l_index * 16);
 235     if (!ctx->l)
 236         return 0;
 237
 238     /*
 239      * We set both the encryption and decryption key schedules - decryption
 240      * needs both. Don't really need decryption schedule if only doing
 241      * encryption - but it simplifies things to take it anyway
 242      */
 243     ctx->encrypt = encrypt;
 244     ctx->decrypt = decrypt;
 245     ctx->keyenc = keyenc;
 246     ctx->keydec = keydec;
 247
 248     /* L_* = ENCIPHER(K, zeros(128)) */
 249     ocb_encrypt(ctx, &ctx->l_star, &ctx->l_star, ctx->keyenc);
 250
 251     /* L_$ = double(L_*) */
 252     ocb_double(&ctx->l_star, &ctx->l_dollar);
 253
 254     /* L_0 = double(L_$) */
 255     ocb_double(&ctx->l_dollar, ctx->l);
 256
 257     return 1;
 258 }
 259
 260 /*
 261  * Copy an OCB128_CONTEXT object
 262  */
 263 int CRYPTO_ocb128_copy_ctx(OCB128_CONTEXT *dest, OCB128_CONTEXT *src,
 264                            void *keyenc, void *keydec)
 265 {
 266     memcpy(dest, src, sizeof(OCB128_CONTEXT));
 267     if (keyenc)
 268         dest->keyenc = keyenc;
 269     if (keydec)
 270         dest->keydec = keydec;
 271     if (src->l) {
 272         dest->l = OPENSSL_malloc(src->max_l_index * 16);
 273         if (!dest->l)
 274             return 0;
 275         memcpy(dest->l, src->l, (src->l_index + 1) * 16);
 276     }
 277     return 1;
 278 }
 279
 280 /*
 281  * Set the IV to be used for this operation. Must be 1 - 15 bytes.
 282  */
 283 int CRYPTO_ocb128_setiv(OCB128_CONTEXT *ctx, const unsigned char *iv,
 284                         size_t len, size_t taglen)
 285 {
 286     unsigned char ktop[16], tmp[16], mask;
 287     unsigned char stretch[24], nonce[16];
 288     size_t bottom, shift;
 289     union ublock offset;
 290
 291     offset.ocbblk = &ctx->offset;
 292
 293     /*
 294      * Spec says IV is 120 bits or fewer - it allows non byte aligned lengths.
 295      * We don't support  this at this stage
 296      */
 297     if ((len > 15) || (len < 1) || (taglen > 16) || (taglen < 1)) {
 298         return -1;
 299     }
 300
 301     /* Nonce = num2str(TAGLEN mod 128,7) || zeros(120-bitlen(N)) || 1 || N */
 302     nonce[0] = ((taglen * 8) % 128) << 1;
 303     memset(nonce + 1, 0, 15);
 304     memcpy(nonce + 16 - len, iv, len);
 305     nonce[15 - len] |= 1;
 306
 307     /* Ktop = ENCIPHER(K, Nonce[1..122] || zeros(6)) */
 308     memcpy(tmp, nonce, 16);
 309     tmp[15] &= 0xc0;
 310     ctx->encrypt(tmp, ktop, ctx->keyenc);
 311
 312     /* Stretch = Ktop || (Ktop[1..64] xor Ktop[9..72]) */
 313     memcpy(stretch, ktop, 16);
 314     ocb_block_xor(ktop, ktop + 1, 8, stretch + 16);
 315
 316     /* bottom = str2num(Nonce[123..128]) */
 317     bottom = nonce[15] & 0x3f;
 318
 319     /* Offset_0 = Stretch[1+bottom..128+bottom] */
 320     shift = bottom % 8;
 321     ocb_block_lshift((OCB_BLOCK *)(stretch + (bottom / 8)), shift,
 322                      &ctx->offset);
 323     mask = 0xff;
 324     mask <<= 8 - shift;
 325     offset.chrblk[15] |=
 326         (*(stretch + (bottom / 8) + 16) & mask) >> (8 - shift);
 327
 328     return 1;
 329 }
 330
 331 /*
 332  * Provide any AAD. This can be called multiple times. Only the final time can
 333  * have a partial block
 334  */
 335 int CRYPTO_ocb128_aad(OCB128_CONTEXT *ctx, const unsigned char *aad,
 336                       size_t len)
 337 {
 338     u64 all_num_blocks, num_blocks;
 339     u64 i;
 340     OCB_BLOCK tmp1;
 341     OCB_BLOCK tmp2;
 342     int last_len;
 343
 344     /* Calculate the number of blocks of AAD provided now, and so far */
 345     num_blocks = len / 16;
 346     all_num_blocks = num_blocks + ctx->blocks_hashed;
 347
 348     /* Loop through all full blocks of AAD */
 349     for (i = ctx->blocks_hashed + 1; i <= all_num_blocks; i++) {
 350         OCB_BLOCK *lookup;
 351         OCB_BLOCK *aad_block;
 352
 353         /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
 354         lookup = ocb_lookup_l(ctx, ocb_ntz(i));
 355         if (!lookup)
 356             return 0;
 357         ocb_block16_xor(&ctx->offset_aad, lookup, &ctx->offset_aad);
 358
 359         /* Sum_i = Sum_{i-1} xor ENCIPHER(K, A_i xor Offset_i) */
 360         aad_block = (OCB_BLOCK *)(aad + ((i - ctx->blocks_hashed - 1) * 16));
 361         ocb_block16_xor(&ctx->offset_aad, aad_block, &tmp1);
 362         ocb_encrypt(ctx, &tmp1, &tmp2, ctx->keyenc);
 363         ocb_block16_xor(&ctx->sum, &tmp2, &ctx->sum);
 364     }
 365
 366     /*
 367      * Check if we have any partial blocks left over. This is only valid in the
 368      * last call to this function
 369      */
 370     last_len = len % 16;
 371
 372     if (last_len > 0) {
 373         /* Offset_* = Offset_m xor L_* */
 374         ocb_block16_xor(&ctx->offset_aad, &ctx->l_star, &ctx->offset_aad);
 375
 376         /* CipherInput = (A_* || 1 || zeros(127-bitlen(A_*))) xor Offset_* */
 377         memset((void *)&tmp1, 0, 16);
 378         memcpy((void *)&tmp1, aad + (num_blocks * 16), last_len);
 379         ((unsigned char *)&tmp1)[last_len] = 0x80;
 380         ocb_block16_xor(&ctx->offset_aad, &tmp1, &tmp2);
 381
 382         /* Sum = Sum_m xor ENCIPHER(K, CipherInput) */
 383         ocb_encrypt(ctx, &tmp2, &tmp1, ctx->keyenc);
 384         ocb_block16_xor(&ctx->sum, &tmp1, &ctx->sum);
 385     }
 386
 387     ctx->blocks_hashed = all_num_blocks;
 388
 389     return 1;
 390 }
 391
 392 /*
 393  * Provide any data to be encrypted. This can be called multiple times. Only
 394  * the final time can have a partial block
 395  */
 396 int CRYPTO_ocb128_encrypt(OCB128_CONTEXT *ctx,
 397                           const unsigned char *in, unsigned char *out,
 398                           size_t len)
 399 {
 400     u64 i;
 401     u64 all_num_blocks, num_blocks;
 402     OCB_BLOCK tmp1;
 403     OCB_BLOCK tmp2;
 404     OCB_BLOCK pad;
 405     int last_len;
 406
 407     /*
 408      * Calculate the number of blocks of data to be encrypted provided now, and
 409      * so far
 410      */
 411     num_blocks = len / 16;
 412     all_num_blocks = num_blocks + ctx->blocks_processed;
 413
 414     /* Loop through all full blocks to be encrypted */
 415     for (i = ctx->blocks_processed + 1; i <= all_num_blocks; i++) {
 416         OCB_BLOCK *lookup;
 417         OCB_BLOCK *inblock;
 418         OCB_BLOCK *outblock;
 419
 420         /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
 421         lookup = ocb_lookup_l(ctx, ocb_ntz(i));
 422         if (!lookup)
 423             return 0;
 424         ocb_block16_xor(&ctx->offset, lookup, &ctx->offset);
 425
 426         /* C_i = Offset_i xor ENCIPHER(K, P_i xor Offset_i) */
 427         inblock = (OCB_BLOCK *)(in + ((i - ctx->blocks_processed - 1) * 16));
 428         ocb_block16_xor(&ctx->offset, inblock, &tmp1);
 429         ocb_encrypt(ctx, &tmp1, &tmp2, ctx->keyenc);
 430         outblock =
 431             (OCB_BLOCK *)(out + ((i - ctx->blocks_processed - 1) * 16));
 432         ocb_block16_xor(&ctx->offset, &tmp2, outblock);
 433
 434         /* Checksum_i = Checksum_{i-1} xor P_i */
 435         ocb_block16_xor(&ctx->checksum, inblock, &ctx->checksum);
 436     }
 437
 438     /*
 439      * Check if we have any partial blocks left over. This is only valid in the
 440      * last call to this function
 441      */
 442     last_len = len % 16;
 443
 444     if (last_len > 0) {
 445         /* Offset_* = Offset_m xor L_* */
 446         ocb_block16_xor(&ctx->offset, &ctx->l_star, &ctx->offset);
 447
 448         /* Pad = ENCIPHER(K, Offset_*) */
 449         ocb_encrypt(ctx, &ctx->offset, &pad, ctx->keyenc);
 450
 451         /* C_* = P_* xor Pad[1..bitlen(P_*)] */
 452         ocb_block_xor(in + (len / 16) * 16, (unsigned char *)&pad, last_len,
 453                       out + (num_blocks * 16));
 454
 455         /* Checksum_* = Checksum_m xor (P_* || 1 || zeros(127-bitlen(P_*))) */
 456         memset((void *)&tmp1, 0, 16);
 457         memcpy((void *)&tmp1, in + (len / 16) * 16, last_len);
 458         ((unsigned char *)(&tmp1))[last_len] = 0x80;
 459         ocb_block16_xor(&ctx->checksum, &tmp1, &ctx->checksum);
 460     }
 461
 462     ctx->blocks_processed = all_num_blocks;
 463
 464     return 1;
 465 }
 466
 467 /*
 468  * Provide any data to be decrypted. This can be called multiple times. Only
 469  * the final time can have a partial block
 470  */
 471 int CRYPTO_ocb128_decrypt(OCB128_CONTEXT *ctx,
 472                           const unsigned char *in, unsigned char *out,
 473                           size_t len)
 474 {
 475     u64 i;
 476     u64 all_num_blocks, num_blocks;
 477     OCB_BLOCK tmp1;
 478     OCB_BLOCK tmp2;
 479     OCB_BLOCK pad;
 480     int last_len;
 481     /*
 482      * Calculate the number of blocks of data to be decrypted provided now, and
 483      * so far
 484      */
 485     num_blocks = len / 16;
 486     all_num_blocks = num_blocks + ctx->blocks_processed;
 487
 488     /* Loop through all full blocks to be decrypted */
 489     for (i = ctx->blocks_processed + 1; i <= all_num_blocks; i++) {
 490         OCB_BLOCK *inblock;
 491         OCB_BLOCK *outblock;
 492
 493         /* Offset_i = Offset_{i-1} xor L_{ntz(i)} */
 494         OCB_BLOCK *lookup = ocb_lookup_l(ctx, ocb_ntz(i));
 495         if (!lookup)
 496             return 0;
 497         ocb_block16_xor(&ctx->offset, lookup, &ctx->offset);
 498
 499         /* P_i = Offset_i xor DECIPHER(K, C_i xor Offset_i) */
 500         inblock = (OCB_BLOCK *)(in + ((i - ctx->blocks_processed - 1) * 16));
 501         ocb_block16_xor(&ctx->offset, inblock, &tmp1);
 502         ocb_decrypt(ctx, &tmp1, &tmp2, ctx->keydec);
 503         outblock =
 504             (OCB_BLOCK *)(out + ((i - ctx->blocks_processed - 1) * 16));
 505         ocb_block16_xor(&ctx->offset, &tmp2, outblock);
 506
 507         /* Checksum_i = Checksum_{i-1} xor P_i */
 508         ocb_block16_xor(&ctx->checksum, outblock, &ctx->checksum);
 509     }
 510
 511     /*
 512      * Check if we have any partial blocks left over. This is only valid in the
 513      * last call to this function
 514      */
 515     last_len = len % 16;
 516
 517     if (last_len > 0) {
 518         /* Offset_* = Offset_m xor L_* */
 519         ocb_block16_xor(&ctx->offset, &ctx->l_star, &ctx->offset);
 520
 521         /* Pad = ENCIPHER(K, Offset_*) */
 522         ocb_encrypt(ctx, &ctx->offset, &pad, ctx->keyenc);
 523
 524         /* P_* = C_* xor Pad[1..bitlen(C_*)] */
 525         ocb_block_xor(in + (len / 16) * 16, (unsigned char *)&pad, last_len,
 526                       out + (num_blocks * 16));
 527
 528         /* Checksum_* = Checksum_m xor (P_* || 1 || zeros(127-bitlen(P_*))) */
 529         memset((void *)&tmp1, 0, 16);
 530         memcpy((void *)&tmp1, out + (len / 16) * 16, last_len);
 531         ((unsigned char *)(&tmp1))[last_len] = 0x80;
 532         ocb_block16_xor(&ctx->checksum, &tmp1, &ctx->checksum);
 533     }
 534
 535     ctx->blocks_processed = all_num_blocks;
 536
 537     return 1;
 538 }
 539
 540 /*
 541  * Calculate the tag and verify it against the supplied tag
 542  */
 543 int CRYPTO_ocb128_finish(OCB128_CONTEXT *ctx, const unsigned char *tag,
 544                          size_t len)
 545 {
 546     OCB_BLOCK tmp1, tmp2;
 547
 548     /*
 549      * Tag = ENCIPHER(K, Checksum_* xor Offset_* xor L_$) xor HASH(K,A)
 550      */
 551     ocb_block16_xor(&ctx->checksum, &ctx->offset, &tmp1);
 552     ocb_block16_xor(&tmp1, &ctx->l_dollar, &tmp2);
 553     ocb_encrypt(ctx, &tmp2, &tmp1, ctx->keyenc);
 554     ocb_block16_xor(&tmp1, &ctx->sum, &ctx->tag);
 555
 556     if (len > 16 || len < 1) {
 557         return -1;
 558     }
 559
 560     /* Compare the tag if we've been given one */
 561     if (tag)
 562         return CRYPTO_memcmp(&ctx->tag, tag, len);
 563     else
 564         return -1;
 565 }
 566
 567 /*
 568  * Retrieve the calculated tag
 569  */
 570 int CRYPTO_ocb128_tag(OCB128_CONTEXT *ctx, unsigned char *tag, size_t len)
 571 {
 572     if (len > 16 || len < 1) {
 573         return -1;
 574     }
 575
 576     /* Calculate the tag */
 577     CRYPTO_ocb128_finish(ctx, NULL, 0);
 578
 579     /* Copy the tag into the supplied buffer */
 580     memcpy(tag, &ctx->tag, len);
 581
 582     return 1;
 583 }
 584
 585 /*
 586  * Release all resources
 587  */
 588 void CRYPTO_ocb128_cleanup(OCB128_CONTEXT *ctx)
 589 {
 590     if (ctx) {
 591         if (ctx->l) {
 592             OPENSSL_cleanse(ctx->l, ctx->max_l_index * 16);
 593             OPENSSL_free(ctx->l);
 594         }
 595         OPENSSL_cleanse(ctx, sizeof(*ctx));
 596     }
 597 }
 598
 599 #endif                          /* OPENSSL_NO_OCB */