Page:Efficient and Secure Group Messaging.pdf/4

• We will assume that a symmetric encryption algorithm is being used as part of the forward secure scheme. Suppose that the challenger was using AES-GCM256 (without loss of generality this can be any semantically secure symmetric algorithm) as his symmetric encryption scheme, such that $c_{2}=AES\_GCM256(m,k')=E(m,k,x_{2})$ for some $k'\in \{0,1\}^{256}$, the challenger shall now provide this key $k'$ to the adversary.

At the end of this game, the adversary should easily be able to compute $m_{2}$ by possession of the AES 256-bit key $k'$, however, if the scheme is forward secure then the adversary will not be able to distinguish $c_{1}$ from any random piece of data, and if now given a random message $m'$ alongside the real message $m_{1}$, the adversary should be statistically unable to distinguish which message was encrypted to generate the ciphertext $c_{1}$. The probability that the adversary guesses correctly minus the probability the adversary guesses wrong, which is the adversary advantage, should be (negligibly) zero. Let $W_{1}$ be the event that the adversary guesses correctly and $W_{2}$ be the event that the adversary guesses wrongly.

$$Adversary~Advantage=|Pr[W_{1}]-Pr[W_{2}]|$$

Definition 2 Break-in recovery:

Break-in recovery is defined by a near equivalent game. The challenger picks a random message $m_{1}\in {\mathcal {M}}$, and an initial key $k\in {\mathcal {K}}$. The challenger initializes the state $x_{1}\in {\mathcal {X}}$ and then computes the cipher $c_{1}\in {\mathcal {C}}$ and sends $c_{1}$ to the adversary ${\mathcal {A}}$. As part of the encryption output the challenger is also left with a new state $x_{2}\in {\mathcal {X}}$.

Next, the challenger picks a new random message $m_{2}$, and encrypts it using $c_{2}=E(m,k,x_{2})$ using the new state generated from step 1. The challenger sends the cipher $c_{2}$ to the adversary.

This time, the challenger reveals to the adversary the initial key $k\in {\mathcal {K}}$ and the initial state $x_{1}$. However, without $x_{2}$, which includes information on a ratchet step performed from the initial step, the adversary cannot decrypt $c_{2}$, and given a random message $m'\in {\mathcal {M}}$ alongside $m_{2}$ should not be able to guess which one was used to generate $c_{2}$.

4A Simple Symmetric Ratchet

Suppose that we are using symmetric encryption (so a shared key has already been securely established by the parties), then we make it into a symmetric ratchet by changing the key in a one-way fashion each time we take a ratchet step (perhaps every message or every hour). Below I provide a simple way of achieving this using just symmetric keys and no public-key cryptography, simply by using a random collision-resistant hash function.

Let key[0] be in the initial agreed symmetric key. Then we recursively define

$$key[i]=hash(key[i-1]))$$

For the ith message key used for authenticated encryption (say with AES-GCM). Each encryption operation would also include a random nonce for added security.

Does this achieve forward secrecy? Only if the parties can securely delete consumed keys - keys which have already been used for their decryption/encryption operations.

In the forward secrecy Attack Game the key k' given to adversary is equivalently the second key generated in the chain: $key[1]=k'$, if the adversary does not have access to key[0] then he cannot distinguish between the messages without breaking semantic security: In other words, if the adversary had some way of distinguishing between two messages encrypted with key[0] without key[0] then that would break the semantic security of AES, and therefore by proof of contradiction this approach is forward secure. We assume that key[1] does not provide any information about key[0], viewing the hash function under the assumption that it acts like a purely random oracle (even though in reality it is in practice going to be collision resistant and certainly not perfect given that the pre-image space is larger than the range).

4