Security Cryptography Whatever
Security Cryptography Whatever
PAKEs, oPRFs, algebra with George Tankersley
Use Left/Right to seek, Home/End to jump to start or end. Hold shift to jump forward or backward.
A conversation that started with PAKEs (password-authenticated key exchanges) and touched on some cool math things: PRFs, finite fields, elliptic curve groups, anonymity protocols, hashing to curve groups, prime order groups, and more.
With special guest, George Tankersley!
Transcript:
https://securitycryptographywhatever.com/2021/10/26/pakes-oprfs-algebra-with-george-tankersley/
Links:
- SRP deprecation: https://blog.cryptographyengineering.com/should-you-use-srp
- OPAQUE: https://www.ietf.org/id/draft-irtf-cfrg-opaque-06.html
- obfs: https://github.com/shadowsocks/simple-obfs
- Elligator: https://elligator.cr.yp.to
- Hash to Curve: https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-12.html
- Magic Wormhole: https://github.com/magic-wormhole/magic-wormhole
- Biscuits: https://github.com/CleverCloud/biscuit
- Ristretto: https://ristretto.group
- Monero signature bug: https://www.getmonero.org/ru/2017/05/17/disclosure-of-a-major-bug-in-cryptonote-based-currencies.html
- SIDH smooth-order supersingular curves: https://link.springer.com/chapter/10.1007/978-3-662-53018-4_21
"Security Cryptography Whatever" is hosted by Deirdre Connolly (@durumcrustulum), Thomas Ptacek (@tqbf), and David Adrian (@dadrian)
Phonetically, correct. The best kind of correct.
Deirdrehello. Welcome to security, cryptography, whatever. I'm Deirdre, I'm here with David. How are you doing David?
DavidI'm doing great. I've organized my drinking for the rest of the evening. So after this is over, it's smooth sailing.
Deirdreexcellent, wonderful achievement for your day. I'm very proud of you. Thomas. How are you doing today?
ThomasHere.
Deirdrehere? Also special guest George Tankersley. How are you doing George?
GeorgeHi, I'm doing, I'm doing great. This was very short notice
DeirdreThis was very short notice and we short- notice- got george to hop on the pod with us today because we were spit balling about what we wanted to talk about and include things like, uh, deprecating SRP: secure, remote password agreement. Is that what that stands for?
Thomasyes.
DeirdreYeah. And in terms of deprecating SRP in favor of a modern PAKE: password agreement key exchange, something like that, George knows a lot about the things that we need for those sort of protocols. So it's like, let's just oblivious, pseudorandom functions and other things that have to do with anonymity credentials that George has worked on. So we just ping George and asked if he could help on a call with us.
ThomasThe other thing that happened was we decided we were going to do a news Roundup because we have to do something and apparently no news has transpired.
DeirdreI mean, there's been a few, uh, iOS zero day kernel vulnerabilities that got patched. But you know, we we've talked about that several
Davidtimes, done three episodes about that at this point.
Deirdrethere's a, there's an apple patch day. There is a zero day exploit at one of their platforms due to memory unsafety. The sky is blue. Water's wet.
ThomasWe should do an episode this time about things we're somewhat qualified to talk about.
Deirdrelike PAKEs?
ThomasSounds good to
Georgeme! Somewhat qualified: checks out.
Thomasa couple of days ago on the front page of the orange site, which is the source of all the topics for this podcast, um, I think a Matt green article on password authenticated, key exchanges, um, just charted at the top of the site and a week earlier, friend of the podcast, uh, Steve Thomas had posted, um, I'm stopping myself here because it's occurring to me that he I'm sure he's Steve Thomas. It's been one of those weeks where I've forgotten everyone's name. His first name's definitely Steve. it's Thomas I'm right about this. Um, Steve had written an article
Davidno, you're Thomas
ThomasUm, yes, that's true. Uh, Steve had written an article about, um, why you should never use SRP anymore. And SRP is like the most popular password authenticated key exchange. So like a password authenticated key exchange is like, um, you think of a cryptographic protocol, where you're initiating the protocol and setting up session keys, um, like with TLS based on certificates, right? well, TLS uses certificates to set up those you know, those keys. So you do a, a Diffie-Hellman with two made-up keys on either side of the connection, but you can't trust those keys because a man in the middle could also just make up two sets of keys for either side of the connection, then proxy. and you'd never know it just straight up Diffie-Hellman whether or not you were talking to the real person you thought you were or whether your, you know, your key was the man in the middle's key. So certificates are one way of solving that; triple Diffie Hellman with a long-term static is a way of solving that problem. And then like, right. For a lot of reasons, um, kind of like an instruction that gets a lot of attention is password authenticated, key exchange, where again, we do like something resembling Diffie-Hellman, but to like break the tie between whether we're talking to a man in the middle, or whether we're talking to the real person, we think we're talking to, we use our password, right? So you could think of a password authenticated key exchange as like I'm going to do Diffie-Hellman. But my, you know, my, my secret or the Diffie-Hellman protocol or some part of it is dependent on my password and the exchange will only complete if both sides agree on what the password is, that's roughly what a PAKE is. Right? And then again, like SRP is this like protocol from the 1990s, which was the first popular password authenticated key exchange. Part of that is because a lot of the good password— like a lot of the good, simple PAKEs were patented for a long, long time. none of that matters anymore. All those patents have expired. but for a long time, SRP was the one you could and Steve wrote a post about, SRP. So. Things to talk about here. Um, we could go through a little bit of the logic that Steve uses. I think it's interesting to point out that people shouldn't use SRP. if only because on that orange site thread, about PAKEs, uh, more than one person suggested that they were considering implementing SRP, and listen to Steve, there's no good reason ever to do that anymore. also just, um, I, I get the attraction of password authenticated key exchanges. I get why people like them. I think part of the reason that people like them is because you can get your head around what they're doing and they seem clever and that's kind of a insidious combination, you've got something that's clever and that you can understand, uh, you'll latch onto it because a lot of things that are clever and hard to understand, you don't like you understand them. And so you don't talk about them that but PAKEs everyone kind of gets
DeirdreLike textbook RSA. It seems easy. And.
GeorgeYeah
Davidfirst question
GeorgeAnd
Daviddon't Diffie Hellman and and then AES-encrypt password on both sides. And the answer is because that's trivially man-in-the-middle'able. is that, that's what I'm hearing so this is
ThomasYes, right. You can do other things, right. You can have an enrollment secret. Like when you set up your device, um, your device can register itself with a long-term static key. And then you can do Diffie-Hellman, you know, or triple Diffie-Hellman with that static you know, and not have to use a, uh, you know, a password or anything else to break the tie because you have another long-term key, to do that. That's, a lot of what you see— when you see people talking about the Noise protocol framework.,Um, that's really what they're trying to do, right. Is, uh, you know, I want to set up a session based on a long-term cryptographic secret that I have, and also have some kind of forward secrecy. So I'm not just dependent on that one key, um, that's Noise, right? That's the idea behind, behind Noise. but Yeah. if you just did Diffie-Hellman did the encryption and then set your password, um, any man-in-the-middle could snarf your password
DavidAnd so we're kind of assuming that we've somehow pre shared a password, but not pre shared a long static key of some form.
ThomasWhich makes sense. It fits people's mental model of how you, like: I sign up for a service. I enter my password. In that one exchange, the server has my raw password. Like anytime I set myself up, you know, and that's not generally true of PAKEs, but like, in your normal like security modeling, you know, when you're thinking about the service, like you register with a password and set it up that one time, and then from that point on the server has something that it can use to verify that, you know, you're using the same password as you've always been using.
DeirdreGeorge, what were you gonna say?
GeorgeI was just going to say, this is all in a category of stuff that, uh, Filippo and I once called crypto 1.5, uh, in, in a talk it's, it's the things that, PAKEs, blind signatures, stuff like that, that that's been around for a long time. Uh, and that everybody looks at and thinks like, oh, I, I understand what's going on here. That's cool. It's just like half a step beyond something I'm familiar with from TLS. where can I possibly use this cool new crypto thing? and you know, that kind of remains an open question, but it's very attractive to play with.
Deirdreespecially when they were originally written up, usually based around either finite field or factoring assumptions or things with RSA, and then you revisit them kind of like the work you've done with, you could just do this now with elliptic curve groups and make it faster and smaller and actually deployable.
ThomasWhich gets to a problem with SRP is because, the formulas for SRP— SRP is a simple protocol, but it was designed, in the 1990s and the formulas for SRP use the Diffie-Hellman group that it's working on. So
DeirdrePure— pure diffie-Hellman not, group
Thomasby the way, I I'm going to poll the group. here. Cause I have this problem every time I write about this What is the term that you use to describe kind of classical, simple multiplicative group Diffie-Hellman? for Finite
DeirdreDiffie-Hellman. That's what I
Thomassay. So we just call it FFA.
DeirdreYup.
Davidhe held. Or just D H if you've already started using ECDH somewhere else.
ThomasOkay. So like, just to be clear for people who don't follow the math here like your kind of your textbook RSA, or you're like your crypto tutorial or your applied cryptography description of RSA, or Diffie-Hellman where you just generate a prime number and then, you know, like raise numbers to a power modulo that prime, that's finite field Diffie-Helman. And we have that distinguisher because it's much more common today to not use, finite field Diffie-Hellman and instead, use elliptic curve which is like incompatible, but at the same ideas. Right? but you're using a different mathematical group and it's, you know, your keys are much shorter and the algorithm is much stronger. So when we talk about
Deirdrewas not a distinguish. There was no need to distinguish between Diffie-Hellman and anything else, because the original was just over a field of integers. And then when elliptic curves came along and it's like, no, this is a elliptic curve group that we're using to do Diffie-Hellman, then you had to start distinguishing it from the old one. And so that's kind of where the finite field Diffie-Hellman came from.
ThomasOkay. And if I'm trying to piece this together, axiomatically in my head like, so why is FFDH like, why is finite field the good description here? Like, can I not use that term to describe what I'm doing with elliptic curves?
Deirdreno, you cannot. Because if you're using a field of integers, you have more than one operation over the algebra algebraic structure. You have a multiplicative operation and an additive operation. With elliptic curve groups, you only have the additive operation And basically it boils down to, why're elliptic curve groups considered a more secure primitive to build stuff on than just the scalars or whatever? It's because there's strictly less algebraic structure of the elliptic curve group to exploit, buy an attacker. So therefore you're able to make your key sizes smaller. and this is sort of the basis of where, why the attacks are slightly different and why the strength of elliptic curve groups is basically better because they're strictly less stuff mathematically, algebraically you can do with the elliptic curve group, as opposed to the field of integers between like zero and a prime.
ThomasGotcha.
Davidto have divide or just inverse?
DeirdreThat's the inverse operation of multiplicative operation.
DavidOkay. And rings, just
GeorgeYeah, I think,
Davidand multiplies
Georgehave inversion.
DavidThis is math 512 at the university of Michigan. We're happy to teach abstract algebra here today. My name is Robert Lazersfell. Three people find this joke hilarious.
ThomasWe're sticking with this though, right? Cause I'm, I'm going to get this nailed down and be good for the rest of my life, right. So like it goes, groups are the simplest thing, right. And groups just have, you know, with finite fields, it's just the are with a classic multiplicative group, diffie-Hellman whatever, it's just the multiply operation. Right. And then one step above groups is rings. Right. It's not field next is ring next. Right. And then one step
Deirdrebecause it's, it's over a different closure, uh, for the operations between additive and multiplicative. And I think fields are the ones that it's like, both of those operations are over the full closure, and rings are not. And I forget which one of them, it's not
DavidRings can have zero divisors, which is why everything breaks, because you can multiply non-zero numbers together in a ring and get zero. So it's like numbers mod a !Prime, for example, like the numbers mod six, if you multiply three and two together, you'd get zero. That would it a ring instead of a field.
ThomasThis is great. great. Now I know now I know abstract algebra on
Davidhaving zero divisors and having an inverse for everything are like mutually incompatible. so it's one of those if, and only if things, so that's how you tell if something's a ring or a field.
Thomasokay. So like one of your, one of your problems with SRP as a nineties protocol was that it was written, with, you know, kind finite field integer arithmetic, and it haphazardly uses both the multiply operation and the add operation in its formulas. which means it's only usable. Those formulas are only usable for kind of classic finite field, you know, integer, whatever whatever's, because elliptic curves can't do the addition trick that, uh, that th that they need in the
DeirdreAnd that's not to confused with scalar multiplication because scalar multiplication over an elliptic curve group is just the additive operation of adding points together, scalar number of times. So, yeah.
ThomasWhich, just to bring this all back to earth, is you can't instantiate SRP directly over an elliptic curve. Um, so that that's one big problem that people have with it. It's not like, uh, it's hard to argue on a message board that that's a deal breaker. Cause it's like arguing, no one should use RSA anymore. It's true. But it's not like clearly, obviously true. the other big problem that people bring up with SRP is that it leaks information in the protocol when you run it. So, um, you're, you're using passwords and you're, uh, you're effectively creating a hash of the password. It's not a hash, it's a verifier but you're creating an artifact that verifies the password from the password. And that needs to be randomized, otherwise you could just pre-compute them all and have a dictionary them, you know, kind of immediately attack anything. So I hate the term salt, but the verifiers in, Uh, an SRP are salted.
Deirdrereally a nonce, it's a salt.
ThomasI use nonce, but when, when this comes up, When you talk about salts, then people invent new kinds of salts and they want to put salts all over the place. And like, I'll say randomized, this is randomized. It's not salted. It's randomized.
DeirdreHimalayan
DavidYeah, Thomas, when should I use kosher salt versus granulated salt
Georgeis, pepper permissible.
Daviddon't, I'm going to credit, uh, my partner with this, but like, why is pepper on the same level as salt, like pepper flavors, things, and salt is a mineral. It helps you cook stuff. Pepper's, just a spice that like has a high opinion of itself.
Deirdreyou have a low flavor palate, salt is also a spice. It does give a flavor.
DavidIf you grew up in the Midwest salt counts as a spice.
ThomasAnd usually when you see pepper tossed around, it's a secret salt, like there's the normal salt. And then there's the secret salt, the black salt, But pepper is, um, and like that's what they call it as they call it a pepper. And it's a stupid idea. And you shouldn't have secret salts for your password hashes. Anyways, SRP has these and, uh, the protocol when it runs leaks the salt. So before you've proven that you have a password, before you've established a key, an attacker who's querying, a server can get the salt for a particular user, which sorta kind of.
Deirdreand yeah.
Thomasyeah. it kind of defeats the purpose of salting.. it's, it might be the case that you almost might as well, not salt, I guess at that point. Cause the, the, the point of the salt is not just that you have to like, you know, um, compute lots of different things is that you have to compute every possible salt the verifier to pre-compute. But if you can get the dictionary of everyone's salts, then you've drastically reduced the amount of computation pre computation you have to do. So it's you know, it's an incremental step instead of, you know, huge multiplicative, exponential step amount of extra computation. So people don't like SRP, SRP sucks. Steve would also point out that, uh, there's ways of implementing SRP that are, There are bugs in SRP implementations that are really common, that leak the verifier directly. Um, so you could run the protocol with a state machine, like out of step a little bit and get the verifier, which is like compromising a password hash for a like, if you could talk to a web web application and get somebody's password hash from it, and they just crack that offline. That's a mistake that happens all the time. I'll point out also that for SRP, another really common mistake is just getting the math wrong. Um, one fun thing about all these, um, finite field, you know, public key things is, you can, there, there often bugs that will zero out the computation. So like you can provide a parameter in the protocol, that's either zero or, you know, kind of more insidiously, the prime itself or a multiple of the prime, which will work out to zero because everything's mod prime. Right. And if you don't check for that, the computation zeroes out and you can predict the result because it's zero, right. Um, Really bad for Diffie-Hellman and you've seen vulnerabilities and like VPNs and stuff like that for, you know, TLS srf, IPSEC or something where like it's possible to zero out, you know, the Diffie-Hellman computation. It doesn't matter, I guess that much because you know, both sides trust each other in those protocols. And so, okay. It's like one side is opting out of security for their connection, but that's all they're really doing. Right. And it's bad, but it's not like the end of the world. In SRP, it's the end of the world. Right. Because if you can zero out the computation, it doesn't matter if you need, if you know the password or not. Um, so you can bypass password authentication. anyways, there's lots of bugs with SRP. People don't like it. And Steve kind of proposes a bunch of alternative PAKEs that have come out of patents, but have kind of the same vintage as SRP, but they're sanely designed and simple protocols that curves fit into. And there are, there are a couple of different knobs on these things. Like there are different kinds of PAKEs. There are balanced PAKEs and augmented PAKEs, and there are also PAKEs that use OPRFs and PAKEs that don't use OPRFs. And here I fall off the cliff of my knowledge, I read the Wikipedia page on what an OPRF is, but, George, you actually know what you're talking about here. So, uh, tell me, you know, explain.
Georgeuh, I think the, you know, I live, I live in a very concrete OPRF world. but I, so I could talk to you about specific protocols, but I think in general, you can, describe an OPRF as a way of, calculating a keyed hash over an input, where the, uh, person holding the key does not learn the message that they're hashing and the, um, person who receives the output does not learn the key. so it's, you, you see— w with OPRFs you see a lot of these services where there's like, some, you know, flow where the user, like blinds a message and then submits it to a server who for in various ways, and for various reasons, will emit, a random out— a deterministic random output, uh, that can then be like unblinded and used. Uh, and this, this, uh, this turns out to have like a really surprising number of uses in the world.
DeirdreLike Privacy Pass?
GeorgeLike Privacy Pass. Uh, you can do it for anonymous credentials. You can do it. Uh, you can do private set intersection like this. You can do, all kinds of like password hardening type stuff.
Thomasso like a PRF is just a keyed hash. So like HMAC-SHA256 is roughly a PRF. Right.
DeirdreA PRF is more general than that, but that is one you can instantiate.
ThomasOkay. And
Georgeit's it's any, any pseudorandom functions. So like most cryptographic hashes, qualifies for this as well. Whether they're keyed or not.
DeirdreThe key part is the oblivious part in this context?
ThomasThat's the 'O', right? But PRF part of it is just: I take a hash, a hash by itself is not a PRF, but a construction that hashes a key into it, or a secret into it turns that hash into a PRF. Right?
DeirdreYou can use a quote unquote, regular cryptographic hash as, slot it in as your pseudo random function, depending on what you're trying to model and your security model for your protocol.
ThomasCause they're like, they're like, parameterized over a key. When I look at a PRF, the notation, it will be like PRF_x or something like that, where X is the secret. There has to be some secret and followed. Right? I could just be totally wrong here by the
GeorgeI
DavidI think it depends on your proof. Like, if for some reason you can say the, like the adversary already doesn't know what your input to this hash is. You don't really need there to be a key, like you could just feed data into it. And I think that as a PRF, for any hash that you could use to make an like it's, it's pretty much always an HMAC, because you need to keep something secret.
Thomasso like this whole time, I've just like, I've been, I've just been like mentally substituting when I read papers, like PRF. Oh. That's like HMAC, whatever, or, you know,
Deirdrebut not necessarily. for example, in Zcash, there's like a whole bunch of PRF's all over the place and they're, they're all different instantiations of BLAKE, but it's literally just sort of like domain separator, I am using. This is for my key gen', like stick a domain separator byte string at the front, and then put in everything else that you're hashing as your pre-image and then spit out the image. And that is your use of that specific instantiation of that hash function as your PRF for this particular case. And literally all it is, is just like adding a byte string at the beginning of your pre-image to do domain separation and that counts.
ThomasYeah. domain separators, by the way, are, are fun cryptographic shibboleths. So you make it look like, you know what you're talking about really sprinkling them all over the like a bad cryptographic protocol won't have domain separator strings, but like look at Wireguard's sometime, or Noise, and you'll see that like part of the protocol, like the version of the protocol or the particular algorithms you're using or whatever are passed in as strings as input. And they're literally part of the protocol as domain separation. The idea being like you don't want to bug where like an output from one part of the protocol gets leaked or spit out somewhere and it can be reused in some totally separate part of the protocol. And like we've seen crypto bugs that are like that and you can break all those bugs just by every time I use, you know, HMAC. Okay. It's not HMAC, it's HMAC_{this string}, just means that string's hashed into it now, like a special version of the family of HMACs here.
Georgethat, that kind of like, sort of cross session or cross protocol, uh, usage comes up in OPRFs a lot, because of the blinding. And so you find, um, you find yourself either shoving your policy into key management or motivating a desire for a partially oblivious PRF, uh, which lets you have a domain separator.
Deirdrecool.
ThomasSo like in my, in my mental model and it's not complete because I know nothing about OPRFs, right. Except for what you've already said, but it's like, imagine I had a web service that could HMAC things for against some key or whatever, actually that's dumb because you can already imagine that service. But like imagine some algorithm where like, I'm the caller into the algorithm and I have some message I want to HMAC. but I don't have the key and I want to produce the output without the key, and the OPRF allows somebody else to, you know, they contribute the key. I contribute the message, but neither of us get the other person's thingy.
GeorgeYep.
ThomasHow does that work.
GeorgeWith algebra.
DavidMoon math.
ThomasGo on.
Georgeno, it's not moon math at all. It's Diffie-Hellman your ingredients here are, um, basically Diffie-Hellman and, and some kind of hash to group. you take, you take your input, you hash it to the group. Uh, you generate a large, random exponent or scalar, you blind your hashed, uh, message, using that. You send it off to the server who essentially You could say that they sign it with their key or they, you know, do their part of the Diffie-Hellman or whatever. and, basically they, they multiply by their secret scalar as well, that they send that back to you and you multiply by the inverse of your blinding factor. And there you go. You've got, you've got an obliviously evaluated, uh, PRF.
DeirdreSo this strictly relies on the commutativity of these operations.
Georgeit. is the same, the same as Diffie Hellman. In fact, the main OPRF that gets deployed is called 2-hash DH.
Davidwell, it also relies on the existence of an inverse, which regular Diffie-Hellman does not rely on
DeirdreRight. There's no inversion in classic diffie-Hellman either, either over a finite field or elliptic curve. Um, in this case, you're, you're dividing out, your value, which does work. Er, you just don't see it in regular Diffie-Hellman.
Thomasthe blinding thing here is just like, I come up with a random value before I, as the person with the message, I come up with a random value and kind of multiply that in beforehand, which obscures my actual message from the other person. They can't get it because it has been obscured by this blinding, random value that I put in. And the algebra here is just when I get their result back, I just divide my, my random value out of it. Again. Am I right about that? You have a weird face on it. It could just be totally wrong.
DeirdreI think you got
ThomasGeorge's afraid to tell me that I'm wrong.
GeorgeNo, that's, uh, uh, that's. That's exactly it.
DeirdreSo hash to group, when you deployed Privacy Pass, was that hash to p256?
ThomasRemind me, remind me Privacy Pass.
GeorgeDeirdre, what is Privacy Pass?
DeirdrePrivacy Pass is a way for you to, it's basically a way for you to solve, CAPTCHAs and get around these like, if you're, if you ever saw a site hosted by CloudFlare and you were trying to access it over Tor and they're like, we don't know who you are because you're, you know, your IP address is indistinguishable from anyone else who's used this IP address from a Tor exit gateway. we want to do, do something that's like solving a CAPTCHA, but still preserves your anonymity because you want to be able to like, change your IP address or whatever. Um, but still assert that you are someone who has solved the CAPTCHA before privately or with anonymity. and Privacy Pass was, initially, I think a browser extension that worked with CloudFlare, terminators or edge edge locations, uh, that let you do this using, uh, anonymous credentials so that you were able to solve a CloudFlare CAPTCHA, get a set of anonymous credentials out of it, and then no matter how you accessed CloudFlare again from either the same Tor exit gateway or any other, you would just hand them an anonymous credential and say, no, no, no, I'm, I am not a bot. I am not a spammer. Um, I'm good to go, but it, it did not link anything about you or your IP address or the thing that you solved, just that you had solved it, and you have an anonymous credential to attest to that fact. Is that right? George.
GeorgeYes. so the, the thing that Privacy Pass adds on top of this, OPR F uh, evaluation flow that I've just described is that, uh, later when you hit a uh, an edge service that wants to, uh, that would otherwise give you a CAPTCHA. Instead, you can reveal one of your, uh, hash-to-group pre-images, along with the, uh, like signed point. And then the server can say, okay, if I take that pre-image I hash it. And I sign it myself with my key that I know, but you don't, uh, if it matches, then it's valid. And in practice, what we actually do is, uh, use that element to key an HMAC, that, that MACs the request.
DeirdreGot it.
GeorgeThat's privacy pass.
DeirdreDid that ever get standardized? I think there was a draft.
Georgethere is an awful lot of IETF activity that came out of, privacy pass. There's the VOPRF draft. There's a privacy pass working group. There's, uh, you know, portions of... hash to curve and Ristretto, were arguably motivated by like the needs of privacy pass and related protocols. so, you know, is it standardized? Like no. Um, but
Deirdreand a leg in, and an eye are all independently getting standardized.
Georgebut, uh, but you know, not for, not for lack of effort, just wheels of CFRG grind slowly.
Davidunless like standardization is like your dream and your thing, this is the ideal way to interact with the IETF, where you do something. And then other people deal with standardizing what you already did. Well, you move on to other things.
Deirdredid that use hashing to p256 or what, I forget,
Georgeso none of that existed at the time, um, in any way, other than in that original, like, Briar or Tibocci paper or wherever it is, you know, the simplified SWU stuff. Um, so, I think it's actually rejection sampling. I think we, I think we just like hashed something repeatedly until we got valid X coordinate. Yeah. Hash and pray.
Deirdrecool. Hey, if it works, uh, you know, it's not the most elegant in terms of a construction or a proof, but if it works to, to make this thing work with general security, it's a win.
Thomaslike, we're
GeorgeIt's fully deterministic, just inelegant statistically might fail.
Deirdreright. Yeah.
Thomaslike for where we're at, we're in heavy math territory here right now. Right? So like for people that are not read into this, like, I know what hash-to-curve is but i'll pretend not to what's, what's the big deal with hashing to a curve?
DeirdreAh,
DavidThat's a question George.
Georgethis?
Deirdreto can, I can, help because we're using in several things, but if you want to go George
Georgeyeah. So, um, you know, when you think of, uh, like a normal cryptographic hash function, the output of that is just random bytes, right? The, the idea usually is to, uh, is actually to project, whatever your input is into this like uniformly distributed space of, of bytes in a way that's difficult to predict and difficult to reverse. Um, and you, you ideally want there to be no structure whatsoever. you,
DeirdreI
Georgendistinguishable from
ThomasAnd, like any like sequence of random bytes is also a number, right? Like it's, you know, if I need it as a number, somewhere else in like a protocol that raises things to powers or whatever, they're all just numbers. Like, they're all fine numbers.
Georgewell, but they all be fine but they might not all be fine numbers, is where hashing to curve comes into it. if instead of big random integers that might or might not mean anything, you actually want like valid coordinates, for a point on your specific elliptic curve, then you have to do something different. That's that's broadly hashing to curve and there are different ways of doing it. And they're different based. They they're actually the part of elliptic curve math that actually uses algebraic geometry. like the, the fact that you're talking about an elliptic curve and not just like a fast way to implement a group begins to matter because you're hashing to the actual curve.
Deirdreso for example, hash and pray is trying to use the, I guess, the numeric style and try to just guess, try, and hope and cross your fingers. That it turns into a valid point on the elliptic curve group that you're trying to use. So you literally will hash something. Turn that into a value that can be the X coordinate of a point on this elliptic curve group, and hope that that X coordinate when plugged into the elliptic curve equation gives you a valid point with a Y coordinate. And it's the one in the group that you actually want to use. That's basically hash and pray. And if it doesn't work, you try and try again.
ThomasTry bumped the counter. Yeah. You'd look bumped the half second.
DeirdreYup. That's hash and pray.
GeorgeThe more correct name for it is, uh, try and increment.
DeirdreSo they just, I remember I heard hash and pray. I'm like, I know exactly what you're doing. Um, using a real hash to curve, uh, solution, yes, uses the algebraic properties of the group and uses things like isogeny maps from your input set, your, your pre-image set and using a actual map that uses the algebraic properties of the curve group and the structure that you're trying to image into, to make sure that you actually get as best as you can an uniform distribution over the set of points in your group. so that when you actually use this as a PRF in like your crypto protocol or your security proof, it is actually like not just sort of a wink and a nod, a, you know, 'pseudorandom function'. It is much, you know, it is an unbiased as much as possible pseudo random function, as opposed to hash and pray, which is definitely not.
ThomasFor Curve25519.
Davidsomething like one in four or one in a like 256-bit numbers would be like a valid curve25519 point. If I remember right
Deirdreoh, that's that has a co-factor though. There's there's the co-factors stuff and there's the hash-n...well I don't know,
GeorgeBut yeah, hash and a hash and pray actually has like a really dense chance of success. I don't know why the number 10 is— I think, I think it works out that we decided to just loop 10 and try it 10 times and like panic, if that didn't work, we expected it to work in two or three at most.
Deirdrefor privacy pass, did it, did the bias in the PRF for hash and pray matter at all for leakage or anything?
Georgeso, I think we were doing it via rejection sampling with like slightly wide number— or a slight, slightly wide hash outputs to, to— we did something along those lines to avoid it. But I don't, I don't actually remember.
DeirdreOkay. So there was a, basically a mitigation to try to handle
Georgebut yeah, you don't, you don't want to like take your hash output and then just like, you know, reduce it, mod whatever you, you do want to, um, try again, if it doesn't fall in the right range.
DeirdreOkay.
Thomasalso, and we'll edit this out if I'm wrong about this, but this is also Elligator, right.
GeorgeElligator is one of the algebraic hash to curves. Yeah.
Deirdreright.
GeorgeOr Elligator 2, the Mike Hamburg one
Thomasyeah. Usually when people are talking about Elligator, it's usually in a hash-to-curve setting.
DavidMy favorite part of Elligator is the logo, which is an Elligator eating elliptic curve points and shitting out random numbers
Deirdrethough. actually I think, I think Elligator goes both ways. It's both taking a curve point giving a canonical encoding and also taking, a, domain and have it canonical, uh, quote, hash encoding to the curve points. Uh, if I recall correctly
DavidYes, cause it's what they used in um, one of those, oh, God, Eric's gonna slap me cause I can't remember the name, but sent anti-censorship things that piggyback on top of a TLS connection. uh, does anyone remember the name of these things? I should know because I sat next to the person them
Georgeit's um, it's obfusproxy, right? Um, it's the, um, like obfs, from Tor, because previous the prior work to Elligator was Ian Goldberg's uniform DH. which was less good for reasons I don't recall. Um, but the, yeah, the idea was to encode it as a, uh, a uniform bitstream to stop deep packet inspection from killing your, uh, your bridge handshake.
Thomasbecause in theory, even though deep packet inspection, can't break the cryptography. It can still spot on the handshake, things that have, you know, P256 curve structure, right? Like they're all there. You know, you look at a number, it might or might not be a valid, you know, curve point. And so if your string isn't uniformly random, if it's encoded to be an actual curve point on a specific curve, then you can spot it on the wire, is the idea there. And then, like, that was like, when I read the Elligator, when I skimmed the Elligator paper a long time ago, that was like the motivation for it is, you know, you can spot curve points, you know, on the wire and traffic. but you can encode them with the Elligator map, uh, to be totally random. And I didn't care at all. Cause it's not like a interesting problem to me, but you know, in modern cryptography, I see Elligator, you know, invoked a lot for the opposite problem, which is, i ran a hash, I have a random value, but it needs to be in this curve protocol now. So how do I adapt it into protocol? that's the Elligator eating its shit and spitting back out curve points.
Deirdreyeah. And, and other, uh, other hash to curve solutions beyond Elligator, which are explicitly like the opposite of like, give me a point and turn it into random. It's like trying to take an input and the output, the domain, the co domain of that hashing is, uh, all of the elements are elliptic curve points, but the distribution of that domain of that codomain is uniform, so that you can slot that in and say it should, you should not be able to distinguish anything about. Anything about the pre-image by the bias of the possible samples of this output.
DavidYeah, they also use it. I was thinking of refraction networking or decoy routing, tap dance, and telex being the, the main examples of it, which is just another anticensorship thing where it relies on a middle box to find like a colluding website, that's willing to like help people get around censorship and then read something secret out of a TLS handshake with the benign site and redirect it to the block site. they use Elligator for that. but I don't know. Maybe we could actually talk about what the hell OPAQUE is now.
Deirdreyeah.
ThomasOkay. The first does anybody here know what OPAQUE is? Cause all I know is that it's a PAKE and that it involves OPRFs.
GeorgeI know a lot more about opaque than I did a few weeks ago.
Thomasgive us a, give us opaque versus other PAKEs.
Georgeokay. So there's, there's two angles on opaque. Um, one of which I, knew and caused me to discount it for years, uh, and one of which is like more, more relevant to my current interests. if you look at the libraries and like the, uh, IETF drafts about it is a, uh, a way of using password authentication, to generate secure session keys, right? It's, it's, um, a standard PAKE in that way. Uh, but it's also a, I believe they're called augmented PAKEs in that there is a server like helping you do that, that you're trying to, authenticate to. So the way that that works is you, you register with a server, uh, you give it a encrypted blob using a, uh, an OPRF-derived key from your password I believe, And that blob contains a private key for, your client identity. And then later, when you want to log in, you run this flow that, uh, executes the OPRF and gives you the OPRF result and that encrypted blob. And if your password was correct, you'll be able to derive the key to decrypt the blob. And then you run an additional round of authenticated key exchange to get a new, random, full strength session key with, uh, with your counterparty server. And then that allows you to, to like log into the website or whatever it is.
ThomasI understand. So like I was going to say like, um, so SRP is in theory an augmented PAKE and in my head, like I know the term and in my head it's always been that like augmented PAKEs are the ones where the server stores effectively a password hash and not the password itself. Right. Not enough information for the server to run the protocol itself with the password. So if you broke into a server running an augmented PAKE, you wouldn't get the passwords. Like you get the verifiers for the passwords. You'd have to do a brute force computation against them. That's my only understanding of what it means to be an augmented PAKE is that, if you steal all the information from the server, you don't get the passwords, you just get effectively the hashes or the thing you have to compute against to recover the hashes. And like a balanced PAKE is the one where both sides could run their protocol. They have the password. So if you broke into the server running a balanced PAKE, then you could dump all the passwords. Is that a crazy way to look at it?
GeorgeNo, that's a that's correct. And actually there's a, a portion of the like, IETF version of opaque, where the user gets a hardened key derived solely from their password that the server never sees. And that is what the new WhatsApp end-to-end backup system uses to encrypt the backups. The password is never seen by the server in a, in an opaque, execution.
Deirdreand that WhatsApp back up is, should be rolling out to iOS and Android devices. So you can end to end back up your, chat records on your Google drive or your iCloud. And it is independent of anything that the iCloud or Google drive does on their own.
Daviddo you need like a third party to run something like this correctly? Or just like a HSM, but you've thrown away the admin key for, or is none of that required at all? Or That's probably.
GeorgeI mean the, opaque spec leaves a lot as an exercise to the. Um, the deployer, uh, and like key management is certainly one of those things, WhatsApp seems to be using like fleets of HSMs, uh, in, uh, in blockchain world. we do or likely would, um, instead use, uh, like a threshold implementation of opaque.
DeirdreUm, Mmm.
Georgebut yeah, for opaque, because it is in that like augmented class, you do have this asymmetry between like, one party, who's expected to be like storing some state and to be online and responsive all the time. Uh, and like one party who is not, uh, whereas in a symmetric PAKE, like with magic wormhole, both people have to be online.
ThomasI think like apple also famously uses a PAKE in this exact same setting for iCloud keychain. So like the secrets that you have vouchsafed in iCloud key chain, they're unlocked with your phone pin. and so to prevent you from sending your pin through to apple, where they could just read the pin, um, and then recover your secrets, what they do instead is they store all your secrets or they store a key that, you know, I don't know what exactly it is, but like they store all your secrets effectively, chain to a fleet of HSMs. and then you speak S— that's the protocol that you use in icloud key chain effectively speaks SRP from your device, from your end point, which you control directly with their HSMs. so do you.
DeirdreI think, the pin on your device is combined with the, the burned in large key with the, whatever the secure module, the secure enclave or whatever of each device. So you, it's not just one or the other, you have to combine the two, but yeah, like they're, they're using that to unlock the things that they are storing on their fleet of HSMs and that was considered very good until China leaned on them to deploy very specific HSMs that are very specifically located in mainland China for, uh, Chinese apple users. So
ThomasThat's bad.
Deirdreit is bad.
Davidthat's why I only like American made HSMs, even though my many HSMs are actually Canadian, but, you know,
DeirdreIt's just, it's just like a box that takes a smart card or whatever.
Thomasalso, I think, I think we see PAKEs in like the new, uh, the new wifi protocol has a kind of controversial
GeorgeIsn't that a PAKE
DeirdreIs this dragon fly?
ThomasSo like you see PAKEs in settings like this, like if I'm, you know, setting up a set of a fleet of HSMs and running a custom protocol to do iCloud key chain, a PAKE kind of makes sense there, right? same with whatever WhatsApp is doing. Um, you know, same with like, you know, logging into a wireless network where I use a password to log into it because people can't remember AES keys off the top of their head. they like, they're fun to talk about. They make a lot less sense in other applications where like the much more sane thing to do is to have an enrollment key, like an actual genuine AES key or something that routes your, the security for your system, where, like, you don't really need to remember something off the top of your head, or if you do, you'll need to remember it locally to like decrypt the key. And then the protocol itself just runs with keys.
DeirdreI think the WhatsApp thing basically splits, splits the difference because they do let you use like a, I think it's like a 64 byte or 252, bit just byte string. You can have a very long password or basically equivalent, uh, aes key. they can help you generate one. And it's like basically to unlock the key that they store in their HSMs or something like that, they let you be like, I, I trust myself to generate a very long, high entropy key, and I am solely responsible for managing this key and, or, or the easier option for, if you want some real life, some backup reliability.
ThomasThis has been good. I feel like I sort of understand opaque now. and I definitely understand OPRFs. I thought OPR F's might involve polynomials, which is where my brain turns off in all cryptography. I've decided that do, I do all the cryptography that doesn't involve polynomials, which is why I don't do anything with GCM.
DeirdreI mean, technically elliptic polynomials
Thomasso so this OPRFs are now on the other side where I could conceivably think about understanding how they work, which is great. So this has been, this has been very good.
Georgethey're their crypto 1.5.
Deirdrethey don't involve pairings, like, like biscuits needs pairings, right? No pairings for this.
ThomasI think we're going to have Geoffroy Capris on to tell us that biscuits does not need pairings
DavidI don't think they ever actually need pairings to be but biscuits 2 was gonna get, I think, much simpler, but I think biscuits one does not have pairings. You'd think I would know because I deployed it in production the other day, but I didn't actually, uh, I was like, ah, I'm— Jonathan and Geoffroy are smart. I'm sure it's fine.
Thomasactually, you're actually using Biscuits?
DavidUh, we use biscuits in production for one use case where, we have some end points that are called by like a mobile devices. And then we have an admin panel where we can do things. And sometimes the read only versions of those end points. We don't want to duplicate the logic. That's like, show me all of the X for this user that would be shown to them in the app. So we have a credential system that could issue, credentials for a specific specific end points to an employee to then be able to make a call as if they were, a user to do something, like to make a GET request to a specific endpoint. And so we're able to encode the endpoint, the person that you are impersonating through the support panel, as well as the employee who is doing the impersonation, all gets put into the credential. And then that can be verified on the other side. So you can be like, 'no, you're not allowed to have impersonation credentials for actions that actually changed something'. Or, and then you get the audit logging of like, 'oh, Hey, like dadrian@name tag, did this and Ross@name tag did that'.
ThomasSo I'm like, I'm curious how pleasant they've been to work with.
Davidso they took a little bit to like get, once you figured out kinda how to write the verification. Um, they've actually been nice cause, we then extended them for one other use case where we needed to issue a blind credential to the mobile app that would then be used to authenticate the next call it would make. And like, I wasn't even online— like I was out the day that someone else did this and they were just like, oh, this is really easy. And like just added in the thing and made the verifier work. So that was good. But what was complicated was doing things like, getting the username that's in the token out of the token, for example, um, is a very silly looking function. It's just very silly. it's not like crazy or it's not like impossible to figure out. It's just very silly looking. Um, and so, and you kind of had to put some constraints on it to make it, constraints from like a programming perspective, not constraints from a biscuit perspective, um, to make it work, uh, in a way that wasn't like, 10 million lines of code every time you did it.
ThomasI have to ask you one other question about your biscuit implementation, which was how did you unit test them?
Davidoh, so we actually did, I did on the podcast say that you should always test the failure cases. so while we do have a verifier that like does specific things, one of the tests for it is actually kind of a duplication of some of that verify code and that we just called the biscuit verification directly. But what we we repeatedly call it and we provide like more information each time. And then we make sure that it fails until you get to the last time. So it doesn't check every possible, like combination of like, will this work or not, but it will do the basic things and be like, are all of these getting passed without the information? Do you, so we test that only the last verify when we've provided all of the data does in fact verify and the rest of don't. And then we have some well. but this is, this is really only used by like the support panel and not, the mobile apps themselves don't use it because they can't hold the, it uses Ristretto as the underlying credential. And that's not something you put in Apple's TSM or TPM,
DeirdreGeorge's, in victory.
DavidUh, we don't do that there. If we do start using them with a mobile app, what we'll end up doing is like signing nonces inside of the biscuits using like the ECDSA key on the app.
DeirdreCool
GeorgeWhat is a biscuit?
Davida biscuit is just a macaroon where the policy language is Datalog, and the crypto is, I don't remember what the crypto is, but they're not using HMAC. They're using asymmetric crypto.
DeirdreSee
Daviddon't know if that makes it easier if that answers your question.
GeorgeNo, not really, but this link probably will.
Thomasknow, what a macaroon is?
GeorgeYes I do.
ThomasSo biscuits are just the new macaroons.
GeorgeBut they need pairings
Davidthey don't actually use pairings. I don't
Thomasit's like, imagine that you wanted to do macaroons, but entirely with public key crypto so that you could you'd get the public key distribution story. But with macaroons, which are purely symmetric key, like biscuits are what they came up with to do a public key, like, first-class public key version of macaroons is sort of what it was. And like, they were trying to figure out what the right operator, cause it's, it's, it's easy to chain in HMAC and it's less straightforwardly obvious how to chain signatures is there doing signatures. Yeah. so it's less straightforward to chain signatures. so they were talking about, I think pairing curves as one solution for the actual concrete implementation of biscuits. And now it's just straight up signatures.
Davidand I think it will become even less moon mathy signatures in the next version. If I remember correctly, we should really get Geoffroy on here to explain this this
ThomasWe were asked to have takes on unit testing, but what might also work instead is just, you said Ristretto and we can just demystify crypto terms for the entire thing. So I'm imagining that there's lots of people here that would not naturally do the baby fist pumping motion
DeirdreOkay
Thomasterm, when they hear the word 'Ristretto'. So take it away.
DeirdreI like telling the whole story cause we've, we've come full circle. So in the beginning, um, when elliptic curves became a thing, not just in academic papers in 1985 by a guy named Koblitz and Miller and whatever, they standardized mostly prime order curves. Um, the most popular one I think in the world, is P256, a NIST standardized prime order curve, uh, over 256 bit field. This is the one that's used by almost every TLS ECDH, uh, handshake. Uh, if you ever see, um, ECDSA signature in the wild, it's probably P 2 56. And if it's not it's it's P 3 84. probably the second most popular curve in the world is probably now the Bitcoin curve, secp256k1, also a prime order curve, but it's a Koblitz curve. once upon a time, the best formulas that we had for doing, all of these operations on elliptic curve group elements were called incomplete formulas. that meant that like if you added two points together that were different points, you would use one branch and do a different set of math. If they were the same point, you would do another branch in a different set of math. And if one of them was the identity, you would have it yet another set of math. This made implementing elliptic curves, a little bit fragile. and the elliptic curves that we had were not super fast. Um, once upon a time, unless someone came along and said, Hey, there are some curves that are Montgomery and Edwards curves, and we have complete formulas for them. And they're faster. So look how fast they are. And the math is better. There's no corner cases or edge cases. Um, just, you know, make sure that you factor out this little co-factor, which might be, uh, points of order two, four or eight. And I think Thomas would be able to tell us about the whole class of attacks that he's able to leverage against small order points in your protocol. this is where the popularity of things like curve 2 5, 5 1 9, ed 2 5 5 1 9 signatures came from is from these extra fast, but, with better formulas, elliptic curves. The better formulas, however, came with co-factors. it's not nice when you have to slide a, you know, 'assume a prime order group' into your cryptographic protocol, and the prime order group is a subgroup of this elliptic curve group. And then you have another subgroup that's very small and you have to do all this kind of hand waving and juggling to make sure that you are in fact operating over the prime order group and not accidentally this, uh, non-prime subgroup that gives you very weak points, on your elliptic curve operation, or your group operation. So someone decided, uh, I think it was Mike Hamburg that came up with a technique called decaf, which basically takes these, cofactor curves like curve25519, um, and others, and turns them into a prime order group, always full-stop whatever, so that you can always map, points on curve25519, or ed25519 onto, uh, or you always have a canonical encoding. So you're never operating over the co-factor group. All the points will always operate in, all the group elements always operate over the prime order group. You get the speed wins, you get the complete formulas and you get the assurance that you are in fact, operating over a prime order group. So there's been kind of pressure in the, in the crypto fans of elliptic curve, community, I guess, to move towards this very nice construction so that if you want a fast, complete, prime order group in your cryptographic protocol, instead of using these co-factor curves users, use Ristretto. However, in 2016, someone published new elliptic curve formulas that are complete, for prime order curves, like short Weierstrass curves, like P 2 56. and they are very fast. So do we even need to use these co-factor curves anymore? Do we even need to use Ristretto anymore? When you can just do p256 with these new formulas that don't have all the branching that don't have all these edge cases and are pretty damn fast. And you just use that as your prime order curve and your prime order group. So we liked Ristretto, Ristretto was very nice. We may not even need it anymore. The End. George, anything
GeorgeI think, uh, 'do we even need it anymore?' Is, is a matter for the benchmarks,
Deirdresure. Oh, that's a good point. Yes.
Georgeuh, and the, you know, full on, uh, Henry deValence-implemented, uh, you know, Ristretto dalek Rust curve code is still pretty scary-fast yeah, you can also do parallel versions of the Edwards formulas, um, which I think are also only implemented in that library.
ThomasThis is like, um, this is relevant for signatures, right. And not for the Diffie-Hellman. So like, my question is like, okay, so we have complete formulas, like much better formulas for, uh, the P curves now or for P256 or whatever. For all the short Weierstrass. So like the question of whether we still need the co-factor curves, of which curve25519 is the most famous, Like the big motivator for me on curve 25519 is not having invalid curve points that you have to deal with in Diffie-Hellman protocols. Those are, those are scary vulnerabilities. It's where you run like an interactive protocol that does Diffie-Hellman with, uh, you know, with a curve. And if you can have invalid curve points, in your protocol, if I can inject that, uh, parameter as a client talking to a server or whatever, and then learn things about the underlying secret from them. Um, that's classically, like when we, when we look at vulnerabilities, those are called invalid curve point and 25519, doesn't have those vulnerabilities, the new formulas don't mitigate that problem, right. Or I'm, not following how they would.
DeirdreI'm doing a quick grep and I don't think it explicitly calls out mitigating that, I think you're correct. ristretto does basically ellide the entire, both, both invalid points because it's, you know, curve 25519, so that the underlying set that it is using doesn't have them, they are not defined, but also the entire subgroup of small order points is also just eliminated that that will never be representable, as a valid Ristretto group element. Um, but I think you're right. I don't think that the, the formulas... so it's interesting is that I feel like, I don't know, George might be able to help me out here, but like, the formulas are nice, but even so, yeah, I guess it's like one less thing you have to worry about with, at least curve 25519, is that you will never be able to get, an unrepresentable point, I guess with p256, you can? You
Davidcan, be giving you the guarantee that you don't have to deal with the invalid points because all the points are valid. It's just with 25519, and Diffie-Hellman all you have do is like mask off the first two bits or whatever. and then, solved.
ThomasBut you can't like you can't, you can't meaningfully attack those protocols,
Georgeif you have a ristretto group element, then you have a ristretto group element. There aren't any special classes of bad ones. you know, the point, you know, I, I talked earlier about like speed and that's fun and all, but the actual point of Ristretto is to present the abstraction that protocols expect. And, you know, this matters a little for Diffie-Hellman and signatures, but it actually matters a lot more when you start trying to do anything more complicated than that. So, you know, zero knowledge proofs or anonymous credentials, or, you know, even more complicated kinds of signatures, the little abstraction gap, starts magnifying the complexity of everything you do. But so the point being that, like you don't, you don't have to worry about most of these things if you're using Ristretto correctly, which the specs and the libraries go to some pains to help you do.
ThomasLike my, like my unfrozen, caveman lawyer, understanding of this, which I'm from everything you guys have said, I'm guessing I'm somewhat wrong about this, but I'm like that, like, it was like the Monero vulnerability is what I'm thinking about here, was preserving a one-to-one relationship between, um, documents as signatures, right? Like there isn't more than one possible signature and that the co-factor in 25519 or in ed25519. If you're not implementing carefully, it gives you the possibility of multiple valid representations for the same signature. and that having the pure Ristretto group or the simple prime order group or whatever means that you naturally won't have opportunities for that malleability. Um, you can't have, you know, I'm getting this wrong on some regard, but like, that was my, like my basic idea of what the motivator was for when people talk about Ristretto it's, 'I want to build complicated signature systems and make sure that like, you know, it's a one-to-one between the input and the signature'. So I'm guessing I'm wrong about that.
DeirdreI think you get that for free from Ristretto, but I think, maybe George can correct me, but I think the Monero one was what ZIP-215 solves. Was that, that?
GeorgeWhich one's ZIP-215?
DeirdreThe one that actually like, specific versions of lib sodium, like the ed 25519 ed, um,
GeorgeOh, the validation criteria thing.
DeirdreI don't recall,
GeorgeYeah.
Deirdrelike that,
Georgeit might have incidentally fixed that, like if we'd had that bug, but I, um, my memory of the problem with the Monero bug and this is not at all guaranteed to be correct either, but it was actually a, a mismatch between like the algebraic notion of the key of like the key and the signature that it produced and the like byte-wise encoding thereof. What they were doing was like to prevent double spends, they were like, hashing the key. you know, with like SHA2 or something, on the assumption that it would be like a, one-to-one like, this key produces these signatures, but fact, with the co-factor malleability, you can kind of like shuffle those around and you get like eight different potential representatives of the same, like class of valid key signature pairs. and like the, obviously those are all like concretely in terms of bytes, different points. So if you're, um, you know, if you're actually hashing them, you will end up with multiple different identifiers that can spend the same funds.
Deirdreyeah, I'm looking, I'm re-reading the Ristretto site and it's basically yes, that the fact that in, basically you use an isogeny map from the entire set of possible ed25519 points, you mod out the eight cofactor, the value, the order eight cofactor so that you have like eight points and they all map to a canonical encoding of a Ristretto group element. And so that you cannot have that sort of malleability attack, you cannot have more than one point that maps to, that is used in a signature because there is only one, there is only one valid element, and one valid representation of all of those eight points. So yes, I think to come back to Thomas, you are correct. This is one of the motivators for Ristretto
GeorgeMmhmm.
Deirdrebut now I'm extremely curious about whether the new formulas help at all with, the fact that you can define a point on an invalid curve for P 2 56... is curve25519 twist secure? Ed25519 is twist secure, right?
GeorgeYeah. Uh, I think, I think it is because, you know, in the kind of like original DJB spec, ladder formulas, you know, like as one might find on a mailing list, somewhere in, in undocumented Python, um, I think the point is that they just take the, u-coordinate and ignore— they don't care whether they're on the curve of the twist
Deirdreright. all the math is completely dependent on the X coordinate. It's actually, if you wittled down all the math you need to do, it is not actually directly dependent on the Y coordinate. So as long as you're just on the quote unquote Kummer line? The projection of this set on just the X coordinate line, it, it doesn't matter about, you know, the other possible values. It's kind of cool.
GeorgeWell, and, I'll, raise another point of order here about, uh, you know, in, in favor of the type of curve I happen to be most familiar with, the fields, uh, the, the like underlying base field of the, of the 2, 5, 5 curves is, you know, chosen to be kind of like convenient and straightforward to them. Right. You get the very cheap reductions and stuff like that. Whereas when I have looked at P256 implementations, which is like primarily the giant blob of assembly in Go, in order to make them fast, you have to do much more complicated stuff.
DeirdreOh, you're saying that the, the field for curve25519 is nicer. I missheard you
GeorgeSo, so like the, the new, um, you know, you have, you have these widely deployed, like short, Weierstrass curves, and you know, that's fine and we know how to make them fast and maybe we have complete formulas for them now. but is it is it still going to be something that you necessarily like want to use? Does it have the same engineering, trade-offs as one of the co-factor curves, who knows. Depends on your situation and like who you are and what you're doing.
DeirdreYeah.
Georgebecause if you're, you know, if you're working with a, a field shape such that literally, you know, like this guy named Vlad who writes really fast code, uh, is the only person in the world who knows how to implement your field. Well, that's not
DeirdreYeah. Why doesn't, why aren't there invalid curve attacks for curve 25519, as opposed to
Thomasthere aren't enough small subgroups in it. so like when you take a random, if you take a random value, and, uh, so I'm probably, again, I have a perfect track record this in this podcast of not of being wrong, about being wrong about but I'm probably wrong about this, but it's, if you take a totally random value over the possible space of the base field or whatever, like, uh, over the possible space of numbers there, you're going to land on a valid curve point. And I think there's like, there aren't enough small subgroups of it or whatever for that to actually do a attack against it. So basically all random strings are valid or at least not attackable,
Davidthe step where you mask off a couple of bits and because you're only operating on the x-coordinates, that fixes it
ThomasRight. But even not doing that, like you're still, there's no practical way to attack that. Right. Well, it won't work anyways, but I'm saying like,
Deirdremasking off those bits is just to eliminate the small co-factor points, right
DavidWhich would be the points in the S in the subgroups
Deirdreyeah.
ThomasThis is the whole clamping debate, right?
GeorgeThis is the hole. That's why I'm making a face. let's not, let's not go down this rabbit hole, not amused.
DavidWell, I will say like, this is one of the
Thomasthis whole
Davidbenefits of elliptic curves over, over finite field Diffie-Hellman, is the smaller subgroups, but that's not, or the lack of small subgroups, but that's not entirely fair to say, because the real benefit is that someone has chosen a group that doesn't have small subgroups. You can choose a finite Diffie Hellman that doesn't have it. It's just for whatever reason, when people do finite field difffie-hellman, 'theyve decided that you should pick the prime at the time that you do it which there are good reasons for it, because if you pick a prime, if everybody agrees on a prime, that's less than 2048 bits and like pulls it out of an RFC, it's probably been like, broken by some intelligence agency, but,
DeirdreYeah,
Thomasthose protocols, those protocols aren't common, right? Like, know, in, you know, yeah. Like in like a dozen years of doing crypto assessments in like the two thousands, right. Like I, you know, like Nate Lawson trained me to go look for, 'okay, can I propose Diffie-Hellman parameters, including, you know, the group that I'm working over?' And if I can do that, then, you know, I have the small sub group attacks on there, subgroup confinement or whatever called them back then. Right. And like, I never found that, right. That was not a real vulnerability for me in real systems. Right. But it's not the case, but the p-curves, like the p-curves just naturally have, if you can, if you can propose a point that isn't valid on the, on the, you know, the P256 curve or whatever, it's like, they're, they're slightly like maybe it's [p]224 is the one that's really scary about this. I forget. But, um, if you can propose an invalid curve point then by doing that, you'll get enough information over iterations, like over like thousands of iterations, not zillions and zillions, right, to reconstruct the key with, uh, with the Chinese remainder theorem.
DeirdreSo now I'm really curious this is, if this falls out of the bad formulas, or if this falls out of the curve that you chose, and my instinct.
Thomasbe the curve.
DeirdreBut does it? Because it sounds like if you're, if you're computing over a point, that's not defined on the actual curve equation, then how are you computing over it? You must not be checking that
Davidthe using the smarter fixes, it has as a side effect of doing the validation that you would have done the the worse
ThomasYup been totally wrong
DavidThere is one protocol that proposed diffie hellman like user-defined Diffie-Hellman parameters, that's pretty popular. It's called TLS versions of 1.2 and earlier. and it's just like the issue with that. And I wrote a paper with, with like, uh, Luke Valenta and Nadia Henninger and a couple other people back in like 2017 or something about this. it's just that the RFCs for— that defined groups for finite field diffie hellman make no goddamn sense. And like, nobody can agree if you should or should not have a subgroup in it. And the actual answer, like you can just ignore the whole paper and just read the last paragraph of it, where there's concrete recommendations. and, uh, It's just like don't, if you're using finite field Diffie-Hellman with a prime, pick a safe prime and a safe prime is a prime where [P-1]/2 is also prime. cause is always going to be even prime numbers are odd for two. and then over 2, get rid of the even part and you wants that to also be prime, because that means you will only have subgroups of order P minus one, over two, which is the max size two. And then, you know, the full group of order P and then everything's just fine. Like, you don't have to do point validation just to make sure you're not getting zero or something dumb.
Thomasis log
Davidthis is, this is not even log— LogJam is just, what if we did number field sieve on your shitty 1024 bit primes and smaller? combined with the fact
Thomaswhich, which paper is
Davidthis is something, something, subgroups, something, something, let me look it up.
Thomassomething? Something's subgroup something. David,
Davidit is called "measuring small subgroup attacks against Diffie Hellman". I contributed the measuring part and people smarter than me contributed the small subgroups part.
DeirdreI was going to bring up one of my favorite things be clear that, you can have a, uh, perfectly defined elliptic curve that has many, many small subgroups, such as a supersingular elliptic curve, which you want it to have a smooth order so that you can use all of those small subgroups to use those subgroup as the kernel of an isogeny map. And then you do a map to a map, to a map, to a map, to a map across a supersingular isogeny graph and, and, and once you have this, you can do, post quantum secure in theory, knock wood, uh, Diffie Hellman-ish, key agreement, but those curves are specifically chosen to be defined so that they have two, independent subgroups. And all of those subgroups are full of small, order-2, order-3 points so that you can use them as generators of subgroups. And you can define isogeny maps with them. uh, but those are, those are supersingular curves and you should not use them for classical elliptic curve cryptography because they are incredibly insecure in that setting. They are explicitly for these, specific post quantum protocol constructions, but they do exist and you, you can use them for reasons like that. Kind of similar to pairing curves, have specific subgroups, with structure for these kinds of different applications.
ThomasI have two things. I have two things on the wrap here. Right? So, uh, number one is for the last month or so I've been typing on a keyboard for my 2017 MacBook pro that's, like Q w six, B T Y. been like harvesting the keys from other keys around my house. And I finally ran out and I bought a 13 inch and it's smaller than the 15 inch I have. So it just sat on the shelf, even though keys are falling off of this one, but they announced the sixteens last week. And so I maxed one out and it's arriving on Tuesday. Now I bring this up, not to talk about M1 macbooks other than that, I think it's funny when I look down at my keyboard, just random letters. but like, because I'm one of those dorks who has like stickers all over their laptops and I decided I needed like one giant ass sticker to cover most of that laptop. And so I had made a bunch of giant ass stickers of our podcast art. We have the. We have the best art of any podcast. I think any podcasts, I think every podcast of all the podcasts our
DavidPeople are talking are best art
Thomasit's just the best. So I could only get a run of 50 of these, even though I only need one of them. So I have 49 giant-ass stickers of our podcast art. So anybody that made it this far in the podcast and listened to Ristretto and OPRFs and all that, uh, you can feel free to hit me up. Um, and I will, uh, endeavor to eventually get you, you know, uh, a sticker. the other thing I had to say was that my wife, the other day, um, pointed out that we've all been pronouncing axolotl wrong. that's not at all how It's pronounced. it's terrible, actually. So the T L at the end of a word, um, but TL is one single consonant. Uh, it does not introduce another syllable, which is important because in those words, usually you're almost always, it's the second to last syllable that gets the emphasis in the word. Um, so when you pronounce it axolotl, you've also introduced another syllable which shifts the accent to the wrong place. So people who actually speak that language, it sounds moronic to we say it
GeorgeIt's actually pronounced like a shallot or something like that.
Thomasit's like a show lot. It's like a sh a sh a shell. Second, the last little booklets, the emphasis, it's like a show level. And like the T is a weird sound like you have to like practice to do the actual T in the language, although it's somewhere between like a T and a C H, but even if you just did the t by itself, you'd be closer than axolotl. So never say that's a lot. That was my other contribution to this.
DeirdreWe're gonna be, we're going to be, phonetically correct. And no one will know what we're talking about.
DavidPhonetically, correct. The best kind of correct.
DeirdreYes, absolutely. Okay. yes. Thank you so much, George. Happy to have you.
GeorgeNo warranty express or implied on, on any statements in the foregoing podcast.
Deirdream a cryptographer. I am not your cryptographer. I do not speak for any employers current or former or future.
DavidAll these comments are actually the opinion of your employer, listener
Georgewho would likely at some point in the past have paid Thomas for his opinions on security.
ThomasDaniels, Midland speeding. A hundred world. we're out.
Deirdrecool. Thank you. Bye.