The Signal Protocol brought secure end-to-end encrypted messaging to over one billion Internet users. More broardly, modern public key cryptography is fundamental to the security of the Internet. However, there are still plenty of unsolved challenges in deploying usable, end-to-end encryption to the masses.
One challenge was framed succinctly by Matthew Green, information security professor at John Hopkins University:
My 90+ y/o uncle uses Messenger on Safari and phone. How do I get him provisioned with keys without freaking him out?
We introduce SUGAR (Scalable, Unified Group Agreement Routine), a new protocol for provisioning identity keys across multiple devices for use in end-to-end encryption protocols, such as Signal, OMEMO, or GnuPG, with the following constraints and design goals:
- SUGAR must work even if most of your other devices are offline.
- SUGAR must provide forward secrecy and graceful revocation.
- SUGAR must provide forward authenticity.
- The strength of the encryption keys used in SUGAR must not depend on the security of any user-chosen passwords.
- SUGAR must be compatible with extremely simple user experiences.
SUGAR combines three separate cryptogpraphic components to accomplish all of these goals:
- Public-key encryption. Every device has its own keypair that never leaves the device.
- Digital signatures, for authorizing the addition and revocation of new device keys.
- Merkle trees, more similar to Certificate Transparency than Bitcoin, which serve to provide an audit trail to any keys added/removed.