# Writeup: De1 CTF 2020 - ECDH

## Information

*category*: crypto*points*: 338

## Description

Exchange your keys

nc 134.175.225.42 8848

1 file: task.py

## Writeup

I solved this challenge together with The_Lillo

and 0ssigeno.

We are given a `task.py`

which is the script running on the server:

1 | import os,random,sys,string |

So the server is defining a custom elliptic curve:

`y^2 = x^3 + ax + b over Fq`

where:

1 | a = 0x4cee8d95bb3f64db7d53b078ba3a904557425e2a6d91c5dfbf4c564a3f3619fa |

And a generator `P = (x, y)`

with:

1 | x = 0xb55c08d92cd878a3ad444a3627a52764f5a402f4a86ef700271cb17edfa739ca |

The main iter of the server is:

- Ask for a Proof of Work where we need to find an easy collision on sha256.
- Generate a random secret between
`(0, q)`

. - Compute
`Q = P * secret`

. `Exchange`

operation.- For 90 times 1 operation between
`Exchange, Encrypt, Backdoor`

.

Code of `Exchange`

:

1 | def exchange(self): |

So the server asks the coordinate of a point (let’s call this point `G`

), and then compute `key`

as `key = G * secret`

.

Code of `Encrypt`

:

1 | def encrypt(self): |

The server asks for a message and then xor our message with the `key`

. If we xor back the result with our message we obtain the `key`

.

Code of `Backdoor`

:

1 | def backdoor(self): |

So if we guess/find correctly the secret we can get the flag.

However finding `k`

from `Q, P`

where `Q = P * k`

is known as the

discrete logarithm problem and is very hard to compute in polynomial time.

(In our case `k`

is the secret).

I found this paper which describe various attacks on ECC, the one I was interested in is the Smart’s attack which is possible when the order of the curve is equal to `q`

.

We can test this in sage:

1 | a = 0x4cee8d95bb3f64db7d53b078ba3a904557425e2a6d91c5dfbf4c564a3f3619fa |

Output:

1 | 100173830297345234246296808618734115432562869561923600152135698390163541578931 |

Ok no smart’s attack.

We tried to set the point `(0, 0)`

during the exchange and then encrypting a

random message. We saw that the ciphertext was equal to the message, so the `key`

was set to 0. Then I wanted to try some basic multiplications on sage using the

point `(0, 1)`

but:

1 | G = E([0, 1]) |

Right! The point `(0, 1)`

and `(0, 0)`

are not on the curve!

So what?

Well we can use the invalid curve attack to find the secret!

The server fails to validate that the point is on the curve, so the custom points have different order, and we can easily compute the discrete logarithm since the order of the new curve is very small.

Example using sage:

1 | sage: E = EllipticCurve(GF(q), [a, 10]) # Define custom curve with b = 10 |

We chose as order `7`

, and then we computed a generator `G`

of the curve. Finally we have computed `G * i`

for every i in range(10).

We can see that after the firsts `7`

multiplication, the points are repeating. This is because we are in a cyclic group.

How can this help?

Well in this case computing discrete log is very easy because there are few possible cases (7).

If we now submit this point in the `Exchange`

to the server and then we retrieve the key it’s trivial to find the secret?

Well no. What we will found is not the secret because the secret is between `(0, q)`

and is presumably around 250/255 bits long and not between 0 and 7.

What we can do is to try retrieving various pair `(dlog, prime)`

and create a system of linear congruences that are solvable using the Chinese Remainder Theorem.

`dlog`

is the result of the discrete logarithm and `prime`

is the order of the generator.

1 | #!/usr/bin/env python3 |

The main problem was time. The server has a connection timeout of 5 minutes and we got 3 main bottlenecks:

- Computing prime factors of the custom curve.
- Find a generator of the curve.
- Solving dlog.

What we did was:

- Use factordb to factorize the order of the curve.
- Cache various generator using an external script.
- Solve the discrete logarithm in a separate process.

## Exploit

Generator script:

1 | generators = {} |

Exploit:

1 | #!/usr/bin/env python3 |

And after a while..

YEAH! We managed just in time to get the flag, fiu.

## Flag

`De1CTF{c47b5984-1a7c-49f5-a2e3-525d83b50ecf}`

## Fails

We spent many time trying to parse correctly the key and to convert it to a point

and the xor gave us some problems.