Automating Crypto Bugs Discovery

um and with no further ado I'm gonna turn it over to these gentlemen hello good afternoon so it will be hard to give because we just back from from blackhat where we gave the same talk we had 50 minute slot and now we have just 25 minutes so I'll try to speak a bit faster not too fast we just remember the few slides but up it should be useful to you so let's talk about testing crypto stuff you know - crypto bit under the blackhat people so you need less introduction to this we want to test crypto you test functionally does it work correctly just what correctly on valid input so you get the right output

and when you send an invalid input what do you get you get some output that you know what's computed in what but or do you get an exception or in error or something that tells the color the user that something's wrong you also want to take the security off the software so crypto software is software's you want to test the euro stuff like memory corruption normal logic bugs you also want to test things are more specific to crypto you want to make sure that the cryptographic secrets they may be the keys the Pentax will not leak lick in several cents it can leak in termsof if you get a memory dump you can have a so

leakage in terms of side channel attacks for example in software you have techniques timing attacks so you want to test all this with a single tool and no such tool exists so that's why we started a quite ambitious project the things that exist today you have for example static analyzers things that the like Genesis and clone they will tell you what or not they will tell you well how secure is your code for example in terms of memory corruption in terms of undefined behavior but it will tell you nothing obviously about the correctness of the crypto if you implement RSA it will tell you that your code is not buggy but each one check obviously that

RSA was correctly is the opposite for test vectors so test vectors usually it's a bunch of input output values that you use to test that your implementation is doing what it's supposed to do but it will not tell you anything about the security the safety of your code so you want to combine these two features you have some more advanced tool to find Feinberg's you probably know things like a file which is kind of preserved because it doesn't know what it's testing is trying to be as small as possible to learn what input will maximize the cut curve read but it has to learn by itself it's not designed for example to test I don't know pkcs 11

passer that's where you have things for example called smart furthers now smart roads are it's dedicated to a specific crypto functionality you might have a smart further if I don't know elliptic curve diffie-hellman and the first I will try to send values that maximize the code coverage like 10 different values that take ten different code path in order in order to test all these all is code okay but it's pretty hard to design and there's not many such tools available there's a few commercial ones but again there's very specific may be the best the most powerful solution is formal verification so it's like getting a mathematical proof theorem saying oh your function your library is correct

and free of bugs you have different different types of verification the one that will tell you that your code is equivalent to this code and you have the other type which is about proving security properties for example recently it was proved that we're at VPN satisfied it forward security property just by looking at the graph code okay now what we want to do is to maximize efficiency in terms of you know like parity efficiency you might be very powerful like formal verification but it takes a lot of efforts is very expensive in degree excuse my people to get it working the test vectors anyone can do it but as I said it's pretty damn it will have race mode code

coverage so you want to like be in the middle maybe on the top of the green rectangle where we put the question mark so our project was to create something that sits between the dam pressing the dam techniques and the smartest ones and that is as easy to run as possible so I came up with this name differential fuzzing a year ago because it sounded cool if fuzzing but differential you know it's actually pretty rare stupid it's like just comparing two different implementations of the same stuff but in a not so stupid way it's been done before by a bunch of people you have two examples there more concretely what what we're going to do if you test the hash function or PRNG

it's something that is deterministic so same input twice am I put twice so let's say you have two implementations I don't know shastri of the Chaucerian function you have the information you want you have the pleasant b2 so the implemented in our quiver I'll give a equivalent sorry for any input you should get twice the same output so that's basically what we're going to do we going to choose input values X different values and maximize the code coverage because we know that we're testing a hash function so we know that we want to send values a different size or different alignments and for each of these values we'll make sure that you wanted me to give us the same output

slightly less trivial cases for public encryption so in this case the input generation was give you a message X a public key and yesterday's a private key difference with the previous case that here p1 and p2 don't do the same thing they do the opposite functionality P 1 will be encrypting X so you will get P 1 of X and P 2 will be decrypting so if everything goes well after computing P 2 on you wanna X what you will you get X again so if something wrong in if the two implementations are not interoperable then P 2 might reject some inputs or P 2 might compute any incorrect plaintext okay so now speak about on YouTube alright so we decided

to actually implement that approach of testing so we developed a tool called CDF as an trip to differential fessing which we basically do not only the functional test GP just described but also do more stuff I'll come to that later so city if CDF is coded in go no it's not in rest it's not in say it's and go because yeah it was easy to code easy to read and it really is easy to support concurrent execution of the test at the same time if you got 16 cores why wouldn't you use 16 at once so yeah the CDF tool is actually made of three ports so the executable CDF itself yeah now I will come to that later

so yeah why will you use CF CDF will test the correctness so the functionality of your implementation through differential filling but it will also test the security of the implementation against known edge cases because CDF will be aware of the test algorithm so if you are testing ECDSA or errors say it has special unit tests for those so it's not just about them fizzing it's also about hedge cases and strangle behaviors so we will check weak parameters and stuff like that so CDF is really not about replacing formal verification it's really about going further than just plain text vector test vectors so you heard about which proof I guess it's another project which is about unit

testing they've got really a nice lot they really got a nice set of unit tests and it's a totally complimentary approach so we could reduce your unit tests in our tool to do the tests and on both tests in the implementation that they don't do anything differential there are not about comparing implementation there are really about testing just one and there currently only support Java which is not our case but yeah so all that it works so you want to test easier this ECDSA you've got plenty of libraries implementing it but they all got their very own API so you are kind of you know you got a problem sir so our approach is to design

interfaces so CDF will interact with your library through interface program which will translate your API into ours so our API is pretty damn it's just playing come on line arguments so CDF can do as his coal on your proxy program and call your library afterwards so for example for easy just say you've got you want to sign a message so you will simply provide the public key coordinate X on Y the private key coordinate D and the message and then you get the output which is R and s so why do we need the public key - well simply because of compatibility reason with certain libraries so yeah that's really dumb we plan to use a FL like file based

interface later but it's not the case yet so the interfaces are really generic and it's really man means to use everything in black box so we won't be instrumenting anything so you can bring us a script C executable anything you want and we can test it directly if it's exact table so yeah all those it works CDF is made to actually use the proxy interface which are in the middle there so CDF will be calling the proxy interface which in turn must be calling the libraries tested so it's really done but it works on it's really well easy to I want to say here is that CDF is the tough stuff we did yeah exactly the

stuff at the bottom is what some people did yeah in the middle it's where you have to walk your - right yeah exactly so what if you want to test anything you have to create the interface proxy programs in the middle it's pretty easy it's really easy to do in Python it's 35 line of code to test cryptography at i/o it's easy yes enter in implementation so fairly quick open SSL you've got to clean the pointers there is a bit more work but still it's not too much work so give you specific tests which is very very simple stuff again so ECDSA so it ticker dangers like said before the first program from let's say

a pencil will issue signature and a second one let's say from cryptography that io will verify the signature created by open ssl so you can test a few things you can test for example squid bullet point here cuz there's two kinds of SDS AP is the one that receives a message that hash is the message for you and that signs the hash value the other kind actually receives a hash and signs the hash directly now what happens if you send a hash value that is bigger or shorter than the expected value some api some libraries will complain with the UI that's not the right size other ones will just send the ignore this and do whatever they can so when you send

you would send the longer ash a message and it will just strip it till the less decided thing that they need so they will ignore some bytes of the message to be silent you also want to test the degenerate cases the obvious invalid not mathematically invalid but in secure parameters for example was the if the public key is the point to infinity so is 0 0 what if the private key is 0 what is you why don't you send a hash value equal to 0 so as you can guess a lot of things can go wrong in this case so some applet some implementations reject is kind of parameters but many accept them just can

you show example you don't have to look at the code but that's an example of test that we do on ECDSA to check that it does not run into an infinite loop when you send seven kinds of parameters now let's switch to encryption RS encryption specificity so like I mentioned the first program will encrypt the second one will decrypt and you can test different things there again you can test for example what kind of exponents are supported what kind of modulus not supported let's look at like open SSL for instance so you know that a secure module size for I say is 2048 but if you ask open SSL to use RSA with 33 bits then it will accept it and generate

to distribute what it was for legacy reasons promptly in the hours I use a public exponent usually you noted II and a private exponent to decrypt usually D so this should be largely huge look like a random value now what happens if you send a very small D or D equal to 1 or 0 - that should not happen so is your library testing this the opposite it should be small usually but for some reason you might want to use a theory now many implementations only allow you to use a small e sometimes it's fixed to 16,000 whatever so that's kind of stuff that we're testing and we also detect timing leaks but we'll talk about this

later how did we win this we don't okay we can detect timing legs up to a nanosecond level but sometimes what we find is that oh yes there was diamond lake but when we try to explain it it's impossible the leak was too too hard to detect too hard to exploit okay so that's yeah okay so we do not reinvent the wheel we took this nice substitute created by Oscar happen and other people we just ported it from C to go to integrate it into into CDF okay then what kind of so did we find all right so we we try to test a lot of well-known Libra is like your crypto open SSL and TLS typically we

tried it again for the DSA it's just sayin OAP irritated or AP encryption and what we found is that often they don't do everything as they should or maybe they fall into some traps accepted for to poppy which was quite impressive but he's known to be a quite paranoid about security so it's good thing that we couldn't find anything there I think they might wonder why did we choose this five libraries and not other ones yes so we choose them because it's well known liberties which are basically secular and which are really yes you died by a lot of people we didn't we didn't go for the low hanging fruits we try to do like

deal the most popular the most critical piece of we're and these are maybe some of the most secure libraries you can find me maybe should in your PI crypto because it's obsolete and not supported yeah what we written there's a number of issues it's actually really issue it's not security issue it's more like small problems I could correct so for example for DSA we found that many libraries were actually accepting invalid weak parameters or even parameters which could lead to Daniel of services which are quite bad I mean and other inputs could also lead to always valid signatures which will discard the hash value of the message through zero multiplication for you so it's really

bad the the library should should assume an error or something there so if you look at this standard the standard really really saying okay you should gain assurance of the domain parameter identity pre rup to signing and when we checked if libraries were doing it we found that most of them wouldn't so for example if you take the DSA signing process you generate a random k you compute the generator G to Z K mod p m-- at Q and if that value is 0 then you just take another random K and hopefully it shouldn't get you shouldn't get 0 again if you do you're really unlucky on on the third time it's a probability of

getting zero again it's so low that it's not possible but some liberals are not checking whether G is zero or not but if G is zero zero two two zero two whatever will give you a zero value and they are falling into infinite loops so if the adversary is able to provide the domain parameters which is a case which could supposedly happen according to the standard then those are quiet screwed so yeah this is what go did when we reported the problem they had a for loop doing the random key generation again again and again at first and when we reported it they actually fixed it by limiting the number of Adam Adam so they

are not checking the domain parameters they are just checking or not doing too many loops because that's the probability of doing easy it is so low that it should so remember that we had pretty much some nice lives we have five minutes okay so one commonly you saw the table before and when you look at this sorry it looks like go crypto really sucks because there's four five six to seven issues but this should not be understood like this we found some like non-compliance and some issue there but go crypto is really well returned is free safe generally it just means they had their bit maybe less conservative or less paranoid than other libraries crypto PP is really paranoid and they

try to do everything right but maybe on other aspects they're not as good as as a go in terms of clarity in terms of productivity it's really easy to use the crypto I encourage you to use the to look at the the code for example of OAP it's ready it's really beautiful and copper pipe is usually a message to you it's some plate don't answer your friends or don't use go crypto because and open it cell is open SSL okay we had the conclusion okay yeah so if you're interested in these two there's still lot to do for example we need some new interfaces in other words we need new the ability to test it more stuff like

we don't even support a different man or CDH which researched so we want to do at this we want more test go if you look at Google's two they do many more tests and then we do so maybe we can try to find a way to include their tests into our software we just added tested a handful of libraries some of them may be more secure ones maybe we want to use up to on other libraries which might not be as secure as this and finally we need to test on software which it would be it's quite embarrassing but we don't test our testing software very well so it was like unit tests yeah we got like

four key portions of coverage yeah that's ridiculous okay so thank you time to take some questions and small commercial talk I've been writing a book with no stars you can order the early access version if you like thank you have we have time for there's like four minutes or like one or two questions anybody you again so as I told you that the other conference yeah this is great I needed this yesterday but now just playing with it I've got a problem just I mean really specific question no one else is interested in the specification of the paths for the files on the command line argument I'm getting no such file and ah but we just fixed this

oh yeah I emerge a PR ten minutes ago and so again we had a problem because we challenged the github pass through the library egos or bounties we still face posting issue tracker and we fixed it thank you we have time I was just wondering in your tables there were a couple of na s in your results and I was just wondering what that was maybe I dismiss the library is just not implementing the algorithm so we can test it I mean if you don't know last question thanks for your words have you tested by crypt atom or not Paquito I created on the maintain invention of Bengal diode to pick hip to do this is

the official not the fork of pipe it frito ardan so I was really eager to see the result but I know that yeah the crypto is not maintaining you know so it's not even a good try laughter yeah we could try it easily I guess if it's the same API as yeah less than a new track we actually have a couple more minutes so yeah just if you wonder it's really easy to add new interfaces for other algorithm it's really easy to add new examples we were providing all the examples programs so if you want to compare your own implementation don't do it every say oep against open ssl then you can just take our open ssl example

I'm a busy at the previous confront someone arrays do a different objection he said oh yeah but you know we're not supposed to write our own crypto should use something or available makes total sense but you might want to use or two on libraries that you may want to use may be to compare their inter probability and just to understand how secure the arrogance or tests yeah and one of the big problem with crypto is that you get a lot of random my stuff like ECDSA era CoAP a lot of stuff is randomized so you can just even test vectors for those it's harder so yeah that's why you might want to use it too

yeah hey um dear plans to fork the like open SSL or the main kind of popular libraries and remove all of the actual checks sorry for generating um stuff you're passing for verification moment you're saying an alert generates I'm not maintaining you off upon itself yeah I don't know if it's not but we reported some stuff to open SSL and from their point of view it was not worth fixing because it from the point to be something that okay that will not happen in practice in yeah maybe I went too fast on that but actually when the Thunder is saying something the libraries are not always really keen on implementing it because it has no

practical incidents in their opinion so if you don't come and come up with a pack they won't they would say hey if the attacker can provide the domain parameter then he can provide the private key why would I care when it's not exploitable until it becomes exploitable yes I can have a big round of applause for these guys great job [Applause]