Now consider the opposite problem: using an encryption algorithm to construct a one way hash function. Consider using RSA with a known key. Then process a message consisting of a sequence of blocks as follows: Encrypt the first block, XOR the result with the second block and encrypt again, etc. Show that this scheme is not secure by solving the following problem. Given a two-block message B1, B2, and its hash
RSAH(B1, B2) = RSA(RSA(B1)⊕B2)
Given an arbitrary block C1, choose C2 so that .Thus, the hash function does not satisfy weak collision resistance. RSAH(C1, C2) = RSAH(B1, B2)
T he Correct Answer and Explanation is :
Answer
Given a two-block message (B1,B2)(B_1, B_2) and the hash function: RSAH(B1,B2)=RSA(RSA(B1)⊕B2)\text{RSAH}(B_1, B_2) = \text{RSA}(\text{RSA}(B_1) \oplus B_2)
Suppose we are given RSAH(B1,B2)\text{RSAH}(B_1, B_2), and we wish to find a different pair (C1,C2)(C_1, C_2) such that: RSAH(C1,C2)=RSAH(B1,B2)\text{RSAH}(C_1, C_2) = \text{RSAH}(B_1, B_2)
Step-by-step Solution:
- Let: H=RSA(RSA(B1)⊕B2)H = \text{RSA}(\text{RSA}(B_1) \oplus B_2)
- Choose any arbitrary value for C1C_1.
- Compute: C2=RSA(C1)⊕RSA(B1)⊕B2C_2 = \text{RSA}(C_1) \oplus \text{RSA}(B_1) \oplus B_2
- Then: RSAH(C1,C2)=RSA(RSA(C1)⊕C2)\text{RSAH}(C_1, C_2) = \text{RSA}(\text{RSA}(C_1) \oplus C_2) Substitute C2C_2: =RSA(RSA(C1)⊕(RSA(C1)⊕RSA(B1)⊕B2))= \text{RSA}(\text{RSA}(C_1) \oplus (\text{RSA}(C_1) \oplus \text{RSA}(B_1) \oplus B_2)) Since x⊕x=0x \oplus x = 0: =RSA(RSA(B1)⊕B2)=H= \text{RSA}(\text{RSA}(B_1) \oplus B_2) = H
Explanation
This construction illustrates a fundamental weakness in using encryption functions like RSA to build hash functions. Hash functions are expected to be weakly collision resistant, meaning that it should be computationally infeasible to find a different input that produces the same hash output.
In this scenario, the proposed hash function uses a chaining mechanism where the RSA encryption is applied to the XOR of the previous RSA output and the next message block. While chaining is common in hash function design (like in Merkle–Damgård), using RSA in this way introduces vulnerabilities because RSA is a deterministic and reversible function.
We exploit this by choosing any arbitrary new first block C1C_1, then calculating the second block C2C_2 so that the XOR in the internal state of the hash matches that of the original message. Since RSA is deterministic, RSA(C1)\text{RSA}(C_1) is well-defined, and we can compute: C2=RSA(C1)⊕RSA(B1)⊕B2C_2 = \text{RSA}(C_1) \oplus \text{RSA}(B_1) \oplus B_2
This guarantees that: RSA(C1)⊕C2=RSA(B1)⊕B2\text{RSA}(C_1) \oplus C_2 = \text{RSA}(B_1) \oplus B_2
Therefore, the same value is input to the final RSA operation, and the hash output is the same: RSAH(C1,C2)=RSAH(B1,B2)\text{RSAH}(C_1, C_2) = \text{RSAH}(B_1, B_2)
Thus, we’ve constructed a second pre-image (a different input with the same hash), demonstrating the lack of weak collision resistance. This makes the scheme unsuitable as a cryptographic hash function, which must resist even this basic form of attack.
