TetCTF - Casino 2

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

\[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 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.