Re: Encryption key longer than text to encrypt

laura fairhead wrote:
On 3 Jan 2007 09:49:14 -0800, "=?iso-8859-1?q?Jean-Fran=E7ois_Michaud?=" <cometaj@xxxxxxxxxxx> wrote:

laura fairhead wrote:
On Wed, 03 Jan 2007 16:44:30 +0000, rossum <rossum48@xxxxxxxxxxxx> wrote:

On 3 Jan 2007 06:41:46 -0800, "Jean-Fran=E7ois Michaud"
<cometaj@xxxxxxxxxxx> wrote:

Since it is easier in practice to use pseudo random data than to
generate random data which is then distributed as appropriate if we
have OTP in mind, would
encrypting messages =E0 la OTP with 'pseudo random data' using a key
greater than the message make any sense to increase security,

No. The reason that an OTP is provably secure is that the keystream
is truly random. As soon as you substitute a pseudo-random keystream
the security proof fails. You no longer have an OTP, you have a
stream cypher instead.


Hello Laura,

I always wonder about this "provably secure". I don't remember seeing
a convincing proof of security for OTP, does anyone have any references?

I believe you're looking for Shannon's proof of security. There's some
information here about it.


Thankyou, I found a copy of his 1949 work and busy reading.

Glad it helped a bit ;-).

For example, a true random number generator could on one particular run
generate a sequence entirely of zeros. Examining the data would then
reveal the original cleartext. Yes it's extremely unlikely to happen
in practise I know (in practise it's probably much more unlikely to happen
than it should even in theory). But it's because of the chance of that
and then a whole series of progressively weaker cases that I would be
inclined to think OTP really isn't 100% secure ...

It's an interresting angle, but the idea behind true random generation
is that given a keyspace, each key has an equal probability of being
generated and as thus, attacks based on trying to find patterns between
captured ciphers is impossible. Even a stream of all 0s would, in such
a context, yield a strong encryption since one can't expect for an all
0 stream key to have a stronger probability of being generated than a
key of all 1s. There's a non zero probability that any plaintext will
look like any other plaintext of similar size given a proper key.

Yes this is true, it wouldn't work by itself because "you don't know"....

Right. Basically, the idea only works because all keys are
equiprobable. If attackers could expect a key of all 0s to surface more
often than not, then there would be a stronger probability that
encrypted text looking like a message would be the actual plaintext
message encrypted with an all 0s key, but since all keys are
equiprobable, any plaintext message that you can think of can actually
accidentally get encrypted to any other possible message of the same
lenght if the key is "just right". This is why an attacker can't
assume, if it so happens to "look" like plaintext, that what he's
reading is the right message and that the key is all 0's any more than
he can assume that he's reading a distorted message that somehow looks
coherent but was in fact a combination of plaintext and a very
particular key that yielded the "wrong message" (although he can
certainly expect that the latter is more probable by a very large

I mean I did read a proof about this some time ago probably and I think
I really already understood this idea, maybe I was going a little astray here
with that example, cheers for you and others to point this out; but what
drives me is a bit deeper than this, so I'm still not satisfied <g>

For example; if you use sampled conversation as the OTP then someone could wade
through looking for patches where the sound had faded (all zeros) of course they
know something about the original message.

Well yes this is "far off" from a random device but how random do you need to be to
eliminate the attack vector to zero?

The attack weans out the closer you get to perfectly random data as
generated by hardware random number generators. All random data
generated by software only, no matter how complex, are always perfectly
deterministic, and as such, predictable in some fashion. Data is only
truely random if no underlying pattern can be uncovered. As algorithms
tend towards and indefinite complexity, true random data can be assumed
to a certain extent because the underlying patterns might be too
complex to extract easily. Interrestingly enough, this might actually
be what is happening with true random data generated by hardware RNGs,
as opposed to the view that the data is generated

What I was looking for/expecting in a proof was
something showing a "snowball" effect at some threshold where the attack vector
goes from significant to insignificant. Just saying OTP with "true" random number
= 100 % secrecy has never convinced me and it still doesn't.

I'm not familiar with the proof myself, but the idea exposed in this
post make enough sense to me that I don't require for a mathematical
proof to understand how it can be perfectly secure.

Anyway thanks again for pointing me to Shanon,

You are most welcome :).

I've read a little before from him
but I read his bio this time and seems like quite an interesting character :)

Indeed, his contribution was very important in many areas. It can also
be seen in the audio world, where the Nyquist-Shannon sampling theorem
is commonly used in the reconstruction of analog signal from digital
data. Whenever you listen to music through electrodynamic drivers (most
headphones/speakers), and a DA conversion takes place, going from data
inscribed on your CDs to an analog signal going through the drivers,
Shannon's work is used {;-).

Jean-Francois Michaud