# Perfect Forward Secrecy with Pre-shared Key

I've recently been looking at how to do perfect forward secrecy on a unidirectional connection (server can only push messages to client, client cannot respond).

What I've come up with is the idea of using a random shared key as a starting place and using this as a symmetric cipher key for the first pushed message. Once this message is pushed, the key is hashed, the result of this hash is the key for the second message. This continues to function as a sort of hash tree, ie:

\begin{aligned} K_0 &= R && \\ K_1 &= H(K_0) &&= H(R) \\ K_2 &= H(K_1)&&= H(H(R)) \\ \vdots &\qquad\vdots && \qquad\vdots \\ K_n &= H(K_{n-1}) &&= H^n(R) \end{aligned}

If this is implemented correctly and the previous key is always destroyed fully (perhaps kept only in RAM) then I believe this could offer perfect forward secrecy assuming client and server can exchange the initial random value securely (the idea is that these be exchanged via QR code or similar mechanism).

The only disadvantage that I'm aware of to this approach compared to interactive Diffie-Hellman would be that if a server or client was compromised in this system, using the information within could allow a passive attack instead of an interactive (MITM) attack.

I doubt this is a new or unique idea at all, but just looking for some people to bounce this idea off before I attempt an implementation. I'm wondering if anyone has any thoughts on additional things to look out for that I may have missed or if I am catastrophically wrong and this won't work at all.

-
Are you talking about something like this? en.wikipedia.org/wiki/Hash_chain –  user11976 Feb 13 '14 at 20:43

A possible deficiency is that if the use made of any $K_j$ allows it to leak, all later security is lost. That makes $K_j$ plain unsuitable in some uses, e.g. directly as keystream for short messages.

The $K_j$ must be wide enough that it is extremely unlikely that a cycle is ever reached in deriving them. For plausible parameters that translates to $n^2<2\cdot|K_j|\cdot\epsilon$, where $\epsilon$ is a small acceptable residual risk, and $|K_j|$ is the bit width of $K_j$. If $K_j$ was a 128-bit key, with 100 keys per microsecond for a decade, I get $\epsilon\approx2^{-19.4}$. That could be a problem when some requirement prescribes a very low $\epsilon$, like $2^{-40}$.

The above two can be solved with a wide key (and hash), derived into a working key (perhaps shorter) using a Key Derivation Function such as HKDF or one of these, preferably not using the same hash function as the one used to derive the $K_j$.

Another: if the adversary can only test a candidate key $K_j$ at relatively high cost $C_0$, and in some conceivable uses of $K_j$ like encryption of a known constant block, an adversary trying brute force and for which hashing has much cheapest cost $C_1$ gains an enormous speed boost from how the $K_j$ are derived; something like $\mathcal O(\min(n,C_0/C_1))$, neglecting cost of a memory fetch per hash. That can be solved by using, in order to derive $K_{j+1}$ from $K_j$, instead of a hash, a slow key-stretching function, such as scrypt or the lesser PBKDF2, with cost parameter(s) such that $C_1\approx C_0$.

Last one that immediately comes to my mind: the receiver must forget the current $K_j$ only after validating the next one, or some later one if lost messages are part of the assumptions. And in the later case it is probably a good idea to limit the number of consecutive messages that can be skipped, else there is a trivial Denial of Service Attack.

-
I should have phrased this question in a more practical way. Hash function will be SHA256, K will be used as a AES key in OCB or CCM mode so I don't believe the key stretching would be necessary though it's probably a good idea to do it anyways. –  ultramancool Feb 13 '14 at 18:19
@ultramancool: that leaves you with my last point as the only practical concern among those I gave. –  fgrieu Feb 13 '14 at 18:21
Yeah, all great points. Definitely appreciate it. I'm hoping to be able to avoid the lost messages issue completely and just fail and tell the user to re-synchronize again. It'll really depend on how well the service I'm using for notifications works. –  ultramancool Feb 13 '14 at 18:26

Your proposal is theoretically sound. If an attacker gets $K_5$ the only way to get previous keys would be to "rollback" the hash. If the hash function is secure, this should not be feasible. You could probably even prove it using the random oracle model, for example.

-