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

Text File | 1992-11-11 | 5.5 KB | 104 lines

Newsgroups: sci.crypt
Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!darwin.sura.net!gatech!news.ans.net!newsgate.watson.ibm.com!yktnews!admin!wo0z!lwloen
From: [e-mail] (Larry Loen)
Subject: Re: pseudo one time pad...
Sender: [e-mail]
Message-ID: <[e-mail]>
Date: Wed, 11 Nov 1992 19:38:48 GMT
Reply-To: [e-mail]
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
References:  <[e-mail]>
Nntp-Posting-Host: wo0z.rchland.ibm.com
Organization: IBM Rochester
Lines: 89

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

>In the FAQ (Thanks to Larry Loen for this... it is informative...), the
>following is stated about pseudo one time pads:

>  There are a variety of cipher systems which generate "pseudo
>  one time pad" streams of cipher key, but all have the same
>  theoretical vulnerability; any algorithmic process introduces
>  relationships between some old key bit(s) and the new key bit
>  and so permits cryptanalysis.  "Random number generators" are
>  frequently dreamed up by newcomers as a "pseudo one time pad",
>  but they are notoriously vulnerable to analysis, all
               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>  independent of whether the pseudo-random stream satisfies
>  randomness tests or not.

>My question is, why?  Now before I get roasted & told to "read the
>literature..." and "your an idiot...", I have read the literature.  I've
>also spent a considerable amount of time working with/analysing pseudo
>random number generators (PRNGs).  It seems to me that, if your source is
>sufficiently random (ie. NOT some type of feedback shift register or linear
>recurrence equation, but something random in a cryptographic as well as a
>statistical sense), and you follow the one time rule (ie. only use any key
>ONCE - never encrypt 2 files with the same key), this should be pretty
>secure.  For example, would the following be "vulnerable to analysis"?

>1) DES a file of ASCII 0's (of the same length as the plain text) with
>some key - this gives you a pseudo-random bit stream.

>2) XOR this with the plain text ---> cipher text.

>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.

A change to DES from a typical "random number generator" is not a trivial change
and was not what I had in mind in the FAQ.  What I had in mind was the
general, non-crypto person's idea of random.  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.
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.

Actually, if your example is DES in Electronic Codebook mode rather than cipher
feedback mode, it is simply "Vigenere cipher" of period 8 and very
vulnerable.  If you meant DES in cipher feedback mode, I can't speak
offhand, but what you have is similar to other things I've seen
proposed as DES-based pseudo-one time pads.  ATMs and the like have
need for something like this; I don't know exactly who has done what,
but I am sure something like that is out there.  I recall, also, the
ANSI standard shows one possible way of doing something along this line.

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 :-) ? ).

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.

Likewise, as what is used looks less and less like a traditional peseudo-
random number generator and more like a general encryption system, your
point is more and more valid.

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?
--
   Larry W. Loen        |  My Opinions are decidedly my own, so please
                        |  do not attribute them to my employer