Topic: Reversing PRNGs

How one could achieve a "random" behaviour of index variable in a polymorphic decription loop? This topic was already mentioned on this forum, here (MentalDriller's PRIDE, xor-based permutation). Another idea is to use a LCG and find the modular mulptiplicative inverse for the selected multiplier. I wont go into math details of the topic (you can easily find all neccessary info in Wiki), so suppose that we have LCG: x_next = (a * x + c) mod m; if we choose prime m, it's immediately follows from the properties of LCG, that there exists such r, that (a * r) mod m = 1, and that x_prev = (r * (x - c)) mod m. In other words it is the random numbers generator which could produce the same sequence in a reverse order. Given the multiplier a and modulus m, r could be foud with the followig code:

uint32_t xgcd(uint32_t a, uint32_t b)
{
        uint32_t x, y, u, v, m, n, q, r, b0;
        x = 0; y = 1; u = 1; v = 0;
        b0 = b;
        while (a != 0) {
                q = b / a;      r = b % a;
                m = x - u * q;  n = y - v * q;
                b = a;  a = r;  x = u;
                y = v;  u = m;  v = n;
        }
        return x % b0;
}
...
r = xgcd(a, m);

the you can go through the sequence both forward and back with

uint32_t lcg(uint32_t x)
{
        return (x * a + c) % m;
}

uint32_t icg(int32_t x)
{
        x -= c;
        while (x < 0)
                x += m;
        return (r * x) % m;
}

so the following code

/* test1 */
        for (i = 0; i < 10; i++) {
                y = lcg(y);
                printf("%d:%u\n", i, y);
        }
        for (i = 9; i >= 0; i--) {
                printf("%d:%u\n", i, y);
                y = icg(y);
        }

would produce:

0:222
1:288
2:142
3:196
4:163
5:236
6:209
7:67
8:189
9:44
9:44
8:189
7:67
6:209
5:236
4:163
3:196
2:142
1:288
0:222

(with a = 17, m = 317, c = 1 and calculated r = 56).

And don't forget that m must be prime, or the rest of constats should be selected by differet criteria.
P.S. I would like to thank whale who years ago asked how to construct reversible rng, just found his message recently ad bothered to find the aswer.
P.P.S. Most likely I will write a few words more on this topic.

update (2011-01-28) Here is the link to the article that appeared in VWB#1:
herm1t Inversing a random numbers
and significant correction.

Re: Reversing PRNGs

Sorry for being a heretic, but what is the actual benefit of this method compared to Mental Driller's algo?

Thumbs up Thumbs down

Re: Reversing PRNGs

technocrat wrote:

Sorry for being a heretic, but what is the actual benefit of this method compared to Mental Driller's algo?

It's just another possibility to do the same thing. It produces the large number of possible variants and uses less code in the decryptor.

4 (edited by SPTH 2010-11-07 02:06:55)

Re: Reversing PRNGs

herm1t, this is crazy, I've tried it now for ~30mins to understand why this works, but I was not able to. And Wikipedia also does not provide some proofs that could help.

So: If you have the r (however you got it), why x_prev = (r * (x - c)) mod m holds? I dont see it.

And: Why can you calculate the r without bruteforce?

Could you please provide a text that explains that crazy modulo fun? smile

(Usually I understand maths quite fast, but i've not much experience with the modulo operator, so I have no idea how to play with that - i'm curious wink)

Re: Reversing PRNGs

First of all I need to apologize for the small mistake in the code, there should be (- c) mod m, instead of just minus to prevent wrap around zero, so the correct code should be:

uint32_t icg(int32_t x)
{
        x -= c;
+      while (x < 0)
+               x += m;
        return (r * x) % m;
}

and

               m = x - u * q;  n = y - v * q;
+              while (m > b0)    m += b0;
+              while (n > b0)    n += b0;

btw, the second "while" is there just in case I didn't saw wrap-around during tests with it removed.

NB! You also have to choose small m's to avoid overflow and a < m to be sure that r would be unique.
For the prime m \in [1024...2048] and a < m there would 200K+ possible generators (with random increments this numbre will grow appropriately).

SPTH wrote:

herm1t, this is crazy, I've tried it now for ~30mins to understand why this works, but I was not able to. And Wikipedia also does not provide some proofs that could help.

Let me cite from wiki (Modular multiplicative inverse)

The multiplicative inverse of a modulo m exists iff a and m are coprime (i.e., if gcd(a, m) = 1).

Since I choose prime m, any a will fulfil the condition.

If you'll choose 2^32-1 as m, then you'll have to check whether a is co-prime with m, it should not be divisible by factors of m (3, 5, 17, 257, 65537)

The requirements on other contants are irelevant because our goal is not to make good random numbers, but to fool the av heuristics, one could use several layers of encryption to achieve better coverage. However, if one will select the constants carefully (check wiki again on LCG) the generator will achieve full range.

SPTH wrote:

So: If you have the r (however you got it), why x_prev = (r * (x - c)) mod m holds? I dont see it.

by definition: a * r mod m = 1, so, if we have x_n = (x_{n-1} * a) mod m and then multiply it by r we'll got: x_{n-1} * a * r mod m, since a * r  = 1, it reduces to x_{n-1} i.e. the previous number.

suppose that we have m = 11, a = 3, r = 4 and x0 = 2

direct: 2 * 3 mod 11 = 6 , 6 * 3 mod 11  = 7
reverse: 7 * 4 mod 11 = 6, 6 * 4 mod 11 = 2

SPTH wrote:

And: Why can you calculate the r without bruteforce?

When the inverse exists, it is always unique in Zm where m is the modulus.

So we knew that r exists, that it is unique and that there is Extended Euclidean algorithm which will find the r in O(log(m)^2), so why brute-force it? ;-)

SPTH wrote:

Could you please provide a text that explains that crazy modulo fun? smile
(Usually I understand maths quite fast, but i've not much experience with the modulo operator, so I have no idea how to play with that - i'm curious wink)

Later I will write an article with more explanations, tests and code. I have to test some other tricks and want to make a small PE that will include this and other snippets.

6 (edited by SPTH 2010-11-07 18:35:02)

Re: Reversing PRNGs

OK, I could follow your explanation now.

I did not know first that this holds:

a*(b mod m) mod m = (a*b mod m)
((a-c)mod m + c) mod m = a mod m

And the Extended Euclidean algorithm is very nice, have used that two years ago once, but forgot about it.

Could you use that Modular arithmetic for more than an inverse number generator?

I'm looking forward reading that text wink

Re: Reversing PRNGs

SPTH wrote:

OK, I could follow your explanation now.
I did not know first that this holds:

a*(b mod m) mod m = (a*b mod m)
((a-c)mod m + c) mod m = a mod m

Just found a funny rhyme:

    In arctic and tropical climes,
    The integers, addition, and times,
    Taken (mod p) will yield
    A full finite field,
    As p ranges over the primes.

And the Extended Euclidean algorithm is very nice, have used that two years ago once, but forgot about it.
Could you use that Modular arithmetic for more than an inverse number generator?
I'm looking forward reading that text wink

May be I could find other applications, dunno smile

Re: Reversing PRNGs

Cl0ne pointed me out that I did a very stupid mistake, I am very thankful to him for his suggestions, and wish to post his message in its entirety:

First of all, the modulus used in 32 bit words is not (2^32)-1, it
actually is just 2^32.

Therefore, modulus factorization is just a power of two, wich means
every odd number is coprime with the modulus. So you don't need to look
for any primes at all, just generate a random odd integer. As silly as
calling some random generator and then setting the less significant bit
of the double word.

So you can make
((2^32)/2) * (2^32) = (2**31) * (2^32) = 2^61 different decryptors with
this tech.
I hope you find this interesting, mathematics are something useful when
it comes to creation.

This will further decrease the number of instructions both in encryption and decryption parts and increase the overall number of possible decryptors. Thanks to cl0ne. :-)