Write-Ups

FCSC 2022 – Write-Ups for some of the crypto challenges

In this post, I’ll present my write-ups for some of the challenges listed in the “Crypto” category, in no particular order. Three of them are not directly written in this post and only contain a link to the actual write-up.

The challenges are:

  1. Shuffled
  2. My Tailor is Rich
  3. T-Rex
  4. Gaston La Paffe
  5. Surface
  6. Hash-ish
  7. Kahl Hash
  8. Share It
  9. IZNOGOOD
  10. Millenium

I didn’t manage to solve two of them, but I will briefly give my thoughts on them.

Shuffled

Difficulty : ⭐
Points : 100
Solves : 490

Description

Oops, nous avons mélangé les caractères du flag. Pourrez-vous les remettre dans l'ordre ?

The following source code was provided :

import random

flag = list(open("flag.txt", "rb").read().strip())
random.seed(random.randint(0, 256))
random.shuffle(flag)
print(bytes(flag).decode())
# f668cf029d2dc4234394e3f7a8S9f15f626Cc257Ce64}2dcd93323933d2{F1a1cd29db

Resolution

This one doesn’t need much explanations.

Basically, we can test all 256 seed values and shuffle an ordered list from 0 to x, with x being the length of the flag.

This will produce a shuffled list, whose elements represent the original index of the flag. We can reconstruct the real flag from this list.

If the guessed seed was correct, the flag should start with “FCSC{“.

The full script is given below :

import random

flag = list(open("output.txt", "rb").read().strip())
for i in range(256):
    a = list(range(len(flag)))
    random.seed(i)
    random.shuffle(a)
    # build a dict with shuffled indexes
    f = {}
    for j, e in enumerate(a):
        f[e] = flag[j]
    # unshuffle flag
    m = []
    for j in range(len(flag)):
        m.append(f[j])
    f = bytes(m).decode()
    if f.startswith('FCSC'):
        print(f)

FCSC{d93d32485aec7dc7622f13cd93b922363911c36d2ffd4f829f4e3264d0ac6952}

My Tailor is Rich

Difficulty : ⭐
Points : 224
Solves : 134

Description

Vos collègues experts en reverse engineering ont reconstitué un algorithme d'encodage de mots de passe d'un certain équipement. Ils se doutent qu'il est cryptographiquement faible mais ils font appel à vos services pour le démontrer.

nc challenges.france-cybersecurity-challenge.fr 2100

The source code of the service was provided :

import string
import random

N = 8

def encode(pwd):
    def F(tmp):
        if tmp % 2:
            return (tmp % 26) + ord('A')
        else:
            r = tmp % 16
            if r < 10:
                return ord('0') + r
            else:
                return r - 10 + ord('A')

    a, res = 0, []
    for i in range(len(pwd)):
        P, c, S = pwd[:i], pwd[i], pwd[i+1:]
        S1, S2, T = sum(P), sum(S), sum(pwd)
        a = F((a + c) * i + T)
        res.append(a)

    return bytes(res)

def get_random_string(length):
    return ''.join(random.choice(string.ascii_letters) for _ in range(length)).encode()

pwd = get_random_string(8)
enc = encode(pwd)

print(f'Can you find {N} different passwords that encode to "{enc.decode()}"?')

P = []
S = [enc]
try:
    for _ in range(N):
        p = input(">>> ").encode()
        if not p.isascii():
            print("Please enter only ASCII strings.")
            exit(1)
        P.append(p)
        S.append(encode(p))

    if len(set(P)) == N and len(set(S)) == 1:
        print("Congrats!! Here is your flag:")
        print(open("flag.txt").read())
    else:
        print("Nope!")
except:
    pass

Resolution

The challenge description indicates that this encoding algorithm has been recovered from some kind of equipment.

I don’t know if this particular encoding was used in the real world or not, but it doesn’t really matter for the resolution.

All characters of the encoded password are entirely dependent on the previous character. The first one is the function F applied to the sum of the ASCII values of the password.

Starting from the first character, we can progressively recover lists of valid password characters for each positions :

def getValid(t, prev, res):
    m1 = []
    # search candidates satisfying the relation
    for i in (string.ascii_letters + string.digits).encode():
        x = (res[prev] + i) * (prev+1) + t
        if F(x) == res[prev+1]:
            m1.append(i)
    # limit to 3 results as it's enough
    return m1[:3]

The above function needs a possibility for the sum of the password characters t. We can build a dictionary mapping the values x to F(x) and use that to find some potential sum values :

DEC = {}

for i in range(1024):
    if DEC.get(F(i)):
        DEC[F(i)].append(i)
    else:
        DEC[F(i)] = [i]

After having gathered 7 lists of potential password characters for each position, the last step is to find all the last ones, that with any combination of the potential password characters, will produces the expected sum :

def solve(res):
    Ts = DEC[res[0]]
    pwd = []
    for t in Ts:
        m1 = getValid(t, 0, res)
        m2 = getValid(t, 1, res)
        m3 = getValid(t, 2, res)
        m4 = getValid(t, 3, res)
        m5 = getValid(t, 4, res)
        m6 = getValid(t, 5, res)
        m7 = getValid(t, 6, res)

        for i in (string.ascii_letters + string.digits).encode():
            for r in itertools.product(m1, m2, m3, m4, m5, m6, m7):
                if sum(r) + i == t:
                    pwd.append([i]+list(r))
    return pwd

This quickly produces several dozens of passwords encoding to the same result.

The full solve script is given below :

import string
import itertools
from pwn import remote

def F(tmp):
    if tmp % 2:
        return (tmp % 26) + ord('A')
    else:
        r = tmp % 16
        if r < 10:
            return ord('0') + r
        else:
            return r - 10 + ord('A')

def getValid(t, prev, res):
    m1 = []
    # search candidates satisfying the relation
    for i in (string.ascii_letters + string.digits).encode():
        x = (res[prev] + i) * (prev+1) + t
        if F(x) == res[prev+1]:
            m1.append(i)
    # limit to 3 results as it's enough
    return m1[:3]

def solve(res):
    Ts = DEC[res[0]]
    pwd = []
    for t in Ts:
        m1 = getValid(t, 0, res)
        m2 = getValid(t, 1, res)
        m3 = getValid(t, 2, res)
        m4 = getValid(t, 3, res)
        m5 = getValid(t, 4, res)
        m6 = getValid(t, 5, res)
        m7 = getValid(t, 6, res)

        for i in (string.ascii_letters + string.digits).encode():
            for r in itertools.product(m1, m2, m3, m4, m5, m6, m7):
                if sum(r) + i == t:
                    pwd.append([i]+list(r))
    return pwd

DEC = {}

for i in range(1024):
    if DEC.get(F(i)):
        DEC[F(i)].append(i)
    else:
        DEC[F(i)] = [i]

conn = remote("challenges.france-cybersecurity-challenge.fr", 2100)
conn.recvuntil(b'to "')
expected = conn.recvuntil(b'"', drop=True)
conn.recvline()

for e in solve(expected)[:8]:
    e = bytes(e)
    conn.sendline(e)
conn.recvuntil(b"flag")
conn.recvline()
print(conn.recvline())
conn.close()

FCSC{515dd8416571401f2f0bf039e9adeec0cb9c51f4430923baa9fcb3fa13e14091}

T-Rex

You can find my write-up for this challenge on my company’s blog here (fr/en).

Gaston La Paffe

You can find my write-up for this challenge on my company’s blog here (fr/en).

Surface

You can find my write-up for this challenge on my company’s blog here (fr/en).

Hash-ish

Difficulty : ⭐⭐
Points : 336
Solves : 71

Description

Savez-vous comment fonctionne la fonction hash de Python ?

nc challenges.france-cybersecurity-challenge.fr 2103

The following source code was provided :

#!/usr/bin/env python3.9
import os

try:
	flag = open("flag.txt", "rb").read()
	assert len(flag) == 70

	flag = tuple(os.urandom(16) + flag)

	challenge = hash(flag)
	print(f"{challenge = }")

	a = int(input(">>> "))
	b = int(input(">>> "))

	if hash((a, b)) == challenge:
		print(flag)
	else:
		print("Try harder :-)")
except:
	print("Error: please check your input")

Resolution

This challenge was quite interesting as it consisted in finding a 2nd preimage for the Python hash function.

I hope everybody knows that this function is not cryptographically secure, but I never wondered if collisions are easy to produce.

The Python hash function behaves differently depending on the type of the object it is applied on :

>>> hash(1337)
1337
>>> hash((1337,))
1536106969631255485
>>> hash("1337")
-1803454164760456366
>>> hash(b"1337")
-1803454164760456366

For numbers it simply returns them modulo P = 2305843009213693951.

For tuples, which is the case in the challenge, it’s not that simple.

The source code of the hash function applied to tuples can be found here (Python 3.9).

Rewritten in Python, this gives :

def tupleHash(t):
	acc = 2870177450012600261
	for i in t:
		acc += hash(i) * 14029467366897019727
		acc %= 2**64
		acc = ((acc << 31) | (acc >> 33))
		acc %= (2 ** 64)
		acc *= 11400714785074694791
		acc %= (2 ** 64)
	acc += len(t) ^ 2870177450012600261 ^ 3527539
	acc %= (2 ** 64)
	return acc

The only difference here is that the hash function returns signed integers, but this has no impact on the resolution :

>>> tupleHash((1337, 88, 9))
11207200829502916047
>>> hash((1337, 88, 9)) % 2**64
11207200829502916047
>>> hash((1337, 88, 9))
-7239543244206635569

The goal of the challenge is to find a tuple containing 2 integers (x, y), whose hash will produce the expected hash. In other words, we must find a 2nd preimage for this hash function.

Now that we have rewritten the function in Python, we can easily access the internal state. For example we could compute the internal state of the hash after having processed the first element :

def forwardHash(i):
	# returns the internal state after having hashed 1 tuple element
	acc = 2870177450012600261
	acc += i * 14029467366897019727
	acc %= 2**64
	acc = ((acc << 31) | (acc >> 33))
	acc %= (2 ** 64)
	acc *= 11400714785074694791
	acc %= (2 ** 64)
	return acc

Knowing the internal state after the first step allows us to calculate the second tuple element that will produce the expected hash. This can be done by inverting the last hashing step, starting with the expected value. The inversion is possible because only additions, multiplications and rotations are used :

def reverseHash(expected, state):
	# inverts the hashing process starting from an expected hash
	# returns the second tuple element that will produce this hash
	# based on the fact that the first element produced a given internal state
	acc = expected
	# only 2 elements
	acc -= 2 ^ 2870177450012600261 ^ 3527539
	acc %= (2 ** 64)
	acc *= 614540362697595703
	acc %= (2 ** 64)
	acc = (acc & 0x7fffffff) << 33 | (acc >> 31)
	acc %= 2 ** 64
	acc -= state
	acc % (2 ** 64)
	acc *= 839798700976720815
	return acc % (2 ** 64)

The strategy is simple. Choose an arbitrary small (<P) value as the first tuple element, compute the internal state and use it to compute the second element.

The only problem is that the second element y will likely be larger than P and as such hash(y) \neq y. In that case, we have to choose another value for x.

Finding a preimage was not too difficult in this scenario.

The full attack is implemented below :

#!/usr/bin/env python3.9

def forwardHash(i):
	# returns the internal state after having hashed 1 tuple element
	acc = 2870177450012600261
	acc += i * 14029467366897019727
	acc %= 2**64
	acc = ((acc << 31) | (acc >> 33))
	acc %= (2 ** 64)
	acc *= 11400714785074694791
	acc %= (2 ** 64)
	return acc

def reverseHash(expected, state):
	# inverts the hashing process starting from an expected hash
	# returns the second tuple element that will produce this hash
	# based on the fact that the first element produced a given internal state
	acc = expected
	# only 2 elements
	acc -= 2 ^ 2870177450012600261 ^ 3527539
	acc %= (2 ** 64)
	acc *= 614540362697595703
	acc %= (2 ** 64)
	acc = (acc & 0x7fffffff) << 33 | (acc >> 31)
	acc %= 2 ** 64
	acc -= state
	acc % (2 ** 64)
	acc *= 839798700976720815
	return acc % (2 ** 64)

def findCollision(expected):
	P = 2305843009213693951
	second = P + 1
	first = 0
	# the 2nd element must be < P otherwise hash(element) != element
	while second >= P:
		first += 1
		second = reverseHash(expected, forwardHash(first))
	return (first, second)


from pwn import *
import ast

conn = remote("challenges.france-cybersecurity-challenge.fr", 2103)
conn.recvuntil(b"challenge = ")
challenge = int(conn.recvline().strip())
t = findCollision(challenge)
conn.sendline(str(t[0]).encode())
conn.sendline(str(t[1]).encode())
conn.recvuntil(b"(")
flag = b'('+conn.recvline().strip()
flag = ast.literal_eval(flag.decode())
print(bytes(flag[16:]))
conn.close()

FCSC{658232b18ebebc53c42dd373c6e9bc788f1fd5693cf8a45bcafbff46dae42e24}

Kahl Hash

Difficulty : ⭐⭐⭐
Points : 477
Solves : 10

Description

Savez-vous réellement comment fonctionne la fonction hash de Python ?

nc challenges.france-cybersecurity-challenge.fr 2104

The following source code was provided :

#!/usr/bin/env python3.9
try:
	flag = tuple(open("flag.txt", "rb").read())
	assert len(flag) == 70

	challenge = hash(flag)
	print(f"{challenge = }")

	T = tuple(input(">>> ").encode("ascii"))
	if bytes(T).isascii() and hash(T) == challenge:
		print(flag)
	else:
		print("Try harder :-)")
except:
	print("Error: please check your input")

Resolution

This challenge looks suspiciously similar to the previous one but was labeled as harder.

The difference here is that we are working with a tuple of ASCII characters (integers < 128).

During my research for the previous challenge, I found this blog post explaining how to generate collisions for an older version of Python’s hash function using a Meet-in-the-Middle attack.

The idea is as follows:

  • Choose a size s for the candidate tuple T. There is no restriction in the challenge, so it can be anything, but should be sufficiently large so there are more than enough potential candidates.
  • For any combination of the last n elements, recover the internal state that should be produced after having hashed the s-n first elements, so the final hash is the expected one. Maintain a list of all those internal states.
  • For a combination of the first s-n elements, compute the internal state that will be produced after hashing them. If it is contained in the previous list, a valid tuple T has been found, otherwise try a new combination.

There are 128 possibilities for each element, so I decided to use n=4 which required storing a table of 128^4=2^{28} elements. I also chose s=16 to give me more flexibility. If you chose s too small and find no candidate T, you’ll have to recompute the first table, as s is involved during the state inversion process.

This attack is more efficient than trying to plainly guess a valid tuple T, instead of having a probability of 2^{-64} of finding a valid T, you now have a probability of 2^{-64+28}=2^{-36}. By spending more ressources on memory, you gain execution time.

I initially thought of implementing this attack in Python, because I could just reuse (after a little adaptation) the code I wrote for the last challenge. But it’s obviously not a good idea, because it would just never find a solution in time.

I wrote it in C.

Here is the abomination :

// gcc -O2 main.c
#include <stdio.h>

unsigned long long rev(const unsigned char * const last) {
    /*
    inverts the hashing process starting from the expected hash given the 4 last elements.
    returns the necessary internal state to produce this hash.
    */
    // expected hash
    unsigned long long acc = 2077196538114990005ULL;
    // hardcoded size : 16
    acc -= 16 ^ 2870177450012600261ULL ^ 3527539;
    // revert for 4 elements
    for (int i=3; i>=0; --i) {
        acc *= 614540362697595703ULL;
        acc = (acc & 0x7fffffff) << 33 | (acc >> 31);
        acc -= last[i] * 14029467366897019727ULL;
    }
    return acc;
}

unsigned long long thash(const unsigned char * const last) {
    // returns the internal state after having hashed 12 tuple element
    unsigned long long acc = 2870177450012600261ULL;
    for (int i=0; i<12; ++i) {
        acc += last[i] * 14029467366897019727ULL;
        acc = ((acc << 31) | (acc >> 33));
        acc *= 11400714785074694791ULL;
    }
    return acc;
}

#define N 268435456ULL // 2**28
unsigned long long TABLE[N];

int main(void) {
    for (unsigned long long i=0; i<N; ++i) {TABLE[i] = 0;}

    unsigned char last[16];
    unsigned long long acc;

    // Build the table. Not very long
    printf("Step1...\n");

    for (unsigned char i=0; i<128; ++i) {
        last[0] = i;
        for (unsigned char j=0; j<128; ++j) {
            last[1] = j;
            for (unsigned char k=0; k<128; ++k) {
                last[2] = k;
                for (unsigned char l=0; l<128; ++l) {
                    last[3] = l;
                    acc = rev(last);
                    /*
                    uncomment the following line when a candidate was found, to print the last 4 elements
                    This is needed because I can't store the last 4 elements along the internal state.
                    Need to save space :(
                    */
                    //if (acc == 15893927934471181201ULL) {printf("found one : %02X%02X%02X%02X\n", last[0],last[1],last[2],last[3]);}

                    // shitty hashmap replacement
                    TABLE[acc % N] = (acc);
                }
            }
        }
    }

    // search for T

    printf("Step2...\n");
    // Because s=16, I will not BF 12 bytes. I fix some to a printable value.
    last[6] = 0x41;
    last[7] = 0x41;
    last[8] = 0x41;
    last[9] = 0x41;
    last[10] = 0x41;
    last[11] = 0x41;

    // starting values are adapted for demonstration purposes
    for (unsigned char i=2; i<3; ++i) {
        last[0] = i;
        for (unsigned char j=78; j<79; ++j) {
            last[1] = j;
            for (unsigned char k=80; k<81; ++k) {
                last[2] = k;
                for (unsigned char l=0; l<128; ++l) {
                    last[3] = l;
                    for (unsigned char a=0; a<128; ++a) {
                        last[4] = a;
                        for (unsigned char b=0; b<128; ++b) {
                            last[5] = b;
                            acc = thash(last);
                            // If this is true, we have found a potential candidate
                            if (TABLE[acc % N] == (acc)) {
                                printf("Potential candidate: %llu (%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X)\n", acc,last[0],last[1],last[2],last[3],last[4],last[5],last[6],last[7],last[8],last[9],last[10],last[11]);
                            }
                        }
                    }
                }
            }
        }
    }

    return 0;
}

In less then 3 hours, it found a potential candidate for T : (0x02, 0x4E, 0x50, 0x18, 0x10, 0x0C, 0x41, 0x41, 0x41, 0x41, 0x41, 0x41, 0x05, 0x33, 0x76, 0x4F)

Converting this to bytes, gives the following solution for the challenge : b'\x02NP\x18\x10\x0cAAAAAA\x053vO'

FCSC{1d43cd910e5775b80ca7a2c3935fc5c76b207d2bb44a596b474521d776b8e412}

Share It

Difficulty : ⭐⭐
Points : 482
Solves : 8

Description

Picsou est féru de chasses au trésor, et en organise régulièrement. En général, il enterre un vrai trésor quelque part et l'objectif des participants est d'en découvrir les coordonnées GPS via diverses énigmes à résoudre. Picsou avait partagé les coordonnées de sa chouette d'or avec quelques amis "de confiance" (qui ne sont évidemment pas censés participer à la chasse, sait-on jamais ce qui pourrait lui arriver ...). Mais son cupide neveu Donald a malheureusement volé l'objet et a disparu avec.

On n'y reprendra plus Picsou ! Ses autres passions étant les maths et la programmation, il a décidé d'implémenter l'outil share-it en optimisant le code sss.c d'une obscure bibliothèque cryptographique nommée libecc. Grâce à son outil, il partage son secret avec plusieurs personnes dont divers huissiers en imposant un quorum parmi les éléments partagés pour le révéler. Ainsi, il est sûr que si un minimum de personnes sont de confiance, son trésor restera sauf. De plus, afin d'obliger de potentielles associations malfaisantes à se révéler aux autres, il n'a pas communiqué le nombre minimum du quorum. Il n'a pas non plus révélé le nombre total de partages générés et donnés, mais des rumeurs parlent d'une soixantaine.

Le vil Donald a mis la main sur un élément partagé share_0.bin ainsi que sur le binaire share-it en les volant à un cousin peu attentif. Il est persuadé qu'il peut remonter seul aux coordonnées secrètes de la licorne d'or fraîchement enterrée par Picsou, et fait confiance à votre expertise en vous promettant la moitié de la récompense : saurez-vous l'aider ?

SHA256(share-it) = 624fb4a8bce80798d44790cd3a036a3cac74b78cc6f2e7f3e2c2a3d3d68a4f4d.
SHA256(share_0.bin) = ea95f60bf6ec19c96ce75bb1399f9cf164a881dbd671ea25457cc7239348a88c.

No source code was provided, only the binary and a single share.

Resolution

The binary is a stripped 64-bit ELF PIE executable.

The usage is printed when executing it with no options :

# ./share-it
./share-it usage:
        gen  k n <file name secret of at most 32 bytes>
        comb k

We can generate n shares and specify that only k of them are necessary to reveal the secret. For example with n=3, k=2 :

# ./share-it gen 2 3
[+] Generating 3 shares with quorum 2
secret (random): 54e1e402aa454170947e7600721f04e439256725bde149de08849a8ab24cafda

# ls
share-it  share_0.bin  share_1.bin  share_2.bin

# ./share-it comb 2
[+] Combining 2 shares
secret: 54e1e402aa454170947e7600721f04e439256725bde149de08849a8ab24cafda

Judging by the name of the created shares, we are in possession of the first one for the challenge. This will be important later.

In the description we are given the hint, that the code is based on this example from ANSSI’s libecc. This should greatly help identify the functions during the reverse engineering steps and will serve as a reference for pinpointing the modifications.

In IDA, in the main function, with the help of the printed strings, we can identify the 2 core functions :

  • sss_generate : sub_3CF0
  • sss_combine : sub_3E30

Only the first one is actually interesting in our case. If there has been modifications that would affect the security of the scheme, it was probably done in the generation process.

Now that we have identified a function, we can clone the libecc repository and compile the example program (using the same gcc version). Comparing the disassembled sss_generate function of the example (which isn’t stripped) with our version, allows us to identify even more function names, without too much trouble.

As you can see, the decompiled code is not perfectly identical, but is similar enough to identify functions (in this simple case). It was not that easy for the massive _sss_raw_generate function.

After a lot of renaming, structure definitions, type conversions and comparisons with the original source code, the decompiled code started to look like the example. This is what the final version of the sss_generate function looks like :

Using this methodology, I was able to reverse engineer enough of the generation process to find the differences.

The _sss_derive_seed function has been modified :

Instead of using the seed as a key for the HMAC computation, it uses a newly introduced 2-byte key (passed as a fourth argument) concatenated with the idx parameter, to form a 4-byte value.

This new key is sneakily generated inside the _sss_raw_generate function.

Rewritten in Python, the _sss_derive_seed function is as follows :

import hmac

P = 115792089237316195423570985008687907853269984665640564039457584007908834671663

def _sss_derive_seed(seed, idx, key):
    if idx == 0:
        return seed
    C = bytes([0, idx])
    h = hmac.new(key+C, C, "SHA512")
    h = int(h.hexdigest(), 16) % P
    return (seed*h) % P

We will see later how this will impact the security of the scheme.

The function _sss_derive_seed is used by the _sss_raw_generate function to compute the shares. This part of the code has not been modified and looks like this in Python :

def makeShare(seed, key, base, k):
    exp = 1
    a0 = _sss_derive_seed(seed, 0, key)
    for i in range(1, k):
        exp = fp_mul_monty(exp, base)
        a = _sss_derive_seed(seed, i, key)
        a0 += fp_mul_monty(a, exp)
    return a0

More formally : S_b = \sum_{i=0}^k a_ib^i with a_i = sH_i, H_0 = 1 and b the share’s index starting at a random 2-byte value, s the seed we need to recover, k the number of shares required for the quorum and H_i the result of the HMAC in the _sss_derive_seed function.

By factoring with the seed s, it can be rewritten as S_b = s(\sum_{i=0}^k H_ib^i) The only real unknown is s. S_b is our share, b is contained in the share (we have the share numbered 0, so it’s directly b), H_i is only partially unknown because it depends on a 2-byte key, which can be brute forced, and k can be guessed (<60 from the description). Recovering the seed is thus possible in a reasonable amount of time.

We however have no way to tell if our guesses for k and the HMAC key are correct, besides assuming the seed should respect the flag format.

The file format for the shares is not very complicated :

00000000: 62e2 b89a 285e 5505 b793 969e 235c 0166  b...(^U.....#\.f
00000010: 3279 7029 e7c4 bf17 7917 65ce fce7 3a27  2yp)....y.e...:'
00000020: 450d 5040 6a74 469f 9c58 a0e1 4d37 f026  E.P@jtF..X..M7.&
00000030: 2c95 ecf9 8a54 4a66 8eb3 9025 bae3 42c2  ,....TJf...%..B.
00000040: 5731 a0fd 34bd 1304 e8fc 9204 ccb8 7ad0  W1..4.........z.
00000050: bc6f 

The first two bytes represent the base b in big endian, to which was added the share number (0 in our case). The following bytes in bold are S_b in big endian too. The rest is not relevant for the challenge.

Before implementing the attack, I had rewritten the generation process in Python and wanted to assert it’s indeed doing the same thing as the challenge. The _sss_derive_seed function was OK, but the makeShare function did not work, which was very frustrating as I had a lot of difficulties understanding why. After several hours of debugging with the help of GDB, I finally found the culprit :

How much of a fool was I to even think a simple multiplication function would just return the result of the multiplication ? Take a look at the comments :

The first one makes you think it’s just a multiplication using a special (optimized ?) algorithm, but the next one actually reveals the odd behavior of this function.

fp_mul(a, b) produces a*b, but fp_mul_monty(a, b) gives a*b*r, and r is some constant dependent on the size of a word on the target machine…

In the case of the challenge this constant is actually :

# fp_mul_monty constant
R = 0xC9BD1905155383999C46C2C295F2B761BCB223FEDC24A059D838091D0868192A
# obtained by modifying sss.c
"""
int main(void)
{
	int ret = 0;
    fp_ctx ctx;
    nn p;
    ret = nn_init_from_buf(&p, prime, sizeof(prime)); EG(ret, err);
    ret = fp_ctx_init_from_p(&ctx, &p);EG(ret, err);

    fp a, b;
	ret = fp_init(&a, &ctx);EG(ret, err);
	ret = fp_one(&a);EG(ret, err);
	ret = fp_init(&b, &ctx);EG(ret, err);
	ret = fp_one(&b);EG(ret, err);

	ret = fp_mul_monty(&a, &a, &b);EG(ret, err);
	unsigned char buff[33];
	ret = fp_export_to_buf(buff, 32, &a);EG(ret, err);
	for (int i=0; i<32; ++i) {
	    printf("%02X", buff[i]);
	}
	printf("\n");
err:
	return ret;
}
"""

Now with a fully working Python implementation of the generation process, the attack can be implemented :

import hmac
import gmpy2

P = 115792089237316195423570985008687907853269984665640564039457584007908834671663
# fp_mul_monty constant
R = 0xC9BD1905155383999C46C2C295F2B761BCB223FEDC24A059D838091D0868192A

def fp_mul_monty(a, b):
    return (a*b*R) % P

def hi(key, i):
    # because the see
    if i == 0:
        return seed
    C = bytes([0, i])
    h = hmac.new(key+C, C, "SHA512")
    h = int(h.hexdigest(), 16) % P
    return h % P

def makeShare(key, base, k):
    exp = 1
    s = 0
    for i in range(1, k):
        exp = fp_mul_monty(exp, base)
        ai = hi(key, i)
        ai = fp_mul_monty(ai, exp)
        # because there is another fp_mul_monty during the blinding
        # just multiply by R
        s += fp_mul_monty(ai, 1)
    return s

def recoverSeed(key, base, expected, k):
    a = 1
    a += makeShare(key, base, k)
    # s = s_b / (1 + sum(H_i*b^i))
    s = expected * gmpy2.invert(a, P)
    s %= P
    s = hex(s)[2:].zfill(64)
    return bytes.fromhex(s)

expected = 0xb89a285e5505b793969e235c016632797029e7c4bf17791765cefce73a27450d
base = 0x62E2

# tweeked for the demo
for k in range(41, 42):
    for keyi in range(65536):
        key = keyi.to_bytes(2, 'big')
        seed = recoverSeed(key, base, expected, k)
        if b'FCSC' in seed:
            print(seed)
            break

Trying all values of k until 41 did take some time, but in the end the flag appeared.

FCSC{48.8522620000/2.2865220000}

As a fun fact, those coordinates correspond to the location of ANSSI’s office in Paris.

IZNOGOOD

Difficulty : ⭐⭐⭐
Points : 474
Solves : 11

Description

Votre stagiaire n'a pas confiance dans l'AES et a écrit son propre algorithme de chiffrement par bloc. Pouvez-vous lui rappeler que construire sa propre crypto devrait être interdit ? :-)

The following source code was provided :

import os

class IZNOGOOD:
    def __init__(self, k):
        self.k = self._b2n(k)
        self.nr = 8
        self.S = [12, 5, 6, 11, 9, 0, 10, 13, 3, 14, 15, 8, 4, 7, 1, 2]
        self.pi = [
            [0x2,0x4,0x3,0xf,0x6,0xa,0x8,0x8,0x8,0x5,0xa,0x3,0x0,0x8,0xd,0x3,
             0x1,0x3,0x1,0x9,0x8,0xa,0x2,0xe,0x0,0x3,0x7,0x0,0x7,0x3,0x4,0x4],
            [0xa,0x4,0x0,0x9,0x3,0x8,0x2,0x2,0x2,0x9,0x9,0xf,0x3,0x1,0xd,0x0,
             0x0,0x8,0x2,0xe,0xf,0xa,0x9,0x8,0xe,0xc,0x4,0xe,0x6,0xc,0x8,0x9],
            [0x4,0x5,0x2,0x8,0x2,0x1,0xe,0x6,0x3,0x8,0xd,0x0,0x1,0x3,0x7,0x7,
             0xb,0xe,0x5,0x4,0x6,0x6,0xc,0xf,0x3,0x4,0xe,0x9,0x0,0xc,0x6,0xc],
            [0xc,0x0,0xa,0xc,0x2,0x9,0xb,0x7,0xc,0x9,0x7,0xc,0x5,0x0,0xd,0xd,
             0x3,0xf,0x8,0x4,0xd,0x5,0xb,0x5,0xb,0x5,0x4,0x7,0x0,0x9,0x1,0x7],
            [0x9,0x2,0x1,0x6,0xd,0x5,0xd,0x9,0x8,0x9,0x7,0x9,0xf,0xb,0x1,0xb,
             0xd,0x1,0x3,0x1,0x0,0xb,0xa,0x6,0x9,0x8,0xd,0xf,0xb,0x5,0xa,0xc],
            [0x2,0xf,0xf,0xd,0x7,0x2,0xd,0xb,0xd,0x0,0x1,0xa,0xd,0xf,0xb,0x7,
             0xb,0x8,0xe,0x1,0xa,0xf,0xe,0xd,0x6,0xa,0x2,0x6,0x7,0xe,0x9,0x6],
            [0xb,0xa,0x7,0xc,0x9,0x0,0x4,0x5,0xf,0x1,0x2,0xc,0x7,0xf,0x9,0x9,
             0x2,0x4,0xa,0x1,0x9,0x9,0x4,0x7,0xb,0x3,0x9,0x1,0x6,0xc,0xf,0x7],
            [0x0,0x8,0x0,0x1,0xf,0x2,0xe,0x2,0x8,0x5,0x8,0xe,0xf,0xc,0x1,0x6,
             0x6,0x3,0x6,0x9,0x2,0x0,0xd,0x8,0x7,0x1,0x5,0x7,0x4,0xe,0x6,0x9],
            [0xa,0x4,0x5,0x8,0xf,0xe,0xa,0x3,0xf,0x4,0x9,0x3,0x3,0xd,0x7,0xe,
             0x0,0xd,0x9,0x5,0x7,0x4,0x8,0xf,0x7,0x2,0x8,0xe,0xb,0x6,0x5,0x8],
        ]
        self.rk = self.pi
        for r in range(self.nr + 1):
            for i in range(32):
                self.rk[r][i] ^= self.k[i]

    def _S(self, s):
        return [ self.S[x] for x in s ]
        
    def _P(self, s):
        r = []
        for j in range(32):
            b = 0
            for i, x in enumerate(s):
                if i == j: continue
                b ^= x
            r.append(b)
        return r
    
    def _addKey(self, a, r):
        return [ x ^ y for x, y in zip(a, self.rk[r]) ]
        
    def _n2b(self, v):
        L = []
        for i in range (0, len(v), 2):
            a, b = v[i], v[i + 1]
            L.append( b ^ (a << 4) )
        return bytes(L)
    
    def _b2n(self, v):
        L = []
        for x in v:
            L.append( (x >> 4) & 0xf )
            L.append( x & 0xf )
        return L
    
    def encrypt(self, m):
        s = self._b2n(m)
        for i in range (self.nr - 1):
            s = self._addKey(s, i)
            s = self._S(s)
            s = self._P(s)
        s = self._addKey(s, self.nr - 1)
        s = self._S(s)
        s = self._addKey(s, self.nr)
        return self._n2b(s)

KP = 1
flag = open("flag.txt", "rb").read()

k = os.urandom(16)
E = IZNOGOOD(k)

P = [ flag[i:i+16] for i in range(0, len(flag), 16) ]
C = [ E.encrypt(p) for p in P ]

for i in range(len(P)):
    if i < KP: print(P[i].hex(), C[i].hex())
    else:      print("?" * 32, C[i].hex())

#464353437b6661343232653333393434 07b0d32c8a6a25dc782d2ee20acd53f3
#???????????????????????????????? ba596368fc650d3d08ffbfb2bda27f28
#???????????????????????????????? 68be7f31b109babfb667aabb92a119cd
#???????????????????????????????? acf46fe7220bf34cb2fe740c5773b354

Resolution attempt

This challenge had me puzzled until the end of the CTF.

Here is a list of all the things I tried and didn’t work :

  • Linear cryptanalysis
  • Differential Cryptanalysis
  • Algebraic attacks:
    • SMT solvers:
      • Represent the cipher using z3 (solved 3 rounds in several minutes)
      • Meet-in-the-Middle using z3 (solved 4 rounds in 9 seconds, never solved 6)
      • Take into consideration the second cipher text bloc and constrain the plaintext to hex (no significant effect)
    • Polynomial representation of the cipher:
      • Gröbner basis reduction (solved only 2 rounds)
      • Change S-Box representation to FWBW (no significant effect at best)
      • Gröbner sliding (solves 1 round)
      • Change term ordering (no effect at best)
      • Meet-in-the-Middle + Gröbner basis reduction (no significant effect)
    • Modify the PRESENT cipher of Cryptapath and use the tool (solved 4 rounds in several minutes)
  • Other random tests
    • Find unmodified key bits through all round keys (there are 2 !)
    • Search for related keys 🦘

I had a feeling the vulnerability would come from the permutation layer, because it’s the only thing that was fishy. The round keys are derived using nothing-up-my-sleeve numbers, so there should be no surprise in there.

I gave up after 4 days of struggles.

After having read other participant’s write-up, I was pleased to see I completely missed the vulnerability. At least it wasn’t an implementation/optimization issue.

Millenium

Difficulty : ⭐⭐⭐
Points : 495
Solves : 3

Description

Notre équipage de rebelles intergalactiques compte sur vous ! Jusqu'à présent notre organisation disposait d'un ordinateur quantique secret capable de contourner les protections cryptographiques mises en place par l'ennemi. Nous pouvions ainsi falsifier nos autorisations de déplacement en hyperespace.

Suspicieux, les agents de régulation des déplacements en hyperespace ont hélas mis au point une nouvelle méthode d'autorisation, appellée "millenium". Celle-ci résiste à notre ordinateur quantique. C'est la déroute ! Toutes nos équipes sont clouées au sol jusqu'à nouvel ordre.

Il y a une lueur d'espoir, la nouvelle méthode de signature a été hautement optimisée pour être efficace et a l'air de comporter une anomalie parallélépipédique. Nous avons besoin de vous pour retrouver la clé privée permettant de re-prendre le contrôle du réseau intergalactique. Nous avons isolé la partie que nous pensons vulnérable dans le fichier sign.py, pas besoin d'examiner le dossier secure_code. Nous avons réussi à mettre la main sur 300 000 signatures et la clé publique associée, cela devrait être suffisant pour trouver la clé secrète ennemie et signer une autorisation de déplacement pour un de nos vaisseaux.

nc challenges.france-cybersecurity-challenge.fr 2102

The source code was provided, as well as a set of 300 000 signatures. Only the main file is presented below :

import os
import sys
sys.path.insert(1, './secure_code')
from random import gauss
from Crypto.Hash import SHAKE256
from ntrugen import ntru_solve, gs_norm
from ntt import ntt, intt, div_zq, mul_zq, add_zq
from fft import fft, ifft, sub, neg, add_fft, mul_fft
from common import q
from math import sqrt

def prvkey_gen(n = 128):
    while True:
        sigma = 1.17 * sqrt(q / (2 * n))
        f = [int(gauss(0, sigma)) for _ in range(n)]
        g = [int(gauss(0, sigma)) for _ in range(n)]
        if gs_norm(f, g, q) > (1.17 ** 2) * q:
            continue
        f_ntt = ntt(f)
        if any((elem == 0) for elem in f_ntt):
            continue
        try:
            F, G = ntru_solve(f, g)
            F = [int(coef) for coef in F]
            G = [int(coef) for coef in G]
            return f, g, F, G
        except ValueError:
            continue

def pubkey_gen(sk):
    f, g, _, _ = sk
    return div_zq(g, f)

def hash_to_point(salt, message, n = 128):
    k = (1 << 16) // q
    shake = SHAKE256.new()
    shake.update(salt)
    shake.update(message)
    hashed = [0 for i in range(n)]
    i = 0
    j = 0
    while i < n:
        twobytes = shake.read(2)
        elt = (twobytes[0] << 8) + twobytes[1]
        if elt < k * q:
            hashed[i] = elt % q
            i += 1
        j += 1
    return hashed

# this function has been HIGHLY optimized to be super efficient
def sign(sk, message):
    f, g, F, G = sk
    B0 = [
        [g, neg(f)],
        [G, neg(F)],
    ]

    r = os.urandom(40)
    point = hash_to_point(r, message)
    n = len(point)

    B0_fft = [[fft(elt) for elt in row] for row in B0]
    [[a, b], [c, d]] = B0_fft

    point_fft = fft(point)
    t0_fft = [(point_fft[i] * d[i]) / q for i in range(n)]
    t1_fft = [(-point_fft[i] * b[i]) / q for i in range(n)]

    z0 = [round(elt) for elt in ifft(t0_fft)]
    z1 = [round(elt) for elt in ifft(t1_fft)]

    z_fft = [fft(z0), fft(z1)]
   
    v0_fft = add_fft(mul_fft(z_fft[0], a), mul_fft(z_fft[1], c))
    v1_fft = add_fft(mul_fft(z_fft[0], b), mul_fft(z_fft[1], d))
    v0 = [int(round(elt)) for elt in ifft(v0_fft)]
    v1 = [int(round(elt)) for elt in ifft(v1_fft)]

    s = [sub(point, v0), neg(v1)]
    return r, s

def verify(h, message, signature):
    r, s = signature
    if len(r) != 40:
        return False
    s0, s1 = s
    n = len(s0)
    signature_bound = 2 * n * q

    hashed = hash_to_point(r, message)
    point = add_zq(s0, mul_zq(s1, h))

    if point != hashed:
        return False

    norm_sign  = sum(coef ** 2 for coef in s0)
    norm_sign += sum(coef ** 2 for coef in s1)
    return norm_sign <= signature_bound

def test():
    sk = prvkey_gen()
    pk = pubkey_gen(sk)

    for _ in range(1):
        message = os.urandom(32)
        sig = sign(sk, message)
        print(sig)
        assert verify(pk, message, sig)

if __name__ == "__main__":
    test()

Resolution attempt

Conclusion

As always, the challenges were really good. I found that the difficulty has increased a lot compared to last year.

Even though I did not manage to solve two of the challenges, I’m pretty happy with my performance and learned a lot during the event.

I’m looking forward for next year !

Leave a Reply

Your email address will not be published.