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 17 Jan 2010 15:14 Peter Fairbrother wrote: > Peter Fairbrother wrote: >> unruh wrote: >>> On 2010-01-17, Peter Fairbrother <zenadsl6186(a)zen.co.uk> wrote: >> [...] >>>> All I'm doing is showing is that in this theoretical and impractical >>>> but *follows-the-definitions-of-cascaded-ciphers* case the cascaded >>>> ciphers are weaker than the first cipher alone - which M+M said, >>>> incorrectly, was impossible. >>> >>> But the cascaded cypher is NOT weaker than the original alone, since >>> the >>> cascaded cypher is exactly exhaustive search >> >> >> ??? >> >> I don't know what you mean here. >> >> >> ( which always sets an >>> upper bound on the strength of a cypher). >>>> >>>> If you don't like the extreme example (although it is theoretically >>>> sound), suppose instead that the second cipher merely does some of >>>> the work of breaking the first cipher - I think I've shown that that >>>> is at least possible. >>>> >>>> The combo is then weaker than the first cipher alone. >>> >>> How are you defining "weaker"? >> >> Let's say a perfectly strong cipher cannot be broken by any method >> easier than brute force. >> >> Any attack which needs less than brute force weakens the cipher. >> >> I assume that the first cipher is perfectly strong. >> >> If the second cipher does some of the work of a brute-force attack, >> then the combo can be broken with less effort (on the part of the >> attacker) than a brute-force attack. > > Alternatively, let's say a cipher is weaker if it needs less work (for the attacker) > to > find the key in some situation, eg a chosen plaintext attack > > If the encryptor does some of that work for you, eg by doing the second > encryption, then that's less work which you have to do. > > If he inadvertently does some of that work - even a tiny bit - by > applying a second cipher, you are better off, and the combination is > weaker than the first single cipher alone, as you have less work to do. > > I think I've shown that that's possible. > > > The *only* thrust of this argument is as a proof, and it is a proof, > that the idea that a cipher cascade is at least as strong as the first > cipher is incorrect. > > > -- Peter Fairbrother
From: Tom St Denis on 17 Jan 2010 15:49 On Jan 17, 1:47 pm, unruh <un...(a)wormhole.physics.ubc.ca> wrote: > On 2010-01-17, Tom St Denis <t...(a)iahu.ca> wrote: > > > > > On Jan 16, 11:31?am, Phoenix <ribeiroa...(a)gmail.com> wrote: > >> Well, is encrypting twice much more secure? > > >> Yes or no? > > >> Alvo > > > Generally no. I've posted the logic to this answer already. > > Basically the argument works like this > > > Question: Is double-AES more secure than single AES? > > > Answer: No. Suppose, O(2^256) work is feasible [e.g. meaning that > > double-AES *is* more secure] than a MITM attack can break the double- > > AES with 2^256 space and 2^256 time. Suppose that 2^256 work/space is > > not possible, then double-AES is not more secure since you can't break > > single AES anyways. > > No, because breaking it requires 2^256 work, and 2^256 space. > Also, it may not require 2^256 time to break single AES. A way might be > found of require just 2^30 work to break single AES.(Noone believes that > 2^256 work will be possible in the next 50 years). But your MITM would > still require 2^256 work to break double AES ( searching or sorting the > database). Ie, double AES IS safer than broken single AES, at least with > this MITM attack, which is what > the doubling was supposed to guard against.. If there is some attack against full AES in 2^30 time there is probably one against double AES in around 2^60 time. So you're probably hosed either way. But in this future it's entirely possible something that ruthlessly breaks AES breaks double-AES to the point it's useless too. It's illogical to assume attacks will advance just far enough to promote your argument. Look at FEAL for instance. It kept getting broken. What if we said FEAL-8 should be infinitely better than FEAL-4 because it's twice as "hard." Reality has proven otherwise. FEAL-8 is practically no stronger than FEAL-4 at all despite having twice the rounds. Tom
From: Tom St Denis on 17 Jan 2010 15:53 On Jan 17, 3:03 pm, Phil Carmody <thefatphil_demun...(a)yahoo.co.uk> wrote: > Tom St Denis <t...(a)iahu.ca> writes: > > > > > On Jan 16, 11:31 am, Phoenix <ribeiroa...(a)gmail.com> wrote: > >> Well, is encrypting twice much more secure? > > >> Yes or no? > > >> Alvo > > > Generally no. I've posted the logic to this answer already. > > Basically the argument works like this > > > Question: Is double-AES more secure than single AES? > > > Answer: No. Suppose, O(2^256) work is feasible [e.g. meaning that > > double-AES *is* more secure] than a MITM attack can break the double- > > AES with 2^256 space and 2^256 time. Suppose that 2^256 work/space is > > not possible, then double-AES is not more secure since you can't break > > single AES anyways. > > Continuing the abuse of O notation, you're conflating > ~2^256 time ~1 space with ~2^256 time * ~2^256 space. > They're not the same. One can be performed in very little > space, for example. 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. Tom
From: Paul Rubin on 17 Jan 2010 16:14 Tom St Denis <tom(a)iahu.ca> writes: > Actually, there is a variant of RSA where N = p^2q and it's provably > reducible to factoring. It's weird in that encryption uses N as the > exponent.... I thought Rabin's method (e=2) was also equivalent to factoring.
From: unruh on 17 Jan 2010 16:21
On 2010-01-17, Tom St Denis <tom(a)iahu.ca> wrote: > On Jan 17, 1:47?pm, unruh <un...(a)wormhole.physics.ubc.ca> wrote: >> On 2010-01-17, Tom St Denis <t...(a)iahu.ca> wrote: >> >> >> >> > On Jan 16, 11:31?am, Phoenix <ribeiroa...(a)gmail.com> wrote: >> >> Well, is encrypting twice much more secure? >> >> >> Yes or no? >> >> >> Alvo >> >> > Generally no. ?I've posted the logic to this answer already. >> > Basically the argument works like this >> >> > Question: ?Is double-AES more secure than single AES? >> >> > Answer: ?No. ?Suppose, O(2^256) work is feasible [e.g. meaning that >> > double-AES *is* more secure] than a MITM attack can break the double- >> > AES with 2^256 space and 2^256 time. ?Suppose that 2^256 work/space is >> > not possible, then double-AES is not more secure since you can't break >> > single AES anyways. >> >> No, because breaking it requires 2^256 work, and 2^256 space. >> Also, it may not require 2^256 time to break single AES. A way might be >> found of require just 2^30 work to break single AES.(Noone believes that >> 2^256 work will be possible in the next 50 years). ?But your MITM would >> still require 2^256 work to break double AES ( searching or sorting the >> database). Ie, double AES IS safer than broken single AES, at least with >> this MITM attack, ?which is what >> the doubling was supposed to guard against.. > > If there is some attack against full AES in 2^30 time there is > probably one against double AES in around 2^60 time. So you're > probably hosed either way. That may be, but it is NOT this MITM attack. The claim was that MITM made double AES weak, at least as weak as single AES, because of the MITM attack. I was simply pointing out that this is false, because the MITM requires 2^256 space, and 2^256 time to search or sort the database. It is possible that a break for single AES would also break double double AES but it would probably also break triple AES as well by the same argument. > > But in this future it's entirely possible something that ruthlessly > breaks AES breaks double-AES to the point it's useless too. It's > illogical to assume attacks will advance just far enough to promote > your argument. Look at FEAL for instance. It kept getting broken. > What if we said FEAL-8 should be infinitely better than FEAL-4 because > it's twice as "hard." Reality has proven otherwise. FEAL-8 is > practically no stronger than FEAL-4 at all despite having twice the > rounds. > > Tom |