Hash Functions

A function that takes data of arbitrary size and returns a fixed-size output.

• Example: Bitwise XOR.

  	Bit 1	Bit 2	...	Bit n
  Block 1	$x_{11}$	$x_{12}$	...	$x_{1n}$
  Block 2	$x_{21}$	$x_{22}$	...	$x_{2n}$
  ...	...	...	...	...
  Block m	$x_{m1}$	$x_{m2}$	...	$x_{mn}$
  Hash Output	$y_1$	$y_2$	...	$y_n$

  For example, XOR the blocks $x_{11}, x_{12}, \ldots, x_{1n}$/ $x_{21}, x_{22}, \ldots, x_{2n}$ to obtain $y_1, y_2, \ldots, y_n$.

A function $h$ that takes a message of arbitrary length and outputs a

fixed-length message digest

.

1. Computational efficiency
   • Given input $m$, it must be possible to calculate $h(m)$ efficiently.
2. One-wayness
   , or
   preimage resistance
   • Given $y$, it must be computationally infeasible to satisfy $h(m')=y$ by finding a value $m'$.
3. Second-preimage resistance
   , or
   weak collision resistance
   • Given $m$, it must be computationally infeasible to satisfy $h(m')=h(m)$ by finding another $m'$.
4. Collision resistance
   • For $m, m'$, it must be computationally infeasible to satisfy $h(m)=h(m')$ by finding a pair $m, m'$.

1. Initialization vector (IV).
2. Message block.
3. Compression function: c.
4. Hash output.

1. Initial values:
   • $A, B, C, D, E$.
2. Round function:
   • $f_t(B, C, D)$ performs a different logical operation depending on round number $t$.
3. Bit rotation:
   • Rotate $A$ and $B$ by 5 and 30 bits respectively.
   • Rotation moves bits to the left, with the leftmost bit wrapping around to the rightmost position.
4. Operations and updates:
   • In each round, $A, B, C, D, E$ are updated using $f_t$ and other operations.
   • An example update is $A = f_t(B, C, D) + K_t + W_t + E$.

• $A = ((A << 5) + f_t(B, C, D) + E + K_t + W_t)$
• $B = A$ (store the previous value of $A$ in $B$).
• $C = B << 30$
• $D = C$
• $E = D$

• $f$ is a block-permutation function made up of XOR, AND, and NOT operations.