| 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 |