'Jerry Solinas deserves a raise' with Steve Weis

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.”

Transcript: https://securitycryptographywhatever.com/2023/10/12/the-nist-curves

Links:

- Steve’s post: https://saweis.net/posts/nist-curve-seed-origins.html
- ANSI X9.62 ECDSA: https://safecurves.cr.yp.to/grouper.ieee.org/groups/1363/private/x9-62-09-20-98.pdf / FIPS 186-2 https://csrc.nist.gov/files/pubs/fips/186-2/final/docs/fips186-2.pdf
- “A RIDDLE WRAPPED IN AN ENIGMA”: https://eprint.iacr.org/2015/1018.pdf
- https://arstechnica.com/information-technology/2015/01/nsa-official-support-of-backdoored-dual_ec_drbg-was-regrettable/
- https://www.muckrock.com/foi/united-states-of-america-10/origin-of-fips-186-4-elliptic-curves-over-prime-field-seed-parameters-national-institute-of-standards-and-technology-78756/
- https://www.muckrock.com/foi/united-states-of-america-10/origin-of-fips-186-4-elliptic-curves-over-prime-field-seed-parameters-national-security-agency-78755/
- Filippo’s bounty: https://words.filippo.io/dispatches/seeds-bounty/
- Recommendations for Discrete Logarithm-based Cryptography: Elliptic Curve Domain Parameters - NIST 800-186 with Curve25519 and friends
- RFC 8422: Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS) Versions 1.2 and Earlier
- https://www.rfc-editor.org/rfc/rfc4492#section-6
- https://blog.cryptographyengineering.com/2017/12/19/the-strange-story-of-extended-random/
- https://en.wikipedia.org/wiki/Bullrun_(decryption_program)
- https://en.wikipedia.org/wiki/BSAFE
- https://sockpuppet.org/blog/2015/08/04/is-extended-random-malicious/

"Security Cryptography Whatever" is hosted by Deirdre Connolly (@durumcrustulum), Thomas Ptacek (@tqbf), and David Adrian (@davidcadrian)

Transcript

Deirdre: 0:12

Hello, welcome to security, cryptography, whatever. I'm Deirdre.

David: 0:16

I'm David.

Thomas: 0:18

I'm whatever.

Deirdre: 0:20

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: 0:33

Good. How're you doing?

Deirdre: 0:34

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: 0:57

Yeah I'll jump in with a little bit of background. So as you all are aware, like whenever there's any sort of news article about the NSA involved with crypto, there's going to be a thread on it. And somebody is 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

Deirdre: 1:23

Oh.

Steve: 1:23

1997, 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.

Deirdre: 1:34

Mmhmm

Steve: 1:35

this document, which is linked online, had many different curves in there and many different, like, what they call examples. They're not even saying that these are like the standards. They use the word, like, these are example curves

Deirdre: 1:47

ha

Steve: 1:47

um, you know, there's a good number in there, maybe like, I don't know, I'm kind of counting off the top of my head here, like 20 of them, 15 of them

Deirdre: 1:54

Oh Uh

Steve: 1:54

types of curves. So, you know, things with prime order, things with like binary curves and, among those are two that ended up in a later spec by NIST, and this is like

Deirdre: 2:07

Mm

Steve: 2:08

that we all, refer to when they call these NIST curves. It's FIPS 186-2. This is around the year 2000, so this is a couple 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, that the idea is that you pick some constant and then you hash that with just, at the time, SHA1, and output of that hash and that defines what the rest of the curve parameters are, the point and other...

Deirdre: 2:48

the coefficients of the curve.

Steve: 2:50

yeah, so,

Thomas: 2:53

Can I jump Can I ask a question real Just real, so like, just, just cause 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, like high school math algebra equation,

Deirdre: 3:08

Mm hmm.

Thomas: 3:09

Or whatever, right? It's just like, you know. Y equals X three plus two AX. I don't Right. But like, um, so the curve itself is defined by the coefficients on like the right hand side of the equation. And then a base point,

Deirdre: 3:25

And the base field prime.

Thomas: 3:26

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

Steve: 3:58

That's correct, yeah. So I mean, for the prime, there's many curves in the field of that order prime, so, know, the idea is that there's a seed that defines these other coefficients and other parameters, point based points, and 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.

Deirdre: 4:19

Uh-huh. And they

Steve: 4:19

say, these are verifiably at random. And the idea is, when they're saying verifiably at random, they're saying that you're running through a hash function. They're basically saying that here's some value and it's going to be random because you ran it through SHA-1.

Deirdre: 4:30

Heh. Mm

Steve: 4:31

verifiably random curves. And it's not really, because, you know, you can imagine that you just sit there and pick the seeds until you get a curve that you...like, for whatever reason. there's, you're familiar with it, but, you know, 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.

Deirdre: 4:56

Mm hmm.

Steve: 4:57

Called 'Riddle Wrapped in an Enigma,' and they go through all of this of like, how this is generated, like why it would actually be hard to pick... you know, if they were able to do this, it would have implications on that these curves would be weak for other reasons.

Deirdre: 5:11

mmhmm

Steve: 5:12

that's actually probably a better paper just to read directly. I think today it's kind of more on all the rumors and things around this.

Thomas: 5:18

but this is like, this is, this is a big deal because, this is the, one of the oldest conspiracy theories in cryptography, right? Like so I, I have to like, I have to be careful here, right, because, I also, I have the misfortune of also having said that Dual EC was also probably a conspiracy theory. Um, not that anyone should ever use Dual EC, right, but like, it was so dumb looking that I kind of doubted that it was enemy action and just thought, like, 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 is an NSA conspiracy, I mean, you should weigh in 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, is 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: 6:12

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, like, you know, if you pick your parameters right, you know, yadda, yadda, yadda.

David: 6:43

To be fair, those, those were, like, they changed the parameters because they probably didn't have the original backdoor and they wanted,

Deirdre: 6:50

Oh, yeah, yeah, yeah, because, because,

David: 6:52

their own.

Deirdre: 6:53

the, the, the,

David: 6:54

backdoor generating machine that everyone knows is

Deirdre: 6:56

yeah, so someone, theoretically the NSA, backdoored Dual EC DRBG, and then someone else went in, broke in via, yes, and used the fact that the NSA had put a backdoor in for just them, to use it to, you know, determine randomness and break VPNs and all stuff

Steve: 7:18

for people listening too is that NSA, one of the things that came out is they had paid companies like I think RSA and somebody else like

Deirdre: 7:25

Mm hmm

Steve: 7:26

to support this random number generator.

Deirdre: 7:28

That's slow.

Steve: 7:29

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,

Deirdre: 7:41

Yep

Steve: 7:41

went in and used the curve as designed, and I never heard any resolution of that, I was like, who did it, was it, you know, China, was it, who, who did it, like, never heard about

Thomas: 7:53

like the 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

Deirdre: 8:02

Oh yeah, I think it's, I think it's even funnier because I think exactly the opposite of what you said, that like, this conspiracy theory may just have been silly and dumb and not, and not in, you know, disproven. But anyway, so.

David: 8:16

Yes. The, the difference here though being that like we know and we've known since forever that Dual EC has a backdoor, could have a backdoor of structure X, whereas we have no idea what that structure would be if, if the NIST curves were somehow backdoored with their parameters. Like we, we don't, we don't have the, oh, it would be this way.

Deirdre: 8:36

Mm hmm.

Steve: 8:37

Everyone I've talked to, you know, doesn't think there's actually a backdoor in these NIST curves, they think, you know, some people have different things about non rigidity and like, selection of the curves, but

Deirdre: 8:49

Yeah, well, yeah,

Steve: 8:51

my take is that I haven't, I haven't run into somebody who's like really convinced by it, uh, other than on like, you know, internet forum threads.

Deirdre: 8:57

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

Steve: 9:11

Honestly, there was one of these threads a few weeks ago. I can't remember what it was, but the NSA was in a, in the news and it came up again. I was like, ah, I should pick this up again because I actually sent a Freedom of Information request NIST and NSA

Deirdre: 9:23

Mm-hmm

Steve: 9:23

five years ago. you know, their response was, we don't have any documentation about our own specs.

Deirdre: 9:30

Mm-hmm

Steve: 9:31

of this in our specs like looking at it now, and kind of digging more in 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 that you know, there's other NIST seeds in there that aren't in the ANSI spec. So, that was unsatisfying. The NSA one just went dead, like they replied once and no response after that. Um, I think this is largely because I don't know what I'm doing, and I, somebody who can write one of these, you know, knowing how to ask the questions could probably get further, because the way I phrased my questions were ways that they were like, can't actually answer. They were more like, you know, there's a way to ask these things, so. not a dead end to actually send a FOIA request to NSA, and somebody, I'll get to this later, but somebody pointed out that some of this stuff may automatically get declassified after a 25 year period, which it has been, so, um, there may be things there that would be publicly available. Anyway, uh, this kicks it off again, I start emailing a couple people, like, hey, did you ever hear about how these were generated? You know, along the way, like, I did get, you know, finally some definitive confirmation, like, Jerry Solinas was a NSA employee whose

Deirdre: 10:35

right

Steve: 10:35

floating around for years. And like, finally I got it in writing that like, yes, he is the person who handed the seeds to the ANSI X9.62 committee,

Deirdre: 10:45

right

Steve: 10:45

Alfred Menezes, and he was chairing the committee, so he— that's a clear answer, like these definitely came from the NSA, they definitely came from Jerry Solinas, we don't know if Jerry... generated them, um,

Deirdre: 10:57

Huh

Steve: 10:57

is like one, you know, discovery, I think it was well known, but like, okay, we, that, that's clear, um, unfortunately I think I mentioned that Dr. Solinas died, uh, earlier this year, so the best thing would have been to just ask him, you and turns out that like several people did ask him about 10 years ago.

Deirdre: 11:13

Uh huh

Steve: 11:15

the latest stuff came off is when the whole Edward Snowden thing dropped. A bunch of people

Deirdre: 11:18

Uhhuh

Steve: 11:19

asked him like, Hey, where'd you get these seeds? And so... probably, you know, this, this goes to the 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 story

Deirdre: 11:42

Uhhuh

Steve: 11:43

and We've now kind of gotten separate multiple people who've 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 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

Deirdre: 12:02

Uh,

Steve: 12:03

you know, I quoted them on the on the blog post. This also was in some comments by Dan Bernstein and Tanja Lange

Deirdre: 12:10

hmm

Steve: 12:11

submissions to NIST that they had heard the same story from NSA employees. Two NSA former employees reached out to me and reported, know, repeated the same anecdote and like they also don't want to be quoted, but I've heard it from four different people now.

Deirdre: 12:26

Okay.

Steve: 12:27

you know, the one or the two kind of clues that came up was like somebody said, Oh, there's actually two names in there.

Deirdre: 12:33

Oh.

Steve: 12:34

oh, by the way, the phrase was that, like,"Jerry deserves a raise." This is not the actual phrase, but, like, this, this was

Deirdre: 12:39

Some like that

Steve: 12:41

of somebody from 10 years ago. So,

Deirdre: 12:44

Yeah.

Steve: 12:45

and then somebody else was like, oh, no, there's actually another name in there, and a counter. So, that's all we have.

Deirdre: 12:50

Okay.

Steve: 12:51

So, you know, it's kind of interesting that, like, we've heard this from multiple people, and, like, what I would like to get out of this is somebody who was ANSI on the committee at the time, or at NSA, who could 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 their reputation on the line that, hey, he told me he did this, I was there, I'm credible, either you believe this or you don't, and, you know, that puts us in a place where it's not so much mystery around it.

Deirdre: 13:22

Yeah. And the idea is that, he had a phrase, Jerry like, either something like, Jerry deserves a raise, or like, me and my buddy deserve a raise. and then you, you know, whatever, ASCII encode that into bytes, and you shove it through, what, SHA 1? And then you, you, whatever, like, split the, the, the image of that in two, into, like, the A coefficient and the B coefficient. And that's, quote, generating a random curve when, when you've already picked a, 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: 14:09

Yeah,

Thomas: 14:09

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: 14:16

I think that's right.

Steve: 14:18

it could be, but it's suspicious, cause like, the seeds 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, like

Deirdre: 14:28

Ah ha ha. ha ha Okay

Steve: 14:31

could be anything, it could just be him rolling dice on his table too.

Thomas: 14:34

but but once we have the output of whatever that PRF was from there on we know we know that the curve is like defined— well, right like we don't wonder how they got from the the 160 bit value to the curve parameters. That's all documented, right? Yeah.

Steve: 14:49

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 like pre seed image

Deirdre: 14:57

Yes

Steve: 14:57

the spec and like there's a little bit of like confusion on my part about that but like 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, it just says, Pick literally any string and hash it, and then try to derive a curve from that. And, you know, some of Solinas's own RFCs he wrote said, This is the thing we did. We picked an arbitrary string, hashed it, and

Deirdre: 15:22

Ah ha

Steve: 15:23

that, and repeated it if it wasn't a valid curve.

Deirdre: 15:26

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

Thomas: 15:41

And it's like it's the only thing that hashes to 160 bits, right? Like it's weird and with the with the block size there, right? so

Steve: 15:48

Yeah, and so, this is a good aside too, is that in that same ANSI doc, there's a bunch of other seeds, and these pretty clearly do not come from NSA, because they have the name of Ming Hua, Ming Hua Chu in

Deirdre: 16:03

Huh

Steve: 16:04

cryptographer who was at Certicom at the time and he's uh, you know, one of the co authors on the MQV key agreement protocol.

Deirdre: 16:12

So

Steve: 16:12

the seeds actually have his name encoded in them in ASCII. And I thought this was weird too, because 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 them. You know, throws a little confusion there too, because like these are clearly not the output of a hash either. So like,

Deirdre: 16:31

huh

Steve: 16:31

basically a string with his name in it, and then hash that to generate the curve, but you know, those ones are not ones that you would go, find like a pre image of that

Deirdre: 16:41

Yeah. Yeah.

Steve: 16:42

I thought that was a weird one that these are like just co mingled in there and like some of those ended up in later specs, but, you know, and this has been known for a while. Like we just noticed it as we're like looking at these seeds is like, Hey, there's a bunch of like repeated bytes and 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, it undermines the conspiracy theory that like, okay, they went back and they, backdoor, just a couple seeds, but then there's a bunch that like clearly are not, you know, backdoored. It's the guy's name shifted back and forth.

Thomas: 17:11

Well,

Steve: 17:12

you know

David: 17:12

Classic misdirection!

Thomas: 17:14

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 up with any kind of backdoor just based on the name of the guy.

Deirdre: 17:28

Yeah Mmm.

Thomas: 17:28

Mmhmm. Which gonna be what people say when, like, if we ever uncover what the seed is, Cause it's, this is like a really basic, like, old exploit developer thing, like, if you're gonna, like, claim a zero day vulnerability on Twitter or something like that, right? Like, you, you make a hash prediction. And like, 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 I'm, this is very silly, right? Um, and, and also very egotistical. But when I post a hash, I'm always worried that some weirdo is going to try and like brute force the hash. So I always like include some random number, so it's like, whatever it was that I'm claiming, you're not going to be able to like dictionary it to find out what it is, right? So like the idea that it's a string, and then like a counter in there. And like, the counter, we think the counter is in there because if you just like say, Bob owes Jerry a raise. There's a decent chance that the SHA 1 of that is not going to be an acceptable set of curve parameters, right? you, you start with Bob owes Jerry a raise one, and then you iterate until you find one that's... valid.

Deirdre: 18:25

Yeah, I'm looking at the appendix right now. Um, that's 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 like, revisiting what we know about this, little period, this story and this little period of history, and now you've kind of like, 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, 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: 19:08

if it really is a string, if it really is just some variant of, you know, Name X owes Jerry a raise with a counter in it, right? Like, you're baiting password hashers, right? So like I've noticed on message boards, on Hacker News, really, I've noticed on Hacker News people like, Like, "what are you gonna do? You're gonna take the hash and find the preimage of the hash? You can't do that. That's the whole point of hash." So 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 like that, and then hash a string, like, it should be possible to just grind through every possible permutation, get chat gpt involved, I don't know what you're gonna do there to generate all the permutations, because I don't crack passwords, right? But other people... seem to derive enjoyment from this, and if you can crack that hash, if you can come up with a hash that maps out to the same seed, you kind of,

Steve: 20:11

You put this to bed.

Thomas: 20:13

Yeah, and it'd be like one of the biggest revelations in internet cryptography. And it'd be like, it'll be in textbooks.

Deirdre: 20:19

yeah.

Steve: 20:20

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 tried, like I don't think he was unleashing the full power of the NSA on this Um

Deirdre: 20:33

even just hashcat.

Steve: 20:35

yeah, so, but you know, it'll be interesting and we don't, we don't know how long the phrase is either. We don't know if there's, you know,

Deirdre: 20:42

Yeah.

Steve: 20:43

it may not just be like SHA 1, it could be whoever, or, you know,

Thomas: 20:47

Yeah, but if you can't get past that if you, if you can't work from that set of clues and figure out what this hash is, you are not a good password cracker. you're just not really, you're not really in the game. Right? So, like, somebody who's in the game is just gonna do it to prove their bona fides. 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 them. So like, I totally get where Jerry is coming from on this, right? Like, I, I, I lose most passwords, right? So that's totally a plausible thing that could have happened.

Steve: 21:20

So I'll put some teasers out there because there was a couple other leads that, you know, 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 10 years ago.

Deirdre: 21:35

right

Steve: 21:35

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. Um, the other one is, they gave me the name of the person who wrote the code that they

Deirdre: 21:46

Ah

Steve: 21:47

used to do this. I found him, he's not responded yet. uh, he was an NSA employee at the time and is now, uh, you know, working, um, in private industry. So that person is still apparently active, but did not respond in time for this

Deirdre: 22:03

how how is this not just, like, a shell script? I feel like it could just be, like, a fancy shell script to I mean, I guess if you're trying to, like, do elliptic curve math.

David: 22:14

script, like, uh, like You know just knowing like oh, was there a new line? Was there not a new line? Like, that might be helpful.

Steve: 22:22

but it's not just the seed pick. It's like, I think he wrote the code that actually did all the rest of the curve checking and all

Deirdre: 22:28

right Right

Steve: 22:29

x962 spec, which is not super complicated, but you know, it is big, big integer math.

Deirdre: 22:35

But you don't want to do it in Bash.

Steve: 22:37

Yeah, I don't think so.

Thomas: 22:40

I guess I have a couple of questions here, right? My first question is about cryptography. I'm trying to figure out what order I want to do this But like, the first question is about cryptography, right? there's a subtext on the NIST P curves. I'm, I always say just the NIST P curves, which I 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,

Deirdre: 23:01

P256 and ilk. Yep.

Thomas: 23:03

So when we're cryptographers, when certain cryptographers, when a specific cryptographer is talking about difference between the NIST curves and the provenance of the NIST curves versus alternatives, the subtext is really the P curves versus curve25519.

Deirdre: 23:19

Or, or other, of its kind of cohort,

Thomas: 23:23

Right

Steve: 23:24

no other, there's no other real contender. I mean, let's, those are the two horses in the race.

Thomas: 23:29

There's 4, 4, 8. If you're not worried about rambus patent, You know, trolling attempts to use 448 to take the internet.

Deirdre: 23:35

It's too big. No one

Thomas: 23:36

it's... Okay that's also internet conspiracy theory. But like, the subtext, the subtext is... You know, 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 single, it would be the zeroth, funniest fucking thing history of the internet, if there was some weird backdoor in curve25519, you, you heard it here first, but what,

David: 24:08

It's actually a supply chain attack in 25519. you download, uh, the software distribution for testing

Deirdre: 24:14

ha ha ha.

David: 24:15

it, it, installs, uh, what is it, QDNS or whatever on your

Deirdre: 24:18

Oh god!

David: 24:19

just off.

Thomas: 24:21

okay. So like one nice thing about it is that we're, we don't really wonder so much how they came up with the parameter, how the parameters for 25519 were chosen. There, but there are other nice things about 25519,

Deirdre: 24:31

that's because they made a big, like, show of like, quote, nothing up my sleeve about these things that the creators of 25519 and the kind of that cohort of curves said are good things to have when you're picking curve parameters. And like, yeah, and basically

Thomas: 24:48

remember there was like a 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, And there was this big argument about, like, nothing up my sleeves numbers curves versus 25519, like, the 25519, again, I'm probably wrong about this, and cryptographers, or certain cryptographers, or a specific cryptographer, is probably gonna tweet or something that I'm completely wrong about this, I accept that off the bat. But my understanding of that.

David: 25:24

like really delayed and in three months

Thomas: 25:26

understanding, my understanding of that whole, that whole drama was that the nothing up my sleeves number thing is not the right approach. the 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. 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 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, you know, use that to come up with. And like, 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 It was like, they didn't backdoor a curve, because that would take real energy, but like, they came up with a curve that started out with a string, or certain strings, or a specific string. And that, like, by being able to take pi and coming up with that string in the curve, you'd prove it. So like, this is a total aside, by

Deirdre: 26:51

That's

Thomas: 26:51

but like there's this notion of like, 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 like, 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, The biggest thing for me in 25519 is you don't need point validation, right? So this is like a hugething 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 Weierstrass curves, I can't pronounce that word,

Deirdre: 27:26

Yeah

Thomas: 27:26

with the normal curves, when you get a point... A point is just a pair of numbers. It's exactly what you think of as a Cartesian, But, like, 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, right? And if you accept blindly a point from somebody else that is not on the curve and you do the math... You know, with your key, based on that, and give a response back, you will leak some of your key. That's actually, like, I'm, I'm drastically simplifying it, but like, if you know Chinese Remainder Theorem, like, it's a, 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 curve25519 key, which is a great property that is not a property of, um, the, of the P curves. But the other, the other big bit of nice engineering about 25519 is that it has complete addition formulas. Now, is a name that I'm dropping without having a complete understanding of what the fuck I'm talking about,

Deirdre: 28:29

It's literally like you can add any, 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 Weierstrass 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, you know, like, 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, whereas

Thomas: 28:58

of those, each of those cases is an if statement, right? You just for the,

Deirdre: 29:01

yep, yep, and so for, with Montgomery, curve25519, it's just, there is one formula for doing the group operation for any of the points on the curve, including the identity, and that's, it's just one, instead of four things you have to get right in doing all these You know, if statements, there is just one operation you have to get right. And that was very nice to, that, that was the first one to bring that to the table for elliptic curves.

David: 29:26

To be fair, we have since found complete formulas the NIST curves

Deirdre: 29:30

In the past five, six years.

David: 29:33

like, convert them to the Montgomery, effectively convert it to, like, a Montgomery style

Deirdre: 29:38

they? Oh,

David: 29:39

I thought that,

Deirdre: 29:40

if they do,

David: 29:41

thinking about it, that is,

Deirdre: 29:42

I mean, you can do that.

David: 29:44

to that style, mathing it, and transforming be mistaken.

Deirdre: 29:47

that, but I don't remember if that's, yeah, maybe it does. Uh, but we, yeah, we do have complete formulas for the short Weierstrass curves. Let's say that includes the P curves and they are basically fast enough now. So you don't just sacrifice, uh, speed for niceness, I guess. You, you basically close the gap between getting the same speed for the same, for better formulas with short Weierstrass. But it took 16, 15 years from when the PE curves were standardized to get there. So.

Thomas: 30:20

So like the, the question is the, the longest question I've ever asked. Right? the, the, the question is like, if the subtext of, of this whole NIST backdoor thing, at least when certain cryptographers talk about it, right? If the subtext is we should be using 2 5 5 1 9 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? 9 is an advance. Is that true? Is that, do we still think that's case? If, if we vindicate the provenance of the seeds for the P curves, should we go back to using the P curves?

Deirdre: 30:49

Well.

David: 30:51

I mean there's no point in changing TLS, ever at point

Steve: 30:56

think it's just like we use the stuff that's standardized and is widely available and so curve25519 is like generally my preference, but you know, says 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, feel just because it got standardized earlier and it's the only game in town, like. We're stuck with p256 for indefinite. There are standardization efforts for 25519, I noticed that, and I don't know the state of it right now,

Deirdre: 31:25

me either. I haven't heard much I mean, it's standardized for IETF and, uh, I know NIST stuff has been pointing over there. I think there's something standardized in NIST so that you can point to that if you're doing NIST stuff.

Thomas: 31:40

This is kind of a big deal, right, because of WireGuard, right? WireGuard is the best VPN protocol in the world, and like, one of the things that makes VPN protocol in the world is doesn't do neg Yeah. no cho no choices, No negotiation. And the the kind of the crypto stack that it picks is essentially... The curve25519 stack, if to call it that, right? like, and, and like 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

Deirdre: 32:14

Oh, I forget. Yeah,

Steve: 32:15

to look in the specs and see if it's actually been

Deirdre: 32:17

Yeah

Steve: 32:17

like proposed about four years ago and navigating this website as we speak. But, yeah, today I don't think there's any FIPS,

Deirdre: 32:26

Okay.

Steve: 32:27

support for

Deirdre: 32:28

Uh, yeah. I haven't heard about FIPS support, but I will say that beyond just sort of like we've standardized these things and like now we include them in regs, like things like FIPS and they're deployed everywhere. One thing that when we adopted these, uh, Montgomery curves, so curve25519 is the Montgomery curve model. And then if you're, doing it for signatures, you turn it into the Edwards curve model, which is ed25519. You got those complete formulas, and you got these niceties about implementing them in constant time, 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 short Weierstrass curves, which were completely prime order, A. K. A. 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 co-factor 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 curve25519 or an Edwards25519. or different, uh, Montgomery or Edwards curve, and then didn't check to make sure that they either eliminated the small cofactor points, or other, you know, weirdness like that. 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... You know, uh, prime order ones in and the, uh, cofactor points in or are they out or, you know, 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, you know, all that sort of stuff. But then we come back to the, to the NIST curves. So the, 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 co-factor issues and they're already standardized. So I think we may like have a renaissance.

David: 35:14

they're prime order, or are they prime power?

Deirdre: 35:16

I think they're prime order, I think I think P256 is prime order. Yeah.

Thomas: 35:21

so like, I think, cryptohipsters are all kind of aware of the cofactor argument about right? And like, part of this is just me checking my intuition, my intuition for the attack here is, because of the cofactor on 25519, for any given signature, And, you know, under a signing system, if you're not careful about this, there are N other identical signed thingies. And there, 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 and...

David: 35:59

Yes there's as many signatures as there is cofactor

Deirdre: 36:03

And the verification algorithm matters. If you multiply by the cofactor or not, it changes whether or not your signature is considered valid or not. And the specification for ED25519's signature scheme said, You can, but you don't have to. Do whatever. It's fine.

Thomas: 36:23

And I know like, there was a vulnerability in certificate transparency about this, right? Like, early, yeah, in an early, in an early version, like a draft of CT or whatever, there was some nit about like, but you can see kind of like in a, in a,

David: 36:36

still exists now, that you can submit the same certificate, like, cofactor times, and any...

Deirdre: 36:43

Oh, shit.

David: 36:44

in the ECDSA case, you might be able to, like, make it negative, don't remember.

Deirdre: 36:48

I didn't know this.

David: 36:49

So you submit, like, certificates more than once, which could be a vulnerability, could not be a vulnerability Like, it doesn't really have any impact on security, it's just a dick way to, like, 8x the load of a CT log. There's much easier ways to do that, like querying it.

Thomas: 37:04

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

Deirdre: 37:25

I would argue... Oh, yeah, there was.

David: 37:29

what chain it was, or why, where, but it definitely happened.

Deirdre: 37:33

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

Thomas: 38:07

but like, okay, So, like, even with complete addition formulas, and even with the cofactor, and these are originally UCDSA curves, so maybe the cofactor thing matters a lot, right? But, like, 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: 38:22

I think that's true,

Thomas: 38:23

And that's cheap. It's not, it's not expensive. You can just do it. Like, crypto library should just do it. But if you forget to... And you're doing a key exchange, you could be very sorely fucked, For, I mean, it's one of the few crypto exploits I've, I've done.

David: 38:38

on your addition your algorithm but

Thomas: 38:41

So like, so I guess there's like, there's arguments on either side.

Deirdre: 38:44

Sure. It's all pluses and minuses. Like you, you, 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 prime ordered short Weierstrass curves, and, but you do have to validate points and things like that. Like it's pluses and minuses all around.

Thomas: 39:03

So this is like my other question about this, which is less about crypto, like about computer

David: 39:08

still don't know what your first question was to be

Thomas: 39:10

and it's, it's, it's.

David: 39:11

We're gonna have a second bounty, the 12k for Thomas to ask a concise question

Thomas: 39:15

Yeah, it's, we're not really, I mean, yes, we're never gonna get there, but like, the first question is, say we solve this, say we find the seed we, everyone believes the curve is benign, should we still use 25519 for all new designs, or should we take seriously the idea of using the P curves again, right

Deirdre: 39:30

think we should take seriously because p256 is the most popular curve in the world besides the Bitcoin curve, and I don't have head to head numbers, and you know. The Bitcoin curve is SECP256K1, but P256 is the most popular curve on the internet. So, you know, uh, certificates, TLS, handshakes, all of that is like 70 plus percent negotiated with the P256 curve. I think it would be, in my opinion, I think all of the reasons why the curve25519 and the Montgomery 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 Weierstrass 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 P256. 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 yadda yadda yadda.

David: 40:39

Does, can P246 do key exchange or is it just signing? I

Deirdre: 40:43

Oh yeah, I think so. Uh, let's look at

David: 40:47

Like, I've never seen a Diffie Hellman using P256, and TLS only uses it for signing.

Deirdre: 40:52

I mean, you can Like, I don't know if anyone does, but I'm, like, you absolutely can do that. Uh...

David: 40:59

TLS does X25519 a lot of the time for, um, key exchange P256 to sign it.'cause the web, k, I doesn't believe in d in, in 2, 5, 5, 1 9, crypto for no part, particular reason other than there's not a big reason to change

Thomas: 41:20

and like, in, in the web PKI, the argument for the P curves is very strong, right? Because that's, like, the invalid curve attack is not a signing attack, the cofactor attack is the signing attack.

Deirdre: 41:29

Yeah. Let's see. Uh huh. Yeah. Although there have been, I don't remember them, but I do remember that there was a ECDH issue involving cofactors. But yeah, the, the things that seem to bite people the most is like, People can't agree on what a valid signature is and, like, different things will come up as valid, which is not good.

David: 41:49

I, I think the actual answer to this question is like whether or not someone finds the, the seed for the hash for the seed, um, to the p256 curves. You should not use that information at all in deciding which elliptic curve to use. Like, this entire episode, or any, uh, all of Steve's posts, none of that should change your opinion Yeah

Steve: 42:13

be right on the internet. That's

David: 42:14

Yeah, Yeah. This is about the XKCD comic, of someone is on the internet. Not about what curve to

Deirdre: 42:20

use. Oh, yeah, yeah, yeah. Yeah.

Thomas: 42:22

My second question is much more in that vein, right? It's almost just a grudge settling thing, right, which is, so like, it's definitely the case that some of the drama about the p curves and the back doors 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 Solinas just asked for a raise with these curve seeds, 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 pie is backdoored?

Steve: 42:59

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 Solinas was still alive where we could just say, look, you accept this as the 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, like, fine, that's a fine outcome for me. I don't need to find the seeds. I'm kind of okay if somebody just tells the story, cause right now the annoying part is that nobody will answer the question of like, well, how did these get generated?

Deirdre: 43:34

Yeah

Steve: 43:34

if it's a dumb reason that like, yeah, we just lost them.

Deirdre: 43:37

Yeah.

Steve: 43:38

I believe it. Other people won't, other people will not believe that. It's fine too.

Deirdre: 43:42

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, you know, kind of tongue in cheek phrase, and he just added a counter, and he just, you know, 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 like, it was 20 plus years ago, and then like, 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, like, just,

Steve: 44:24

And also the spec side, there's nothing special about these values. They're supposed to be just arbitrary values. So like. it'd be nice to have the record of like, okay, well, why did you pick this seed? But it just says pick any value.

Deirdre: 44:36

Yeah.

Steve: 44:37

it's kind of a flaw of the generation, you know, spec that know, it doesn't say like, we'll pick it this way, like start with zero and count upwards until you get a curve that works. Like, the idea is that by following the directions, like you're never going to satisfy, satisfy this argument.

Deirdre: 44:57

Yep. 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 like, the fact that it wasn't fully documented got some people suspicious 15 years later, 14 years later.

Steve: 45:20

It does feel really sloppy and like not what you'd expect the NSA to do. So I can't really like say whether this is, you know, realistic or not, but people have come out and said, yeah, I heard the same story

Deirdre: 45:33

Yeah

Steve: 45:34

it like personally. And what I'd like to do is find somebody who would just.

Thomas: 45:37

Yeah

Steve: 45:38

actually sign their name to that.

Deirdre: 45:39

Yeah,

Thomas: 45:40

I mean, the argument has been made that, like, you know, we're really, we're kind of, we're retconning this whole thing, and like, the NSA didn't turn evil until, you know, the early 2000s with Dual EC. But then the flip side of that is that, like, it's the other way around, right? Like, the 90s NSA was deeply involved in— like, the discourse back then was, like, Clipper chip, right? It was, like, uh, all cryptography is going to be backdoored by the NSA by default, right? So like, 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 gonna have a curve standard? Okay, we'll just backdoor it, right? It will be good. I got,

David: 46:15

we know that there's two halves, like there are literally two sides of the NSA, of NSA, of like, information assurance just got renamed to like, cybersecurity or of like, making things harder to hack, the side, that's like, counterintelligence, like, decrypting communications,

Deirdre: 46:30

mm hmm mm hmm

Steve: 46:30

a huge organization. It's like,

Deirdre: 46:32

yeah,

David: 46:33

yeah

Steve: 46:34

teams that are doing contradictory stuff.

Deirdre: 46:36

mm hmm,

Steve: 46:37

So I, I believe it just like organizational experiences, other places that, yeah, this could have happened, but you know, we won't know until we may never know.

Thomas: 46:45

See, you have, you have a little bit of a problem there, right? So like, the, the idea that like 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 Solinas like the Yo La Tengo of cryptography just, just in the sense that like, not super popular with mainstream people, but like everybody in the field

Deirdre: 47:06

Oh, is YOLO Tango a band?

Thomas: 47:08

Oh, for fuck's sake, listen to

Deirdre: 47:11

I fucking re I re read your post, and I was just like, Oh, it's a band. I didn't know what it was. I'm sorry

Thomas: 47:19

And, so Jerry Solinas is also knee deep in the extended random controversy.

Deirdre: 47:24

Oh, really? Oh,

Thomas: 47:25

like, I'm gonna here, I'm gonna take a beat here, and I'm just gonna poll... 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 anybody?

Deirdre: 47:46

No. Not re No. Like, I

Thomas: 47:49

in the whole field, do you know anybody that you think, in good faith, thinks that the NIST curves are backdoored?

Steve: 47:56

I know people who think it's backdoor, but not the people who I would kind of like take their, their opinion seriously.

Deirdre: 48:03

Mm hmm

Steve: 48:04

short answer is no.

Thomas: 48:05

And a David.

David: 48:06

Um, I'm not sure what Voldemort's opinion of the curves are, but other than no, I'm not aware of anyone that seriously thinks the NIST curves are backdoored?

Thomas: 48:15

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 to take a poll we all agree that that's a backdoor,

Deirdre: 48:24

It was, it was so, it was also so obvious that this is sort of like, this is slow, why would you ever use this unless, like, someone, like, leaned on you because it would be good for, quote, national security to use the thing. Oh, no.

David: 48:41

so, there is I do think Dual eC is a backdoor, to be fair, it's over a curve, but like, there is a situation where you might actually want to use, like, 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 Um

Deirdre: 49:03

IP addresses, not...

David: 49:05

an elliptic like, we're just gonna create a group and then we're gonna multiply a random number into the thing and then it'll go in a circle, and so naturally, if you can, if you like, dlog the first IP address that ZMap scans, you can predict the rest of the order but like

Deirdre: 49:19

But...

Thomas: 49:19

okay, so

David: 49:20

did, but

Deirdre: 49:21

Oh, shit.

Thomas: 49:23

okay so just summing that whole thing up. No. Moving on.

Deirdre: 49:27

Ha ha ha ha ha ha...

Thomas: 49:29

so like, right after the BULLRUN documents came out, that like kind of fingered Dual EC, and like, the smoking gun there was that, like, major VPN, you know, vendors were using Bsafe, which is the RSA Bsafe library, and RSA Bsafe was using dual EC, right? That was smoking gun. 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, like, you can decrypt them, right? They're the product of a public key transform. So if you have the private key, you can just... You know, uh, you know, transform it back and get the internal state of the RNG and then, like, unwind all future and previous keys from it, right? That's the, the attack, right? But to do that, you need enough state on the wire to decrypt, right? You need a full ciphertext to, and so, like, and one of your problems is that, like, kind of natively, by default, TLS is, it's giving you enough state that you can do it, right? But painfully is what I remember, of this were like, you could, you can break TLS with it. But like, you need a lot of compute to do it. right.

Deirdre: 50:32

But the adversary was not going after TLS. They were going after other things. Like your

Thomas: 50:38

it's like, but it's like, wouldn't it be nice if TLS just coughed up enough random state that

Deirdre: 50:42

Oh, yeah, yeah, yeah.

Thomas: 50:45

and so kind of contemporaneously, there was a series of attempted standards in IETF. They were all about getting TLS to cough up more random bits. It was called extended random, right And this is the thing where, like, 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. add an extension to TLS

Deirdre: 51:14

This is coming back to me now,

Thomas: 51:16

yeah, yeah, yeah. like you, you add this extension, just kind of like the TLS hello extension that gave us Heartbleed, right? You, you add an extension and when you see that extension, the client coughs up more random bits, 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 U S government is just so fucking stupid that they really do think they need more random bits in the protocol. Right? So there's.

David: 51:42

they wanna pull in like, random bits from some like, hardware device and then mix it in with

Deirdre: 51:47

yeah.

David: 51:48

like, pull some bits out of a smart card or something

Thomas: 51:51

I wrote a whole blog post about it. It's, 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, it really pissed Trevor Perrin off, I wrote this. Yeah, cause, I mean, he's actually, he's been very good about spotting NSA influence in standards groups and all that, and I, 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 NSA involved, right? So, like, 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 Solinas name is on those things, right? like

Deirdre: 52:30

random proposal?

Thomas: 52:31

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 in here that's derived from other key exchanges to link sessions or some stupid shit like that or do with the smart cards they were using, I don't know, right? Either you believe that or Jerry Solinas was involved in trying to get Dual EC to work on TLS.

Deirdre: 52:53

Mm I... I don't know.

Thomas: 52:59

Yeah, why would you? No one does! Sorry, Trevor. I

David: 53:03

don't know. I mean, it could be both, right, though. Like, uh, if Jerry Solinas was involved in it, he could just be their standards guy, same like, Eric Rescola is the standards guy.

Deirdre: 53:13

Yeah, I don't

David: 53:14

remember if in the whole Juniper thing, if Extended Random was involved or

Deirdre: 53:18

I don't think so.

Thomas: 53:21

it was never standardized.

Deirdre: 53:23

No, yeah, so I think it With Juniper, it was all IPSec, right? And how Dual EC got hooked into that and got and got popped out. And they swapped out the the whatever.

Thomas: 53:35

They didn't even, they didn't notice. They notice for, for years.

Deirdre: 53:40

fucking notice. didn't notice they got infiltrated

Steve: 53:44

change in their, their repository. like, I've never heard an explanation. It's like, okay, well. What happened with that?

Deirdre: 53:50

Yep, yep, and it just, you know, just got built, or whatever, maybe they didn't

David: 53:54

conspiracy theory I've heard from that is that's how the OPM breach happened.

Deirdre: 53:58

Oh, yeah, yeah, I heard that yeah,

Thomas: 53:59

there's no, there's no way. I don't believe it.

Deirdre: 54:03

Really?

Thomas: 54:04

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

Deirdre: 54:15

It might, it might have been, we're gonna, you know, 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 of thing.

Thomas: 54:25

That's cryptographers wanting to feel special.

Deirdre: 54:28

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

Steve: 54:45

I think there's probably a lot easier ways to look at OPM, but maybe also I'm hearing the same rumor from you. Like, I where, where

Deirdre: 54:52

We just keep

Steve: 54:52

it just you?

Deirdre: 54:53

no, I, I've heard that in a completely different context too, but yeah

Thomas: 54:58

I, I hope it's, I hope it's true. I say, send your comments and your concerns and questions to our one star podcast reviews And we we will, we will read them on the next episode and address them.

David: 55:10

And if you're a password hashing cracker type person, um, uh, you should go read Filippo's blog post about, I believe he's currently at 12k ish

Steve: 55:19

000 bucks.

David: 55:21

to find these seeds. I don't know if that's like a lot or a little, like I have no frame of reference for like,

Thomas: 55:27

The real reward is, your name will yeah, it is, it really is, it really is, it's the maximum number of internet

Deirdre: 55:34

Yeah. Yeah. Um, we're linking to the, the bounty posts in our show notes, but yeah, uh, happy hunting. And, uh, if you spin it, if you spin up your, your hashcat or your, you know, mining rig for greater good, let us know. I don't know.

Thomas: 55:52

Steve 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 Solinas, echo, give me a raise, pipe into, SHA-1

Deirdre: 56:04

I heard that! And it might been from the Bernstein paper, or it might have been from the Menezes Enigma Wrapped in a Riddle thing, but...

Thomas: 56:12

is, it is for sure the funniest fucking thing I've ever heard. It's an awesome blog post. Everyone should read it. Lots details. And then, yeah, somebody please find the seeds, because it'll be message board bragging rights for all fucking time, so.

Deirdre: 56:25

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

David: 56:39

And for joining the two timers club. Have exactly 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

Steve: 56:50

All right, well, we'll find the next backdoor.

Deirdre: 56:53

Cool. Thank you, Steve. Uh, Security Cryptography Whatever is a project from Deirdre Connolly, David Adrian, and Thomas Ptacek. Uh, our editor is Nettie Smith. Uh, you can contact us on the internet. We're not really on Twitter anymore. Uh, if you would like merch, you can go to merch dot securitycryptographywhatever dot com. Thank you for listening.