Hubert Hackin''

Can we be dumb here? | Crypto Math | Nsec24

In Mitosis System, we were presented with a lottery game in which we choose a combination of 6 numbers and then, we lose. If we do the contrary often enough and consecutively, we end up getting a flag by reaching 5000 points (a few is being given on every win).

Sideni joue

That sounds fun, but how does it work? When we send a request, we see our combination in this JSON object.

{"ticket:":[
    {"numbers":[1,2,3,4,5,6]}
]}

Short story, I once bought this exact lottery ticket and my mother told me: “Why would you do this, you’ll never win…”

And out of no where, do you know what happened?

…

I didn’t win…

Sideni joue au sudoku

Have you seen the interesting bit where our ticket is a list of combinations (called “numbers” here)?

Let’s look at the code real quick to see how it’s handled.

from flask import Flask, render_template, redirect, request, session
from flask_session import Session
import random, json

app = Flask(__name__)
app.config["SESSION_PERMANENT"] = False
app.config["SESSION_TYPE"] = "filesystem"
app.secret_key = 'changeme' #this is not the value in production 
Session(app)

@app.route("/")
def main_page():
    if (session):
        return render_template('index.html')
    else:
        session['tries'] = 0
        return redirect('/')


@app.route('/loto2', methods=['POST'])
def loto():
    data = request.get_json()
    x = random.sample(range(1,59),6)
    x.sort()
    points = 0
    for numbers in range(0, len(data['ticket:'])):
        ln = data['ticket:'][numbers]
        zz = validateNum(x,ln['numbers'])
        if zz > 0:
            points = points + zz
    if session['tries'] > 5000:
        return 'A flag goes here' # This is not the value in production
    if points > 0:
        session['tries'] = session['tries'] + points
        return 'Success. Adding ' + str(points) + ' to your score. You currently are at ' + str(session['tries']) + ' out of 5000'
    else:
        session['tries'] = 0
        return 'Failure, expected ' + str(x) + '. Resetting to ' + str(session['tries']) + ' out of 5000'


def validateNum(x,num):
    if (len(num) != len(x)):
        raise Exception('Invalid Number Lenght')
    num_v = 0
    for i in range(0,len(x)):
            if x[i] in num:
                num_v = num_v + 1
    if num_v == 2:
        return 1
    if num_v == 3:
        return 2
    if num_v == 4:
        return 4
    if num_v == 5:
        return 8
    if num_v == 6:
        return 16
    else:
        return 0

Our intuition about the ticket list was correct! With the loop for numbers in range(0, len(data['ticket:'])):, we iterate through all combinations we’ve sent. We can send many combinations for each attempt!

Sideni joue aussi au tennis

The validateNum function returns a gain in points if we have at least 2 numbers present in the winning combination. It does so for each combination we’ve sent. All we need is to have at least one combination that scores points and we’ll be saved from having our score reset.

Sideni joue au hockey

We need a PoC and it seems pretty easy to craft. To be sure that one of our combinations has at least 2 numbers of the winning combination, we can just send all possible pairs of numbers between 1 and 58 (and random numbers for the other numbers, they don’t matter).

Basically, we’ll send something like this:

{"ticket:":[
    {"numbers":[1,2,58,58,58,58]},
    {"numbers":[1,3,58,58,58,58]},
    {"numbers":[1,4,58,58,58,58]},
    {"numbers":[1,5,58,58,58,58]},
    ...
    {"numbers":[2,3,58,58,58,58]},
    {"numbers":[2,4,58,58,58,58]},
    {"numbers":[2,5,58,58,58,58]},
    ...
    {"numbers":[55,56,58,58,58,58]},
    {"numbers":[55,57,58,58,58,58]},
    {"numbers":[55,58,58,58,58,58]},
    ...
]}

Woops… Internal server error (or some other error, I don’t have the infrastructure available anymore). What could it be?

Mais, Sideni joue aussi au jeu

My conscience: Am I blind? Let’s try again with only one combination!

My conscience: Ok, that looks good, let’s try 10 combinations?

My conscience: Good, again! What about 29?

My conscience: Nope, we can send 28 combinations maximum!

My conscience: Awwww…

My conscience: Do I really need to understand what I’m doing now?

Let’s bring back probability theory from the old days to prove ourself that this is doable.

With nCk = C(n, k) = n! / k! * (n - k)! where n = 58 and k = 6, we have 40 475 358 unique combinations without repetition.

For info, this is the equation to calculate the number of unique combinations without repetition.

Then, according to my good friend, we can use C(k, B) * C(n - k, k - B) / C(n, k) where n is the number of possible values (58), k is the number of values in a combination (6) and B is the number of matching values to have a winning combination.

A winning combination needs at least 2 values present in the drawn combination. This means that B can be either 2, 3, 4, 5 or 6.

For B = 2, C(6, 2) * C(58 - 6, 6 - 2) / C(58, 6) = 0.10032956348403392

For B = 3, C(6, 3) * C(58 - 6, 6 - 3) / C(58, 6) = 0.01092022459690165

For B = 4, C(6, 4) * C(58 - 6, 6 - 4) / C(58, 6) = 0.0004914101068605743

For B = 5, C(6, 5) * C(58 - 6, 6 - 5) / C(58, 6) = 7.708393833107048e-06

For B = 6, C(6, 6) * C(58 - 6, 6 - 6) / C(58, 6) = 2.4706390490727716e-08

Because these probabilities are each the individual probability of having a B values winning combination, we need to add them all together to get the probability of a single win (whatever the number of values in the drawn combination).

This would be 0.11174893128801973 = 11,174893128801973% to win some points once by playing only one combination.

Disclaimer, don’t quote me on this. If you lose the lottery, it’s on you. I can be quite dumb as you’ll see if you keep reading…

You could also have used a hypergeometric distribution calculator to arrive to the same result.

But for the flag we need 5000 points without ever loosing. So an astonishing flag probability of 0.11174893128801973^5000 = 1.6477534206169263e-4759 if we play a single combination each time.

What matters is that we can now (try and fail to) calculate the probability of winning some points with 28 combinations.

It’s easy, you take that 11% probability and we multiply it by the number of combinations (28).

Me: Bear with me, if we take only two tickets in the lottery, we should double our chances of winning, right?

Jean: And you lose twice as much.

Me: Now, what if we get three tickets?

Jean: You lose three times?

Me: Ah ha! We triple our chances!

At this point we each were talking without really listening to each other

Jean: A tiny amount gained, but so much loss…

Me: With 4 tickets, we should quadruple!

Jean: We’re losing soooo much money…

Me: Let’s get 28 tickets and twenty-eigth-uple our chances!

Jean: We’re sure to lose a lot… and for what??

Me: We have 312,89700760645522% chances to win with 28 combinations!

Jean: Isn’t a probability from 0 to 1?

Me: ¯\(ツ)/¯

Jean: …

Me: Now, how do we get me these 28 combinations?

Jean: …

Me: …

Au début, Sideni jouait une seule combinaison

At this point in the challenge, I’m starting to believe the lottery knows the game more than I do. So, I let it be my guide!

How do I do this, you ask? Well you see, the values randomly chosen by the lottery are supposedly distributed evenly (or at least, in its own distribution). What if I let the lottery decide which combinations I’m going to play myself? :)

This is what I did!

import requests
from math import ceil, floor

out = []
l = list(range(1,59))
n = ceil(len(l) / 6)

session = requests.Session()

data = {"ticket:":[
{"numbers":[1,11,21,31,41,51]}
]}
cookies = {"session":"rErYpIUJirYPtVogkSQKRY0Qkv96s-ODweDp0UZGKoo"}

while True:
    response = session.post("http://rna-evolve.ctf:5000/loto2", json=data, cookies=cookies)
    txt = response.text
    print(len(data['ticket:']))
    if 'Failure, expected ' in txt and len(data['ticket:']) < 28:
        i = txt.find('Failure, expected ')
        combination = txt[i + len('Failure, expected '):txt.find('.')]
        combination = eval(combination)
        is_already_there_too_much = False
        for i_comb in combination:
            combs = data['ticket:']
            if sum(comb['numbers'].count(i_comb) for comb in combs) > n:
                is_already_there_too_much = True
                break

        if not is_already_there_too_much:
            data['ticket:'].append({'numbers': combination})
            print('Added :')
            print(combination)

    if 'You currently are at' in txt or 'Resetting to' in txt:
        i = txt.find('You currently are at ')
        print(txt[i + len('You currently are at '):])

        continue
    else:
        print(txt)
        break

Let me help you understand this impressive solution; this is CTF code after all! I start with a single combination and loop for eternity. Every time I see that I don’t have 2 numbers inside the winning combination, I add this combination to my ticket list up until I have a full list of 28 combinations! By running this over time, we can see that we hit 3000 points from time to time!

For now, we just wait for the machine to pay out. I can feel it, it’s gonna pay!

Sideni s’est toutefois mis à jouer son avenir…

While the previous code was running, why not read through the Internet? According to my search history, I’ve been possessed by some omnipotent being whom used a highly intellectual jargon that I have no recollection of.

Let’s list a few of these searches while I was unresponsive:

how to choose many combinations for multi prize lottery
how to choose multiple combinations to win small prizes lottery
limiting covariance matrix for random sampling

And at some point, that entity which had a reverse shell into my head searched the following: build set of combinations for guaranteed prize lottery

I don’t know what happened to this all mighty being, but his connection to my head must have dropped as I was left alone with this search result, an interestingly looking GitHub repo.

Un jour, Sideni a même joué un club maté…

In that repo, we see that a paper called You need 27 tickets to guarantee a win on the UK national lottery is referenced. So, I did what everyone on my team would do; I did not read it…

Instead, I went into the demonstration available in the repo and saw a list of tickets!

((1, 2, 3, 4, 5, 6),(1, 2, 3, 4, 7, 8),
(1, 2, 5, 6, 7, 8),(9, 10, 11, 12, 13, 14),
(9, 10, 11, 15, 16, 17),(12, 13, 14, 15, 16, 17),
(18, 19, 20, 21, 26, 27),(18, 19, 22, 23, 30, 31),
(18, 19, 24, 25, 28, 29),(20, 21, 22, 23, 28, 29),
(20, 21, 24, 25, 30, 31),(22, 23, 24, 25, 26, 27),
(26, 27, 28, 29, 30, 31),(32, 33, 34, 35, 40, 41),
(32, 33, 36, 37, 44, 45),(32, 33, 38, 39, 42, 43),
(34, 35, 36, 37, 42, 43),(34, 35, 38, 39, 44, 45),
(36, 37, 38, 39, 40, 41),(40, 41, 42, 43, 44, 45),
(46, 47, 48, 49, 54, 55),(46, 47, 50, 51, 58, 59),
(46, 47, 52, 53, 56, 57),(48, 49, 50, 51, 56, 57),
(48, 49, 52, 53, 58, 59),(50, 51, 52, 53, 54, 55),
(54, 55, 56, 57, 58, 59))

There’s just one issue. The UK national lottery have values from 1 to 59 instead of 1 to 58…

What if I take these three:

(46, 47, 50, 51, 58, 59),
(48, 49, 52, 53, 58, 59),
(54, 55, 56, 57, 58, 59)

And that I shift everything that doesn’t look good inside the valid range like this:

(46, 47, 50, 51, 57, 58),
(48, 49, 52, 53, 57, 58),
(53, 54, 55, 56, 57, 58)

Sure enough, being dumb in the proper way paid off once again and I managed to get to 5000 points in one attempt!

I guess I should now read that paper…

NSEC24 Mitosis System - Fri, Jun 28, 2024 - Sideni Jean Privat