[tahoe-dev] Using a cipher cascade (was: survey on side-channel attacks)

[David-Sarah Hopwood]

Zooko O'Whielacronx wrote:
> Nate Lawson (a good security researcher) wrote a nice article
> summarizing side-channel attacks [1].  It includes this discouraging
> line: "Unfortunately, owing to the structure of AES, there appears to
> be no way to build a high-performance implementation on a
> general-purpose CPU while avoiding cache side channels.".  This is why
> I want to switch from AES to XSalsa20 [2].

If an attacker can run on the same machine as the gateway server, then
there are currently much more serious attacks than against the crypto,
e.g. the variant of #870 where the attacker binds to the webapi port first.

OTOH, the existence of one attack is not a reason to miss an opportunity
to fix another, if they can be fixed independently.

> (Also because XSalsa20 uses much less power and/or time [3].)

Is the AES encryption a significant bottleneck in Tahoe? Anyway,
<http://cr.yp.to/snuffle/salsafamily-20071225.pdf> says that on a Core-2,
Salsa20/20 encrypts in 3.93 cycles/byte and AES in ~9.2 cycles/byte, so
a cascade of AES and Salsa should be not much slower than AES alone.
(Like CTR-mode AES, Salsa is block-parallelisable; see section 3.1 of
that paper.)

> Unfortunately, "AES" is a
> successful brand -- it is the only crypto brand that matters and it
> appears on all crypto products -- and if we offer our users XSalsa20
> instead, even though they will probably be safer, they will probably
> think that we are making them less safe.  :-(

As you say, marketing does matter. Dan Bernstein is highly competent,
and I have no reason to question Salsa20 or XSalsa20's security.
OTOH, just the fact that few non-cryptographers have heard of it
is a cause for hesitation.

If we use a cascade, then if either AES or Salsa were broken (even
only a technical break), we'd still have to replace that cipher in
the cascade. But this does suggest a long-term strategy for cipher
evolution -- whenever a significant attack is found against
one of the ciphers in the cascade, add support for replacing that
cipher with another for decryption, and then in a later version,
change to using the new cascade for encryption.

If each key is 256 bits, there should be no realistic possibility
of a meet-in-the-middle attack against the cascade. (As far as I know,
the related-key attacks against 256-bit AES depend entirely on related
keys and are of no concern if the key is generated by a conservative KDF.)

Incidentally, Bernstein has a very good paper on why to use keys
longer than 128 bits (he suggests 256 bits):
<http://cr.yp.to/snuffle/bruteforce-20050425.pdf>
A summary is that parallel key search for multiple keys can be done
with almost the same work factor (that is, machine size * time) as a
search for a single key. (The recent publication of Rainbow tables
for the GSM cipher A5/1, which has a 64-bit key, is a practical
demonstration of the perils of short key sizes -- these tables allow
A5/1 to be broken for *any* key with much less than 2^64 work.)

I've updated <http://allmydata.org/trac/tahoe/wiki/NewCaps/WhatCouldGoWrong>
with a footnote to make it clearer what the brute force cost estimates
mean for parallel and multi-key attacks.

> I posted this same note on my blog (and posted it to identi.ca which
> reposted it to twitter):
> http://testgrid.allmydata.org:3567/uri/URI:DIR2-RO:j74uhg25nwdpjpacl6rkat2yhm:kav7ijeft5h7r7rxdp5bgtlt3viv32yabqajkrdykozia5544jqa/wiki.html
> 
> Also as my new co-worked Brendan O'Connor reminded me on twitter, US
> Gov is required by Federal law not to rely on crypto other than AES.
> :-(

Do you have a more precise reference? Presumably it can rely also on
SHA-256 as a cryptographic hash?

> If the only problem were the potential for algorithmic cracks of AES
> then we could solve this problem (at a cost in power and/or time) by
> *combining* AES and XSalsa20. Unfortunately, if AES is leaking its
> secrets by a timing channel then this won't help.
> 
> Oh wait!  Yes, it *could* help.  Encrypt *first* with XSalsa20, *then*
> with AES, giving AES a key which cannot be used to figure out the key
> that we gave to XSalsa20.  That way even if AES completely divulges
> its key *and* its plaintext to the enemy, we're still safe.  Hooray!

I'll take this into account when designing the successor to the Elk Point
designs, which will be called Rainhill 3. (Rainhill is where I live.
Rainhill 1 and 2 are abandoned designs; like Elk Point 1, they were more
complicated than necessary.)

The approach I would suggest is to derive the encryption key for a given
algorithm using a hash-based KDF (for example HKDF) with the following
inputs:

  tag:         separates this from other uses of the KDF,
                 and mutable from immutable
  algorithm:   separates AES, Salsa20, etc.
  fork_id:     can be used to separate forks of the file from each other,
                 e.g. for deep-verify caps or encrypted metadata
  version_id:  version of a mutable file
  block_num:   block number of a mutable file, to support random access
  UEB:         the contents of the URL extension block
  read_secret: the secret value (e.g. K1 in Elk Point)

Note that the read_secret may have less entropy than the number of bits
in the encryption key, because it is constrained by the length of a read
cap. The encryption keys should each be at least 256 bits, for the reasons
explained in Bernstein's paper on brute force referenced above.
Including the UEB contents in the KDF input effectively acts as a
salt to prevent the simultaneous attacks against multiple keys described
in that paper (this is the same principle as salting a limited-entropy
password). Of course the cost of an attack against a single key is still
limited by the read_secret length, since that's the only secret input.

Note that with this approach, the extended nonce in XSalsa
(http://cr.yp.to/snuffle/xsalsa-20081128.pdf) isn't really necessary.
Using plain Salsa20/20 (even with a zero nonce, or by deriving the
nonce in the same way as the key), might reduce implementation complexity.

-- 
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 292 bytes
Desc: OpenPGP digital signature
Url : http://allmydata.org/pipermail/tahoe-dev/attachments/20100105/29e84bd2/attachment.pgp