What advantage does Signal protocol have over basic public key encryption?

[jamesd at echeque.com]

On 2021-01-25 07:02, David Barrett wrote:
> Hi all, I'm the CEO a company called Expensify, developing a new open
> source chat application at https://Expensify.cash.  I was pretty
> prolific on the p2p-hackers mailing list back in the day, but this is my
> first post to Cypherpunk, so... hi!
> 
> I'm writing because I've read a bunch of overviews of *how* the protocol is
> designed, but I haven't really seen good sources explaining (in a
> dumbed-down enough manner for me to follow) *why* it was designed that
> way.  In general, I'm trying to understand the reasoning behind the Signal
> protocol in terms of what real world attacks each of its features defends
> against, because on the surface it seems _really_ complicated in order to
> protect against only a very narrow range of attacks.
> 
> However, I imagine every bit of that complexity has a purpose, and thus I
> figured this was the right place to try to get to the bottom of that
> purpose.  If you have some other link that you think does a great job
> breaking it down, I'm all ears!  Until then, here are some questions I'd
> love your help with:

> 
> 1) This is perhaps an obvious question (I've got to start somewhere, after
> all), but what is the downside of the simplest possible solution, which I
> think would be for all participants to publish a public key to some common
> key server, and then for each participant in the chat to simply re-encrypt
> the message N-1 times -- once for each participant in the chat (minus
> themselves) using each recipient's public key?


This does not work in itself, because what assurance do you have that
you are seeing the same public key as everyone else?

They could tell Ann that Bob's key was a key that in fact belonged to
antifa, and tell Bob that Ann's public key was a key that in fact
belonged to antifa.

What assurance does Bob have that Ann is seeing the same "Bob's key" as
Ann is seeing.

To solve this you need a cryptographic primitive known as a reliable
broadcast channel, which is typically implemented as a blockchain or
something similar.

Jitsi implements this, but I am not aware of anyone else implementing
it.  With Jitsi, Ann's software is guaranteed to see the same list of
public keys as Bob's software.

This is a distributed consensus problem, and distributed consensus is hard.

I don't know if Signal's solution solves this problem.  I have not
checked them.

> 2) I would think the most significant problem with this ultra-simple design
> is just performance: asymmetric encryption is just too expensive in
> practice to use for every single message, 

Nah, because its cost in human generated messages is absolutely
insignificant, particularly if you are using ed25519 or, better,
ristretto25519

Secondly you don't need to use it on every single message.

Assume we have solved the public key distribution problem, perhaps the
way Jitsi does it, and everyone is seeing the same set of public keys.

When you join a room, you submit a transient public key to each of the
participants in the room, and they respond with a transient public key,
constructing a shared secret between each pair of participants.

You then use symmetric encryption with that shared secret.  And then,
over the encrypted connection, set up a shared secret based on both the
durable public and private keys, and the transient keys.  So you now
have, for each pair of participants, a shared secret that depends on
both parties durable and transient keys.  Possession of the shared
secret proves you know the secret key corresponding to your public key,
and you get perfect forward secrecy because the shared secret and the
transient keys are abandoned when you leave the room.

Assume Bob's secret key is b, and his public key is B, and similarly
Carol's secret key is c and her public key is C.

b*C=c*B.  So, to construct a shared secret that can be used for
symmetric encryption, Bob calculates b*C and Carol calculates c*B

Suppose that Bob's transient private and public keys are b and B, and
his durable private and public keys are _b_ and _B_, and similarly for
Carol.

Then to construct a shared secret that depends on both the transient and
the durable keys, Bob calculates (_b_ + b)*(_C_ + C), and similarly
Carol.  (But this is only safe if both Bob and Carol have first proven
that they also know the shared secret b*C = c*B, by first successfully
decrypting and encrypting stuff symmetrically encrypted to that secret)