Our participation to the CTF of Starknet CC Lisbon 2022

Ledger had a team there to compete against other starkpilled-companies. Our team was composed of four members from the innovation team (@btchip, @qdqd___, @crema, @RenoCrypto) and two members from Ledger Donjon (@kajaz, Nics). At the end of the event, our team finished first and was awarded the price of 6000$. In this CTF, the organisers chose to use a dynamic scoring: this means that each challenge starts at 500 points and, at the end of the CTF, the more teams have solved it, the less point it is worth (down to 100 points). In this blogpost we explain what kind of challenges our team had to solve, and we describe in details the solution to a challenge. This challenge was solved only by our team, thus awarding us the full 500 points!

You can find a write-up for every challenge solved (11 of the 12 possible) on this GitHub repository.

Overall feedback

This CTF was a good opportunity to learn or sharpen the Cairo skills of the team. The challenges ranged between very easy and medium difficulty, some of them were designed to give a glimpse at how Cairo bytecodes work under the hood. Overall, the challenges were interesting and their design was clever.

What kind of challenges we faced?

The challenges were focused on Cairo, the language used to write smart-contracts that run on Starknet. More specifically, version 0.10.0 of Cairo for this CTF. The goal was to find low-level as well as logic vulnerabilities in some contracts, and exploit those vulnerabilities.

Infrastructure

For the participants to interact with the needed smart contracts and issuing transactions, the organisers have used the same infrastructure as for Paradigm CTF 2022. To interact with the different challenged, each competing team was provided with a unique ticket and a different TCP endpoint was given for each challenge. The TCP endpoint was used as a menu for game interaction:

$ nc <DOMAIN> <PORT>
1 - launch new instance
2 - kill instance
3 - get flag
action? 1
ticket please: <TICKET>

your private blockchain has been deployed
it will automatically terminate in 30 minutes

The “launch new instance” command was used to deploy the needed smart contracts and to get access to an account contract’s private key. This account contract was provided with some funds by the game server and, together with the details of an RPC endpoint, this allowed us to send transactions. If need be, we were able to destruct the current game instance in order to create a fresh new one. The last action that was allowed from the game interface was the “get flag” action. This command was used to instruct the game server to check if the challenge was solved by the team and, if it is, return the sought-for flag. The exact way a challenge instance was created and how the resolution was checked was defined by a Python script given to us along with the source code the challenge.

How to solve dna efficiently?

Among all the 12 challenges, only one was solved only by our team: dna. We will now explain what was the setup and how we managed to solve it.

Challenge setup

The setup for this challenge was quite straightforward. The source code of a smart contract was given to us. During the initialisation of the game instance, this contract was deployed with a known value as the _password argument of the contract’s constructor. For the challenge to be considered completed by the game server, a call to the function is_challenge_done of the contract must return 1.

Source code analysis

The only function declared as “external” in the contract is test_password. This means that this was our only entrypoint to interact with the contract. However, in order to understand this function, we first needed to understand a function that is called during the execution of test_password: test_value.

Helper function test_value

The function test_value is short and very simple, even for someone not familiar with Cairo:

func test_value(input: felt, res1: felt, res2: felt, res3: felt, res4: felt) -> (res: felt) {
    alloc_locals;

    let value = input;

    if (value == 67) {
        return (res=res4);
    }

    if (value == 71) {
        return (res=res2);
    }

    if (value == 84) {
        return (res=res1);
    }

    if (value == 65) {
        return (res=res3);
    }
    return (res=0);
}

One thing that may appear surprising is the word felt that appears many time in the list of argument and return value. felt is the name given to a Cairo type. It is the contraction of “field element” and it is the type representing exactly that: an element of the base field on which Cairo is computing. As a first approximation that is sufficient for this challenge, it can be seen as an integer modulo a 252-bit prime number. In fact, in Cairo, every decimal litteral is interpreted as a felt so the number 67, 71, 84 and 65 is the source code are also felts.

The test_value function is mapping the input value to one of five possible field elements: either one of the four parameters if input is among [84, 71, 65, 67] or 0 for any other value. If the input value is 84, then the second argument res1 is returned, if it is 71 then the third argument res2 is returned, etc. The four possible values for input were not chosen at random by the designers of the challenge: they correspond to the ASCII representation of the four letters “T”, “G”, “A” and “C”, that are the four letters used to denote the four possible nucleobases in the DNA.

Challenge body function test_password

The code for test_password is a little bit longer but once the important part are identified, then it was relatively simple to understand what its execution was performing on the input.

@external
func test_password{syscall_ptr: felt*, pedersen_ptr: HashBuiltin*, range_check_ptr: felt}(
    inputs_len: felt, inputs: felt*
) -> () {
    alloc_locals;
    let values_len = inputs_len;
    let values = inputs;

    with_attr error_message("    ERROR: You have to use a list with a len equal to 17!") {
        assert values_len = 17;
    }

    test_value([values], 1498, 997, 2753, 6301);
    let result1 = [ap - 1];

    test_value([values + 1], 5939, 1823, 5501, 2069);
    let result2 = [ap - 1] + result1;

    test_value([values + 2], 113, 127, 131, 137);
    let result3 = [ap - 1] + result2;

    test_value([values + 3], 1913, 7919, 7127, 7577);
    let result4 = [ap - 1] + result3;

    test_value(
        [values + 4],
        877,
        27644437,
        35742549198872617291353508656626642567,
        359334085968622831041960188598043661065388726959079837,
    );
    let result5 = [ap - 1] + result4;

    test_value([values + 5], 16127, 1046527, 16769023, 1073676287);
    let result6 = [ap - 1] + result5;

    test_value([values + 6], 2381, 2521, 3121, 3613);
    let result7 = [ap - 1] + result6;

    test_value([values + 7], 3259, 3301, 3307, 3313);
    let result8 = [ap - 1] + result7;

    test_value([values + 8], 479, 487, 491, 499);
    let result9 = [ap - 1] + result8;

    test_value([values + 9], 23497, 24571, 25117, 26227);
    let result10 = [ap - 1] + result9;

    test_value([values + 10], 60493, 63949, 65713, 69313);
    let result11 = [ap - 1] + result10;

    test_value([values + 11], 87178291199, 479001599, 39916801, 5039);
    let result12 = [ap - 1] + result11;

    test_value([values + 12], 13, 29, 53, 89);
    let result13 = [ap - 1] + result12;

    test_value([values + 13], 433494437, 2971215073, 28657, 514229);
    let result14 = [ap - 1] + result13;

    test_value([values + 14], 131071, 2147483647, 524287, 8191);
    let result15 = [ap - 1] + result14;

    test_value([values + 15], 786433, 746497, 995329, 839809);
    let result16 = [ap - 1] + result15;

    test_value([values + 16], 9091, 101, 333667, 9901);
    let result17 = [ap - 1] + result16;

    let (test_password_) = hash2{hash_ptr=pedersen_ptr}(result17, 317);
    let (read_storage) = test_pass.read(test_password_);
    if (read_storage == 1) {
        challenge_is_done.write(1);
        return ();
    }
    return ();
}

In summary, this function takes as input an array of field elements and:

• checks that the input is a list of exactly 17 values;
• for each of the input values:
  • it replaces it with another value by using test_value and a set of four seemingly arbitrary integers, different for each of the 17 calls;
  • increments an accumulator (that we call a) by the value returned by test_value;
• after processing the 17 inputs, hashes this accumulator using hash2(a, 317);
• compares this hash with the target value set in the storage variable test_pass during the deployement of the contract.

The target value test_pass could be recovered from the deployement script and was equal to: 3329738248317886966279794942297149793815292158761370755733235303955518040301. Our goal was thus to find an appropriate list of 17 values such that the result of the final hash was equal to this value.

Hashing function: hash2

The hash2 function is a built-in function in Cairo and is imported at the start of the contract. This function takes two field elements a and b and, in our case, uses arithmetic on an elliptic curve to compute their hash. More precisely, the result is the x-coordinate of H defined by:

Where

are points that are fixed for every call to hash2 in the contract and ⋅𝚕𝚘𝚠(respectively, ⋅𝚑𝚒𝚐𝚑) is the integer represented by the 248 lowest bits (respectively, 4 highest bits) of ⋅.

In this contract, since the value of b was fixed to 317 and since the highest reachable value for a (sum of the 17 highest values) was lower than 2²⁴⁸, the formula for the hash could be simplified:

Because of how elliptic curves works, having a target value for the x-coordinate of hash2(a, 317) fixes two possible points H and H′ , and we were looking for a value a such that:

That is, we were looking for the discrete logarithm of either 

or

with P₁ as a base point.

Finding a solution

In general, this is a difficult problem. However, we knew that the solution a is the sum of 17 values and that each value can only be one of four possibilities given to us. This means that we would have at most 4¹⁷ = 2³⁴ different values to try. While this is much less than the number of possible values in the general discrete logarithm problem, this was still too costly in the context of this challenge: computing every hash possible can be slow because the underlying elliptic curves operation (namely scalar multiplication) is somewhat slow (around 350 hash per second with our implementation).

Baby-step giant-step methodology

To help us solve this challenge in a reasonable time, we used a strategy inspired by the well-known baby-step giant-step algorithm. Instead of doing 2³⁴ operations, we used a trade-off between memory and computation cost. Remember that the value we needed to find, a, was computed as the sum of 17 unknown values that we call a_i:

Let split a into two parts:

What we have done first is to compute every possible value for A₀, storing the result of [A₀]P₁ in a table. 

Then, we computed every possible value for A₁, computed H − S − [317]P₂ − [A₁]P₁ and looked in the previously computed table if the value was present.

 If it was the case, then we had two values A₀ and A₁ such that S + [317]P₂ + [A₀] P₁ + [A₁] P₁ = H, which in turn meant that a = A₀+A₁. The cost of such an algorithm have an upper bound at 2¹⁶ + 2¹⁸ scalar multiplications and 2¹⁶ stored elliptic curve points. Once we obtained the values of A₀ and A₁, we were able to quickly recover the values of each a_i and in turn the 17 values needed as input to the test_password function.

Our implementation of this attack was written in Sage and it took around 100 cpu-seconds to run on our laptop’s i7 processor. It is important to note that in our case, the second step ended more quickly than expected for a random unique solution: we found the right A₁ after only 3% of the 2¹⁸ possible values. This may be due to the fact the solution (A₀,A₁) was not unique in combination with some luck.

Additional optimisation

However, we realised after having solved this challenge that we did not really need to do that much scalar multiplications. As an additional optimisation, it was possible to precompute every possible partial point [a_i]P₁ such that during the actual search we only have to compute point additions and not scalar multiplications. This is much less costly to compute and allows to solve the challenge in less than 10 seconds.

The optimised implementation can be found here.

Conclusion

It was really fun participating in such a CTF. We would like to thank the organizers and challenge authors for their work. We are looking forward to compete in the next CTF if we have the opportunity to do so!