Thursday, January 1, 2015

31c3ctf - Reversing - casino

Let's play a game!
nc 2000

Before attempting to read it, I used a couple sourcecode search engines to see if this was one of those little known languages like sleep (you know who you are are). Not finding any results, I assumed they built their own interpreter, and thus a new little known language was born.

The key to understanding languages is understanding grammar. If you constantly failed English class like myself, this may sound a bit intimidating. Luckily, I also constantly aced my Math classes, and we're talking about Math languages and Math grammar. Going into detail on this subject is outside the purpose of this write-up, so I'll suggest for people that are interested to review As a bonus, understanding grammars and building languages to parse input will allow you to build more secure code.

The first line looks like its including networking code.

The next chunk of code is reading from urandom a random number. Note that this number is only read once, and is reused repeatedly, so its possible to determine the random number. This is a design flaw.

The next chunk of code reads the flag. Its the flag, Horray flag!

The beginning of the next chunk initializes variable and prints the introductory greeting before entering a loop. Inside the loop appears to be a select-case format. Each time you make a bet, variable j is incremented, and if your bet is less than or equal to how much you have, checks your guess against a value using variable random and j.

Variable i isn't used except to be incremented, i is for ignore. Variable j is initialized with unknown or random value, but is incremented each time you bet. Variable k is the amount you can bet with, k for koins?

The second design flaw is that the code allows for a 0 value bet. True if you win, you gain nothing, but you also have nothing to lose, allowing you to learn a pattern with the relationship between variables j and random.

There is a bug (flaws are an error in design, bugs are an error in code) in the code that subtracts your bet from k. Given a large enough bet (any value over 9223372036854775807 as these are running on 64bit machines) causes an integer overflow making your large positive a negative number, and subtracting a negative number from your balance effectively increases you balance by the absolute value of the negative number, because basic math.

Adding 1 to the largest positive signed integer 9223372036854775807 and we get the following result

Huh? I clearly have enough money, why can't I get the flag? Oh that's right, signed integer overflow again. The problem is I have too much money, a problem I'm sure we're all familiar with. In order to give ourselves less money, we need to increase our bid by a much larger amount. This is do to the fact that negative numbers are stored in an two's compliment format. So we'll add another 900000000000000000 to our bid.

Congratulations, we got the flag by exploiting a bug, but we did identify two design flaws. How about we try for the flag again using them and ignoring the bug just in case some white-hat reports the bug and it gets fixed.

Here is an example of the second bug. We're able to gleam information for free. After some observations I'm able to determine that the number appears to always between 1 to 199 inclusive. This would mean some modulation is in effect, but not clearly represented in the code.

If theres modulation, and we have one constant, and another number incrementing, it sounds a bit to me like a Galois field, which I learn from watching this wonderfully mathy video (Shmoocon 2012: New Cool Crypto). If this is true, then variable random is our generator (g), and its being raised to the exponent in variable j. So we could figure out random...or we could just wait for the numbers to repeat, and use the previous numbers as answers. I love math, but I'm also lazy...

Here we have confirmation of the numbers repeating. Having done this a few times, the numbers repeat again after 125 bets, supporting the hypothesis that this is a Galois field. I'll leave figuring out variable random to the reader as again, I'm lazy.

We're on a roll now!

And....the same flag. They could have easily made two challenges from this by having one with the bug fixed, and the other with a flaw fixed.

Some observations of the EY language.

== is used to initialize a right-side variable with a left-side value. Lines 17 & 23 are a prime example of this. On line 17, variable i is being initialized with 0. Line 23, variable k is initialized with 10.

Lines 22 and 24 are a bit more mysterious. I presume these values are being initialized from <stdin>, as line 24 directly deals with user input. If this is true, then its possible the challenge is feeding line 22 a random number via <stdin> at launch, but we were never able to determine what value(s) were used to initialize line 22.

= is a mathematical assignment, assigning the right-side variable with the value of the left side expression. The best example is line 33, where k is assigned k-bet, as I'll explain soon.

and, sub, mul are mathematical operators taking the previous two values and performing an operation (add, subtract, and multiplication respectively) on the first value with the second value. Now, other than sub, we're not able to prove what add and mul do. The add operator could easily multiply and the mul operator could add or divide,

* could be an exponential or modulo operator, as there's already a mul operator. Again, we're unable to prove either with the limited information we have.

Many other operators fit this pattern of following two operands, such as regex, le, and eq.

_ is a denotes the operation left of it has precedence. Think of it as a final ), with an implied ( at the beginning of the line. Line 21 doesn't need it, but line 34 does.

No comments:

Post a Comment