Consider the following hash function. It has as output an n vector whose entries

Question

Consider the following hash function. It has as output an n vector whose entries lie in the range 0, . . . , K-1 where k is a small integer (thus decimals if k = 10 and binary if k = 2). For any message M, the first n characters (converted to numerical values) are placed in the first row of a matrix A, the next n entries in M are placed in the second row and so forth until all of M has been used. Any remaining entries in the last row of A is padded with zeros if needed. Now on the first pass all rows are added (mod k) and the resulting n-vector v1 stored. On the second pass the ith row is translated to the right with wrapping around by i- 1 places then the rows are added once more (mod k) to get v2. On the third pass, the columns are shuffled to be in the reverse order, and again the rows are added (mod k to obtain v3. At the final step, the row vectors vi, v2 and v3 are added (mod k) to obtain the hash value h(M) a) Is h pre-image resistant? b) Is h strongly collision-free? In each case give reasons for your answer-or if the answer is negative give a specific example

Explanation / Answer

let us understand first about pre-image resistance and collision attack or conversly collision free:

pre-image resistance: for a given hash value 'h' in output space of hash function it is hard to find any message M such that h(M)= h. then Hash is pre-image resistance.

A preimage attack gives the ability to create an input that produces a specified result. A feasible preimage attack basically means that (as a crypographic hash) an algorithm is almost completely broken. Essentially the only attack that [edit: might] break it more completely is a second preimage attack. Either, however, basically means that what you have isn't a cryptographic hash function at all any more -- the whole point of a cryptographic hash is that it's a one-way function, but either sort of preimage attack means it's now a two-function function.

collision resistance: it is very hard to find a pair of messages M1 and M2 such that H(M1)= H(M2). then Hash function is collision resistance.

a) so seeing the operation on above hash function encryption we can easily say that it is pre-image resistance as

the final output vector of hash values is actually matrix operation performed and then mod is taken after each operation and then all such values are added then again mod(k) is taken. so even someone knows output n vector values but how they came, it is not very feasible to know it. as any number which computer permits (like 128 bits) can give that particular mod value so it is not unique( like for 128 bits there will be such 3.4028237e+37 numbers or 1.7 e+38 binary numbers ). also even if we know all combinations but next is it came by summing three vectors. so again we need to find summing combinations for each n entry. but till here also it may be attacked but next is to perform matrix reverse operations which are not easy to track..( or practically impossible in a given time span of computation).....

b) also if h is pre-image resistance then we can say that mostly it would be collision free.... but not gaurantee . but in this case it is not strongly collision free as any two messages can result into same hash value as hash value is generated using mod(k) so even different number after mod(k) gives same answer . as 9mod(10)= 19mod(10) .

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.