# Breaking ECDSA (Elliptic Curve Cryptography) – rhme2 Secure Filesystem v1.92r1 (crypto 150)

The first challenge I did from this competition

was the secure filesystem, which we exploited

with a hash length extension attack. And then

we also solved this other crypto challenge

“key server”, which was about breaking

RSA signatures. So let’s continue the path

and do the last crypto challenge, I wonder

what we will have to break this time.

Crypto 150 points. Secure Filesystem v1.92r1.

That version number is already suspicious.

But let’s read the description first.

After the horrible debacle of the first file

system, we got together again, invited our

friend Mr. Wodka and waterproofed the secure

file system. You can test it again, but this

time it uses unbreakable encryption.

The filesystem allows you to request the contents

of one or more available files by using the

following format:

Which is basically the same like in the previous

filesystem challenge.

Token, then a hash symbol, followed by one

or multiple filenames.

And we get a list of example tokens and filenames.

Here is how it looks when you run the challenge.

You get the list of files, and if you supply

the correct token and filename, you get the

content back. And somehow we want to read

passwd.

Before I tell you the solution, let me explain

my thought process here. Because I went into

a completely wrong direction at first and

somebody on IRC had to nudged me into the

correct direction. I completely failed this

challenge.

So first I had a look at the version number.

That seemed too specific to not be a hint.

And it could have lead me to the correct solution,

but I got distracted by the list of examples.

Because there we can immediately notice, that

the first part of it is always the same, which

I interpreted to be some kind of block cipher.

And I thought the first block always encrypted

the same secret key or something – similarly

how the bad hash implementation prepended

a secret key in the first level.

And the version number for me became the bit

length of the cipher. The text said it’s

strong encryption, so I went to look for ciphers

with 192 bit options. I mostly looked into

AES.

But all attempts of manipulating blocks, for

example for padding oracle didn’t work.

Another lead I had was the waterproof filesystem.

I figured maybe it is some kind of whirlpool

hash? But that also didn’t make much sense.

Then maybe it had to do with the vodka? Maybe

there is a russian cryptographer named gorbatschow

with some weird obscure encryption. But everything

I tried just didn’t seem to be the right

path. I kept running in circles and really

wanted to give up.

Then I got a slight hint to focus more on

the version number again.

And while I did find hints to elliptic curve

cryptography when googling for the version

number before, I ignored them. That was a

mistake.

It turns out, 192r1 is a curve parameter for

ECDSA. Elliptic Curve Digital Signature Algorithm.

Ok. So I know this elliptic curve stuff exists,

but I never really looked into it as much

as I should have. While RSA seems pretty straight

forward, this stuff always seemed a lot more

difficult to understand. So I started to read

wikipedia.

And there is even a section called “security”,

where they say that Sony did not properly

implement the algorithm on the PlayStation

3, because one of the variables k was static

instead of random. And apparently it means

you can then break the signature.

So let’s have a quick look at the algorithm

and math itself.

So the provate key is an integer randomly

selected and the public key is the result

of some fancy ellyptic curve multiplication.

You hash the message you want to sign, like

with RSA.

And then you have to select a random k. And

it must be securely random.

Then you calculate a point on the curve based

on that number.

Then you do some more calculations, r and

s. And the signature is the pair of r and

s.

So when we look at our example tokens, we

can assume, that those are the two different

values. R and s.

And r is always the same, which is suspicious.

If you look what r is, then r is basically

x. And x is the x-coordinate of the point

on the curve after the ellyptic curve multiplication

with the secure random k. This means for every

signature, the multiplication had the same

result, which means, k was probably always

the same.

BOOM!

That’s it.

As the standard notes, it is crucial to select

different k for different signatures, otherwise

the equation in step 6 can be solved for the

private key d.

Given two signatures rs and rs-prime, employing

the same unknown k, for different known messages,

an attacker can calculate some fancy stuff

and recover k. And then you can solve this

equation for the private key d. Done.

I’m not very good in math, but I knew that

this is such a basic security issue, that

I’m sure this came up in some other CTF

competitions before. And surely somebody implemented

this calculation in python already.

That is generally a good hint for CTFs. So

I googled specifically for CTF challenges

with ECDSA, and sure enough, I find some example

code. I can just copy that code, but I also

wanted to understand what it does. So let’s

do it step by step.

Let’s start by getting the ecdsa python

module, because we might reuse some functions

and in the end use it to create a proper signature

for the filename we want.

Let’s copy two of the example tokens and

messages and extract the values.

So we got r and s from the first message.

And r and s from the second message.

Then I try to follow the wikipedia article.

So first we check the two rs, if those two

signatures are vulnerable.

Then I wanna prepare most of the values as

I need them. First I hash the message we want

to sign and convert it to a number, so we

can do calculations with it. Which is z1 and

z2.

Then we need n. N is the order of the curve,

so we can get that value from the module.

To find that I just look around in the source

code of the ecdsa module.

Next we gonna recover k like it says here

on wikipedia.

The first part is simply z1 minus z2, so this

is basically just the hash of message1 minus

message2, divided by the substraction of the

signature.

And because you all got some basic math education,

you know that instead of division, you can

also multiply the inverse. Like 6 divided

by 3, is the same as 6 times ⅓.

So we just multiply the inverse of s1 minus

s2.

And we can reuse the inverse modulo function

from the ecdsa module.

Everything happens here always modulo the

n.

Ok, now we got the k.

So next we recover the private key dA. Which

is super simple. It’s just a signature times

k minus the hash, divided by r.

And there we have it. K and the private key

recovered. Now we just have to figure out

how to plug this into python ecdsa to sign

a value for us.

Again, I just look at the source code of the

module and find the correct classes.

To test this I’m gonna sign a test message

which we know the signature of.

And print the original and our calculated

signature.

This looks perfect!

Now let’s sign passwd, so we can get the

flag.

Copy the signature, send it to the board,

and we get the flag.

i really need to turn on notifications

Really nice video, maybe a bit too much math this time of day.

Gutes Video, wie immer 🙂 Jede Woche freue ich mich auf ein neues Video von dir und ich werde nie enttäuscht. Unendlich interessante Inhalte und jemanden der es perfekt erklärt. Herzlichen Dank, deine Videos sind wahrlich eine Bereicherung.

Very nice videos.

Question, lets say when this challenge site is over, can I go back and do the challenges myself?

amazing! you explain very well, btw

dude, how do I learn what u know?

Major sticking point for me on this one was that they used SHA1 as the hash algorithm. I tried with SHA2 for way too long before trying SHA1 and solving it in seconds….

Quality content as always

Great video! I love the math behind elliptic curve crypto! I'm sure i wouldn't have been able to figure it out, but I can remember my lecturer emphasizing that k needed to be recalculated every time, last year at uni 😀

It's important to understand such a protocol before you implement it!

are you gonna make a video about wannacry?

Very nice channel bro, it will go up for sure! 🙂 Keep going!!!

Ha, really liked this one, wish I could have participated myself 🙂 Thanks again for the upload, great as always

You should put up a Patreon, I am sure many of us would love to be able to give you beer money! Awesome video as always.

Where is the "6277101735386680763835789423176059013767194773182842284081" ("FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831") constant documented? I found too many libraries using this number as a constant in the source-code. However I don't found a "documentation", where this number came from and why not another? When you use "NIST192P.order" you get the same number?

can you put some ctfs please , you explain very well Keep going man

This is mindblowing. I'm a bit late to watch this video (around 5 days late), but it's great that I found it.

You deserve waaaay more subs than you have!

Awesome videos man , keep them making! (y)

Thanks for another great video.

From the Wiki article, "In December 2010, a group calling itself

fail0verflowannounced recovery of the ECDSA private key used by Sony to sign software for the PlayStation 3 game console." Illuminati confirmed.How do people learn how to use a crypto API without also learning how to use it properly?

Hello

Can one break the OFW 3.56 and higher on PS3 with this method?

holy shit awesome

Rаte my nаkеd photos (ᵔᴥᵔ), my blоg ➩ http://tinyurl.com/y99aszw5

well done! great info. but what if the "r" given is not the same? is it still possible to solve for "k" if we have different "r"?

need to calculate Z1*S2 -Z2*S1 how to get it….any calculator…help me pleases brooooooo

hey brooo mail me at [email protected] need calculator brooo

why are k(0x7e0) and dA(0x2a) so small? can I just brute force them to solve the challenge?

yes try to do this with btc on a transaction number and find out the PK

Hey, man du hast es echt drauf!!!!!! Ich würde dir gerne dein Programm abkaufen für 1000 Euro, aber es muss so programmiert werden das ich nur noch wenige Eingaben machen muss. Ich habe versucht dir zu folgen, aber kriege es nicht hin. Ich habe auch keine Ahnung vom Programmieren!!! Wäre echt super wenn du mir helfen könntest. [email protected]

Man that's dope!!!

Getting encryption right is hard!

Fuc*ing youtube, didn't receive a message ::( (Bell is checked)

"encryption encryption 192"

got kVery, very nice video. I couldn't get my head around ECDSA and the use of the random number k until I saw your video. I just need to rewatch it a hundred times or so, lol.