## Summary

We bet on a casino that implements the Golang PRNG. From truncated outputs we can (almost) reconstruct the internal state. By winning with high frequency we are able to exponentially increase our balance and retrieve the flag.
**Event Link:** [TetCTF 2023](https://ctftime.org/event/1842)/[Casino 2](https://ctftime.org/task/24351)

## Challenge Description
We have a casino implemented in `golang` and we have to make bets in order to earn money and win the flag. The structure is quite simple, and we are provided some `JSON` APIs to play:
- `{'recipient':'Casino', 'command':'Register', 'username':username}` registers a user;
- `{'recipient':'Casino', 'command':'ShowBalanceWithProof', 'username':username}` gives us the balance, plus a proof of the validity of that balance that we have to exibit in order to obtain the flag once we have enough money;
- `{'recipient':'FlagSeller', 'command':'PrintFlag', 'balance':balance, 'proof_data':proof}`, where `balance` and `proof` are the result of `showbalance`, gives us the flag; by reading the function in `flag_seller.go`, we notice that this call shows us only the first `l` characters of the flag, where `l` is the bitlength of our balance divided by `8`;
- finally, `{'recipient':'Casino', 'command':'Bet', 'username':username, 'amount':amount, 'n':n}` allows us to bet on one number `n`; the casino then picks a random number between `0` and `2023`, and if we guessed correctly, we are given back our bet multiplied by `2023`, otherwise we loose it; notably, if we make a mistake we are returned the correct number.
We start from a balance of `2023`.

## Solution
This challenge is the follow-up of the `Casino` challenge. The `Casino` challenge was more of an intrduction, since negative bets were allowed. You can hence earn an illimited ammount of money while losing, and quickly buy the flag. However, this bug is fixed in `Casino2`. This means that we have to actually break the casino.
The random number is generated using the builtin golang function `rand.Intn(2023)`, which is seeded at the startup via `rand.Seed(int64(binary.LittleEndian.Uint64(tmp)))`. The `tmp` vector is initialized using `cryptorand.Read`, which accordingly to the official golang documentation is cryptographically secure. This means that the only way to break the seed is to try all the possible ones. According to [this post](https://will62794.github.io/security/hacking/2017/06/30/cracking-golang-prng.html), `rand.Seed` takes values `mod 2^31`, which means that we can break it computing and storing the first values of `rand.Intn` for seeds from `0` to `2^31`. Most of the people on the discord channel solved it in that way (for example [here](https://hackmd.io/@toxicpie9/H1ieXyJsj#Challenge)). However, it took *a few hour of CPU time* on their machine. On my old laptop, this was probably not an option.
I then tried to understand how `rand.Intn` works. This was a very hard step, since I never used golang before and hence I tried to avoid reading the source code, regarding it as the last step. On the other hand, I didn't find a lot of docs online. However, [this post](https://www.leviathansecurity.com/media/attacking-gos-lagged-fibonacci-generator) affirms that it is a **Lagged Fibonacci Generator** with equation

$$x_n = (x_{n-273} + x_{n-607}) \mod (2^{63}-1).$$

This means that the PRNG has an *internal state* consisting of the last `607` numbers, and each number returned is then appended to the state. Of course, we have no control on the first `607` numbers, which are generated by the seed. However, we can discover them `mod 2023` by betting `1` on random numbers for `607` times. This does not give us precisely the internal state (which is made up by numbers up to `2^63`) but is a good start. We can still use the numbers we have to try to compute the upcoming ones and win money.
I implemented this simple formula, and the result was promising: it had a good winning rate of about `1/5`. Recall that every time we win our bet is multiplied by `2023`. This means that on average if we bet `1` five times, we will win once with a gain of `+2018`.
We are clearly beating the casino, but this is not enough. Infact, from the source code we see that when we ask for the flag we only obtain the first `L` characters, where `L` is the number of bytes of our balance. Even without knowing the length of the flag in advance, it is clear that we have to exponentially increase our balance over the time. A simple way to achieve that is to split our balance in a reasonable number of equal parts, for example `10`. Then for `9` times we bet `1/10` of our initial balance, and if we win we obtain `200` times our balance. If we lose all the `9` times (which is very unlikely, since we win on average once every `5` times) we still have `1/10` of our initial balance. In both cases we start again splitting the new balance in `10` parts, until we have enough money.
This simple trick gives us the flag (`TetCTF{______l3ft_0r_r1ght_0r_b0th?______}`) very quickly; actually, most of the time was spent on retreiving the first `607` numbers.