140
2 Computer Viruses, Malicious Logic, and Spyware
– The received message block is hashed in four stages with 20 rounds each, and
each stage uses its own constant Kp K2, K3, or K4;
– Function output for each block will be the new values a, b, c, d, e, which are added
to the result:
h 0 = h 0 + a, h 1 = hj + b, h 2 = h 2 + c, h 3 = h 3 + d, h 4 = h 4 + e;
– The final hash result will be a 160-bit value obtained by concatenating five 32-bit
values of 0, hp h, h, h4 after processing the last block of the message.
Collisions Building
The aim of the examined attack is to find such constants Kp K2, K3, K4 and such
messages M1, M that Hash(M1) = Hash(M2). This attack modifies only the first
512 bits (first block) of messages for which a collision is required. The algorithm
is based on the known differential attack on SHA1, which was suggested in 2005
and has complexity of about 269 operations, which makes it difficult to implement
in practice. Due to this fact, no real collisions have been found for SHA1 to this
moment.
However, if creating a malicious version of SHA1, the intruder can vary both
message blocks Mx and M2 and the round constants Kp K2, K3, K4. According
to the studies, it significantly reduces the complexity of the attack to the order of
248 operations and makes creation of such collisions a real task, which can be
implemented on several computers. Thus, the authors of the research managed to
create single-block collisions for many known file types.
Single-Block Collision
M 1 (512-bit)
Content
M 2 (512-bit)
Content
Mj and M2—first message blocks (512), which differ from each other but produce
the same hash sum:
Content is the remaining content that is the same for both files.
Example of Using Malicious Cash for Backdoor Creation
The described attack was used to create two scripts, which if case of selection of K
= 5a827999, K2 = 88e8ea68, K3 = 578059de, K4 = 54324a39 give the same hash
sum SHA1 but operate differently.
2 Computer Viruses, Malicious Logic, and Spyware
– The received message block is hashed in four stages with 20 rounds each, and
each stage uses its own constant Kp K2, K3, or K4;
– Function output for each block will be the new values a, b, c, d, e, which are added
to the result:
h 0 = h 0 + a, h 1 = hj + b, h 2 = h 2 + c, h 3 = h 3 + d, h 4 = h 4 + e;
– The final hash result will be a 160-bit value obtained by concatenating five 32-bit
values of 0, hp h, h, h4 after processing the last block of the message.
Collisions Building
The aim of the examined attack is to find such constants Kp K2, K3, K4 and such
messages M1, M that Hash(M1) = Hash(M2). This attack modifies only the first
512 bits (first block) of messages for which a collision is required. The algorithm
is based on the known differential attack on SHA1, which was suggested in 2005
and has complexity of about 269 operations, which makes it difficult to implement
in practice. Due to this fact, no real collisions have been found for SHA1 to this
moment.
However, if creating a malicious version of SHA1, the intruder can vary both
message blocks Mx and M2 and the round constants Kp K2, K3, K4. According
to the studies, it significantly reduces the complexity of the attack to the order of
248 operations and makes creation of such collisions a real task, which can be
implemented on several computers. Thus, the authors of the research managed to
create single-block collisions for many known file types.
Single-Block Collision
M 1 (512-bit)
Content
M 2 (512-bit)
Content
Mj and M2—first message blocks (512), which differ from each other but produce
the same hash sum:
Content is the remaining content that is the same for both files.
Example of Using Malicious Cash for Backdoor Creation
The described attack was used to create two scripts, which if case of selection of K
= 5a827999, K2 = 88e8ea68, K3 = 578059de, K4 = 54324a39 give the same hash
sum SHA1 but operate differently.