Challenge description

Inventing hash functions based on elliptic curves is not easy, but now I found out that with the quadratic twist I can lift any x! This should be enough to create a secure one.

Note: the challenge is running with SageMath 10.2 on the remote server.

nc invention.challs.open.ecsc2024.it 38011

Table of contents

• Overview
• The algorithm
• Collidin
  • CT - the easy part
  • CE - the hard part
  • An annoying detail
  • Solving the instance
• Conclusion

Overview

We are given invention.sage and a connection to the server which is running it. The core of the program is the function elliptic_hash, which recieves a bytestring and returns two elliptic curve points.

The protocol for communicating with the server is as follows:

• You send your username
• The server sends you a random token
• You send a password which has to start with said token
• The server hashes your password and saves it
• The server registers an admin user and you are shown the token and password of the admin
• Finally we get to log in, in order to get the flag we must log in as our user (hence it has to start with our token), but the password hash must be that of the admin. Essentially we must find a hash collision for the admins password with a set prefix (our token).

The algorithm

Let's look at how elliptic_hash is structured. Two different elliptic curves are used, and its quadratic twist which will be referred to as . These two curves have the generators and .

We will not need any deep knowledge of elliptic curves to solve this, these are the main relevant principles:

• If the point is a generator of then any point on can be written as for some integer .

• If a given -coordinate does not correspond to a point on then it will correspond to a point on , and vice versa.

When the program is initialized two random integers and are generated. These are then multiplied by the corresponding generator point of each curve to yield two new points and (Pu and PTu in the source code). We are shown and and can hence calculate both points ourselves.

The message is first divided up into blocks of 20 bytes, which corresponds to the size of the -coordinate of a point on the curve. When referring to blocks from now on we are interested in their integer representation.

The first two blocks are special and will be denoted and , the remaining blocks are . The first step is to calculate and (Ci and CTi in the source code).

Afterwards, for each , we check if its value corresponds to the -coordinate of a point on . If that is the case we lift the -coordinate to the corresponding point, , and add it to (i.e we modify ).

If the -coordinate is not on , and hence on , it is lifted to a point on and added to instead.

The final hash is the tuple , which will equal:

The final crux is that when we and the admin are first registering all the blocks we use are saved. Later, when logging in, we are only allowed to use blocks which were already used in the registration phase (from before we even know the admin's password).

Collidin

Since we are given the admin's password we can calculate the corresponding hash ourselves. The core problem is that we are forced to use the given token as our first block (i.e ).

Since the hash is split up into two parts ( and ) let's first focus on the easier one: .

CT - the easy part

Since we are given full control of we can simply set it to be the same as in the admin's password. From there we grab all blocks from the admin's password which are and add them to our password as well. Our will now be identitcal to the admin's. We are allowed to do this since the admin's blocks were added to the allowed ones during registration.

CE - the hard part

Now for . The from the admin's password can be added to ours as well just as in the case, so we can ignore all but the first block.

Let's call our given token and the admin token. Before we even gain control will equal . Recall that the result of the first admin block will be . We thus want to find such that , or equivalently

If we rewrite each as some multiple of the generator we get

It thus suffices to find such that

This is a problem in integers which is a lot nicer to work with.

Normally we could just set and be done, but recall that we had the restriction that only blocks which had been used during registration may be used now, and when registering we don't know yet.

An important thing to note is that we may use one point several times by just repeating the block in the password, essentially multiplying the point by a small scalar. So if we predefine a set of points during registration we can then build up any linear combination of them later, which will be of the form for reasonably small (otherwise the password will be too long).

There are several ways to choose a basis here. An easy approach would be to collect all powers of 2 times the generator, i.e . We could then build any multiple of by just looking at its binary representation. This will require as many points as there are bits in .

An annoying detail

A problem you will encounter is that due to implementation details in the source code our password is required to be valid utf-8, else the code will raise an error. You can get around this by for example brute-forcing pairs of points which sum to and are each valid utf-8, but from my experience this takes a looong time.

We thus want to have as few basis points as possible since finding each one requires extensive brute force. My approach was to simply generate random multiples of and check if it decodes properly. I could then save the point together with that multiple, and after around 17 points I could reliably reach most points on the curve using quite small coefficients (in the base-2 case we restricted ourselves to coefficients of 0 and 1, we can now use any non-negative integer).

Solving the instance

Finding the such that is not completely trivial. A common method is to use a lattice reduction algorithms like LLL, but configuring it such that all can be a bit cumbersome (although definitely possible). If you're interested the lattice will resemble the ones presented here.

I've encountered this problem several times before so I have made a utility which combines lattice reduction with some more exact linear programming methods. I was happy to be able to test it out so soon and it worked well for this purpose, you can check it out here.

Conclusion

This covers all the ideas used in my solve script, read it for more details. This was a very fun challenge which combined several known primitives into an interesting problem, thanks to the author for writing it and I hope we will see more like this in the ECSC finals! 🇮🇹🤌🍕🍍