[lxgr]

> The initial shared private key exchange could be done with more expensive, quantum resistant cryptography but the actual communication could be done through symmetric encryption.

That's exactly how Signal's symmetric ratcheting works (with the addition of an asymmetric ratcheting step to limit the forward impact of a key compromise on either side, which you can't do symmetrically).

> For the key exchange itself ("PAKE")

A PAKE requires a short shared secret. That does not usually exist in Signal's scenario.

> And for the symmetric encryption: [...]

Why that over regular AES?

[blurbleblurble]

Interesting! Thanks for explaining this.

> Why that over regular AES?

Well, I don't understand the exact details but it seems mostly to do with possible vulnerability to brute forcing if certain pseudo-random number generators are used:

https://eprint.iacr.org/2019/1208

> A PAKE requires a short shared secret. That does not usually exist in Signal's scenario.

I'm not too familiar with the details of how Signal's initial key exchange works, other than that from a user experience point of view it relies on people having shared phone numbers in at least one direction. So in practice this is kind of similar to the sharing of a one time password. Basically the users already need some kind of a "trusted outside channel" to exchange phone numbers.

From that vantage requiring people to "pair" in a secure context, most likely in person, wouldn't be that much different in practice from the way people usually exchange global public identifiers now (social media handles, phone numbers, etc.) over existing trusted channels. And having a shared private key that you store in a kind of pet-name address book is already so conceptually similar to an address book, which I find kind of amazing.

The big difference being that you'd obviously want to keep this address book secret, whereas phones have made it incredibly easy and have normalized leaking your contacts to any app that requests it. In practice, preventing private key leaks would be a challenging part of building out something like backchannel. The shared secret petname address books would probably need to be application specific, used in a sandbox and encrypted at rest.

Maybe there could be some standard tools for securely using one application's channels to bootstrap connections on another, but ideally it should be very, very hard for the shared secrets to leak, but easy enough for users to manage and be aware of them.

[lxgr]

> https://eprint.iacr.org/2019/1208

Ah, it's apparently a quantum-hardened variant of AES! But AES-256 is inherently quantum-hard and much better understood at this point. In other words, AES is really not the security bottleneck against quantum adversaries.

> I'm not too familiar with the details of how Signal's initial key exchange works, other than that from a user experience point of view it relies on people having shared phone numbers in at least one direction. So in practice this is kind of similar to the sharing of a one time password.

A user's phone number is public information; you can't use that as the password in a PAKE.

Signal has basically two ways of exchanging keys: Unauthenticated (in which case you trust Signal's service to really provide you your contact's keys, and not their own, which would allow them to MITM your chats), and "safety number comparison", for which you have to manually compare a short numerical string with each contact over a trusted channel (ideally in person). It's less convenient, but removes Signal's servers from the set of entities you need to trust.

Theoretically Signal could also offer a PAKE option to interactively authenticate a new contact remotely (if you do indeed have a shared password), but that's probably not easy to do in a way that's not prone to social engineering attacks, since you don't have a channel to communicate about what your password should be. (Remember that you don't trust the contact yet; an attacker could pick a password hint that they know the answer to as well!)

[blurbleblurble]

> A user's phone number is public information; you can't use that as the password in a PAKE.

For sure, I just mean that people are already used to exchanging numbers, in person, to establish phone contact. So from a user experience point of view, exchanging a PAKE password for a shared secret isn't that much different from exchanging phone numbers. The resulting shared secret could be treated very much like a phone number, except it's like a secret phone number between you and that person.

> Theoretically Signal could also offer a PAKE option to interactively authenticate a new contact remotely (if you do indeed have a shared password), but that's probably not easy to do in a way that's not prone to social engineering attacks, since you don't have a channel to communicate about what your password should be. (Remember that you don't trust the contact yet; an attacker could pick a password hint that they know the answer to as well!)

This kind of thing makes the most sense to establish a secure connection with someone you already trust over an existing trusted channel. Much in the same way that you'd commonly get someone's phone number for the first time at a party, in person. (The physical environment of the party being the trusted channel.)

Assuming these generative fake voice/video models get to the point (over the next five years) where people cannot easily differentiate between a real and fake conversation over an arbitrary/untrusted digital channel, I'd assume that the most trusted channels for these kinds of exchanges will be IRL in person or established secure channels.

> A user's phone number is public information

One of the big arguments in the backchannel proposal is that global public identifiers are vulnerable to spam, fraud, impersonation, etc... and that maybe we don't actually need them as much as we assume? Maybe we can instead share per-contact shared secrets as a form of identity?

If you haven't watched it already, I highly recommend this talk about backchannel: https://www.youtube.com/watch?v=5ClLkuaoE-o