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

Jeffrey Walton noloader at gmail.com
Mon Nov 29 15:25:57 UTC 2010


Hi All,

I find Tahoe-LAFS an interesting and needed project (and I have a lot
of respect for Zooko in other circles), so I thought the project might
find the following useful. Please take it for what its worth.

>From reading "Add combined AES+XSalsa20 cipher module",
http://tahoe-lafs.org/trac/pycryptopp/ticket/46:

   For preserving confidentiality in the event of a break in AES, we
   want to combine AES (256 bit, CTR mode) with XSalsa20. This will
   simply process the message with both in sequence; it doesn't matter
   which order they are applied in, as both are effectively key stream
   generators, so AES-CTR(XSalsa20(m)) == XSalsa20(AES-CTR(m)).
   ....

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.

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)

3) A flaw in one component could allow subverting the other component.
   Interestingly, ticket 46 attempts to remdiate a compromise in one
   component with a cascade.

4) Key material independence is not only more difficult due to larger
   key bit requirements, it is required for the security of the system.

Bad interactions between components have plagued cryptography. History
has shown its very easy to combine secure components in such that the
resulting system is insecure. Confer: CBC mode encryption and
CBC-MACs. The problem was so wide spread in data authentication that
the cryptographic community (and bodies such as IEEE, IETF, ISO, NIST,
and NESSIE) began supplying authenticated encryption modes.

A search of sci.crypt might offer some interesting reading: [1].
Schneier covers it in Applied Cryptography (which is not handy at the
moment): Chapter 15: Combining Block Algorithms, and Chapter 17:
Other Stream Ciphers and Real Random-Sequence Generators. Keep in mind
that Applied Cryptography is not the HAC, (and the HAC is dated) so
take it for what its worth.

I'm aware of a few papers on the subject, but I have never fully
researched the topic since I don't use the construction [2,3]. From
the Massey and Maurer paper [3], here's the extent of my knowledge:

    * 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
    * Even and Goldreich's theorem holds only under unrealistic and
      restrictive assumptions, which are not explicitly stated [sic]
    * Folk Theorem: A cascade of ciphers is at least as difficult to
      break as any of its component

Jeff

* If the keys are *not* independent, the construction is known as a
"product cipher".

[1] http://groups.google.com/group/sci.crypt/search?group=sci.crypt&q=cipher+cascading&qt_g=Search+this+group
[2] Even and Goldreich, On the Power of Cascade Ciphers. 1985
[3] Massey and Maurer, Cascade ciphers: The importance of being first. 1993



More information about the tahoe-dev mailing list