New PRNG algorithm
Ilya O. Levin
Hello,
I would like to bring to your attention the paper
"Sapparot-2. Fast Pseudo-Random Number Generator".
The purpose of this paper is to introduce an enhanced
version of Sapparot. It is a high-speed pseudo-random
number generator efficient in both software and hardware
yet very simple.
The paper is available at
http://www.literatecode.com/get/sapparot2.pdf
Regards,
Ilya
g...@qualcomm.com
Your paper talks about this as a PRNG, and yet you have a section in it
about security, and you're posting to sci.crypt.research; both of these
lead me to the impression that you think it might be useful as a stream
cipher. By the standards stream ciphers are currently held to, I don't
think it is. Although it might be a perfectly good PRNG for statistical
or gaming applications.
There is a class of attacks called "Guess-and-Determine" attacks. In
these we first tally up what we know about the various unknown values,
usually considered as single bits. Things like "this xor that xor carry
= known". Choose the equation with the least unknowns, and guess the
value of one of them. Eventually this will allow us to infer
("determine") the value of some other unknown bit, so we get to a place
where we start to get two-for-the-price-of-one. Soon after that
happens, we start to get to a point where we can check whether the
results seem to "add up" -- where, if we guessed wrong, we'll get a
contradiction, and can backtrack. Our paper
http://www.qualcomm.com.au/PublicationsDocs/new_snow_gd3.pdf shows one
application of this technique in all its glory, where we manage to
recover the key for the original version of SNOW in
less-than-brute-force time. (And I'm not talking about time-memory
tradeoffs here, which you mention in your paper.)
I can see a fairly straightforward way to apply this kind of attack to
Sapparot-2. There's only one thing in there that prevents it being
pretty easy, and that's the variable rotation by the B column, applied
to the C column. (The carries from the integer additions are only a
minor complication, best handled by working from least significant bits
upward where possible.) So, we work around the rotation. Assuming that
it really is a fairly OK PRNG, we can assume that any desired value for
that rotation occurs uniformly at random. (In all the discussion that
follows, I'll use numbers for the t = 32 bit version.) It seems to me
that it will be advantageous to the attacker to keep the incoming "A"
column and the C column "lined up", so we will first look for places
where the high order 5 bits of the incoming B are "00111". This will
rotate the C column by 7 places, same as A. To do this we'll have to
gather about 33 consecutive words of output from the generator, and try
to apply the attack to each pair; generally it will fail, but we expect
it to work for one of them. This multiplies the effective complexity of
the attack by 2^5, but then gives us 5 bits of information we can use
already.
Anyway, we now can assume the value for those five bits is what we
needed it to be. Note that these are also the same five bits that get
xored to the low-order values taken from A into the B column! (This is
lucky for this attack; you might want to change that 5 bit rotation to
something different.) Now look at the least significant bit of the
first output. It's the xor of the three LSBs. But the first thing you
do to it xor A into C (we're talking about the LSB here, so add is
equivalent to xor since there's no carry.) So we know that that bit is
actually, now, just the LSB of B xor C... one variable has already
disappeared! If we guess the LSB of input B, for example, we now know
the corresponding LSB of input C, which becomes bit 7 of output C. Now
look at the B column; we already guessed that LSB, so we know it. It
gets xored with a 1 bit (that we knew from the rotation amount) and a
constant 1 bit from the A column, which cancel out, so the LSB of
output A is now known. ...
Now this kind of analysis is most amenable to machine optimization, but
even in the example I started above, where I just consider one pair of
consecutive outputs, we have 64 bits of information about the state,
and only 96 bits of state. Our experience tells me that we can probably
recover the internal state in something not much worse than 2^32
guesses, counting backtracking when we can check internal
contradiction; the depth of the search tree will probably be greater
than 32, but many branches will get pruned before they are anywhere
near that deep. Note: I'm describing the attack as if I just look at a
single pair of words, but in reality I think it will probably work
better on three or four consecutive outputs, with corresponding
requirements for more plaintext. The tradeoff here is that you get much
more information about the bits, but have to manage more complexity. I
wish I had finished my "generic G&D attack" program, this would be a
great exercise for it. But I never did, and I don't have time to go off
and implement this specific attack.
Hmmm... going back and looking again, I think that choosing the
rotation to be 5, and not 7, actually works even better. But anyway.
Any honours student out there who wants to take my start and run with
it?
Anyway, I could be wrong, particularly about the expected complexity of
such an attack, but I really don't think this generator is
cryptographically sound.
Greg.
Francois Grieu
In article <pgpmoose.200503020432.10634@garie>,
"Ilya O. Levin" <e...@literatecode.com> wrote:
> I would like to bring to your attention the paper
> "Sapparot-2. Fast Pseudo-Random Number Generator".
http://www.literatecode.com/get/sapparot2.pdf
I have a simple attack on Sapparot-2 with t=32 bit, that from three
consecutive outputs (after a warm-up of 2**33 steps) recovers the
internal state with excellent probability, and thus is then able to
trivially predict future output. The average attack cost is about 2**30
rounds, less than the cost of the warm-up. The attack still often
succeeds with the warm-up reduced to 2**31 steps.
One round of 32-bit Sapparot-2 goes:
#define R(x,y) (((x)<<(y))|((x)>>(32-(y))))
unsigned long a,b,c,s; // assumed to be 32 bit
c = R(a+c, b>>27);
s = a+0x9e3779b9;
a = ((a<<1)+1+b) ^ R(b, 5);
b = R(s, 7);
s = a ^ b ^ c; // the output
I observe that C does not influence A and B. The round function
transforms AB thru an iterated function. This function is not a mapping,
therefore the theory of iterated functions makes it reasonable to expect
that, after enough steps [say about 2**33], AB belongs to a relatively
small subset of roughly 2**32 values, whatever the 2**64 values of the
initial AB; and that this subset is mostly covered by a handful of
cycles.
Experiment confirms this. For a hundred seed values that I tried, AB
converges in less than 2**33 steps into one of four cycles, best
described by one of their point and the cycle length:
A B length
00000014 D23BF92E 0371C52B
00000001 C3241368 07EA945A
00000002 A704E990 66218565
00000000 58C47C28 A37F7BFF
Given 3 consecutive outputs Sj S{j+1} S{j+2} for j>=2**33, the attack
simply assume that AB entered one of these four cycles, explore the
(slightly over) 2^32 values of AB, deduce C as A^B^Sj, step the
generator once to verify S{j+1}, and if it matches step once more to
verify S{j+2}. Because the first cycle is both short and likely, the
attack has cost about 2**30 rounds, and takes seconds. Computing the
above 12 values (necessary to run the attack) required about 2**38
simplified rounds, and took a few minutes (and less than 2 hours of
programming).
Conceivably, the attack could translate to the 64-bit Sapparot-2, but
then it would be very compute-intensive; something better is needed.
Sapparot-2 also seems a possible target for SAT cryptanalysis. General
sketch: assuming the first few (4) outputs known, express using Boolean
logic the relationship between the 2t unknown variables forming A0 B0
(introducing some extra variables for carries where addition is
involved, to keep the equations simple); translate into a Satisfiability
problem; then solve using a general SAT solver. It seems possible this
would break both the 32-bit and 64-bit version, but I have not tried.
Yet.
Note: SAT cryptanalysis fails on "good" cryptosystems
http://www.ing.unitn.it/~massacci/papers/mass-marr-00-JAR.pdf
Francois Grieu
Ilya O. Levin
Greg wrote:
> Your paper talks about this as a PRNG, and yet you have a section in it
> about security, and you're posting to sci.crypt.research; both of these
> lead me to the impression that you think it might be useful as a stream
> cipher. By the standards stream ciphers are currently held to, I don't
> think it is.
I would definitely agree with you. Sapparot was designed as a PRNG
and it is not meant to be a stream cipher by itself. What I think is it may
be
used as an element to build a proper stream cipher on top of it. Thus I
believe that treat and analyze this generator as a self-sufficient stream
cipher is a good idea because it will help to identify aspects you need to
pay attention during design of actual cipher.
For example Sapparot-2 as a PRNG may be converted to a simple stream
cipher by replacing final confusion a xor b xor c with filter
R(R(c,22)+b,13)+R(R(c,7)+a,14). This replacement will not degrade
randomness but it will significantly reduce likelihood of attack that
you've described.
> Although it might be a perfectly good PRNG for statistical
> or gaming applications.
It may be better to use original Sapparot in this case because it was
simplified exactly for such purposes. It has the similar statistical
characteristics yet simpler and faster.
> Any honours student out there who wants to take my start and run with
> it?
Yes, anyone?
Meantime thanks for your nice outline of G&D attack, Greg.
Regards,
Ilya
---
http://www.literatecode.com