Multiparty Protocol Specification - Gordin/cryptocat GitHub Wiki

Version 2.3.6 (Draft) - 27/11/2013

1. Introduction

The protocol is developed with the following design goals:

  • Provide a portable encrypted chat environment made for use in web browsers and other media over XMPP.
  • Provide the ability for multi-party chat (more than two parties.)
  • Provide asymmetric key encryption with forward secrecy from chat to chat.
  • Confidentiality and public key authentication.

Note: Cryptocat software currently uses the Multiparty Protocol only for group conversations. Private (one-to-one) conversations are encrypted using the Off-the-Record protocol (OTR). [1] The Multiparty Protocol does not provide deniability. It is meant to be superseded by the multi-party version of the OTR protocol.

This specification is released under the GNU Affero General Public License. [2]

2. Cryptographic Primitives used

  • AES-CTR-256 with randomized IV for data encryption and decryption.
  • Curve25519 for Elliptic Curve public key generation.
  • SHA-512 for generating 512-bit message authentication codes, shared secrets, fingerprints and message tags.
  • HMAC-SHA512 for message authentication. (Encrypt-then-MAC)

3. Definitions

User: A person N accessing a chat with a specific nickname nickN, a key pair privateKeyN publicKeyN, and a fingerprint fingerprintN.

Nickname: A user N's nickname nickN identifies them within the chat. Nicknames can only be 1 to 16 lowercase alphanumeric characters.

Private key: A user N's private key privateKeyN is composed of 32 randomly generated bytes. See §4 "Key Generation". It is used for shared secret negotiation as described in §6 "Shared Secrets".

Public key: A user N's public key publicKeyN is generated as described in §4. It is used for shared secret negotiation as described in §6. Once a user leaves a chat, its public key is discarded from the records of other users.

Shared secret: A user N's shared secret sharedSecretNM is a 64 byte (512 bit) random integer negotiated between two parties (N and M). The first 256 bits of a shared secret are used to encrypt and decrypt ciphertexts to and from another user M, while the last 256 bits are used to authenticate those ciphertexts through HMAC-SHA512 (Encrypt-then-MAC) as described in §8 "Message Authentication". Shared secrets are discarded when the associated party leaves the chat.

IV: A 16 byte value consisting of a 12 byte random nonce followed by a 4 byte counter incremented once for each block within a single ciphertext. IVs are never used for more than a single encryption operation by any party within a conversation. An IV array is maintained client-side through a conversation to protect against replay attacks and to ensure that the 12 byte random nonce and 4 byte counter is never re-used.

IV array: An array of all previously usedIVs is maintainted through the conversation. This array contains all the values of the IVs associated with valid received and sent messages. This array acts as a lookup table for the client to ensure that no replay attack is possible and no IV can be re-used by accident.

HMAC: a ciphertext's HMAC is defined as a MAC of the associated ciphertext. It is generated with the 256 last bits of sharedSecretNM as their key.

Tag: a tag is an integrity hash used to ensure all parties receive the same plaintext for a given message object. It is created and appended to the message object it refers to.

Chat: A chat session (or "chat room") that contains one or more users, identified by a unique chat name matched by the regular expression ^[a-z0-9]{1,20}$.

Message: A message being sent by user A to a chat with users A, B and C would be a JSON object structured as follows: {"type":"message", "text":{nickB:{"message":ciphertextB,"iv":ivB,"hmac":hmacB}, nickC:{"message":ciphertextC,"iv":ivC,"hmac":hmacC}}, "tag":tag}. All binary data (ciphertexts, IVs and HMACs) is encoded as Base64 when sending. See §9 for more information.

4. Key Generation and Agreement

Cryptocat relies on the Curve 25519 key agreement scheme. [3]

Generating the privateKey relies on a cryptographically secure pseudo-random number generator.

Each user's privateKey is stored within her/his Cryptocat client and is never shared. The user's publicKey is then generated:

// Generate public key (Curve 25519 Diffie-Hellman with basePoint 9) myPublicKey = Curve25519.ecDH(myPrivateKey);

A user A may her/his public key to B using a JSON object formatted as follows:

{"type":"publicKey", nickA:{"message":publicKeyB}} where publicKeyB is encoded using Base64.

Once a user receives another user's public key, s/he must send her/his own public key in return. Thus, user A requests user B's public key merely by sending her/his own public key.

Alternately, a plain public key request can be made by sending the following message:

{"type":"publicKeyRequest", nickA:{}}

In this case, both key request and reply messages are not encrypted and do not include an HMAC or tag.

5. User Authentication

Cryptocat clients can generate public key fingerprints for each other user using the following technique. In this use, the SHA-512 value is represented in hexadecimal.

fingerprintN = SHA-512(publicKeyN).substring(0, 40)

Users can verify someone else's identity simply by confirming his/her fingerprints over a trusted out-of-band channel (which may be public, but difficult to impersonate) such as a telephone.

6. Shared Secrets

Each two parties use a sharedSecret to exchange and authenticate messages between themselves. Shared secrets are sensitive and should never be exposed.

In a chat between Alice, Bob and Carol, Alice uses the following formula to establish her shared secret with Bob:

sharedSecretAB = SHA-512(scalarMult(privateKeyA, publicKeyB))

And the following formula to establish her shared secret with Carol:

sharedSecretAC = SHA-512(scalarMult(privateKeyA, publicKeyC))

Bob similarly calculates sharedSecretBA and sharedSecretBC. Carol also creates sharedSecretCA and sharedSecretCB.

Alice uses sharedSecretAB to communicate with Bob, while Bob uses sharedSecretBA. Thus sharedSecretAB = sharedSecretBA since:

scalarMult(privateKeyA, publicKeyB) = scalarMult(privateKeyB, publicKeyA)

The first 256 bits of sharedSecret are used as the encryption key for AES-CTR-256 operations, while the last 256 bits are used as the key for HMAC-SHA-512 operations.

7. Messaging

Messages are formatted in a JSON format. See the Message definition in §3 "Definitions". 64 random bytes are added to the end of the message before it is encrypted. This is done to prevent bruteforcing of a message tag for a short or guessable message.

The message is then encrypted using AES-CTR-256 with the first 256 bits of sharedSecret as the encryption key. The IV is composed of 16 bytes: 12 bytes that are randomly generated, followed by 4 bytes acting as a counter, incremented once per block. Different IVs are used to encrypt the same message for different recipients. The ciphertext and IV are both communicated in Base 64 format.

In order to prevent replay attacks, recipients keep track of all received IVs in a client-side IV array and drop messages that reuse an IV. Sender clients should also make sure to never reuse IVs while encrypting.

If a received message was not encrypted or sent for every party in the chatroom, for any reason, the recipient must be notified, with a warning, that the message was not properly sent to certain parties. The message is still displayed, with this warning, to the recipients to which it was sent. Additionally, if the sender could not encrypt the message due to not having a certain recipient's public key, the sender's client should also warn them that the message could not be encrypted to that particular recipient.

8. Message Authentication

HMACs are generated by running the concatenation of the ciphertext-IV pairs for every party in the conversation (including the sender) : ciphertextAlice || IValice || ciphertextBob || IVbob || ciphertextCarol || IVcarol || ... (arranged by sorting the recipient nicknames lexicographically) through HMAC-SHA-512. The sender N uses the last 256 bits of sharedSecretNM as the HMAC key for the ciphertext sent to the user M. They are stored inside the message's text object, which is part of the transmitted JSON. HMACs are stored and communicated in Base 64 format.

Then, the message tag is calculated by hashing the plaintext concatenated with the HMAC of every recipient: plaintext || HMAC-SHA512alice || HMAC-SHA512bob || HMAC-SHA512carol || ... through 8 passes of SHA-512. It is stored inside the message's tag object, which is part of the transmitted JSON. Message tags are stored and communicated in Base 64 format.

Upon the successful verification of the HMAC, the message is decrypted by the user N using the first 256 bits of sharedSecretNM relative to the sender M. If the HMAC check fails, the decryption fails silently, the message is discarded and an error is logged to the local console.

Once the message is decrypted, the plaintext is verified against the message tag. This is done by doing 8 passes of SHA-512 to the concatenation of the plaintext (including the random padding) and all HMAC plaintext || HMAC-SHA512alice || HMAC-SHA512bob || HMAC-SHA512carol || ... If the message tag check fails, the message is silently discarded and an error is logged to the local console.

9. Conversation Workflow

Consider an empty chat room R.

  • User A joins R.
  • User B joins R. A's Cryptocat client automatically asks for B's public key as described in §4 "Key Generation", and vice-versa.
  • Once public keys are exchanged, fingerprints are calculated as defined in §5 "User Authentication".
  • Shared secrets are then calculated as described in §6 "Shared Secrets".
  • Message exchange can now begin as defined in §7 "Messaging".
  • User C joins R. C's Cryptocat client automatically sends its public key to A and B in two separate public key messages. A and B do the same.
  • Once A, B and C all have each other's shared secrets, normal messaging may continue.

10. Endnotes

Special thanks to Jacob Appelbaum, Joseph Bonneau, Daniel "koolfy" Faucon, Arturo Filastò, Meredith L. Patterson, and Marsh Ray for their helpful comments and insight.

11. References

[1] http://www.cypherpunks.ca/otr/
[2] https://www.gnu.org/licenses/agpl-3.0.html
[3] http://cr.yp.to/ecdh/curve25519-20060209.pdf