🚀 go-pugleaf

The key, so to speak, to this scheme is how you generate the pseudo-random
numbers.  When I need good random numbers, I run DES in output feedback
mode.  Of course, the security of this PRNG is exactly that of DES itself.

There are two issues here: 1) The academic consideration of RNGs with
"truely" random distributions and 2) The consideration of being able to
predict the random number series.

All of the academic consideration of RNGs I have seen focus on 1). 2) is
necessary for using them in an encryption system. I have made my RNGs
pretty unpredictable by running 32 different Additive Congruential Method
RNGs, and only selecting one bit of each for each 32-bit number. I do so
by randomly (another RNG) selecting the particular bit from each. Of course,
this is computationally extremely expensive.

I believe that the OTP using itis pretty safe. However, safety can be improved
by compressing the oriignal file and then distributing it randomly through
a random number file.

The compression removes redundancy in the signal. The distributing it randomly
through a random number file hides the signal in noise, similar to spread
spectrum transmission.

However, none of this works if the opposition can predict the random number
series.

-- 
Lew Glendenning		rlglende@netcom.com
"Perspective is worth 80 IQ points."	Nils Bohr (or somebody like that).

In<1992Oct5.221733.27777@netcom.com>, rlglende@netcom.com (Robert Lewis 
Glendenning) writes:

>                                                    I have made my RNGs
> pretty unpredictable by running 32 different Additive Congruential Method
> RNGs, and only selecting one bit of each for each 32-bit number. I do so
> by randomly (another RNG) selecting the particular bit from each. Of course,
> this is computationally extremely expensive.
>
> I believe that the OTP using itis pretty safe.

I don't.

If you're using a standard linear congruential generator as supplied with
the average compiler, then it will have 32 bits of internal state and we 
can assume the attacker knows the constants (the a, b such that x_{n+1} = 
ax_{n} (mod b)).

Now guess the internal state of the generator which you use as a pointer: 
this takes on average 2^{31} tries. For each guess, do the following:

  Take about 1500 bits of keystream and from it pick, for the first of the
  32 target generators, 40 bits which would have come from that
  generator (if our guess was right).

  Use the first 32 of these bits to solve for the target generator's state 
  (note x_{n+k) = ka.x_{n} (mod b)).

  Check the next 8 bits to see if they're consistent with your reconstruction. 

    If not, go to the next guess.
    If they are, go to the second target generator

     . . .

  If no contradiction is found despite reconstructing all 32 target
generators,   
  stop.

The above can be optimised a lot - with more maths, you can discard lots of
guesses at a time. 

It can get slightly messier if the generators' recurrence relations are 
unknown, but even then it's still reasonably tractable. Even with only the 
known optimisations, you'd have to put at least 80 bits of internal state 
in each of your component generators for the above analysis to become
unfeasible. Even then, I'd be nervous about someone coming up with a better
optimisation.

This is a variant of an attack on multiplexed shift register sequences which 
I thought up in 1986 and was allowed to send off for publication in 1989;

	Cryptologia vol XIV no 3 (July 1990) pp 285 - 288
	`Solving a class of stream ciphers' 
	RJ Anderson

There's a more general (but slower) attack in:

	Proc Crypto 89 (Springer LNCS 435) pp 164 - 174
	`On the Linear Consistency Test (LCT) in Cryptanalysis'
	KC Zeng, CH Yang, TRN Rao

Stream ciphers are fun - why do so few Americans do any work in the field?
Almost all the research seems to come from Europe and China!

Ross

In <1992Oct5.221733.27777@netcom.com>
rlglende@netcom.com (Robert Lewis Glendenning)
writes:
> There are two issues here: 1) The academic consideration of RNGs with
> "truely" random distributions and 2) The consideration of being able to
> predict the random number series.

	For the sake of accuracy:

	(1) is it statistically random?
	(2) is it predictable?

	if (1) is not true, the chances for (2) becoming
	true increase.  This is the academic argument.

	The pragmatic argument says it is possible to
	generate a stream for which (2) is true, without
	consideration for the truth of (1).  But the fact
	is that if (2) is true, you can bet that (1) is
	likewise.  It won't be an accident.

> All of the academic consideration of RNGs I have seen focus on 1). 2) is
> necessary for using them in an encryption system. I have made my RNGs
> pretty unpredictable by running 32 different Additive Congruential Method
> RNGs, and only selecting one bit of each for each 32-bit number. I do so
> by randomly (another RNG) selecting the particular bit from each. Of course,
> this is computationally extremely expensive.

	You have 32 PRNG using different parameters (but same algorithm).
	You pick 1 bit from each, but in RANDOM order.  How random?  Is
	it another PRNG?

	You realize that if each PRNG is not cryptographically secure in
	its own right, the 32 are not any more secure, unless you have
	a "true" random source to pick your PRNG sequences.  In which
	case you don't need the 32 PRNGs.

> I believe that the OTP using itis pretty safe. However, safety can be improved
> by compressing the oriignal file and then distributing it randomly through
> a random number file.
> [ ... ]

	PRNGs can be usefull as key generators, if they are used
	to pick material from a non random source, but nevertheless
	unknown to the opposition.  Take one PRNG and use the result
	to index into a string of sufficient length (say, some book
	on CD).  As long as you don't divulge the source of your raw
	material (and change it often) you are in clover.  But: how do
	you distribute the key?  Do you phone your covert correspondant
	and tell him to go buy the CD?  Aside from the annoying security
	considerations, can you be sure the two of you will get the exact
	same text (editions vary from country to country)?

	But why bother with PRNG's of you have access to long files
	you can share with your correspondants.  The files themselves
	are good enough as a source of key material.

	Suppose you have enough raw material to make two files.  For each
	character of each file generate a parity bit.  If the two bits
	are different use the byte from the first file, else use the
	byte from the second file.  Advance to next byte of each file.
	Or you could simply use the parity bits as your OTP key.
	These are just two samples of the many ways...



--
 Alain