deadhacker.com

Formal aspects of mobile code security – Chapter 5
PhD thesis for Richard Drews Dean
23 page chapter.

Incomplete: Need to discuss how the author discovered attacks. Need to check my description using the detailed equations provided. I must illustrate the attack methods.

The interest in this thesis is due to its reference in Heard Hash Functions and many other papers relating to hash algorithms. In Chapter 5 a fixed point attack against hash algorithms is discussed. Methods are given for overcoming the appended message length specified in Merkle-Damgård (cache) constructed hash functions.

What is a Fixed Point Attack?
A Fixed Point Attack involves finding a random block whose properties allow the attacker to insert the block into the original message without changing the final hash. As a result two different messages are created with the same hash (the original message and the original+the special block). To produce this special block first make note of all the internal hash states produced after each block is compressed (see: SHA-1 Illustrated). Next generate random blocks (Xi) until you find one that meets two properties:

1. The hash state before compression of block Xi is the same as the hash state returned after compression.
2. The hash state of Xi equals one of the internal hash states of the original message.

After finding such a block it can be inserted into the message directly after the message block whose internal hash state it matched.

Overcoming Message Length
MD5, MD4 and SHA use Merkle-Damgård construction (cache) which specifies that the length of the entire message be appended to it. Therefor, a simple Fixed Point Attack will not do because the message length will change when the special block is inserted. This intern changes the hash of the last block thereby changing the final hash returned. The paper gives 3 methods to overcome this.

1. The length is a 64 bit integer so add the special block 2^64 times, in affect causing the number to loop. This does not work on SHA because SHA does not cover messages greater than 2^64 bits.

2. Look for any two internal hash states in the message that equal each other. If you are lucky enough to have such a message you can delete all the blocks between the two and then expand the message back to the original size using the Fixed Point Attack.

3. Run a Fixed Point Attack and make note of the place in the original message where you can insert the special block. Now, remember that the block compression function adds the resulting hash state to the previous hash state. That means that compression is a function of the current block and the previous blocks hash state. With that understood, we want to find another random block that means the following two requirements:

• The hash state before compression of block Xj is set to the first hash state of the original message.
• The resulting hash state of Xj equals one of the internal hash states of the original message which is less than the hash state matched by the Fixed Point attack.

You’ll notice that this block uses the same method as the Fixed Point only it initializes the incoming hash state to the compression function to be that of the first hash state of the message.

Now we can insert the Xj into the message directly after the message block whose internal hash state it matched. Since the compression of Xj takes the first hash state of the message we delete all the blocks up until that point, effectively making Xj the first block and reducing the size of the message. Now the Fixed Point block Xi can be inserted into the message directly after the message block whose internal hash state it matched and can be repeated to bring the message back to it’s original size.

This chapter also discusses how the attack was found as well as possible solutions. which I still need to cover.

References
References I must find:

• [PvO95] Bart Preneel and Paul C. van Oorschot. MDx-MAC and building fast MACs from hash functions. In Don Coppersmith, editor, Proc. CRYPTO 95, pages 1–14. Springer, 1995. Lecture Notes in Computer Science No. 963.

To find the attacks the author used Binary Decision Diagrams to look at the logical structure of MD5,MD5,SHA-1. References I must find:

• [Bry92] Randal E. Bryant. Symbolic boolean manipulation with ordered binary decision diagrams. ACM Computing Surveys, 24(3):293–318, September 1992.
• [Hu97] Alan J. Hu. Formal hardware verification with BDDs: An introduction. In IEEE Pacific Rim Conference on Communications, Computers, and Signal Processing, pages 677–682, 1997.