Post-Quantum iMessage with Douglas Stebila

Apple iMessage is getting a big upgrade! Not only are they rolling out ratcheting, but they’re going post-quantum, AND they’re doing post-quantum ratcheting! Douglas Stebila joined us to talk about his security analysis of the new PQ3 protocol update and not indulge our wild Apple speculations:

Transcript: https://securitycryptographywhatever.com/2024/03/03/post-quantum-imessage-with-douglas-stebila/

Links:
- https://security.apple.com/blog/imessage-pq3/
- Security analysis of the iMessage PQ3 protocol
https://security.apple.com/assets/files/A_Formal_Analysis_of_the_iMessage_PQ3_Messaging_Protocol_Basin_et_al.pdf
- Ratcheting design: https://eprint.iacr.org/2024/220.pdf
- When Messages are Keys: Is HMAC a dual-PRF?: https://eprint.iacr.org/2023/861.pdf
- Real World Deniability in Messaging: https://eprint.iacr.org/2023/403.pdf
- Padmé: https://www.petsymposium.org/2019/files/papers/issue4/popets-2019-0056.pdf
- Max Headroom: https://www.youtube.com/watch?v=cYdpOjletnc
- Extended Canetti-Krawczyk model: https://iacr.org/archive/eurocrypt2001/20450451.pdf
- Douglas Stebila: https://www.douglas.stebila.ca/

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

Chapters

• 0:12 Apple's Post-Quantum iMessage Security Analysis
• 17:08 Hybrid Key Agreement Protocols and Security
• 27:47 Cryptographic Deniability in Messaging
• 39:36 Messaging Security Protocol Updates

Transcript

Deirdre: 0:12

Hello. Welcome to Security Cryptography Whatever. I'm Deirdre.

David: 0:16

I'm David.

Deirdre: 0:17

And we have a special guest today. We have Professor Douglas Stebila with us, hi, Douglas.

Douglas: 0:23

Good morning.

Deirdre: 0:24

Douglas is— very rapidly agreed to join us after a new announcement from Apple about a post-quantum security upgrade to iMessage. And not just a post-quantum security message to upgrade to iMessage, but a whole bunch of upgrades to their iMessage protocol that have been updated in other secure messaging protocols. And now Apple is just sort of rushing ahead of everybody on a whole bunch of fronts. And it's pretty interesting. We've invited Douglas to join us because he wrote a security analysis that Apple published as part of their announcement. And he was the first one to say, yes, I can jump on a call with you for an hour. For the record, we reached out to some people at Apple and they did not get back to us. So Douglas wins. So, Douglas, can you tell us a little bit about one, iMessage and two, the changes that Apple has made to iMessage that you analyzed?

Douglas: 1:25

Yeah. So iMessage is Apple's very large scale consumer instant messaging app and provides end-to-end encryption. And so the announcement on this week talked about their addition of post-quantum cryptography to iMessage. And so the cryptographic structure of the protocol that they announced is that it has a handshake and then a kind of double ratchet structure similar to we're familiar with in Signal. And so whereas it had been previously using Diffie-Hellman key exchange in the initial handshake and the asymmetric ratchet ellliptic curve Diffie-Hellman key exchange, they've now added post-quantum KEMs there, specifically ML-KEM.

Deirdre: 2:14

And so they're using, I made sure to double check, because in a couple, the post and the two papers, they had said different things in different places about whether they were using Kyber or ML-KEM. And some people have basically confirmed. It's all ML-KEM. I have a feeling they were working on this for a while. And so they started with Kyber, and then they moved to ML-KEM because that seems to be the case for a lot of parties. But anyway, they're using ML-KEM 1024 for their post-quantum upgrades to their device keys or identity keys for part of the session's initial handshake. And then one of the big things is they are including ML-KEM 768 keys every so often when they do the ratcheting during the ongoing back and forth messaging conversation. And one thing that's interesting is one Signal made a post-quantum upgrade recently, but just to their conversation setup handshake, not ongoing post-quantum updates to the ratcheting. And no one else has done any post-quantum updates to their ratcheting like this, of any similar conversation that I've seen before, any sort of end-to-end messaging conversation. Apple is the first, but they're only doing it if I'm correct, every 50 messages, or at least every seven days. I think they have a more complicated heuristic under the hood, but those are kind of the bounds of that heuristic. And they said that they're only doing that only that often because these ML-KEM keys are so large on the wire and they just can't afford it. Can you tell a little bit more about that?

Douglas: 4:00

Yeah, that's right, Deirdre. So ML-KEM keys are, well, a key exchange with ML-KEM is a couple of kilobytes of communication, whereas with ECDH we're looking at 32 or 64 bytes. So there's a pretty big increase there. And so you have to kind of make a decision whether you want to pay that two kilobyte cost on every round trip that you do. And for chat messages where the message itself could be a two character emoji or something, that's a pretty substantial overhead. So it's a choice to make. And, yeah, so what you described is my understanding that there's an amortization, basically that they'll send the post during the asymmetric ratchet. They'll send ML-KEM keys periodically, and I think that's a tunable parameter they're able to adjust over time. But in a setup right now, what they've said is that it's every 50 messages, or at least every seven days, depending on how frequently the device is being used.

Deirdre: 5:05

Okay, that's pretty interesting. I would be very— unfortunately, Apple has never released anything like a specification for iMessage. It's all been kind of reverse engineering how it works and having people like you kind of blessed to look inside the curtain and do an analysis and then release an analysis. So I would be very interested to look at it from like a protocol design perspective or an implementation perspective where that turnable parameter lives and how far is it exposed and stuff like that. But anyway, can you tell us a little bit about what you looked at to do your security analysis? And for those listening, Apple released Douglas's security analysis on their website, and we'll link to that in our show notes. And this is a straightforward, like, I'm a cryptographer, I'm modeling this as a security game. This is like game-based proofs. This is not some of the computer aided cryptography proofs that we've talked about on this podcast recently. This is bread and butter, I'm sitting down, I'm using my brain, and I'm drawing up some security proof sort of analysis. Can you tell us a little bit how you approached it?

Douglas: 6:17

Sure. So Apple gave me kind of their version of the design document and the protocol description, and so I kind of translated that to the format that I understand, pseudocode in a paper in LaTeX. And so that's what's in the security analysis that I wrote for them that they've released, and they kind of reviewed that my interpretation of what they gave me was correct.

Deirdre: 6:44

Good.

Douglas: 6:44

And then I proceeded with the analysis from there.

Deirdre: 6:47

Okay. So deduced security properties that they were trying to achieve, or did they say, we are trying to achieve certain security properties, please double check our work, or something like that.

Douglas: 6:58

Yeah. They were very clear from the outset on the security properties that they were aiming for. So post compromise security or healing, forward secrecy. So forward secrecy on both the asymmetric and symmetric ratchets. Post compromise security on the asymmetric ratchet, both post-quantum and elliptic curve assumptions for that part, and also confidentiality in the session key establishment, the initial handshake establishment.

Deirdre: 7:26

So did you have some sort of tunable advantage when the post compromise security and the forward secrecy stuff was being analyzed, given this heuristic of, "we're only updating our post-quantum security with these ML-KEM ratcheting keys every 50 or so", or up to seven days, however, that is measured in terms of advantage. How did you account for that? Sort of like, when it's literally like the original Signal ratcheting double ratchet design is you send a new handshake, Diffie-Hellman every, like, I send a message and my partner sends me one back. If they haven't sent one back to you in a while, and you just keep sending them, like, I saw this TikTok. I saw this TikTok. I saw this TikTok. That's where the symmetric ratchet comes in. And you're not doing the asymmetric ratchet, but when you finally complete another back and forth handshake, that's when you do an asymmetric ratchet. So that's a very deterministic way to analyze the post compromise security and the forward security that the ratchet gives you. How do you analyze the sort of, like, maybe it's every 50? Maybe it's every seven days? Who knows? How do you do that?

Douglas: 8:44

Right. So, basically, the model that I kind of gave of the protocol is actually kind of assuming that there's both ratchets happening, both post-quantum and elliptic curves happening in each step, and so that kind of simplifies the analysis.

Deirdre: 9:00

Okay.

Douglas: 9:01

And then if you wanted to leave out one of the components, you could do so and extend the analysis. But the write up that I have just focuses on both of them happening at once for simplicity.

Deirdre: 9:12

Okay. Both of them happening at once. So did you kind of give sort of like a bound on if it at least happens every 50 messages, that means blah, or am I asking the wrong question?

Douglas: 9:29

No. So, basically, on the asymmetric ratchet, the analysis here is doing a post-quantum and elliptic curve exchange on every step of the asymmetric ratchet.

Deirdre: 9:44

Interesting. So your sort of analysis is the ideal when this tunable parameter is, like, cranked up to, we don't care about no stinking badges, we're just going to send them all the time, every time an asymmetric ratchet is appropriate.

Douglas: 10:01

Right.

Deirdre: 10:01

So it sounds like, strictly speaking, what Apple is deploying, at least right now, and can be tunable later, is strictly below what you have analyzed in the paper.

Douglas: 10:11

Yeah, I guess so.

Deirdre: 10:14

Okay. I'm not aware of a nice, measurable advantage of an adversary of, like, oh, we only do ratcheting every 50 handshakes, and we only do ratcheting, and it could be somewhere between 50 and a million, whatever. So I was very curious if you had pioneered a new sort of analysis or something like that. But that makes it a lot more obvious.

Douglas: 10:39

Yeah, you could do that. I think you'd have to kind of exchange the, extend the key exchange model to maybe give the adversary the chance to control how frequent that happens. And that introduces a whole lot of extra bookkeeping, keeping, and state management into the security experiment. But you could do it.

Deirdre: 10:57

Yeah. Okay. By the way, how much time did you have to work on this?

Douglas: 11:01

Yeah. So they reached out to me kind of middle of last year to start looking at it.

Deirdre: 11:05

Okay. All right. So you had time. Just curious. One interesting thing is that the setup of the initial handshake has these 1024 bit ML-KEM keys, which are the highest security parameter that's being published by the standard, which makes sense if you're going to root your stuff. Sure, why not? This is ostensibly a one time thing, unless you completely reset your session, your chat session or something like that, and then having something, the next step for these ephemeral, for these ratcheting asymmetric ratcheting keys. One other thing that seems to jump out at me is that they explicitly call out that they're not doing any post-quantum authentication like signatures in this update. And this chimes with the Signal PQ extended Diffie-Hellman update that they did. They also have the original Signal setup. And kind of similar with iMessage is you have an identity key pair or a device key pair that is associated with an identity, and you can both do that to do Diffie-Hellman like curve25519 Diffie-Hellman. And then you can tweak that key pair and you can sign with it. And so if you're using what Signal uses, which is curve25519, you can do this transformation and you can use a key pair to do the key exchange, and then you can use that same root of key material to sign with Ed25519 or something like that signature scheme. Apple uses the same thing. They're doing everything with P-256, so it's ECDSA and stuff like that. But they ship their Apple devices with a key pair rooted in hardware. And so I completely understand why they are like, this is extremely valuable. We have a very, very trustworthy root of trust. Unfortunately, we can't go over to TSMC and just be like just shove in ML-KEM roots of trust at the same time. That is way years away from them doing that. So they do the session setup, they do their ECDH part of the session set up with P-256, they do their ML-KEM session set up with ML-KEM 1024, but they're signing with their root of trust key pair for ECDSA and they don't have an equivalent for the post-quantum stuff. Did I get anything wrong? Does that sound correct?

Douglas: 13:38

I don't know about the hardware, the root of trust stuff, but yeah, you got the protocol description right. As far as I know, yeah.

Deirdre: 13:45

In their blog post they were like, they mentioned a couple of places where I'm just sort of like, oh, right. So my whole point of describing this is, one, they don't have post-quantum authentication stuff, which is just understandable. It's not a very, no one has that. Yeah, speaking of the guy who has to worry about this for the web PKI and his web browsers, but also that they have invested a lot into hardware optimization, like all these things that are rooted in their secure enclave implementations, including P-256, ECDSA and ECDH over P-256 and stuff like that. And then they have this key material that's rooted in their devices and they have this whole chain of trusted compute and trusted hardware, but it's all rooted in classical elliptic curve cryptography. And this other stuff, the new stuff is all, I think, all in software, which makes sense. But it's also interesting from a security perspective of like you've got these layers of like you've got some real solid root of trust, but it's all classical. And then you're kind of layering on this post-quantum stuff that is all in software, and it kind of chains to this software update mechanism that also is root of trust, but it's all based on classical as well. And this is a little bit outside your brief, but I hope hardware backed, high optimized implementations of things like ML-KEM will get rolled out eventually. I don't know if they're going to get stamped into the silicon in TSMC anytime soon, but if those high efficiency optimized implementations get rolled out, that may have an impact on how frequently you can do the ratcheting, at least at a computational level, the transmission of bytes on the wire, Apple doesn't have a lot of control about how expensive that is for your battery, how long that takes. But that was just one thing that I kind of noted that they mentioned in their post. They had this scale, they had PQ1, PQ2, and now they're calling this PQ3. And I think PQ4 is where you will have this post-quantum authentication in there. So this is me just talking. I don't have a question here, I'm sorry, but to actually ask you a question, in your analysis, did you look at the lack of post-quantum secure authentication as it impacted the protocol or not?

Douglas: 16:15

No. So that was kind of outside the brief. The design criteria were for post-quantum confidentiality, but not post-quantum authentication. So I think you speak to a lot of reasons why adopters are doing post-quantum confidentiality. First, I think your example on the whole hardware stack and roots of trust kind of speaks to the magnitude of this transition, that there's so many different pieces that have to come into play, and even a company that controls a large part of its stack still has to take its time to get all of those pieces in place. And I think obviously as well, post-quantum signature schemes are still developing a bit more than post-quantum KEM are with the continued NIST signature scheme on ramp. And the need is maybe a little bit less pressing as well because we don't have the same threat of store now and decrypt later attacks on authentication. That just doesn't make sense.

Deirdre: 17:18

Definitely. Like completely understand it is a problem that we will eventually have to solve. And all of our options at the moment don't seem very attractive, and yet we will eventually have to solve it. And it's not that we're putting it off, it's just that we get to focus on, like, we've got some KEMs, all right, we have a tool set that we're all right with. We have a very pressing a— currently facing us problem, because you can store everything that we're putting on the wire now and haven't been for years, and then just theoretically rifle through it when you've got a cryptographically relevant quantum computer come online and just point it at your favorite thing and you're done. But the problem doesn't go away anytime soon. Okay, some of the other cool things that I'm going to ask you about, and I don't know if you actually have anything to say about them, but I'm going to ask you anyway. One of the things that has been a topic for people in the area, like myself, is how you do hybrid combinations, or whatever you want to call it, for these shared secrets or KEM combiners or whatever you're combining. So in this case, this whole protocol is not a fully PQ protocol. This is a hybrid design, because they're keeping all this sort of elliptic curve based stuff that we talked about and adding this hybrid stuff, this, sorry, post-quantum stuff onto it. If it was just all post-quantum asymmetric primitives, we would just call it fully PQ. But technically, this is hybrid. And so when you're doing this hybrid stuff, you've kind of got a range of options about how to smoosh the things together. Can you tell us a little bit about how they are combining the shared secret key agreement from classical and the shared secret key agreement from the post-quantum stuff and smooshing it together and getting security out of it.

Douglas: 19:18

Right. So in the iMessage PQ3 protocol, especially, like, let's focus on, say, the asymmetric ratchet. So there's kind of three pieces of input keying material, or up to three pieces of input keying material. There's the chaining key from your previous stage or from the initial handshake, there's a new ephemeral Diffie-Hellman shared secret, and there's potentially a new ML-KEM post-quantum shared secret. And so from those three pieces of input keying material, we want to derive a new chaining key from which we can derive the next stages and the next message keys. So the approach that they used was to kind of use HKDF-Extract, which is really just HMAC, a two input function to smash those together. So they put one piece of keying material in the HMAC key input and the other piece of keying material in the HMAC message input. And so they do that once to accumulate together the chaining key and the ECDH shared secret, and then another time to accumulate that intermediate value with the post-quantum shared secret. And then from that result, then you apply HKDF-Expand as a PRF to expand out a bunch of keys from there.

Deirdre: 20:41

And in the slot in the label, they have a ton of session contextual transcript material. And we love this. If you can afford to do it, if it's computationally affordable to you, just shoving everything public in your session handshake transcript in there is just like. We love that. And we love that because it means that you get the session independence stuff. No one can swap-a-doodle your encapsulated shared secret for another one. And all these nice things come out of just shoving all that stuff in there. So I'm very happy, I'm very happy about that.

Douglas: 21:25

Yeah, I'm of the philosophy, hash everything in if you can. So I'm glad to see that. I think in key exchange protocols, there was this trend for a bit of time, trying to be clever and leave things out. And you can prove security, but it's a little bit more fragile. Right. And you have to be careful and make sure if you change something or you move to a different model or a different primitive, you have to make sure that it really goes through properly. Whereas if you hash everything in, there's less risk.

Deirdre: 21:55

Yes. When we weren't sure if they were using Kyber, if they were using ML-KEM, they are using ML-KEM, blah, blah, blah, this would be quite relevant is that if you are changing the KEM you use later, because different KEMs have different binding properties to their encapsulation key, to the ciphertext, to yada, yada, yada, about how much guarantee you get from the shared secret that comes out the backside of your KEM, and how closely it's like you cannot get this value if you use a different public key or if you use a different ciphertext, or you have a different ciphertext. So the fact that they're binding all of the stuff into their KDF means that that doesn't matter, that they have a lot more ability to swap those KEMs out, because they're literally committing to everything related to that KEM. And so it doesn't matter. They can change things around in a much more agile way, which seems to be a bit of a crypto agility is coming back, but in a different context, and it's kind of breaking my brain.

David: 23:00

Are they committing to the actual algorithm used somewhere like feeding in the name.

Deirdre: 23:06

Of, let's see where it's invoked up here because it's used several times. We've got id, we've got the label for the ratchet, we've got the public key, the elliptic curve public key, we've got the post-quantum ciphertext, the post-quantum public key I think they are, because they're committing to a bunch of identifying material, not just the key material, but I need to go double check anyway. I would be surprised if they weren't. One interesting thing about this kind of nested HMAC KDF that they've put together, they call it KDFRKCK because it is, the whole KDF they've designed. They take the sort of root key, if you have a root key, you have this elliptic curve shared secret, you've got the KEM shared secret, and you've got all this contextual session information. They call it sid. And then you do this computation on the inside and it spits out your RK and your CK. And those are the two different ratchet keys. Is that what those are?

Douglas: 24:10

Yeah. So the root key is the one that continues on the asymmetric ratchet, and the CK is the one that's fed down into the symmetric ratchet.

Deirdre: 24:20

Awesome. Okay, this is an interesting approach, because I've seen a lot of different approaches of how you take two different secrets and you throw them through a KDF, and then you just have a value at the end, and then you either just split it down the middle and use like the first half of the bytes for some other purpose, and then half of the bytes for another purpose, and you might shove those through more KDFs or something like that. This one is, my first naive approach to doing something like this is I would concatenate all this information

together: 24:53

your KEM shared secret, your elliptic curve Diffie-Hellman shared secret, your session information, your transcript information, concate it all together and shove it through HKDF, which is what they use internally. They didn't do that. Do you have any notions about why they didn't do it that way and they did it this way instead?

Douglas: 25:14

So I don't have insight from their side. We see this pattern elsewhere. So the TLS 1.3 key schedule kind of also combines the preshared key with the Diffie-Hellman shared secret using two arguments of HKDF extract. So we've seen this design pattern before. So I have thought about this a bit, and when you do it this way, it allows you to model HKDF as a dual PRF.

Deirdre: 25:42

Yeah.

Douglas: 25:43

So you really have a two input function and you're asking it to be a PRF in its two kind of distinct inputs. And there's subsequently been some security analysis, specifically of the dual PRF property of HMAC. There's a crypto 2023 paper by Backendal, Belare, Günther and Scarlotta. So that's a very kind of well defined specific property you're making of assumption you're making of HMAC, whereas concatenate and just hash, I mean, if you're in the random oracle model, then great, it's fine, but otherwise you're less clear on where the different parts of the secret are in the hash function input, whether it's going across a block boundary. It feels like you're being a little bit less specific on that, and you're making a variable length assumption as well on kind of where the secret stuff is within the input.

Deirdre: 26:34

That's interesting, because I'm a part of a team that's working on a different hybrid KEM called X Wing, and part of that is literally concatenating a bunch of stuff together and shoving it through SHA-3. But. To your point about where is the secret material and the block boundary and all this sort of stuff, our team has done very specific analysis about this length of bytes, where the key material is, how many rounds of Keccak inside SHA-3 are being used to parse this material, for both performance reasons and for security reasons, this analysis indicates to me that it allows you to use HKDF and HKDF-Extract and HKDF-Expand in a slightly higher level of abstraction without having to do, " how many rounds of the internal cipher block function of this hash function that I'm using as my KDF and how long is my—", it allows you to almost achieve a similar thing, but with a nicer, safer to use higher level of abstraction. Neat.

Douglas: 27:45

Yeah, it is a higher level of abstraction. I think you still have to really be careful about judging whether HMAC satisfies this. And it hadn't really gotten very much attention until last year's paper and last year's paper that I mentioned from CRYPTO 2023. There are a lot of subtleties to it, because HMAC does some interesting things like, and I can't remember all the details. But if the key is less than a certain length, then the key is used raw. If the key is longer than a certain length, it's hashed first. And there's a few extra little details in there. So it's a subtle analysis and sometimes the lengths do matter. So there's a lot to be careful about here in how you do the key derivation in dual prfs and hybrid combiners.

Deirdre: 28:34

Okay, that's very good to know because there's a discussion about trying to make a draft about how to do hybrid KEM combiners and recommend it to things like IETF. And I've had that paper on my sort of queue, but then I saw this in the Apple thing and I was like, oh, this is very relevant to my interests. And then I didn't detect that subtlety just from a cursory disorder. Like, oh, this is neat. This is another option. Maybe we'll just try it like this. And it's like, okay, there are other subtleties to doing it this way too. Okay, thank you. I need to read that. Okay. One thing that I noticed, or someone noticed when looking at this protocol update is the lack of deniability in this update to iMessage. If I'm Apple, I don't think they care about deniability. But there are other very similar end-to-end encrypted messaging protocols like Signal that do seem to care about deniability. Can you tell us a little bit about what cryptographic deniability is and why some people care and why apparently Apple and iMessage don't care.

Douglas: 29:40

So I can tell you what cryptographic deniability is. I can't tell you what Apple's opinion is on it. So cryptographic deniability is the idea that when you participate in a protocol exchange, that exchange should not produce any kind of output that can be transferred to another party and be used to verify something that occurred during the protocol execution. So either it can't be used to confirm that a particular party said something during a protocol execution or even participated in a protocol execution. And so kind of this dates back at least to the off the record messaging protocol OTR, which is in some sense an ancestor to many of our chat protocols today. And OTR had a form of cryptographic deniability because the two main things that gave it that were that it used Diffie-Hellman for authentication rather than signatures, and then from that shared secret use MACs to authenticate messages. And so first off, because it's a symmetric key in a mac, either party could have generated a MAC tag. And so you can't proverif that the other person said something, and then there are no signatures, so you kind of don't have that as well. And OTR, I think, even went so far as to release the MAC keys at the end of the conversation so that they could really argue, hey, the key is out there. And in fact, if you download OTR, you get this tool to forge a transcript. So take it with a huge grain of salt.

Deirdre: 31:20

For me, we've come so far in the deployment of end-to-end encrypted messaging protocols in the world, where it's actually deployed by your whatsApps, your facebooks, and honestly, your wide scale Signals. We've gone so far the other way away from deniability. For example, Facebook released full support for end-to-end encrypted Facebook messaging chats. It used to be opt in, and now it's, I think, on by default. And they have like a whole bunch of stuff that allows you to report a message to Facebook and for Facebook to authenticate that Facebook sent that message that was end-to-end encrypted, that they sent it, they couldn't read it. But now you are reporting the decrypted message, know, a tag that was on the encrypted message to Facebook to be like, someone's being a dick to me or harassing me on Facebook messenger, I'm reporting them to you. And Facebook needs has very explicitly put extra cryptographically safe, but extra stuff in here that's like the opposite of deniability. It's someone sent something, and we Facebook ferried it from point a to point b, and someone received it and decrypted it. And now we are able to check all of those. Anyone who wants deniability except cypherpunks.

David: 32:46

I desperately want to see deniability.

Deirdre: 32:53

Oh, my God.

David: 32:55

Yeah, I want a court case that has an OTR.

Douglas: 32:55

Yeah, I've wondered about that, too. And there are a couple of things that I thought of that I wanted to mention about this. So there was this talk last year at RWC on deniability in messaging, and we have this notion of cryptographic deniability. But what does it mean in the real world? And is it actually promised in the real world, even if you have a deniable protocol Signal, or OTR? So this paper by Collins, Colombo and Huguenin-Dumittan. So they argue that for deniability, you have to consider the context in which the protocol is running. So maybe the core chat protocol is deniable, but then it's running in some kind of— there's a separate layer above that authenticates the users to the server or something like that. So all of that could be undermining cryptographic deniability. And then, as David said, we have no idea how this would play out in a court. Right. The legal system has for centuries had its own way of assessing credibility of evidence long before digital signatures were a possibility. Right. In fact, there was a paper at SMP last year as well, like, touching on this question just a little bit. So there's some researchers from University of Maryland, they did this study where they had like, 600, well, 1200 users across 2600 user studies where they asked how nonexpert users would perceive deniability of chat messages in a courtroom setting. So, like, how likely are you to convict if you are told that if a cryptographer comes in and tells you that it's cryptographically deniable, or if you sieve that the chat program includes a function to edit the messages or tamper with screenshots or whatever? So I think we're starting to touch just a tiny bit on what deniability, cryptographic deniability really means. But I don't know really what it means.

David: 34:52

Okay, Deirdre, we're going to need you to do some crimes and then leave evidence in OTR, and then we'll create some forged transcripts and send you to the US justice system and write a paper about it.

Douglas: 35:03

Well, so one other thing on this. So we have seen court cases where chat messages have been evidence, and I'm thinking, among others, of anchor chat in Europe, which was a chat program used by organized crime and so on, and law enforcement infiltrated this and that evidence has been used in convictions and so on. And the chats there contain all kinds of corroborating evidence, like a selfie of someone holding a bag of cocaine, or like someone, and I think this is true, someone holding a block of cheese. And you can see the fingerprints from their fingers holding the block that are in the picture. They're holding the block of cheese.

Deirdre: 35:45

Right? Wow.

Douglas: 35:46

All this corroborating evidence, regardless of the metadata of the chat.

Deirdre: 35:51

Oh, boy. Yeah. Oh, God. I could see someone be like, oh, right, "This is like a picture of my passport for backup." And then be like, "but the transcript is deniable!" Just like, okay, all right. Yeah. It kind of reinforces, like, it's a cute cryptographic trick, but I think the end user demand for deniability has only decreased over time. But it seems funny that cryptographers are like,"there's no deniability here? Oh, no!" And I'm like, why would, why would there be? But actually, on the other hand, Apple might be one of those parties that actually kind of is no, like, nothing to see here, like, we care about your privacy. We care about all this sort of stuff. They might be one of those parties that are like, yes, you cannot... But they're also just a large company. I don't know.

David: 36:47

The EU, just to rampantly speculate, the EU does care a lot about trust and safety and deniability and trust and safety in general don't play nice with each other.

Deirdre: 37:00

I know there's nothing in your analysis, Douglas, about the padding that they added to iMessage, which is basically like a privacy win. I don't know if other messaging protocols have something similar or if they're just sort of just doing the maximal padding by default anyway. But basically, this is another way to avoid a completely different class of attack, which is just sort of like looking at the different sizes of the ciphertext on the wire to get some information about what's actually being encrypted. And so to counteract that, they call it, this is a Padmé padding heuristic, which literally makes it so that that information that is being leaked by the size of the ciphertext on the wire is much, much smaller. Can you tell us a little bit about that?

Douglas: 37:54

I can't. I didn't take a look at that. All right, so basically, my focus was on the key establishment, right? The key exchange, not the authenticated encryption or anything of her message transmission.

Deirdre: 38:06

Okay.

Douglas: 38:07

Sorry I didn't take a look at Padmé, but it looks promising.

Deirdre: 38:11

Yes. This is sort of like yet another thing that is just, iMessage has been a little bit of a... iMessage came out the gate when Apple released it as a pretty good, groundbreaking, or at least for wide scale messaging protocol encrypted messaging protocol. It wasn't documented very well, but it was considered pretty good at the time. And then it's been kind of stagnant. People have analyzed it. People find some breaks, they fixed some breaks, and things like that. Signal has screamed ahead, WhatsApp adapted Signal. WhatsApp's had their own advancements, and then Signal has been an influence to a lot of end-to-end encryption protocols, not just messaging in a lot of places. And iMessage has just been kind of plateaued, I would say. And then all of a sudden, they've got post-quantum, and they've got more post-quantum stuff than anyone else has. They've got this much better padding for privacy. They've got a whole bunch of stuff going on in here all at once. I don't have a question here, but it's just kind of good. It's good to see because iMessage kind of was a big leader to start, and now they're coming all the way back after being somewhat quiet for a long time, and it's pretty good to see. And I'm glad that they basically reached out to people like you. And there was another team that did a Tamarin analysis, and I have to go through their analysis, and I want them to release their Tamarin model. I was grepping in their paper for a git link or something, and there isn't one. So I have to dig a little bit harder, and I would like to take a look at that. And someone did an audit of the code. They were not named, just that an audit happened. All right, but that is also good. And the other thing is, a couple of months ago, they announced their contact key verification thing, and that came with key transparency logs. And for us nerds, like, this is like a big, big thing because did Whatsapp do that first or did I forget? Okay, David's nodding at me. I think WhatsApp did similar, a slightly different design, but they did a similar thing first. And basically the contact key verification, or key verification stuff is about when we talked about setting up your sessions and you have these long term keys that might be per device or per identity or whatever it is, those are long term and you really want to know when they change because you have to restart your session and things like that. In the long, distant past of messaging, encrypted messaging, it was just sort of like, here's a code, here's an encoding of someone's public key, and maybe you compare codes to make sure that you're both seeing the same thing and that it was relying on you to check that out of band. So, like, in the distant, distant past, this might actually involve someone at some data center calling you and be like, read me off the hex encoding of your ssh public kem, which I had to do back in the day, and then Signal and WhatsApp literally had like a little QR code. And you do that out of band, blah, blah, blah. So this contact key verification stuff, and the equivalent WhatsApp one was literally doing it for you. It was WhatsApp or Apple or whomever is running the service watches all the public keys that are being verified, has these logs that anyone can check to keep track of the changes of these public keys and then prompting you, the user, if they notice something is wrong, if they notice a public key being advertised from a party, that shouldn't be, because WhatsApp or iMessage or whatever knows the trusted public private or the trusted public keys from trusted devices that it knows. And so it can catch or any of these logs can catch, it doesn't have to be by the service providers, but they are in the most advantageous position to operate this; they will notice if David Adrian's device, which is showing me a hash of a public key that's like 1234, but the hash of the public key that I'm seeing on my device is actually four, five, six, seven or something like that and they will notify me. So that's the whole thing. They did that too. They did that a couple of months too. And basically it seems to be the, I don't have the numbers in front of me, but it was the largest deployment of key transparency logging period because they have so many devices. I think the Apple one was bigger because they just turned it on. I think they only turned on by default. And the WhatsApp one is like slightly smaller for reasons and I don't remember why, but it's literally billions versus billions.

David: 43:10

I believe that Apple's users times average number of Apple devices is bigger than total number of WhatsApp users. Since it's just one key per user on WhatsApp.

Deirdre: 43:19

That might be it. But yeah. Anyway.

David: 43:21

My understanding is also that Apple launched PQ3 and the key transparency at the same time and then just being Apple didn't tell people about it.

Douglas: 43:30

No. I think key transparency came out in an earlier version of iOS. Yes, 17 two and now we're on. And I think they said post PQ3 will come out in 17.4. Yeah. Which we're not at yet. Yeah. Although I also was fiddling around with contact key verification yesterday.

Deirdre: 43:57

Oh yeah.

Douglas: 43:58

And I had to go and turn it on. So I don't know if it is on by default or maybe I just screwed up a setting but I had to turn it on, at least.

Deirdre: 44:07

I think for Apple this started as high risk users, whatever their official name is for know, if you think you're a high risk target, turn on all of these features, including contact key verification or whatever. And now they're rolling out contact key verification for basically everybody. But I do think you have to turn it on. And I think in WhatsApp they have set it up so that it is on by default because they're literally doing the, like, we're doing all this work on the back end so that only when we give you a prompt or a flag or whatever, you have to do anything or whatever. Just not even do anything, just not message somebody or something like that. I think that's what it is. And it may literally just be. It's harder for Apple to turn this on by default for so many heterogeneous devices and operating systems because they're doing this stuff for iOS, iPadOS, macOS, watchOS, blah, blah blah. They have a heterogeneous environment. And WhatsApp is just like, we have an app, well, they have iOS, they have an Android app, they have WhatsApp web, which is tightly bound to those other apps. So I think they have an easier time turning it on by default than Apple does. But I wouldn't be surprised if they did eventually.

David: 45:27

All of those are bound to a single phone number, though. Like, you don't have two instances of your WhatsApp at the same time.

Deirdre: 45:33

I have to remember how they handled this, actually, because I think they evolved it.

David: 45:39

You can do web and a phone at the same time, but I don't think you can have two separate phones.

Deirdre: 45:43

I think you might be changing it, but you might be right. But yeah. Tldr yeah.

David: 45:48

If anyone with inside knowledge of Apple wants to come on and wear a max headroom mask and use a voice.

Deirdre: 45:54

Changer, we'd be happy to talk. We would love if you just quietly gave us the inside scoop, but I think everyone is sworn to secrecy by Apple. Incorp. But yeah, Tl the or iMessage on a wide scale has gone from pretty stagnant, like okay, but hasn't really changed much in a long time to changing a lot in about six months, or at least from our public vantage point. The contact key verification was October. This is February. It's been a lot of awesome stuff being rolled out all in one go. Very cool to see. And they're now at the front of the game in terms of the most post-quantum resistant end-to-end messaging protocol because they are including these post-quantum ratchets. Not every asymmetric ratchet, but at all. No one else is doing that right now. No one else has deployed that to their users right now. So that's awesome. I'm trying to think if there's anything else you want to cover. Douglas, I looked at Signal's post-quantum extended Diffie-Hellman pretty closely. Have you looked at that significantly to be able to compare and contrast how iMessage does its post-quantum hybrid session setup versus the Signal version, not the extra ratcheting stuff, just the setup of the session.

Douglas: 47:21

Right. It's been a while since I looked at it, so I don't remember the full details of how it went. Right. So they have, in the handshake they're doing a post-quantum KEM. I think they're just doing with ephemeral keys. They don't have long term identity keys.

Deirdre: 47:38

I think they do, yes. So now it's the post-quantum variant long term key, the post-quantum pre keys or whatever, and the classical long term keys and the classical pre keys, and they're all smushed up there together, I think. And yeah, all the pre keys and all that stuff are signed classically with the long term classical id keys.

Douglas: 48:07

Right. So it looks like the PQXDH has a bunch of one time post-quantum KEM pre keys, and then also a last resort one that they call it if there are no more one time ones available.

Deirdre: 48:21

Yes, and that last resort may be used repeatedly if they haven't refreshed the other pre keys,

Douglas: 48:29

but no identity keys in the post-quantum chem.

Deirdre: 48:35

So in iMessage PQ3, they don't have a long term ML-KEM, they just have a strong session set up ML-KEM, but their id key is still their, I guess their hardware rooted elliptic key pair or something like that. Okay, I didn't pick up on that. That's cool. And actually they seem very similar except for the KDF.

Douglas: 49:06

Yes, it looks like the Signal PQXDH key derivation function concatenates the three or four Diffie-Hellman shared secrets and then also the post-quantum shared secret after that, and then runs that through the key derivation function itself, which it says HKDF. And I guess that would mean HKDF-Extract. And then there's an-Expand after that.

Deirdre: 49:35

Yeah, the standard, just one after the other. And I think the only other kind of note is that Signal's extended Diffie-Hellman gives these sort of implicit authentication things to this that I think the iMessage session setup doesn't have. So the iMessage session setup is signing a bunch of stuff with their ID key or whatever. The transformed equivalent of their P-256 id key; Signal does that too. But they're also doing this triple Diffie-Hellman that they've been doing for a long time. So they have a diffie helmet between their id key and a pre key and vice versa. So the other party between their it and the other person's pre key, and then between these two pre keys as well, and they're doing those are the triple Diffie-Hellman, which have been a part of Signal for a long time. And then they add in this ML-KEM between these pre keys for the post-quantum variant, and then they concate those all together and smoosh them through their KDF. So can you tell us a little bit about the authentication properties that these extra Diffie-Hellmans give us, that they just don't happen to be present in iMessage, and I don't think they ever have been.

Douglas: 50:54

Right. So in Signal, the authentication of a session or messages in that session of the session is done using implicitly authenticated key exchange. So there are these long term Diffie-Hellman keys, and we compute a shared secret, and only you and I should be able to compute that shared secret. So no one else has that, that's implicit authentication. Then from that, if we derive a MAC key or something and we use that, then you subsequently explicitly authenticate a message tagged under that MAC. That's kind of the main idea from which cryptographic deniability comes from as well. Whereas in the iMessage protocol, the long term keys are signing keys, not Diffie-Hellman keys, and they use them in a signature scheme, not in a key exchange.

Deirdre: 51:45

So besides the deniability part, why is this attractive beyond signing things with your long term id key? Because that's what iMessage has, and that gives us some amount of authentication that we are talking with someone who controls this long term ID key to start the session. Why is this extra implicit authentication attractive when we already have these signatures over a lot of this stuff that is bound to our long term id key, for example.

Douglas: 52:18

So if you're doing implicitly authenticated key exchange with long term Diffie-Hellman keys, you can do extra combinations ephemeral with long term or vice versa. And this can increase the resistance to certain type of compromise attacks. So there's this security model paper for key exchange called the extended Canetti-Krawczyk paper [eCK]. And what this model says is that, so we know forward secrecy, that's like it should be secure if your long term key is revealed afterwards. But an eCK model, and with these many combinations, you can also have security against randomness reveal. So if your random number generator is bad or somehow revealed, then if you also did a static Diffie-Hellman, and you did that static Diffie-Hellman using well generated safe static Diffie-Hellman keys, because maybe they're in a hardware route of trust or something, then you at least still have that basis of confidentiality, even if all your ephemeral keys were bad.

Deirdre: 53:25

Awesome. Okay, thank you. Because I think I knew something about that once upon a time when I first learned about triple Diffie-Hellman or whatever, and I literally was like, why do we do this again? I was like, okay, it's not just quote robustness, but it's like different kinds of robustness all throughout the protocol. And it's efficient enough, whether it's efficient enough to throw these big KEMs on the wire, to do the same thing, to do like I've got my long term KEM keepers and I've got my ephemeral KEMs. I'm just shoving like 6 wire to do it. We'll see. But thank you.

Douglas: 54:05

And if you're really sensitive with bandwidth, there is one more benefit to doing KEM based authentication rather than signatures, is that post-quantum KEMs are a little bit smaller than post-quantum signatures. You can save a little bit bandwidth, at least with our current post-quantum KEMs and our current post-quantum signatures. You could save a little bit of bandwidth with implicitly authenticated post-quantum key exchange rather than explicitly.

Deirdre: 54:29

Yeah, there's definitely some protocols that currently really rely on signatures, and I'm taking another look at them. Like, what if, all KEMs? Oops, all KEMs? And I might talk to you more about that later. Douglas Stebila, thank you so much for joining us. And thank you for letting us ramble about things that you did not look at at all, but try to answer our questions. Anyway. Thank you very much.

Douglas: 54:57

Thank you.

Deirdre: 54:58

Security Cryptography Whatever is a side project from Deirdre Connolly, Thomas Ptacek, and David Adrian. Our editor is Nettie Smith. You can find the podcast online at scwpod and securitycryptographywhatever dot com, and the hosts online @durumcrustulum,@tqbf, and @davidadrian. You can buy merch at merch dot securitycryptographywhatever dot com. If you like the pod, give us a five star review on Apple podcasts or wherever you rate your favorite podcasts. Thank you for listening.