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

[David Barrett]

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?


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, especially given the O(n) cost of
re-encrypting for every single recipient.  Accordingly, the vast majority
of the complexity of the Signal protocol is really just a performance
optimization exercise to securely create (and rotate) a shared symmetric
key that enables high-performance encryption/decryption.  Is that right?
Said another way, if asymmetric encryption had adequate performance for a
given use case, would that obviate most of the advantage of the Signal
protocol?


3) The other problem with the ultra-simple design would be a lack of
forward secrecy: if anyone's private key were compromised, all historical
messages sent to them could be decrypted (assuming the attacker had stored
them).  But even with the Signal protocol, if someone's local device were
compromised (the most likely way for an attacker to get the private key),
they're screwed anyway, in two different ways:

a. The act of compromising the private key would likely ALSO compromise
nearly all past communications.  So all that hard work to rotate historical
keys is kind of pointless if the messages themselves are compromised on
device.

b. If the private key itself (which is *only* stored on the device) were
compromised *without* also revealing the messages stored on that same
device (though how this would happen I'm struggling to understand), then an
attacker could still decrypt all past communications if they had a perfect
record going back to the start.


4) So in summary, is it safe to say that the primary real-world advantages
of the Signal protocol over the super-basic solution are:

a. achieve high performance encryption using frequently rotated symmetric
keys, and

b. prevent an attacker who has compromised the device AND has a partial
record of communications from decrypting messages that are no longer stored
on that device.


Is that the gist of it?  Again, these are real high level questions, so I
appreciate your patience with me!

-david
Founder and CEO of Expensify
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/html
Size: 4119 bytes
Desc: not available
URL: <https://lists.cpunks.org/pipermail/cypherpunks/attachments/20210124/b634c567/attachment.txt>