Is it possible to implement the Signal Protocol without a server? My question is regarding the Signal Protocol[1]. Is it possible to implement the protocol securely, without a server?

(I have no particular motivation for the question other than to understand better how the Signal Protocol works, what kind of trust I give to the server, and what attacks are possible if the server can be hacked or if server &lt;> client communication can be monitored).

Imagine a room with a big whiteboard (or a chalkboard). This is our "server", but anyone can enter the room at any time and make any modification they want. The goal is for Alice to initiate an encrypted, asynchronous conversation with Bob by writing messages on the board.

My understanding is that neither XEdDSA/VXEdDSA nor the Double Ratchet component of the protocol are affected by the board being public. Is that correct?

That leaves the other two components of the protocol.

X3DH

As stated in X3DH Section 4.7, "Server Trust"[2], the following properties are true when using a server, and would still be true using a whiteboard:


The server can cause communication to fail by refusing to deliver messages (someone can erase the board).
The server can refuse to provide pre-keys, or somebody can drain pre-keys (erase them from the board), reducing forward secrecy.


What are the other attacks which would be made possible by giving anyone access to the board?

Sesame

As stated in Sesame Section 6.3, "Protecting Server Communications"[3]:


  If an attacker is able to impersonate a victim device when authenticating to the server, the attacker could fetch messages being sent to this device. The attacker would not be able to decrypt these messages, but would learn sender UserIDs and DeviceIDs.


This would obviously be impossible to prevent on the whiteboard, so everyone would be able to see who is communicating with whom.

Sesame also relies on server &lt;> client communication being encrypted and authenticated. From the same section:


  Communication between devices and servers should be encrypted and authenticated. This limits the amount of metadata that is exposed to eavesdroppers, and makes it harder for third-party attackers to perform active or passive attacks on device-to-device communications.


What attacks would be made possible by giving anyone access to the board?

Conclusion

As best I can tell, the only reduction in security comes from the fact that anyone would be able to monitor who is talking to whom.

Forward secrecy could also be reduced by eliminating pre-keys. Would that completely eliminate forward secrecy?

How could cryptographic deniability be affected?

Have any similar protocols ever been developed which would give the same properties as the Signal Protocol without trusting a server at all (e.g. you could literally do it on our whiteboard)?

Thanks, and I hope you have fun thinking about it!

[1] https://www.signal.org/docs/

[2] https://www.signal.org/docs/specifications/x3dh/#server-trust

[3] https://www.signal.org/docs/specifications/sesame/#protecting-server-communications
Expanding from the whiteboard example as that is just a transparent central server.

This is not an issue although with a different model, you just need to decide which properties you care about.


Without a trusted entity maintaining the lookup of verified phone numbers to public keys, you will need to rely on another means. I recommend using the public key directly to effectively null out this layer while keeping it orthogonal such that lookups may exist in the future.
Without a trusted store-and-forward service you'll need to establish a rendezvous point such a DHT or wrap another chat protocol that knows nothing about Signal. Wrapping another protocol can solve (1) opportunistically, although the service (like Signal) may return keys it controls and is just as trusted and centralized.
If you do not have a store-and-forward service then the signed prekeys are redundant. This does not reduce forward secrecy, but it does require the 3DH handshake to occur before messages may be sent. So no 0-RTT semi-forward-secure messages.
If delivery is synchronous and ordered you can simplify double-ratchet.
You may use an anonymity network such as Tor to hide who is talking with whom. Each user could be their own ed25519.onion service. But if they are, then double-ratchet and 3DH are both redundant and we've got ricochet.im.


Social graphs and deniability depend on the above choices. I.e. ricochet.im hides the social graph great using onion routing; if you want better, you'll need a mixnet. Or if you forward messages over some existing service, they can see the social graph prove you communicate and record the ciphertexts forever to verify any revealed keys and plaintexts.



On another note: you might want to take a look at matrix.org's libolm, a double-ratchet implementation that does not assume server cooperation.