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