[tahoe-dev] FW: cleversafe says: 3 Reasons Why Encryption isOverrated

[Jason Resch]

Zooko O'Whielacronx wrote:
>
> On Mon, Aug 10, 2009 at 3:40 PM, Jason Resch<jresch at cleversafe.com> wrote:
> >
> > Recalling what the original poster said:
> > "Surely this is fundamental to threshold secret sharing - until you
> > reach the threshold, you have not reduced the cost of an attack?"
> >
> > Cleversafe's method does have this property, the difficulty in breaking the random transformation key does not decrease with the number of slices an attacker gets.  Though the difficulty is not infinite, (as is the case with an information theoretically secure scheme) it does remain fixed until a threshold is reached.
>
> That isn't correct.  The more slices an attacker has access to, the
> more information they have which they might be able to use to break
> the encryption.  This is equivalent to saying that "the difficulty"
> (in the sense of computationally secure cryptography) decreases.  Now,
> if the encryption scheme (in this case one formed out of AES-256 and a
> hash function) is secure, then whatever information they gain won't
> help them (until they reach the threshold), so "the difficulty"
> remains too difficult for them (until they reach the threshold).

There are two routes one may take to breaking the security of AONT+Dispersal with less than a threshold number of slices:

1. Attempt to brute force the transformation key, having complexity 2^256 (For a 256-bit transformation key)
2. Attempt to brute force the missing data of the transformed package, having complexity 2^(Bits missing)

Let's look at a near worst-case scenario for us, where slices are very small, and the threshold is high, for our block interface we disperse a 4096 block into 16 pieces with a threshold of 10:

Each slice will be approximately 400 bytes in length.  Therefore if two slices short of the threshold, one has the choice of either attacking the key (2^256), or attacking the missing data (2^800).  If the attacker gains one additional slice, meaning one slice short of the threshold, the attacker has the choice of 2^256 or 2^400.  At no point short of the threshold does the complexity of attack drop below that of compromising the encryption key.

Where this doesn't hold is if the message is extremely small to begin with, say 50 bytes, and we dispersed them into 5 byte slices.  In that case, brute forcing the missing data could be easier than brute forcing the key, but it is an atypcical case for us and can be alleviated by padding small objects up to a minimum size of key_length*threshold.

Short of there being some specific attack against the cipher I don't see how having more ciphertext available makes brute forcing the key any easier.

> However, if the encryption scheme is less than perfect, then maybe
> they can crack the system without having a threshold number of the
> slices.  This is just the normal definition of a
> computationally-secure cryptosystem based on an encryption scheme.
If the cipher were critically flawed in a way where more ciphertext made an attack easier then I concur that the same attack would carry through to AONT.  Using a cipher without this weakness, however, should result in a system that has the same level of security regardless of the number of slices an attacker posses, short of the threshold of course.
>
> The AONT design doesn't make it stronger in the case of a weak cipher
> or a weak hash function than a similar design such as Tahoe-LAFS.
> Indeed, the AONT arguably makes it weaker.
How so?

Tahoe-LAFS depends on hash functions, symmetric ciphers, and asymmetric ciphers.  AONT+Dispersal depends on hash functions and symmetric ciphers.
>
>
> Hm, your overview diagram [1] doesn't say what hash function is used
> to generate the mask for the AONT, but this document [2] says you are
> using MD5.  However, [2] also says you are using AES-128 which
> contradicts [1]'s statement that you are using AES-256, so I'll bet
> [2] is obsolete.  Could you point to more details about the
> implementation of the AONT and the other algorithms?
>
> Thanks!
>
> Regards,
>
> Zooko
>
> [1] http://dev.cleversafe.org/weblog/?p=111
> [2] http://www.cleversafe.org/documentation/Cleversafe-Arch.pdf

I'm afraid the documentation you cite is outdated, it does not even mention the AONT.  Our current implementation supports RC4 and AES, each with key lengths of 128, 192, or 256 bits.  For 128-bit keys, the hash function is specified to be MD5, for 192- or 256-bit keys, the specified hash function is SHA-256.  The left most bits of the hash are used to mask the transformation key.  The detailed documentation you requested is still in development, but should be made public shortly.


Jason