## 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.  

Original writeup (https://r98inver.github.io/posts/casino2/).## 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.  

Original writeup (https://r98inver.github.io/posts/casino2/).