chiark / gitweb /
debian/changelog: Start new version 0.3.2~~
[secnet.git] / 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