Hybrid Key Establishment in Production: Post-Quantum Cryptography

[00:00:09]Okay, let's start our session.

[00:00:14]Afternoon. U welcome to the very first schedule of KPI workshop. I'm Sing Kim from Sunshine Master University and thank you for attending our session. So this session would be proceeded with online presentation.

[00:00:28]So and uh it is great honor to introduce our speaker uh Miss Dere Connelly. She's a senior step standardation research engineer in sandbox AQ. Before she joining sandbox AQ she was an engineer in Zach Brite Cove and Akami. So today she will be talking about recent trends and opportunities of hybrid quantum resistance cryptography. So please give a big round of applause for our speaker.

[00:01:08]>> Thank you so much for having me. Hi Dearra. Uh I as as uh my announcer uh mentioned uh I do cryptography and especially the past few years have been focusing on uh migrating uh deployed protocols especially open port protocols in the IETF uh to a quantum resilient posture or at least making those designs available. Uh so when we're looking to move our cryptography uh into a a quantum resilient uh future we have three big buckets. We have c generally key establishment stuff which I'll be talking about today. We have authentic authentication via signatures and a big bucket of fancy crypto. Um but today I'm mostly focusing on key establishment.

[00:01:49]This is where a lot of the activity is happening uh around the world in trying to mitigate uh a live attack scenario uh for the traffic for the messages that we're trying to protect uh via encryption. uh especially encryption where you uh agree on a shared secret uh over an open channel uh and those things are generally uh rely on cryptographic assumptions and mathematical assumptions uh that we don't think are secure anymore uh when we have a large cryptographically relevant quantum computer uh in the hands of our possible adversaries. Um so that that's pretty much the big reason why we're talking about this sort of stuff is because we have a ton of cryptography deployed in the real world. Uh that depends on the security of Diffy Helman and we do not no longer have that assumption of uh Diffy Helman being strong either by elliptic curve cryptography uh or even finite for field cryptography and especially uh factoring uh numbers like in RSA. uh we do not have the assumption anymore that that is a secure thing to build cryptography on or or secure our communications or storage with because uh Shor's algorithm is a theoretically uh strong efficient attack against these schemes uh when we have a sufficiently large quantum computer to execute it. Uh so not these Diffies and Helmans, this Diffy and Helman. Uh we build this into so many of our protocols that we use uh today and we now have to find a different way to establish a shared secret based on public parameters uh and a little bit of secret secret data that we keep secret to ourselves uh to agree a shared secret with somebody else who we've not exchanged information with before over a public channel. So in the postquantum realm it looks like the best thing that we've got in our toolbox are chems which are key encapsulation mechanisms and I see in the program we have a lot of discussion about the newly uh adopted candidates for the KPPPC competition um which is really cool to see. So for for anyone unfamiliar uh a key encapsulation mechanism is a is a triplet of algorithms for a secure crypto scheme. We have key generation that produces a secret encapsulation key and a public uh encapsulation key. With the encapsulation key, you can run the encapsulation algorithm and that will spit out a cipher text and it'll spit out the shared secret. And usually you you hand that cipher text and that decapsulation key to the decapsulation algorithm and it will also spit out the same shared secret. And so now you and your your other party can start using that shared secret to derive session and uh encryption keys or other uh keys for other uh other use cases uh based on a shared secret value that's uh considered hard to break because of different cryptographic assumptions uh based on things like lises or other uh assumptions that are considered resilient to an attacker with a large quantum computer uh that can run things like shor's algorithm. So when we talk about chems being uh secure, we we are talking about uh chems that are secure uh against an indistinguishable under chosen cipher text attack. Um this is similar to the uh CC in CCA2 uh game that is relevant in public key encryption schemes, but for chems because of reasons it's generally just in CCA. And this is kind of the scenario where we have an adversary that's able to throw whatever cipher text it wants at a decapsulation oracle uh and try to distinguish between what is getting spat out from the decapsulation as a shared secret and whether they can distinguish whether that's the real shared secret or random. Um and this is the thing that almost all of the chems that are being uh standardized, worked on and developed uh either in a purely postquantum way uh in a uh in a classical way. I wish I had time to talk about some of the classical chems but I just did not have time to fit it in uh and if we want to do it in a hybrid postquantum traditional way in CCA is the security standard of is this a cryptographically secure cam. Uh so about two years ago uh in the United States, NIST uh not didn't conclude but came to a a significant milestone of its postquantum cryptography competition uh by picking uh the first chem that that was previously called Kyber and eventually became standardized as the document FIPS 203 and called MLAM. But I'll get into the differences between them in a second. And then a couple of weeks ago they announced their kind of like uh alternative backup chem because they had announced when they selected uh uh Kyber to become moam that they were going to continue with like a fourth round uh to because they wanted something that was not based on lattises and they wanted to see if they could get something that was possibly smaller, possibly faster. Um and they selected HQC uh as the the upcoming fourth round selection. So when the when Kyber was announced um a lot of work started happening about uh trying to integrate these in a kind of provisional sense into protocols and how one would use them uh to take a existing protocols uh and start in making them in a quantum resilient uh fashion. Um, and when MLKM landed as the final FIPS 203 standard in August of last year, in August of 2024, it was like a shotgun went off, a starting gun went off, and everyone was off to the races. Previously, I was working in the IATF, and previously people were hesitant about getting PQ adoption and documents uh, ready to go.

[00:07:36]They were a bit hesitant. And as soon as it became a US federal standard, people all over the world, not just in the United States, were like, "Oh, now we really actually have to get moving on uh PQ adoption, especially for uh protecting key agreement uh in in the you know, kind of over a public channel.

[00:07:54]Uh so Crystal's Kyber, the last version that was submitted to to NIST uh looks a little bit like this. I'm just going to do some overview because it'll be come in handy come in handy later. So for keygen uh we generate a 32- byt random seed. Uh we do the pk key genen. Um, as I kind of mentioned, you kind of take a you take public key encryption that's usually randomized and you dandrandomize it, make it deterministic, and then uh you kind of wrap it up in this FO transform, Fujisaki Okamoto transform uh to to to take that deterministic chem and encryption public key encryption scheme and make it into a chem, a key encapsulation scheme. Um, and so that's a little bit of what's going on here. We're prepping the keys for that. So we do the key gen for the PKE part. We take that 32 byt seed, stick it with the the the the encryption key and decryption key uh for the public key encryption scheme and the hash of the public key and that is your whole decapsulation key for Kyber and then you spit that out with the actual public key encryption scheme and that seed that 32 byt seed is the fo transform rejection value and that will be used in decapsulation here. So for Kyberv3 decapsulation, we parse out our keys. We are given a cipher text that may be attacker controlled uh and we parse out our secret encapsulation key. Uh we do our public key decryption of that cipher text and have a possible uh random message seed. um we hash or you know put through a KDF uh that seed and the concatenation of the public key the hash of the public key uh the hash of the the whole chem public key in actuality um and we get the kind of uh proto like the primordial uh shared secret it's not the actual shared secret but it'll be used later and our prime which is like the the randomized seed uh the the secret randomness not secret this the randomness that you use to take to give to that PKE that public key encryption scheme to take it from randomized to deterministic that's that randomness and then you recomputee the cipher text and recomputing the cipher text so you can compare it to what you should have been computing to encrypt under this public encapsulation key using this this randomness uh what you should have gotten if you were doing this honestly uh and compare it to what the possible adversary handed to you and if those cohhere if they agree Then you take the the kind of primordial uh uh um shared secret concatenate with the hash of the cipher text and then you put that through your KDF and return that as your actual chem shared secret. Uh and if it if those two cipher texts do not agree, uh you take that FO transform rejection value that 32 byt C concatenate that with the hash of the cipher text which is attack possibly attacker control because this is a inCCA secure chem right uh and return that and that that value is considered a nice thing to have from kind of um a practical security perspective of integrating these new these new in the world of a world of protocols expects things that are like diffy helman, you kind of always get a a general real value with diffy helman, right? Um, in the explicit um uh rejection form of a chem, you might output a symbol that's just like an error or panic if you implement this in a certain way in software. And that that generally you have to offload the decision of what to do with that value and what to do with that state uh to the programmer. And instead the implicit rejection uh trans uh lets you have a value that is pseudo random um that has some cryptographic value and you can use it. It's not like you're outputting zero um but you will not agree with someone on the other side. So you're kind of in a in a slightly better way uh of running your protocol in a slightly better setting than just literally throwing an error which can also be detected by a possible adversary. Um, and one thing I just want to point out is that you can see very explicitly in this design of Kyber V3 that when we're d uh deriving our shared secret, we are deriving it directly from the hash of the public key that we've encoded in our secret decapsulation key and directly from the cipher text that was handed to us as part of decapsulation. So when we're deriving our shared secret, we are very directly tying the cipher text that we're using to compute it and the public key that we're the the encapsulation key that we're using to compute it right in here and it's very clear to see and this can have very nice properties when you're trying to integrate it into protocols that I'll get into later. So as I mentioned, FIPS 203 landed and this is taking Kyber and moving it into MLEM.

[00:12:44]And I I have to remind people frequently Kyber and MLM are not interchangeable, interoperable cryptographic algorithms and cryptographic schemes, they have small differences. And one of the major differences here is that that cipher text that I mentioned, yes, we do our decryption and yes, we do this. But if you notice we no longer directly in compute over the cipher text when we're uh when we're outputting our shared secret. Now we are hashing we're including that hash of the public key the public encapsulation key but we're no longer also hashing in the hash of the uh of the cipher text anymore. We are kind of indirectly depending on it via the the security properties of the of the public key encryption scheme. So that's a key difference and one of the reasons that they did this is because one they were able to clean up the NCCA proof um by not including uh the hash of the cipher text into the computation.

[00:13:44]They had a tighter reduction and they had you know much tighter bounds and it you know it was much nicer to have a very a much cleaner NCAC in CCA proof uh uh of what became MOAM. Um, and that's the the goal, right? That's how you prove security of a scheme like this.

[00:14:01]And also, if you're not those cipher texts are at least a kilobyte, 1.5 kilobytes or more depending on your parameter set. And that's over a kilobyte of stuff. You're not hashing in anymore because the public keys are still you you cache the hash for the public key. In this case, you only do it once. um you know you you could theory in theory do it later but you you always had to hash in that cipher text live when you're doing decapsulation and in this design for ML cam you aren't um so those seem to be the and this is kind of discussed on the uh public uh pqc-form mailing list that is hosted by NIST who who runs the the whole kind of competition. Um so that's where those two diverged. I'm talking a lot about this because these are the key players of how a lot of the stuff uh uh of a lot of the protocols are moving to a postquantum uh position. Why aren't they just going directly to uh uh just replacing all their Diffy Helman uh with MLAM uh or or something like it? Um well you know uh for mitigating the attack scenario that we care about for key agreement and key establishment um that threat is the you know store now decrypt later attack or also known as harvest now decrypt later um which is basically live now anyone can can capture the public traffic going across a public uh connection including TLS handshakes secure uh encrypted messaging handshakes and sessions setups and other things.

[00:15:35]And they can take all of that and store it. And when they have their sufficiently large efficient quantum computer uh ready to go, they can rifle through their their collection of uh you know, handshakes and cipher texts that have been protected by the computations under those handshakes um and just go to town and say, "I I think that looks juicy to me." And go do go decrypt it.

[00:15:57]So things that we're doing right now and the cryptography that we've deployed right now and using it to do to try and protect traffic and messaging um is currently under threat because you can just store it and decrypt it at a later date. So the people that want to mitigate this threat right now are more motivated to move quickly even though these primitives are quite new and for a lot of people they don't understand them and they're a little bit unsure about them. Um, and we've already seen um, a couple of non-trivial vulnerability classes that have just sort of sprung up in reference implementations and many other rep uh, implementations of uh, MLCAM, especially uh, the the FIPS 203 standard. um that was like able to leak uh the the shared secret in general because of the way that you were computing over a not fully uh not fully public not fully uh uh uh vulnerable secret uh leaking data and like compression and things like that. Um so it's not just we're worried that I don't know structured lattises are weak and we'll find like someone will just you know crack it over the weekend on their laptop. Some people are worried about that because they just don't fundamentally understand this new um you know cryptographic assumptions and constructions but others it's just this is new software this is a new scheme and this is a kind of newer class of implementation um and just new stuff has new new risks that we're just we haven't you know bulletproofed it yet um and so there's a risk for that too. So to mitigate those kind of risks uh moving to a hybrid postquantum and classical uh construction in protocols and in primitives uh seems to be attractive to a lot of people and there's a lot of other um regulatory environments that actually are going to be requiring hybrid uh including several European governments. So, um, we're going to see a lot of different approaches to to, uh, moving to a po postquantum resilient posture, um, for a bunch of different reasons at the same time. And so, I'm going to get into some of those, but I also want to make one point. Um, we have a lot of experience now with elliptic curve cryptography, especially in production.

[00:18:14]Um, we have these very small, very cheap, computationally speaking, uh, primitives and we know how to do them very well. Um our current uh toolbox of PQ primitives are large. I mentioned one 1.5 even larger sizes for public key 1.5 kilobytes for public keys and cipher texts. Um they're also computationally cheap. Kyber uh sorry MLM is quite fast.

[00:18:38]In fact uh I think it's faster to compute decapsulations in keygen for MLM than for X2509 for example. um but they are large. If uh our um our PQ constructions were the same size as elliptic curves or smaller um I have a feeling we wouldn't be talking about hybrid, but they aren't. And so the fact that it's very cheap and computationally easy and cheap to staple these two things together um I think is a big factor into why people are like trying to uh hedge their bets and they're just like I'll just keep my my small cheap elliptic curves while I'm deploying this large and mostly computationally cheap uh lattice base cam. Um but so that's the world we're in. Okay. So let's look at some protocols. So TLS13 TLS13 was blessed with a beautiful protocol and key schedule that allowed us to do the simplest possible way of combining a postquantum chem and a classical key agreement like defy helmet like elliptic curve diffy helman which is you do your uh ephemeral the elliptic curve diffy helman with something like x2519 or you could also use the you know the p56 curve which is quite popular as well.

[00:19:57]Uh, and you have your ephemeral keys that have an ephemeral elliptic curve uh, point and you have your chem and you have an ephemeral public encapsulation key that you generate. You send those public values as a client to a server.

[00:20:13]The server responds by generating its ephemeral elliptic curve point um, and computing its shared secret from from the two of them together on its side.

[00:20:21]And then it takes that public uh uh encapsulation key uh computes an encapsulation to it. The cipher text sends that out and has it shared secret.

[00:20:30]So on the server side and then you know the the client gets the response and it's able to compute it side uh complete it side of the handshake shared secret concatenated with shared secret and then you just shove it back into the TLS13 key schedule exactly where you put just the plain old elliptic curve diffy helman shared secret and you're kind of done. Um this is this is a lovely efficient most computationally efficient. There is no extra overhead or extra operations or extra anything being done here. This is possible because TLS13 is already hashing everything in the uh transcript of the whole handshake protocol into its key schedule into uh all of these nested HKDFs extracts and derived secrets and all of that. It was already doing that for the client hello and that ephemeral uh key material and for the server hello and its responsive key material and the cipher text. All of that is getting hashed in automatically. Anyway, um so in secretly TLS13 is hashing in quote everything. It's hashing in the two shared secrets from the traditional elliptic curve side from LS13. It's It was It's lovely. This is being deployed right now. It's been integrated into Google Chrome and it's on by default across Chrome on all devices. I think it wasn't on on Android for a little bit because of performance issues and then they those resolved and they were able to turn them on. It's been deployed by Cloudflare. It's being integrated by Apple into it's how you're developing apps with uh CryptoKit. It's being deployed by AWS and it's a KMS system. It's getting deployed all over the place. Uh this is one of the fastest moving updates of uh moving to a postquantum posture uh in a protocol that I am aware of. Um it's also now the default most prioritized key agreement in OpenSSL in its latest latest version.

[00:22:50]So, uh, speaking of Apple, Apple updated iMessage, and they updated it in a major update that they called PQ3.

[00:22:59]And this was, uh, their major update to make, uh, iMessage, uh, quantum resilient, but also it included a lot of updates to the messaging protocol in general that were kind of, uh, well overdue. Uh, and this included ratcheting. So this message also included uh better forwards and post compromise security uh in your uh encrypted iMessage chats than before. Um but the important thing I wanted to to note here is how whoops uh how it computes its how it does its KDF over its session setup information. So when you're trying to set up uh for those who might be familiar with signal um uh similar to the long existing versions of signal uh iMessage PQ3 has uh these long lived identity keys um which are kind of identified here ID ECBK and things like that for the sender and the receiver. Um we also include like ID like numbers, labels and a label for what this uh this computation is going to be in its key schedule. It also includes these kind of prekey things. So when you want to create a new encrypted chat with uh an async chat with someone who might not be online, um what you want to do is have these you have the long lived identity keys that you kind of those are like the root of your identity. Um but you also want to have the ephemeral part, the kind of like freshly ephemeral part to start up the the new encrypted session with. Um but if your partner is not always online, um what do you do? Well, what you do is you premputee the ephemeral things and you sign them with your, you know, authentication key, which is usually like a permutation of your ID key and you cache them up on the server. Um, so you trust the server to just be an honest fetcher and broker of that sort of information. Um, and so you pre-cache these prekeys on the server.

[00:24:50]So for uh Apple's um update to iMessage, uh they had already I actually don't remember if they already had the elliptic curve prekeys, but you have these elliptic curve prekeys for the sender and the receiver. And now you have these postquantum prekeys over here for the receiver. And then uh the the person who is sending the message fetches down the postquantum uh encapsulation key prekey. and then they encapsulate to it. So when you're computing the whole new session setup, you have the the receivers's prekey and you have the cipher text that the sender computes for encapsulating to them. This is the kind of public transcript of this session getting smooshed down into uh into this like additional information that's going to get stuck into the KDF.

[00:25:42]And then we call this KDF. And so we have the kind of public data and that goes into ps down here. And we've got the elliptic curve shared secret and the postquantum shared secret that spat out of that. And if you look in here, this is a this is an interesting variant of how to do a nice KDF. This is like a split key split key KDF version with multiple uh HKDF extracts extracts and then your expand. Um but I think I've already gave it away, but you can kind of see um iMessage PQ3 also just hashes in everything. So we've got all the public stuff and we've got the shared secrets and we go through our trusted KDF that has you know the way we want to formulate our KDF but everything public to set up the session uh that everyone can see that is used to compute the shared secret uh goes into the KDF.

[00:26:34]Okay, we talked about signal. Now let's get into signal. So signal also went to update to a postquantum hybrid update.

[00:26:44]Uh this included a very similar thing to what I mentioned with iMessage where the ID keys that they have uh they're a slightly different variety than the iMessage ones but um those are still just elliptic curve based but they updated their existing elliptic curve prekeys with these new kyber based uh or at least in the in the first version they're kyber um postquantum prekeys as well and both both sides have them of course. Um so when um when we're doing a session setup um we have our pre-signed uh prekey keys up on the server. We do the triple diffy helman. So we have a trip uh diffy helman one two three some of them involve the ephemeral key the signed prekey and the ID key and vice versa. And then we do uh like the ephemeral prekey and the ephemeral prekey and that's the third helman. And then we have our chem encapsulation. So that's our cipher text and our shared secret. And we include the shared secret. And I will point out here the KDF is just shared secret concated with shared secret concat with shared secret concatained with the postquantum shared secret. And then we have our additional data which is concing the uh sender ID public key and the receiver ID public key.

[00:28:06]And that's it. And those are both elliptic curve based. And that is included as the additional data for uh encrypting under you know authenticated encryption with additional data uh cipher. So uh I'll I I won't bellay blay the uh the lead. Signals first version of its postquantum update just hashed in the shared secrets and was lacking a lot of the public uh context of the protocol from actually getting tied in to um the KDF. And it kind of makes sense because this is one of those tension points of when you're making updates to an existing protocol where you have a lot of robust security proofs about existing things that you care about. Um, and you don't want to diverge too much, but they're including a new primitive with different security properties than Diffy Helman. and Diffy Helman kind of included some other stuff that a straightup cam when you're just relying on in CCA as the thing that you need from it did not. Um so this got this opened up this first version of signal PQXCH2 reenccapsulation attacks. Um, and just to go in here, basically if an adversary compromised one of those uh pre uh postquantum prekey key pairs, one of them, and got access to the secret key and was able to kind of man in the middle here, um, they're able to decapsulate that shared secret from one, you know, chem cipher text and then re-encapsulate it uh under new people to, you know, the other party's public key uh or whatever. So that um say for in this example we have Alex thinks that he's computing a a new session with Blake, but he's actually computing the same session shared secret with this adversary Charlie in the middle. And so we we have this attack on session independence. Um and uh we have this like key uh key this impersonation attack. um and that this is, you know, a a fundamental uh uh protocol violation that we didn't think was happening. Um this is completely allowed and valid under NCCA.

[00:30:32]This is like totally in scope of an NCCA adversary. um the first version uh of this protocol update from signal um they wrote down in the specification um and have a in CCA cam blah blah blah blah blah um and it just turns out that that is not enough to protect against this kind of attack um the compromise of a single uh postquantum public key in fact enables an attacker to compromise all future cam shared secret of the responder um even after the responder deletes their compromised postquantum public key because you were able to get one of them and you're able to reenccapsulate it under another one. Um, yeah. So it basically implies that there is more that we need to care about about our chems that we're slotting into protocols such as such as protocols that were designed specifically around Diffy Helman and these sort of kind of implied guarantees that we get from Diffy Helman um that we don't get from a purely in CCA account. Um so the reason we care about this is because not every protocol like TLS13 or P postquantum iMessage uh can just hash everything into their their key schedule or into their protocol KDF. Um for one some of those protocols just might not be in the the kind of environment that can afford that or they might not be in a kind of a compute device environment that can afford that. Um, I've been trying to look at these IoT protocols um that can't afford a lot of that stuff. Um, but also we want to be able to use these chems in a way that like we don't have to hash everything in all the time um to wield them. We want to know more about them so that we can decide what we need to include as opposed to including everything just because that's the only way to cover your butt. Um because some of these chems are again quite large like kilobytes of data that needs to be included into these case schedules and that's not including some of the much larger one which are multiple multiple kilobytes or or even larger. Um so this is where we kind of get into uh more notions beyond in CCA for chems these binding properties that came out. This is sort of the kind of like a spurring paper not the only paper um from Kramer's DAX and and Miger about the binding properties of chems. And so really quickly, this is kind of the the general security game of a lot of the binding properties we care about, which is a uh these are collision resistant properties. And the ones that we care the most about is basically I'm going fast because I I don't want to run out of time. Um, when we have a shared secret, is it hard to find a collision between cipher texts, public encapsulation keys, or combinations uh or of those things um to result in the same value of a shared secret? And we find that those are kind of the the most salient for when we're integrating cams into into higher level protocols. there's like a whole zoo of other kinds of combinations uh of of uh these binding properties. Um and one of the things that we have three different general attacker models um that we're trying to protect against uh an honest adversary who doesn't have access, he just sees everything public and he acts normally. um a leak adversary that can have access to honestly generated key material or a malicious adversary that has access to honestly generated key material and can manipulate key material uh including secret key material. And basically these properties can also hold independent of NCCA. So like you might have a chem construction uh that has a good binding property uh but you might have a bug in um in your implementation and your inca may break down and we've seen that um I might have been in HQC uh that got fixed um actually I'm not I'm not sure about that. I think it was the reference implementation of the submission um and it got fixed um but this can hold up even independent of that. So it's kind of like a nice layer uh uh that you can have independent of NCCA. Um we it looks like um a leak bind KPK CAM slotted in where the MCCA cam is into the first version of signals PQXCH uh protects against that key encap key encapsulation attack and that um uh session independence uh uh falling down.

[00:35:25]So um the specification only specified an inca chem but in their implementation they used kyber and they use kyber v3 and then um I think they've cued up ml cam now and I don't remember if they've actually deployed it with mlcam or not um and so the the analysis by crispen of signals pq xdh um seems to show that a variant of this collision resistance does ina in fact uh protect against this kind of attack. So um and I I'll skip through this because I'm running out of time. Um so when you have kyber though that's one thing and because that is hashing in it cipher text mlch doesn't hash in cipher text. Does this have any implications?

[00:36:16]Um so I'm going to go quickly through ML Chem's binding properties because it directly hashes in that public key or the hash of a hash of the public key that should be um uh controlled by the decapsulator. Um it has strong binding properties on the public key. Uh we have to revisit this in terms of seeds. Um but it's not directly binding this the cipher tax. We do have a proof that uh we have cy like cipher tax collision resistance. um uh especially against a leak adversary. And we have the another property that I'll get to later that's uh pre-image resistance that or second pre-image resistance for the cipher text which comes in very handy. Um putting all these things together, it does seem like MLM slotted into that first version of signal pqc pqx uh prevents that reenapsulation attack.

[00:37:09]Um but you know what they actually did and what was recommended by the the reviewers is include that public that postquantum public key into the additional data. Um then you don't have to worry about all these extra properties and stuff like that. It's not quite hashing everything in the way what we saw on TLS13 uh and PQIM message. Um but it gets it closes that attack vector. Um but this is like a lot of work just to uh and like this this does hold for these particular chems Kyber ML chem um it's it does classic mic does not meet this threshold for these uh you know the specific variance of collision resistance for these binding properties to slot into that part and it's unclear for bike and A2C. I think there's updated analysis to answer that question but I I wasn't able to confirm it. Um, this is a lot of work to try to figure out how to integrate these chems into your existing protocol. Um, because you can't just rely on the NCCAS.

[00:38:16]What else can we do? So, okay, that's at the protocol level and trying to get something nice for your protocol, but we can also just shove all this decision- making into the primitive itself and make a hybrid CAM. So, um, yes, it's it's an NCCA chem that slots into a place where a chem is already expected.

[00:38:36]That includes protocols like hybrid public key encryption, different kind of hybrid um that's being used directly in the new uh encrypted client hello update in TS13 that's getting deployed uh and is becoming an RFC any day now. Um, it's a key dependency in the the new messaging layer security protocol. uh it abstracts some of this decision makingaking and thinking about it away a bit, but you might lose a little bit of the efficiency and might be doing extra work than if you were doing if you had like a finely tuned custom protocol uh like you can kind of get with TLS13 uh or some of the others. Um so I wanted to talk about X-Wing. X-Wing is an example of one of these hybrid. It's a concrete construction um based on a generic framework that we laid out in the paper and it's based on MLCM 768 and X25519.

[00:39:28]And the thing I want to point out here is that we have kind of similar to oops I'm sorry our prior constructions. We have our uh uh postquantum shared secret concatenated with a label and our uh elliptic curve shared secret and the elliptic curve kind of ephemeral public key and the elliptic curve uh long-term public key and we shove all that through our KDF which is shot 356. Um and we're able to do that because we were able to show kind of this other flavor of binding property specifically uh it's this uh cipher text second pre-image resistance. So the binding properties I talked about were collision resistance.

[00:40:07]This cipher tech second pre-image resistant was sufficient to show that if we have a chem with that property, we can prove in CCAS uh in the standard model and we're able to prove in CCA incess and the in the random model um based on the properties of the KDF as a random and the the strength of the elliptic curve group um when you know so that if the the postquantum bit just completely falls apart we still and we still believe in the uh security of elliptic curves. We still have a strong uh in CCAM on that side. Um it does look this allowed us to exclude the large cipher text kind of what we saw earlier but also the large public key from hashing this in um to make things a lot more efficient. Um similar work that's happening out there is influenced by X-wing but also uh this is the the work in the ITF and the crypto forum research group. This includes the generic framework that uh supports X-wing but also this sort of hash everything in variant. Uh it includes all the the the traditional the public the postquantum and all of the public stuff in one uh h one hash one uh uh hybrid cam and also an optimization of that design uh but with you prehashing the public encapsulation keys which can be large.

[00:41:28]So you can do that hash once and cache that information which is an optimization. Um that is becoming adopted in other IETF documents. We're also seeing uh another composite cam design uh coming from NIST. It's very similar to that GHP style and that's we we're trying to align them on purpose um and other stuff in the IATF trying to um align on these composite chems especially when using them in a certificate because that might also be a way to authenticate uh using chems and using hybrid chems. Um so one nice thing about X-Wing is that's showing a lot of popular adoption. It's being adopted and rolled out by Apple for its latest version of CryptoKit. It's being used in HPKE. It's been implemented uh in boring SSL from Google and we think that they are using it for their deployment of encrypted client hello and it's being uh supported in MLS in the IATF. Uh several of those other hybrid chems from CFRG are also getting supported in MLS in general HBK use if you want to use it.

[00:42:28]There's other uh encryption schemes um in the IATF that use that. Um and we've seen a lot of interest from designers who are trying to integrate or move to postquantum in sort of HSM designs and open compute designs. Um so this is kind of like a survey of like the various ways that people are trying to move into a hybrid postquantum posture. We've got all these protocol updates that are kind of bespoke but kind of hard to do really well. Uh and now we've got these hybrid chems that people are trying to slot in um in different protocols and different ways. It might be slightly less efficient, but they have a lot less to think about if they kind of, you know, people does it do all the work for them, wrap it up in a hybrid cam, and if they're fine with that, they can just deploy that really nicely. um if that works for them. There's going to be multiple ways that we can go hybrid both in the the component algorithms we're going to deploy where in the stack that you're actually going to integrate it and even amongst the different places in the stack there's multiple ways to do it like these different designs for hybrid cams and for for a long time in the future I think it's going to be a long long time until when we are in a fully postquantum future with no uh traditional broken uh you know vulnerable to shores algorithm stuff uh for a long time. Um, and that's not even looking at uh the authentication piece with signatures and things like that.

[00:43:52]Um, there's going to be a a lot of different stuff that's hybrid postquantum all over the place for a long time. Um, if you think this is confusing and a little bit messy, talk to your local cryptographer about whether going directly to PQ is the right solution for you and maybe you can avoid some of that mess. Thank you. I'm open to questions.

[00:44:21]Thank you for your invaluable talk. Do you have any questions?

[00:44:33]>> Oh, so uh I have a question. So this question might not directly relevant to your talk but I saw some rust code in your slide for example ROS TLS. So I uh do you en envision the adoption of Rust language while implementing some cryptographic uh uh protocols or primitives would be accelerate accelerated and also what are what are the implications of implementing some cryptographic encryption uh protocols or primitives using Rust beyond the memory safety guaranteed by the Rust itself.

[00:45:26]>> Sure. Um I'm a big fan of Rust. Um I've implemented uh I've implemented MLM and Rust and some other postquantum schemes.

[00:45:35]Um I'm a big fan because beyond the memory safety which is very nice for complex protocols like say TLS or some of these other complicated protocols uh the safety that gives you the strong typing and lowcost abstraction that Rust gives you is very very nice for abstracting out your uh your types like your different key materials your different kinds of cipher text for chems um so that it is practically impossible for when you're using an implementation that's abstracted in such a way uh to confuse uh the public cipher text that got handed to you by an adversary and the recomputed cipher text that you have done yourself. It may be influenced by attacker control data uh and needs to be treated in a different way by uh computing over it than you would from the uh fully public one. uh this is directly related to kyber slash and I've I've updated my own code to specifically be like um you cannot compute over this uh in a secret dependent way which would result in side channels and for this cipher text you can this is a thing that is just cheap and easy to do at a performance level and like a software engineering level in rust um that you kind of learn the hard way and you have to kind of eat the cost depending on another programming language language.

[00:46:59]Um I I think I think that's great and um I really love using Rust for cryptography because of because of the the the the capabilities like that uh far beyond the memory safety.

[00:47:11]>> I see.

[00:47:12]>> So another question please.

[00:47:20]>> Yes, this is Nari. Um I have two questions. Uh first um I think there can be similar concerns um in the context of a hybrid signatures. Uh so do you think the concept of uh C2PRI used in chem combiners? Um maybe can it be meaningfully extended to signature schemes as well or would you argue that um a completely different approach is needed for signatures?

[00:47:57]Signatures are kind of tough because it's a the way you integrate them in into your protocol is is like a binary.

[00:48:05]You're one of the nice things that's allowed people to move quickly with adoption of key establishment uh of these cams into protocols is like if you compute the wrong especially these implicit rejection cams is if you compute the wrong thing or you get the rejection value out of it the parties don't agree to a shared secret and they just cannot compute and you can detect it. Signatures are did you validate it and did it validate or not. It's one you have to do it and just did it validate or not and then to continue your large protocol you just have to stop uh and like it does not flow its value into the rest of the protocol. And there's some there's some nice work being done about oh I don't I don't have the name off the top of my head of like trying to output values beyond just it verified or not um that you can use to integrated into your key schedule to change the value of what you agree on to detect this sort of thing. If we had those sort of signature or authentication primitive constructions, I would be looking closely at binding properties or, you know, second pre-image resistant properties. But because they have this fundamentally different like way that you work with the primitive, um it doesn't quite it they don't quite compute. Um there's a document in uh the the IETF that I'm a co-author on that's literally um how you do hybrid signatures and there's a spectrum of separability um that seems to be a a key property about how to do hybrid signatures and like the spectrum from like it's very easy to strip off one of the component signatures to it's a you blow up the signature scheme and wrap it up with you know postquantum and and traditional assumptions and wrap it all up. So, it's a very tightly bound signature scheme uh and practically it's strongly non-separable. So, because of the way that signatures are and that we're used to using them, and I have a feeling that's not going away anytime soon, um it's less uh collision resistance or or pre-image resistance and more these uh separability properties and e and those are kind of they're just a little bit squishier than like here is the game uh for for for binding or uh cypher tech second pre-image resistance. Um so I I I welcome more research on that. Um it may be difficult.

[00:50:37]>> Thank you for your answer. My second question is just my personal curiosity uh about the hybrid cam. Um I wonder why you named it as Xwing. Maybe anyone of Yeah. your um the co-authors um is Star Wars Mania, you know. I don't know. So >> yes. uh uh I'm pretty sure I can I can uh attribute this to to one of the co the co-authors Peter Schuave. Um he has names he is also a co-author of Kyber uh and the the related uh signature scheme Dithium um those are also um uh big Star Wars things. Uh, I'm pretty sure he was the one that came up with the name X-Wing. And I think he uh, if you notice in the diagram, the label is kind of this like forward slashord slash dot, you know, whatever. If you line that up, it's like asky art for an actual X-wing starf fighter.

[00:51:39]Um, yeah, we we've got a bunch of Star Wars nerds in our group.

[00:51:45]>> Thank you for your answer.

[00:51:47]>> Okay. Uh thank you for again thank you for your great talk and please give a round of applause for our speaker again.

[00:51:54]Thank you.

[00:51:55]>> Thank you so much.