[PATCH 15/25] EAX: provide an implementation of EAX

[Mark Wooding]

Ian Jackson <ijackson at chiark.greenend.org.uk> wrote:

> Then for completeness we also provide a set of EAX-Serpent test
> vectors and the corresponding test code.  The EAX-Serpent test vectors
> were generated by this very code, so aren't independently verified.

I've understood how my Serpent implementation differs from Secnet's, and
have reproduced your test vectors.

NIST have managed to completely screw up their archive of the AES
contest pages, but the WayBack Machine works fine -- even on the various
PDF documents.

The sorry tale begins with the initial Request for Candidate Algorithm
Nominations, wherein the specification[1] for the test files unhelpfully
muddles things by implying a big-endian representation in the test
vector files, e.g., in 3.1, 

: Each of the possible key basis vectors is tested in this manner, by
: shifting the "1" a single position at a time, starting at the most
: significant (left-most) bit position of the key.

It doesn't help that the original Serpent C implementations in the
submission package[2] failed to implement the defined API correctly, and
implicitly coerced BYTE pointer (from the defined entry point
`blockEncrypt' to an `unsigned long' pointer as an argument to the
internal `serpent_encrypt' function.  The Java version carefully picks
words out of its input byte array in a little-endian order.

Secnet's implementation is derived from this original reference
implementation.  Originally, (v0.03) it had the same bug (only with
`uint8_t' and `uint32_t'), but was patched (v0.1.16) to correct the
obvious dependency on host endianness.  Unfortunately, this patch is
wrong: it creates a perfectly portable completely-byte-reversed Serpent
compatible with nothing else.  I've not found many other
implementations, but where I have, they agree with me and the Java
reference, and not with Secnet.

[1] http://web.archive.org/web/20000420040415/http://csrc.nist.gov/encryption/aes/katmct/katmct.htm
[2] http://www.cl.cam.ac.uk/~rja14/Papers/serpent.tar.gz

> diff --git a/Makefile.in b/Makefile.in
> index 182204b..6f36e4f 100644
> --- a/Makefile.in
> +++ b/Makefile.in

> +eax-%-test.confirm: eax-%-test eax-%-test.vectors
> +	./$< <eax-$*-test.vectors >$@.new
> +	mv -f $@.new $@

This should read

	./$< <$(srcdir)/eax-$*-test.vectors >$@.new

otherwise VPATH builds fail.

> diff --git a/eax.c b/eax.c
> new file mode 100644
> index 0000000..8c07fac
> --- /dev/null
> +++ b/eax.c

> +static void xor(uint8_t *dst, const uint8_t *a, const uint8_t *b, size_t l)
> +    /* simple block xor */
> +{
> +    while (l--)
> +	*dst++ = *a++ ^ *b++;
> +}

Annoyingly, `xor' is a reserved word in C++, and a macro defined in
<iso646.h>.  I'd recommend a different name, like `block_xor' or
something.

> +static void alg_omac_t_k(INFO, uint8_t *mac_out, uint8_t t,
> +			 const uint8_t *m, size_t m_len)
> +{
> +    cbc_init(I, mac_out);
> +
> +    uint8_t tn[n];
> +    memset(tn, 0, n-1);
> +    tn[n-1] = t;
> +
> +    if (!m_len) {
> +	/* We're running pad() on just [t]_n, so we have to xor B into
> +	 * [t]_n rather than some part of M */
> +	xor(tn, tn, INFO_B, n);
> +        cbc_iter(I, mac_out, tn);
> +	return;
> +    }
> +
> +    cbc_iter(I, mac_out, tn);
> +
> +    size_t in=0;
> +    for (; in+n < m_len; in+=n)
> +	cbc_iter(I, mac_out, m+in);
> +
> +    assert(in <= m_len);

Following the logic, you should have strict inequality here.

> +    size_t remain = m_len - in;
> +
> +    uint8_t lastblock[n];
> +    if (remain==n) {
> +	xor(lastblock, m+in, INFO_B, n);
> +    } else {
> +	assert(remain>0 && remain<n);
> +	memcpy(lastblock, m+in, remain);
> +	size_t pos=remain;
> +	lastblock[pos++] = 0x80;
> +	assert(pos<=n);
> +	memset(lastblock+pos, 0, n-pos);
> +	xor(lastblock, lastblock, INFO_P, n);
> +    }
> +    cbc_iter(I, mac_out, lastblock);
> +}

This can be made less fiddly, I think, by splitting `cbc_iter' in two
and delaying the `BLOCK_ENCRYPT' application.  Something like this
(tested).  This subsumes the `cbc_init' and `cbc_iter' functions, so I
removed them.

	static void alg_omac_t_k(INFO, uint8_t *mac_out, uint8_t t,
				 const uint8_t *m, size_t m_len)
	{
	    /* Initial tweak. */
	    memset(mac_out, 0, n-1);
	    mac_out[n-1] = t;

	    /* All of the whole blocks. */
	    size_t in=0;
	    for (; in+n <= m_len; in+=n) {
		BLOCK_ENCRYPT(mac_out, mac_out);
		xor(mac_out, mac_out, m+in, n);
	    }

	    /* The last partial block, if there is one. */
	    assert(in <= m_len);
	    size_t remain = m_len - in;
	    if (!remain)
		xor(mac_out, mac_out, INFO_B, n);
	    else {
		BLOCK_ENCRYPT(mac_out, mac_out);
		xor(mac_out, mac_out, m+in, remain);
		mac_out[remain] ^= 0x80;
		xor(mac_out, mac_out, INFO_P, n);
	    }

	    /* Final block-cipher application. */
	    BLOCK_ENCRYPT(mac_out, mac_out);
	}

Also, this file has lines containing trailing whitespace and a mix of
tabs and spaces for indentation, sometimes on the same line.  (My Emacs
goes into `angry-fruit-salad-mode'.)

-- [mdw]