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 '20 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 '20 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 '20 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 '20 at 9:38
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 '20 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 '20 at 15:54

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.