Cryptography in VpnCloud
This document explains the use of cryptography in VpnCloud.
Although VpnCloud is based on stateless UDP, it maintains state associated with its peers. Peers are distinguished by their UDP/IP address. The state associated with a peer can be considered a stateful connection.
VpnCloud aims to protect all sensitive data and especially all payload end-to-end. Third parties, with or without control over network in between the endpoints should not be able to read the payload, or manipulate the data in or inject data into the data stream.
VpnCloud tracks two kinds of state on connections: The initialization state and the crypto state of established connections. These states usually represent two phases that a connection undergoes: once the initialization is finished, it becomes an established state that can be used to transfer payload. However, there is no restriction on whether both states can be present at the same time. Peers can re-initialize an established connection if they want/need to. The payload data will be handled by the established state until the initialization is completes and becomes the new established state.
Every VpnCloud node is configured with the following information:
- An ED25519 key pair (Sk, Pk) consisting of a private key (Sk) and a public key (Pk)
- A list of trusted public keys (Tk_1..n)
- A list of supported symmetric algorithms (Algos). Note that "no encryption" is also considered as a symmetric algorithm that can be part of the list if the node accepts unencrypted connections. The node benchmarks, all supported symmetric algorithms and stores the measured speed for later use.
Since setting up a network consisting of many nodes becomes a tedious task if one has to create key pairs for each node and exchange public keys as trusted keys, VpnCloud supports deriving this configuration from a password. If the user specifies a password instead of a key pair, a 256 bit seed is generated from the password using the PBKDF2_HMAC_SHA256 method with 4096 rounds. The key pair (Sk, Pk) is then created from this seed. If the user does not specify any trusted public keys Tk, the own public key is used as trusted key (Tk=[Pk]). In sum, that means that all nodes configured with the same password all use the same (Sk, Pk) key pair and trust each other.
The connection initialization protocol is used to exchange all information needed to bootstrap and setup an encrypted connection. This information includes the identity of the remote peer, its supported symmetric algorithms and their speeds, as well as an initial shared symmetric key. It is crucial that all messages are signed using a key that the remote peer trusts, so that the transferred information is authenticated. Also it is important, that during this initialization the confidentiality of the information and privacy of the nodes is protected.
The initialization protocol consists of 3 messages called Ping, Pong, and Peng. The node that starts the initialization (called node A) sends a Ping message to the receiving node (called node B). Node B then replies with a Pong message, to which node A replies with a Peng message.
The messages contain the following common information:
- The stage of the message, i.e. Ping, Pong or Peng.
- The salted hash of the public key Pk of the sender of the message.
- The salted hash of the node id of the sender of the message.
- A cryptographic signature of the whole message, signed with the senders private key Sk.
Also the messages contain additional information depending on the stage of the message:
- An ephemeral ECDH public key (only on Ping and Pong).
- A list of supported symmetric algorithms together with the speeds of those algorithms (only on Ping and Pong).
- Encrypted initialization payload (only on Pong and Peng).
When receiving a protocol message, that message is first verified. If the format of the message is incorrect, the message is discarded. The salted hash of the senders public key, is compared to the hashes of all trusted keys of the receiver (using the same salt) to identify the senders public key. If no public key can be matched, the message is discarded as being from an untrusted source. Finally, the message signature is verified using the identified public key of the sender. If the signature is invalid, the message is discarded as being tampered with. Only valid messages signed from trusted nodes can pass this verification step.
As a second step, the salted hash of the senders node id is compared to the receivers node id by calculating the hash of that node id using the same salt. If the node ids match, the initialization is aborted as the node is attempting to connect to itself.
In the third step, the stage of the message is compared to the expected stage of the next message:
- If the the received stage is Ping and the expected stage is Pong, that means that both peers sent a Ping message and both consider themselves to be the initiator node A. To sort this out, the node which sent the smaller salted node id hash (when compared as binary), resets its state and assumes the role of node B. The node which sent the greater salted node id hash, discards the received Ping message and waits for a Pong reply to its own Ping instead. When comparing the salted node id hashed, both nodes will reach the same conclusion on who is node A and who is node B. Note that this comparison only happens when both nodes disagree on their roles and both sent a Ping message. Otherwise, the initiator could very well have a smaller salted node id hash when the receiver has not sent a Ping message and therefore accepts the role of node B.
- If the received stage is not the expected stage and a message has been sent previously by the receiver, that message is repeated and the received message is discarded. If no message has been sent by the receiver before, then the initialization is aborted as the node received a non-Ping message as first message, which can not be recovered.
After the third step of message processing, the message stage matches the expected next stage. On a mismatch, the processing has either been aborted by discarding the message or the expected stage has been changed to the one that has been received.
The initialization is started by one node by sending a Ping message. To create that message, the sender creates an ECDH key pair, stores the private key and adds the public key to the message. It sends the Ping message and sets the next stage to Pong.
When receiving a Ping message, the receiving node creates an ECDH pair of its own. It uses the private key together with the senders public key from the Ping message to calculate the initial key material and use it for the symmetric crypto core. The node then encrypts the initialization payload with the symmetric crypto core. The node creates a Pong message containing its own ECDH public key as well as the encrypted init payload data. The node then sends the Pong message and sets the next stage to Peng.
When receiving a Pong message, the receiving node uses its stored private key together with the senders public key from the Pong message to calculate the initial key material and use it for the symmetric crypto core. The node uses the crypto core to decrypt the senders init payload from the Pong message. The node then encrypts its own initialization payload with the symmetric crypto core and sends it as part of a Peng message. The node then passes the senders init payload back to the application and records the state as Pending close.
When receiving a Peng message, the receiving node uses its crypto core to decrypt the contained init payload and pass it on to the application. It then finishes the initialization process.
A node will stay in the Pending close state for 60 seconds until it closes the initialization process. This will allow the peer to retransmit the Peng message when it has been lost.
Both nodes store the last sent message in order to retransmit it when it has been lost. Lost messages are detected on the sender of the message when the expected reply is not received within one second. In such a case, the node will retransmit its last message. When a node receives an unexpected message, it also retransmits its last sent message.
If a Ping message gets lost, the sender will detect it after a second and resend it. The receiver will not notice that the first message has been lost and process it normally.
If a Pong message gets lost, both the sender and the receiver (sender of the Ping) will detect it after a second and resend both the Ping and Pong messages.
If a Peng message gets lost, the receiver (sender of the Pong) will detect it after a second and resend the Pong messages, which will trigger the resending of the Peng message.
Symmetric algorithm selection
VpnCloud offers several encryption algorithms to use in the symmetric encryption. For each of the algorithms, each client determines the speed by running a small benchmark on startup. During initialization, both peers send the supported algorithms as well as the measured speeds along with the Ping and Pong messages. Both peers then independently choose that algorithm that is fastest on the slower peer, i.e. that will yield the overall fastest connection.
The algorithms currently supported are:
- AES-128 in GCM mode
- AES-256 in GCM mode
- ChaCha20-Poly1305 (RFC 7539)
ECDH key agreement
The initialization protocol uses ED25519 to create a public/private key pair and calculate the first ephemeral symmetric key. The key pair is generated based on random data that is discarded after deriving the ephemeral key.
Due to the ECDH properties, both peers will generate the identical symmetric key. To prove and test that the symmetric encryption works, the initialization payload is encrypted with the symmetric crypto core.
The symmetric encryption is used to encrypt all messages except for the initialization messages. It is based on 4 slots, that each contain a different symmetric key and a nonce counter. Each message contains an id of the slot that it is encrypted with so that the receiver can use the correct key.
The symmetric encryption is based on the invariant, that both peers agreed on the same encryption method and their role in the communication (initiator of the connection or not), and that the keys of all slots that are used for sending are known to both peers.
The message format is pretty simple:
- Each message starts with one byte that contains the slot id. For initialization messages that do not use the slot based symmetric encryption, this byte contains the value
0xffand serves to distinguish initialization messages from other message types.
- After the slot id byte, 7 nonce bytes follow. Those bytes contain the lower 7 bytes of the 12 byte nonce used for encryption. The upper bytes of the nonce are not encoded and assumed to be zero, except for the most significant bit of the highest byte which is assumed to be 1 for the connection initiator and 0 for the other peer.
- After the 8 byte header, the encrypted message follows. The message ends with and includes an authentication tag depending on the used encryption method.
The receiver of such a message reads the slot id and uses the key in the corresponding slot together with the nonce data to decrypt the message. The authenticity of the message is automatically verified during decryption using the authentication tag contained at the end of the message data.
Both peers start with randomized nonces for all slots, containing random bytes for the lower 6 bytes and the upper 6 bytes being zero, except for the most significant bit of the highest byte which is set to 1 for the connection initiator and 0 for the other peer.
On each message that is sent, the nonce is incremented by 1 and sent along with the message as described. Since only 7 of the 12 bytes are encoded in the message, the total nonce space is much bigger than the valid nonces (those that can be encoded using the 7 bytes). That means, a peer sending lots of messages will first run out of valid nonces before the nonce wraps around. Since the highest of the 7 bytes is initialized as 0 and only the other 6 bytes are randomized, most of the valid nonce space is available for use regardless of the random start value.
In order to be resistent against replay attacks but allow for reordering of messages, the symmetric encryption uses nonce pinning. For every slot, both peers track the biggest nonce received so far. Every second, the biggest nonce value one second ago plus 1 becomes the minimum nonce that is accepted for that slot. That means, that reordering can happen within one second but after a second, old messages will not be accepted anymore.
In order to increase security by only using keys for a limited time, the keys in the slots are rotated periodically. A key rotation protocol is used to negotiate new keys using the ECDH protocol and coordinate their usage via the slots.
During regular operation, the 4 slots are split among the two peers. One peer uses slots 0 and 2 for sending and the other peer uses slots 1 and 3. Both peers only use one of their slots at a time (active slot).
The plain ECDH handshake consists of 3 steps:
- The first peer creates a key pair and sends the public key to the second peer (proposal).
- The second peer creates a key pair, uses the received public key to derive a symmetric key, stores that key in a slot, and sends its own public key to the first peer (confirmation).
- The first peer receives the public key, derives the same symmetric key, stores that key in a slot, and uses that slot from now on to send messages.
The messages of the actual key rotation protocol contain a proposal and a confirmation of different ECDH handshakes. That means that every message proposes a new key and confirms a previously proposed key (all messages except the first one).
All messages of the key rotation protocol are encrypted and authenticated using the currently active encryption key. That means, that the negotiation of new keys is fully protected by the previous keys. Since ECDH is being used, breaking one key only allows the attacker to read and manipulate the communication for as long as the key is valid. It does not enable an attacker to obtain any new keys negotiated in the key rotation. In order to perform a man in the middle attack on the key rotation, an attacker would need to break a key and use it while it is still active which is practically impossible given the key length and rotation frequency.
Both peers send out messages periodically. Each of those messages confirms the key previously proposed by the remote peer and proposes a new key. Whenever a peer sends out a confirmation, it stores that key in a slot but does not use it. Whenever a peer receives a confirmation, it stores that key in a slot and uses it, knowing that the remote peer knows it too since it has confirmed it.
Each message contains a message id. The peers start with different starting ids 0 (initiator) and 1 (other peer). Whenever a new key is proposed, the message id is incremented by two, so both peers will never use the same ids.
To recover from any message losses, the peers follow some simple rules:
- Peers will only propose a new key if their previous proposal has been confirmed. Otherwise, they will repeat their previous proposal.
- Peers will confirm the latest proposal, they have received.
Connections are initialized with the key material and encryption method, that has been negotiated in the initialization protocol. One of the peers starts the key rotation by sending a message that proposes a new key but does not confirm any key. This is the only time that both peers use the same key for encryption. After one key rotation cycle, both peers will have switched to different keys. Also this is the only time in the rotation protocol, that no key is confirmed.