NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/sci/crypt/4674

Internet Message Format | 1992-11-12 | 5.3 KB

Path: sparky!uunet!ogicse!uwm.edu!zaphod.mps.ohio-state.edu!sample.eng.ohio-state.edu!blanc!butzerd
From: [e-mail] (Dane C. Butzer)
Newsgroups: sci.crypt
Subject: Your post about pseudo one time pad...
Message-ID: <[e-mail]>
Date: 12 Nov 92 17:11:27 GMT
Article-I.D.: ee.1992Nov12.171127.2162
Sender: [e-mail]
Organization: The Ohio State University Dept of Electrical Engineering
Lines: 105


I was going to reply via e-mail, but I can't seem to reach you (and I
forget how normal mail works ;-).  Anyways, maybe some of the other
non-experts will have some other comments...

Also, I did not mean for the original post to come off as an attack on the
FAQ.  I think the FAQ is very informative (esp. to a newcomer).  I would be
willing to help w/ it in any way possible (although I'm obviously not an
expert - more of a serious hobbyist :-)

Now, on to it:

In article <[e-mail]> [e-mail] writes:
>In article <[e-mail]> Dane C. Butzer
>writes:
>

[My stuff describing DES as a pseudo one time pad omitted]

>
>>This is pseudo one time pad that I don't think would be "easy" to break.
>
>I agree, in principle, with your last statement.  But, it isn't what I had
>in mind when writing.  And, it does not contradict what I said.

Wasn't trying to contradict you :-)

>
> [Stuff about DES != typcal "random number generator" and clarification of
>  the type of PRNG you had in mind omitted]
>
>Indeed, I personally avoid the
>word "random" in the sense you call "cryptographic randomness"; I tend to
>call it "unpredictable" as contrasted with "random" and mean "algorithmically
>unpredictable" as opposed to "algorithmically random" since we are dealing
>with pseudo-randomness in virtually every case where these ideas apply anyway.
>

Good idea.  I'll do that from now on.  How about trying on a new acronym,
too: URNG for Unpredicatble Random Number Generator, to distinguish RNGs
that are designed for cryptography from the typical PRNGs?

>As the old "Ax+C" pseudo-random number generator shows, there is a clear
>distinction between satisfying statistical tests for randomness and avoiding
>a cryptanalyst's hunger for a predictable keystream.  Unfortunately, while I
>do see this fine point much discussed, it is not done in a standardized way
>and is certainly hard to convey to the uninitiated.

Another good point.  Hopefully, via your FAQ, we may get some standardization
of terms, atleast within the newsgroup.  Or is that too much to hope for?

>
> [stuff about how DES in electronic codebook mode gives you a nice random
> number stream... for 8 bytes :-) and how DES in CFM would work OK for POTP]
>
>So, such methods, if done right, are exactly as safe or as vulnerable as
>DES itself.  Done wrong (as I just gave an example above), it is not
>as good, of course.  But, you seem to understand this already.  (Perhaps you
>were wondering if I do :-) ? ).
>

Actually, I was just making sure I wasn't missing something.  From the way
pseudo one time pads are usually frowned upon, I thought I was.  However, I
hadn't found anything in the literature about that, and I'd seen several
proofs of the absolute security of a true one time pad, so I was getting a
bit worried that I'd overlooked something obvious :-(

>The problem is, of course, random number generators designed to satisfy
>statistical randomness may well not satisfy at all the need for being
>unpredictable in a cryptographic situation; most are very poor at this, in
>fact, not having been designed with the problem in mind.  Most novices do
>not understand the distinction between "randomness" as in passing Chi Square
>and "unpredictable" as in frustrating analysis.  So, they grab any old
>random number generator out of Knuth or something and usually grab wrong.
>
> [stuff omitted]
>
>Can I/How do I concisely clean it up with out hopelessly confusing the novice?
>I thought about the DES example,but decided to leave it out on grounds of not
>the right audience for the added information.  I don't want to have them read
>a section that intends to tell them that Ax + C "random" number generators
>are worthless and have them come to the opposite conclusion, even if I clean
>it all up, at length, elsewhere.
>
>Is there something simple I can say that will fix this, but won't introduce
>the "Ax+c is OK" problem, which is far worse, in my judgement, than leaving
>it as is?

I'm not sure.  You may want to include a section on randomness, and note
that there is a definite difference between statistical randomness, and
unpredictable in the sense of frustrating analysis.  I think that this is a
sufficiently basic point to include in the FAQ.  Then you could note
that the typical novice's PRNG might very well satisfy statistical
randomness, but probably won't satisfy "unpredicability".  Next you could
show a statistically good PRNG (as I recall, Ax+c and other linear
recurrence equations are actually pretty good statistically, right?), and
show why it wouldn't work as an unpredictable random number generator
(UNRG? :-) However, this might just confuse some of them too much anyways,
and lead to the "Ax+c is OK problem".  It may just be better to let people
that aren't sure about this issue post, like I did.  Anyways, thanks again
for the clarification...



Dane Butzer