[tahoe-dev] Tahoe-LAFS Ticket 46 (Add combined AES+XSalsa20 cipher module)

[Jack Lloyd]

On Mon, Nov 29, 2010 at 10:25:57AM -0500, Jeffrey Walton wrote:

> AES-CTR(XSalsa20(msg)) is known as "cascading" if the keys are
> independent*. Depending on whom you ask, the feature is generally not
> desired. Paranoid cryptographers feel that the construction presents a
> number of undesirable traits. I fall into this group even though I'm
> not a cryptographer. The paranoid have [at least] three concerns,
> which I believe can be broadly digested to "increased attack surface":
> 
> 1) AES and SHA are two primitives that must perform flawlessly 100% of the
>     time. AES, SHA, and Salsa20 are three primitives that must perform
>    flawlessly 100% of the time. The later is a 50% increase in primitives.

Could you explain what you mean by this? Since AES-CTR and XSalsa20
commute (they both just generate a keystream that is XORed with the
plaintext), it doesn't matter

And in fact from the abstract of your ref [3]:

"""
A consequence of this result is that if the ciphers commute, then a
cascade is at least as difficult to break as the
most-difficult-to-break component cipher, i.e., the intuition that a
cryptographic chain is at least as strong as its strongest link is
then provably correct. It is noted that additive stream ciphers do
commute, and this fact is used to suggest a strategy for designing
secure practical ciphers.
"""
 (http://www.springerlink.com/content/2281r01440482637/)

> 2) If cipher = Salsa(AES(message)) has a bad interaction between AES and
>    Salsa, there could be a scheme ENC' (or DEC') such that:
> 
>      Salsa(AES(message)) == ENC'(message) and
>      Salsa(AES(cipher)) == DEC'(cipher)

Assuming the keys are independent, wouldn't a property of this form
imply a method to distinguish AES with a random key from a random
permutation?

>     * The ciphers should be additive stream ciphers since they
>       are known to commute. On the surface, I'm not convinced
>       Salsa(AES(message)) is additive

If AES was used as a permutation on the input, say with
Salsa(AES-CBC(msg)), then no this would not commute. But AES-CTR is
just another keystream generator, so:

AES-CTR(Salsa(m)) == Salsa(AES-CTR(m))

Which means the result from [3] applies. Yay!

-Jack