# Forward Secrecy with pseudorandom functions

Let $H_1$, $H_2$ be keyed hash functions (e.g. $H_i(x) = SHA_{256}(s_i||x)$ for pseudorandom $s_1$, $s_2$).

Let $s_n = H_1^k(s_0)$, $k_n = H_2(s_n)$, where $s_0$ is a secret (pseudorandomly chosen from a distribution).

Is using $k_n$ as a sequence of forward-secure keys secure (i.e., forgetting $s_n$ when changing to $k_{n+1}$), noting that $H_i$ are known to the attacker?

It seems that not being able to distinguish $k_n$ from random, knowing $s_{n+1}$, $k_j$ for $j<n$ is enough. When $H_i$ are modeled as random oracles, it seems that attackers would require $\Omega(2^K/n^2)$ oracle requests on average for this (where $K$ is the key length of $H_i$), because we lose a factor of $n$ on the reduction, and as long as the attacker's guesses are disjoint from $s_j$ ($j$<$n$) the attacker gains no information.

Is this intuition correct? Can you get a better bound (although $\Omega(2^K/n^2)$ is good enough, given that $n << 2^{64}$ and I am using SHA-256 for a 128-bit security level).