Path: illuminati.io.com!uunet!news.mathworks.com!udel!gatech!swrinde!elroy.
+     jpl.nasa.gov!decwrl!waikato!auckland.ac.nz!news
From: suk@usceast.cs.scarolina.edu (Peter Kwangjun Suk)
Newsgroups: sci.crypt.research

Subject: Re: A cryptographic pseudorandom number generator
Date: 8 Mar 1995 21:47:42 GMT
Organization: University of South Carolina - Columbia - Computer Science
Lines: 48
Sender: crypt-submission@cs.aukuni.ac.nz (sci.crypt.research co-moderator)
Approved: crypt-submission@cs.aukuni.ac.nz
Message-ID: <3jl8lu$pdv@net.auckland.ac.nz>
References: <3jdkuc$k6h@lyra.csx.cam.ac.uk>
Reply-To: suk@usceast.cs.scarolina.edu (Peter Kwangjun Suk)
NNTP-Posting-Host: cs13.cs.auckland.ac.nz
X-Newsreader: NN version 6.5.0 #7 (NOV)





John Kelsey  writes:
 
>   I like this general idea (using a fast stream cipher for short lengths
>of ciphertext, and then refilling the internal state from a slower cipher).
>There's a tradeoff going on between size of the fast cipher's internal state
>(which may impact security) and how often you can afford to resynch.
>[deleted]
>
>   A couple ideas for the general design of this kind of thing:
>
>1. Resynch needs to be relatively fast, so it can be done fairly often.  I
>   think this implies using a fast cipher with a relatively small internal
>   state, because you want your resynch function to be strong, and it should
>   be OK for it to not be able to generate too many bits quickly.
>
>2. Resynch should be independent of current internal state--there should be a
>   resynch string or IV passed in which, along with the key, can be used to
>   resynch the cipher.
> [deleted]
>
>...RC5-32/16/40 in OFB-mode, with S as the IV.  The throughput you need
>determines how often you can afford to resynch, but I like the idea
>of using this kind of method to encrypt sectors of a disk for
>random-access.
>
> --John Kelsey, jmkelsey@delphi.com
 
 
How about using the secure Blum-Blum-Shub quadratic residue generator
with a 512 bit modulus?  We could run a fast 64-bit block cipher in
OFB mode, and occasionally flush the shift register and insert 63 bits
from seven iterations of the BBS generator.  (We have lg(512) = 9 bits
available from an iteration.)  Since we can compute the ith state of
the BBS generator, we can even use this to do random access.  (We just
start our decryption one resynch before we need that data.)
 
For greater security and speed in a hardware implementation, we could
run the above in hardware, using 7 BBS generators in parallel (with 7
different 512-bit moduli) and the same 64 bit block algorithm running
in OFB mode.
 
--PKS