Racer (crypto 300)

Category: Crypto Points: 300 Solves: 7/419

Join the race and make a round. Don’t forget to view the winner animation!

Hint: Just distinguish it from random data.

Another hint: Accuracy not good enough? Get more pills!

Yet another hint: Get the binary.

Still not solved … get the source code


TL/DR For the english readers : The whole challenge consisted in making the difference between random data and data that has been generated via a RC4 stream cipher with a random key. Hopefully RC4 have some biases (paper) . One of them is the probability the 2nd byte of the stream have, to be 0x00. With that in mind we could sometime make the previous distinction and with a bit a scripting and time get the flag 🙂


Pour les lecteurs de français :

Pour le contexte :

Racer était un service web où l’on nous présentait une voiture sur un circuit automobile. Le but était de faire un tour entier du circuit. Pour cela 2 options s’offraient à nous, soit prendre une pilule rouge, soit en prendre une bleu. Une d’entre elles nous faisait avancer d’une fraction de circuit, l’autre faisait exploser la voiture et nous ramenait au départ…

Une troisième option était d' »examiner les pilules ». Cela consistait en le téléchargement d’une archive contenant 2048 fichiers avec des noms de molécules, formés de 16 bytes à priori aléatoires. A chaque téléchargement l’archive changeait.

Notons aussi que à chaque run, nous obtenions une nouvelle « license » dans l’url, basiquement un id de session pour le service. Cet id était réinitialisé à chaque fois que l’on se trompait de pilule, mais pas quand on demandait à les « examiner ».

Voilà pour le contexte, peut être un peu trop perché 🙂

Ce que ça cachait vraiment :

Cette épreuve n’a visiblement inspiré aucune équipe dans un premier temps. Les organisateurs ont fini par donner des indices, puis le binaire et enfin les sources du service avant qu’une première validation ne soit faite.

On était en réalité devant un service écrit en Go. Les source nous apprennent qu’il fallait trouver 40 fois de suite la bonne pilule avant d’obtenir le flag et que le choix de la bonne pilule est fait côté serveur en partant d’un nombre aléatoire. On apprend aussi qu’on avait en tout 15 min pour réussir l’épreuve avant que notre id périme.

La partie intéressante résidait dans le handler pour « examiner » les pilules :

func handleExaminePill(w http.ResponseWriter, r *http.Request) {
    s := getState(r.FormValue("driver_license"))
    if s == nil {
        w.Header().Set("Content-Type", "text/plain")
        w.WriteHeader(http.StatusForbidden)
        fmt.Fprintln(w, "Your driver license expired. Try again.")
        return
    }
    var fn func([]byte)
    if s.GetColor() == "red" {
        fn = fillRc4
    } else {
        fn = fillRandom
    }
    w.Header().Set("Content-Type", "application/x-gtar")
    buildArchive(w, fn)
}

En résumé, si la bonne pilule était la rouge, on appelait buildArchive avec la fonction fillRc4, sinon on utilisait la fonction fillRandom, toutes deux définies par :

func fillRc4(data []byte) {
    for i := 0; i < len(data); i++ {
        data[i] = 0
    }
    key := make([]byte, 16)
    if _, err := io.ReadFull(rand.Reader, key); err != nil {
        log.Fatal("Oh no! Out of randomness for RC4 key")
    }
    c, _ := rc4.NewCipher(key)
    c.XORKeyStream(data, data)
    c.Reset()
}

func fillRandom(data []byte) {
    if _, err := io.ReadFull(rand.Reader, data); err != nil {
        log.Fatal("Oh no! Out of randomness for real random")
    }
}

Bref, si le bon choix était la pilule rouge, les fichiers étaient remplis avec des bytes sortis d’un flot RC4 initialisé avec une clef aléatoire, sinon dans le cas de la pilule bleue on utilisait crypto/rand qui elle dérive de /dev/urandom .

Le problème de trouver la bonne pilule se réduit donc à différentier des données issues de RC4, à des données aléatoires. Heureusement RC4 a quelques biais statistiques ( papier ). L’un d’entre eux concerne la probabilité qu’a le 2nd byte du flot à être nul.

Dans un cas parfaitement aléatoire, la probabilité d’avoir un byte à 0x00 est de 1 / 256. Dans le cas de RC4 pour le 2nd byte, elle se rapproche de 1/128.

Donc dans notre échantillons de 2048 fichiers, il suffit de compter le nombre de bytes nuls en 2nde position et de faire des statistiques : Dans le cas aléatoire on devrait en avoir en moyenne 8, dans le cas de RC4, 16.

Pour un lot donné, il est impossible d’être certain de la fonction qui a généré les données, mais on peut au dessus/dessous de certains seuils avoir une idée assez juste.

Par l’expérience, on a considéré qu’au dessus de 16 bytes nuls à la position 2, les données étaient issues de RC4 et donc que le bon choix était la pilule rouge et que en dessous de 8 elles avaient été générées aléatoirement et qu’il fallait choisir la bleu. Dans tous les autres cas, il suffit de redemander une nouvelle archive et de revérifier.

Voici notre exploit’  (moche):

#!/bin/zsh

STAGE=0

# 1) Get a race and a licence
LICENSE=$(wget -q -O- http://racer.hackover.h4q.it:8202/race | grep "license\":" | cut -d'"' -f 4)

for i in {0..10000}; do
    mkdir try$i
    cd try$i 

    # 2) Get the pill archive for this stage and extract it
    wget -qO- "http://racer.hackover.h4q.it:8202/pills.tar.gz?driver_license=$LICENSE"
    tar xf pills.tar.gz

    # 3) Select and concat all the 2nd byte of each pill file
    for file in $(ls 4R-*); do head -c 2 $file | tail -c 1 >> data; done

    # 4) Count all the null bytes
    COUNT=$(xxd -p -c 1 data | grep "00" | wc -l) #Yay it's a bit ugly but if you have a better solution I'm interested

    # 5) With pure random we should get 8 pills on average, with the RC4 bias, 16 on average
    # Over a certain threshold found by experience, consider the pills created via RC4...
    if [[ $COUNT -ge 17 ]]; then
        wget -qO- "http://racer.hackover.h4q.it:8202/take?driver_license=$LICENSE&color=red"
        STAGE=$(($STAGE+1))
        echo "STAGE : $STAGE"
    # ... And below a certain one, consider them created randomly
    elif [[ $COUNT -le 7 ]]; then
        wget -qO- "http://racer.hackover.h4q.it:8202/take?driver_license=$LICENSE&color=blue"
        STAGE=$(($STAGE+1))
        echo "STAGE : $STAGE"
    # Inbetween, we can not be that sure, just get a new batch of pill from the same stage
    else
        echo 'RETRY'
    fi
    
    cd ..
done

Et on obtient

{"action":"flag","text":"Winner!\u003cbr\u003ehackover15{yepRC4isTOTALLYbr0ken}"}

Merci à Mastho pour son aide sur les biais de RC4 !
Merci aux organisateurs pour le CTF !

JohnCool

Leave a Comment

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *