'Jerry Solinas deserves a raise' with Steve Weis

'Jerry Solinas deserves a raise' with Steve Weis

SCW's Picture
SCW episode cryptography security nsa nist elliptic curves seeds hashing backdoors dual_ec_drbg

We explore how the NIST curve parameter seeds were generated, as best we can, with returning champion Steve Weis!

“At the point where we find an intelligible English string that generates the NIST P-curve seeds, nobody serious is going to take the seed provenance concerns seriously anymore.”

Links:

This rough transcript has not been edited and may have errors.

Deirdre: Hello. Welcome to Security Cryptography Whatever. I’m Deirdre.

David: I’m David.

Thomas: I’m whatever.

Deirdre: And we have a returning champion today. Our first entry into the N-Timers Club, and you’ll get a bomber jacket at some point, I swear: Steve Weis. How are you, Steve?

Steve: Good, how’re you doing?

Deirdre: Awesome. Thank you for coming back. We’re having Steve back because he wrote a cool blog post about new kind of folk history gumshoe journalism about how we generated those NIST curves, the P curves that are the most popular elliptic curves used in modern cryptography. Steve, what have you found?

Steve: Yeah, I’ll jump in with a little bit of background. So, as you all are aware, whenever there’s any sort of news article about the NSA involved with crypto, there’s going to be a threat on it, and somebody’s going to talk about these ECDSA curves that historically were first developed by ANSI, which is like a standards committee. And it was basically organized by the American Bankers Association. So this is back around 1990, 1998. And this is when these things first appear in print that I can find. Some of these things are behind paywalls. So it’s kind of like whatever pieces we can find on the Internet. And this document, which is linked online, has many different curves in there and many different what they call examples.

They’re not even saying that these are like the standards. They use the word, like, example curves. There’s a good number in there, maybe like, kind of counting off the top of my head, like 20 of them, 15 of them, and different types of curves. So things with prime order, things with binary curves, and among those are two that ended up in a later spec by NIST. And this is like the NIST standard that we all refer to when they call these NIST curves. It’s FIPS 186 two. This is around the year 2000.

So this is a couple of years later. These curves in the ANSI spec eventually appear in NIST, they eventually appear in other standards, there’s one called SEC G, which is out there, too, and basically, the idea is that there’s these constant values that are used to define these curves. And a little bit about how that works: the idea is that you pick some constant, and then you hash that with just at the time SHA-1, and then you take the output of that hash, and that defines what the rest of the curve parameters are.

Deirdre: The point and the other the coefficients of the curve.

Steve: Yeah.

Thomas: Can I ask a question real quick, just because this is a thing that has tripped me up forever, right? So, when we’re talking about the definition of a curve, so a curve itself, when we use the word curve, we’re talking about like a pretty simple high school math algebra equation, right? Or formula or whatever, right? It’s just like y equals x three plus two x.

Steve: I don’t know what it is.

Thomas: Right. So, the curve itself is defined by the coefficients on the right-hand side of the equation and then a base point. Right.

Deirdre: And the base field prime.

Thomas: Yeah. And the prime, I think of the prime as something that, we don’t generate that at random. Right. We’re careful about picking the prime. So it has nice properties for— even the NIST curves have like— nobody’s wondering why we have the primes that we have for the, tell me if I’m wrong about this, but my understanding thing was that we’re not so much worried about the primes, but we are wondering about the coefficients. You might also worry about the base point, which is like a thing we all have to agree about, that we’re all going to start from this one point on the curve to do the rest of our math. Is that right?

Steve: That’s correct, yeah.

Steve: For the prime, there’s many curves in the field of that order, prime. So the idea is that there’s a seed that defines these other coefficients and other parameters, base points, and that you could have many of those. So you’re kind of picking one arbitrarily. And the concern here is that these just appear in the text. It’s like, okay, here’s a seed. And they say these are verifiably at random. And the idea is when they’re saying verifiably at random, they’re saying that you’re running it through a hash function. They’re basically saying, “Here’s some value, and it’s going to be random because we ran it through SHA-1.”

That’s what they mean by ‘verifiably random curves.’ And it’s not really because you can imagine that you just sit there and pick these seeds until you get a curve that you like, for whatever reason you’re familiar with it. But if people at home are interested, there’s this really good summary of this whole controversy that was about eight years ago by Neil Koblitz and Alfred Menezes, called ‘A Riddle Wrapped in an Enigma.’ And they go through all of this of how this is generated, why it would actually be hard to pick… if they were able to do this, it would have implications on that, these curves would be weak for other reasons. And that’s actually probably a better paper just to read directly. I think today is kind of more on all the rumors and things around this.

Thomas: But this is a big deal because this is one of the oldest conspiracy theories in cryptography, right? So I have to be careful here, right, because I have the misfortune of also having said that Dual EC was also probably a conspiracy theory. Not that anyone should ever use Dual EC, right, but it was so dumb looking that I kind of doubted that it was enemy action and just thought, this is just really stupid, and nobody pays attention to it, right? So, with my luck and me saying that this is a conspiracy theory, the likelihood that it actually is an NSA conspiracy, I mean, you should weigh it a little more heavily. Right? If I make a claim, the claim is probably wrong. But this is one of the older conspiracy theories in cryptography, that the most popular elliptic curves that we use for internet cryptography were selected by the NSA, and they were selected in a way that we can’t understand why they were selected. And clearly, that was because they’re backdoored.

Deirdre: To be clear, it’s because people do think that the parameters for Dual EC were NOBUS-picked because there was an actor who went in and broke in and changed the seeds for a deployment to theoretically have deterministic randomness spat out of Dual EC DRBG. So why would you do that if there was no— if you pick your parameters, yada, yada, yada?

David: To be fair, they changed the parameters because they probably didn’t have the original backdoor, and they wanted oh, yeah, they built their own, because the backdoor-generating machine that everyone knows is there.

Deirdre: Yeah. So someone, theoretically— the NSA backdoored Dual EC DRBG, and then someone else went in, broke in, and changed the keys, and used the fact that the NSA had put a backdoor in for just them to use to determine randomness and break VPNs and all that stuff.

Steve: Some history for people listening, too, is that the NSA, one of the things that came out is they had paid companies like, I think, RSA and somebody else, like, $10 million to support this random number generator (that’s slow) pretty much at its publication time, everyone’s like, hey, you can backdoor this almost immediately. And so they paid companies to support this. And the thing you’re talking about, I think, is the Juniper one, right, where they went in and used it as designed. And I never heard any resolution as like, who did it, China, was it? Who did it?

Thomas: So that’s yeah, that’s like, the second funniest thing that has ever happened in cryptography. And what we’re about to talk about is, I believe, a strong contender for the funniest thing ever to happen in cryptography.

Deirdre: I think it’s even funnier because I think exactly the opposite of what you said, that this conspiracy theory may just have been silly and dumb and not disproven.

David: The difference here, though, is that we know, and we have known since forever, that Dual EC could have a backdoor of structure X, whereas we have no idea what that structure would be if the NIST curves were somehow backdoored with their parameters. We don’t have the oh, it would be this way.

Steve: Everyone I’ve talked to doesn’t think there’s actually a backdoor in these NIST curves. They think, some people have different things about non-rigidity and the selection of the curves, but that’s my take, is that I haven’t run into somebody who’s really convinced by it. Other than on internet forum threads.

Deirdre: Yeah. So, Steve, you started just kind of knocking on doors and asking questions. So, like, what kicked you off on pounding the pavement to talk to some people about this just now?

Steve: Honestly, there was one of these threads a few weeks ago. I can’t remember what it was, but the NSA was in the news, and it came up again. I was like, I should pick this up again because I actually sent a Freedom of Information Act request to NIST and NSA about five years ago. NIST, their response was we don’t have any documentation about our own specs or where the origins of this and our specs. Looking at it now and kind of digging in more history, it makes a little bit more sense because they were just copying some of them from ANSI, but there’s other ones in there, there’s other seeds in there that aren’t in the ANSI spec. So that was a little unsatisfying.

The NSA one just went dead. Like, they replied once, and no response after that. I think this is largely because I don’t know what I’m doing, and somebody who can write one of these knowing how to ask the questions could probably get further because the way I phrased my questions were ways that they can’t actually answer. They were more like, there’s a way to ask these things. So, that’s not a dead end to actually send a FOIA request to the NSA. Somebody pointed out that some of the stuff may automatically get declassified after a 25-year period, which it has been, so.

Deirdre: Right.

Steve: There may be things there that would be publicly available. Anyway, this kicks it off again. I start emailing a couple of people, like, hey, did you ever hear about how these were generated along the way? I did get, finally, some definitive confirmation. Like, Jerry Solinas was an NSA employee whose name had been floating around for years. And finally, I got in writing that, yes, he is the person who handed the seeds to the ANSI X nine six two committee. And that was Alfred Menezes, and he was chairing the committee. So that’s a clear answer. These definitely came from the NSA.

They definitely came from Jerry Solinas. We don’t know if Jerry generated them. So that is, like, one discovery. I think it was well known, but, okay, that’s clear. Unfortunately, I think I mentioned that Dr. Solinas died earlier this year. So the best thing would have been to just ask him. And it turns out that several people did ask him about ten years ago.

So that’s kind of where the latest stuff came off, is when the whole Edward Snowden thing dropped. A bunch of people emailed him and asked him, like, hey, where’d you get these seeds? And so probably this goes to this story is that the story is that he just wrote some English phrases, hashed them, and then eventually lost the phrases and was not able to remember them 15 years later. That’s the story. And we’ve now kind of gotten separate multiple people who said they heard this. Unfortunately, the one person I asked who was not at NSA, they were involved with IETF and crypto standards at the time. They didn’t want to get quoted because they kind of didn’t want to embarrass Jerry Solinas. It wasn’t like they couldn’t. I quoted them in the blog post.

This also was in some comments by Dan Bernstein and Tanja Lange on one of their submissions to NIST that they had heard the same story from NSA employees. Two NSA former employees reached out to me and repeated the same anecdote, and they also don’t want to be quoted, but I’ve heard it from four different people now, and the one or the two kind of clues that came up was like, somebody said, oh, there’s actually two names in there. By the way, the phrase was that Jerry deserves a raise. This is not the actual phrase, but this was the recollection of somebody from ten years ago. And then somebody else was like, oh, no, there’s actually another name in there, and the counter. So that’s all we have. Okay, so it’s kind of interesting that we’ve heard this from multiple people. And what I would like to get out of this is somebody who was antsy on the committee at the time or at NSA, who can just confirm the stories, like, oh, yeah, he lost the phrases.

And then this thing, it’s not put to bed because we can’t verify it, but somebody’s at least putting the reputation on the line that, hey, he told me he did this, I was credible, either you believe this, or you know, that puts us in a place where it’s not so much mystery around it.

Deirdre: Yeah. And the idea is that he had a phrase either something like, Jerry deserves a raise, or like, me and my buddy deserve a raise. And then you, whatever, ASCII-encode that into bytes, and you shove it through what? SHA-1. And then you, whatever, split the image of that in two into the A coefficient and the B coefficient, and that’s “generating a random curve” when you’ve already picked a prime field or whatever. And then you see what that gives you. And then, if you don’t like it, you just add a counter to the same phrase, and you try it again. And you try it again, and you try it again, and you try it again until you find some curve params that you’re happy with. And you’re done. That’s, in theory, how it went, right?

Steve: Yeah.

Thomas: We don’t know for sure that it’s just SHA-1. Right. Like, it could be the output of any kind of string-based PRF or something like that. Right?

Deirdre: I think that’s right.

Steve: It could be. But it’s suspicious because the scenes are 160 bits, which is the length of the SHA-1 output. So whenever I see 20-byte output, I’m like, that’s SHA-1 output. That’s my intuition on it. But you’re right. It could be anything. It could just be him rolling dice on his table, too.

Thomas: But once we have the output of whatever that PRF was from there on, we know that the curve is defined well, right? We don’t wonder how they got from the 160-bit value to the curve parameters. That’s all documented, right?

Steve: Yeah. And also, to clarify, too, is like, the seed-to-curve is documented in there. And so we’re saying the way they got the seed is like another precede image, and that’s not in the spec. And there’s a little bit of confusion on my part about that. But you can pick any arbitrary value and throw it in SHA-1 and then try to get a curve from that. And that is the spec. It’s arbitrary. It doesn’t say this needs to be random.

It doesn’t say anything. Just says, pick literally any string and hash it, and then try to derive a curve from that. And some of Solinas’s own RFC Zero said, this is the thing we did. We picked an arbitrary string, hashed it, generated a curve from that, and repeated if it wasn’t a valid curve.

Deirdre: And in the first ANSI document, they specifically mention SHA-1, and it hashes to values of length, exactly 160 bits. And so, in context, it seems that’s likely.

Thomas: And it’s the only thing that hashes to 160 bits. Right. Like it’s weird with the block size there, right?

Steve: Yeah. And so this is a good aside, too, is that in that same antsy dock, there’s a bunch of other seeds. And these pretty clearly do not come from NSA because they have the name of Mingwa Chu in there. He’s a cryptographer who was at Certicom at the time, and he’s one of the co-authors on the MQV kegerman Protocol. The seeds actually have his name encoded in the mask. And I thought this was weird, too. It’s like, if your theory is that the NSA backdoored some seeds in this doc, there’s like these other seeds there that are clearly just like jokes. Like the guy put his name in know, throws a little confusion there, too, because these are clearly not the output of a hash either.

So, like, taking basically a string with his name in it and then hash that to generate the curve. But those ones are not ones that you would go find, like a pre-image of that. I thought that was a weird one that these are just co-mingled in there, and some of those ended up in later specs. And this has been known for a while. We just noticed it as we’re looking at these seeds. Like, hey, there’s a bunch of repeated bites in a bunch of these seeds. And then somebody’s like, oh, that’s actually ASCII. So that’s kind of a weird question, too, is like, all right, it undermines the conspiracy theory that, okay, they went back, and they backdoored just a couple of seeds, but then there’s a bunch that clearly are not backdoor.

The guy’s name shifted back and forth.

David: Classic misdirection!

Thomas: Yeah, depending on how many times you shift it back and forth, right? Or what you do to manipulate or where it’s positioned in the seed, or how you abbreviate it. There’s so many degrees of freedom, you could come out with any kind of backdoor just based on the name of the guy. Which is going to be what people say if we ever uncover what the seed is.

Steve: Right, yeah.

Thomas: Because this is like a really basic old exploit developer thing. Like, if you’re going to claim a zero-day vulnerability on Twitter or something like that right? You make a hash prediction. And every time I’ve ever made a hash prediction, I’ve always included a random counter into it. I literally just generate a random number because this is very silly, right, and also very egotistical. But when I post a hash, I’m always worried that some weirdo is going to try and brute force the hash. So I always include some random number. It says, like, whatever it was that I’m claiming, you’re not going to be able to dictionary it to find out what it is.

Right. So the idea that it’s a string and then like a counter in there, and we think the counter is in there because if you just say Bob O’s Jerry arrays, there’s a decent chance that the SHA-1 of that is not going to be an acceptable set of curve parameters.

Deirdre: Right, right.

Thomas: You start with Bob O’s Jerry arrays one, and then you iterate till you find one that’s.

Deirdre: I’m looking at the appendix. Right? Cool. Like, I enjoyed your whole post putting all this sort of stuff together, and it feels like every couple of years, people are kind of revisiting what we know about this little period, this story, and this little period of history. And now you’ve kind of collected a bunch of new stuff and put it all in one place, which is extremely useful. One of our friends and one of our earlier guests on the Pod, Filippo Valsorda, has opened a bounty for people to try to crack these seeds and try to figure out how they are actually generated.

Thomas: Right. Because if it really is a string, if it really is just some variant known name, x owes Jerry a raise with a counter in it, right? Like you’re baiting password. Right. So I’ve noticed on message boards, packer News, really? I’ve noticed people like, what are you going to do? You’re going to take the hash and find the pre-image of the hash? You can’t do that. That’s the whole point of hash. It’s like, no, there’s a whole sport in security of finding the fastest way to generate all possible permutations of every possible string that’s an input to a hash function that is matching it.

Right. So there’s a whole group of people that do this just for fun. Your hope is if it’s really the case that all they did was take SHA-1 or some stupid combination of hashes or something like that and then hash a string, it should be possible to just grind through every possible permutation, get chat GPT involved. I don’t know what you’re going to do there to generate all the permutations because I don’t crack passwords. Right. Other people seem to derive enjoyment from this. Right. And if you can crack that hash, if you can come up with a hash that maps out to the same seed, you put this to bed.

Deirdre: Yeah.

Thomas: And it’d be like one of the biggest revelations in it be like, it’ll be in.

Steve: I mean, one thing to point out, too, is that the claim is that Jerry Solinas tried this and couldn’t remember it, but we don’t know how hard he might have. Like, I don’t think he was unleashing the full power of the NSA on.

Deirdre: This or even just.

Steve: You know, it’ll be interesting. And we don’t know how long the phrase is either. We don’t know if there’s any other thing. Like you mentioned, it may not just be like SHA-1; it could be whoever or whatever.

Thomas: But if you can’t get past, if you can’t work from that set of clues, then figure out what this hash is, you are not a good password. Really. You’re not really in the game, right? So somebody who’s in the game is just going to do it to prove they’re and like, I don’t know how hard Jerry tried to do anything, but I have in my office a bucket full of USB hard drives that are all perfectly secured by dint of me having forgotten the passphrases that unlock the disk encryption on. So like, I totally get where Jerry is coming from on this, right? I lose most passwords, right? So that’s totally a plausible thing that could have happened.

Steve: So I’ll put some teasers out there because there was a couple of other leads that I have not published on this. But one is somebody who is pretty well known, says that they had an email exchange with Jerry Solinas around ten years ago and he said in the email directly that this is how he generated it. So maybe there’s some more clues in there. I’m working on getting them to actually publish that. The other one is they gave me the name of the person who wrote the code that they supposedly used to do this and I found him. He’s not responded yet, but he was an NSA employee at the time and is now working in private industry. So that person is still apparently active but did not respond in time for.

Deirdre: This how is this not just like, a shell script? I feel like it could just be like a fancy shell script. I guess if you’re trying to, like sure.

David: But even within a shell script, you got to write, was there a new line? Was there not a new line? Like, that might be helpful.

Steve: Yeah, but it’s not just the seat pick. I think he wrote the code that actually did all the rest of the curve checking and all the order checking the rest of the X nine two spec, which is not super complicated, but it is big energy mo.

Deirdre: But you don’t want to do it in bash?

Steve: Yeah, I don’t think so.

Thomas: I guess I have a couple of questions here. Right? So my first question is about cryptography. I’m trying to figure out what order I want to do this in. Right. But the first question is about cryptography. Right. So there’s a subtext on the NIST P curves. I always say just the NIST P curves, which I don’t know if that’s the right terminology, but the curves we’re talking about are the curves that I would call the NIST P curves.

It’s the standard TLS browser curves, right?

Deirdre: 56 and ilk. Yeah.

Thomas: So when we’re cryptographers, when certain cryptographers, when a specific cryptographer is talking about the difference between the NIST curves and the providence of the NIST curves versus alternatives, the subtext is really the P curves versus curve 25519 or other of.

Deirdre: Its kind of cohort generation.

Steve: There’s no other real contender. I mean, look, those are the two horses in the race.

Thomas: There’s four four eight. If you’re not worried about Rambus’s patent trolling attempts to use four four eight.

Deirdre: Take over the Internet too big, no one uses it.

Thomas: Okay, that’s also Internet conspiracy theory. But the subtext is the P curves versus 25519. Right? So 25519 has some other nice properties. Like, one of the nice properties is there isn’t a conspiracy theory behind it. Although although although it would be the 0th funniest fucking thing in the history of the Internet if there was some weird backdoor in curve 25519. You heard it here first.

David: It’s actually a supply chain attack in 25519. When you download the software distribution for testing it, it installs what is it, Qdns or whatever on your system.

Thomas: Okay, so one nice thing about it is that we don’t really wonder so much how they came up with how the parameters for 25519 were chosen. But there are other nice things about.

Deirdre: 25519, and that’s because they made a big show of, quote, nothing up my sleeve about these things that the creators of two 5119 and kind of that cohort of curves said are good things to have when you’re picking curve parameters.

Thomas: I remember CFRG is the Internet’s kind of crypto review board, and there was a huge debate on CFRG about standardizing 25519 as it existed, or tuning up 25519 before standardizing it, or adapting some other curve right? And there was this big argument about nothing up my sleeves numbers curves versus 25519, where, again, I’m probably wrong about this, and cryptographers or certain cryptographers or a specific cryptographer is probably going to tweet or something that I’m completely wrong about this. And I accept that off the bat, my understanding but like, really delayed. And in three months, my understanding of that whole drama was that the nothing up my sleeves number thing is not the right approach. And the right approach is to come up with a set of engineering principles. Like, this will be fast with the multipliers that are in standard 64 bit CPUs, and we’ll use these operations and won’t require point validation. Like, here’s a set of engineering constraints, and here’s the simplest possible thing you can come up with to fit those engineering constraints. In other words, the right approach to coming up with a curve that everyone can trust is to take a list of properties that cryptographers or certain cryptographers or a specific cryptographer comes up with and says that those are the right parameters and then just fit the curve to it versus what I remember as the brain pool argument, which is the right way to do this is to come up with Pi e and a couple of other mathematical constants, glom them together. Everyone trusts pi.

NSA didn’t backdoor e and then use that to come up with and then cryptographers or certain cryptographers or a specific cryptographer wrote a paper where they took every possible permutation of pi e and other mathematical constants and came up with a kind of model backdoor curve that started they didn’t backdoor a curve because that would take real energy, but they came up with a curve that started out with a string or certain strings or a specific string. And by being able to take Pi and coming up with that string in the curve, you’d prove it. So this is a total aside, by the way. There’s this notion of nothing up my sleeves numbers curves, and then there’s the just do the engineering, right, and it’ll be obvious to everybody. But back to my original thing, right? The subtext of the NIST curves versus other curves is really the NIST curves versus 25519. And there’s a lot of good engineering in 25519, right? The biggest thing for me in 2519 is you don’t need point validation, right? So this is like a huge thing when you’re doing DH with a curve, right, which is to say, if you’re doing TLS and you’re doing key agreement or whatever, a huge problem you have is that with kind of ordinary short wire Strauss curves I can’t pronounce that word, but whatever with the normal curves, right? When you get a point, a point is just a pair of numbers. It’s exactly what you think of as a cartesian, right? But obviously not every if you imagine the cartesian plane and you draw a picture of a. curve in your head. Not every point on that plane is in the curve. Most points are not on the curve.

Deirdre: Right?

Thomas: And if you accept blindly a point from somebody else that is not on the curve and you do the math with your key based on that and give a response back, you will leak some of your key. That’s actually like, I’m drastically simplifying it, but if you know Chinese remainder theorem, it’s a pretty trivial exploit, and it just sucks the private key out of the other side of the connection. It’s awesome. It’s a great attack, right? And 25519 is intrinsically not vulnerable to that attack, right. Any 32 byte string is a valid curve 2519 key, which is a great property that is not a property of the P curves. But the other big bit of nice engineering, about 25519 is that it has complete addition formulas. Now, this is a name that I’m dropping without having a complete understanding of what the fuck I’m talking about, right?

Deirdre: It’s literally like you can add or do a group operation with any of the points of the curve of the group, and there are no exceptions because with the original short virus stress formulas, it was like if you try to add P to itself. You do something different than if you’re adding P to Q or if you’re adding P to the identity, or there were basically four major cases of where you would do something slightly different, which made it hard to implement in a side channel and bug free way.

Thomas: Whereas each of those cases is an if statement. Right.

Deirdre: You just watch for the and so for with Montgomery curve 2519, it’s just there is one formula for doing the group operation for any of the points on the curve, including the identity. And it’s just one instead of four things you have to get right. And doing all these if statements, there is just one operation you have to get right. And that was very nice to that was the first one to bring that to the table. For elliptic curves, to be fair, we.

David: Have since found complete formulas for the NIST curves in the past.

Deirdre: Nowadays, five, six, which, to be fair.

David: I think, convert them to the Montgomery, effectively convert it to like a Montgomery style curve. I thought that there’s a way of thinking about it that is like I.

Deirdre: Mean, you can we’re doing a transform.

David: To that style, mathing it and transforming it.

Deirdre: I may be mistaken, do that, but I don’t remember if that’s yeah, maybe it does, but yeah, we do have complete formulas for the short fire Strauss curves that includes the P curves and they are basically fast enough now. So you don’t just sacrifice speed for niceness. I guess you basically close the gap between getting the same speed for better formulas with short fire styles. But it took 1615 years from when the PE curves were standardized to get there.

Thomas: The question is the longest question I’ve ever asked. Right. The question is, if the subtext of this whole NIST backdoor thing, at least when certain cryptographers talk about it, right? If the subtext is we should be using 25519 and not the NIST P curves, my default answer there would be that’s, right? Like, we should not be using the P curves. Right. 25519 is in advance. Is that true? Do we still think that’s the case? If we vindicate the provenance of the seeds for the P curves, should we go back to using the P curves?

Deirdre: Well.

David: There’S no point in changing TLS at this point.

Steve: I think it’s just like, we use the stuff that’s standardized and is widely available. And so curve two five 5119 is, like, generally my preference, but somebody said you need to use standardized curves, and it’s already in the library and it’s there, and it’s like, you use that. So I feel like just because it got standardized earlier and it’s the only game in town, like, we’re stuck with P two five six for indefinite. There are standardization efforts for 25519. I noticed that. And I don’t know the state of.

Deirdre: It right now, but it me either.

Steve: Pretty far along, actually.

Deirdre: I mean, it’s standardized for IETF, and I know NIST stuff has been pointing over there. I think there’s something standardized in NIST so that you can point it out if you’re doing NIST stuff.

Thomas: This is kind of a big deal, right. Because of WireGuard. Right. WireGuard is the best VPN protocol in the world. And one of the things that makes it the best VPN protocol in the world is no choices. No choices. Right. No negotiation.

Thomas: And the crypto stack that it picks is essentially the Curve 25519 stack, if.

Deirdre: You want to call it that.

Thomas: Right. And a thing people bring up every once in a while is, well, that’s great, but you can’t use WireGuard everywhere because some places need kind of NIST approved or FIPS approved cryptography. Although I thought there was, like, FIPS approval for 25519 right now. I don’t know.

Steve: Right. I’m trying to look in the specs and see if it’s actually been added. I know it was proposed about four years ago and navigating this website as we speak, but yeah, today, I don’t think there’s any FIPS support for 5119.

Deirdre: I haven’t heard about FIP support, but I will say that beyond just sort of like, we standardize these things, and now we include them in regs, like, things like FIPS, and they’re deployed everywhere. One thing that when we adopted these Montgomery curves, so curve to 509 is the Montgomery Curve model. And then if you’re doing it for signatures, you turn it into the Edwards Curve model, which is ed 2519. You got those complete formulas, and you got these niceties about implementing them in Constantine, using the Montgomery ladder to do your Scalar multiplication. You got all this stuff that made implementing these things nice and less error prone in terms of doing scalar multiplication. However, we went from these shortfire Strauss curves, which were completely prime order, aka you don’t have any other points on the curve that are accidentally not in your prime order group to Montgomery curves that have to have a cofactor of four times the actual size of the prime order group that you’re actually trying to operate in. And for the Edwards curves is a cofactor of eight. And this has led to some attacks on the protocols that have assumed a prime order group of when they’re either doing diffie hellman or other sort of group operations and they slotted in a curve to 5519 or an edwards two 5119 or a different Montgomery or Edwards curve and then didn’t check to make sure that they either eliminated the small cofactor points or other weirdness like that.

Deirdre: Or, for example, if you’re using it for signatures and you’re validating public keys and you rely on the validity of signatures to determine what is consensus on, say, your blockchain. It’s really important that all implementations of your algorithm agree on what is a valid point and actually a valid signature, including are these prime order ones in and the cofactor points in or are they out? Or how do you verify? Do you multiply by the cofactor? Do you not? All this cofactor shit we never thought about or had to think about when it was just the prime order curves. So there’s been a lot of movement to take these advantages, the speed and completeness advantages of these Montgomery and Edwards curves and turn them into prime order groups again. So they get all the nice things. They’re fast and they’re prime order, and you don’t have to think about this shit, and you have all that sort of stuff. But then we come back to the NIST curves, to the P curves, because now we have better formulas for them and they’re fast enough and we still don’t have to think about these cofactor issues. And they’re already standardized. So I think we may like, are the NIST prime?

David: They’re prime order, or are they prime power?

Deirdre: I think they’re prime order.

David: Prime order.

Deirdre: I think peak 56 is prime order. Yeah.

Thomas: So I think crypto hipsters are all kind of aware of the cofactor argument about 25519. Right. And part of this is just me checking my intuition. Right. But my intuition for the attack here is because of the Cofactor on 25519 for any given signature under a signing system. If you’re not careful about this, there are n other identical signed thingies. And it’s the same document that you’re signing, it’s the same Blob that you’re signing, and it’s the same key, but it’s multiple different signatures that would all map back to that same tuple of key.

David: And there’s as many signatures as there is the cofactor.

Deirdre: Yes. And the verification algorithm matters if you multiply by the cofactor or not changes whether or not your signature is considered valid or not. And the specification for Ed 25519 signature scheme said you can, but you don’t have to do whatever. It’s fine.

Thomas: And I know there was a vulnerability and certificate transparency about this, right. In an early version, like a draft of CT or whatever, there was some knit about, but you can see kind.

David: Of like it still exists now. It’s just that you can submit the same certificate, like cofactor times in any or even in the ECDSA case, you might be able to make it negative. I don’t remember.

Deirdre: I didn’t know this.

David: So you can submit certificates more than once, which could be a vulnerability. Could not be a vulnerability. It doesn’t really have any impact on security. It’s just a dick way to eight x the load of a CT log. There’s much easier ways to do that. Just querying it.

Thomas: This is my problem when I hear cofactor is that the real obvious place where this is a problem? You can kind of just get here by intuition, right. The system where it really matters that you can’t submit the same signature more than once is a cryptocurrency. Right? It’s a built in double spend or whatever. Right. So it matters a lot for blockchain applications.

David: Yeah, there was a theft based on.

Deirdre: The oh, yeah, there was.

David: I don’t remember what chain it was or where, but it definitely happened.

Deirdre: I would argue that having, say, client software, that there’s multiple implementations of client software and they should all agree on what is a valid certificate signature, and they disagree. But according to the spec, they are both valid implementations of this verification algorithm that can lead to problems like someone giving you the wrong certificate. And they’re like this one, you don’t multiply the cofactor so you accept it. But this other person does multiply by the cofactor, so you don’t accept it or something like that. It’s not currency.

Thomas: So even with complete addition formulas, and even with the cofactor and these are originally ECDSA curves, so maybe the cofactor thing matters a lot. Right. But even with those two things set, you still have the problem with the NIST curve that you have to verify points when they come in.

Deirdre: I think that’s true.

Thomas: And that’s cheap. It’s not expensive. You can just do it. Like every crypto library should just do it. But if you forget to and you’re doing a key exchange, you could be very sorely fucked. Right. It’s one of the few crypto exploits.

David: I’ve I think it depends on your addition at your algorithm.

Thomas: Again, I guess there’s arguments on either side, right?

Deirdre: Sure. It’s all pluses and minuses. There’s stuff you don’t have to worry about with these cofactor curves, and there’s new stuff you have to worry about. And there’s stuff that you didn’t have to worry about with these primordial show Firestars curves. But you do have to validate points and things like that. It’s pluses and minuses all around.

Thomas: This is like my other question about this, which is less about crypto, about computer. I still don’t know what your first.

David: Question was, to be honest. We’re going to have a second bounty, the twelve K for Thomas to ask a concise question.

Thomas: Yes, we’re never going to get there. But the first question is, say we solve this, say we find the seed. Everyone believes the curve is benign. Should we still use 25519 for all new designs? Or should we take seriously at the idea of using the P curves again?

Deirdre: Right, I think we should take seriously because P 256 is the most popular curve in the world besides the bitcoin curve. And I don’t have head to head numbers, and the bitcoin curve is SEC P, but P 256 is most popular curve on the internet. So certificates, TLS, handshakes, all of that is like 70 plus percent negotiated with the P 256 curve. I think it would be, in my opinion, I think all of the reasons why the curve 25519 and the Montgomery and Edwards curves, the speed, the completeness formulas, the niceness, the side channel resistance, that sort of stuff, has basically been the P curves. And the research on implementations and algorithms for short fire stress curves has caught up to that. And there is not a nice compelling reason to favor the cofactor curves over a modern up to date implementation of P 256. And in fact, that there are arguments in favor of it, amongst them, the fact that it is most supported. It’s a prime order curve and yada, yada yada.

David: Can P 256 do key exchange or is it just signing?

Thomas: I should know this.

Deirdre: I think so.

David: I thought it was just signing. Like, I’ve never seen a diffie hellman using P two six. And TLS only uses it for signing.

Deirdre: I mean, you can signing, I don’t know if anyone does, but you absolutely.

David: Can do that like TLS does x two five nine a lot of the time for key exchange and then P 256 to sign it. Let’s see, because the web PKI doesn’t believe in 25519 crypto for no particular reason other than there’s not a big reason to change in the web PKI.

Thomas: The argument for the P curves is very strong. Right. Because the invalid curve attack is not a signing attack. The cofactor attack is the signing attack.

Deirdre: Yeah, although there have been I don’t remember them, but I do remember that there was an ECDH issue involving cofactors. But yeah, the things that seem to bite people the most is people can’t agree on what a valid signature is and different things will come up as valid, which is not good.

David: I think the actual answer to this question is whether or not someone finds the seed for the hash for the seed to the P 256 curves. You should not use that information at all in deciding which elliptic curve to, like, this entire episode or Steve’s post?

Thomas: None of them.

Steve: Argument on the Internet just to be right on the Internet.

David: That’s all about yeah. This is about the Xkcd comic if someone is wrong on the Internet, not about what curve to use.

Deirdre: Oh, yeah.

Thomas: My second question is much more in that vein. Right. It’s almost just a grudge settling thing. Right. Which is it’s definitely the case that some of the drama about the B curves and the backdoors is about 25519. Right. So you said earlier, Steve, that cryptographers or certain cryptographers or a specific cryptographer posted a submission to NIST where they said that they were aware of the story, that Jerry Solanis just asked for a raise with these curve C’s, and that’s all it was, was him trying to get a better paycheck. Right. And it was not a backdoor. Should we have been more aware of that when those people were also writing papers about how Pi is backdoored?

Steve: Yeah, I mean, I think it would have helped the story here because it was useful information, and you could have gotten a situation when Jerry Slings was still alive where we could just say, look, either you accept this a story, or you think he’s lying through his teeth and putting his reputation on the line. And that’s what I’d like to get now, is get somebody who is actually there, be willing to go on the record and say, yeah, he lost the seeds. We don’t know. That’s fine. That’s a fine outcome for me. I don’t need to find the seeds, but I’m kind of okay if somebody just tells the story, because right now the annoying part is that nobody will answer the question of, like, well, how did these get generated? And even if it’s a dumb reason that, yeah, we just lost them, that’s fine. I believe it. Other people won’t other people will not believe that.

Steve: That’s fine too.

Deirdre: I mean, it’s such a prosaic banal explanation that I really think it really slots into something that actually happened. It’s a boring, oh, he just tried a thing. It was just a kind of tongue in cheek phrase, and he just added a counter, and he just did a couple of iterations on it. And then I don’t think it’s in your post, but I think it was mentioned somewhere else that it was 20 plus years ago, and then there was an equipment rotation, and it was on one machine, and then just like that, equipment just got rotated out, and they just didn’t have access to it anymore, so oops.

Steve: From the spec side, there’s nothing special about these values. They’re supposed to be just arbitrary value. So, yeah, it’d be nice to have the record of, like, okay, why did you pick this seed? But it just says pick any value, and it’s kind of a flaw of the generation spec that it doesn’t say, like, we’ll pick it this way, like Star Wars zero and count upwards until you get a curve that works. I think the idea is that by following the directions, you’re never going to satisfy this argument.

Deirdre: Yeah. This is so funny though. It’s just sort of a guy just was just hashing random stuff because it didn’t matter, because the spec says it doesn’t really matter and just tried something and then the fact that it wasn’t fully documented got some people suspicious. 15 years later, 14 years later, it.

Steve: Does feel really sloppy and not what you’d expect the NSA to do. So I can’t really say whether this is realistic or not, but enough people have come out and said, yeah, I heard the same story, that I do believe it personally and what I’d like to do is find somebody who would just actually sign their name to that.

Thomas: Yeah, the argument has been made that we’re retconning this whole thing and the NSA didn’t turn evil until the early 2000s with dually C. But then the flip side of that is that it’s the other way around, right? Like the 90s NSA was deeply involved in the discourse back then was like clipper chip, right? It was like, all cryptography is going to be backdoored by the NSA by default, right. So this would be like the most obvious possible thing for them to be thinking about doing in the 90s would have been, oh, we’re going to have a curve standard. Okay, we’ll just backdoor it. Right? It will be good.

David: Also, we know that there’s two halves. Like there are literally two sides of NSA of information assurance just got renamed to cybersecurity or something of making things harder to hack. And then the side that’s like counterintelligence, that’s like decrypting communications.

Steve: Yeah, it’s a huge organization. There’s going to be multiple teams that are doing contradictory stuff. So I believe it just like organizational experiences, other places that, yeah, this could have happened, but we won’t know until we may never have.

Thomas: You have a little bit of a problem, right? So the idea that this is just the benign part of NSA that’s doing this the countervailing fact there is that Jerry Solinas was I mentioned at one point I wrote a blog post at one point where I called jerry Salanis like the Yolitengo of cryptography, just in the sense that not super popular with mainstream people, but everybody in the field.

Deirdre: Talks about is Yolo Tango a band?

Thomas: Oh, for fuck’s.

Deirdre: Fucking I reread your post and I was just like, oh, it’s a band. I didn’t know what it jerry.

Thomas: Jerry Solanis is also knee deep in the extended random controversy.

Deirdre: Oh.

Thomas: Refresh, I’m going to take a beat here and I’m just going to pull the room here. I’m going to go to each one of you in turn and I’m going to ask, do you personally think or take seriously or do you know any serious cryptographer who takes seriously the idea that the NIST curves might be backdoored. Deirdre, do you or know in the whole field, do you know anybody that you think in good faith thinks that the NIST curves are not backdoored?

Steve: I know people who think it’s backdoored, but not the people who I would kind of take their opinion seriously. So short answer is no.

Thomas: And then, David, I’m not sure what.

David: Voldemort’s opinion of the curves are, but other than that, no. I’m not aware of anyone that seriously thinks the NIST curves are backdoored.

Thomas: Okay. Same place here, right? So that’s the NIST curves. Right. But there’s also Dual EC, and all of us I don’t have to take a poll. We all agree that that’s a backdoor.

Deirdre: It was also so obvious that this is sort of like, this is slow. Why would you ever use this unless someone leaned on you? Because it would be good for, quote, national security to use the.

Thomas: Is.

David: I do think Dual EC is a backdoor, but to be fair, it’s over a curve. But there is a situation where you might actually want to use that approach to doing random number generation, and it’s because you’re actually just using it as an iterator with a smaller group. This is how ZMap generates IP addresses. It’s the same type of math that’s I over an elliptic curve, but it’s like we’re just going to create a group, and then we’re going to multiply a random number into the thing, and then it’ll go in a circle. So naturally, if you DELOG the first IP address that ZMap scans, you can predict the rest of the order. Some students did.

Thomas: Okay, so just summing that whole thing up. No. Moving on. So right after the Bull Run documents came out, that kind of fingered Duly, see? And really the smoking gun there was that major VPN vendors were using Bsafe, which is the RSA Bsafe library, and RSA B safe was using Duly C. Right. That was like the smoking gun. Right. Kind of contemporaneously.

There was this thing about like so you’ve backdoored the random number generator, which means that you can take the state, the output, the random bits that come out of the random number generator, and you can decrypt them. Right. They’re the product of a public key transform. So if you have the private key, you can just transform it back and get the internal state of the RNG and then unwind all future and previous keys from it. Right. That’s the attack. Right.

Deirdre: Yeah.

Thomas: But to do that, you need enough state on the wire to decrypt. Right. You need a full ciphertext. And one of your problems is that kind of natively by default, TLS is giving you enough state that you can do it. Right. But painfully, is what I remember.

Deirdre: Right.

Thomas: The details of this were like, you can break TLS with it, but you need a lot of compute to do it. Right.

Deirdre: But the adversary was not going after TLS, they were going after other things, like your VPN.

Thomas: But it’s like, wouldn’t it be nice if TLS just coughed up enough random.

Deirdre: Safety and pull out the keys, right? Yeah.

Thomas: And so kind of contemporaneously, there was a series of attempted standards in IETF that were all about getting TLS to cough up more random bits. It was called extended random. Right. And this is the thing where some part of the federal government had a requirement for their transport protocols where there’s X amount of randomness in the protocol or something like that, like some fig leaf of we need more randomness, so we should add an extension to TLS.

Deirdre: This is coming back to me.

Thomas: So, like, you add this extension, just kind of like the TLS hello extension that gave us heartbleed. Right. You add an extension, and when you see that extension, the client coughs up more random bits. And I’m like, the obvious problem there is, okay, you coughed up more random bits. You’re really feeding into this Dual EC thing. And the flip side of it is it’s possible that the US. Government is just so fucking stupid that they really do think they need more random bits than protocol, right? Yeah. Or they want to pull in random.

David: Bits from some hardware device and then mix it in with your pull some random bits out of a smart card or something.

Thomas: I wrote a whole blog post about it. I think the blog post that has made me most famous within NSA, but it’s not one of my best blog posts. Right. It really pissed some people off. For instance, I think it really pissed Trevor Peron off. Yeah. Because he’s been very good about spotting NSA influence and standards groups and all that. By the way, I buy the premise you don’t want NSA involved in your standards groups.

I go further and say you don’t want standards groups, but either way you don’t want an involved right. But, yeah, it really pissed people off to see the alternate arguments about why this might not be a conspiracy theory. But either way, Jerry Slinaus’name is on those things, right?

Deirdre: The extended random proposal.

Thomas: Yeah. So either you believe that there really was a requirement that the be more random bits, or this is some weird channel binding proposal where there’s like, you can put information here that’s derived from other key exchanges to link sessions or some stupid shit like that, or something to do with the smart cards they were using. I don’t know. Right. Either you believe that or Jerry Slinas was involved in trying to get Dual EC to work on TLS.

Deirdre: I don’t know.

Thomas: Yeah. How would you?

Deirdre: Yeah, no one does.

Thomas: Sorry, Trevor.

David: I don’t know. I mean, it could be, uh if Jerry Solinas was involved in it. He could just be their standards guy. Same way that Eric Roscoe is the standards. But I don’t remember if in the whole Juniper thing, if extended random was involved or not. I have a vague recollection of it.

Thomas: Being involved, but I feel like it was never standardized.

Deirdre: No. Yeah. So I think with Juniper it was all IPsec, right? And how Dulce got hooked into that and got popped up and they swapped out whatever, those points.

Thomas: They didn’t even notice. They didn’t notice for years.

Steve: They didn’t fucking why would you notice?

David: Right?

Deirdre: They didn’t notice.

Steve: They got influenced, landed the change in their repository, and I’ve never heard an explanation. It’s like, okay, well, what happened with that?

Deirdre: Just got built, whatever.

David: Maybe they didn’t even the conspiracy theory I’ve heard from that. Is that’s how the OPM breach happened?

Deirdre: Oh, yeah, I heard that.

Thomas: No, there’s no way. I don’t believe it. Right?

Deirdre: Really?

Thomas: Well, I mean, think about SolarWinds, right? Like, think about how easy it was to pop all that stuff anyways. Like, you would need a backdoor that stupid.

Deirdre: It might have been, we’re going to get a foothold in this and we don’t even know what we can use it for until they figured out what they could use it for. So it might have been that sort.

Thomas: Of thing, that’s cryptographers wanting to feel special.

Deirdre: No, I mean, maybe someone in the adversary’s org was just like, you know, we could just try this and see what we get in our big haul. And then they realized, oh, we got OPM. Nice. I don’t know.

Steve: I think there’s probably a lot of easier ways they got OPM, but maybe also I’m hearing the same rumor from you where I’m recalling from like, was it just you?

Deirdre: No, I’ve heard that in a completely.

Thomas: Different context, too, but yeah, I hope it’s true. I say send your comments and your concerns and questions to our one star podcast reviews. We will read them on the next episode and address them.

David: And if you’re a password hashing cracker type person, you should go read Filippo’s blog post about I believe about he’s.

Steve: Currently at twelve k $12,000.

Deirdre: Yeah.

David: To find these seeds. I don’t know if that’s like a lot or a little. I have no frame of reference for it.

Thomas: Like the real reward is your name. Yeah.

David: Points.

Thomas: It really is. It’s the maximum number of Internet.

Deirdre: Yeah, we’re linking to the bounty post in our show notes, but yeah, happy hunting. And if you spin up your hashcat or know, mining rig for greater good, let us know. I don’t know. We’ll see.

Thomas: Steve, before you had written this blog post and before you were working on this blog post, I had never heard the story that the seeds might literally just been Jerry Solanas Echo, give me a raise pipe into SHA-1.

Deirdre: I heard that it might have been from the Bernstein paper, or it might have been from the Menezi’s enigma wrapped in a riddle thing, but it is.

Thomas: For sure the funniest fucking thing I’ve ever heard.

Steve:

Thomas: It’s an awesome blog post. Everyone should read it. Lots of details. And then, yeah, somebody please find the seeds because it’ll be message board bragging rights for all fucking times.

Deirdre: Yes. And thanks for being kind of cryptographer journalist or something like that. This is cool. Thank you for tracking these people down and asking to get them on the record as much as you could. That’s pretty cool.

David: And for joining the Two Timers club exactly, two episodes after your first episode. So in three episodes, we’ll have you back for a third topic. I hope you found something else to investigate.

Deirdre: Yeah.

Steve: All right. We’ll find the next backdoor.

Deirdre: Cool. Thank you. Steve. Security Cryptography Whatever is a project from Deirdre Connolly, David Adrian and Thomas Tachak. Our editor is Nettie Smith. You can contact us on the Internet. We’re not really on Twitter anymore. If you would like merch, you can go to merch securitycryptographywater.com.

Deirdre: Thank you for listening.

Latest Posts

STIR/SHAKEN with Paul Grubbs and Josh Brown
57 min read

STIR/SHAKEN with Paul Grubbs and Josh Brown

SCW's Picture
SCW
Cryptography Tier List
21 min read

Cryptography Tier List

SCW's Picture
SCW