0
$\begingroup$

I recently studied a Hash function and its security requirement. I have studied that simple hash construction from XOR is weak. My question is, based on Xor property the following Hash based on RSA Mi<n calculated by $H(M_1,M_2)=(M_1^e \bmod n) \oplus (M_2^e \bmod n)$, where $(n,e)$ is an RSA public key.

satisfy the collision resistant and 2nd preimage resistant?

$\endgroup$
4
  • 5
    $\begingroup$ You did not specify the construction, so it's impossible to say. $\endgroup$
    – Maeher
    Sep 23, 2020 at 16:39
  • 3
    $\begingroup$ We can guess that the function is/involves $m\mapsto m^e\bmod N$ where $(N,e)$ is an RSA public key which matching private is secret. But the question critically misses a definition of the input domain (and as a comparatively minor aside the output domain). Also, the security requirements are not precisely defined, which often matters. $\endgroup$
    – fgrieu
    Sep 23, 2020 at 18:36
  • 2
    $\begingroup$ You keep removing the actual construction. In its current state this questing cannot be answered and my answer makes no sense. Why are you doing that? Is the construction the wrong one? If yes, add the correct one. $\endgroup$
    – Maeher
    Sep 26, 2020 at 18:50
  • 2
    $\begingroup$ Accepting the current answer means that the construction needs to be present in the question. Please do not edit it out again; remember that Q/A's need to be readable by any user of the system. $\endgroup$
    – Maarten Bodewes
    Sep 27, 2020 at 9:38

1 Answer 1

2
$\begingroup$

The construction is trivially neither collision resistant nor second preimage resistant, since XOR is commutative. I.e. for any $a,b$ it holds that $a\oplus b = b \oplus a$. Consequently, given $M_1,M_2$ as a first preimage, we can trivially find $M_2,M_1$ as a second preimage. To break collision resistance, simply choose $M_1,M_2$ arbitrarily.

$\endgroup$
2
  • $\begingroup$ Also note that self-inversion is also a factor here and $M_1=M_2$ would also lead to collisions as they generate the same hash for all $M_1$... $\endgroup$
    – SEJPM
    Sep 24, 2020 at 13:00
  • $\begingroup$ Just change the order of the inputs arbitrarily to get a second preimage. The fact that you're using RSA is irrelevant. This works for any deterministic mapping. $\endgroup$
    – Maeher
    Sep 24, 2020 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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