Problems With Elliptic Curve Cryptography in TLS and SSH

my name is Joe and today to talk about problems with an elliptic curve cryptography and TLS and SSH it's a first an overview ECC elliptic curve cryptography it's become pretty popular in the last decade it's used quite a bit of in TLS and somewhat in SSH common parameters in it are let's say shady some people think that they're back they've been back doored by the NSA so I'm going to go into that I'm going to go into the history of how of what's happened the timeline of the progression of how things were standardized the punchline though is is that last question what can you do about it from a sysadmin perspective so the punchline is what can I do

let's say I have production systems what can I do to turn these off you know I don't care if so the first question I should answer is well what is elliptic curve cryptography and I promise you this is not math presentation I'm not going to go into much math that's one equation that's it so what ECC is it's cryptography done with elliptic curves it's done over finite fields in this form so it's y squared equals x cubed plus ax plus B and it's usually mod some prime so really what it is is it's based on the discrete log problem which is a very well tested cryptographic primitive just happens to be over elliptic curves so

it's a similar primitive that different element and DSA I know and there's easy equivalence of those two named DCP is it so your next question is probably going to be why does ECC matter well this chart really drives the point home if you look on this on the left side you've got security strength say hundred twenty-fifth security strength in the traditional crypto world for DSA and RSA you would need a key size of thirty 72 bits in order to achieve that security level in the ECC world that's somewhere around 256 if there's a there's a range here 256 to 3 degree so it's much smaller look at the bottom there that last row 256 bits of

effective strength in the in the tradition crypto world you need a 15,000 bit defeat how many people have actually run into a 15,000 bit key out in the real world so that's snake oil right yeah nope it doesn't exist nobody uses it it's not practical but take a look at there on the the right bottom right under ECC to get that level is somewhere around 512 bits that's the punch line as your security strength is increasing linearly your ECC keys increase linearly whereas traditional crypt dose it's increasing exponentially so that's the problem that's the main advantage so unsurprisingly a key generation is much faster embedded devices can encrypt and decrypt faster they'll use up less power

if you've got an underpowered VM somewhere it can do more just with less resources if you're using ECC and of course the 256 bit security level then becomes practical it was a practical world traditional Kruti however in the ECC world it's not just immediately you can't just immediately use it you have to set the curve parameters going back to that equation that I showed before the question is around what do you use for values you know a B in there there's more to it than that there's neither prime over our coefficient and a base point so this is all like math stuff and if you were a developer and you're like ok I'm gonna use ECC oh wait I gotta

figure out these things and we're gonna set a to 10,000 what what's even bowel never mind what's good what's even foul so NIST the National Institute of Standards Standards and Technology government a US government agency they came out in a document FIPS 186 deaf to in January 2000 basically it was like hey everybody here's curve parameters just use these don't ask any questions no here they are and in that document they defined three classes occurs there was five or four prime fields which they say generated randomly there were five hundred binary fields which they also said there were a randomly generated and then some special case Copeland's curves and right off the bat people people

thought those random parameters were really suspicious the way they claimed that they were generated so they took these random seatbelt use and they ran it through sha-1 five over binary field so it's five curves defined over binary fuels so they took they supposedly randomly generated seat value State applied the sha-1 hash algorithm to it and then they somehow mapped that out to curve parameters but there's no mention as to how where did these C values come from for their curve p2 56 I got right there to see value like what is that it looks Brandon it looks round 1 but is this chosen today search through menu see values to produce outputs that make wheat curves so that's

that's really the punchline behind it all is that where did these come from a few years ago there is a project called the GPU farm and they did exactly that they're like ok well we're just gonna search through a whole bunch of seed parameters as quickly as we can fly shot one and evaluate all the outputs and and find curves that have properties we're actually going to do this and so that's it's a website that you can go to you can actually download the source code to that stuff so if you want to generate curves yourself with bad properties that codes already exist it's already out there so back to the NIST document here's here's a quote from the

pseudo-random curves are generated via sha-1 based on the method given and the ansi x9 62 and I Triple E standards okay so let's take a look at them well it turns out either my free the ansiedad costs a hundred bucks the I Triple E document currently is 97 although it's 77 for members I remember 10 years ago the grad student here and I wanted to read that ANSI job it was over 500 bucks to get the PDF so it might as well have not existed so while doing research on this I recently I started thinking one of the see proof that somebody actually took the seeds applied sha-1 and then somehow map that that's it's not obvious how that's done

you can do that many many ways and it's supposedly defined in the ANSI tag which I don't have but I said okay well I'll look around to see did anybody verify this I've not found anybody who's verified I could be wrong somebody may have done it and if you find that please let me know so I am very interested but I personally have not found any proof that the seeds even the old browsers so these 5/5 curves the ones that define that were prime fields they started becoming very very popular P 192 p224 P 256 and so on P 256 that's a curve that has a security level of 128 bits and that ended up becoming the most

popular in 2005 NSA released their what they call the sweet B protocols so it's publicly known algorithms they say okay you can use these to protect classified information so I guess the question is are at if there's something called sweet B what's sweet a it's actually just fully classified protocols so in this sweet B they recommend okay you can use ECDSA zdh here's some appropriate parameters and of course curve P 256 was included so the US government back then was actively saying we are going to use the miss occurs I'm going to go into this later I'm going to talk this is one of the big arguments against the idea that uh these are backdoored is

hey if their back door why is the government themselves using them for classified information so you know that that does sound pretty compelling but I will get back to this - this is the very interesting point and I will get back to this in 2006 ECC gaps formally added to TLS in that RFC spec it referenced what was in this SCC to document became in 2000 that SEC document included all the madness curves so effectively TLS one in 1.1 now has the NIST curves as of 2006 May then in August 2008 TLS 1.2 that spec team up and said we'll just import all the things from SSE 2 so again all the best pictures made it in there a

little bit of an aside if you know anything about Bitcoin you'll know that it's heavily based on ECDSA the assistant designers chose instead of using the peakers they were suspicious I guess because they picked the SEC P 256 K 1 let's say it's one of the co blitz curves it's not even it's not even defined in the MIS for standard at all they they just decided they one of us they clear that entirely and so if you look at it into into that curve little bit more you can you can see that the parameters are chosen and it seems pretty decent it's kind of it's got a nice performance benefit at 30%

so now I'm going to go into a little Side Story they can help you understand maybe put things into context talk about this dual EC drbg back towards quite a mouthful so I'm just going to call it the random number back to this the punchline is the NSA got caught red-handed factoring a standard and pushed this on the public so I'll go to the details so in an C 9 X 9 82 it was defined this was published in September 2007 although there is early drafts kicking around the 2004 the members of the ansi committee right off the bat are very suspicious what they noticed was that this random number generator had these two parameters to it and if there

was a known relation between these two parameters you'd be able to predict our future output like you need some small sample of the random number generator and then you can exploit a final in relation between two of these parameters and boom just all the output you now have it's a fatal flaw or any kind of cryptographic random number generator so right off the bat the ansi committee was was very suspicious of it so they came with they came to trade off they said okay we'll include this but we want to give end users the ability to regenerate their own parameters so then you can then say alright I'm generating this myself so they can't have this potential problem

they didn't know at the time that the NSA had at backdoor that they just no notice that if somebody inserted backdoor it's a big problem however later on the open SSL project they were chasing down the FIPS 140 - 2 certification and to do that they had to implement this this this algorithm and they said ok well we don't like these parameters either so we're just gonna regenerate our own no they were told no they cannot do that they have to use the existing parameters in the spec so for a time I mean they didn't like this but they didn't have a choice they need they wanted to get this certification they had to put that in so this code is back

to our main event to open SSL some time goes on and after got into the the ansi documented it gets through this in a special publication in June 2006 about a year after that some Microsoft employees shimano and Ferguson they they gave a presentation saying you know hey this is looking pretty shady here but nothing happens for like the next four years for next more than six years or so that was it somebody they just said this looks really Shady in 2011 it becomes a nice so span so you see it goes from being in an ANSI document to in this document and then it goes into an iceless thing and the Snowden leaks happen as everybody knows

and that's when they got caught red-handed here's here's a quote from the New York Times classified NSA number memos appear to confirm that the fatal weakness discovered by to Microsoft photographers in 2007 was engineered by the Agency the NSA wrote the standard and aggressively pushed it on the international group privately calling the effort to challenge and finesse so they got caught red-handed but even more they paid Rs a corporation ten million dollars to include it in their be safe crypto toolkit and not only that but as the default random number generator so are say accepted the NSA's money so when this blew up naturally people got much more suspicious about the NIST P curves like at this point people were very very

concerned

in 2014 an apprentice ting and Lang came out of this x8 curves project it's actually a set of web pages where they evaluate 20 curves across 11 criteria and in that was three of those peekers along with secti 256k one that's the big point anybody want to guess what those results were so if you're a math person you could you could click on any of those those column names and it'll go into like all the math like yours all the math we did on this curve here's why this looks bad and this other thing what's bad - it's well beyond the scope of my presentation so I'm not gonna go into that but basically what it's saying

overall is it's nothing immediately exploitable but it's got these little properties that they're just not looking good and in the crypto world there's that feeling that if there's smoke there's fire so if you're seeing these these red flags it's just not looking good take for example shot one shot one has been breaking slowly for like the last decade a decade ago it had it was showing Kratz you're like some problems and then all the way up until maybe a couple weeks ago I think Google came out with so probably supposedly some method to grease collisions so Shawn's been slowly breaking for a decade at the very least you can look at this and say it's

not looking good you look on the way the bottom there's her route 255 19 straight green across the board not children is curved for 48 but it also had full passing marks

I'm thinking I don't want to read this whole thing out in August 2015 the NSA released this big bombshell of the statement and they'll summarize it basically what had happened as it for two decades NSA was strongly pushing ECC for US government use and suddenly they said you know thanks for migrating from traditional crypto to ECC thank you for for going along with that for putting in all the effort but at this point we don't want you to continue doing that anymore just wait and save your money and wait for us to come out with post quantum resistant algorithms so this was this is just a big block show that got dropped on everybody first of all they

were the biggest proponents of ECC and second of all they don't just make these these like huge statements out of nowhere it was just it was very bizarre so kicked off a whole bunch of conspiracy theories some people thought well if they're moving away from that does I mean ECC is completely broken does it mean that traditional cryptos broken and they don't want people to move to ECC that's a possibility maybe they broke post quantum algorithms and they want everybody to move to that quickly so that they can break everybody's crypto they're all kinds of conspiracy theories I'm not gonna say much more than this list they're interesting and think about what past that there's no proof at the same time

interestingly and sweet bead which is that suite of protocols that they want US government to use they just sadly dropped P 256 they didn't say anything about it just disappeared overnight literally disappeared and they said nothing about it they didn't say anything about why just they replaced it with p34 so to cryptographers couplets and Mendez's they published a new formal paper it's quite in-depth and rather interesting one of the things they talked about because this is a topic that had come up is all right so let's talk about these myths hers may be being back door and this is an opposing view and I thought it was be fair to include them so they showed some

estimations all right and they said all right here's some math they figured out okay an essay 1997 they could if they could iterate let's say 2 to the 48 seeds and that would imply a 2 to the 209 wheat curves would exist in a pool of 2 to 2 to the 257 so in other words there would be this massive pool of wheat curves here's a quote this would mean that this huge class of wheat curves was known to the NSA in 1997 but is still undiscovered by outside researchers in 2015 it is highly unlikely that such a large family of weak elliptic curves would have escaped detection by the cryptographic research community from 1997 to President so this

is an opposing view and I include this because I do want to present this this topic fairly but like I said before I am going to refer to this later this this does tie into what some of my conclusions at the end so yeah they went through those crazy based on the NSA announcement they went through all those crazy conspiracy theories like I said one of the interesting ones that they they floated was was they pointed out that hey you know during the cold war with the USSR their economy tanked like they failed as a result so maybe the NSA threw out that bombshell of a statement because maybe a crypto a cold war could

damage them too and I just concluded that it's kind of like that's our this year's theme for b-sides crypto Cold War but another possibility is well maybe they just what they said it is exactly what they meant we just need to move past ECC in traditional crypto something quantum [Music] so in a summary of that rationale the loop that I wrote out before it does it does sound compelling but I can't get over it look at these seed values there it's entirely possible that they chose them they iterated over them to find weak curves there's just no rationale ever provided I just can't get over that and again like I pointed out before there's that

that project where you can take there's public code you can take a GPU farm and generate your own weak curves and then claim that they were random and of course the NSA got caught red-handed so that was you know that's another thing that really stands out here's a quote from the former director director Hayden from the NSA it's kind of a rambling it sounds like he was talking and they just pointed him directly from the Washington Post it's a little rambling but I'll read it out loud you look at a vulnerability through a different lens even if if even with the vulnerability to require a substantial computational power or substantial other attributes and you have to make the

judgment who else can do this if there's a vulnerability here that weakens encryption but you still need four acres of cranked computers in the basement in order to work it you kind of think no bus and that's a vulnerability we're not ethically or legally compelled to try to patch it's one that ethically and legally we could try to exploit in order keep Americans safe from others so he's talking about this no bus policy which stands for nobody but us so you can kind of interpret this as the missing link so I said before one of the big arguments against the miss curves being backdoored is the fact that the US government uses them so they say well why would the

government push back their workers and if they were done using that themselves well because of this no bus policy if they think that nobody else can exploit these issues but them then they would they could plausibly feel safe pushing them out of public

so in terms of what my personal suspicions are I do think that the NSA did iterate through seeds and chose parameters to show us the seeds that they created the parameters that looked weak at the time and I think maybe they chose them and they looked at them and they said okay well we can't exploit them immediately but they look weak so maybe we can in the future like that thing I said before where there's smoke there's fire it's possible that they had found these sets of curves that said okay well we can't take the bedroom right now but maybe ten years from that weekend and you know maybe they did maybe 10 10 years after that they found

a way to to break all those cryptography based on those curves maybe they did 18 years later which would have been just two years ago maybe they never did maybe if we keep using them three years from now they're going to break them better so these are all plausible things to me but let's let's toggle back and just look at the fast fact is that say first project make sure they showed that P 256 and 3/4 they do have some bad product that's another fact is the NSA just dropped P 256 so they no longer recommended for classified and there happens to be other curves that are created by the community with better properties so in the end

really ask yourself why why continue using the peepers

so in terms of alternative since I just spent so much time up here talking about these these curves that are bad so the question would be well what's better there's this curve 255 19 which is proposed by Bernstein it's to 128 bits of security rationale for all the parameters is provided it's got excellent performance and it's not just academic it's actually being used it's become the default and OpenSSH for like the last three years over three years in the default so it's being used there's this curved 448 also known as the goldilocks it's got the same perks but it offers more security about 224 bits both happen to be formalized in an RFC and there they're actually referenced in

the upcoming TLS 1.3 spec so now here's the punchline so this is why I undertook this big research project is I want to find out how can I get rid of them how can I disable them from a sysadmin perspective something that's practical and you see all the way the bottom I I originally put I got bad news for you guys and I cross that out I stumbling on somewhere the information at just yesterday so I'd update my slides

so I was going to say that in Apache and modest Acela you just can't and there it's fixed so it turns out I was wrong you can in theory still use any of the other curves because if you recovered I said before the SEC two curves were incorporated into TLS so it's there's more than just the peakers there is a sec P 256 K 1 which is 1 it's the big point curve in theory you get you can't use that and after I was wrong after turned out that I was wrong about Apache lavas and so I did say nginx you can't change it either although now I'm starting to second-guess myself but it does always appear by default you use P

256

if you use the SSL scan tool that's the cell scan because it's a tool to analyze TLS tunnels if you run that against let's say a default Apache or nginx you'll see I've got there in bold how you can actually spot that out that's curve P 256 is in use in that cipher suite and you'll see that a lot you see that in all the ECD H and DSA PCTs a cipher Suites so this is what I had just found out very recently in my cell there's this very obscure command SSL OpenSSL con CMD which you can then say alright I just want to use this one curve it seems very very rarely used so

I started thinking well if it's even if it doesn't work only like point below 1% or whatever all servers are using it in production are you sure you want to roll the dice on that I mean it doesn't seem like something that's used very well much at all so you turn that on on your production server what's going to happen and strangely when I then skin with SSL skin after I specify that it still tells me the 250 P 256 is in use so this is a bug in SSL scanner it's about looking to sell I don't know so I don't know what's going on so what you could do is you could disable EC pH

entirely the problem though is that you'll break Firefox because you should have sha-1 disables as well and if you turn off sha-1 and easy th Firefox just as a no cipher Suites left to community and it just gives you that error just says no safer overlap so you can't turn off as of right now I've tested this against Firefox 53 which is a pretty new you cannot turn off ECD age and sha-1 and support Firefox now you can use an ECG DSA an x.509 certificates you've got quite a bit of curves to choose from when you when you generate them but a lot of them didn't pass those that seekers tests and a lot of them even offered less secure than

after 20 bits so there doesn't seem to be good choices there so for now in terms of x5 of nines you probably just stick with traditional or so 3072 or 4096 pinkies

so that some good and bad news about TLS 1.3 is it's currently in a draft stink good news is a curve 255 1948 they're both included in the spectrum but guess what star the mispers and here's a here's a quote from the specs the TLS compliant application must support key exchange with SEC P 256 R 1 which happens to be 2 X just a different name and should support key exchange of X 255 19 so it doesn't mean that everybody's going to be forced to use it that means that compliant applications need to support that so your server 1 being fully compliant has to accept those connections from clients so it sounds like you're gonna be able to

disable them if you want and use these better curves but I get the feeling it's not gonna be there by default so you know right off the bat like 90% of people are just gonna be using the default much better news for ssh these peers were in a part of ssh for quite a long time like I said before the default got changed about three years ago you can use this keeps change algorithms directive it's very easy to just and you can just straight-up disable ECDSA as well so it's very easy that's the good news is it an SSH you can disable that pretty pretty easy by default though a lot of districts just have them sitting there so so there's a

to extend on that there's this excellent hardening guide for SSH available so if you want to know exactly what to do that right there is an excellent part of god I use that all the time I also talks about how you just save a lot of things like shadow 1 do USA and other stuff you could probably even disable more than what's in that guy because there's a new version of putty became out stone so we bring SSL is it's a fork of OpenSSH but they're bound to adhere to the spec TLS 1.0 1.1 1.2 they have to abide by the spec so it's all in there we'll see how would you go about to get going I'm working Frank I've been

told we've done I never confirmed it but I've been told that banking algorithms have to comply with NIST families it's just part of that so this yeah if it's one for tf2 was 186 s2 so because I've you know sent concerns you had like recommended like Curt 25 519 this off from like what we can't do that because we have regulatory things that we have to meet how do we address something like that I mean to other than sort of you know I'm trying to get missed to change your standards you're just you're bogged down by just a whole lotta red tape you have to comply with your regulations invoice get massive massive on caffeine that's right

there the problem so you have to change the regulatory compliance standards which that's a massive I mean you don't really have a choice

any other questions

with that TLS curves that are one of the things that I suppose that yeah I suppose that does that is a factor and the conspiracy theorist will say like oh my god there's they're just pulled with NSA moles the other rationale could be that well here's curves that have been used and tested and we want to be conservative and not really rush into these other things that's another perspective what's really going on I you know I can't really say yeah let's see theory on this just a sec do you think that protecting the information if these are compromised cryptography is what's holding back the 17 agencies of disclosing how they know oh yeah I'm not moving because they

didn't do an awful lot to hide their tracks fallen into the cozy barracks off there so the Cold War is to make enemy reduce the value of their assets by making that's well the when I was bringing up before and this was not my this is that my theory was just a period I just thought it was pretty amusing so I just talked about it the idea was that you know in the Cold War their economy just failed I think they couldn't handle that string where as hours worked so the idea is well maybe that's what they're trying to do it's like let's force them to waste lots of money by saying hey everybody needs to move to post partum photography

and now China and Russia is just gonna like exert so much effort to try to get to that and they just waste a lot of money and it's like ha we got you to waste your money back on it but in terms of any kind of relation to what's been going on lately I don't think there's all that much ovens well I'm not really if there's

right let me comment on that if I just came from the clock words then it's a former NSA whistleblower world ingenuity knows this theory on this is because we basically the only way that they could do this is they way because they basically take like equipment in fact or like Roger gruesome you know switches everything and so they put like you know things like trace routes and stuff in budget isms he says they could of if it came from Russia they could actually like nail it down to the exact building it came from because but his theory is that they don't want to do that because they were done reveal put your capabilities let's go outside

yeah I don't think it has to do with the curve that elliptic curve technology so much as is but I think it is other things that they don't want any other

[Music]