[4915] in cryptography@c2.net mail archive
Re: permutations
daemon@ATHENA.MIT.EDU (David Wagner)
Sat Jun 19 22:20:14 1999
To: cryptography@c2.net
From: daw@cs.berkeley.edu (David Wagner)
Date: 18 Jun 1999 18:48:14 -0700
In article <376AC73C.50BA@counterpane.com>,
Mike Stay <stay@counterpane.com> wrote:
> Consider a cipher in which the key size and block size are equal, such
> as AES-128. The key specifies a pseudo-random permutation of the
> plaintexts, producing a ciphertext. [...] It's not
> necessarily true, however, that a plaintext specifies a permutation of
> the keys [...]
>
> What are the pros/cons of having only one key take a given plaintext to
> a given ciphertext?
The pro is that you get a more useful primitive; for instance, it looks
like a nice property to have if you want to build a hash function out of
the cipher using Davies-Meyer mode.
The con is that there are economies of scale in breaking this type of cipher.
Consider a cipher with 64-bit block size and key size, with the property
that when you fix a plaintext p the map k |-> E(k,p) is always a permutation.
(Some people call this object a multipermutation.)
Then the cipher can be broken with a time-space tradeoff that needs 2^64
work for the precomputation and 2^32 space. After the precomputation, each
subsequent key can be recovered with only one chosen plaintext and 2^32 work.
The algorithm is due to, I believe, Yao et. al. Alternatively, it may be
viewed as a straightforward extension of Hellman's time-space tradeoff.
