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/Casino 2

## 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, `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). 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 by LeviathanSecurity affirms that it is a **Lagged Fibonacci Generator** with equation

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 up to a small error, and if we are lucky the errors will often be `0`

and we will be able to win money. Notice that if this approach doesn’t work, a more advanced attack is possible: I refer again to the post by LeviathanSecurity and the linked repository for more details.

However, I started implementing the 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. After that, we pick the resulting balance and play again. Assuming a winning rate of `1/5`

, the probability to lose 9 consecutive time is $\frac{4^9}{5^9} \approx 13\%$. This means that $13\%$ of the times we play this way, our balance is divided by 10. However, the remeaning $87\%$ of the time, we will win at least once, obtaining `200`

times our starting balance as a reward. On average, playing this game our balance will be multiplied by `~175`

times.

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.

## Alternative Solutions

After the CTF, I found out on the Discord channel two other way people solved this challenge. The first one, already mentioned, was to brute-force the seed.

Another one was proposed by SloppyJoePirate in a youtube video. He exploited a bug in the IAVL library used to validate the balance. Apparently, this bug recently led to a Binance Hack of almost $600M. This solution is very cool and completely different from mine; notice that the flag seems to suggest that this one was also the intended one.