Re: Use of Pseudo Random Generators for One Time Pad?

From: Peter Fairbrother (zenadsl6186_at_zen.co.uk)
Date: 03/08/04 

Date: Mon, 08 Mar 2004 00:46:15 +0000

Gregory G Rose wrote:

> In article <Y9adnSB2brlY7tbd4p2dnA@comcast.com>,
> Douglas A. Gwyn <DAGwyn@null.net> wrote:
>> RPK wrote:
>>> I want to know that considering PGP's high-quality Pseudo Random
>>> Generator, can it be used to create One Time Pad.
>>
>> Yes, it can, but the resulting OTP will not have ideal
>> security.
>
> Doug, I strongly disagree with your (and the
> original poster's) terminology. PGP's PRNG does
> not generate truly random numbers, so the output
> does not qualify for use in a One-Time Pad. What
> RPK proposes is a stream cipher, nothing more, and
> nothing less. Let's get away from the snake-oil
> terminology of "Pseudo-OTPs" and "Yes, it's an OTP
> but without ideal security".

I was thinking about this.

"One-time-pad" might be used to refer to the process of encryption by xoring
or mod26letteraddition or whatever a plaintext with a large file. It's a
pad, and you use it once. That's a definition.

It's the same operation as encrypting with a stream cipher, ignoring the
stream generator part. If the pad is deterministic and not random, then we
only need to send the keying material that generates the pad, and as people
have pointed out that's effectively a stream cipher. There is no need to
send the whole pad, and it's wasteful.

But suppose one party didn't have a computer, but only had a printed silk
handkerchief, it might make sense to use pseudo-random pad data rather than
keying material. I can think of other benefits of such a system - suppose
the guy with the computer and the prng has a thousand correspondents and
doesn't want to store the random keying material needed to service them, but
only some human-memorable keying material. Other possible benefits will
ocurr to you.

Of course a pad like that does not have the theoretical unbreakability of a
true random otp. We associate the words "otp" with that proof of
unbreakability, and for that the pad must be random. The needed properties
are both single use and randomness.

But that's not what the name says.

Several systems, like the one above, can be secure if used once, and not
otherwise. There is the straight stream ciphering operation, and the
non-random but practically irreproducible pad, and the "true otp". There may
be a few others, but let's leave it at that.

So why should the term otp be used only for a real random pad? The stream
cipher operation can be renamed - stream enciphering would do - and that's
not a problem, but the non-random pad does have it's uses - it's just not
"forever secure"*. It is a pad, and you have to only use it once.

Historically the phrase has been used to mean - well, that's not actually
clear to me. I was surprised when I looked. It has often been used to mean
only a random otp, but it has been abused so often that perhaps we should
call that an otr or OTR, for one-time-randomness.

I don't much like it. It goes agin' my grain. But I think it's probably what
we ought to do. It specifies the two main properties needed for perpetual
security, single use and randomness. That's important. We are in the
security business after all, and we abuse natural language a lot. Let's make
it easy and clear, and at least try and prevent ordinary people getting
conned.

So as of NOW, anything called an otp or OTP is not "forever secure".

An otr, or OTR, or one-time-randomness still is. :)

What a great idea ... like metrication - more like, what a terrible idea.
Thing is, randomness is kinda hard, and there may not be such a thing as an
otr anyway. Ooops.

BTW, does anyone know what the US military call an otr? They very
occasionally have some gonzo acromyns. GI.

Yikes! I started this intending to take the opposite viewpoint, OTP is a
real random otp and nothing else and darn those who think otherwise! But I
couldn't entirely blame them. Of course, they are not _cryptographers_, but
I often try and avoid that too. 

-- 
Peter Fairbrother
*BTW, if you are not a crypto theory guy, there are lots of things that make
me use "forever secure" in quotes. I'm being kind and nice to you. It's not
as straightforwardly forever secure as it seems - or actually it is, but
people think that means things it doesn't. We can still do horrible things
to you if you think it means those things. Usually, people do. Find out.
We use words, or some words, to mean very specific things, and unless you
know what we mean you might assume we mean something else. And sometimes we
disagree, or use the same words to mean different very specific things, or
different things in different situations, or just use the wrong words
because it's hard to keep that precision, especially in a NG posting, and
then we get emails like this one discussing precisely what a word of phrase
means, or should be used to mean. I digress.

Relevant Pages

  • Re: What is a "perfect secret" ?
    ... Hi, this is an example of OTP, one important condition for this cypher ... many ways and, yes, doesn't give perfect security even if it is as ... you will need some external check and autentication tools, or the pad ...
    (sci.crypt)
  • Re: Vigenere style One time pad?
    ... Look up the exact definition of a One Time Pad. ... Look up a working method of using OTP and stick to it. ... Reuse of the pad allows the code breaker to change the encryption used ... m1 XOR k ...
    (sci.crypt)
  • Re: research into modern computer-based one-time pad implementations?
    ... > Alan Tu wrote: ... I'm researching possible techniques for using OTP to ... the key in q at offset q' to encrypt p using ... so the next pad p will be a mystery... ...
    (sci.crypt)
  • Re: OTPs [was: Re: Help: Randomizing a List of Numbers]
    ... 1) how is anyone going to delete a 4k OTP from the CD once it's ... Remember that OTP stands for "one time pad", ... I myself don't know much about Swiss banks or embassies, ...
    (sci.crypt)
  • Re: multi time pad to seed other cypher
    ... > Lets say you have a symmetric cipher with a 256 bit key. ... > Obviously this method depends on the security of the symmetric cipher. ... One Time Pads (OTP) are just used once. ... Since OTP can be big, an entire hard disk for instance, a pad ...
    (sci.crypt)