2
$\begingroup$

I'm new to cryptography, and I've searching about ECDSA because I'm trying to solve a CTF.

I've already check this site and Google, and I think I'm in the right path, but probably I am missing something.

I have access to messages and the ECDSA signature that they generate. The format is always the same:

Example of a message:

{"session_id": "6621a96c7db568374f2885d6d135f395010e75a94ec2233a433ff8e2", "user": peter}

And the signature have always the same first half.

znnlVaDhCokfqzU5figrY2cZ1nk87rH/

Example of two signatures:

znnlVaDhCokfqzU5figrY2cZ1nk87rH/+Zc/DvAEIyjZ4pv8SVmCsWLtq+yJrtFJ znnlVaDhCokfqzU5figrY2cZ1nk87rH/zcCHDV2rLJ6nhdjE9vzblfpkzrhqzVjY

This looks like signatures generated with NIST192p curve (because of the size) ?

There are similar CTF that used the same thing as this one, and a solution like this one: http://ropnroll.co.uk/2017/05/breaking-ecdsa/

But the new generated signature doesn't start with the same part as the above ones.

They seem to be based on this one, https://antonio-bc.blogspot.com/ (you can look for ECDSA).

Here is again another CTF with a similar issue, but with a different curve. http://itemize.no/2016/08/26/IceCTF-contract-task/

Also I've checked the video from LiveOverflow that tackle the same issue, https://www.youtube.com/watch?v=-UcCMjQab4w

Since these are solutions for previous CTF, I'm thinking the the way I'm creating the messages isn't the same as the server.

This ECDSA implementation should be vulnerable, right ? This is the modified code that I have right now.

$\endgroup$
2
$\begingroup$

You are right. And this had been exploited in the past in the PS3 and Bitcoin wallet events.

The first half of the signature is the x coordinate of $k \times G$, and $k$ is the ephemeral key that must be unique to each signature generated. If it's static then the following formula would recover the private signing key:

$k = {{z_1 - z_2} \over {s_1 - s_2}}$ and $d = {{sk-z} \over r}$ where $z_1$ and $z_2$ are the truncated hash bitstring, $s_1$ and $s_2$ are the two corresponding signature component, $r$ being the fixed part in both signatures, and $d$ the private key we hunt.

For more, Wikipedia has an article covering ECDSA and its security.

$\endgroup$
  • 1
    $\begingroup$ For clarity: the equations given are modulo the group order, often noted $n$. $\endgroup$ – fgrieu Nov 19 '18 at 12:58
  • $\begingroup$ So, finally found the solution. There was an missing step that had nothing to do with ECDSA. CTFs are to dive in new stuff, learn a lot about ECDSA and general crypto. $\endgroup$ – David Magalhães Nov 19 '18 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.