3
$\begingroup$

Say I have a function that calculates a pseudo random permutation and this function is easy to invert.

For example $P(i) = AES_k(i)$ where $k$ is a publicly known key. So anyone can compute $P(i)$ and also get back $i$ if $P(i)$ is known.

Would the following function be hard to invert?

$$F(i) = P(i) \oplus i$$

I am trying to understand why the Salsa20 construction is secure and would like to know if any construction like this will be secure provided that $P(i)$ is a good pseudo random permutation, or if there is more to it.

|improve this question
$\endgroup$
  • $\begingroup$ I edited your title to more closely match your question. $\endgroup$ – orlp Sep 13 '13 at 13:18
3
$\begingroup$

If you take a pseudo random permutation permutation you usually get a hard to invert PRF.

AES with its 128 bits is a bit narrow, but Salsa's 512 bits are certainly wide enough.

Commonly used compression functions are built from block-ciphers with similar techniques:

For example Davies–Meyer (used in popular hashes such as MD5, SHA-1 and SHA-2) uses:

$H_i = E_{m_i}(H_{i-1}) \oplus H_{i-1}$

The $\oplus$ operation prevents solving for $H_{i-1}$ given $m_i$ and $H_i$. Without this one-way operation a narrow-pipe hash-function would be vulnerable to meet-in-the-middle attacks.

With Matyas–Meyer–Oseas the $\oplus$ is even more crucial:

$H_i = E_{H_{i-1}}(m_i) \oplus m_i$

This construction directly relies on $\oplus$ turning a permutation into a one-way function for its pre-image resistance.

The only different between Matyas–Meyer–Oseas constructions and Salsa is that salsa is lacking the chaining value/block cipher key which it doesn't need.

|improve this answer
$\endgroup$
  • $\begingroup$ "If you take a pseudo random permutation permutation you usually get a hard to invert PRF." - That statement is misleading or irrelevant here: here we have a known key, so PRFs are not relevant. Davies-Meyer is one-way if the block cipher acts like an ideal cipher, but the ideal cipher model is a much stronger assumption than assuming that the block cipher is a PRP (it's analogous to the difference between the random oracle model vs assuming the hash function is collision-resistant). I don't know if Salsa20 acts like an ideal cipher. $\endgroup$ – D.W. Sep 13 '13 at 20:36
  • $\begingroup$ "AES with its 128 bits is a bit narrow" - 128 bits is plenty for one-wayness (which is all that the question is asking about). $\endgroup$ – D.W. Sep 13 '13 at 20:37
  • $\begingroup$ If I understand it correctly, once I fix the key of an ideal cipher, I get a PRP. The key in the first round of Matyas–Meyer–Oseas is fixed, so the ideal cipher assumption may be important only for the chaining, which salsa does not need. So if Matyas–Meyer–Oseas is secure with an ideal cipher, salsa should be secure if its mixing function is a PRP. Is there a proof of security of Matyas–Meyer–Oseas? $\endgroup$ – green lantern Sep 13 '13 at 22:50

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.