Chat protocol

Example

let a_sk = ed25519_dalek::SigningKey::from_bytes(&[0; 32]);
let b_sk = ed25519_dalek::SigningKey::from_bytes(&[1; 32]);
let a_pk = a_sk.verifying_key();
let b_pk = b_sk.verifying_key();

let mut rng = rand::thread_rng();

let a_m0 = b"Tu bluffes, Martoni.";
let (mut a, c0) = State::send_first::<ThreadRng>(Some(a_sk), b_pk, a_m0, &mut rng);

let (mut b, b_m0) = State::receive_first(b_sk, a_pk, &c0).unwrap();
assert_eq!(&b_m0.payload, a_m0);
assert!(matches!(b_m0.secrecy, SecrecyData::SignedAndEncrypted { .. }));

let b_m1 = "Pas sûr.".as_bytes();
let c1 = b.send(SecrecyCommand::Encrypt, b_m1);

let a_m1 = a.receive(c1).unwrap();
assert_eq!(&a_m1.payload, b_m1);
assert!(matches!(a_m1.secrecy, SecrecyData::Encrypted));

Protocol

Suppose the two parties have ed25519 key pairs and know each other's public key.

• Magic number "CHAT" (4 bytes)
• Version (1 byte)
• Metadata length (1 byte)
• Metadata (custom clear data for application and transport protocols)
• Message type (1 byte)
• Message content (depends on message type)

This protocol MUST be wrapped in an asymmetric signature protocol to ensure its security properties. Example:

• Pubkey
• Signature of CHAT message
• CHAT message

Message type

A conversation MUST begin with a first message from Alice.

Bob SHOULD answer using an established message.

Alice CANNOT send an established message until the first established message from Bob.

First message (clear)

Message type 0

• DH pubkey (32 bytes)
• Ratchet pubkey (32 bytes)
• Payload

The Diffie-Hellman Shared Secret (DHSS) is an ephemeral-static DH generated using the sender's ephemeral DH private key (corresponding to the DH pubkey included in the message) and the recipient's long-term public key (converted to x25519).

The ratchet is initialized using DHSS.

First message (encrypted)

Message type 1

• DH pubkey (32 bytes)
• Ratchet pubkey (32 bytes)
• Nonce (12 bytes)
• Ciphertext of:
  • Signature of payload (ed25519) (64 bytes)
  • Payload

DH and ratchet are used in the same way as above.

The ciphertext is the output of AES256-GCM-SIV using HKDF_SHA256(DHSS) as the key and Nonce as the nonce.

The purpose of this signature is to force the sender to give a non-denialability guarantee to the recipient.

Established message (clear)

Message type 2

• Payload

Established message (encrypted)

Message type 3

• Ratchet pubkey (32 bytes)
• Nonce (12 bytes)
• Ratchet n (4 bytes, big endian)
• Ratchet pn (4 bytes, big endian)
• Ciphertext of:
  • Signature indicator (1 byte)
  • Signature of payload (ed25519) (optional, 64 bytes)
  • Payload

The ciphertext is encrypted using the ratchet.

The signature indicator can be 0 or 1. Any other value is invalid.

Iff the signature indicator is 1, the payload's signature is included.

The purpose of this signature is to allow the sender to give a non-denialability guarantee to the recipient.

The recipient SHOULD decide whether they accept unsigned encrypted messages. There are two methods for this:

• Never use established messages.
• Show unsigned messages as invalid to the user, and use applicative protocol in custom metadata to inform the sender.

Technical choices

What we want:

• Fast (should run on smartphones)
• At least 128 bits of security
• Integrity
• Authentication
• Decent key exhaustion
• Any received ciphertext (including AEAD) could have been generated from its plaintext by its receiver without knowing the sender's secrets (i.e. a message's receiver cannot prove to anyone, except their interlocutor, that some message is authentic)
• Disclosable non-denialability for untrusted interlocutors
• Easy setup with low overhead (suitable for high-latency protocols: one protocol message is one user message)
• Forward secrecy

Not goals but nice to have:

• Side-channel resistance
• Postquantum resistance
• Hardware fast
• Constant time

Unsolved questions

• Should the encrypted signature contain more metadata?
• What public metadata are needed?
• Can n and pn be used for applicative purposes?
• Can we benefit from AD?
• When is wrapping signature really needed?
• How to make the protocol reflect that one party wants to end the conversation?
• Can non-denialability be publicly verified on an encrypted message?
  • i.e. the transport layer could verify that an encrypted message contains a valid signature, so that the recipient can choose to disclose the message. This could be done using fancy things like zk or by signing the ciphertext and making the signature public. Then the recipient can disclose the private key.
• Can a conversation be anonymous to the transport layer?

TODO

• Use varint for n and pn
• Find a good name
• Reimplement double ratchet to simplify, optimize, and avoid depending on postcard

Sources

• https://signal.org/docs/specifications/doubleratchet/
• https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme
• https://soatok.blog/2020/07/12/comparison-of-symmetric-encryption-methods/

License

Support me via LiberaPay

GNU AGPL v3, CopyLeft 2024 Pascal Engélibert (why copyleft?)

This program is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free Software Foundation, version 3 of the License.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details.
You should have received a copy of the GNU Affero General Public License along with this program. If not, see https://www.gnu.org/licenses/.