how to tell if decryption was successfull?

[Jerrold Leichter]

| [newbie here]
| 
| I was wondering how can one tell if some data was successfully decrypted.
| Isn't there an assumption going on about what the cleartext data should be?
| Text? Image? ZIP file? Ziped jpeg? Another cyphertext? rot-13?
Without some additional information, there's no way to tell anything!  Take
the limit case:  I generate a Megabyte of random bits, encrypt them, and
send them to you.  You decrypt what you receive and see - a million random 
bits.  Are they the *right* random bits?  How could you possibly know?  Any 
key at all gives you - a million random bits.

The only way to know you decrypted correctly is to have some way to recognize 
a correct decryption.  Any bunch of *random* bits looks like any other - 
there's no possible way to tell.  What you need is a *non*-random set of bits.
If I sent you English text and what arrived looked like English text, you
can recognize that - exactly because English text is non-random at many
different levels.  The 8-bit bytes, if it's standard ASCII, all have the top
bit set to 0.  For 100 random bytes, the chance that all the top bits are 0 is 
1 in 2^100 - already a pretty good test!  Beyond that, most of the characters
are going to be lower-case letters.  Certain control characters won't appear 
at all.  There will be statistical properties - e much more common than j.
And, of course, the letters will form words, which fit together into 
meaningful sentences, etc.

The way this is usually described is that English text has tons of redundant
information.  If you see a q, you can pretty much guess that u follows.  If
you see th, you can be very certain that a vowel, a space, or a punctuation
mark follows.  Etc.

The same kind of redundancy - predictability - appears in other file formats.
If you expect rot-13, rot-13 it and check for English.  If it's a ZIP'ed
file, check for the ZIP header and directory.  Etc.

In practice, if this is of concern, you *add* redundancy.  For example, you do
a checksum and append it to the message before encrypting.  Decent 
cryptosystems - anything worth consideration today - will, with the wrong key, 
produce something effectively indistiguishable from random bits.  So you can
model what you can expect from, say, a 64-bit checksum as:  What's the chance
that it will match just by pure chance?  Answer:  1 in 2^64.

Note that I'm specifically dealing only with how you know you decrypted with 
the right key.  Looking for inherent redundancy, and even a typical checksum, 
does *not* provide a solid indication of authenticity:  There are deliberate 
attacks that can, for example, change a message "under" the encryption but
leave the checksum intact.  There are more sophisticated techniques that
protect against such things as well.  In practice, "solid" systems use those -
and as a side-effect, end up detecting things like using the wrong key "for 
free".
							-- Jerry


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com