Is encrypting twice much more secure?
in [Cryptography]
|
Prev: A published list of rare tetragraphs?
Next: A discrepancy in literatures on permutation polynomials
From: Peter Fairbrother on 25 Jan 2010 17:48 Paul Rubin wrote: > Peter Fairbrother <zenadsl6186(a)zen.co.uk> writes: >> Let me rephrase - can anyone remember the formula for calculating the >> Shannon entropy of a "random" permutation? > > Basically you use Stirling's approximation of n! for that: > > n! (approx) = (n/e)^n sqrt(2 pi n) > > So log2 (n!) (approx) = n log2 (n/e) + 0.5 log2 (2 pi n) > > That is equal to the Shannon entropy of the uniform probability > distribution on the space of permutations on n objects, which I > think is what you are asking. Thanks, I hadn't thought of doing it that way - I've been approaching it from two different angles, which give sightly different results. Some heavy math ahead, methinks! Will let you know any interesting results. -- Peter Fairbrother
From: Simon Johnson on 26 Jan 2010 04:36 > Well since you can't perform or store either 2^256 time nor space it's > largely academic. My point was if you assume that you can't store > 2^256 data [or even compute that] then double-AES isn't actually more > secure. There's this folk law that states that ciphers degrade in quality over time, therefore you need more rounds or more key space to resist these future attacks. However, this isn't really true. Consider DESX. The underlying DES transform was published in the middle of the 70s and DES itself was only broken because of its short key size. DESX is still secure today. The only reasons we moved to AES, rather than adopting DESX as the improved standard, was that it was slow and that a 64-bit block is not enough in an era where you can easily encrypt a terrabyte of data under counter mode. DESX would still be a sensible choice of cipher for encrypting your SSL traffic, even today. Cheers, Simon
From: Tom St Denis on 26 Jan 2010 08:47 On Jan 26, 4:36 am, Simon Johnson <simon.john...(a)gmail.com> wrote: > > Well since you can't perform or store either 2^256 time nor space it's > > largely academic. My point was if you assume that you can't store > > 2^256 data [or even compute that] then double-AES isn't actually more > > secure. > > There's this folk law that states that ciphers degrade in quality over > time, therefore you need more rounds or more key space to resist these > future attacks. > > However, this isn't really true. Consider DESX. The underlying DES > transform was published in the middle of the 70s and DES itself was > only broken because of its short key size. DESX is still secure today. > > The only reasons we moved to AES, rather than adopting DESX as the > improved standard, was that it was slow and that a 64-bit block is not > enough in an era where you can easily encrypt a terrabyte of data > under counter mode. > > DESX would still be a sensible choice of cipher for encrypting your > SSL traffic, even today. It's been shown that DES with a new key schedule would also resist DC and LC much more effectively. Re-using key bits is part of why the attacks work so well at establishing key bits from the signal [that is sampled LC and DC queries]. IIRC the official reason for the AES contest was that triple-DES was too slow [and 64-bit too small], not single DES. DESX runs in basically the same time as DES since all the difference is is an additional XOR of key material. I disagree with the notion that "ciphers degrade over time so 3-cipher is better" since there are counterproofs to that argument in history. Look at FEAL. It was originally proposed with all seriousness to have 4 rounds. It was later shown to be vulnerable up to [iirc] 31 rounds. 3 * 4 is 12. Therefore "triple-FEAL" isn't actually any usefully more secure than single FEAL. There has largely been a tapering off of cryptanalysis published reports [from what I can tell] with focus being shifted to related key attacks and forced collision attacks on PRFs and hashes. I think ciphers have been resisting cryptanalysis better now than say in the 80s and early 90s because there has been a large focus on ensuring provable qualities [like branch]. In the 80s and 90s most designs reached for notions like SAC with complicated permutations which ultimately were not sufficient. Key schedules have long been ignored [hence the related key attacks] since most designs look to preserve entropy [AES for example is fairly simple] with minimal computational effort. PRFs [like hashes] aren't much different. With the exception of Whirlpool no modern hash has ANY proof of branch, nor efficacy (possible exception being VSH but who uses a public key hash anyways??? hehehehe). Heck the SHA-2 series were designed after wide input UFNs even after such structures were known to be vulnerable to DC. I would not be surprised to see SHA-2 hashes being eroded over the next 10 years. Probably not to the point where they're useless, but to the point where there are academic inklings that they're not exactly what is promised. Much like SHA-1 today. Even if the Qualcomm results hold true, 2^52 work is too much work for most people to attempt, and whether that can turn into a pre-image attack is another story altogether (much like the results on MD5). Tom
From: Thomas Pornin on 26 Jan 2010 09:35 According to Tom St Denis <tom(a)iahu.ca>: > IIRC the official reason for the AES contest was that triple-DES was > too slow [and 64-bit too small], not single DES. Speed was a secondary issue; the main "official" problem was the 64-bit block size. The contest rules included a clause that the candidates shall be "as fast as 3DES, or faster, at least for 128-bit keys". The NIST was quite pleasantly surprised that most of the candidates were substantially faster than 3DES, but this was not an absolute requirement. One of the candidates was DEAL, which, when used with a 128-bit key, mostly consisted in a 6-round Feistel network with DES as the inner confusion function. This yielded the same performance than 3DES (6 DES invocations for a 128-bit block). > DESX runs in basically the same time as DES since all the difference > is is an additional XOR of key material. There is a result somewhere (I think it was published in Eurocrypt some time between 1999 and 2001) which shows that "academic strength" of FooX, for whatever block cipher 'Foo', is not as high as expected. I.e., for a n-bit block cipher, then the 'X' part adds only about n/2 bits of security. This is "academic strength", i.e. we are not talking about a simple 2^(n/2) time factor with no increase in memory requirements or plaintext/ciphertext pairs; but academic strength is what the NIST uses to state that 3DES offers 112 bits of security, not 168 bits. According to that result, DESX has 56+32 = 88 bits of security, which is still a bit too high to be in the realm of the economically feasible, but still not high enough for comfort. > I would not be surprised to see SHA-2 hashes being eroded over the > next 10 years. Probably not to the point where they're useless, but > to the point where there are academic inklings that they're not > exactly what is promised. It can be expected that the SHA-3 contest will act similarly to the AES contest. The pre-contest designs (SHA-2 / 3DES) will gradually lose popularity, perceived strength, or both, and the new designs will be there to last. Bets are open on what subjects will the symmetric-cryptologists massively investigate when the SHA-3 competition closes. --Thomas Pornin
From: Tom St Denis on 26 Jan 2010 10:18
On Jan 26, 9:35 am, Thomas Pornin <por...(a)bolet.org> wrote: > According to Tom St Denis <t...(a)iahu.ca>: > > > IIRC the official reason for the AES contest was that triple-DES was > > too slow [and 64-bit too small], not single DES. > > Speed was a secondary issue; the main "official" problem was the 64-bit > block size. The contest rules included a clause that the candidates > shall be "as fast as 3DES, or faster, at least for 128-bit keys". The > NIST was quite pleasantly surprised that most of the candidates were > substantially faster than 3DES, but this was not an absolute > requirement. > > One of the candidates was DEAL, which, when used with a 128-bit key, > mostly consisted in a 6-round Feistel network with DES as the inner > confusion function. This yielded the same performance than 3DES (6 DES > invocations for a 128-bit block). Stand corrected. Though I don't see how DEAL stood a realistic chance, it was an academic proposal at best. > There is a result somewhere (I think it was published in Eurocrypt some > time between 1999 and 2001) which shows that "academic strength" of > FooX, for whatever block cipher 'Foo', is not as high as expected. I.e., > for a n-bit block cipher, then the 'X' part adds only about n/2 bits of > security. This is "academic strength", i.e. we are not talking about a > simple 2^(n/2) time factor with no increase in memory requirements or > plaintext/ciphertext pairs; but academic strength is what the NIST uses > to state that 3DES offers 112 bits of security, not 168 bits. I think a standard MITM applies does it not? > According to that result, DESX has 56+32 = 88 bits of security, which is > still a bit too high to be in the realm of the economically feasible, > but still not high enough for comfort. I don't know about you but I don't see 2^88 effort of even simply incrementing an 88-bit counter being feasible in the near future. The fastest AES runs in around 12 cycles per byte [192 cycles per block] on a Core 2 Duo processor. To achieve 2^88 clockings would require 2^95 machine cycles. Even if you had a billion processors running each running at 3GHz it'd still take 2^34 years to complete. Even with a dedicated ASIC you're still in the realm of 2^30+ years. The truth of the matter is 80-bit symmetric keys are plenty secure today. 128-bit was chosen as a minimum because of paranoid fears, it's a round power of 2, and generally bits are cheap. > It can be expected that the SHA-3 contest will act similarly to the AES > contest. The pre-contest designs (SHA-2 / 3DES) will gradually lose > popularity, perceived strength, or both, and the new designs will be > there to last. Sadly, there isn't a lot of theory in the SHA-3 designs. Tom |