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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.