# 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 ${\displaystyle c_{2}=AES\_GCM256(m,k')=E(m,k,x_{2})}$ for some ${\displaystyle k'\in \{0,1\}^{256}}$, the challenger shall now provide this key ${\displaystyle k'}$ to the adversary.

At the end of this game, the adversary should easily be able to compute ${\displaystyle m_{2}}$ by possession of the AES 256-bit key ${\displaystyle k'}$, however, if the scheme is forward secure then the adversary will not be able to distinguish ${\displaystyle c_{1}}$ from any random piece of data, and if now given a random message ${\displaystyle m'}$ alongside the real message ${\displaystyle m_{1}}$, the adversary should be statistically unable to distinguish which message was encrypted to generate the ciphertext ${\displaystyle 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 ${\displaystyle W_{1}}$ be the event that the adversary guesses correctly and ${\displaystyle W_{2}}$ be the event that the adversary guesses wrongly.

${\displaystyle 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 ${\displaystyle m_{1}\in {\mathcal {M}}}$, and an initial key ${\displaystyle k\in {\mathcal {K}}}$. The challenger initializes the state ${\displaystyle x_{1}\in {\mathcal {X}}}$ and then computes the cipher ${\displaystyle c_{1}\in {\mathcal {C}}}$ and sends ${\displaystyle c_{1}}$ to the adversary ${\displaystyle {\mathcal {A}}}$. As part of the encryption output the challenger is also left with a new state ${\displaystyle x_{2}\in {\mathcal {X}}}$.

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

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

${\displaystyle 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: ${\displaystyle 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