2
$\begingroup$

Suppose we use a pseudorandom function $PRF$ and a random key $k$ to generate a set of pseudorandom values:

$\forall i, 1\leq i \leq n: w_i=PRF(k,i)$

Now, consider instead of picking a fresh key, we increment the key by one:$k'=k+1$. Then, we compute a set of pseudorandom values:

$\forall i, 1\leq i \leq n: q_i=PRF(k',i)$


Question: Are the set of $w_i$ values are computationally indistinguishable from the set of $q_i$ values?

$\endgroup$
2
  • $\begingroup$ That would be dependent of the PRF. $\endgroup$
    – Azarinak
    Mar 1 '16 at 19:31
  • 1
    $\begingroup$ For any cryptographic PRF, I would hope that's true, but you'd have to analyze each PRF algorithm to be sure. $\endgroup$ Mar 1 '16 at 19:48
2
$\begingroup$

Question: Are the set of $w_i$ values are computationally indistinguishable from the set of $q_i$ values?

No, that is not guaranteed by standard security notions.

AES for example is considered a secure PRP (and thus PRF up to a bound), but has related-key attacks. Granted, the known attacks have more complex key-dependence between a large number of keys, but still, in theory an otherwise secure PRF may be insecure if you see outputs for such related keys. They are only required to be secure with a randomly chosen key.

$\endgroup$
2
  • $\begingroup$ Thank you for the answer. What if we set $k'=k+PRF(k'',i)$ where $k''$ is a random key. $\endgroup$
    – user153465
    Mar 6 '16 at 12:55
  • $\begingroup$ @user153465, that should be ok (assuming addition is modulo key size). However, the standard primitive for this is a key derivation function. For example, HKDF. $\endgroup$
    – otus
    Mar 6 '16 at 13:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.