Security Cryptography Whatever
Security Cryptography Whatever
Tink with Sophie Schmieg
Use Left/Right to seek, Home/End to jump to start or end. Hold shift to jump forward or backward.
We talk about Tink with Sophie Schmieg, cryptographer and algebraic geometer at Google.
Transcript:
https://securitycryptographywhatever.com/2022/05/28/tink-with-sophie-schmieg/
Links:
- Sophie: https://twitter.com/SchmiegSophie
- Tink: https://github.com/google/tink
- RWC talk: https://youtube.com/watch?t=1028&v=CiH6iqjWpt8
- Where to store keys: https://twitter.com/SchmiegSophie/status/1413502566797778948
- EAX mode: https://en.wikipedia.org/wiki/EAX_mode
- AES-GCM-SIV: https://en.wikipedia.org/wiki/AES-GCM-SIV
- Deterministic AEADs: https://github.com/google/tink/blob/master/docs/PRIMITIVES.md#deterministic-authenticated-encryption-with-associated-data
- Thai Duong: https://twitter.com/XorNinja
- AWS-SDK Vuln: https://twitter.com/XorNinja/status/1310587707605659649
"Security Cryptography Whatever" is hosted by Deirdre Connolly (@durumcrustulum), Thomas Ptacek (@tqbf), and David Adrian (@dadrian)
Hello. Welcome to security, cryptography, whatever. I am Deirdre. We're here with co-host David. How are you doing, David?
SPEAKER_02I'm doing well today, thank you.
SPEAKER_03That's great. And we also have co-host Thomas. How are you doing, Thomas?
SPEAKER_02Is that my title? I'm a co-host.
SPEAKER_03I don't know. You're you're you. You're Thomas Tacek.
SPEAKER_02Thomas, I had someone come up to me the other day and be like, your podcast is great, but Thomas keeps talking about how he's bad at his job every episode. He could just not do it.
SPEAKER_03Um and our special guest today is fellow isogenist Sophie Schmieg, who is a like high-level muckity muck cryptographer at the big Google. Uh hi, Sophie. Welcome. Hi.
SPEAKER_00Yeah. I'm uh uh happy to be here. I'm not set that high level, I think, but um I guess I'm in charge of my team these days.
SPEAKER_03So that's pretty you're in charge of other cryptographers.
SPEAKER_00That's uh I'm in charge of other cryptographers. That's true. That makes me like a uh a meta-cryptographer.
SPEAKER_03Yes. Um you're also, I think you're the first person I met who helped calls themselves an algebraic geometer. What is an algebraic geometer, if you can define it?
SPEAKER_00I mean, there is uh like distinct from uh from cryptography, there's the mathematical study of algebraic 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 gonna mostly call uh talk about like elliptic curves over the complex complex numbers and stuff like that. So it's like uh uh you can do a lot of like basically uh geometry is a giant field, and cryptography is using like a tiny bit of it.
SPEAKER_03Yes, yes, cool. So you're almost a mathematician, algebraic geometry first, and the cryptographer flows from that.
SPEAKER_00I used to be a mathematician first, and these days I would say I'm I'm probably uh more for cryptographer.
SPEAKER_03Fair enough. Chronologically, at least. Um Thank you, Sophie. Uh I I'm Googling your thesis now because I realize that I haven't read it, so I'm gonna go find it and read it.
SPEAKER_00It's not gonna be a fun experience.
SPEAKER_03Yeah, I've read other PhD thesis that were farther outside my wheelhouse, and they just did it anyway. Um beyond being a uh uh a favorite isogynist and uh algebraic 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 um with a nice template, um, one of the things that you worked on that kind of is touching on tink 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?
SPEAKER_00Yeah, yeah. Um I have to admit, I I didn't come up with this idea. Like uh that was like done before I even joined the team. Uh it's sort of a communation of like things that we've learned uh between different versions uh that we had of that eventually led to Tink. 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 bytes of uh random data that like don't include the full information of how it's going to be used. And um 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 giving the key, I should be able to encrypt something. I shouldn't need any additional context uh for that. Okay. And that means I need to know: do I use AES GCM with this key? Do I use AESCDR HMAC or something with that key? And um this is a fairly simple concept in in some aspects. Like I just put everything into the key and then I get a very straightforward uh API where I just have a function called encrypt that takes a plaintext and some associated data and then just encrypts that because the key already includes everything else that you need to know. Um 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. Yep. 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. I have obviously two algorithms that are different but are related. But uh uh by like 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 uh or you you might put that algorithm otherwise into the ciphertext as like JWT, which is like a favorite topic on this uh on this podcast, as I hear um uh uh famously does, where you have like an algorithm in the in the ciphertext or in the signature, and that means that this isn't trusted information, so it can be changed. And that clearly shows that like 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 uh like people will take care of handling the key material securely, most of the time at least. Um and if we also put the algorithm information in that blob, 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 ID is, it doesn't require them to know what the difference is between various uh algorithms and trade-offs and so on. So um yeah, that is where 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.
SPEAKER_03Yep.
SPEAKER_00And 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 like operates on sets of keys, and the keys could both be 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 like create my new signatures or to encrypt things or something like that, and uh use all of these keys as uh like secondary keys to for as 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 like start with uh start with things uh so that it can get distributed. I can switch that to active so that like people start using it. Yes. 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.
SPEAKER_03Yes, 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 you're 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 Macing or some 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, quote unquote a key, um, you will run into this issue.
SPEAKER_00Yeah, and like the you definitely don't run into this issue if you hard-code the algorithm choice. Like that is a way of avoiding a lot of these problems with like trusting uh like the ciphertext. So like 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 unlucky, uh 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 uh you need to change something, whether it's like you discovered 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 it.
SPEAKER_03That's interesting because my first instinct would be if I need to make a change, like 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, like 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 macking algorithm or whatever it is. So do you think that you would not have to do that in sort of this kind of tink API world?
SPEAKER_00Ideally, you would not have to version. The thing that is important uh though is that you have to operate on key sets when you do these things. Okay. And you have to keep in mind that any key in that key set 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 the least trustworthy key that is gonna caveat. But like then you can basically say the key set is your versioning.
SPEAKER_03Yep.
SPEAKER_00And it's just uh pushing it out of the day.
SPEAKER_03That 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, yeah. Shunting all the old keys, but the whole set must be kind of uh turned over, and then the next algorithm, then that is that's all you do. You turn over all the keys in the key set and you're done. All right. All right, cool.
SPEAKER_02What 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 ed 25519 key that's only signing how do you handle that situation?
SPEAKER_00That 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 Bonnet'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're not in for a good time. Like you don't want to mix a signature scheme with uh with a Mac scheme because the guarantees that you get are very different. So like the thing that Think does is uh uh it will have these primitive 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 two. Okay when you do that, uh it doesn't really make sense because the 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 signatures key. And I think that is another one of the mistakes in in JWT, in my opinion, is that you shouldn't have two things like symmetric and asymmetric signatures are different enough that they shouldn't be in the same functionality.
SPEAKER_03And I I have a little bugbear of whenever a symmetric signature is not really a thing in my 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 Yeah.
SPEAKER_00Yeah, 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 a compute Mac and verify function, as they're called, in a single interface. Whereas uh a digital signature will have uh different primitives for signing and verifying, because these operate on different keys. Like one operates on the private key, the other one operates on the public key. And what's even more interesting is that sometimes even the same algorithm can be a different primitive. Uh when we are talking about Macs in particular, uh like probably at least half of the time, if not more, uh when you use HMAC, you're actually using a PRF. You're using it as like a pseudo-random function as a key hash function. Yep. And what Tink will do is it it has different primitives for PRF and for Mac, and they even use different key tabs. You cannot use your Mac key as a PRF key because these are again completely separate things. They shouldn't be crossed.
SPEAKER_03Big big fan of strong typing in these scenarios. And and like and especially languages that let you do this. I know that Tink is available in in Java, in Go. There's like a Rust port. There are some other ones, right?
SPEAKER_00There is so we're currently available uh and supporting C, Go, Java, and Python. Yeah. We do have a JavaScript slash TypeScript implementation. I don't think that 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. Yeah. And adding a language is a huge difficulty. And like the Rust port is not maintained by us. But it's the as far as I know there's someone who's Project Oak people.
SPEAKER_03They started the port or something like that. That would just 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.
SPEAKER_01Um Dave, you got to Oh no, I had nothing useful to say. Go ahead. I was gonna ask a question, right? Which would just be this is actually my my big tink question, right? So I I I guess first of all, like this is like classic us, but like we like we kind of we dove right into it. 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 then. We were just like, so you work on Tink. Yeah. And then I have a more specific question about when and how to use Tink, right? But like, yeah, like you know, my my horrible take on Tink, and I I've talked to people that were working on Tink before. I I know um Ty pretty well. Um like to me, it seems like Tink is like Google's answer to sodium and tweet knuckle, 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?
SPEAKER_00I don't think it's a terrible way of thinking what Tink is going for. If I would uh describe Tink, it's like basically uh like the usual blurb that I give people uh who are especially interested in joining a team or something like that is that uh our team started out doing security reviews. And when you do security reviews, you get uh you start seeing patterns at some point. Like you start seeing people like going for deterministic IVs when there's no reason to, or they like need to build an AEAD and uh or or like they need to handle their key. And at some point, uh reviewing the same mistake over and over again is very frustrating, and you just start 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.
SPEAKER_04Yeah.
SPEAKER_00Um and that is uh like the main origin story of Tink in a lot of ways. That it's like it makes reviewing uh cryptographic uh applications of 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 UIVs? Hey, is there an HMAC on on that uh like uh CTR mode here and stuff like that? So that was the like origin story in a lot of ways. And uh you've brought up uh knuckle and and lipsodium and so on. There is a lot of similarities in like trying to be a cryptographic language that is uh cryptographic library that is uh um like hard to misuse and easy to use. I would say the main difference between Tink and Lypsodium is that Tink integrates much more closely with the key management layer. Like Lypsodian still pushes the the like owners on like uh generating well it does generate keys, but of like handling keys much more to the user, where Tink tries to as much as possible just uh ideally you would never ever see the the key in an unencrypted fashion anywhere. Nice. And um yeah, I think that is also where where like this difference that we talked about earlier is like uh um what uh um do we just hard code the algorithm or do we have it in the key material uh itself? Uh comes in a lot where uh um when you put it in the key material itself, you can actually do all that key management layer for like for them. There is like uh uh Google's internal key management system has integration with Think that it will just uh uh generate the keys for you and uh ideally you get the situation where no human ever has seen this this cryptographic key uh anywhere and uh um I love that. Lip uh Libsodium while it tries to do this uh to do to solve a similar thing, it has a very different approach to it, I would say.
SPEAKER_01It's uh it 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 the the the sort of the design that you're talking about for Tink, 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 in Java. I think it fell out of everything is 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 were 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-byte blob is, you know, a curve 255 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? Um, but like, yeah, you can 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 tink 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 um a Rust code base right now? I imagine you wouldn't be using the Rust port, right?
SPEAKER_00You'd probably be calling into I would imagine you would call into the 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 um it's a Google library, so of course we use proto in it. Um and we regret it uh ever since. Um but uh um like the tink keys are fairly awkward to parse if you don't have a good proto library available. Um and that that has been a bit of a sore spot that we like uh especially this year want to tackle uh and and refactor some things to make it easier to import and export keys. Because in some sense, yes, 32-byte key uh is the wrong way to think about it. But uh if I want to be compatible with someone else and I want to transfer my public key and they are not using Tink, then I need to like have something where we can agree on that this is uh the 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 uh ECIES now that it exists as well. But but we obviously need some way of like actually importing the public keys and so on, and that is something that we're working on. Um it's not trivial because at the same time we 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 with this key, even if you don't like serialize them with the key, then you need to like know these parameters and give them back when you when you want to make them into a deserialized key again, because otherwise you run into that issue of like uh uh not knowing where the parameters came from.
SPEAKER_01I I guess like another interesting thing about Tink, like I I think like when when like lib sodium is a derivative of Knackle, which was um Peter Schwab and Daniel Bernstein and uh I think uh Tanya Launch and all them. Um so like there was an original specification for Knackle. Um part of the I 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 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, it'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 you're using some Chop Poly, you know, variant and curve 25519. And that's not necessarily the case with Tink, and it never really was, right? Like the first thing that ever struck me um when people showed me Tink was that it does EAX mode as one of its A ADs, right? Which is it's a it's an idiosyncratic choice, right? Like it's it's the only place you ever see EAX.
SPEAKER_00It is in Tinky and it's it is in certain very important uh Google infrastructure, which is what it is. Uh yeah, 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 uh uh encryption, and that the like if you read the paper, then it will be like, okay, now we do uh do a case-by-case analysis of 56 cases or something like that. Um which definitely isn't my my uh like the best idea, uh, but it is a very nice, very like decently fast mode. It's nowhere near GCM, but it is decently fast. And uh uh 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. Um yeah, that is that is how uh why 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 of uh like an official default for encryption. Like for the longest time, the the predecessor of Tink had the encoded uh default for AEDs to be ASCBC HMAC SHA1, which is a completely fine, secure uh AED. It's not what anybody would use today because it's slow, it uses Share1, and yes, HMAC SHA1 isn't broken, but like do we really need more things that use SHA 1? Um But uh by it having a default, it makes it very, very hard to actually move away from that default because as Dietre 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 AADs 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 uh uh they all have benefits and drawbacks, and any of them are secure, like we can just uh not pay attention to what people choose, and it will likely be fine. But uh there's like ASGCM, which is by far the fastest mode, but it is also by far the most fragile mode. Um that there's ASGCM SRV, which is uh pretty much about as fast as AESGCM, but good luck finding any support for it in anything that isn't uh boring SSL. Um then there is uh um well EAX mode is like usually just historically uh useful. Uh there's CTRH Mac mode, which is the like sort of standard in it is extremely slow because no system can evaluate SHA 2 quickly because there's no hardware support for it in most systems. Uh but it has very good bounds and it will even if you violate the bounds, oh well, maybe an attacker gets two random uh plaintex. That's not the end of the world as opposed to like GCM, where they're like, get part of the key. Um and then there's like the um the modes that are uh like uh I don't want to ever think about how many encrypt calls I'm ever making, like X Shutcher or um ASGCM SIV also falls under that. Uh uh where you can just be like when you talk to a team in a review, they will be uh 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, two, maybe a hundred a month, and or you get something where they're like, um yes, so it's about a million q queries per second. So about that. And um, I don't know, don't quote me on that. Uh whether it's actually a million queries per second or like but like uh um definitely large. You have a huge range of how many uh queries then uh 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 AESGCM. That will give you the least trouble in in any interoperability. Everybody supports AESGCM. And if you're doing like a hundred encrypt calls a month, who cares? Yes.
SPEAKER_01And 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 AADs 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 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 I I I have a weird way of looking at this, which is like I'm really only interested in these systems to the extent that I can look at code and spot vulnerabilities in them. And like, I don't like when I'm thinking about vulnerability research, I'm never thinking about the number of times something's called like 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 knots where like you use the nonce one first and then you try to make sure that you never use it again, then you use the nonce two and the nonce three or whatever, like that avoids that like how many times am I calling it bound problem? But it introduces like a whole pl a whole playground of fun issues for me as a vulnerability.
SPEAKER_00Nice. You can uh avoid this issue of like uh I can only make 2 to the 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 to the 32, uh you need to keep in mind that that is like the number that the NIST standard mentions for the probability going above one in four billion. So it's not like I encrypt uh four billion times and uh here's the key. It's I encrypt four billion times and there's a one in four billion chance that I can recover the key. You need to go like two to the 48 or something to get an actual like decent chance as an attacker to uh to like actually do something with it. Uh there's like sort of two reasons to still care about it at least a little bit. One is compliance. Like 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 BigQuery the other day. And like if there is a if there is anything where you can exploit this, then 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, it's not really like I'm not too worried about this being actually exploited uh for the most part. It's like I think the the biggest uh worry that I have really is like uh uh compliance and best practices and security posture. You should just you should keep an eye off on that.
SPEAKER_01The documentation for GCM and Libsodium has a like a snarky warning at the top saying, you know, GCM is super popular, but it sucks, don't use it, right? But like the their their approach to this, the whole problem here is it's it's similar to how they handle keys, right? It's like the interface takes a nonce if it's uh a fixed size, and it's like have fun. It's not it's it's it's a it's a long-standing like Knackle and uh sodium criticism is like it defers nonces to it's like the one thing that is gonna break up and uh break you know blow up in these systems is use user-specified.
SPEAKER_00I I should know this off the top of my head, but like remind me of the tank API for ADs that have uh an encrypt and a decrypt function, and it will just not take a nonce. It will only use uh random nonces, and it will then just uh like the ciphertext format is like nonce followed by ciphertext followed by by tag. And uh that way you just completely circumvent that problem because users never can specify a nonce. What we have is something called deterministic AEAD, which some people uh don't know about that primitive existing uh at all sometimes. You there is some research on how you can do deterministic authenticated encryption. Like there is uh um the whole like uh uh things about like nonce reuse resistant uh crypto uh or encryption and like uh the various SIV modes where AES, GCM, SIV, I wouldn't reuse the nonce too much because it's still GCM under the wood uh in the end or similar to GCM. But like there is um AES uh SIV uh CMAC, I think it's called, where um funnily enough, what you need to do is uh you need to do a MAC then encrypt instead of the the other way around. But uh you compute the CMAC of your plaintext, use that CMAC as an IV, and then uh use that IV with a different key in CTR mode. And then when you decrypt, you decrypt in CTR mode, recompute that uh CMAC, see if it is equivalent 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 the caller. Um and because CTR mode is like constant time and will never fail, it can decrypt any string that you give it, uh that is secure because you you don't have any kind of operation on untrusted data that actually depends on the plaintext in any way. It's just XORing with something. And um like Tink separates out the deterministic uh AED from the non-deterministic AEADs, and we try to get people to use the non-deterministic ones, and like it's like called AAD and not uh uh anything more complicated. But sometimes you need to have something deterministic, and in those cases, that mode is very much feasible and very robust against any of like uh uh nonce we use, 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 Macs it with like uh CMAC which acts as a PRF uh uh for the IV. And that means that uh uh 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. Hey. It is it is homomorphic.
SPEAKER_03You map the plaintext and you're using that as your IV. So how is this secure against a chosen plain text attack? I'm probably missing it.
SPEAKER_00You need to have a different game. It's not an AED anymore.
SPEAKER_03I see. Okay.
SPEAKER_00So so the game that you play, like the the other uh the other name that you can call it is uh pseudo rand random injection. Okay. Um where the like uh pseudo random function uh standard uh 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 set, so I can still tell whether or not this was a valid plain text. But I have the same uh uh property of like the uh PRF oracle description that like I'm not allowed to ask for the same plain text twice, or like I'm expected that I get the same pla uh ciphertext when I uh ask for the same plain text twice. And that is how you uh define uh the properties for data ministic AAD. 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 an AEAD.
SPEAKER_03With a classic AAD, yeah. Okay, cool. Thank you.
SPEAKER_01This is like this is a thing Colin McCarthy talks about a lot. Like if you bring up SIV with him on Twitter, you'll get a you'll get a long thread about how like there are applications where deterministic AEADs are problematic because of message correlation.
SPEAKER_00Because like, definitely deterministic 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 is if I like take uh 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 uh at least there. So uh um SIV has its place, but it shouldn't be your go-to when you want to encrypt something.
SPEAKER_01You have in the Tink API, there's also you have ex cha-cha. So like my feeling, and again, I'm mad 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 non-size or whatever, like the two kind of standard answers in modern cryptography for that problem are deterministic AEADs, and GCM Civ is the big one that people talk about. And then X Chacha is the other one, where the solution 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 kind of like because it's really simple to reason about. How do you feel about that argument that like uh you know non-space use resistance is maybe a little bit of a blind?
SPEAKER_00Which like kind of limits all of the these non 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 uh use cases are slightly different. Like the question is do you have something that can act as a non? Maybe as a low quality nonce, but can act as a nonce. Like something like a timestamp is a perfectly reasonable, very low quality nonce. Like, yeah, there will be collisions, but there shouldn't be too many collisions. Or do you just not have anything of that sort? And I think that definitely the exchange methodology is like the best way of dealing with that problem. The main reason why we have both in there is performance uh related. Like when you care a lot about uh the non space being exhausted, you're likely having making a lot of queries. So uh uh the difference between GCM SIV and XCH20 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 AESGCMSIV can use all of that nice polynomial uh average metric over over characteristic two tricks to to speed things up, which XCH20 poly 1305 doesn't have or uh uh uh it uses AES and has hardware support for that. So it is uh XH20 poly 1305 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 the the AES part and the carry-less multiplication part, then AES GCMSIV is quite a bit faster. And uh so if you are in a situation where you really care about this non-space, you probably want to use C and you probably want to use uh GCMSIV. Or or Rust, I guess. But um have much Rust, unfortunately.
SPEAKER_03Yeah, it was in my brain, it was ASGCM 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.
SPEAKER_00And uh that is as far as I can tell, that is pretty accurate. And then you have uh anything CTR or CBC HMEC uh very, very far off the very slow end because HMEC is very slow.
SPEAKER_01Is Tink the first like thing you did at Google for cryptography?
SPEAKER_00Like, how did you get from algebraic geometry to where you're because it is uh not as all straight? So I finished my PhD when 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 hearts that that like 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 that team for four years and uh was then like I'm kinda uh uh uh looking for something else. Like uh you can't do searches forever. It's uh uh I got too bored with that. And I was looking at several different teams, and then I ran into Thai on that search, and Ty was like, wait, you you have you know algebraic geometry? Why aren't you doing crypto? You know this 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 um 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 why like uh I compute an Euler totion 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 path 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 Ulm in Germany was uh not the right place, at least for me at that time.
SPEAKER_03I had no idea you worked on search or ads or anything. That's awesome. Oh, yeah.
SPEAKER_01So so Thai, who you're talking about, this is Tai Duan, 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 at are you like a different kind of cryptographer for being in contact with the people?
SPEAKER_00Definitely like 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 you're like sometimes that uh sometimes I'm like incapable of like imagining that a key would not be uh containing the parameter set. Because it'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 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 unknowns, 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.
SPEAKER_01I I have a I have a dumb question, right? So like um in kind of the same vein, because when I think about the way Ty thinks about cryptography, it's very he's he comes from vulnerability research too. Um I have kind of a mental this is a total aside, but I've 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 and 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 Taidewan, and then you get to like all of the modern TL has attacks through the work that he did. Like, I I don't know that like the tendrils of of that Trevor Perrin guy are bananas. You um you twit somebody asked you how you got to however many followers you have on Twit. I don't know how many followers you have on Twitter, but your answer was that you dropped a Vuln to get back to it. What was the Vol?
SPEAKER_00To the conversation. The Vuln was uh really funny. What happened was that someone uh imported uh some AWS SDK 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 came uh uh SDK. And 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 wrong uh of like uh uh having the parameters that's stored with uh with the ciphertext uh as metadata in the bucket uh instead of having it stored um uh uh with the key material or or otherwise authenticated. Um and uh uh it was uh that was uh the biggest uh one and like I uh it supported both CBC without an HMAC and um GCM mode, and GCM mode was the default. Um but CBC was in there um 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 wide access to a bucket uh that uh uh has these encrypted uh files in it, you could change the algorithm from GCM to CBC, and then you can do a padding oracle attack on the CBC uh that like requires the entire 16 bytes of plain text to be guessed. It's not the most feasible attack in most cases, but it's definitely uh 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 uh AWS uh vulnerability and that like people like that uh it's like uh uh 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 and 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.
SPEAKER_03Why is there MD5 in here?
SPEAKER_00The MD5 was an uh was another part of the vulnerability, unfortunately, because there was um the the cloud buckets have these e-tags that are like uh uh used as um as integrity checks. Um and what it did was this client uh computed the MD5 of the plain text um and encrypted uh the plain 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 plain text uh for a cryptographer is the same as the plain text. So congratulations, you just revealed the plain text. And uh like yeah, it was all in all, it wasn't the biggest uh vulnerabilities per se, but they were kind of cool vulnerabilities, and so people enjoyed that.
SPEAKER_03I love that it got fixed.
SPEAKER_00Yes, 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 uh uh were very happy that they they could fix that. And um yeah, it it definitely got fixed and uh was nicely is is working very nicely now.
SPEAKER_03Awesome. What what's happening on in Sophie Land that's not just all tink in keys all the time?
SPEAKER_00Um uh Isogenies, yeah. Isogenies. We can believe they're gonna make this isogenies of like I've been trying to find a way of uh selecting uh a random supersingular curve, which is an extremely hard problem. Yes, it is.
SPEAKER_03And I was gonna be like, have you solved this?
SPEAKER_00No, I have I'm 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 uh I think there's an argument to be made that it's not possible to select a random supersingular curve without revealing the or without learning the endomorphism ring. Um which is sad, like it's it is it's isogeny is the closest that we have to this paradise that are elliptic curve groups for cryptography. And they're just nowhere near uh like they they're nowhere near as good as uh what elliptic curve groups can group structure can do, but yeah. At least they are they are a different variant, so that's good.
SPEAKER_03Uh what do you think of the the class group actions versus the super singular walks? Uh the SIDH style.
SPEAKER_00I've looked a lot more at the super singular walks than I've looked at the class group action. The class group action, it definitely seems to have a lot of promise. Uh I'm a bit concerned that it has like these abelian things happening. Yeah. Because it feels to me, intuition-wise at least, that quantum computers are bad at anything non-abelian uh non- non-abelian.
SPEAKER_04Yeah.
SPEAKER_00And doing something abelian feels kind of scary. Yeah. 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 uh when you read like class group algorithms, where it just says, and now we compute the discrete logarithm towards the spaces. And you're 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 like maybe 10 bits at most.
SPEAKER_03Yeah, I mostly am just sort of aware of like SADH and everything related to it is like, oh, we were too conservative. We can reduce our sizes because we were too conservative, and the it like everyone was worried about these uh these uh auxiliary torsion points being uh 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. They're just like, ha ha ha ha ha ha, it's a lot of hedging.
SPEAKER_00Yeah, yeah, that'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 talked to my PhD advisors and they've never heard about uh the fact that people want to do cryptography with that stuff. And they 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 with isogenies, 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 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. I'm 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, it's much, much harder to to teach um and to understand. Uh but it's like it has clearly shown that it's superior to RSA in almost all ways. And I would be very unsurprised if we see the same thing 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 switch to isogenies because we made them more we made them faster, they are smaller, uh, and so on. Like same things that happen with elliptic curves.
SPEAKER_03Yeah. I I like that kind of pattern match because I that does feel very there's all there's a ton of stuff you can do with lattices that we probably will never be able to do efficiently with isogeny stuff, like the fully homomorphic encryption and 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 codes, the code stuff goes back so much even further. But then when we learn the 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.
SPEAKER_00Yeah, yeah. But I definitely think right now I can't see uh uh Mist or or anyone like going this isogeny and being like, oh yeah, we totally trust this. Yes. It's it's cool, and I want it to be the one that wins out in the end, but it's not there yet.
SPEAKER_03Yeah, 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 we never mentioned it before.
SPEAKER_02Wasn't uh almost nobody even like using elliptic curves at all until Wiles showed up and was like, hey, I've proved uh Firma's last theorem. Something like that. Because it was the mid-90s.
SPEAKER_00Definitely made algebraic geometry 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 Jacobi and Abel 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 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 Wiles and Klamazla's 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 in algebraic geometry instead of just being like, oh yeah, we conjecture this, um and uh uh uh things like that, and like the the algebraic number series. Uh like basically Groten-Dieck 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 uh the the most well researched uh uh for cryptography there.
SPEAKER_03Yeah, it's it's so new. Um Sophie, thank you so much. I'm so glad you could join us. This is great.
SPEAKER_02One last hard take. Is anyone ever gonna prove or disprove the Riemann hypothesis?
SPEAKER_00Uh let me see. There has been some uh 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 st uh studying uh this. Uh none of them asymptotically ever moved beyond the uh uh Z the real part of Z is equal to one line. Like they they have like proved the Riemann hypothesis for like sort of curvy bits, but they all asymptotically go to the uh real part uh 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 any P uh than P equals NP, I think.
SPEAKER_03I hope so. I hope so. We're all screwed.
SPEAKER_00I mean I hope nobody proves P equals NP, but uh even P unequals NP seems to be uh like one of the the things that it's very hard to get any traction on.
SPEAKER_03Spicy hot take. No one's ever gonna prove it. Cool.
SPEAKER_00I mean maybe it's maybe it's not provable. Like there is there's a bunch of uh things that we've shown that they are undecidable.
SPEAKER_03Yeah. Sophie Schmieg, thank you so much for joining us.