NetNews Usenet Archive 1992 #16/NN_1992_16.iso/spool/sci/crypt/2791

Text File | 1992-07-30 | 2.8 KB | 60 lines

Newsgroups: sci.crypt
Path: sparky!uunet!usc!cs.utexas.edu!hermes.chpc.utexas.edu!jonathan
From: [e-mail] (Jonathan Thornburg)
Subject: linear congruential RNG cipher (was: Re: Cypher algorithm question.)
Message-ID: <[e-mail]>
Summary: this is a very bad cipher, it's easy to break
Keywords: cipher linear congruential random number xor weak Knuth break
Sender: [e-mail]
Organization: U of Texas at Austin / Physics Dept / Center for Relativity
References: <tom.712397505@cluster>
Date: Fri, 31 Jul 92 03:42:44 GMT
Lines: 46

In article <tom.712397505@cluster> [e-mail] (Thomas Essebier) writes:
>By far not being an expert on cryptology, I would appreciate some
>comments on the crypto scheme below.
> [ use a standard linear congruential random number generator (= RNG),
>   primed with the key, to derive a stream of bits, which is then xor-ed
>   with the data ]
>
>Where does it stand in terms of security when compared to transposition
>cyphers, DES etc.

I'm sorry, but this is a very weak cipher -- it's very easy to break.
There are (at least) two main weaknesses:

(1)    As you described it, there are only 2^32 possible internal
    states of the RNG.  Computers are fast enough today that
    the brute-force attack of trying all of them is feasable
    for any mildly determined opponent.

(2)    The simple structure of a linear congruential RNG makes this
    scheme breakable using a much cheaper and more "elegant"
    attack.  The linear and self-inverse nature of xor
    (i.e. a xor b xor a = b) makes the RNG output stream
    recoverable from the ciphertext only with a bit of work,
    or trivially from a plaintext/ciphertext pair.  Given the
    RNG output stream, Knuth v.2 section 3.6 excercise 7
    describes how to recover the RNG parameters, including the
    starting value = crypto key.

In general, the fundamental lesson of crypto history is that good
cryptosystems are designed *only* by people who have both theoretical
knowledge of, *and* practical experience with, breaking existing
high-quality cryptosystems.  In other words, unless you have a lot
of crypto experience you're unlikely to come up with a system that
would withstand professional attack.

If you simply want a secure cryptosystem, use DES (appropriately,
i.e. in the right mode, with secure keys, and with proper attention
payed to defense against "practical cryptanalysis").  It's secure
against anyone short of a very big corporation or a medium sized
government.  And if Exxon or the FBI *really* want the contents
of your disk drive, they'll probably get it one way or the other...

- Jonathan Thornburg
  <[e-mail]> or <[e-mail]>
  University of Texas at Austin / Physics Dept / Center for Relativity
  and (for a few more months) U of British Columbia / {Astronomy,Physics}