Re: David's authenticated encryption mode.

David Gothberg <david.gothberg@xxxxxxxxx> wrote:

It has not been checked by professional cryptographers so we do not
know if it is secure.

Brief description follows.

Let f_k be a family of pseudorandom functions. Fix a key k, and an
initialization vector v. Let the input message be split into blocks
x_0, x_1, ..., x_{n-1}. Set x_n to be some kind of length indicator
(precice nature is unclear from the description).

Let:

z_0 = f_k(v)
z_i = f_{k xor i xor z_{i-1}}(x_{i-1})
y_i = x_i xor z_i

Then y_0, y_1, ..., y_{n-1} are the ciphertext and z_{n+1} is the tag.

The author suggests instantiating f_k using a pseudorandom permutation
E_k(.) as follows:

f_k(x) = E_k(x) xor k xor x

Objections:

* I'm not aware of many block ciphers which can provide sufficient
key-agility to make this a particularly efficient mode of operation.

* The standard definition of security for a PRF allows the possibility
of related-key attacks. Your design seems to give rather more
information about key inputs than I'd feel entirely comfortable
with. I don't have any immediate attacks beyond my vague
nervousness.

* There's no proof of security. There have been many proposed
authenticated-encryption modes which made n + o(1) block cipher
applications, and before Jutla's paper (see below) they were being
proposed and broken so often that people started trying to prove
that such a thing was an impossiblity.

: Authenticated encryption modes like this mode causes the block cipher
: to re-key for each block operation. In many block ciphers rekeying
: takes some time, which probably makes modes like this slower than just
: using CTR mode and HMAC together. So ideally a block mode should not
: cause rekeying. I don't know if it is possible to design a secure
: authenticated encryption mode that only uses one block operation per
: message block and no rekeying (and perhaps 1-2 additional block
: operations for set-up and finalisation), but it would be very neat.

You've not done much research, then.

In 2001, Charanjit Jutla described `Encryption Modes with Almost Free
Message Integrity' -- i.e., using n + o(1) block cipher applications.
He actually described two modes: IACBC and IAPM. The former looks quite
similar to CBC mode; the latter is more interesting, because it allows
the message blocks to be processed in parallel. He also proved both his
modes secure, in the sense of showing a reduction from the security of
the underlying block cipher. His constructions require two keys for the
underlying block cipher.

Gligor and Donescu described XCBC and XECB not long afterwards (I
remember little about these schemes except for the paper describing them
being very hard to read); and Phillip Rogaway published OCB -- Offset
Codebook -- which `crypto- engineered' Jutla's IAPM into something truly
practical, in particular, using only a single key. He later enhanced
OCB to provide AEAD -- authenticated encryption with additional data --
i.e., to have the authentication tag for an encrypted message depend not
only on the encrypted message itself (to show that it hasn't been
tampered with) but also some auxiliary data. He also provided a proof
of security for OCB.

All the above schemes are covered by patents, which has limited their
use. A slew of other, unpatented, designs followed, some of which made
less efficient use of their block cipher. The best of these look as if
they're CWC (Kohno, Viega and Whiting) and GCM (Viega and McGrew).

For more information, see the survey by Greg Rose, at

http://www.qualcomm.com.au/PublicationsDocs/Enc+MAC%20paper.pdf

-- [mdw]
.

Relevant Pages