Recover RSA private key from public keys – rhme2 Key Server (crypto 200)
Articles,  Blog

Recover RSA private key from public keys – rhme2 Key Server (crypto 200)


We are going to learn about a weakness of
RSA, that allows us to recover the private key of an admin for a ctf challenge. This will be fun. It was also the next easy challenge after
the ones I solved already. If you know what you have to do, you can quickly
google and find solution scripts online, but I wanted to take the opportunity to look a
layer deeper into RSA. Key Server, crypto 200 points. We have received a portable assymetric key
storage for evaluation purposes. It generates and stores administrators’
public keys. Customers can use this repository to find
the public key of the admin they want to contact, and administrators can use this repository
to update their key information. If this fancy keychain passes the test, we
are going to give them away like candy, secure candy. And we have a challenge binary that we can
download and flash onto the arduino board with avrdude. Then we can use screen to connect to the board
via serial. Ok, so we get a menu with two options. First, if you are a customer you can list
all public keys. Second, if you are an admin you can update
your keys. Just sign the plaintext “admin” and more
options will be provided. The parameters to be used for the signature
are SHA1 and PKCS #1 version 1.5 And it’s pretty clear that that is our goal. We want to be able to sign the text “admin”
with one of the admin’s private keys. You can also look up PKCS #1 version 1.5 and
quickly see that the asymmetric encryption is RSA. And otherwise it basically just tells you
what the description said, that for signature you first reduce the message with a hash algorithm,
by default that would be md5 but in our case we use SHA1, and then we encrypt that hash
with the private key. Wait that doesn’t make sense, does it? encrypting
with the private key? Do you not usually encrypted with the public
key and decrypt with the private key? Well, we want to sign a message. If you have my public key, and I want to send
you a signed message, so that you can verify that I really sent it, then I can simply encrypt
my message with my private key, and then you decrypt the message with the public key. Only me with the correct private key would
be able to encrypt it so that you can decrypt it with the matching public key. And that’s how signing works with RSA. So if we had the private key, we could take
the sha1 hash of the “admin” message. And then we encrypt it with the private key. And we take the result, and give it to the
board. This way we proved that we are admin. Because only an admin with the private key
could sign the message. But how can we get the private key of an admin. All we can do is list the public keys. At this point you can google for common ways
how you can break RSA, like mistakes that can happen, because crypto is hard. but let’s see if we can figure it out ourselves
by looking at the math. At least partially. So here is the wikipedia article of RSA, and
it tells you exactly how RSA works. But first of all I like to mention something. When people ask, what’s the difference between
RSA and AES. The textbook response is, one is asymmetric
and the other symmetric encryption. But that’s pretty shallow. Maybe you have heard about how we usually
do assymetric encryption of larger messages. We don’t just use RSA. We generate a secure random key, and use it
to encrypt our message with AES. And then we encrypt this random key with the
RSA public key of our recipient, and send the RSA encrypted key, and the AES encrypted
message to our contact. Our contact then decrypts the key with their
RSA private key, and then use AES with that key to decrypt the message. We often say, we do that because it’s faster. But again, that’s kind of a shallow reason. what’s really the difference. AES is a block cipher. It basically is a glorified byte mixer. First it operates block based, it divides
the message, the data, into blocks, divides that block further and basically handles bytes. It then substitutes those bytes, it mixes
them. Of course doing a lot and way more complicated
stuff than that. But key takeaway here is, that it operates
on bytes. That’s completely different on how RSA works. RSA is pretty much basic math which operates
on numbers, it doesn’t really care for bits and bytes. Sure AES is also math. But what I mean is, for plain RSA we never
really talk about bytes or bits. We just do calculations with huuuge numbers
and that is not trivial with computers. The bigger the message you want to encrypt,
the bigger your number gets. Of course there are algorithms how you implement
those calcluations on a computer to make it efficient, but still. It’s a big difference. So let’s look at how this RSA math looks
like. We won’t get into why it works, but we look
at all the operations that are done to do RSA. So encryption works by taking the message
to the power of the key. And then modulo n. I think that’s like high school level math,
isn’t it. It’s super simple. I mean it’s kinda magical that it works,
totally goes over my head why. But I don’t care. It’s math. Somebody understands why it works, I just
know that it does work. And Decryption works very similar, you take
the cipher text, the encrypted text, and take that to the power of the other key. Of course the magic lies in the properties
and dependency of the two keys, the private and public key, that it works. But whatever. So that also means, if you take the cleartext
message to the power of the first key, which results to the encrypted text. And then to the power of the second key, you
get back the original message again. Well modulo n. Just so I don’t loose anybody here. Modulo is this clock calculation. Ehm. What is 3 o’clock + 12 hours? 15 oclock? Well, yeah, in a sane country like germany
it is. But it’s just 3 o clock again, if you take
that whole thing modulo 12. Modulo 12 means to restrict the numbers to
only what’s available in that range and you wrap around. So even though that exponentiation of the
message will be a frkn huge number, if you take it modulo this n, it will be the smaller
message again. So what exactly is the public key. Let’s have a look at the key generation. If you want to generate RSA keys, you first
need to get two prime numbers. P and q. And they have to be random. Then you calculate p times q and that becomes
what we call the modulus n. And n is part of the public key, because the
person encrypting something needs to know the n. So when n is public, and it’s just a product
of two numbers, why can’t you just figure out those two random primes? That seems simple? Well it turns out, that it is unbelievably
hard. We don’t know how you can figure out the
prime factorization of a number efficiently. If we find a way to do this easily, RSA is
dead. So now you got your public n. Next we want to get the private key part. There is some fancy math involved how you
get your private key d now, but eventhoug you don’t know exactly what they are doing
here, they only use p, q, n and e. You know n, n is part of the public key, and
you do know e, because that is also part of the public key. Mayeb now you are confused, because we only
got one number per public key from the admin list, but that’s not a big issue, usually
the public key exponent e is pretty constant, there are some typical numbers that are always
used. And the reason why they didn’t give us here
one is, because it’s a standard one. Anyhow. This means to generate the private key d,
you need n and e which you already know and p and q. Which you don’t know. So all you have to do to get the private key,
is to factorize n into the prime numbers p and q, and with them, the system falls. After that it’s just doing the calculations
right. So how could we factorize n. Based on our current knowledge of math, there
is no easy way to do that. But let’s start simple. If we would know ONE of these numbers, let’s
say we know p. We can just divide n by p and we get q.
Mh, that’s easy but also doesn’t help us much. Well here comes the point where you actually
have to think a bit outside of the box. Because in an ideal world, p and q must be
random. Also we only looked at ONE public key n, and
came to the conclusion it can’t be broken. Well if p or q were super small primes we
could probably bruteforce it and get lucky. That’s certainly something you could try. But here is one thing, we have more public
keys. We don’t have only one. If they were all perfectly random we couldn’t
break them. But what if one of the primes is the same. So two keys share the same p? By coincidence, or because of bad random generation. The thing is, we know an efficient algorithm
to find the greatest common divisor, GCD, of two numbers. It’s also known as euclid’s algorithm. This algorithm is over 2000 years old. It’s always blowing my mind what kind of
crazy stuff people figured out long time ago. I wish I were this smart. Euclid didn’t even have the internet, and
I can’t even figure this out today. Anyway. His algorithm can, given two numbers, find
the greatest common divisor. Of course only if they do have a common divisor. So if you have two numbers, it can find the
value that can divide them both. See what I’m getting at? If two public keys have one random prime number
in common, then this prime number is the common divisor. So if one public key is a times q. And the other one is b times q. So they both share q, then euclid’s algorithm
will find q. So let’s try this. We just have to implement this. So we loop over all keys, which obviously
has to be converted to a number not a string, and we try to find a greatest common divisor
and print the result of gcd. Obviously if the greatest common divisor is
1, then that’s not the prime, but look here. Gary and Bob have a greatest common divisor. And as you know that divisor is already one
of the primes. We got everything we need now! Because Dividing the public key n by this
q, we get p. So we now got n, p and q. Only missing is the public exponent e, but
that one has, as I already told you, some typical values like 3 or 65537, you may have
seen these before. So we just try them all. Now we just have to perform the math as described
on wikipedia. D is the modular multiplicative invese of
e module phi(n). I just copied a modular multiplicative function
from the internet. So we can do just modinv from e and phi(n). And what is phi(n). phi(n) is just n – (p+q-1)
Easy. Then I just use pycrypto to do the RSA signing
for me. Just check the documentation how to use pycrypto. First we create a key object from the values
we now know. And then we use the PKCS1_v1.5 class to sign
our message. Which is the sha1 hash of admin. So we just run this, we get a couple of possible
sigantures. All for different e’s. Then we try them, aaand, there we go! The last one was the correct e. Our signature is accepted and we get the flag.

66 Comments

  • cyancoyote

    It's so unbeliveable that people are smart enough to create things like this that just work. It always blows my mind…

  • Nirmal

    Reminds me of RSA challenge which I faced in a CTF and I had no idea how was this RSA thing working but thanks to you. I got clear concept about RSA 😃

  • Gego/XAREN ゲゴザレン

    If you want to understand cryptography and RSA and Public Key Cryptography I recommend watching the "Gambling With Secrets" and "Lanuage of Coins" episodes from Art of the Problem here on YouTube.

  • クリスチャン

    I heard about some news that the "Shor Algorithm" will be able to crack all Public keys Encryption methods but you'll need a Quantum Computer for that which nearly nobody has.

  • John Undefined

    But you could use RSA the same way as AES. Break the message up into blocks according to the modulus. I see you talk about the difference. But you dismiss actual differences as "shallow." And then you claim a "difference" that is no difference at all.

    Though you may dismiss this as "shallow" (you seem to dismiss all actual differences as "shallow") the fundamental difference is that AES is designed such that the information needed to encrypt is the same as the information to decrypt, while in RSA the ability to encrypt will not also allow you to decrypt. Reversing the algorithm is computationally hard.

  • wgm4321

    Nice presentation. It was easy to follow. Here is a recent video on the RSA maths but it is not, for me, easy to follow.
    https://www.youtube.com/watch?v=12Q3Mrh03Gk

  • Rafael Arriaga

    The technical aspects still go over my head, I'm new to this. But your thought process man, that's gold. Thanks for sharing and keep it up!

  • Calm1

    Regarding Euklids Algorithm: Check out PBS Infinite Series if you haven't yet. They just released a great video explaining it, absolutely worth the time watching!

  • Brett Salmiery

    You are the man. Great video again, as always. I would have never thought to use GCD. Just curious, did that take a long time to compute the GCD, or was that result real time?

  • Joseph Vannucci

    Well done video. I am working with a vendor that is both a repository of public keys AND provides that key generation as a complimentary service.  I'm interested and a bit fearful of the results of this experiment on their keys.

  • Grégory Lefevre

    Is there a way to recover our private key of ETHEREUM address with our public Key ? I loose my backup. My funds are on Etherdelta's platform and i already try to go into google's development tool => application tab => localstorage to check if they were the key value of my private key but no in fact. No other way to find it? because otherwise i loose a lot of money.. thanks for your help if its possible

  • rafid mhaskar

    Seccon 2017 had a same type of ctf problem, and it was the first ctf problem i had solved on my own, your videos is where i started my journey into RE and ctf and stuff. Keep up the good work.

  • Michael Lin

    What are the chances of two public keys having the same random prime in a real life setting? Like, given 10 randomly sampled public keys from a given keyserver plus one that we want to cryptanalyse, how likely is this to happen? There has to be a certain keyspace for RSA given that the keylength is just the length of n.
    To get anything, I would imagine that we would have to exhaust every combination of two public keys and the gcd() function just to find anything. This come to be O((b^2/2)-(b/2)), where b is the number of public keys in the directory (worst case scenario, big O).
    If we were given 10 public keys, we would attempt 45 combinations. 100? 4950 combinations. Note these are all worst case scenarios. In real life, I think b would be much, much bigger.

  • TheGrimravager

    high school level ?
    maybe, but explaining how it works.. pfft I took codes and security.. unofficial prerequisits: functional analysis, group theory, algebraic structures and linear algebra.. third year physics elective
    edit: but I was able to implement my own RSA encryption algorithm and code it such that a mathmatician could understand it

  • Madushan Nishantha

    What am I missing here? It looks like GCD is way faster than prime factorization, what stops me from collecting a lot of public keys on the internet(say from SSL certificates) and try to brute-force and at least get factors for few of them?

  • Cihan Erdem

    Hello, i have public keys and i want to know if i can create private key from those public keys which can decrypt my encrypted files ?

  • Ático Records

    Guys sorry to bother, but can anyone help me out with a ransomware situation? All my files were apparently encrypted. Encryption was produced using unique private key RSA-1024 (as the ransom note claims)

  • Nicholas Pipitone

    @liveoverflow It's really not black magic, I mean the proof is quite short. d was calculated as invmod(e, (p-1)(q-1)), so d*e = 1+(p-1)(q-1)*K. Now, you're done by Euler's Theorem. (That m^((p-1)(q-1)) = 1 mod pq).

  • cabinboy1031

    About the two prime numbers bit.

    If you figure out how to find two prime numbers easily. It wont just be RSA thats dead, a LOT of things can be solved as soon as that simple breakthrough is found(as far as i know) the whole P=NP problem right?

  • Silica

    Couldn't you also try changing the public key in the application to one that you know the private key for then just sign it?

  • Rena Kunisaki

    I think this is the same mistake Sony made with the PS3? Reusing Q for two different signatures, allowing people to compute the master key?

  • typedeaf

    Awesome video. Going to have to watch it again to digest it (unintentional crypto pun.)
    Tip: put a hyphen between bullshit and free, ie. bullshit-free, or else it might imply that is is both bullshit and free, instead of being free of bullshit.

  • Puran Yadav

    sir my pc data corrupt from virus and readme massage for private key in 0.08 bitcoin .so help me about this

  • My Keyboard

    For anyone using python 3+ you will want to do q = n//p since one division operator results in an approximated float and will lose some precision resulting in a wrong q.

  • Ahmed Habib

    Decipher RSA:
    For example 12345 reverse it
    54321, minus 54321-12345 every time take mod of result now devide by 9 repeat process until you get zero last value before zero is key to decipher this algorithm.

Leave a Reply

Your email address will not be published. Required fields are marked *