We talk about Tink with Sophie Schmieg, cryptographer and algebraic geometer at Google.
This rough transcript has not been edited and may have errors.
Deirdre: Hello, welcome to security, cryptography, whatever. I am Deirdre, we’re here with cohost David, how are you doing David?
David: I’m doing well
Deirdre: That’s great. And we also have cohost Thomas, how are you doing Thomas?
Thomas: that my
Deirdre: I know you’re you’re you? You’re Thomas Ptáček.
David: Thomas, I had someone come up to me the other day and be like, your podcast is great, but Thomas keeps talking about how he is bad at his job every episode. He could just not do it.
Deirdre: Um, and our special guest today is fellow isogenist, Sophie Schmeig, who is a like high level muckety-muck cryptographer at the big Google. Hi, Sophie! Welcome.
Sophie: uh, happy to be here. I’m not that high level, I think, but, um, I guess I’m in charge of my team these days. So.
Deirdre: That’s pretty, you’re in charge of other cryptographers. That’s
Sophie: I’m in charge of other crypto, is this true? That makes me like a meta cryptographer.
Deirdre: Yes. Um, you’re also, I think you are the first person I met who calls themselves an algebraic geometer. What is an algebraic geometer, if you can define it
Sophie: I mean, there
Deirdre: and, uh,
Sophie: distinct from, uh, from cryptography. There’s the mathematical study of algebra geometry. And, um, I somehow managed to write a PhD thesis in that study. And, uh, the thesis, uh, has an introduction that I read the other day and noticed that I talk a lot about elliptic curves in that introduction without mentioning cryptography at all.
so it’s, it’s going to mostly talk about like elliptic curves over the complex numbers and stuff like that. So it’s like, uh, uh, you can do a lot of, like basically, uh, algebraic geometry is a giant field and cryptography is using like a, a tiny bit of it.
Deirdre: Yes. Yes. Cool. So almost a, a mathematician algebraic, geometry first, and the cryptographer flows from that.
Sophie: I used to be a mathematician first and these days I would say I’m, I’m probably, uh, more of a cryptographer
Deirdre: fair enough. Chronologically, at least.
Thomas: Dave, I too, I’m an algebraic geometer, but I’m very bad at my job. So I’m a very bad algebraic
Deirdre: cool. Um, thank you, Sophie. Uh, I I’m Googling your thesis now, cuz I realize that I haven’t read it. So I’m gonna go find it and read it.
Sophie: not gonna be a fun experience.
Deirdre: Ah, I’ve read other PhD thesis that were farther outside my wheelhouse and I just did it anyway. Beyond being a favorite isogynist and algebra geometer, you work on some of the things at Google, like the Tink library, and one of beyond being like a nice to use crypto like encryption library with a nice template.
One of the things that you worked on that kind of is touching on tin is binding properties of key material to the key material itself, as opposed to it kind of being defined by a standard or out of band or stored somewhere else. Um, and I think this was like a, like a security design property that I first heard about from you and your work and your team’s work related to Tink.
Can you tell us a little bit more about that?
Sophie: Yeah. Yeah. Um, I have to admit, I didn’t come up with this idea, like that was like done before I even joined the team. Uh, it’s sort of a combination of things that we’ve learned, uh, between different versions that we had of, that eventually led to thing of like, um, a lot of problems stem from the fact that, uh, we, when we talk about keys, we think about like the 32 or 16 raw bites of, uh, random data that don’t include the full information of how it’s going to be used and. The right way, in my opinion, to handle these things is to always consider the key as the entirety of the like function or functions that it defines that it, like I should be able just given the key, I should be able to encrypt something.
I shouldn’t need any additional context, uh, for that. And that means I need to know, do I use AES-GCM with this key? Do I use as AES-CTR-HMAC or something with that key? And, um, this is a fairly simple content, except in some aspects, like I just put everything into the key and then I get like a, a very straightforward API where I just have a function called encrypt that takes a plain text and some associated data.
And then just encrypts that because the key already includes everything else that you need to know. But it also has a lot of security benefits to it. Like I usually do not want to use the same raw key material in two different independent contexts. And that means I don’t want to use the same key material with two different algorithms.
Like, uh, the only case where that would be different is if these algorithms are somehow related, like public key cryptography that have obviously two algorithms that are different, but are related. But, by having all that is necessary to know about your problem contained in that key, you get a lot of things that are like common problems automatically.
Like we have the problem that you don’t know which algorithm to use, which, you might put that algorithm otherwise into the ciphertext, like JWT, which is a favorite topic on this podcast, as I hear, famously does this, where you have like an algorithm in the, in the cyphertext or in the signature.
And that means that this isn’t trusted information, so it can be changed. And that clearly shows that this kind of parameter set needs to be trusted. It doesn’t need to be secret, it could be just authenticated, but in practice, it’s fairly hard to actually enforce that in a generic sense. So just putting everything in one blob and encrypting it with some authenticated encryption will mean that people will take care of handling the key material securely most of the time, at least.
If we also put the algorithm information in that block, then they will not make that mistake of putting that information in the ciphertext. It makes it possible to give people an API that is much simpler because it doesn’t require them to know what, uh, like what an IV is. It doesn’t require them to know what the difference is between various, uh, algorithms and trade offs and so on.
That is where this comes from. And it has a lot of interesting ramifications as well. Like you can do. Uh, you can switch between algorithms. Like say I want to do a post quantum transition, uh, to, I don’t know if isogenies or not, but, uh, in any case I will need to, at some point replace my current key with a new key.
And, uh, in that transition period, I will have two keys. And if both of these keys are like using the same API to be used with them, which in the case of Tink is what happens. Tink operates on, on sets of keys. And the keys could both be like, uh, digital signal speed, like a digital signature or hybrid encryption or something like that.
They just have to be the same primitive. And then you automatically can like switch from I’m now using this key as primary to create my new signatures or to encrypt things or something like that, and use all of these keys as secondary keys to, for active keys, to decrypt something or verify a signature.
And then I can just like, uh, like I put a new key into that set to start with things, uh, so that it can get distributed. I can switch that to active so that like people start using it and then I can, uh, like remove the old one once I’m done. And then I’ve switched the algorithm and ideally, none of your callers and users have ever noticed anything happening at all.
Deirdre: the code changes involved are minimal at best. And it’s just sort of like tweaking a, like a pointer or whatever, to primary versus secondary, and then switching them out. And the API call is the same, which is very nice. Um, it occurs to me, my, my first thought was like, oh, if your hard coding parameters somewhere, and you only have one parameter set, this is basically not an issue, but you almost always have more than one parameter set or in the case of JWT or something similar, you have either signing or some sort of like MAC’ing or something other than asymmetric, you have something symmetric.
You have two different modes. So anywhere where you have a different way to do use a key, you will run into this issue.
Sophie: Yeah. And like the, you definitely don’t run into this issue. If you hard quote, the algorithm choice like that is way of avoiding a lot of these problems with like trusting, uh, like the ciphertext. Developers will not know what to do with these things. So they will put them into some configuration.
And if you’re lucky, they, this configuration is part of your source. And if you’re UN unlucky, this configuration is part of your ciphertext. Um, but by hard coding solves this kind of problem, it doesn’t solve the problem of what do you do if you messed up and you want, you need to change something, whether it’s like you discover that your algorithm is, uh, broken, or you discover that your algorithm isn’t as performant as it could be, or whether it is something like, yeah, I need to transition to post quantum crypto.
So you don’t really have the ability to switch if you hard code. And that is, I think the main downside of hard coding.
Deirdre: That’s interesting because my first instinct would be if I need to make a change with my algorithm or what kind of keys or what, what mode that I’m running in, even. Probably not mode, but definitely algorithm. I would want to version, I would want to make a new release of either my software or like if I’m running a web service or something like that, I would version the web service to be like, cool, you must upgrade to the new version, whatever that looks like for your software to do the new cryptographic thing that is either like new signature algorithm or new symmetric macing algorithm or whatever it is. So do you think that you would not have to do that in sort of this Tink API world?
Sophie: Ideally, you would not have to version the thing that is important, uh, though, is. You have to operate on key sets when you do these things and you have to keep in mind that any key in that key is equivalent. So if I, uh, say something is broken and I need to switch, then only good once I’m actually gotten rid of this key, because my key set is only as trustworthy as a least trustworthy key in it.
Deirdre: Got it.
Sophie: That is, uh, the main caveat. But like, then you can basically say the key said is your versioning and it’s just, uh, pushing it out.
Deirdre: That makes sense. So that instead of it kind of pushing it onto your users to be like, sorry, you must upgrade to get the new thing. It’s you controlling the viable key set and being like cool shunting all the old keys, but the whole set must be turned over and then the next algorithm, then that is, that’s all you do.
You turn over all the keys and the key set and you’re done. All right. All right. Cool.
David: What about the case where like keys have just completely different operations? Like, could you have a key set? That’s like an X25519 key that’s only doing key agreement and an Ed25519 that’s only signing. How you handle that?
Sophie: for Tink, that is going to just lead to exceptions being thrown like it, uh, I think the right thing to do there is to say like, there are these primitives and we can look up in Dan Boneh’s book how they’re defined, and that is what we, uh, what we will use there. And if you like mix those primitives, you are not in for a good time.
Like you don’t want to mix a signature scheme with a, with a MAC scheme. The guarantees that you get are very different. So like the thing that sync does is, uh, it will have these primitives or it has these primitive interfaces. And like, they basically have like one or two functions in them that are like encrypt or sign or verify or something like that.
And then they have a very, very long comment that describes the contract. That is pretty much the, the like academic definition of these functions as, uh, as like, uh, you would define them in a paper or in a book. And that means that you cannot really mix those too. Like, uh, when you do that, it doesn’t really make sense because the key set is supposed to be like, for, from a user’s perspective, the keys in a key set are supposed to be sort of, it’s not supposed to matter which one they take.
Like they shouldn’t even notice. And they notice when they use like an encryption key or a signature key. And I think. That is another one of the mistakes in, in JWT, in my opinions that you shouldn’t have two, two things like symmetric and asymmetric signatures are different. enough that they shouldn’t be in the same functionality.
Deirdre: I have a little bug of mine where a symmetric signature is not really a thing in my mind. A signature is a thing that asymmetric keys are used for a MAC, a message authentication code that uses symmetric stuff in its construction. So I call it a MAC or something like that, but I completely understand where people don’t see the difference, especially when they’re side by side in something like JWT.
And they’re just like,
Sophie: yeah. Yeah. I mean, they, they look very similar. Like the thing that you will see in Tink is very different is that the MAC interface has, uh, compute MAC and Verify function as they’re called. In a single interface, whereas, uh, uh, digital signature will have, uh, different primitives for signing and verifying because these operate on different keys.
Like one operates on the private key. Other one operates on the public key. And what’s even more interesting is said sometimes even the same algorithm can be a different primitive when we are talking about max in particular, like probably at least half of the time, if not more, when you use H me, you’re actually using a PRF, you’re using it as like a pseudo random function as a key hash function.
And what Tink will do is it, it has different primitives for PRF and for MAC, and they even use different key types. You cannot use your MAC key as a PRF key because these are again, completely separate things. They shouldn’t be crossed.
Deirdre: Big big fan of strong typing in these scenarios and, and Lang and especially languages that let you do this. I know that Tink is available in, in Java and go there’s like a Rust port. Am I right? There were some other ones, right?
Sophie: There is. So we currently available, uh, and supporting C++, Go Java and Python.
Deirdre: Oh, Java. Yeah,
Sophie: We do have a JavaScript / Typescript implementation. And don’t think that the, the open source version of that is very usable at the moment. Um, we have, uh, I think an Objective-C one where it’s like similar, we maintain it.
Uh, but it’s not super easy. Like our team only has a finite number of people and adding a language is a huge difficulty. And like the, the Rust port is not maintained by us, but, uh, as far as I know, there has
someone working on it. Yeah,
Deirdre: people, they started the port or something like that. I see rust. I go there first, even if it’s not me not supported, if it’s just over here in a corner, just be like, don’t look at me. Um,
David: If you put
too much
Thomas: if you were talk, oh, Dave.
David: Oh no, I had nothing useful
Thomas: I was gonna ask a question. Right. Which would just be, this is actually my, my big team question. Right. So I, I guess, first of all, like this is like classic us, but like, we, like, we kind of, we dove right into no, no, it’s great. I think it’s, it’s become our trademark. Right. But like, it’s, it’s, it’s probably worth asking Sophie to sell the rest of the world on Tink and what tink is
Deirdre: just like, so you work on Tink!
Then I have like
Um,
Thomas: And then I have a more specific question about when and how to use Tink. Right. My horrible take on Tink, and I’ve talked to people that were working on Tink before, I know Thai pretty well.
Deirdre: think it’s,
Thomas: To me, it seems like Tink is like, Google’s answer toS odium and Tweet NaCl, right?
Like high level cryptography library, like kind of a pin compatible, one for one kind of replacement, like different kind of design ideas. Right. But, uh, you know, the same, the same general goal. Is that a terrible way to think about what Tink is going for?
Sophie: I don’t think it’s a terrible way of think what tin is going for. If I would describe Tink, it’s like basically, uh, like the, the usual blurp that I give people who are especially interested in joining a team or something like that is: our team started out doing security reviews. And when you do security reviews, you start seeing patterns. At some point, start seeing people like going for deterministic IVs when there’s no reason to, or they like need to build an AEADs and, uh, or, or like they need to handle the key.
And at some point reviewing the same mistake over and over again is very frustrating. And you just started writing, uh, like you, you start writing code that, uh, if used will just make it, so that, that is not a problem that you run into anymore. Um, and that is, uh, like the main origin story of Tink in a lot of ways. It makes reviewing, uh, cryptographic applications and cryptographic launches much, much easier because we can focus much more on the design of like, I want to encrypt this with that key over here and push that data over there and so on.
And we don’t need to like, focus that much on like, Hey, how are you generating your IVs? Hey is there an HMAC on that CTR mode here and stuff like that. So that was the like origin story in a lot of ways. And you’ve brought up, uh, NaCl and, and libsodium and so on. There is a lot of similarities in like trying to be a cryptographic library that is hard to misuse and easy to use.
I would say the main difference between Tink and libsodium is that Tink integrates much more closely with the key management Like libsodium still pushes the, the onus
Deirdre: on like
Sophie: of generating, well, it does generate keys, but of like handling keys much more to the user where Tink tries to as much as possible. Ideally you would never ever see the key in an unencrypted fashion anywhere.
And, um, yeah, I think that is also where, where, like this difference that we talked about earlier was like, uh, um, what, uh, um, do we just hardcode the algorithm or do we have it in the key material, uh, itself, uh, comes in a lot where, um, when you put it in the key material itself, you can actually do all that key management layer
Deirdre: mm-hmm
Sophie: for them.
Google’s internal key management system has integration with Tink that it will just generate the keys for you. And, uh, ideally you get the situation where no human ever has seen this, this cryptographic key anywhere and, uh, um,
Deirdre: I love that.
Sophie: lip, Libsodium tries to do this, uh, to do, to solve a similar thing.
It has a very different approach to it, I would say. Yeah.
Thomas: It’s it’s a little, it feels a little tricky to me. I’ve looked a little bit at Tink and like every other programmer I’ve used libsodium for things, but like the sort of the design that you’re talking about for tin it’s similar in some ways to how the old Java APIs for crypto used to work with like Java KeyStore or whatever it was called. Like the keys are abstracted.
Um, you don’t ever really directly touch them. Uh, the things you do with keys are properties of the key objects. And I don’t think that fell out of good crypto design and Java. I think it fell out of, everything’s an object in Java and that’s just a nice way to stuff it all together. Right. But it’s a thing that frustrated programmers that we’re working on cryptography.
And one of the advantages that sodium has is that like, it’s the wrong way to think about keys? Like, you know, a 32 by blob is, you know, a Curve25519 key or whatever. Like that’s not the right way to think about it, but it is the easy way to think about it. Right? Like, it’s definitely like if you’re just trying to get a system up and running and you know, enough to be dangerous, it’s an, it’s an easy way to make a system work.
And like there’s good reasons for you to make this difficult, actually there’s good reasons to make all of cryptography difficult. Right. but you can imagine that being like one of the things about like, you know, one of the culture shock things about switching from, um, sodium to Tink, I guess like the biggest question I would have immediately about tin is, um, we have a lot of Go code and we have a lot of Rust code, right?
Like, would you imagine, like, would it be worth spending a lot of time trying to get Tink working or compatible with a Rust code base right now? I imagine you wouldn’t be using the Rust port, right? You’d probably be calling into,
Sophie: I would imagine you would call under C++ bindings or like the, the problem really is if you don’t have support in a language, you can do, you can do two things. You can do the, the way, like, I just want something that is compatible, uh, which basically means you look at the, at the via format documentation and write something that will just, uh, be compatible.
There is a huge problem though, because it’s a Google library. So of course we use Protobuf, um, and I’ve regretted it ever since. Um, but, uh, um, like the Tink keys are fairly awkward to parse if you don’t have a good roto plibrary available.
Deirdre: And that
Sophie: and that, that has been a bit of a sore spot that we like, uh, especially this year, want to tackle. And refactor some things to make it easier to important export keys, because in some sense, yes, 32 byte key is the wrong way to think about it.
But if I want to be compatible with someone else and I want to transfer my public key and they’re not using Tink, then I need to have something where we can agree on that this the key format that we are using. And, uh, like Tink tries to be very standard compatible, usually like it, uh, uh, will like, we, we now added HPKE support, for example, because we were like, yeah, we want to have the standard ECIS now that it exists as well, but we obviously need some way of like actually importing the public keys and so on.
And that is something that we are working. It’s not trivial because at the same time you want to make it clear to developers that they cannot just take a key and abstract the parameters from it. Like these parameters need to stay this key. Even if you don’t like serialize them with a key, then you need to like, know these parameters and give them back when you, when you want to make them into deserialized key again, because otherwise you run into that issue of not knowing where the parameters came from.
Thomas: I guess, like another interesting thing about Tink, I think. While libsodium is a derivative of NaCL, which was, um, Peter Schwab and Dan Bernstein and, uh, I think, uh, Tanya Lange and all them. There was an original specification for NaCL. Well sort of, right, but like part of the idea of it was there was a specific set of kind of hard-coded choices for what the algorithms were.
And that was part of the premise, right? Is we’re taking away lots of choices from people on purpose, so you only make good choices, right. So there’s a kind of like, if you, if you tell me that you’re using libsodium, that’s no longer the case, libsodium has become its own big thing. Right. Um, but you know, if you tell me you’re using libsodium, I’m going to assume that you’re using some ChaCha Poly variant and Curve 25519.
And that’s not necessarily the case with Tink. It never really was. Right. Like the first thing that ever struck me, um, when people showed me tin was that it does EAX mode as one of its AEADs. Right. Which is, it’s an, it’s an idiosyncratic choice, right? Like it’s, it’s the only place you ever see
Sophie: It is, it is in Tink and is it is in a certain, very important Google infrastructure, which is why it’s in Tink. EAX mode. It’s an interesting mode, honestly. It’s like, it’s not a bad mode in a lot of ways. Um, I somewhat dislike the fact that it uses the same AES key for both, uh, authentication and encryption.
And that the, like, if you read the paper, then it will be like, okay, now we do a do a case by case anlysis of 56 cases or something like that. Which definitely isn’t like the best idea, but it is a very nice, very like decently fast mode. It’s nowhere near GCM, but it is decently fast. And it has a very small code footprint, which I think is the reason that originally people went for it because you need AES and you don’t need anything else.
That is how that mode came in there because it was used and we needed it for some things. But the, the largest thing is that it’s somewhat hard to give an like an official default for encryption. Like for the longest time, the, the predecessor of had the encodedCBC-HMAC-SHA1, which is a completely fine secure.
But AEADs it’s not what anybody would use today because it’s slow, it uses SHA1, and yes, SHA1 isn’t broken, but like, do we really need more things that use SHA1? By it having a default, it makes it very, very hard to actually move away from that default. Because as Deirdre said earlier, you need to make a basically breaking version change.
And that is very hard. If you want to do it across several products at once or something like that. So having the flexibility to choose between different AEADs is very useful if you one day wake up and don’t like your default choices anymore, all that much. And the currently most used, uh, algorithms are like, they all have benefits and drawbacks and any of them are secure.
Like we can just, not pay attention to what people choose and it will likely be fine. But AES-GCM is just by far the fastest mode, but it is also by far the most fragile mode, um, that there’s AES-GCM, which is pretty much about as fast as AES-GCM, but good luck finding any support for it in anything that isn’t BoringSSL. Um, then there is, well EAX mode is like usually just historically useful. Uh, there’s CTR-HMAC mode, which is the like sort of standard in it is extremely slow because no system can evaluate SHA2 quickly because there’s no hardware support for it most systems. But it has very good bounds and it will even if you violate the bounds, oh, well maybe an attacker gets too random, plaintexts.
That’s not the end of the world, as opposed to GCM where they like get part of the key. And then there’s like the modes that are like "I don’t want to ever think about how many ecrypt calls I’m ever making", like XChaCha or AES-SIV also falls under that. Where you can just be, like, when you talk to a team in a review, you will ask them:
"So how many encrypts calls do you do?" And you get an answer that is ever, uh, either like. So, I guess like, uh, "let’s see one to maybe a hundred a month?" And or you get something where they’re like, um, "Yes, so it’s about a million queries per second." So about that. And, um, I don’t know, don’t quote me on that,whether it’s actually a million queries per second, but definitely you have a huge range how many queries people make.
And sometimes you want to be like, okay, I give you this thing that is like, definitely not going to break if you do that. Or I can just say like, yeah, use a GCM that will give you the least trouble in terms of interoperability. Everybody supports a GCM. And if you’re doing like a hundred encrypt calls a month, who cares?
Deirdre: Yeah.
Thomas: The, and like the reason that we care about the number of encryption calls here is because of the nonces, right? It’s because all of these AEADs are non-deterministic, they’re randomized with, you know, a nonce and the GCM nonce is too small. It’s just too small, right? So like the way people like, is that the way you think about the GCM nonce is it’s a bound on the number of times you can call encryption. I have a weird way of looking at this, which is I’m really only interested in these systems to the extent that I can look at code and spot vulnerabilities in them. And I don’t, like when I’m thinking about vulnerability research, I’m never thinking about the number of times something’s called as an encryption function.
Because even though that system blows up, if you encrypt too many times, it’s a nightmare pain in the ass to try to like come up with an exploit for that. Right. But like, you know, if you’re, if you were trying to do a deterministic GCM, no. Where like you use the nonce 1 first and then you try to make sure that you never use it again.
Then you use the nonce 2 and then nonce 3 or whatever like that avoids that. Like how many times am I calling it bound problem. But it introduces a whole playground
Sophie: Yeah. And
Thomas: for as a vulnerability researcher.
Sophie: What you will notice is, uh, Tink will not give you the option of using a deterministic Nonce for exactly that reason. Like you, you can, uh, avoid this issue of like, uh, I can only make 2^32 encrypt calls, but I pay for that with, if I have any kind of problems in my state management, I now have a vulnerability that is much, much easier to exploit than, than that.
And like, even with the 2^32, uh, you need to, to give in mind that that is like the number that the NIST standard mentions for the probability going above one in 4 billion. So it’s not like I encrypt, uh, 4 billion times. And, uh, here is the key it’s I encrypt 4 billion times and there’s a one in 4 billion chance that I can recover the key. You need to go like 2 to the 48 or something to get an actual, like, decent chance as an attacker to actually do something with it. There’s like sort of two reasons to still care about it, at least a little bit. One is compliance. There are some rules that say you’re not allowed to, so you need to, you need to care about it.
Um, and the, the other is that in some cases, these encrypted blocks sit right next to each other in a database. Uh, we added encryption support to query the other day. And like, if there is a, if there is anything where you can exploit this and probably, uh, uh, the, the SQL variant is one of them where you can like, just do a nice little, uh, um, little query to, to find if there is any, uh, of them and in the end, uh, it’s not that much data to go over.
It’s only in the like gigabytes, uh, terabytes range, but, but yeah, I’m not too worried about this being actually exploited. Uh, for the most part the biggest worry that I have really is compliance and best practices and security posture. You should just, you should keep an eye on that.
Okay.
Deirdre: mm-hmm now
Thomas: The documentation for GCM and linsodium has like a snarky warning at the top saying GCM is super popular, but it sucks. Don’t use it. Right. But their approach to this, the whole problem here is similar to how they handle keys. Right? It’s like the interface takes a nonce with a fixed size and it’s like "Have fun!".
It’s a longstanding criticism of NaCl and libsodium that it defers nonce to it’s users. It’s the one thing that is gonna, you know, blow up in these systems is user specified. I should know this off the top of my head, but remind me of the Tink API
Sophie: Tink just
Thomas: this.
Sophie: has an encrypt and a decrypt function and it will just not take a nonce, it will only use a random nonce. And the ciphertext format is like nonce followed by ciphertext followed by by tag. And that way you just completely circumvent that problem because users never can specify a nonce.
What we have is something called deterministic AEADs. Which some people don’t know about that primitive existing at all. Sometimes you, there is some research on how you can do deterministic authenticated encryption. Like there is, um, the whole things about nonce reuse resistant crypto or encryption, and the various SIV modes.
AES-GCM-SIV, I wouldn’t reuse the nonce too much because it’s still GCM under the In the end, similar to GCM, but like there is AES-SIV-CMAC I think it’s called where, um, finally enough, what you need to do is, uh, you need to do a MAC then encrypt instead of other way around. But, uh, you compute the CEC of your plant text, use that CEC as an IV, and then use that IV with a different key in CTR mode.
And then when you decrypt you decrypt in CTR mode, we compute that CMAC, see if it is equivalent to, to your tag or slash IV, which is the same thing. And, uh, uh, only give the, the plaintext you recovered, uh, once you’ve verified that to, to the caller. And because CTR mode is constant time and will never fail it can decrypt any string that you give it that is secure because you don’t have any kind of operation on untrusted data. That actually depends on the, the plaintext in any way. It’s just XOR’ing with something. And, um, like things separates out the deterministic, uh, AEADs from the non-deterministic AEADs and we try to get, get people to use non-deterministic ones.
And like it’s like called AEADs and not, uh, uh, anything more complicated, but sometimes you need to have something deterministic. And in those, those cases, that mode is very much feasible and very robust against any of like, uh, uh, nonce reuse, because like say you put a timestamp or something in there, or some other fairly weak nonce, as long as your, uh, plaintext differs in a single bit it will be completely different because the first thing that it does is it takes your plaintext and, uh, MAC it with, with like CMAC, which act as a PRF for the IV. And that means that you can use it with a weak nonce, you can use it without a nonce and get something where you can do like a form of homomorphic encryption.
That is sort of the, the most boring homomorphic encryption ever imagined where the only thing that I can do is like check equality on the, on the outputs.
Deirdre: Hey
Sophie: It is, it is homomorphic.
Deirdre: you Mac the plane text and you’re using that as your IV. So how is the secure against a chosen plaintext attack? I’m probably missing it.
Sophie: You need to have a different game. It’s not an AEADs anymore.
Deirdre: I see. Okay. Okay.
Sophie: So, the game that you play, like the other, the other name that you can call it is, uh, pseudo random injection, um, where the like pseudo random function, uh, standard primitive, pseudo, random permutation being the block cipher and, uh, a pseudo random injection is, uh, uh, where the permutation is between sets of equal size.
The injection is, uh, one set is smaller than the other. And the image of my, of my encryption operation is somewhat sparse in my, in my set. So I can still tell whether or not this was a valid, plain text, but I have the same, uh, property of like the, uh, PRF oracle description that like, I’m not allowed to ask for the same plaintext twice, or like I’m expected that I get the same ciphertext when I ask for the same plaintext twice.
And that is how you define. Uh, the, the properties for data AEADs, but that is, that is also, uh, showing why we make it a different primitive because it has a different definition. So even though it has an encrypt and a decrypt and they take the same arguments, it will be a different primitive because, uh, it violates the contract that you make with, with an AEADs.
Deirdre: With a classic AEADs. Yeah. Okay, cool. Thank you.
Thomas: This is like, this is a thing Colm about a lot. Like if you bring up SIV with him on Twitter you’ll get, you’ll get a long thread about how like their applications were deterministic. AEADs are problematic because of message correlation.
Sophie: It’s definitely that AEADs is definitely a bit of a sharper tool. Like it is something that you need, uh, in quite a few scenarios. You need something where I can still have equality, but it also means that yeah, there. If I like take a, take a text and, uh, tokenize every word and encrypt it deterministically, yeah, I can totally, uh, uh, do some statistical attacks and probably recover, uh, uh, several words at least there.
So, uh, um, SIV has its place, but it shouldn’t be your go-to when you want to encrypt something.
Thomas: You you have in, in the Tink API, there’s also. You have XChaCha. So like my feeling, and again, I’m bad at my job, so David can correct me on my feelings, but like my feeling is that when, when you’re thinking about this problem of, you know, um, I have to manage this nonce and I have a certain number of calls I can give for a certain nonce size or whatever.
Like the two kind of standard answers in modern cryptography for that problem are deterministic AEADs and GCM-SIV is the big one that people talk about. And then XChaCha is the other one where the solution to that, that it provides is just a gigantic freaking nonce, right? Like, you know, just so much that you could just fill it up with random data and never ever think about it.
Right. Which I, I, I kind of like, cuz it’s really simple to reason about. How do you feel about that argument that like, uh, you know, nonce misuse resistance is maybe a little bit of a
Sophie: I definitely
Thomas: and what we really just need are nonces.
Sophie: has this long nonce, and I think that the fact that we are still, uh, stuck with AES, which visits, uh, 16 byte block size, uh, which like kind of limits all of the, these nonce sizes and everything is kind of a problem. Uh, a lot of times because it makes collision probabilities way too low.
Um, I think that the, uh, uh, use cases are slightly different. Like the question is, do you have something that can act as a nonce, maybe as a low quality nonce, but can act as a nonce? Like something like a timestamp, uh, is a perfectly reasonable, very low quality nonce. Like, yeah, there will be collisions, but there shouldn’t be too many collisions.
Um, or do you just not have anything of that sort? And I think that, uh, definitely that the XChaCha mythology is like the best way of, of dealing with, uh, with that problem. Um, the main reason why we have both in there is performance, uh, related. Like when you care a lot about, uh, the nonce-space being exhausted, you are likely having, making a lot of queries, um, so, uh, uh, the difference between GCM-SIV and XChaCha20 is significant enough to count in these cases to be like, uh, uh, enough monetary value that you want to have the option for both.
Um, like just because, uh, as AES-GCM-SIV can use all of that nice polynomial, uh, algebraic metric over, over characteristic two tricks to two speed things up which XChaCha20 Poly1305 doesn’t have, or, uh, uh, it uses AES and, and has hardware support for that. So it is, uh, XChaCha20, Poly1305 is certainly not the slowest, uh, cipher out there.
Uh, and it’s like the, the best choice if you’re not sure what hardware support, um, platforms have. But if you know that you have hardware support for both, uh, the AES part and the carryless multiplication part, then AES-GCM-SIV is quite a bit faster. And, uh, so if you are in a situation where you really care about this nonce space, you probably want to use C++, and you probably want to use, uh, GCM-SIV or rust, I guess.
But, um, we don’t have much plus unfortunately.
Deirdre: Yeah, it was in my brain. It was as GCM for all the hardware that supports it. And then Chacha poly for software, the fast option for software that doesn’t have the hardware support. And I think that’s been burned in there from like TLS 1.3 stuff and, uh,
Sophie: yeah, yeah. That is as far as I can tell that is pretty accurate. And then you have, uh, Anything CTR or CBC-HMAC, very, very far off the very slow end,
Deirdre: yeah, legacy.
Sophie: me is very slow.
Thomas: Is Tink the first like thing you did at Google for cryptography, like how did you get from algebraic geometer to where you are?
Sophie: because it is, uh, not as all straight. So I finished my PhD when I was at 2013, and then I got a job offer from Google 2014 and ended up being on the search ads, uh, team on specifically the team that, uh, computes the auction price. So like the, the different headset that.
Uh, all the things that run when you do a search query that like, uh, determines what an advertiser will have to pay when you click on that. And, uh, I was on the team for four years and, uh, was then like, ah, I’m kind, uh, uh, looking for something else. Like you can’t do search ads forever. It’s uh, I got too bored with that and I was looking at several different teams and then I went into Thai on that search and I was like, wait, you, you know, algebraic geometry.
Why aren’t you doing crypto? You know, the crypto stuff as well. And that’s how I ended up doing crypto, uh, or that’s how I joined the crypto team. I, I was doing crypto before then as well. Uh, mostly like because I was like doing, uh, things like doing a PhD in algebraic geometry. And what usually happens then is that you have to teach the class about cryptography.
And I was like, yeah, I kind of want to know how this now actually works. Like, I understand why, like, uh, I compute an Euler totient and then you get an RSA that works, but that can’t possibly be how you actually use it. And so, uh, uh, I like sort of doing that PhD on the side was like reading Schneier’s book and, and stuff like that to like, at least know how this works.
And it turned out that that would be come very useful later on, but that’s, that’s how I ended up on, uh, on the cryptography team, uh, which was like, yeah, it was definitely not. The straightest pass into it. And it was definitely a, a case of, uh, like not really knowing how to get into cryptography. Like I always was interested in it, but it’s a very hard field to get into if you don’t happen to be in the right place.
And, uh, the University of Allman Germany was not the right place, at least for me at that time.
Deirdre: I had no idea you worked on search or ads or anything. That’s awesome. Yeah.
Thomas: So, so, so Thai, who you’re talking about, this is Thai Duong, right? So, um, of TLS BEAST and CRIME, one of my, by the way, one of my favorite people on the, on the Internet, um, So did working with Thai change the way you, uh, you think about cryptography, you look, are you like a different kind of cryptographer for being in with Thai?
Sophie: Yeah. I definitely like, uh, as I said, the things like, uh, the, the way that Tink handles keys was something that existed before I joined the team. And it’s definitely, uh, like the, the interesting part about that is that it very, very quickly sort of gets absorbed as like your default way of thinking about things to the point that, that you’re like sometimes that, uh, sometimes I’m like incapable of imagining that a key would not be, uh, containing the parameter set because that’s not a complete key. Why, why would you do that? Uh, so, so it is like, it felt very natural and like, especially given that I like worked on a more software engineering focused team for like several years, it also makes, uh, makes the interface feel a lot more natural in my, my opinion, because it’s like, it’s a very clean API of like, when I want to encrypt something, I want to give you the things that I want to encrypt.
I don’t want to handle a nons. I don’t want to like, think about that. Um, so it very, very quickly just sort of like, oh yeah, this is how you’re supposed to do that. So yes, definitely it’s changed my, my way of thinking about cryptography. Um, like almost to the point that I didn’t even notice that it changed.
I
Thomas: have a, I have a dumb question, right? So like, um, In kind of the same thing, cuz when I think about the way Thai thinks about cryptography, it’s very he’s he comes from vulnerability research too. Um, I’ve kind of a mental, this is a total aside, but I have like a, I have like kind of a mental kind of org chart of cryptography.
I, I try to keep track of how many people are in cryptography or doing the kind of cryptography that they do because of the influence of Trevor Perrin. Because you get from Trevor Perrin to Nate Lawson and then from Nate Lawson, you get to Thai Duong and then you get to like all of the modern TLS attacks through the work that he did.
Like I, I don’t know that like the tends of, of that Trevor Perrin guy are, are bananas. You, um, you tweet, somebody asked you how you got to however many followers you have on Twitter. I don’t know how many followers you have on Twitter, but your answer was that you
Sophie: yeah, it’s, uh, actually relevant, uh, to, to the conversation. The vuln was, uh, really funny. What happened was that someone, uh, imported some AWS SDK into, into some Google system for some project, I don’t even know what project it was. And, um, it tripped some, uh, required review alert. Uh, I think because it used MD5 somewhere and it was like the entire AWS SDK and I, I like looked at that giant code base and I was like, yeah, I, I like, I can either just click LGTM or I can at least say, uh, search for crypto.
And that’s what I did. And, uh, that way I managed to find uh, the S3 crypto, um, S3 encryption SDK, which like, uh, um, did several things that we talked about from, uh, of like, uh, uh, having the parameters set start with, uh, with the ciphertext as metadata in the bucket, uh, instead of having it stored, um, with, uh, key material or, or otherwise authenticated, um, and, uh, uh, it was, uh, that was, uh, the biggest, uh, one and like, I, it supported both CBC without an HMAC and, um, GCM mode and GCM mode was the default, but CBC was in there because of like, it allows for an easy streaming API, which is a topic for a different podcast, I think, uh, on the difficulties of, of doing, uh, encrypting large files. Um, but, uh, uh, yeah, so what you could do is you could take, uh, if you have right access to a bucket, uh, that uh, uh, that has these encrypted files in it, you could change the algorithm from GCM to CBC, and then you can do a padding oracle attack on the CBC that like requires the entire 16 bytes of plaintext to be guessed.
It’s not the most feasible attack in most cases, but it’s definitely feasible in certain cases. And, uh, that was like, uh, I think that was the point where I gained the most followers, uh, that I like found, found an AWS, uh, vulnerability and that like, people like that. Yeah, I, I, I like the story because it was just so random.
It was just really like, uh, uh, me trying to see, like, I basically me not wanting to just rubber stamp it, but then at least look why this, uh, alert, wanted me to review something and then finding like, wait, that’s not how this is supposed to be. The MD5 was, was another part of vulnerability, unfortunately, because there was, um, the, the cloud buckets have these ETAGs that are like, uh, uh, used as, um, as integrity checks. Um, and what it did was this client computed the MD5 of the plaintext. Um, and encrypted, uh, the plane text and then added this MD5 of the plaintext in plain to the metadata.
And that was like, uh, so that was like the, the third part of that vulnerability of like, yeah, you, you shouldn’t like the MD5 of plaintext, uh, for cryptographer is the same as the plaintext so congratulations to just revealed the plaintext and, uh, like, yeah, it was all in all. It wasn’t the biggest vulnerabilities per se, but they were kind of cool vulnerabilities.
And so people enjoyed that. Yes. Yes. AWS did a stellar job. Uh, like I, uh, uh, gave them, uh, like I notified them and they like, uh, fixed it, uh, very fast. And they were like, oh yeah, this was like, uh, uh, like, yeah, we, we didn’t really see that part. And we’re very happy they, they could fix that. And, um, yeah, it, it definitely got fixed and, uh, was nicely is, is working very nicely now.
Deirdre: Awesome. what what’s happening in, in Sophie land? That’s not just all tink and keys all the time.
Sophie: Um, uh, isogenies yeah,
David: don’t believe they
Sophie: with such of, like, I’ve been trying to find a way of, uh, selecting a random, super singular curve, which is an extremely hard problem.
Deirdre: it is. And I was gonna be like, have you solved this?
Sophie: No, I have, I have nowhere near solving it. I think if anything, I’m, uh, uh, getting convinced that it is impossible, uh, under certain circum, uh, under certain assumptions, but I’m not, uh, I haven’t formalized that enough yet to actually like, be like, yeah, it’s definitely impossible to do this, but I think there’s an argument to be made that it’s not possible to select a random, super singular curve without revealing the, or without learning the, the
Deirdre: the ring
Sophie: endomorphism ring.
Um, but which is sad. Like
Deirdre: It is.
Sophie: it’s I saw is the closest that we have to this paradise that are elliptic curve groups for cryptography. And they’re just nowhere near, like they, nowhere near as good as, uh, what, what elliptic curve groups can group structure can do. But.
Deirdre: Yeah.
Sophie: At least they are, they are Diffie-Hellman variant, so that’s good.
Deirdre: Uh, what do you think of the, the class group actions versus the super singular walks? Uh, SIDH style? Yeah,
Sophie: I’ve looked a lot more at the super singular walks and I’ve looked at the class group action, the class group action. It definitely seems to have a lot of promise. Uh, it I’m a bitch concerned that it has like this a billion things happening. It feels to me, intuition wise, at least that quantum computers are bad at anything non, non, non abelian and doing something abelian feels kind of scary.
On the other hand, the class group is notorious for being super difficult to compute anything with, but then again, quantum computers can compute a lot more about the class group than normal computers can do. Like there’s a bunch of cases where the algorithms, when read like class group algorithms that just says, and now we compute the discrete logorithm towards this spaces and you just like, okay, that means that, um, I’m not going to use this for, uh, for cryptography ever, because I’m like, uh, uh, restricted to, to like maybe 10 bits at most.
Deirdre: Yeah, I mostly am just sort of aware of like SIDH and everything related to it is like, oh, we were too conservative. We can reduce our sizes because we were too conservative. And the, like, everyone was worried about these, uh, these, uh, auxiliary torsion points being a, a, a vulnerability mechanism. And it doesn’t really seem to have panned out.
but on the other hand, like class groups and seaside and CRS and stuff like that, it’s like, no, we gotta keep bumping up the parameter sizes. And we have to keep, uh, bringing down the capability of our adversary as opposed to modeling them as like, you know, the most powerful adversary with the quantum computer that might ever be in order to like, theoretically be able to deploy this thing.
I’m just like, ha, it’s a lot of hedging.
Sophie: Yeah. Yeah, it’s definitely, I mean, that’s like the, the downside of like all isogeny crypto, to some extent, a bit that like compared to lattices and codes, it’s very new and, uh, it’s very scary. Like I talk to my PhD advisors and they’ve never heard about, uh, the fact that people want to do cryptography with that stuff.
And the like, we need to, we need to be at that point where like any mathematician who works on this topic is aware if they like right now, if they run into a factorization algorithm, we can be fairly certain that they’re like, oh yeah, this is, this is going to break RSA, this is a big deal I should follow up here.
Whereas such is, I’m not sure if they would notice. Uh, and we definitely need to get to the point that, that, uh, people notice we need to like, uh, uh, have much more like research and also, um, like making it much more approachable, uh, like understandable for, for non algebraic geometers, uh, to do before isogenies are really ready to work out and pretty sure what will happen is similar to, to the way it happened with RSA and elliptic curves, where RSA was, uh, there first and I can teach RSA to a high schooler and they will probably know, uh, like they probably have an idea of why it’s difficult and how it works. Uh, elliptic curves is much, much harder to, to teach, um, and to understand, but it’s like, it has clearly shown that it’s superior to RSA in almost all ways.
And I would be very UN surprised if we see the same thing with, with the post quantum algorithms that like lattices and codes will be the things that, uh, NIST goes with now. Um, and then over time, as we understand isogenies better and trust them more, we actually switched to isogenies because we made them more. We made them faster and they’re smaller.
And so on, like same things that happened with elliptic curve.
Deirdre: Yeah. I, I like that kind of pattern match, cuz I, that does feel very, there’s a, there’s a ton of stuff you can do with lattices that we probably will never be able to do efficiently with isogenies, stuff like the fully homomorphic encryption and you know, whatever. But that pattern of like the first things first gets deployed.
It’s fine. You know, you can understand it easily, which is a lot of the lattice stuff. And the code, the code stuff goes back so much, even further. But then when we learn algorithmic tricks and implementation tricks for the isogeny stuff, it’s both smaller and faster and we’re, and we everyone’s like let’s use this.
This is better for reasons.
Sophie: yeah, yeah. But I definitely think right now, I can’t see, uh, uh, NIST or, or anyone like going with isogeny and being like, oh yeah, we totally trust this. It’s just, it’s cool. And I want it to be the one that wins out in the end, but it’s not there yet.
Deirdre: yeah, it’s a bit early and yes, I want, I want all the mathematicians who are just hanging out in their departments being like, wait, you’re using this for cryptography. You should know about this thing that we just all vaguely know. And we never mention it before.
David: Wasn’t uh, almost nobody even like using elliptic curves at all until Wiles showed up and was like, Hey, I’ve proven, uh, Fermat’s Last Theorem. And like, when
Sophie: Definitely. Definitely. He made algebra, geometry, the, the hot topic, but, uh, elliptic curves are sort of like you run into them automatically when you do algebraic geometry, like in some sense you can say that like Jacoby and Arkell worked on, uh, uh, elliptic curves. You can’t tell them that though, because they wouldn’t have known that.
But, uh, they like a lot of the, the theorems that they did. are actually theorems about elliptic curves or like related to elliptic curves. They just didn’t know that they were doing that. But, uh, certainly for you for use, like, it certainly got a lot more popular with this Wiles and Fermat’s Last Theorem. Um, there’s like, there’s some other things.
So there’s like the, the generalized Riemann hypothesis that you can prove for, uh, an algebraic geometry instead of just being like, oh yeah, we’ve conjecture this. Um, and, uh, uh, things like that and like the algebraic number series, uh, like basically gro deep started a lot of the, the like, uh, uh, memes in, uh, uh, in algebraic geometry and made it this very, uh, uh, very popular research.
It definitely isn’t the, the most well researched, uh, uh, for cryptography there.
Deirdre: it’s it’s so new. Um, Sophie, thank you so much. I’m so glad you could join this. This is great.
David: Is anyone ever gonna prove or disprove the Riemann hypothesis?
Sophie: Uh,
David: I
Sophie: let me see. There has been some progress that has been made so far, at least, uh, the things that I did 10 years ago, or like more than 10 years ago when I was still, uh, uh, studying, uh, this, uh, none of them symptomatically ever moved beyond the, uh, uh, that the real part of that is equal to one line. Like they, they have like proved the Riemann hypothesis for like, sort of curvy bits.
But they all as symptomatically go to the real part being equals to one. So it’s not looking super good. But then again, um, I don’t know. It’s more likely to be proven than P than P equals NP I think. I don’t
Deirdre: so. I hope so.
Sophie: I mean, I hope nobody proves P equals NP, but, uh, even P unequal NP seems to be, uh, like one of the, the things that is very hard to get any interaction on.
Deirdre: Yeah. Spicy hot take. No one’s ever gonna prove it. Cool.
Sophie: I mean, maybe it’s, maybe it’s not provable. there’s, there’s a bunch of, uh, things that we’ve shown that they’re undecidable.
Deirdre: Sophie Schmieg thank you so much for joining us. Writing us.
Sophie: Yeah. Thank you for having me.
