[8382] in cryptography@c2.net mail archive
Re: Cryptographic Algorithm Metrics
daemon@ATHENA.MIT.EDU (Paul Crowley)
Thu Jan 4 09:17:02 2001
To: Peter Fairbrother <peter.fairbrother@ntlworld.com>
Cc: Greg Rose <ggr@qualcomm.com>, John Young <jya@pipeline.com>,
<cryptography@c2.net>
From: Paul Crowley <paul@cluefactory.org.uk>
Date: 04 Jan 2001 11:59:37 +0000
In-Reply-To: Paul Crowley's message of "04 Jan 2001 01:23:30 +0000"
Message-ID: <87pui3ttna.fsf@hedonism.subnet.hedonism.cluefactory.org.uk>
Paul Crowley <paul@cluefactory.org.uk> writes:
> Peter Fairbrother <peter.fairbrother@ntlworld.com> writes:
> > Not so. Perfect compression with encryption works too.
>
> Er, does it? I get a 1k message from you, perfectly compressed and
> then encrypted with some strong algorithm and a 128-bit key. As a
> godlike being unhindered by constraints of computational power, I try
> all 2^128 possible keys, and find due to the perfect compression that
> each of the 2^128 plaintexts is equally likely. From an information
> theoretic point of view, I'm much better off than I was before: I used
> to be missing 8192 bits of entropy, but now I'm only missing 128 - the
> space of possible messages has been vastly reduced. Put it this way,
> if all I want to know is whether you're asking for a ticket to the
> dance, I might well learn the answer since I might find that none of
> the candidate messages include that request.
There's a much easier way to make the point I'm reaching for here: how
long does the encryption have to be before perfect compression with
encryption works? Will 1 bit do? 1 bit is enough that you can't
uniquely identify the correct plaintext, but that's not necessarily a
problem for the attacker.
The problem with my original example is that "perfect compression"
gets very counterintuitive: it has to be perfect WRT the model of
message likelihood that the *attacker* has. So if, on seeing that
your message is 1k long, I still think there's a reasonable chance
you're going to the dance, it's therefore overwhelmingly likely that
I'll find a candidate message that says you are when I get to
decryption.
--
__
\/ o\ paul@cluefactory.org.uk
/\__/ http://www.cluefactory.org.uk/paul/
