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