[Forward Secrecy] Protocols for key exchange and communication

[covert-encryption]

Introduction

Covert currently implements a messaging model similar to PGP, where fixed identities (keypairs) are used for public key messaging, providing no forward secrecy.

One thing that is already provided for is the ability to reply to signed messages, as the sender key is included within each signed message itself. This eases key exchange compared to PGP, where both parties have to add each others' public keys to allow for bidirectional communication. Alice needs Bob's public key to send the initial message, but then Bob can simply reply to it, to get back to Alice. The data is there although no direct "reply" functionality is provided as of now in the app.

Ideally, we would like to have some forward secrecy, which can be accomplished by using random keys for replies, rather than one's identity directly. The random keys cannot be derived from a seed key (e.g. one's permanent ID or a seed passphrase) because then the seed could be used to break forward secrecy. Instead, they must be created on demand and the previous secrets permanently disposed once no longer needed. Signal's double ratchet protocol is useful for this and could very well be implemented within Covert.

Another approach risen by @LoupVaillant (in #2 that contains related discussion) is relying on the Noise protocol handshake schemes. This needs further investigation, in particular in the context of reply messages in hopes of also saving some bytes in message size.

ID files

The random keys should be stored in identity files, which would be specified on CLI using a new -I alice flag that could refer either directly to a filename, or by profile name to a file in a known location such as ~/.covert/id. In contrast to -i flag specifying secret keys, -I implies that the ID is in Covert's own format and that the application may read and write the ID file, where secret keys are read only.

Should Alice wish to operate pseudonymously, she would have multiple identities, possibly with one randomly created each time she initiates a new conversation. It remains an open question whether each such identity should create its own identity file, or whether we want a single file that can contain many identities (unlocked by a single passphrase or other form of authentication that Alice might be using locally). A single file for multiple IDs provides more anonymity in the event someone inspects the files on Alice's drive, so that does indeed seem like the better option, and it does not prevent still having separate files locked by different passphrases each potentially containing multiple identities. As a technical detail, these would be standard Covert archives but with all the key data stored in their index headers in MsgPack format (not as files within the archive). Potentially the same archive could also contain a message to store Alice's private notes.

Forward secrecy

The core point of forward secrecy is that at some points the keys need to be permanently disposed, i.e. removed from ID store. Signal's double ratchet does this whenever a matching message is received (so the same key can never be reused) and also whenever a message round-trip is accomplished (all past keys become void soon after that, and a new shared secret is negotiated so that even if keys were leaked earlier, no future communication can be eavesdropped, providing backward security).

The problem is that if Bob does not reply or if some of the messages get lost on the way (potentially intercepted by Mallory), Alice does not know when to delete the keys. Potentially this could be implemented via key expiry, such that with no further communication the keys would expire e.g. after two weeks.

Because Covert is not a constantly running communication app (nor intends to be one), deletion can only occur when the ID store is accessed, again making the single file ID store a more feasible option to make it less likely to keep old keys of some profile stored on one's drive for years.

The first message problem

The initial message still remains a problem even if such protocols are implemented, because the initial message still would be encrypted with Bob's key (no forward secrecy) and Alice still needs to find that key from somewhere (and ideally confirm that it actually belongs to Bob and not to Mallory who could be doing MitM). In general Alice needs some way to know that Bob exists, and needs to acquire some contact information to send the message in the first place, so in principle Bob could provide his key in the same place where his contact info is found, be that a business card or his social media profile, although we don't see PGP style key servers or web of trust as viable solutions.

The initial message not much a problem for online IM software or TLS connections that can establish a message round-trip prior to initiating any communication. Covert intends to stay compatible with offline messaging, and thus cannot rely on such initial round trip.

Rather than giving out PGP-style fixed keys, a scheme like Signal's X3DH (not directly related to the double ratchet) would be useful. In these the keys frequently change but are signed with a permanent identity key. If the key would be on Bob's social media profile, he'd need to update it frequently to maintain forward secrecy, but this needs no other software support. The system supports even one time keys, that could be implemented online with a server that dispenses a different key on each request, or even on business cards if a different key can be printed on each card. The X3DH key can be represented as a few-hundred character base64 string (shorter than PGP public key) or as a fairly small QR code, possibly together with a contact info URL.

Discussion welcome

This thread is intended for discussion and questions on these key distribution and protocol issues, in hopes of concluding on the most useful yet maximally simple protocols and practices to implement on Covert. It needs to be noted that we don't intend to establish any online services such as key servers or IM systems, although Covert be a useful component in implementation of such third party software.

[covert-encryption]

Forward secrecy built on continuously changing public keys:

Assuming that the initial message from Alice to Bob uses Bob's permanent public key, which is later breached, any initial messages sent by Alice can be leaked. Alice bundles inside each message a randomly created public key, that Bob uses in his initial response also including a randomly generated public key. Once Alice receives that response, he learns of Bob's new key and afterwards the leakage of either party's long term secret keys is no longer a concern.

The implementation cost of the above is very low, only needs to keep track of the ever changing keys in idstore but the authentication is the same as with permanent public keys, so no added complexity there. The problem is that messages expire only once a round-trip of communication is completed such that the keys are replaced, especially since messages may be lost or may be received out of order.

Signal takes the approach of only replacing the ECDH keys whenever a message is received from peer with a new key. If the peer sends multiple messages in a row, no replacing occurs, and all sent messages bundle the same key. Unfortunately this also means that the key cannot be sent in plain (ephemeral) key by Covert as it would be apparent that multiple ciphertexts contain the same initial bytes, but will take another 32+ bytes inside the message.

The current plan on forward secrecy is to use three hash chains as in Signal:

• Sending chain, advanced a step on each message sent (for message encryption key)
• Receiving chain, advanced a step on each message received (for message decryption key, matching the peer's sending chain)
• Root chain, used to derive new sending and receiving key state each time when there is a communication round-trip

The sending and receiving chains produce a sequence of symmetric encryption keys that both parties hold and that are unique to each message. The chains are based on SHA-512 and thus can only move forward, and the chain state cannot be recovered from the message keys. This allows producing message keys for the messages not yet received, and individually deleting them as the messages are received, paving a way to perfect forward secrecy. Sending keys are immediately disposed after a message has been sent, so the sender is unable to decrypt his own messages, and won't need ephemeral keys (public key system) for that. The system also restores the correct ordering of messages and shows which ones are missing, even if received in wrong order.

The purpose of the root chain is to provide post breach security by feeding in new randomness from ECDH exchanges, such that the connection will heal if one or both parties' keys are leaked, after a few messages are exchanged. A simpler implementation could omit the root chain and directly generate new sending and receiving chains from the ECDH shared secret but that could make the protocol vulnerable to quantum attacks avoided by maintaining old state in the root chain (not a very realistic risk but this design is quantum safe).

What exactly to put in the auth header is an open question that needs more consideration. The Signal protocol proposes an encrypted header format but it makes the already complex system even more cumbersome. Still, this is one option to look at. It would seem to make the auth header 64 bytes, including a random nonce, a ratchet key and one or two message number variables as well as the auth tag.

A potential problem is that when there are a lot of authentication keys to try (i.e. for each active conversation at least 20 future and some past keys to account for skipped messages), opening a message could become slow. This can be avoided by including in auth header a random sequence derived from the send/receive chains, allowing for immediate lookup of matching keys in idstore, at the cost of some more header bytes. With the Signal encrypted headers this would not be an issue as there are far fewer options to brute force.

[covert-encryption]

The double ratchet using header keys, adapted slightly from Signal spec

Alice sends an initial message to Bob using his public key and a hashed ephemeral key, as with normal Covert messages. Alice includes her public key in the encrypted auth header, and the file encryption key additionally ECDH's in Alice's public key, such that the sender is verified (to Bob but not to others).

Bob receives an unknown message and tries decoding the initial ratchet header using his public key with the ephemeral key, and once that succeeds, finds Alice's pk inside and can proceed to decrypt the message.

Key points:

1. Alice may send multiple initial messages, some of which may be lost or received in wrong order
2. The initial message first received initialises the ratchet for Bob, and it must match Alice's, so we keep the keys the same for all initial messages.
3. The ephemeral key is not used by ratchet because it needs to change for each message and also because Alice should immediately dispose the secret key, preventing ratchet update when receiving Bob's response.

Auth header prior to first ratchet reply (Alice's initial messages):

[eph:32] {[pk:32] [n:2] [f:1] [nextlen:3]} [tag:16]   # {} denotes encryption, n is the message number, f is flags

Both parties initialise the root chain with derive_symkey(b"ratchet/init", localkey, peerkey) ECDH exchange on initial communication. Note that if Bob's keys are compromised, the attacker can open all initial messages to Bob and calculate the root key, but the connection should heal as soon as Bob's response reaches Alice. This can be avoided by Bob using X3DH key rather than simple public key (to be implemented soon).

Other initialisation secrets are pulled from the root chain, and the file encryption key comes from send/receive chains as per normal ratchet operation. It needs to be noted the send and receive chains as well as header encryption keys for send/receive must be reversed on each peer. This is accomplised by Alice performing a half step update before sending the first message, so that she gets a send chain for herself, that will match Bob's receive chain once Bob does a normal ratchet step, obtaining first the receiving keys and then the sending keys. Then once Bob's response reaches Alice, she does a full step and obtains Bob's send keys as her receive keys, and it keeps updating like that each time a message round trip is completed.

The normal ratchet step, performed whenever receiving a message with a new header key, advances the root chain twice:

1. Using old locally stored key with the new peer key just received (as part of encrypted auth header). New receiving chain is then pulled.
   • Bob starts with this step, getting the same chain that Alice's half-step got for her receiving chain.
2. Generating new local key and using that for another update, getting the new send chain.

Between these two steps the peers' ratchet chains are in identical position, but otherwise one is always a root chain step ahead the other.

Once the ratchet is running, the ephemeral key is left out and instead of message number the previous chain length PN is sent. Bob's first message already uses this format:

Normal ratchet header: (used by Bob in all messages, by Alice once she receives any message from Bob)

{[dh:32] [pn:2] [f:1] [nextlen:3]} [tag:16]   # dh is Bob's randomly generated ratchet public key

Alice receives the message, tries to decrypt it with her receiving new header key (matching Bob's current header send key), using sequential nonces (starts at all zeroes, gives the message number when it succeeds). No ephemeral key is used because the nonce and the stored header keys give sufficient randomness. During the update Alice's new header keys become current header keys and new/next keys are generated for both directions.

The message numbers and the PN field allow detection and reordering of messages lost or received out of order.

The nextlen field is included to avoid having to search for the first blockstream block, and allowing it to be larger than 1 KiB, breaking away from how the other auth modes of Covert work.

In summary: the header key stays the same for any sequence of messages with no round-trip. Round-trips are detected by the peer using the next header key (all taken from the root chain) and this triggers a ratchet DH step on the receiving end. Everything other than the header key then uses the just-received new DH key, allowing for faster healing.