eax.c

   1 /*
   2  * eax.c: implementation of the EAX authenticated encryption block cipher mode
   3  */
   4 /*
   5  * This file is Free Software.  It was originally written for secnet.
   6  *
   7  * Copyright 2013 Ian Jackson
   8  * Copyright 2013 Mark Wooding
   9  *
  10  * You may redistribute secnet as a whole and/or modify it under the
  11  * terms of the GNU General Public License as published by the Free
  12  * Software Foundation; either version 3, or (at your option) any
  13  * later version.
  14  *
  15  * You may redistribute this file and/or modify it under the terms of
  16  * the GNU General Public License as published by the Free Software
  17  * Foundation; either version 2, or (at your option) any later
  18  * version.
  19  *
  20  * This software is distributed in the hope that it will be useful,
  21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  23  * GNU General Public License for more details.
  24  *
  25  * You should have received a copy of the GNU General Public License
  26  * along with this software; if not, see
  27  * https://www.gnu.org/licenses/gpl.html.
  28  */
  29
  30 /*
  31  * This file is designed to be #included into another .c file which
  32  * sets up the environment.  It will declare or define three
  33  * functions, eax_setup, eax_encrypt and eax_decrypt.
  34  *
  35  * Manifest constants which are expected to be defined:
  36  *
  37  *  INFO       One or more formal parameter definitions.
  38  *             Used in all relevant function declarations.  Typically
  39  *             the application will use this for its context pointer,
  40  *             key schedule structure, etc.
  41  *
  42  *  I          Corresponding actual parameters for chaining onto
  43  *             sub-functions declared to take INFO parameters
  44  *
  45  *  EAX_ENTRYPOINT_DECL
  46  *             Declarator decoration for the three entry points.
  47  *             Typically either "static" or the empty string;
  48  *
  49  *  EAX_DECLARATIONS_ONLY
  50  *             Tested with #ifdef, so should be #defined to 1, or left
  51  *             undefined.  If defined, #including eax.c will produces
  52  *             only the function prototypes for the three entrypoints.
  53  *             Otherwise it will produce the implementation.
  54  *
  55  *  BLOCK_SIZE
  56  *             Constant expresion of integer type.
  57  *
  58  *  void BLOCK_ENCRYPT(uint8_t dst[n], const uint8_t src[n]);
  59  *
  60  *             Function to encrypt with the selected key.  The block
  61  *             cipher's key schedule (ie, the key) to be used is
  62  *             implicit; uses of BLOCK_ENCRYPT always occur in a
  63  *             context where the parameters defined by INFO are
  64  *             available.
  65  *
  66  *             So in a real application which wants to use more than
  67  *             one key at a time, BLOCK_ENCRYPT must be a macro which
  68  *             accesses the block cipher's key schedule via one of the
  69  *             INFO parameters.
  70  *
  71  *             BLOCK_ENCRYPT must tolerate dst==src.
  72  *
  73  *             EAX does not need to use the block cipher's decryption
  74  *             function.
  75  *
  76  *  uint8_t INFO_B[n], INFO_P[n];
  77  *
  78  *             Buffers used by the algorithm; they are written by
  79  *             eax_setup and used by eax_encrypt and eax_decrypt.
  80  *
  81  *             That is, effectively they are the part of the key
  82  *             schedule specific to EAX.
  83  *
  84  *             An application which wants to use more than one key at
  85  *             a time must define these as macros which refer to
  86  *             key-specific variables via one of the INFO parameters.
  87  *
  88  *  int consttime_memeq(const void *s1, const void *s2, size_t n);
  89  *
  90  *             Like !memcmp(s1,s2,n) but takes the same amount of time
  91  *             no matter where the discrepancy is.  Result must be
  92  *             a canonicalised boolean.
  93  *
  94  * The entrypoints which are then defined are:
  95  *
  96  *  void eax_setup(INFO)
  97  *
  98  *      Does the EAX-specific part of the key setup.  The block
  99  *      cipher key schedule must already have been done, as
 100  *      eax_setup uses BLOCK_ENCRYPT.
 101  *
 102  *  void eax_encrypt(INFO, const uint8_t nonce[nonce_len], size_t nonce_len,
 103  *                         const uint8_t h[h_len], size_t h_len,
 104  *                         const uint8_t m[m_len], size_t m_len,
 105  *                         uint8_t tau,
 106  *                         uint8_t ct[m_len+tau])
 107  *
 108  *      Does a single EAX authenticated encryption, providing
 109  *      confidentiality and integrity to the message m[0..m_len-1].
 110  *
 111  *      The output message is longer than m by tau bytes and is stored
 112  *      in the array ct which must be big enough.
 113  *
 114  *      nonce must never be repeated with the same key or the security
 115  *      of the system is destroyed, but it does not need to be secret.
 116  *      It is OK to transmit the nonce with the message along with the
 117  *      ciphertext and have the receiver recover it.
 118  *
 119  *      h is the "header" - it is some extra data which should be
 120  *      covered by the authentication, but not the encryption.  The
 121  *      output message does not contain a representation of h: it is
 122  *      expected to be transmitted separately (perhaps even in a
 123  *      different format).  (If h_len==0, h may be a NULL pointer.)
 124  *
 125  *      tau is the tag length - that is, the length of the message
 126  *      authentication code.  It should be chosen for the right
 127  *      tradeoff between message expansion and security (resistence to
 128  *      forgery).  It must be no longer than the block cipher block
 129  *      size.
 130  *
 131  *      For any particular key.  the tag length should be fixed.  (The
 132  *      tag length should NOT be encoded into the packet along with
 133  *      the ciphertext and extracted by the receiver!  Rather, the
 134  *      receiver must know what tag length to expect.)
 135  *
 136  *      It is permissible for ct==m, or for the arrays to be disjoint.
 137  *      They must not overlap more subtly.
 138  *
 139  *  _Bool eax_decrypt(INFO, const uint8_t nonce[nonce_len], size_t nonce_len,
 140  *                          const uint8_t h[h_len], size_t h_len,
 141  *                          const uint8_t ct[ct_len], size_t ct_len,
 142  *                          uint8_t tau,
 143  *                          uint8_t m[ct_len-tau])
 144  *
 145  *      Does a single EAX authenticated decryption.
 146  *
 147  *      On successful return, the plaintext message is written to m
 148  *      and eax_decrypt returns true.  The length of the plaintext
 149  *      message is always ct_len-tau.
 150  *
 151  *      If the message did not decrypt correctly, returns false.
 152  *      (There is no further indication of the nature of the error.)
 153  *      In this case the buffer m may contain arbitrary contents which
 154  *      should not be revealed to attackers.
 155  *
 156  *      nonce, h, tau are as above.
 157  *
 158  *      It is permissible to call eax_decrypt with an input message
 159  *      which is too short (i.e. shorter than tau) (notwithstanding
 160  *      the notation m[ct_len-tau] in the faux prototype above).
 161  *      In this case it will return false without touching m.
 162  *
 163  *      As with eax_decrypt, ct==m is permissible.
 164  */
 165
 166 /***** IMPLEMENTATION *****/
 167
 168 /*
 169  * We use the notation from the EAX paper, mostly.
 170  * (We write xscr for "x in fancy mathsy curly script".)
 171  *
 172  * See:
 173  *  Mihir Bellare, Phillip Rogaway, and David Wagner
 174  *
 175  *  _The EAX Mode of Operation
 176  *   (A Two-Pass Authenticated Encryption Scheme
 177  *   Optimized for Simplicity and Efficiency)_
 178  *
 179  * Preliminary version in:
 180  *   Fast Software Encryption (FSE) 2004. Lecture Notes in Computer Science,
 181  *   vol. ??, pp. ??--??.
 182  *
 183  * Full version at:
 184  *  http://www.cs.ucdavis.edu/~rogaway/papers/eax.html
 185  */
 186 /*
 187  * In general, all functions tolerate their destination arrays being
 188  * the same pointer to their source arrays, or totally distinct.
 189  * (Just like BLOCK_ENCRYPT and the public eax entrypoints.)
 190  * They must not overlap in more subtle ways.
 191  */
 192
 193 #define n ((size_t)BLOCK_SIZE)
 194
 195 #ifndef EAX_DECLARATIONS_ONLY
 196
 197 static void xor_block(uint8_t *dst, const uint8_t *a, const uint8_t *b,
 198                       size_t l)
 199     /* simple block xor */
 200 {
 201     while (l--)
 202         *dst++ = *a++ ^ *b++;
 203 }
 204
 205 static void increment(uint8_t *value)
 206     /* value is a single block; incremented (BE) mod 256^n */
 207 {
 208     uint8_t *p;
 209     for (p=value+n; p>value; )
 210         if ((*--p)++) break;
 211 }
 212
 213 static void alg_ctr(INFO, uint8_t *c, const uint8_t *nscr,
 214                     const uint8_t *m, size_t m_len)
 215 {
 216     uint8_t blocknonce[n], cipher[n];
 217     size_t in;
 218
 219     memcpy(blocknonce, nscr, n);
 220     for (in=0; in<m_len; in+=n) {
 221         BLOCK_ENCRYPT(cipher,blocknonce);
 222         increment(blocknonce);
 223         size_t now = m_len-in < n ? m_len-in : n;
 224         xor_block(c+in, m+in, cipher, now);
 225     }
 226 }
 227
 228 static void alg_omac_t_k(INFO, uint8_t *mac_out, uint8_t t,
 229                          const uint8_t *m, size_t m_len)
 230 {
 231     /* Initial tweak. */
 232     memset(mac_out, 0, n-1);
 233     mac_out[n-1] = t;
 234
 235     /* All of the whole blocks. */
 236     size_t in=0;
 237     for (; in+n <= m_len; in+=n) {
 238         BLOCK_ENCRYPT(mac_out, mac_out);
 239         xor_block(mac_out, mac_out, m+in, n);
 240     }
 241
 242     /* The last partial block, if there is one. */
 243     assert(in <= m_len);
 244     size_t remain = m_len - in;
 245     if (!remain)
 246         xor_block(mac_out, mac_out, INFO_B, n);
 247     else {
 248         BLOCK_ENCRYPT(mac_out, mac_out);
 249         xor_block(mac_out, mac_out, m+in, remain);
 250         mac_out[remain] ^= 0x80;
 251         xor_block(mac_out, mac_out, INFO_P, n);
 252     }
 253
 254     /* Final block-cipher application. */
 255     BLOCK_ENCRYPT(mac_out, mac_out);
 256 }
 257
 258 /*
 259  * Constant-time multiply-by-x in F = GF(2^128), using the EAX representation
 260  * F = GF(2)[x]/(x^128 + x^7 + x^2 + x + 1).
 261  *
 262  * The input vector V consists of the input polynomial L = a_127 x^127 +
 263  * ... + a_1 x + a_0; specifically, the byte v[15 - i] contains a_{8i+7}
 264  * x^{8i+7} + ... + a_{8i} x^{8i}.  The output vector O will contain L x on
 265  * exit, using the same encoding.
 266  *
 267  * It is fine if O = V, or the two vectors are disjoint; Bad Things will
 268  * happen if they overlap in some more complicated way.
 269  */
 270 static void consttime_curious_multiply(INFO, uint8_t *o, const uint8_t *v)
 271 {
 272 #define POLY 0x87u
 273
 274   unsigned m = ~((v[0] >> 7) - 1u) & POLY;
 275   unsigned i, mm;
 276
 277   for (i = n - 1; i < n; i--) {
 278     mm = (v[i] >> 7) & 1u;
 279     o[i] = (v[i] << 1) ^ m;
 280     m = mm;
 281   }
 282
 283 #undef POLY
 284 }
 285
 286 #endif /* not EAX_DECLARATIONS_ONLY */
 287
 288 EAX_ENTRYPOINT_DECL
 289 void eax_setup(INFO)
 290 #ifndef EAX_DECLARATIONS_ONLY
 291 {
 292     uint8_t work[n];
 293     memset(work,0,n);
 294     BLOCK_ENCRYPT(work,work);
 295     consttime_curious_multiply(I, INFO_B, work);
 296     consttime_curious_multiply(I, INFO_P, INFO_B);
 297 }
 298 #endif /* not EAX_DECLARATIONS_ONLY */
 299 ;
 300
 301 EAX_ENTRYPOINT_DECL
 302 void eax_encrypt(INFO,
 303                  const uint8_t *nonce, size_t nonce_len,
 304                  const uint8_t *h, size_t h_len,
 305                  const uint8_t *m, size_t m_len, uint8_t tau, uint8_t *ct)
 306 #ifndef EAX_DECLARATIONS_ONLY
 307 {
 308     assert(tau <= n);
 309     uint8_t nscr[n], hscr[n], cscr[n];
 310     alg_omac_t_k(I, nscr, 0, nonce,nonce_len);
 311     alg_omac_t_k(I, hscr, 1, h,h_len);
 312     alg_ctr(I, ct, nscr, m, m_len);
 313     alg_omac_t_k(I, cscr, 2, ct, m_len);
 314     uint8_t *t = ct + m_len;
 315     xor_block(t, nscr, cscr, tau);
 316     xor_block(t, t, hscr, tau);
 317 }
 318 #endif /* not EAX_DECLARATIONS_ONLY */
 319 ;
 320
 321 EAX_ENTRYPOINT_DECL
 322 _Bool eax_decrypt(INFO,
 323                   const uint8_t *nonce, size_t nonce_len,
 324                   const uint8_t *h, size_t h_len,
 325                   const uint8_t *ct, size_t ct_len, uint8_t tau, uint8_t *m)
 326 #ifndef EAX_DECLARATIONS_ONLY
 327 {
 328     assert(tau <= n);
 329     const uint8_t *t;
 330     uint8_t nscr[n], hscr[n], cscr[n], tprime[tau];
 331     if (ct_len < tau) return 0;
 332     size_t m_len = ct_len - tau;
 333     t = ct + m_len;
 334     alg_omac_t_k(I, nscr, 0, nonce,nonce_len);
 335     alg_omac_t_k(I, hscr, 1, h,h_len);
 336     alg_omac_t_k(I, cscr, 2, ct,m_len);
 337     xor_block(tprime, nscr, cscr, tau);
 338     xor_block(tprime, tprime, hscr, tau);
 339     if (!consttime_memeq(tprime, t, tau)) return 0;
 340     alg_ctr(I, m, nscr, ct, m_len);
 341     return 1;
 342 }
 343 #endif /* not EAX_DECLARATIONS_ONLY */
 344 ;
 345
 346 #undef n