TLS Private Key Recovery

okay okay can i start oh good yeah go ahead okay thanks so the thanks besides for having me today this session will i will talk about the rsa private key recovery in a tls session which is transport layer security um i did that study a couple of years ago let's say one two years ago because i was interested in the cryptography parts of the rsa algorithm and this presentation i will show you how to recover a private key from a dls session so maybe in short because time is limited i'm a security researcher and a security specialist from belgium at the bottom you can see my email address so if you want to be in contact

i'm linkedin as well and if you have questions regarding this presentation you can always send me an email and i'm glad to answer you all your questions now before we start first a little mad because this is really important to understand how the the rsa algorithm works this will just take a couple of minutes but during my demonstration i will come back to this so it's uh just a quick overview on what is what is all these uh the definitions so um in math we have uh yeah we have here an integer so which is a collection of positive numbers yeah positive numbers is one two three four five and so on uh a factor is basically an integer is a

factor of c when there is another integer b that complies with c is a product of a and b so this basically means that if you have the number six this is a product of two numbers because later on in my demonstration i will use a factorization to calculate the two factors of my prime numbers then what is a prime number that's an integer is prime but it can only be divided by one in itself and not by a num but not by an another number so let's say four is not a prime number because it can be divided by two but five is a prime number because it can be divided by 1 and itself

now the modulo is a remainder of an entire division uh this is an example if you divide uh 10 by 4 then you have a reminder and the reminder is 2 that's actually the example that i gave here and a co prime that is a number that is no factors in common with another number so and uh i come back on this later uh in the next slide the audience the total fee n is the amount of integers less than or equal to n and you are co-prime so this means the total of nine is six and six is the amount of prime numbers and there is no common factor between the nine and the prime numbers between

the brackets so there is no common divider and that is actually uh the definition of the call prime and that is really important in the rsa algorithm because if uh numbers are call prime then there can be a common divider and you can easily calculate the private parts of the prime numbers now what is factorization factorization is a process of decomposing an integer into its prime factors so as i explained earlier uh if you when you have a number this is just a number six you can divide it in two numbers which are two and three and two and three are the are the factors and the factorization is basically the process of calculating the two prime

numbers from one number and that's what we will do in the demo as well and the greatest common divider that is a number a largest integer that divides each of the integers so this means when you want to calculate the greatest common divider between 60 and 48 you have 12 but you have other numbers of slow but in this case the largest integer is 12. this can be important when we calculate the greatest common dividers from public keys when they are available on the internet okay this is the mathematical parts i know it's it's very quick but again time is limited and i want to demonstrate some the the most interesting parts of this study and this

is of course the calculation of the private key now before we start going in that what is rsa rsa is an algorithm that is that is based on asymmetric encryption and is founded by three guys in 1977 so it's a quite old algorithm ethic encryption means that you have two keys and we call it a key pair and a keypad consists of a public and a private key so it means that the rsa algorithm will generate two prime numbers and each prime member is part of that key and the private key needs to be kept right and the public key can go public but more on this within a moment it is very important that a security

identity at its o key pair a security identity can be a web server it can be a workstation it can be a website it can be a user because we can use asymmetric encryption to authenticate a user or a system on the network i said before the keys are based on prime numbers but it's important that these prime numbers are very large because if prime numbers are small then we can use factorization to calculate the prime numbers and based on these numbers we can easily calculate the public part and the private parts another interesting case is that when a prime number is generated on a system that it's randomly the question is of course what is

randomly um that is not what we will discuss here but you have to trust your random number generator finally all that material generated by a tool or your own application is stored in a pen file i will demonstrate this at the end of this presentation um how that looks like a pen file is a basically a base64 translation of an certificate file a certificate file is also an x 509 version 3 file but again more in one of the next slides now the key generation process how the rsa algorithm calculates the keys that is explained here so first what we need what we need is very large prime numbers and a tool will generate the prime

members for you it can be open as a cell it can be a switch it can be whatever device that generates the prime numbers with a certain key size and the case size can be 512 1024 bits and more so in the rsa algorithm we have two prime numbers and we call them p and q p is a prime number and q is another prime number now from these two prime numbers we calculate the products and the products is named and and this is basically the modulus the modulus is also part of the certificate but we all will what i will discuss in one of the next slides in the beginning we just give the definition of the tortions and

here we will calculate authorities which is a prime number which does not have any uh prime numbers in common and these tokens is based on the two prime numbers calculated before next is we generate another prime number e which is the public or encryption exponents as i discussed earlier uh rsa is based on two numbers on two keys a public and a private key so we will encrypt information with the public key and we decrypt the information with the private key the public part or the encryption part is e and these are the the values so it must be greater than one but less than the torsions that's the reason why we had to calculate the

total before now a typical size of e is uh 65 537 um which you can find in most of the certificates when you buy them on the internet the next part is to calculate d and d is the private part or the decryption component as you can see to calculate d it's the inverse of the public part modulus the total value okay you don't have to remember this but it's just an introduction about how the rsa algorithm works and how the keys are processed so to continue the public part or the public key of my rsa algorithm is the modulus in combination with the public exponents which is my e and the private key is the modulus with the private parts

so the e was my 65 000 and so on and d is a private number it needs to be private so it needs to be stored securely on your system whatever that system is okay now what does this means in practical we cannot do anything with all this key material because our operating system will do that for us so we need something to work with and this is basically a certificate a certificate is a representation of a security identity and it basically it contains a public key and or a private key a certificate can be generated by using an internal certificate authority or you can buy a certificate from an external party like globalsign rapid as a zell let's say

encrypt and so on when the key material is generated you need to generate a certificate signing request this is basically a file which contains some public information like what is the email address uh what is the fully qualified domain name of the website what is the it departments and so on and all that information is used to digitally sign a certificate in the certificate what can you find in a certificate you can find the public key and you can find the models i will show that to you within a moment when a certificate file contains as well the private key then they call it a bfx file or a p12 file [Music] a certificate can be used for server and

client authentication i will use a certificate for server authentication which is assigned to my website to my web server so when a client connects to a web server it downloads the certificate from the web server it verifies the validity if it's the certificate is valid and then it will check the certificate revocation list to verify that the certificate is not revoked then finally the client will generate a symmetric key and will use asymmetric encryption which means now the public key of my web server to encrypt my symmetric key and it will send it to my web server the web server will use its private key to decrypt the information and then now has the same symmetric key which was

previously generated on my client side and then finally we have a secure channel between the client and the web server and this is then based on transport layer security whatever version you have one one one or one and two in my demonstration i will use tls 1.2 to secure the traffic now this is a briefly overview on how tls works so first my web browser my client will send a client hello message to the web server with the question hey this is all the cipher suites i support which do you support the server will send its certificates and will also send a list no not a list but it will choose one of the selected ciphers which was previously

sent by the client and then sent its certificate back to the clients when they both have an agreement they have the algorithm used or selected to encrypted information and then finally the https connection is set up now this is an example of a client hello message so uh here you can see a list of all the cipher switches that my client sends to the web server and then on the next slide we can see the answer of the slide of the server and he will send or select one of the cypher suite so in this case it's tls rsa the rsa algorithm and so on now what does this mean this is a breakdown of the selected

cipher slitter so the first part is the transport layer security the protocol used to secure the information the second part is the rsa algorithm for key exchange and authentication the other part is we use randall encryption or ias encryption as a symmetric key which is 256 bit length then we have the counter mode in this case each gcm you have also a cbc uh an ecb electronic code book and then finally we have the mac which is the message authentication codes and it's based on sha 384 okay now during my study um i found a lot of vulnerabilities now did i found them by myself no because i previously i i've searched on the internet about

known vulnerabilities in the rsa algorithm and there were some other people that did some work before but only from the mathematical part what i did is i translated the mathematics that other people did into a python script and that python script contains these vulnerabilities now what we will discuss or demonstrate today is only the first one when the rsa algorithm generates prime numbers which are close to each other that's what i talked before uh that you have to trust your random number generator the random genre number generator will generate prime numbers for you and the the num the numbers must be uh far from each other another one is a common factor and this means that if you generate two prime

numbers that one of the true prime numbers is common and this can be a huge problem uh when certificates exist on the internet it means that somewhere a prime number is generated and on the other side of the world other prime numbers are generated but one of the two prime numbers is the one that was generated before and there are other vulnerabilities as well which are all available in the scripts the script is not yet publicly available but it will in the next couple of weeks or months now um for my demonstration my tool will generate prime numbers which are very close to each other and the size of the prime number can be 512

or 1024 bits the size of the modulus is then the product of these two so this means if my prime number is 512 bits then my modulus is 1024 bits if my prime number is 1k then my modulus is 2k here we can say in the formula when the prime numbers are very close to each other that the prime number are equal and then we can use for fermat factorization to calculate the two prime numbers when we have the two parameters we can easily calculate the total and next part is to calculate the private exponent of my rsa algorithm okay this is a screenshot of my tool but i will demonstrate this life using virtual

machines now uh in the demo what do i use i use python3 i have my script i use yafu yafu is a tool that i use to for factorization which is a tool to calculate the prime numbers based from the modulus and i use open ssl to convert and to generate some key material okay

i have some virtual machines i have a windows server an iis which contains a website and i have my clients with my tool available which is here you see there are there are several options that you can use to generate some faulty key material and then finally you can use the recover option to calculate the private keys and the output will always be a pen file which contains the private key of one of these vulnerabilities so i will give you the process how what i did before and then i start the to demonstrate the vulnerability so what i did before is first you need to generate some key material and the comments that i use

is generates false primes bit length let's say uh 1024 bits and then the output is a file let's say server02.10 the tool will now generate prime numbers which are very close to each other this is my server2.pam you can have you can see the content by using openssl rsa

this is my base 64 information it's what i explained earlier in slides that the pen file is base but we can easily translate this into text and then you have this so this is the modulus which is n the product of the two prime numbers this is my public exponent e this is my private exponent and these are the two prime numbers so you can see these numbers are almost the same except here for the last two bytes let's say okay now when you have a pen file the next step is to generate a certificate request because our goal was to ask or request for a certificate which contains the public key so the next part

is basically these command open ssl request new i need a new key which is my server and then the output will be a csr then you need to fill in some information so you can specify the country name the uh the states the locality name uh the organization name so in my case it's a a fake company called whitehead security organization name i.t the common name is very important because this will be the fully qualified domain name of the website so in my case it will be white hat security dot b e and then the email address your one ad white hat security dot be a password [Music] it's optional and then the output is a

css file that css file that's something that you can use to uh buy a certificate or to request a certificate by let's say crypts the css file contains as well the public key because our result will be a certificate when you bought or when you request a certificate from let's encrypt you have a set file and then you need to combine the public key with the private key to generate a pfx file and then you can install that file on your web server so that's what i did before so i bought a certificate based on faulty gamer material and then i have a certificate of mine for my website when i double click on the certificate you can see

here that it's issued to whitehead security.be it was digitally signed by rapid tessell it's valid up to next years and i have the corresponding private key because we know that it's based on the rsa algorithm and we have a public and a private key the details uh yeah we have the fully qualified domain name and here this is the public key the public key is my modules which is n and then we have other information this is elected a legitimate certificate because it works but it contains only faulty material okay to demonstrate the vulnerability to calculate the private part of this key because the private key is somewhere located on my web server and from the

attacker's perspective i want to calculate the private key to decrypt my tls session so i go back to my uh to my machine i remove my files that i've generated before because i don't i don't need them anymore what i do now is i need the public key of the certificate from that specific website how do i do that i can use my web browser or i can use ssl to connect to that site with the following comments

output will be written into a file i will do that in i will export that in a text file not as a certificate and i will name the file server 2 dot pen okay so what is the output the output here is server2.pen which is my public key to view the contents it can be easily done with with these commands oops it's not rsa it's uh x5109 because it's a certificate file so if you can as you can see here you see now the details of the same details of my certificates which was available on my website because it is digitally signed by rapid ssl this is the public key which is let's say pretty secure because it's

2048 bits this is the modulus this is my exponents my encryption exponents e and then we have additional details about the dns name full qualified domain name who has signed the certificate and timestamps and and so matching information and so on this is my certificate which is basically my public key now for us it's uh the most interesting part is to calculate the private key before i can do that i need the models and the models can be retrieved by the by using the following equipment and now this is the modules as you remember from the beginning of the presentation the modulus is the product of the two prime numbers i copy this and now

i can use factorization to calculate the two prime numbers and to factor for factorization i use the tool yahoo and then factof zero x because it's an hexadecimal number this will take let's say uh 30 seconds in my case or maybe a minute and the result will be two prime numbers so let's wait until the numbers are calculated they are here and as you can see these prime numbers are very close to each other only the last four digits are different and this is one of the vulnerabilities which currently exists in the rsa algorithm now i can do anything with this i now need the private key now calculate the private key i use my tool

so what i do now is python and then my script now i use the switch recover closed lines and then the first prime number is that number and the second prime number is this number and then i want to write the private key of the known public key into a file called server02 dash recover and it's in a written into a pen file so now the tool used the two prime numbers to calculate the private part of my public key and then i have now a file called server two dash recovered which contains my private key okay let's now connect from a web browser to our server so i open here in this case microsoft

edge before i connect to my website first i start wireshark because i need wireshark to decrypt all the information

okay then https whitehead security.e and what is the website the website is just a basic website and it contains a login page where you can type in a username and then a password

it's ssl or transport player security so i'm sure that all my personal information is encrypted when i click on login i'm logged in and that's it i can see other stuff now for us the most interesting part is to first filter the traffic between the clients and the web server as you can see here it is all encrypted by use of tls transport layer security version 1.2 as i explained earlier in the slides you can see here the client hello packets with what's sent by the client and it contains a list of all the cipher switches that the client supports and they are listed here and then the server will send a server hello packet

with the selected cipher switcher and it will also send the public key or the certificate to the web to the web clients to my clients and then there is a key exchange the login page is displayed i type in my username and my passwords and all the information is encrypted now as i explained before we had a vulnerability in the rsa algorithm means that the close numbers the prime numbers are very close to each other i can now use my pen file which i created previously to decrypt all this information so i right click protocol preferences rsa list i select here the the ip address of my web server the port number and then this part is a key file and the key file

is my recovered uh private key this one open okay and now my tls traffic is decrypted and you can you can now see the name and the password in clear texts so this is one of the vulnerabilities which currently exist in the rsa algorithm there are others as well but yeah during time constraints here we have only 45 minutes so there are other as well and interesting as well but this gives you an idea that when the key material is not correctly generated that you have a vulnerability and the vulnerability in this case is that the private parts of the certificate can easily be calculated when you have only access to the public key and then you

can decrypt all the tls packages now what can you do to avoid this that's my conclusion and don't use tls 1 1.1 and 1.3 anymore because in tls 1.3 rsa is not supported because all of the known vulnerabilities in my case or in most cases the rsa algorithm is used for key exchange and this is now this is not good for the tls traffic so in that case it's better to use elliptic curve diff diffie-hellman it means that instead of using these these prime numbers in the key material that it will now use temporary key material and it will change during every session which is more secure but if your applications or your web server

does not support uh other algorithms and you have to use resale then you have to be sure that the prime numbers are very large enough because if they are very large factorization is almost im not possible and make sure that the prime numbers are random and this is the most difficult part because you have to trust your random number generator and you do not know upfront which numbers are generated so this is maybe some uh food some thought for developers to to keep in mind if my tool or your tool use need to generate prime numbers that they must be randomly enough okay or there may be any questions thank you very much for your talk it was a really

interesting study is there any question

i haven't seen anyone popping up about the um as we have you know time um i've got a couple of questions actually for video yes so first of all you know the um really great presentations i appreciate you know your time today that was super cool you know what you're showing here so what you were talking about the um that you need the two prank numbers to be close enough so i wonder if there is any actual you know quantitative value you know for that close enough right because i my understanding if you know the if they are not close enough you know your two is going to take longer to execute or is this a specific value

where you know that proximity you know stop working yeah um when you generate prime numbers they have to be not close enough to each other but they you have to be far enough uh far away from each other so let's say if you ask on people in a room give me two numbers one person will say one and 99 and one per another person will say four and five so in that case when the prime numbers are close to each other you have the vulnerability and you can use factorization to calculate the private part so it's important that the prime numbers are far from each other because when they are close then you have a problem

cool and how you can see the scanning the internet you see this is a um this problem has been seen in a while in the in the past have you said about it yeah um that is basically for another presentation but i'm i'm i'm involved into a project which is called uh sonar as a zl this is part of uh rapidly repeated rapid seven the developers of metasploit and other tools so they they have some certificates available and i'm currently running another project to calculate the greatest common divider between certificates from the internet and when there is a common divider between two certificates again the private part can also be calculated but that's something that we that i have

to do in another presentation because it meets at at least one hour or more very interesting

awesome so if there are no more questions so thanks johan for for your presentation it was great i really appreciate you know your your time today and now we have a break of 15 minutes so see you all in in if you think okay thank you for listening to me i hope it was interested interesting and uh yeah it's it's something that we as security professional do not think about but um when key material needs to be generated even for a medical device or from a an iot device where the key space is very limited keep in mind that when generating prime numbers that they are very large enough and randomly enough thank you