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

[Karl]

Hello!

Don't trust anything anyone says here unless you find somebody who
says the opposite thing, and judge other statements from both people
to see whether they are saying true stuff or not.

I'm an ex-activist who posts during his delusional psychotic breaks,
not a cryptographer.

On 1/24/21, David Barrett <dbarrett at expensify.com> 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!

Punk's comment on javascript has merit.  It's hard to secure
javascript.  It's gotten easier, but it's still designed for the web,
where everything you do is handed to you by a stranger.

> 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.

It's been a while since I used signal, but it did these things amazingly well:
1. getting cryptography into a solid UI that anybody can use.
ease-of-access is cryptography's biggest problem.
2. open source and demonstrating transparent honesty about open source
going forward.  most attempts fail this.
3. used modern cryptographic research to produce something that is
above and beyond the current norm.  because research is always
advancing, this should happen with every product.
4. perfect forward secrecy.  addresses the issue with pgp where future
advancements decrypt all your messages
5. metadata encryption.  pgp does not do this
6, the ratchet protocol produces a hash of previous messages that
provides for detection of dropped data, among many other things.  pgp
does not do this.
7. the software is maintained and improved.  pgp does not do this.
8. other stuff, i dunno.

my focus was on #6.  it's a big hole in pgp to not have a way to
verify a message was read when replied to, in this modern environment.

> 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:

I think if you break your questions into smaller parts, and ask those
parts in ways that demonstrate you have an understanding of
cryptography already somewhat, more people who are busy doing their
jobs may take time to answer you, but really clear security is a topic
where everyone lies for some reason, it seems.

> 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?

Basically this approach has a huge number of problems that a real
cryptographer would enumerate with extensive technical words.  Some of
them are plugged in signal.  For example, the 'forward secrecy' which
makes it hard to decrypt archived information when the cipher is
compromised, later.  In your example storing your message provides for
straightforward decryption when technology advances.

> 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?

Is performance really an issue when these algorithms were designed so
long ago?  Is this something addressed by the algorithms chosen in
Signal?

I think occasionally saying the word 'key rotation' is different from
the concept of a 'ratchet protocol'.  If you rotate your keys every
message, then I would start reviewing the details of the protocol to
see what other differences are.

> 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.

The hard work is effective on the network level.  Other people on the
same networks can capture the data in transit, and try to decrypt it.

> 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.

Not really an answer to your point, which seems similar ot the one
before, but one of the things Signal does is it _gets the code and
protocol out there_.  It is totally possible to keep your key on an
airgapped device in a shielded case you chain to your neck, and
communicate with people's mobile phones in a secure manner by moving
protocol data in and out of that box when you enjoy, without them ever
having to set up PGP.  Other people can build even more secure
projects, on top of the code that already exists.

> 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.

Decryption of destroyed messages is a big thing that signal deters.
Journalists can get seriously physically injured when that happens.

> 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

I haven't visited your site, I'm sorry!