Tyler Weitzman

“ Namely, suppose that each time Alice sent Bob an encrypted message, Bob then generated a new public-key pair, replied to Alice with his new public key, and the next message from Alice to him would use the new public key. In this fashion, even if the first 3 messages get compromised, any new messages would still be secured (break-in recovery) ; and if today’s key was compromised, all the old messages were encrypted with old keys that may have been deleted by now (forward secrecy) . Each generation of a new public-key pair would be considered a ratchet step. ”

“ Even the Diffie-Hellman key exchange demonstrates the mechanics of a ratchet step in that it relies on the fact that it is difficult to take the discrete log of a generator put to a power, so the function is effectively one way (under the appropriate group) .
Indeed, the Diffie-Hellman exchange algorithm could rather naively be used to achieve forward secrecy and break-in recovery. ”

“ This method of message encryption is currently one of the most popular methods for message encryption in the world, with more than 2 billion users’ messages being encrypted using this scheme on WhatsApp’s messaging platform, which uses the Signal protocol.
Security Features Below I will define more formally our desired features of forward secrecy and break-in recovery. In general, the best practice for defining security in cryptography is by describing an attack game where a challenger encrypts data and provides it to an adversary who wishes to gleam information from the encrypted data. ”

“ In practice, the way Signal uses this idea is in combination with the idea of a chain generated from a key-deriving function. A key deriving function is a function which derives a seemingly random function from an input (a simple example would be a collision-resistant hash function like SHA256) . The symmetric key continues to go through this function to generate the next one, while then also being combined with new Diffie-Hellman values being generated with each message as described above. ”

“ Finally, since both of these keys reduce to elements in themselves, they can now be used as private keys in a meta-Diffie-Hellman computation of , the shared key of the entire tree.
With any such structure, and one that may soon be rotating keys using a ratchet step, we aim to fulfill the following
Definition 3. Tree invariant
Each node represents a secret that is only known to its children (and recursively to those children’s children) . In such a way, the root is by induction always supporting a key known to every group member. Even as node values change this property remains unchanging. ”

“ The state space is an addition on a standard encryption scheme and will allow these features to exist. As described in regards to Signal’s Double Ratchet step, this state can include information about the chain of derived keys or the new Diffie-Hellman key information. In the case of a tree structure, the state might represent the current values and nodes of the tree structure. The state could at its simplest be a simple counter of natural numbers counting the number of total messages sent between Alice and Bob. ”

“ Likewise, an add operation becomes simple to do, similarly equivalent to a new node performing an update, though, since they are not yet part of the group, it would likewise be required for another member to perform the add on their behalf. The member performing the add operation would choose a new random secret value for the new group member, add the new group member to the tree, maintaining a left-balanced tree as much as possible so as to work nicely with the algorithm of the update operation, and then perform an update operation on that node’s behalf. ”

“ The probability that the adversary guesses correctly minus the probability the adversary guesses wrong, which is the adversary advantage, should be (negligibly) zero. Let be the event that the adversary guesses correctly and be the event that the adversary guesses wrongly.
Definition 2. Break-in recovery:
Break-in recovery is defined by a near equivalent game. The challenger picks a random message , and an initial key . The challenger initializes the state and then computes the cipher and sends to the adversary . As part of the encryption output the challenger is also left with a new state . ”

“ Let be a group with generator used for public-key cryptography. Let be a key encapsulation method which takes a value in some space and outputs a private-public key pair of elements in the group . Then,
Where is a private key, is a public key, and is optional ciphertext in the ciphertext space containing securely encrypted information about . ”

“ This paper omits technical details of actually implementing the structure and is not meant to provide a guide for implementing an exact protocol. Rather it should serve as an easy introductory understanding to the concepts used in creating such a protocol. ”

“ In ElGamal encryption, as done in most public key cryptography encryption schemes, a symmetric key is established and then proceeding communication can occur using a symmetric-key based algorithm such as . ”