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

Sat Jul 25 14:01:43 PDT 2009

Russ Weeks wrote:

> Yikes, that All-Or-Nothing transform, that's an interesting algorithm.
>

It certainly is.  When first described by Ron Rivest, it was mostly a curiosity with little practical benefit, and therefore had been mostly forgotten. However, when it is combined with an information dispersal algorithm, the combined system has many of the properties of the Shamir Secret Sharing Scheme, but maintaining the perfect storage efficiency of the IDA.

> Seems to me that it reduces the security of AES-256 to the security of
> the dispersal algorithm.  If I control a subset of malicious nodes
> within the distributed storage system, and I can convince the sender
> (via DDOS or some network coordinate trickery, perhaps) to spread K
> slices of user data amongst my nodes, then I can recover the user
> data.

To see the security benefits of this approach it is best to think of AES as a special case of this system where K = N = 2.  Where one "slice" is the encrypted data and the other slice is the key.  To compromises this system an attacker must compromise data from two locations, the location where encrypted data is kept and the location where the key is kept.  Disperal+AONT can improve upon this, as K can be greater than 2, forcing an attacker to have to compromise a large number of locations.  Additionally, N can be greater than K, therefore yielding a higher degree of reliability, where in the simple case of AES, one would have to make copies of the key and data to increase the reliability (but this decreases confidentiality).

The system you envisage is one in which the owner of the system is different from the user of the system.  You are correct that this system would not be secure if one stored >=K number of slices on untrusted machines, but the same is true for AES: one couldn't store their key and encrypted data on machines they didn't trust and expect their data to be safe.  Of all the ways to store secret keys reliabily and confidentially, secret sharing schemes are the best known technique.  Dispersal+AONT allows one to store their data itself in the same way that people have been storing their keys when using a secret sharing scheme.  Therefore it can be somewhat redundant to use a traditional key based system along with dispersal+aont, because the question them becomes, "How do you secure that secret key?"  If the technique for securing the key is the same as the data, there is little practical benefit.  Of course this requires that the machines storing slices must be as secure and trusted as locations one would store shares of their key.  Nothing prevents one from using both an existing encryption system and then dispersal+aont, this will yield greater confidentiality but reduced reliability.

>
> Why would I take a nice, robust, well-understood algorithm like
> AES-256 and hobble it with my in-house dispersal algorithm?  Because
> key management is hard?  It _is_ hard, definitely, and I don't quite
> understand how TahoeLAFS approaches the problem (I guess it has to do
> with these 'caps' you guys keep talking about), but we shouldn't
> ignore the problem just because it's hard.
>

It's not just a question of technical or logistical difficulty of a key management system.  The bigger concern is _how_ exactly your key management system actually secures your keys.  Often it is stored in a single physical medium, and the loss of that one device storing the key means one loses all data that it was encrypted with.  Or, the theft or compromise of that one system means the attacker has access to all of your data.  As Zooko noted before, AONT utilizes AES in an unmodified way, the only difference is how the key is protected.  Dispersal+AONT doesn't ignore the problem of key management, rather it solves the key management problem by eliminating it (or more accurately collapsing it into the same problem of how the data is managed).

> As for Reason #1, that computers get faster and faster: pick a key
> size sufficiently large for you to retire well before your customers
> come calling with pitchforks and torches.

In the response #1 post, the problem is not only exponentially increasing computing power, but advances in mathematical theory and quantum computers which threaten the asymmetric algorithms which so many key management systems are dependent upon.  Such advances leading to breaks in RSA or ECC could come at any time, because it's never been proven that those problems have no efficient solutions.  Use of asymmetric algorithms in key management systems is very common because all the secret keys used by one person can be protected by a single asymmetric key.  Asymmetric algorithms are completely unnecessary when Dispersal+AONT are used, and therefore this approach offers greater time-resistance.

> As for Reason #3, that disclosure laws are a PITA: Any storage system
> based on distributing erasure-encoded slices is going to enjoy those
> benefits, right? I don't see how All-or-Nothing is a big win over a
> key-management infrastructure.

Without the AONT applied prior to dispersal, some slices, we call "data slices" would contain recognizable information from the original input data.  This could be avoided by computing all "code slices" which are slices produced by the erasure codes, but this is computationally expensive, and unnecessary when AONT is applied.

P.S.

Many of the questions you and Zooko raised were brought up by others in a previous discussion thread.  You might find then interesting:

http://groups.google.com/group/cloud-computing/browse_thread/thread/bd763d933d40394e/451f43e9eafee6da

However replies to that thread seemed to have stop appearing, so if you have comments regarding any of them you should post them to this mailing list.

Thanks,

Jason

>
> -Russ
>
> On Fri, Jul 24, 2009 at 6:33 AM, Zooko Wilcox-O'Hearn<zooko at zooko.com> wrote:
>> [cross-posted to tahoe-dev at allmydata.org and cryptography at metzdowd.com]
>>
>> Disclosure:  Cleversafe is to some degree a competitor of my Tahoe-
>> LAFS project.  On the other hand, I tend to feel positive towards
>> them because they open-source much of their work.  Our "Related
>> Projects" page has included a link to cleversafe for years now, I
>> briefly collaborated with some of them on a paper about erasure
>> coding last year, and I even spoke briefly with them about the idea
>> of becoming an employee of their company this year.  I am tempted to
>> ignore this idea that they are pushing about encryption being
>> overrated, because they are wrong and it is embarassing.  But I've
>> decided not to ignore it, because people who publicly spread this
>> kind of misinformation need to be publicly contradicted, lest they
>> confuse others.
>>
>> Cleversafe has posted a series of blog entries entitled "3 Reasons
>> Why Encryption is Overrated".
>>
>> http://dev.cleversafe.org/weblog/?p=63 # 3 Reasons Why Encryption is
>> Overrated
>> http://dev.cleversafe.org/weblog/?p=95 # Response Part 1: Future
>> Processing Power
>> http://dev.cleversafe.org/weblog/?p=111 # Response Part 2:
>> Complexities of Key Management
>> http://dev.cleversafe.org/weblog/?p=178 # Response Part 3: Disclosure
>> Laws
>>
>> It begins like this:
>>
>> """
>> When it comes to storage and security, discussions traditionally
>> center on encryption.  The reason encryption - or the use of a
>> complex algorithm to encode information - is accepted as a best
>> practice rests on the premise that while it's possible to crack
>> encrypted information, most malicious hackers don't have access to
>> the amount of computer processing power they would need to decrypt
>> information.
>>
>> But not so fast.  Let's take a look at three reasons why encryption
>> is overrated.
>> """
>>
>> Ugh.
>>
>> The first claim -- the today's encryption is vulnerable to tomorrow's
>> processing power -- is a common goof, which is easy to make by
>> conflating historical failures of cryptosystems due to having too
>> small of a crypto value with failures due to weak algorithms.
>> Examples of the former are DES, which failed because its 56-bit key
>> was small enough to fall to brute force, and the bizarre "40-bit
>> security" policies of the U.S. Federal Government in the 90's.  An
>> example of the latter is SHA1, whose hash output size is *not* small
>> enough to brute-force, but which is insecure because, as it turns
>> out, the SHA1 algorithm allows the generation of colliding inputs
>> much quicker than a brute force search would.
>>
>> Oh boy, I see that in the discussion following the article "Future
>> Processing Power", the author writes:
>>
>> """
>> I don't think symmetric ciphers such as AES-256 are under any threat
>> of being at risk to brute force attacks any time this century.
>> """
>>
>> What?  Then why is he spreading this Fear, Uncertainty, and Doubt?
>> Oh and then it gets *really* interesting: it turns out that
>> cleversafe uses AES-256 in an All-or-Nothing Transform as part of
>> their "Information Dispersal" algorithm.  Okay, I would like to
>> understand better the cryptographic effects of that (and in
>> particular, whether this means that the cleversafe architecture is
>> just as susceptible to AES-256 failing as an encryption scheme such
>> as is used in the Tahoe-LAFS architecture).
>>
>> But, it is time for me to stop reading about cryptography and get
>> ready to go to work.  :-)
>>
>> Regards
>>
>> Zooko
>> ---
>> Tahoe, the Least-Authority Filesystem -- http://allmydata.org
>> store your data: $10/month -- http://allmydata.com/?tracking=zsig
>> I am available for work -- http://zooko.com/résumé.html
>> _______________________________________________
>> tahoe-dev mailing list
>> tahoe-dev at allmydata.org
>> http://allmydata.org/cgi-bin/mailman/listinfo/tahoe-dev
>>
> _______________________________________________
> tahoe-dev mailing list
> tahoe-dev at allmydata.org
> http://allmydata.org/cgi-bin/mailman/listinfo/tahoe-dev