# Challenge Name: Delegate Wallet

I have been using this software for generating crypto wallets. I think if I was able to predict the next private key, I could probably steal the funds of other users.

EU instance: 161.97.176.150 4008

US instance: 185.172.165.118 4008

Author: Soul

## First Glance

We are given a remote service and a [wallet.py](https://github.com/pragyanmehrotra/0x414141_2021/blob/master/Delegate%20Wallet/wallet.py).

```
class prng_lcg:

def __init__(self):
self.n = pow(2, 607) -1
self.c = random.randint(2, self.n)
self.m = random.randint(2, self.n)
self.state = random.randint(2, self.n)

def next(self):
self.state = (self.state * self.m + self.c) % self.n
return self.state

```
This is the most interesting piece of code in the file rest of the code is just interacting with the client. So from here it's clear that our n = 2^607 - 1 which stays constant for each execution, but m and c are generated randomly.

We have a look at the remote service as seen in wallet.py we are given 2 options to generate a new wallet seed or to guess it.
```
1) Generate a new wallet seed
2) Guess the next wallet seed
>
```

## Approach

From the above observations, our task boils down to simply finding m and c. Since if we know m and c then we can generate a seed $s$ and we would know that the next seed is given by the equation s_new = m\*s + c %n

Now, we are given the liberty to generate as many seeds as we want. Which creates the vulnerability with reused parameters in [LCG (Linear Congruential Generator)](https://en.wikipedia.org/wiki/Linear_congruential_generator).

This can be seen as a simple mathematical problem as -

Let s0 <- random seed, Then,

s1 = (m\*s0 + c) mod n

s2 = (m\*s1 + c) mod n

s3 = (m\*s2 + c) mod n

Now,

=> s3 - s2 = (m\*s2 + c) - (m\*s1 + c) mod n

=> s3 - s2 = m\*(s2 - s1) + c - c mod n

=> s3 - s2 = m\*(s2 - s1) mod n

=> (s3 - s2)\*(s2 - s1)^-1 = m\*(s2 - s1)\*(s2 - s1)^-1 mod n

=> m = (s3 - s2)\*(s2 - s1)^-1 mod n

and once we have m,

s2 = m\*s1 + c mod n

=> c = s2 - m\*s1 mod n

Simple code to solve the equations given s1, s2, s3

```python
n = pow(2, 607) -1
m = ((s3 - s2)*gmpy.invert(s2 - s1, n))%n
print "m: ", m
c = (s3 - m*s2)%n
print "c: ", c
print "s4: ", (s3*m + c)%n
```

Actual solution: [solve.py](https://github.com/pragyanmehrotra/0x414141_2021/blob/master/Delegate%20Wallet/solve.py)

`flag{NBD_7H3Y_U53D_0ffsh1ft4532}`

Original writeup (https://github.com/pragyanmehrotra/0x414141_2021/blob/master/Delegate%20Wallet/writeup.md).