Is encrypting twice much more secure?
in [Cryptography]
|
Prev: A published list of rare tetragraphs?
Next: A discrepancy in literatures on permutation polynomials
From: unruh on 17 Jan 2010 13:38 On 2010-01-17, Ilmari Karonen <usenet2(a)vyznev.invalid> wrote: > On 2010-01-17, Peter Fairbrother <zenadsl6186(a)zen.co.uk> wrote: >> >> Hmm, maybe someone breaks key sharing in the next 50 years - quantum >> computers could do that, mostly it's public key type stuff. >> >> Though iirc there are some known-work techniques which QC won't break - >> but it's not my field. > > There are several well known information-theoretically secure secret > sharing schemes. A trivial one, for sharing a key among N persons, is > to encrypt it with N-1 independent one time pads, give the result to > the first person and one of the pads to each of the remaining N-1. Of course the chance that the lawyers will have lost, misplaced, corrupted those keys by the time he dies is probably far far greater than the chance that say AES will be broken cheaply enough to make it worthwhile breaking his source code. > > Shamir's secret sharing scheme, based on polynomials over a finite > field, is a slightly more elaborate solution which can allow the key > to be recoverably by any K out of the N persons, for some 1 < K <= N, > and is also information-theoretically secure. > So it just means the attacker has to bribe K people.
From: unruh on 17 Jan 2010 13:47 On 2010-01-17, Tom St Denis <tom(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.. > > Tom
From: Peter Fairbrother on 17 Jan 2010 14:51 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. (btw, this leads us to ... more, but I'm not ready to post it here yet, it's still incomplete research results - as is the proof above, afaik it's not yet in the literature) -- Peter Fairbrother
From: Phil Carmody on 17 Jan 2010 15:03 Tom St Denis <tom(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. -- Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
From: Peter Fairbrother on 17 Jan 2010 15:10
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 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 |