Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I a have a question about PRNGs and this is my very first experience with them. I have the following generator that takes a 56-bit seed $p$ during initialization and then chooses both $X$ and $Y$ randomly from the interval $[0, p]$.

Every time it is called, it returns the output of the next function:

def next(self):
    self.x = (2*self.x + 5) % self.p
    self.y = (3*self.y + 7) % self.p
    return (self.x ^ self.y)

I have the first 9 outputs of the generator and I need to predict the next output.

prng_output = [210205973, 22795300, 58776750, 121262470, \
           264731963, 140842553, 242590528, 195244728, 86752752]

I have thought of the solution which turned out to be correct by very slow, so apparently there must be another way to solve it.

My solution was to constrain the range of values for $p$ according to the given output. Also, generate all values for $X$ and for every value of $X$, calculate the first 9 values according to the previous equation and XOR it with the output to get $Y$. Finally, check of the sequence of $Y$s is valid or not (also according to the previous equation).

After some reading I learned that a reduced state (reduce the number of bits) of the generator can be determined.

So my question is how to crack the given generator, what is the "reduced state" of the generator, and how can I use that "reduced state"?

share|improve this question
    
Terminology nitpick: your $p$ is not a "seed", it's a parameter of the generator. Usually one would call it a "modulus", since that's how it's used in your algorithm. –  Ilmari Karonen Apr 6 '12 at 14:51
    
Thanks, for the correction. –  Samer Meggaly Apr 6 '12 at 22:10
    
The question is less than accurate: it turns out that p is 57-bit, not 56-bit (although that's not apparent from the known output, which happens to remain within 56 bits until the 28th output). Also, if the first self.x and self.y are chosen randomly in [0..p] rather than [0..p-1], that's an irregularity. –  fgrieu Apr 7 '12 at 6:32
    
No, this is a mistake of mine, x and y and chosen randomly in [0..p-1] and the problem stated that p is 56-bits. –  Samer Meggaly Apr 7 '12 at 6:43
add comment

3 Answers

I'm not familiar with the terminology "reduced state", so I can't address that half of the question.

However, this particular PRNG makes it easy to reconstruct the internal state; we note that the state function can be rewritten as:

x := 2*x + 5 - kx * p
y := 3*y + 7 - ky * p

for some small integers $k_x$, $k_x$ (in fact, $0 \le k_x \le 2$ and $0 \le k_y \le 3$. Once we do that rewrite, we notice that the lower bits no longer depend on the higher bits.

So, what we can do is:

  • Iterate over the possible $k_x$, $k_y$ values used to generate the second, third and fourth outputs; a total of 1728 possibilities.
  • For each set, we go through the possibilities for bit 0 of p and the initial x (note: because the initial y can be immediately deduced from the x and the first output, we don't have to iterate through that)
  • Check to see if there's a combination that gives the bit 0's on the second, third and fourth outputs that we have; if there is, then start looking through the various possibilities for bit 1 of p and initial x.

When we manage to get through all 29 bits, and get all the bits of the output we observed, then we have the answer (and in fact, continuing the generate outputs will, in this case, continue to generate the listed outputs).

Going through the above procedure gives us the answers p = 295075153, x0 = 89059908, y0 = 164204369, next output = 231886864

share|improve this answer
    
nice, Poncho's solution beats my explicit one, and convince me that the SAT solver would crunch the problem. –  fgrieu Apr 6 '12 at 20:14
    
First, thanks a lot for the help. Second, i still have some points that i cant understand ... how did u determine the ranges for Kx and Ky ? ... Also, i don know whether i got the second step or not, so u mean that for all values of X [0, 2^56] and for all values of bit-0 of p {0, 1}, find 3 pairs of (Kx, Ky) that will generate the 2nd, 3rd and 4th outputs. –  Samer Meggaly Apr 6 '12 at 22:01
    
@SamerMeggaly: well, because $0 \le x_0 < p$, then we know that $0 \le 2*x_0 + 5 < 3p$, and so doing the $\bmod$ reduction will cut out between 0 and 2 multiples of p (and similarly on the y side). As for step two, we start by iterating through the various possibilities of bit 0 of p and bit 0 of $x_0$, and once we've determined settings that works, we start on bit 1 of both, and work our ways up until we've recovered the entire value (or decided that the particular $k_x, k_y$ values weren't the right ones) –  poncho Apr 6 '12 at 22:17
add comment

The generator can be re-stated as having a key $(p,x_0,y_0)$, the recurrences $x_{j+1}=(2\cdot x_j+5)\bmod p$ and $y_{j+1}=(3\cdot y_j+7)\bmod p$, and the output $r_j=x_j\oplus y_j$ known for $j\in\{1\dots 9\}$.

We define $(u_j,v_j)$ such that $x_{j+1}=2\cdot x_j+5-u_j\cdot p$ and $y_{j+1}=3\cdot y_j+7-v_j\cdot p$. Notice that $(u_j,v_j)$ can take only 12 values. At the beginning or the sequence, or if $p$ was chosen such that the Linear Congruential Generators $x$ and $y$ are maximal-length, $(u_j,v_j)=(0,0)$ has odds only slightly lower than $1/6$. It is reasonable to hope that $(u_j,v_j)=(0,0)$ occurs for some $j\in\{1\dots 8\}$. If so, we know both $x_j\oplus y_j$ and $(2⋅x_j+5)\oplus (3\cdot y_j+7)$, as these are $r_j$ and $r_{j+1}$. There can be at most one solution $(x_j,y_j)$ for that, and it can be found simply by determining bits of $y_j$ from right to left. Some of these solutions can be eliminated, for they lead to $x_j$ or $y_j$ too big for $(u_j,v_j)=(0,0)$ to hold.

Then, for many values of $(u_{j+1},v_{j+1})$, there will be few possible values of $p$ compatible with $(x_j, y_j, r_{j+2})$, which are known unless $j=8$. and these candidates for $p$ can be found reasonably efficiently, again by finding bits from right to left. The rest is pesky details. Among these, the given that $p$ is 56-bit turns out to be wrong.


Another option is to encode the problem in the formalism of boolean satisfiability, and throw that to some SAT solver, like theses ones. This will work fine even if we have only 4 consecutive output values, none of which with $(u_j,v_j)=(0,0)$.

share|improve this answer
    
Thanks @fgrieu, i have two points that i tried to figure out, but i couldn't. First, how did u limit the range of p to [2^55, 2^56] ... Second, also the same for Xj and Yj. –  Samer Meggaly Apr 6 '12 at 22:09
    
@SamerMeggaly: By definition of the remainder, what is the range for $(2\cdot x_j+5)\bmod p$? Assuming $p$ known, what's the range for $x_j$ when $j>0$?. Same for $y_j$. What's the highest known $r_j$? Consider the high bit of that: how was it formed? What does that tell us on the minimum value of $x_j$ or $y_j$? What does that tell us on the minimum value of $p$? Does the problem statement give us a maximum value for $p$? If it did not, could we make a plausible conjecture, and at what odds? –  fgrieu Apr 7 '12 at 5:53
    
I know that the range for (2x + 5) mod p is [0..p-1], but wouldn't that make x < (p-5)/2 that is (2^56-5)/2 ? and the maximum value for p will be (2^56-1), please correct me if i am getting anything wrong. –  Samer Meggaly Apr 7 '12 at 6:46
    
We know $x_j<p$, including for $j=0$, given your recent comment. But contrary to the question's statement, $p$ is NOT 56-bit, it actually happens to be slightly above $2^{56}$ (that does not show until the 28th output). Ignoring the "56-bit" fragment of the statement, given that the first 9 outputs are within 56-bits, and assuming $(x_j,y_j)$ are random in $[0\dots p-1]$, odds are low that $p>2^{57}$, and we can confidently assume $p\le 2^{57}$. Thus $u_j=0\Rightarrow 2⋅x_j+5<2^{57}\Rightarrow x_j\in[0\dots 2^{56}-3]$; similarly $v_j=0\Rightarrow y_j\in[0\dots(2^{57}-8)/3]$. –  fgrieu Apr 7 '12 at 8:24
add comment

The two seeds add up to 56 bits but the fact that the random number is generated by xor'ing constrains the problem to 28 bits. With my machine running all 28 bit numbers xor the generating number gives every possible x and y in about 90 seconds. In python:

    P, out1, out2 = 295075153, 210205973, 22795300
    def search():
        for i in range(P):
            if ((2*i+5)%P) ^ ((3*(i ^ out1)+7)%P)  == out2:
                print('\nFound it! x =', i, ' y =',(i^out1))
                print()
                x = i
                y = (i^out1)
                print('output #1:',x ^ y)
                for j in range(2,11):
                    x = (2*x + 5) % P
                    y = (3*y + 7) % P
                    print ("output #%d: %d" % (j, x^y))          
                return
    search()
share|improve this answer
    
How did you derive P in the first place? It wasn't given in the original problem statement. –  poncho Nov 15 '13 at 19:39
1  
This was actually a programming assignment from Prof Boneh's class in Cryptography a few years ago online at Coursera. The P value was given. –  macAttack Nov 15 '13 at 19:52
    
@macAttack Nice share… [+1] –  e-sushi Nov 16 '13 at 16:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.