Problem : Time-Memory-Tradeof

We've seen the Time-Memory-Tradeoff (TMTO) of hash chains and rainbow tables used to efficiently attack many wireless (and wired) systems. In this question, we'll explore TMTO in a bit more practical detail.

(a) Hash chain reduction functions map hashes back into the pre-image space. Can there be collision of the reduction function output? I.e. is there an X and X0 such that R(X) = R(X0 )? Explain your answer.

(b) Assume that the pre-image space is 8 bytes of ASCII. Write the pseudo-code for a good reduction function R() in this problem scenario. Explain any relevant details of your function R().

(c) Assume that the pre-image space is 8 bytes (where each byte can take on any value, not just ASCII). Write the pseudo-code for a good reduction function R( ) in this problem scenario. Explain any relevant details of your function R( ).