Re: Is encrypting twice much more secure?

Mok-Kong 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.

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 proof-by-example 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

Relevant Pages

  • Re: Is encrypting twice much more secure?
    ... encryption with statistically independent keys is at least as secure as ... so if one pass is secure enough you're okay. ... imply that the 2nd cipher couldn't weaken the work of the ... Now imagine the second cipher has only one possible key (or two, if you don't like the idea of a cipher with only one key, but they are both very similar permutations) which is a permutation the reverse of the list above. ...
  • Re: =?windows-1252?Q?The_Renaissance_is_Here_=96_SD_cryptography=2E?=
    ... cipher in itself. ... alphabet later to create keys ad hoc, ... All modern cryptography depends on going public with the vitally ... Even RSA and other public-key algorithms do not ...
  • Re: Initializing GFSR Generators.
    ... It is important to see the system around "the cipher" ... I innovated an "alias file" to hold the actual keys, ... somebody has to get through a combiner ...
  • Re: Im still amused.
    ... keys with certain algorithms. ... independent operation to the encryption algorithm that will use it. ... cipher whenever you wish to call it. ... Reference: "Theoretically Unbrakable Cryptography" ...
  • Re: Im still amused.
    ... keys with certain algorithms. ... true permutations but the function will use any entry in a way to ... an adequate key for another algorithm. ... theoretically unbreakable cipher - no doubt about this. ...