Commit | Line | Data |
---|---|---|
9018e07a IJ |
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 |