eax.c

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