Re: Is encrypting twice much more secure?
 From: Peter Fairbrother <zenadsl6186@xxxxxxxxx>
 Date: Fri, 15 Jan 2010 14:14:54 +0000
MokKong Shen wrote:
Peter Fairbrother wrote:
I don't know about screwing up the implementation, which could do
horrible things  but yes, there is established theory that multiple
encryption with statistically independent keys is at least as secure as
the first encryption, see:
M. Maurer and J. L. Massey, Cascade ciphers: The importance of being
first, Journal of Cryptology, vol. 6, no. 1, pp. 55–61, 1993.
www.isiweb.ee.ethz.ch/archive/massey_pub/pdf/BI434.pdf
so if one pass is secure enough you're okay.
(I have a tiny doubt about their result, which I've been working on for
some years now  but in practice it won't mean much even if it pans out)
Wouldn't an 'definition' of 'statistically independent keys' (not very
simple to verify absolutely in practice, I surmise) by itself
('logically') imply that the 2nd cipher couldn't weaken the work of the
1st cipher? (For in the other case one could say then that the keys
aren't 'independent' after all.)
When your work bears fruit, please let us know as soon as possible, for
that would be very interesting and valuable.
I don't think that's going to be for some time if ever, and it probably won't be very valuable (although it might be interesting), but here's a rough outline of my thoughts ... my doubts are more intuitive than clearly expressible, and originally based only on a nebulous doubt of the proofbyexample in the paper mentioned ...
.... if anyone wants to finish it feel free, but credit me in the paper please! ...
.... and this is probably going to get long, and I'll be including some beginner's stuff. And I'm only looking at block ciphers here, not stream ciphers.
Consider a block cipher as a set of permutations of plaintext into ciphertext.
[ In simple terms, we could write the possible plaintexts out in numerical order, then write out the corresponding ciphertexts in order  that ordered list is a permutation, and there is a different permutation for each key. ]
If there are B different possible plaintexts in a block, there are B! (B factorial) possible permutations. If there are K possible keys then there are K actual permutations.
The cipher, in effect, chooses one the possible permutations, and assigns one to each key. For a "secure" cipher, one usual requirement is that these choices and assignations "look" random for all purposes.
So far, so normal.
[ There is another requirement for a cipher  in order to be able to uniquely decrypt, the cipher cannot assign the same permutation to two different keys.
[]> Therefore it is impossible to have a truly random choice over the entire set of possible permutations.
This also implies that B! must be greater than K  not usually a problem, for the average block cipher B! is very very much larger than K.
Later we'll consider a case where B! is about equal to K. This doesn't happen with today's real block ciphers, which is why it isn't likely to be a valuable result in practice (although it isn't a result at all, as yet). ]
First, let's go back a bit  for a secure cipher the choices of permutations should look random for all purposes.
But for any real cipher the choices are fixed by the cipher itself, in the sense that they don't change  and there are patterns in them even if they are truly chosen at random.
In any finite fixed set of random numbers there are patterns of some kind, if you look for them.
[]> It is therefore impossible to create a real cipher where the permutations look random for all purposes  in some sense patterns can be detected in them.
Incidentally, this is why rainbow tables can be used to break most (all?) ciphers, although in practice they may often need more resources than brute force.
On to cascaded ciphers. The second cipher also has patterns in it, and these can interact with the patterns of the first cipher.
Usually, for real ciphers, this isn't a problem, in the sense that it takes more resources than brute force to break them, and it's usually possible to prove that an attack based on this kind of interaction is statistically overwhelmingly likely to take more resources than brute force on the first cipher, when the keys are independently chosen.
But for cases where B! is about equal to K in both ciphers, I *think* birthday problems negate that statistical proof. I haven't worked out the details though, and I may very well be wrong.
 Peter Fairbrother
.
 FollowUps:
 Re: Is encrypting twice much more secure?
 From: Peter Fairbrother
 Re: Is encrypting twice much more secure?
 References:
 Is encrypting twice much more secure?
 From: Michael B Allen
 Re: Is encrypting twice much more secure?
 From: Sebastian Garth
 Re: Is encrypting twice much more secure?
 From: Michael B Allen
 Re: Is encrypting twice much more secure?
 From: unruh
 Re: Is encrypting twice much more secure?
 From: Michael B Allen
 Re: Is encrypting twice much more secure?
 From: unruh
 Re: Is encrypting twice much more secure?
 From: Michael B Allen
 Re: Is encrypting twice much more secure?
 From: Peter Fairbrother
 Re: Is encrypting twice much more secure?
 From: MokKong Shen
 Is encrypting twice much more secure?
 Prev by Date: Re: RC4 x 2 rounds
 Next by Date: Re: Is encrypting twice much more secure?
 Previous by thread: Re: Is encrypting twice much more secure?
 Next by thread: Re: Is encrypting twice much more secure?
 Index(es):
Relevant Pages
