Modification of the prime generation method of the OpenSSL library
Formal Metadata
Title 
Modification of the prime generation method of the OpenSSL library

Title of Series  
Part Number 
07

Number of Parts 
29

Author 

License 
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. 
Identifiers 

Publisher 

Release Date 
2015

Language 
English

Content Metadata
Subject Area  
Abstract 
Random numbers are very important in many fields of computer science, especially in cryptography. One of the most important usages of pseudorandom number generators (PRNG) are is key generation methods for cryptographic purposes. In this presentation a modification of the prime generation method of the OpenSSL library will be presented. The modified version of the library passes every wellknown statistical tests (e.g NIST test, DIEHARD test), however while an adversary is still able to reconstruct the prime numbers (P,Q) from the public key. The method can be used for malicious purposes as a sophisticated backdoor. The presented research is based on the theory of kleptography and a recently published research paper.

Related Material
00:00
Statistical hypothesis testing
Presentation of a group
Message passing
Topological algebra
Interior (topology)
Insertion loss
Endliche Modelltheorie
Topological algebra
Cartesian coordinate system
Prime number
Library (computing)
Prime number
01:01
Statistical hypothesis testing
Ciphertext
Presentation of a group
Source code
Set (mathematics)
Insertion loss
Instance (computer science)
Open set
Solid geometry
Public key certificate
Arm
Computer programming
Medical imaging
Estimator
Insertion loss
Vector space
Library (computing)
Physical system
Presentation of a group
Source code
Open source
Bending
Sound effect
Nonstandard analysis
Statistical hypothesis testing
Statistical hypothesis testing
Proof theory
Oval
Uniform resource name
Order (biology)
Normal (geometry)
Encryption
Whiteboard
Information security
Arithmetic progression
Electric generator
Slide rule
Random number
Implementation
Topological algebra
Random number generation
Open source
Algorithm
Real number
Online help
Topological algebra
Number
Statistical hypothesis testing
Advanced Encryption Standard
Centralizer and normalizer
Vector graphics
Computer hardware
Implementation
Topological algebra
Key (cryptography)
Consistency
Cartesian coordinate system
System call
Prime number
Number
Function (mathematics)
Computer hardware
Universe (mathematics)
Key (cryptography)
Local ring
Library (computing)
06:39
Statistical hypothesis testing
Context awareness
Length
Mountain pass
Multiplication sign
Source code
Combinational logic
Function (mathematics)
Open set
Subset
Medical imaging
Mathematics
Encryption
Library (computing)
Metropolitan area network
Block (periodic table)
Cycle (graph theory)
Closed set
Menu (computing)
Streaming media
Bit
Sequence
Statistical hypothesis testing
Data mining
Proof theory
Frequency
Uniform resource name
output
Normal (geometry)
Cycle (graph theory)
Slide rule
Random number
Functional (mathematics)
Random number generation
Algorithm
Computergenerated imagery
Maxima and minima
Topological algebra
Bit
Number
Element (mathematics)
Statistical hypothesis testing
Sequence
Advanced Encryption Standard
Population density
Internetworking
Operator (mathematics)
Loop (music)
Execution unit
Shift operator
Topological algebra
Inheritance (objectoriented programming)
Length
Content (media)
Expert system
Binary file
Prime number
Number
Software
Circle
Function (mathematics)
Vertex (graph theory)
Table (information)
Library (computing)
12:02
Statistical hypothesis testing
Manufacturing execution system
Primality test
State of matter
Mountain pass
Multiplication sign
Decimal
Sheaf (mathematics)
Open set
Prime number
Mereology
Integer factorization
Subset
Neuroinformatik
Formal language
Medical imaging
Feasibility study
Personal digital assistant
Moving average
Endliche Modelltheorie
Library (computing)
Factorization
Metropolitan area network
Algorithm
Bit
Mereology
Publickey cryptography
Message passing
Malware
Uniform resource name
Right angle
Modularithmetik
Resultant
Polynomial
Slide rule
Random number
Multitier architecture
Topological algebra
Random number generation
Open source
Algorithm
3 (number)
Limit (category theory)
Topological algebra
Law of large numbers
Number
Hexagon
Internetworking
Glattheit <Mathematik>
Modal logic
Topological algebra
Electronic data interchange
Sine
Planning
Integer factorization
Prime number
Key (cryptography)
Integer
Library (computing)
17:16
Random number
Primality test
Open source
Algorithm
Code
Mountain pass
Multiplication sign
Combinational logic
Limit (category theory)
Prime number
Rule of inference
Law of large numbers
Arm
Neuroinformatik
Number
Integer factorization
Internetworking
Glattheit <Mathematik>
Library (computing)
Social class
Physical system
Publickey cryptography
Statistical hypothesis testing
Prime number
Oval
Uniform resource name
Selforganization
Modularithmetik
Integer
Laptop
Library (computing)
Wide area network
19:08
Statistical hypothesis testing
Implementation
Random number generation
Observational study
State of matter
Maxima and minima
Set (mathematics)
Open set
Public key certificate
Statistical hypothesis testing
Number
Measurement
Sequence
Order (biology)
Crosscorrelation
Different (Kate Ryan album)
Ranking
Endliche Modelltheorie
Library (computing)
Mathematical optimization
Condition number
Physical system
Scalable Coherent Interface
Newton's law of universal gravitation
Domain name
Area
Metropolitan area network
Standard deviation
Distribution (mathematics)
Public key certificate
Physical law
Interior (topology)
Bit
Binary file
Cartesian coordinate system
Measurement
Prime number
Orbit
Message passing
Word
Frequency
Personal digital assistant
Crosscorrelation
Uniform resource name
Normal (geometry)
Key (cryptography)
22:34
Slide rule
Server (computing)
Presentation of a group
Functional (mathematics)
Observational study
Source code
3 (number)
Client (computing)
Prime number
Public key certificate
Event horizon
Computer programming
Metadata
Number
Integer factorization
Neuroinformatik
Mach's principle
Endliche Modelltheorie
Library (computing)
Domain name
Lattice (order)
Peg solitaire
Publickey cryptography
Prime number
Number theory
Personal digital assistant
Tunis
25:07
Statistical hypothesis testing
Musical ensemble
Statistics
Random number generation
Topological algebra
Digital electronics
Source code
Insertion loss
Topological algebra
Parameter (computer programming)
Open set
Prime number
Public key certificate
Computer programming
Number
Supercomputer
Neuroinformatik
Integer factorization
Order (biology)
Strategy game
Operator (mathematics)
Information security
Library (computing)
Physical system
Curve
Information
Cellular automaton
Binary code
Plastikkarte
Cartesian coordinate system
Variable (mathematics)
Offenes Kommunikationssystem
Publickey cryptography
Prime number
Number
Personal digital assistant
Normed vector space
System programming
Local ring
00:01
welcome ladies and gentlemen my name is not working and then I was looking for the Hungarian as the model 7 years and I was responsible to make precision testing and people license and then they do some some researchers relating to prime number during and right now I'm messages secreted by the as an indirect company has a consumer Tshirts this is green Tshirts as you know we didn't have such kind of school teacher in the Hungarian inner city communities was the 1st reason might just set the company on narratives presentation and I'm just would like to show you how to hide some big loss and hope to make some malicious called or the Generations methods and how to identify the schools and often that's how to implement in practice these and that those and applications of prime Number generation approach and in uh but most of them and the generations are the general
01:05
background of the research can be shown in the slides and the main concept of this presentation is based on the following research is that you can see in the slide that such and that to Rafi so on generation and this presentation also presented in the Central European Conference on people the best we can do mathematical but runs and right now we implemented the called and right now we would like to show you how to implement in the real world peace and help to make some 6 certification call to implement some sophisticated bend loss on random number generators come and this such and is therefore projectionbased goes into some a random number generators some visited this research start reading the armor of the 100 ns and WriteNow which try to implement all of the courts and then this is the main reason we would like to show you how you can delete and after the presentation you can also get the source of these onwards and implementations as you will open
02:15
and it's in the number of open source applications and using a corpus of library and the universe friends open SSH our or current standards and that all of these application is very important to emphasize that some of these applications are built on the set of open source so fully means if you can make some endorsing this library or on you can you can implement new techniques that use open a salivary after that there's a chance to highlight some loss of course it's also easy because as you know know there subjects found from the library and there are many many different how to prevent this kind of images that we saw the main question needs as and try to try to show you my presentation that is it possible to hide the bed or online libraries for example everybody knows that RSA for ASR is well known for effect would be expected so that means that if you would like to make some some Bible so that for example in a clothes if you know how does it work if you know uh was I which is do and you have some receptors so lazy to identify that goes for example in an antigen and what it means as you can see in the slide for example you have encryption key you have into this summer you have estimate the year cyphertext and if you know whole year solids is working on you can make some tests there is an no reasonable it's working or not if that alter these defines then the simple that's then it means that maybe there is some that or on yes always or that is some programming mistakes on the wing so it means such kind of test of course a proof of concept that the modifications have been made for example on ways and it's very difficult to the height an that or in the yes and the alignment which onwards so this was the main idea that's and modification as an intrusion on which there is to have more sophisticated that so what about random number generators and as you know the number of tests that pass it means because and the behavior of random number generators is to produce a true random numbers of course if you're using only such that the progress itself normal number generators but of course you can try to me but it was really about random numbers however you have to to use some statistical tests by the National consistent and those that want to test for the diehard tests in order to define and the local board in order to test the if you would like to modify it is noticed that he means and as I mentioned in the previous slide so if you're using a yes doesn't cost that's working on a new random number generator metals because they're notice that costs you can identify the malicious called upon the random number generators just the ground that's imaging of them is an embedded system there are some hardware random number generation on them and that system and you don't know the source told you not only the all of the random number generator and it is shown the number generated passes all statistical test by the news that I have that it should be used on the number generated and you can do nothing in these so as you can see the main idea hope modified accessible random number generator uh for example in an open society I believe it's actually dead set on the modified local steel policies on statistical test I mean if I modifying random number generator which is also a statistical test if not of course it's people often enough people difficulty not set so this was the main idea and then they try to make some mathematical background we can this topic and they try to try to to implementing practice so the
06:42
first one is just I presented in a sentence vertices and there is down and that's how to use this kind of mathematics and reading the number going to hide some vendors until the random number generator um hands off to get you can identify that there have been lost in the random number generator so as you can see in the slide that so let be defined it so long number generator and maybe I did not then I'd be clench binary sequence and then let us define the following function as you can see the BI and I would like to go into details and that's where important so we this topic that at all and that there exists a polynomial time are going to have to do your friend very and that's the DDI either 0 it means and that's observing 118 minus 1 and considered this from the output of that so the random number generator it is possible to predict the next big with 100 % of success is very important as and 100 % of substance so it's all it's very easy to create such kind of operating
08:11
all in this slide there is a proof of concept concept already written to that AES it's good to see itself and Picheny yes and this is at the you'll see proof of concept of and as you can see in the slide so he was a seed he's an alias encryption it's a combination of the content 1 and the CBC more and as you can see in the slide so that all shift there and that is a new input for the next block as you can see that I will get that see because that is also a CI of just 1 so that the density this 1 and this he's only this 1 so that does see I was once you get to the end he of the uh and this as you can see the policy and here is the next 1 well and there is no weights and so it means if I'm using this kind of cycle and using this kind of content of it can be proved that the size and length of their self and antigen AS and his mining deals 128 bits uh and that is known to have in the content in such a way as you know AS is designed in such a way that tried to pass on of norm where no specific context like the National Institute standard of technology has been used as ordered I have test so it means if you are including the so the random number generator OK in such a way that network is almost at table and that will the end of the existing be distinguished from 2 numbers to random numbers only by statistical tests so if you have source close if you know how this solve it is working you can predict the next big with 100 per cent of subsets however with only statistical test tests I have to emphasize that only statistical test you cannot distinguish from 2 random numbers and it's very interesting and leading to the proof of this proof of concept barbarism that there is a very important corrolary as you can see in the slide so if you want to observing the holy because you have to to observe you know density of the cost of the internet seed of the random number generator you have also policy 100 and it is we use so it was too much to the most of their parents next did so it means uh as you can see in this proof and that's the consecutive epoch ICI and CAI this 1 is 256 bits of verse elements can be found 383 if you just so that the 2 D image in this scanner so there is a slide that is because and you can check that 258 each of can be found only 300 it distributes relating to it's only just a proof of concept called so if someone tried to implement this close in openness library is not a sophisticated because if you are if you have a rival and that there is a separate the experts and the 2nd expect just try to check these on the notion of contaminants CBC mode of and they saw what it's like to definitely identify the malicious activity in the education that of however
12:05
and it's very interesting that's we just make some of mapped modifying them open as such as a library and they tried to modify their internal state of the Prime Number Generation as you know if I'm trying to modify the plan and Generation presently opens library after that there are some statistical tests that have to pass possible the old so that means if I'm doing some that prime numbers and so on and so on and after that they were really going to have qualified and we don't want to passes or statistical testing open library so you have to be very careful when you're modifying the prime numbers generation of of of the open source library In this operates and you can see that it's an interesting algorithm that's you are just searching prime numbers less than the binary and so the embodies a thousand and twentyfour so it means you just multiply together prime numbers less than 100 thousand and as maybe some of you have heard about that so in 1947 John Burnett true that's it it possible to surprise with large numbers in polynomial time if for example if it's crimes factors might be minus 1 or minus 1 has only a small profit for smaller patent this means for example less than 100 thousand as is seen in the previous section this side so it means if somebody would like to make such kind of sophisticated breadboarding t to prime number generation and the values for example these techniques and the the generates some prime numbers and after that they can check that how many how many thank you and OK so after that you just generated some of prime numbers you can test it these tests and other sophisticated statistical test and all well known statistical test it means any metal that's implemented in opensource library not identify the and that measures that grants activity is going on in the cold in this slide you can see that so just want because the public key and adjust the generated that public key which all modified corpus library and after that we just published a public key to everybody and then as you know it's a 2048 bits of public key and so it's almost the feasibility to surprise however if you are using such kind of bad because you are if you are using such kind of malicious uh random number generators is it possible to reconstruct its prime numbers the a mistyping this slide can feed and this is the public key of the previous probably keep this is about number of data and models from this public key of course it is the 64 encoded mention of the public key and this is that and modernist decimal number is 2 thousand 40 number and then we just generated in such a way as I mentioned to you we jump on techniques and because we would like to constant the private key from the public key so I would like to emphasize that after that is it possible to the cost of the private key from the public key and of course and if you're using 1 statistical tests you cannot find any animations of the feeding on the numbers because there are no such kind of activities
16:25
going on if you know you can also check on the internet in the last few minus 1 August so go codes as against see here and the 1st that is that the smooth as long be I really would like to to get into is hard to say these bond but after that there is a very important part of language in this 1 that said that although it is running the the time image is not reached so it means I had a right to surprise many large number and for example if it's larger number it's 1 and 2 thousand bits means he just try to surprise it and your computer is not working there's no result what is known is that there is no reason for it means you can accept rise at home as I mentioned the and this number is it
17:17
possible to factorize is computation approximately and is it possible to reconstruct the and q prime numbers and if I'm
17:28
choosing this would the number of larger than 100 thousand for example 1 we'll then we'll 100 million then it means the factorization time is not 18 minutes on not 5 minutes 1 hour 1 day 1 week so it means if you are trying to to factorize a larger number and there is no reason you don't know why is that is known is out there and all code because this is a very secure huge number or there is a very large news number uh and generated in such these numbers I didn't want the the 2 main explanation of this organism you can find the answer in the internet and they just used the combination of these always and the combination of the previously mentioned of reason assessing Picheny asset to produce a sophisticated them and there are many good quality from the numbers in open source library and of course it into the huge that's my number of between Armenians quality 7 from what the rules found all of their brand factors of the huge numbers so you can find p and q less than reading 1 minute so it means and that is it possible that a constant from the public key the private key and it's of course everybody knows that is in this activity can be used in in system you know what the genes that are made are using some SSH or something like that out of class
19:09
and just some words are related to the news on the left that's that's when you are modifying the openness to sell all put that is very well no statistical test that generated numbers have to pass so it means and is generating some bad numbers and not much passes or statistical tests from the National Institute standard of technology that it means that the than fact the and so you can refuse for cryptographic purposes to run on whatever we tested all of these all of the 15 and 16 and 17 test this there are some some x and testing that these just so all of the 15 tests and pass pass the orbit of the random number generation and after that they tried to modify some of the numbers in we tried and different approaches also maybe you have ever of those chapters in military tho the tests we also applies uh let distribution this 1 and we also applied the quota correlation measure this 1 and after that we didn't identify any differences between 2 random numbers and between the generated on the members so didn't find any statistical test that can distinguish these their numbers from the numbers so after the statistical tests we tried to influence we tried to implement the discovery the and to try to do that we try to make some some implementation of the cold so they just you can see that because the set of columns and we just the 1st of these domains and to be generated and CSR Centocor model that you would like to mention the certification you know we would like to use a 2nd application and we just a requester centrifugate under a set of conditions by Khalilzad to create and that this is a 2048 bits and some intuition for it and let us take as you know and it's very interesting that so if you assuming that it's not possible to identify any measures activity in such kind of numbers because you don't have enough facilities to make for optimization to find a bad behaviors such kind of of numbers so that means that after that the approved and Ishida centrifugation we just deployed to the cases that you can check on your mobile phone also the fish and the commas and active and it's working of course you can
22:02
check some measure testing maybe you know it's that we try to configure the system recycling it means people want you know it's everything user anywhere on December the 25th really it seems the most secure as you can see the less probable states and the birds and HTTP as Fermat's secrecy is also enabled on the 7 so we looked into this includes certification everything is the norm and this area seems studies that were written to the certification and also certified by the common law i
22:37
is against the in this slide so just using some very basic comments in the lines and further but all so as client comments you can just download the certificate from the server it's very easy you can now what you can try it and after that you can write out the models and you can write out from the certificate which is the public key models this is the huge number and the next step is to try to factorize this number and
23:13
this is the domain of the source code in Beijing being married to computer assistant studies of these every function you have to find it and the number theory can very easy right and programs written to this topic and you can find some the accused of his program is again the the presentation in the this slide is the 1 who is this is the largest 2048 this number and you have to factorize it's of course if you decide to surprise normal number if they want a million years passing the computer solitaire you cannot do this all this metadata is generated by a sophisticated modified opens this library and after that this is the 1 hour p minus 1 August invited by John blown out in 1974 the gist of the world this problem in body GP because it's a short 1 and just try to try to stop the huge number and this 1 and as you can see he takes 1 minute and so as to 1 the 2nd meeting the needs and we were able to to factorize the huge number and the certification and it means that is it possible the cost of from public key the private key and if you see that just that for example I can be conscious had come that everything is secure the certificate is satisfied by the event on the CA and everything is called grand well maybe there is some some problem be deceptive it also because you can you can you can make some such kind of that prime numbers that can be used in such kind of certificate and
25:10
summarizing the research it's very important to emphasize that so get the roughly and this is the socalled so towels and keep the left and then you try to hide information and to keep the graphic methods and try to steal information for from companies and to keep the graphic metal it's it's a very well known now these and then we just let it be modified openness salivary holler you can use this kind of methods in embedded system and it's very important to know that when you are using a simpler prolific metals and there is a viable cell the Secretary expect want identified and malicious activity for example in a source told and of course and if you know that such kind of Panama generation exists and then you will see the source code that you know that there is some problem with the prime numbers or if you know only the locals all present with strategy it I can be conscious up on and you don't have any clue how to factorize if you don't have any clue for the prime numbers p and q generated so it means and you can make some vendors you can implement some variables such kind of applications like interstage certificates this is a local Netherlands it means that you can find the binary of the open systems and is it possible to to modify the binaries and after that's the Panama generation is malicious and of course uh as I mentioned the slave important emphasize it is not possible to distinguish the statistical tests so many many random number of Parliament and then in the generation of such that Number generation generator and tried to try to get proving such they that they tried to analyze the old In this way if you're trying to analyze the market it's not possible to distinguish from other 2 random number generator OK thank you for your attention if you have any questions relating to underline the generation or only into the source code of an underdetermined straight forward it can also send the you know anemia PUT to dried where you can also try to feed the self of or days an SSH this is also the case in the interest of the thank you would want to thank the was it would also mean come on come on come very was that it was not I want yeah and you need to have some problems relating to muscle them uh and some some of the courage emission methods less as a multiple operating to cryptography many due to companies like an essay are are occupied cards or something like that so you very huge companies using such kind of that goes and it's very interesting because when you are when you are identified and then loss and related to that of the you don't know it's it's really about the or what is just some of thinking about what the programming and when I checked analytically because they using that have the same techniques that some cryptographic techniques how to hide some basic parameters they think edit it because and after that they tried to try to and how can I say you know when you generating prime numbers we have some statistical prime numbers generator it means there a chance that is not a prime number that is likely highlighted that is a prime number that might be of interest or something like that and then they just generating some political they just don't everybody that it's 100 per cent security and it's 100 per cent so and there is at least a chance that is that is not on that curve and something like that and after that some years ago it's can the identified is there is some problem with the the curves and then uses the same techniques relating to these the number to the teacher and groups like it because so they're using maybe a more sophisticated vendors and it's and you don't have such kind of so the search is you don't have that many supercomputers to analyze it is really a problem but this is beyond the curve or something like that and of course they have that is such and they can make such kind of sophisticated but also as I mentioned to my computer takes 8 minutes the the the cost of from the public key the private key it means I can choose a larger number and it takes 8 days so member trying to factorize after Monday after to is just solution OK basic number however if you try to learn uh when they do this you will find the factors so this is the same if you don't have enough research is to find some curves on there and the curves and their 1st find something parameters using that everything is settled on this random number generation however after that everybody tried to find the circuit parameters and everybody trying to cope with everything after that they found and realized that there is some problem with that and the number generator OK but I want you to