contrib/bearssl/src/aead/eax.c

   1 /*
   2  * Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining
   5  * a copy of this software and associated documentation files (the
   6  * "Software"), to deal in the Software without restriction, including
   7  * without limitation the rights to use, copy, modify, merge, publish,
   8  * distribute, sublicense, and/or sell copies of the Software, and to
   9  * permit persons to whom the Software is furnished to do so, subject to
  10  * the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be
  13  * included in all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  18  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  19  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  20  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  21  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  22  * SOFTWARE.
  23  */
  24
  25 #include "inner.h"
  26
  27 /*
  28  * Implementation Notes
  29  * ====================
  30  *
  31  * The combined CTR + CBC-MAC functions can only handle full blocks,
  32  * so some buffering is necessary. Moreover, EAX has a special padding
  33  * rule for CBC-MAC, which implies that we cannot compute the MAC over
  34  * the last received full block until we know whether we are at the
  35  * end of the data or not.
  36  *
  37  *  - 'ptr' contains a value from 1 to 16, which is the number of bytes
  38  *    accumulated in buf[] that still needs to be processed with the
  39  *    current OMAC computation. Beware that this can go to 16: a
  40  *    complete block cannot be processed until it is known whether it
  41  *    is the last block or not. However, it can never be 0, because
  42  *    OMAC^t works on an input that is at least one-block long.
  43  *
  44  *  - When processing the message itself, CTR encryption/decryption is
  45  *    also done at the same time. The first 'ptr' bytes of buf[] then
  46  *    contains the encrypted bytes, while the last '16 - ptr' bytes of
  47  *    buf[] are the remnants of the stream block, to be used against
  48  *    the next input bytes, when available.
  49  *
  50  *  - The current counter and running CBC-MAC values are kept in 'ctr'
  51  *    and 'cbcmac', respectively.
  52  *
  53  *  - The derived keys for padding are kept in L2 and L4 (double and
  54  *    quadruple of Enc_K(0^n), in GF(2^128), respectively).
  55  */
  56
  57 /*
  58  * Start an OMAC computation; the first block is the big-endian
  59  * representation of the provided value ('val' must fit on one byte).
  60  * We make it a delayed block because it may also be the last one,
  61  */
  62 static void
  63 omac_start(br_eax_context *ctx, unsigned val)
  64 {
  65         memset(ctx->cbcmac, 0, sizeof ctx->cbcmac);
  66         memset(ctx->buf, 0, sizeof ctx->buf);
  67         ctx->buf[15] = val;
  68         ctx->ptr = 16;
  69 }
  70
  71 /*
  72  * Double a value in finite field GF(2^128), defined with modulus
  73  * X^128+X^7+X^2+X+1.
  74  */
  75 static void
  76 double_gf128(unsigned char *dst, const unsigned char *src)
  77 {
  78         unsigned cc;
  79         int i;
  80
  81         cc = 0x87 & -((unsigned)src[0] >> 7);
  82         for (i = 15; i >= 0; i --) {
  83                 unsigned z;
  84
  85                 z = (src[i] << 1) ^ cc;
  86                 cc = z >> 8;
  87                 dst[i] = (unsigned char)z;
  88         }
  89 }
  90
  91 /*
  92  * Apply padding to the last block, currently in ctx->buf (with
  93  * ctx->ptr bytes), and finalize OMAC computation.
  94  */
  95 static void
  96 do_pad(br_eax_context *ctx)
  97 {
  98         unsigned char *pad;
  99         size_t ptr, u;
 100
 101         ptr = ctx->ptr;
 102         if (ptr == 16) {
 103                 pad = ctx->L2;
 104         } else {
 105                 ctx->buf[ptr ++] = 0x80;
 106                 memset(ctx->buf + ptr, 0x00, 16 - ptr);
 107                 pad = ctx->L4;
 108         }
 109         for (u = 0; u < sizeof ctx->buf; u ++) {
 110                 ctx->buf[u] ^= pad[u];
 111         }
 112         (*ctx->bctx)->mac(ctx->bctx, ctx->cbcmac, ctx->buf, sizeof ctx->buf);
 113 }
 114
 115 /*
 116  * Apply CBC-MAC on the provided data, with buffering management.
 117  *
 118  * Upon entry, two situations are acceptable:
 119  *
 120  *   ctx->ptr == 0: there is no data to process in ctx->buf
 121  *   ctx->ptr == 16: there is a full block of unprocessed data in ctx->buf
 122  *
 123  * Upon exit, ctx->ptr may be zero only if it was already zero on entry,
 124  * and len == 0. In all other situations, ctx->ptr will be non-zero on
 125  * exit (and may have value 16).
 126  */
 127 static void
 128 do_cbcmac_chunk(br_eax_context *ctx, const void *data, size_t len)
 129 {
 130         size_t ptr;
 131
 132         if (len == 0) {
 133                 return;
 134         }
 135         ptr = len & (size_t)15;
 136         if (ptr == 0) {
 137                 len -= 16;
 138                 ptr = 16;
 139         } else {
 140                 len -= ptr;
 141         }
 142         if (ctx->ptr == 16) {
 143                 (*ctx->bctx)->mac(ctx->bctx, ctx->cbcmac,
 144                         ctx->buf, sizeof ctx->buf);
 145         }
 146         (*ctx->bctx)->mac(ctx->bctx, ctx->cbcmac, data, len);
 147         memcpy(ctx->buf, (const unsigned char *)data + len, ptr);
 148         ctx->ptr = ptr;
 149 }
 150
 151 /* see bearssl_aead.h */
 152 void
 153 br_eax_init(br_eax_context *ctx, const br_block_ctrcbc_class **bctx)
 154 {
 155         unsigned char tmp[16], iv[16];
 156
 157         ctx->vtable = &br_eax_vtable;
 158         ctx->bctx = bctx;
 159
 160         /*
 161          * Encrypt a whole-zero block to compute L2 and L4.
 162          */
 163         memset(tmp, 0, sizeof tmp);
 164         memset(iv, 0, sizeof iv);
 165         (*bctx)->ctr(bctx, iv, tmp, sizeof tmp);
 166         double_gf128(ctx->L2, tmp);
 167         double_gf128(ctx->L4, ctx->L2);
 168 }
 169
 170 /* see bearssl_aead.h */
 171 void
 172 br_eax_capture(const br_eax_context *ctx, br_eax_state *st)
 173 {
 174         /*
 175          * We capture the three OMAC* states _after_ processing the
 176          * initial block (assuming that nonce, message and AAD are
 177          * all non-empty).
 178          */
 179         int i;
 180
 181         memset(st->st, 0, sizeof st->st);
 182         for (i = 0; i < 3; i ++) {
 183                 unsigned char tmp[16];
 184
 185                 memset(tmp, 0, sizeof tmp);
 186                 tmp[15] = (unsigned char)i;
 187                 (*ctx->bctx)->mac(ctx->bctx, st->st[i], tmp, sizeof tmp);
 188         }
 189 }
 190
 191 /* see bearssl_aead.h */
 192 void
 193 br_eax_reset(br_eax_context *ctx, const void *nonce, size_t len)
 194 {
 195         /*
 196          * Process nonce with OMAC^0.
 197          */
 198         omac_start(ctx, 0);
 199         do_cbcmac_chunk(ctx, nonce, len);
 200         do_pad(ctx);
 201         memcpy(ctx->nonce, ctx->cbcmac, sizeof ctx->cbcmac);
 202
 203         /*
 204          * Start OMAC^1 for the AAD ("header" in the EAX specification).
 205          */
 206         omac_start(ctx, 1);
 207
 208         /*
 209          * We use ctx->head[0] as temporary flag to mark that we are
 210          * using a "normal" reset().
 211          */
 212         ctx->head[0] = 0;
 213 }
 214
 215 /* see bearssl_aead.h */
 216 void
 217 br_eax_reset_pre_aad(br_eax_context *ctx, const br_eax_state *st,
 218         const void *nonce, size_t len)
 219 {
 220         if (len == 0) {
 221                 omac_start(ctx, 0);
 222         } else {
 223                 memcpy(ctx->cbcmac, st->st[0], sizeof ctx->cbcmac);
 224                 ctx->ptr = 0;
 225                 do_cbcmac_chunk(ctx, nonce, len);
 226         }
 227         do_pad(ctx);
 228         memcpy(ctx->nonce, ctx->cbcmac, sizeof ctx->cbcmac);
 229
 230         memcpy(ctx->cbcmac, st->st[1], sizeof ctx->cbcmac);
 231         ctx->ptr = 0;
 232
 233         memcpy(ctx->ctr, st->st[2], sizeof ctx->ctr);
 234
 235         /*
 236          * We use ctx->head[0] as a flag to indicate that we use a
 237          * a recorded state, with ctx->ctr containing the preprocessed
 238          * first block for OMAC^2.
 239          */
 240         ctx->head[0] = 1;
 241 }
 242
 243 /* see bearssl_aead.h */
 244 void
 245 br_eax_reset_post_aad(br_eax_context *ctx, const br_eax_state *st,
 246         const void *nonce, size_t len)
 247 {
 248         if (len == 0) {
 249                 omac_start(ctx, 0);
 250         } else {
 251                 memcpy(ctx->cbcmac, st->st[0], sizeof ctx->cbcmac);
 252                 ctx->ptr = 0;
 253                 do_cbcmac_chunk(ctx, nonce, len);
 254         }
 255         do_pad(ctx);
 256         memcpy(ctx->nonce, ctx->cbcmac, sizeof ctx->cbcmac);
 257         memcpy(ctx->ctr, ctx->nonce, sizeof ctx->nonce);
 258
 259         memcpy(ctx->head, st->st[1], sizeof ctx->head);
 260
 261         memcpy(ctx->cbcmac, st->st[2], sizeof ctx->cbcmac);
 262         ctx->ptr = 0;
 263 }
 264
 265 /* see bearssl_aead.h */
 266 void
 267 br_eax_aad_inject(br_eax_context *ctx, const void *data, size_t len)
 268 {
 269         size_t ptr;
 270
 271         ptr = ctx->ptr;
 272
 273         /*
 274          * If there is a partial block, first complete it.
 275          */
 276         if (ptr < 16) {
 277                 size_t clen;
 278
 279                 clen = 16 - ptr;
 280                 if (len <= clen) {
 281                         memcpy(ctx->buf + ptr, data, len);
 282                         ctx->ptr = ptr + len;
 283                         return;
 284                 }
 285                 memcpy(ctx->buf + ptr, data, clen);
 286                 data = (const unsigned char *)data + clen;
 287                 len -= clen;
 288         }
 289
 290         /*
 291          * We now have a full block in buf[], and this is not the last
 292          * block.
 293          */
 294         do_cbcmac_chunk(ctx, data, len);
 295 }
 296
 297 /* see bearssl_aead.h */
 298 void
 299 br_eax_flip(br_eax_context *ctx)
 300 {
 301         int from_capture;
 302
 303         /*
 304          * ctx->head[0] may be non-zero if the context was reset with
 305          * a pre-AAD captured state. In that case, ctx->ctr[] contains
 306          * the state for OMAC^2 _after_ processing the first block.
 307          */
 308         from_capture = ctx->head[0];
 309
 310         /*
 311          * Complete the OMAC computation on the AAD.
 312          */
 313         do_pad(ctx);
 314         memcpy(ctx->head, ctx->cbcmac, sizeof ctx->cbcmac);
 315
 316         /*
 317          * Start OMAC^2 for the encrypted data.
 318          * If the context was initialized from a captured state, then
 319          * the OMAC^2 value is in the ctr[] array.
 320          */
 321         if (from_capture) {
 322                 memcpy(ctx->cbcmac, ctx->ctr, sizeof ctx->cbcmac);
 323                 ctx->ptr = 0;
 324         } else {
 325                 omac_start(ctx, 2);
 326         }
 327
 328         /*
 329          * Initial counter value for CTR is the processed nonce.
 330          */
 331         memcpy(ctx->ctr, ctx->nonce, sizeof ctx->nonce);
 332 }
 333
 334 /* see bearssl_aead.h */
 335 void
 336 br_eax_run(br_eax_context *ctx, int encrypt, void *data, size_t len)
 337 {
 338         unsigned char *dbuf;
 339         size_t ptr;
 340
 341         /*
 342          * Ensure that there is actual data to process.
 343          */
 344         if (len == 0) {
 345                 return;
 346         }
 347
 348         dbuf = data;
 349         ptr = ctx->ptr;
 350
 351         /*
 352          * We may have ptr == 0 here if we initialized from a captured
 353          * state. In that case, there is no partially consumed block
 354          * or unprocessed data.
 355          */
 356         if (ptr != 0 && ptr != 16) {
 357                 /*
 358                  * We have a partially consumed block.
 359                  */
 360                 size_t u, clen;
 361
 362                 clen = 16 - ptr;
 363                 if (len <= clen) {
 364                         clen = len;
 365                 }
 366                 if (encrypt) {
 367                         for (u = 0; u < clen; u ++) {
 368                                 ctx->buf[ptr + u] ^= dbuf[u];
 369                         }
 370                         memcpy(dbuf, ctx->buf + ptr, clen);
 371                 } else {
 372                         for (u = 0; u < clen; u ++) {
 373                                 unsigned dx, sx;
 374
 375                                 sx = ctx->buf[ptr + u];
 376                                 dx = dbuf[u];
 377                                 ctx->buf[ptr + u] = dx;
 378                                 dbuf[u] = sx ^ dx;
 379                         }
 380                 }
 381
 382                 if (len <= clen) {
 383                         ctx->ptr = ptr + clen;
 384                         return;
 385                 }
 386                 dbuf += clen;
 387                 len -= clen;
 388         }
 389
 390         /*
 391          * We now have a complete encrypted block in buf[] that must still
 392          * be processed with OMAC, and this is not the final buf.
 393          * Exception: when ptr == 0, no block has been produced yet.
 394          */
 395         if (ptr != 0) {
 396                 (*ctx->bctx)->mac(ctx->bctx, ctx->cbcmac,
 397                         ctx->buf, sizeof ctx->buf);
 398         }
 399
 400         /*
 401          * Do CTR encryption or decryption and CBC-MAC for all full blocks
 402          * except the last.
 403          */
 404         ptr = len & (size_t)15;
 405         if (ptr == 0) {
 406                 len -= 16;
 407                 ptr = 16;
 408         } else {
 409                 len -= ptr;
 410         }
 411         if (encrypt) {
 412                 (*ctx->bctx)->encrypt(ctx->bctx, ctx->ctr, ctx->cbcmac,
 413                         dbuf, len);
 414         } else {
 415                 (*ctx->bctx)->decrypt(ctx->bctx, ctx->ctr, ctx->cbcmac,
 416                         dbuf, len);
 417         }
 418         dbuf += len;
 419
 420         /*
 421          * Compute next block of CTR stream, and use it to finish
 422          * encrypting or decrypting the data.
 423          */
 424         memset(ctx->buf, 0, sizeof ctx->buf);
 425         (*ctx->bctx)->ctr(ctx->bctx, ctx->ctr, ctx->buf, sizeof ctx->buf);
 426         if (encrypt) {
 427                 size_t u;
 428
 429                 for (u = 0; u < ptr; u ++) {
 430                         ctx->buf[u] ^= dbuf[u];
 431                 }
 432                 memcpy(dbuf, ctx->buf, ptr);
 433         } else {
 434                 size_t u;
 435
 436                 for (u = 0; u < ptr; u ++) {
 437                         unsigned dx, sx;
 438
 439                         sx = ctx->buf[u];
 440                         dx = dbuf[u];
 441                         ctx->buf[u] = dx;
 442                         dbuf[u] = sx ^ dx;
 443                 }
 444         }
 445         ctx->ptr = ptr;
 446 }
 447
 448 /*
 449  * Complete tag computation. The final tag is written in ctx->cbcmac.
 450  */
 451 static void
 452 do_final(br_eax_context *ctx)
 453 {
 454         size_t u;
 455
 456         do_pad(ctx);
 457
 458         /*
 459          * Authentication tag is the XOR of the three OMAC outputs for
 460          * the nonce, AAD and encrypted data.
 461          */
 462         for (u = 0; u < 16; u ++) {
 463                 ctx->cbcmac[u] ^= ctx->nonce[u] ^ ctx->head[u];
 464         }
 465 }
 466
 467 /* see bearssl_aead.h */
 468 void
 469 br_eax_get_tag(br_eax_context *ctx, void *tag)
 470 {
 471         do_final(ctx);
 472         memcpy(tag, ctx->cbcmac, sizeof ctx->cbcmac);
 473 }
 474
 475 /* see bearssl_aead.h */
 476 void
 477 br_eax_get_tag_trunc(br_eax_context *ctx, void *tag, size_t len)
 478 {
 479         do_final(ctx);
 480         memcpy(tag, ctx->cbcmac, len);
 481 }
 482
 483 /* see bearssl_aead.h */
 484 uint32_t
 485 br_eax_check_tag_trunc(br_eax_context *ctx, const void *tag, size_t len)
 486 {
 487         unsigned char tmp[16];
 488         size_t u;
 489         int x;
 490
 491         br_eax_get_tag(ctx, tmp);
 492         x = 0;
 493         for (u = 0; u < len; u ++) {
 494                 x |= tmp[u] ^ ((const unsigned char *)tag)[u];
 495         }
 496         return EQ0(x);
 497 }
 498
 499 /* see bearssl_aead.h */
 500 uint32_t
 501 br_eax_check_tag(br_eax_context *ctx, const void *tag)
 502 {
 503         return br_eax_check_tag_trunc(ctx, tag, 16);
 504 }
 505
 506 /* see bearssl_aead.h */
 507 const br_aead_class br_eax_vtable = {
 508         16,
 509         (void (*)(const br_aead_class **, const void *, size_t))
 510                 &br_eax_reset,
 511         (void (*)(const br_aead_class **, const void *, size_t))
 512                 &br_eax_aad_inject,
 513         (void (*)(const br_aead_class **))
 514                 &br_eax_flip,
 515         (void (*)(const br_aead_class **, int, void *, size_t))
 516                 &br_eax_run,
 517         (void (*)(const br_aead_class **, void *))
 518                 &br_eax_get_tag,
 519         (uint32_t (*)(const br_aead_class **, const void *))
 520                 &br_eax_check_tag,
 521         (void (*)(const br_aead_class **, void *, size_t))
 522                 &br_eax_get_tag_trunc,
 523         (uint32_t (*)(const br_aead_class **, const void *, size_t))
 524                 &br_eax_check_tag_trunc
 525 };