Breaking Crypto with Randomness

I'm Dan Anderson I'm going to talk about crypto and breaking crypto referendum number generators the background I've been working on crypto and security for about 10 15 years at Sun Microsystems and later Oracle most recently the whole project was kind of canceled its lares and everything and they're now just admittance mode and that one advantage that I would freed up a lot of time for me to work on this presentation so what did I do I started fixing up everything around the house painting gardening drainage everything but the presentation but it's it's good because I got everything else I needed done I also implemented verified boot on Solaris which Don verifies kernel modules using RSA

signatures I'm gonna post this presentation on Twitter and that's my twitter handle at the bottom so I'm a common attitude I have IR I see it is that crypto is broken and there's nothing that we could do about it and that's some nice tea from my technical co-workers you don't work in security but they have that up to that all equipped all has backdoors and it's just that's the way it is but the truth is the crypto is not broken it's the math is solid over time you just have to have longer keys and and some algorithms especially the early ones like md5 sha-1 they have been been broken but the current crypto is still working there's

action of course that quantum math and that I'll talk about a little later but the important point is it's not necessary to break crypto there's a lot of easier methods around it's if you want to pick the hardest method you would try to break the math but some waste of time let's talk about some other methods I on the social engineering physical threads blackmail you could actually take the device fishing is probably the best way to do it because it's very easily automated and you could attack the whole world there's also side channel leaks that's where you could listen to the radio ways or or or or look for the timing in the responses and to try to get information

there's also a large databases available for passwords in hashing and finally there's poor implementation of crypto and what I'm going to talk about is this this one little FAFSA FAFSA bad run rendering them are generators so all the other stuff you could see another talks one problem is crypto is confusing especially public and private keys you have two keys and it's very confusing to people you know if you like do crypto and send some something that's encrypted what do you do do some of them the public key or the private key maybe should be safe and send them both I don't know that's what Adobe Adobe has it they're Security Response some team you know there's security gurus so what

they do they posted their public key and private key on the web and that happened last month they take it took it down but it's easily you can see I even the experts can make mistakes and of course one thing you should not do is throw your private public key in the same file it's not a good idea

let's start from the beginnings random number generators I don't know when they started but dice have been found from the 24th century beast BCE so that's probably the earliest generator in 1950s RAND Corporation wrote this book a million random digits and it was recently republished and night in 2001 and it created that book by using an electronic roulette wheel and the output was was punched into several IBM cards and they published the book from that if you want to see a lot of funny reviews you could look at the go to amazon.com and look at the book reviews for that like somebody complains that the let me complain that the page numbers had not been randomized pseudo-random number

generators were invented by John new von Neumann you know he invented the concepts of the modern digital computer in the 1950s the problem was with his random number generator is it repeated very frequently and that's what all pseudo-random number generators do is they repeat so the idea is to make them not repeat for for n bits around digits and but you just have to be aware of that problem and true and random number generators follow then and they usually take the input from nature like using heat sensors or something else like that and finally after that there's crypto secure rent on pseudo-random number generators and they have been analyzed by experts and they have to have these

properties like not repeating after n bits

randomness there's several ways to tell if randomness is good and the first sanity test which is not enough by itself is just to create a scatter gather chart I just got some random numbers and converted into comma separated variables and imported them into my open alpha spreadsheet knew you could do that with Excel to now ran remembers that I'm going to do this and that's supposed to see any geometric patterns in there and if you looked at early random number generators especially from 1020 years ago you would see lines in the chart it also is not supposed to be perfect for example we see yeah which is okay if it's perfectly distributed I would mean you could be

able to predict some of the random number generator members generated towards the end NIST which is the US government standards organization they have a test suite where you could um take take them your random numbers and see if their their values according to them and you can also use this statistical analysis on it the the best bet is on is you actually analyze the code that actually analyzed algorithm to see if it's valid and and that's usually best done with a public discussion and not in some private secret group okay I'm going to talk about three different RSA's and this is the confusion but there's three to three of them there's RSA algorithm RSA the conference RSA the

company RSA the algorithm that was invented in 1978 it was actually invented in 1973 by the British but is kept secret there was a top secret algorithm and so these people in the u.s. invented it five years later they didn't know about the earlier invention because secret but RSA is a pub is a public private crypto algorithm so you have a private key and a public key you encrypt with the private key and you give it to somebody else and they could decrypt it or anybody else could deep decrypt it with the public it's very robust it's been around forever the main flaw with RSA is humans they leak keys and they don't store keys properly I've worked in

hardware a lot in operating systems and one thing I found with with a lot of computer manufacturers is is they have biases you know for booting everything and they sign their BIOS but they don't care about the private key they just keep it on your hard drive or the home directory so you could probably for any BIOS manufacturer eventually snoop around and find their private keys they don't store it very well you're supposed to store it on in a physical stay for an HSN which is a secure way of storing keys secure hardware and also as I mentioned for it's a hard concept to grasp um especially for the public RSA is also not quantum safe so supposedly

it would work for next say 20 years or so but after that it probably won't work its best in the meantime to use long RSA keys on 2048 or 342 you could try 4096 but that's kind of very slow okay now we're talking about RSA the conference that's in San Francisco and it's kind of tainted a little bit they the emphasis is on comedian and actor keynotes I like comedians and actors too but I don't go to a conference for technical content I can see them on TV fortunately they got rid of the booth babes or whatever so I'm more professional but still it's it's there's a lot of sales hype too so they kind of

emphasize more buying somebody device that will solve all your problems as opposed to technical content they still have technical content but it seems like it's overshadowed by this other stuff our RSA security that company they were formed after RSA was created they they started with her RSA the algorithm and sold that and RSA was later bought by ECC and now it's owned by Dale corporation they had this product called be safe which is their secure crypto library it had algorithm called dual ec drbg and but unfortunately the NSA paid them ten million dollars to put it in there and they also created algorithm they they went to an Zi which is kind of a closed

source standards organization and had a standard approved then they had missed approved that standard but all the people who created the standard were from now and I say so I was very suspicious and that code that backdoor code their vector a random number generator is in there for almost nine years until 2013 okay let's talk about breaking crypto that the you start with brute force so brute force is just trying every possibility there is one at a time and that just gives you an existence proof that you could break it but it's not very practical on you want a solution that will you want to have a solution before the Sun turns into a red giant

five billion years from now so so you try to chip away from the possibilities and one way of chipping away is is well the key and generating keys is using random numbers you just you take random numbers and try each one see if they work it's if you there I'm number and everything and if your input random number input is predictable your keys are predictable so all that's and in fact in 2012 somebody tried to harvest all the SSL keys on on the web that they could find and they found that almost a half percent of all the keys were duplicates that kind of implies there's a lot of sharing or that a lot of the key generation is no good because

they use flawed random number generator so let's talk about remnant number generation in Trophy is a term that people use in crypto to talk about the input for random numbers and that's just it's taking numbers from the nature or any other source you could fine and mix them together to a random pool but problem is is if you get input if your garbage in garbage out if your input your in trophy is bad your random numbers won't be bad and much software has had port in trophy wanted at one time or another I don't want to go over each problem but here's there's common problems are found using session IDs or process IDs those are usually very low

numbers when you first boot a system mostly zeros same with the clock that sometimes starts at 0 or at a fixed date like 1980 1970 whatever 2000 clock resolution if you use that that's that's could be fine if you have a high resolution clock but it's rarely your clock is rarely down to 1 nanosecond and some clocks don't go down to 1 seconds so your high resolution clock is mostly zeros and one bit on or something also sometimes used as a random input disk seek times your keyboard your mouse and that's all good for desktops it doesn't work for servers it doesn't work for embedded devices Internet of Things because it doesn't have any peripherals

so it's all missing temperature sensors and other sources of course when you first boot a system it's the kind of known temperature is pretty cold so that's kind of predictable so you don't want to use a lot of this stuff is just bad for for your interested rolling your own number generator is is kind of bad and risky um let's talk about Debian Linux they broke the random number generator in 2006 somebody on an Adobe entomb ran the static source analyzer and that does a lot of good things like looking for corrupt pointers around initialized data or duplicate code code well this analyzer flags some duplicate code so the guy just deleted the duplicate code

except in this case that code was really needed and it created a bug and that was not discovered until several years later I didn't put down the date there on the OpenBSD project got tired of problems not only with Debian Linux by all the other operating system manufacturers with poor random number generation so they had idea we will just invent our own by just inventing your own doesn't mean it's good they created this algorithm or function arc for random 2008 it's based on Northfork crypto algorithm which was originally a secret invented by a secret algorithms and by RSA Labs in 1987 and it was a reverse engineered by somebody a few years later looking at the object but it really is a

poor crypto algorithm it's not used anymore it's a very fast algorithm but it has problems as in key attack sirs are several ways of to attack RSA our rc4 that have been discovered from 2001 to 2015 you could hook them all up on on this wiki page also rc4 is equip program there's never intended as Oh generator and output is not uniforms you if you take that output and put on that scatter gathered short short you'll see a lot of dark and whites plots on your your graph and on your form is as bad because that means you kind of easier to predict your random numbers and reinterpret predicted it's easier to to break crypto when it depends on your

end numbers OpenBSD replaced our c4 with another algorithm for our Berlin called cha-cha 20 a couple years ago and it seems to work better but that's just a lesson as dangerous to invent your own I'm gonna invent your own crypto but invent your own random number generator now there's still code code out there that uses the old version of rc4 that's tomato entropy entropy is not all alike so you want to try to figure out how how much entropy is in your input we you generate random number numbers simplifies you mix all your I'm two feet together you do some stuff and you have a random number pool and mixing is often performed by XOR and in your extracting

fee for you using some crypto algorithms or like each Mac or CBC Mac but you need estimate your interface let's take a simple example of passwords let's assume your passwords are always lowercase and often they are unless there's a restriction there's only 26 characters to choose from so you could ask me to dance trophy or square root of 22 6 that's around 5 bits so you don't get your full 8 bits of entropy in a byte you only get five out of the eight so and that's you could do that with any other interface source you try to estimate how much randomness there actually isn't isn't there so let's talk about drool you see drbg which I

mentioned again that's a deterministic random bit generator ECC based as I said before is based on the X 982 standard anji again is a closed standard so has just done by this closed working group that consisted completely of NSA people and was approved by angie the nist US government standards board just adopted the standard unchanged so the P and Q values which are used in initialization are hard-coded in the standard and that's a problem because they put it back door when you use those P and Q standards and made them easier to to know what random numbers were generated as far as we were concerned in Solaris we did not implement it in our operating system because there was just

so slow they had about five different options for bit generators and we just didn't implement that one there was other ones out there that have been out there for years and are tried-and-true and open SSL they they did implement it because somebody paid them some money and of course open SSL is open source and they're desperate for money and stuff they only have a couple developers so they were paid to implement all the bit generation algorithms in the standard but fortunately there was a bug early do you say your fortunately there's a bug in there but because of there's that bug that the random number generator did not work and so the backdoor did not work so and later when

there was found to fixing the bug was in one line bug they just deleted all their code the algorithm itself has been suspected since 2007 Microsoft Research you could look it up and they they had some doubts about that algorithm

okay as far as implementing algorithm is if you want to implement the algorithm ever use it you should choose your own P and Q but nobody did and in fact that's true in January you try to if you have option to choose your initial IV your initial vectors or initial numbers you should do that over the over a number of recommended and standard especially that standard does not tell you how to drive it okay this kind of repeat duplicate slides here okay as I said ten million dollars or state denies that they knew anything about this but they did gladly take million ten million dollars from the NSA and they did make it the default algorithm

even though it's slow and unproven they made it to default so it's very suspicious to me breaking crypto refrán the numbers I'm running out of time here Renne magic number referred to mysterious numbers you don't know where they come from and they're using crypto algorithm rhythms be where are magic numbers if you find one on a standard ask where that magic number came come from for example on sha-256 it uses as magic numbers and on the first 32 bits of the fractional part of square roots of the first eight prime numbers that's hard to fake so that's sounds pretty good but and there's you see similar stuff and other legitimate crypto algorithms that tell you how they came up with those random

numbers okay until Rd ran that's their ran remember instruction until self-certified that their new random instruction meets all these standards nist SP 800 well that's fine but self-certification does not mean anything I could self certify that my dog here also meets the standard you need a third party to active to actually say that this meets a standard they can also contributed the changes so we could use it on Solaris but later on when we found out about this mischief we kind of changed it to use it as entropy input so that you'd do some later processing to mix everything up and that's the approach that Linux did from the beginning and free FreeBSD also change their code to them

mix up the input of our dear Ann and not used that input directly and that seems to be good enough there's a suspicion you know about our dear Ann Intel's our dear Ann that NSA did they introduced the backdoor into it some of the Snowden papers revealed that the NSA and the GCHQ that's a British equivalent broke an unnamed chipset there was in the design stage there's four micro processors I know they have random numbers in it until AMD via spark now forgive rule out time travel that takes out two of the candidates spark was 2006 and AMD was after the fact 2015 so we have two more via ok there that was designed and created in a Czech

Republic Intel was designed and created in the United States now if I were as a USA spy organization who would it by be who would be more easier to subvert the check somebody in a Czech Republic or the United States so but until I think denies it and there's no smoking gun so you've got to decide for yourself also until later and permitted a Rd seed instruction which is used for seeding random numbers which is supposed to be better nonces nuts means once a number that you used once and it really means that it doesn't mean use it twice three times four times means once it doesn't have to be a random number it could be a

sequential number one two three four five but you better never ever use one two three four five again even after rebooting even among several systems these he's just ready to generate announces with a random number especially one that's real long because I go even a 32-bit random number that's to 1/32 it's you won't repeat that ever unless you're on number generators as bad but ran being random is not sufficient it can't be a constant random number so you can't put the nonce value in your code and expect it to work as exercises a user you could go to github or any other your favorite source repositories and look for not to see if you could find where they hard card it I

found it once in a code review I haven't searched github but it's a common mistake a nonce can't also be usually guess it just can't take time of day or your process ID as a recent flaw found in W wpa2 you know your Wi-Fi the crypto called crack and that replaced your nights on error conditions and that's not OK even an error conditions you can't reuse your your nights TPM that's the security chip trusted platform module that does crypto and lots of other things are called the Swiss Army knife of crypto there's some problems with it what if you just one manufacturer get something wrong that could cause a lot of damage or what if

one manufacturer is subverted by some government organization you're just trusting a black box there how do you break a TPM it's a side-channel attacks it has a very slow bus they all PC lopen camp bus when runs a three through megahertz that means it's easy to probe you could actually probe it directly there's only four data pins out there or you could try to use monitor for radio ways or power frequency or something the OPC also has no checksum so it's just data doubt going out there and it clear there's awesome yes okay I'll speed it up there's also virtual TP and Rich's could be it's averted more easily because it's software the current Infineon ship has a flaw in it from RSA

key generation but that's just not from random number generators but that's just from using a low exponent so TPM is a pro-forma checkbox security that's there just because they have to have it that's then in my talk I'm going to post this on my Twitter feed clogging a couple days that Dan Anderson

you