54 views

Skip to first unread message

Mar 1, 2005, 12:32:53 PM3/1/05

to

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

Mar 2, 2005, 2:57:31 AM3/2/05

to

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.

Mar 4, 2005, 4:57:58 AM3/4/05

to

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

Mar 4, 2005, 11:49:20 AM3/4/05

to

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu