# 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$.

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 `felt`

s.

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`

;

- it replaces it with another value by using
- 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^{248}, 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_{1} 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^{17} = 2^{34 }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^{34} 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_{0}, storing the result of [A_{0}]P_{1} in a table.

Then, we computed every possible value for A_{1}, computed H − S − [317]P_{2} − [A_{1}]P_{1} and looked in the previously computed table if the value was present.

If it was the case, then we had two values A_{0} and A_{1} such that S + [317]P_{2} + [A_{0}] P_{1} + [A_{1}] P_{1} = H, which in turn meant that a = A_{0}+A_{1}. The cost of such an algorithm have an upper bound at 2^{16} + 2^{18} scalar multiplications and 2^{16} stored elliptic curve points. Once we obtained the values of A_{0} and A_{1}, 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_{1} after only 3% of the 2^{18} possible values. This may be due to the fact the solution (A_{0},A_{1}) 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_{1} 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!