Re: Can we obtain securer data encryption if we encrypt the data once more?

From: Ernst Lippe (ernstl-at-planet-dot-nl_at_ignore.this)
Date: 06/23/03 

Date: Mon, 23 Jun 2003 13:50:55 +0200

On Mon, 23 Jun 2003 10:36:14 +0000, Mark Wooding wrote:

> Richard Heathfield <invalid@address.co.uk.invalid> wrote:
>
>> > For if it does, an adversary faced with one of the two schemes can
>> > simply make up a key for the other one and pretend to himself that
>> > he's attacking the composition. Hence, the composition is at least
>> > as strong as the stronger scheme.
>>
>> Or there is mileage in this adversary's scheme.
>
> But that implies that, in fact, /both/ of the encryption schemes was
> weak, contrary to hypothesis. Hence the theorem is proved...
>
>> I'm not saying it isn't a daft idea. I'm just saying I don't recall
>> anyone mentioning a proof to support what I think even the most
>> amateurish amongst us (i.e. me) can intuitively understand to be true.
>
> Ah. That was indeed an attempt at just such a proof. I was going to
> embark on one of my usual incomprehensible articles filled with $(t, q,
> \epsilon)$-secure partridges in peartrees, but took them out.
>
> Just to keep the TeXnician in me happy, I'll write $E$ for the first
> encryption scheme, and $E'$ for the second; the composed scheme is then
> $E \o E'$ (where $\o$ is a little raised-`o' function composition sign).
>
> I'm going to try to prove that, if at least one of $E$ and $E'$ is
> secure, then the composition $E \o E'$ is secure. (Exactly what
> `secure' means is something I'm going to gloss over -- the proof works
> for a number of different definitions of `secure' and `composition', so
> you can slot your own in later...[1])

Essentially what you are trying to prove is what Maurer and Massey
called the Folk Theorem. Somewhat surprisingly perhaps, they
proved that is was false. Their article, "Cascade Ciphers: The
importance of being first" that you can find at
http://www.crypto.ethz.ch/pubs/MauMas93a contains a nice counter
example.

Also you forgot to require that the keys must be independent.
Without that condition you could select encryption with a certain
key as the first cipher and the corresponding decryption with the
same key as the second cipher. Each of these is secure when used
in isolation but when they are composed the end-result obviously
is not.

greetings,

Ernst Lippe

Relevant Pages

  • Re: FOOL OR FASCIST? Andy Burnham, Under Secretary of State, Home Office, London SW1
    ... while private organisations will be able to conduct verification checks ... I am reminded of a new scheme adopted at the local primary ... As I had with the previous child been persuaded against my ... teacher kept asking, kept saying she couldn't complete the forms, was ...
    (uk.politics.misc)
  • Re: who needs scheme when you have happs?
    ... I am saying that your application is likely to be well ... within the constraints required for HAppS to make sense for it. ... Well, PHP, Ruby, Python, and Perl have all gotten their fame from web ... I just find it odd to make the barb in a Scheme forum, ...
    (comp.lang.scheme)
  • Re: OT: Happy Plumber
    ... I remember Veggie Dave ... saying something like: ... I've seen some dreadful cowboy work, ... If such a scheme goes ahead, I can see a direct parallel to Pt P ...
    (uk.rec.motorcycles)
  • Re: [Full-disclosure] Most common keystroke loggers?
    ... shows the new alignment of characters,such as saying a=c, d=3, b=z, etc. so instead of typing foobar the password they would type in for that session would be hnnzck. ... My main point is that if your computer is fully compromised and the attacker can adapt, there's no scheme you can up by adding just software to the existing client computers that will help. ...
    (Full-Disclosure)
  • Re: Countering chosen-plaintext attacks
    ... > plaintext fed to the encryption scheme. ... Build a stateful encryption ... > scheme using a block cipher and a mode of operation. ...
    (sci.crypt)