2 * eax.c: implementation of the EAX authenticated encryption block cipher mode
5 * Copyright 2013 Ian Jackson
6 * Copyright 2013 Mark Wooding
8 * This file is Free Software. It was originally written for secnet.
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
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.
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.
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.
30 * Manifest constants which are expected to be defined:
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.
37 * I Corresponding actual parameters for chaining onto
38 * sub-functions declared to take INFO parameters
41 * Declarator decoration for the three entry points.
42 * Typically either "static" or the empty string;
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.
51 * Constant expresion of integer type.
53 * void BLOCK_ENCRYPT(uint8_t dst[n], const uint8_t src[n]);
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
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
66 * BLOCK_ENCRYPT must tolerate dst==src.
68 * EAX does not need to use the block cipher's decryption
71 * uint8_t INFO_B[n], INFO_P[n];
73 * Buffers used by the algorithm; they are written by
74 * eax_setup and used by eax_encrypt and eax_decrypt.
76 * That is, effectively they are the part of the key
77 * schedule specific to EAX.
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.
83 * int consttime_memeq(const void *s1, const void *s2, size_t n);
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.
89 * The entrypoints which are then defined are:
91 * void eax_setup(INFO)
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.
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,
101 * uint8_t ct[m_len+tau])
103 * Does a single EAX authenticated encryption, providing
104 * confidentiality and integrity to the message m[0..m_len-1].
106 * The output message is longer than m by tau bytes and is stored
107 * in the array ct which must be big enough.
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.
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.)
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
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.)
131 * It is permissible for ct==m, or for the arrays to be disjoint.
132 * They must not overlap more subtly.
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,
138 * uint8_t m[ct_len-tau])
140 * Does a single EAX authenticated decryption.
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.
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.
151 * nonce, h, tau are as above.
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.
158 * As with eax_decrypt, ct==m is permissible.
161 /***** IMPLEMENTATION *****/
164 * We use the notation from the EAX paper, mostly.
165 * (We write xscr for "x in fancy mathsy curly script".)
168 * Mihir Bellare, Phillip Rogaway, and David Wagner
170 * _The EAX Mode of Operation
171 * (A Two-Pass Authenticated Encryption Scheme
172 * Optimized for Simplicity and Efficiency)_
174 * Preliminary version in:
175 * Fast Software Encryption (FSE) 2004. Lecture Notes in Computer Science,
176 * vol. ??, pp. ??--??.
179 * http://www.cs.ucdavis.edu/~rogaway/papers/eax.html
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.
188 #define n ((size_t)BLOCK_SIZE)
190 #ifndef EAX_DECLARATIONS_ONLY
192 static void xor_block(uint8_t *dst, const uint8_t *a, const uint8_t *b,
194 /* simple block xor */
197 *dst++ = *a++ ^ *b++;
200 static void increment(uint8_t *value)
201 /* value is a single block; incremented (BE) mod 256^n */
204 for (p=value+n; p>value; )
208 static void alg_ctr(INFO, uint8_t *c, const uint8_t *nscr,
209 const uint8_t *m, size_t m_len)
211 uint8_t blocknonce[n], cipher[n];
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);
223 static void alg_omac_t_k(INFO, uint8_t *mac_out, uint8_t t,
224 const uint8_t *m, size_t m_len)
227 memset(mac_out, 0, n-1);
230 /* All of the whole blocks. */
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);
237 /* The last partial block, if there is one. */
239 size_t remain = m_len - in;
241 xor_block(mac_out, mac_out, INFO_B, n);
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);
249 /* Final block-cipher application. */
250 BLOCK_ENCRYPT(mac_out, mac_out);
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).
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.
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.
265 static void consttime_curious_multiply(INFO, uint8_t *o, const uint8_t *v)
269 unsigned m = ~((v[0] >> 7) - 1u) & POLY;
272 for (i = n - 1; i < n; i--) {
273 mm = (v[i] >> 7) & 1u;
274 o[i] = (v[i] << 1) ^ m;
281 #endif /* not EAX_DECLARATIONS_ONLY */
285 #ifndef EAX_DECLARATIONS_ONLY
289 BLOCK_ENCRYPT(work,work);
290 consttime_curious_multiply(I, INFO_B, work);
291 consttime_curious_multiply(I, INFO_P, INFO_B);
293 #endif /* not EAX_DECLARATIONS_ONLY */
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
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);
313 #endif /* not EAX_DECLARATIONS_ONLY */
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
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;
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);
338 #endif /* not EAX_DECLARATIONS_ONLY */