Computer Security MT24, Example hash functions



Flashcards

Checksums

Consider the function

\[g : \\{0, 1\\}^{32} \times \\{0, 1\\}^{32} \to \\{0, 1\\}^{32}\]

defined by

\[g(x, y) = x + y \pmod {2^{32}}\]

and extend to a function $h : \{0, 1\}^\ast \to \{0, 1\}^n$ by

\[\begin{aligned} h\langle \rangle &= IV \\\\ h\langle x_1, x_2, \ldots, x_m \rangle &= g(h\langle x_1, \ldots, x_{m-1}\rangle, x_m) \end{aligned}\]

where $\langle x _ 1, \ldots, x _ n \rangle$ is the input split into 32-bit blocks. What is this construction called?


A checksum.

Consider the function

\[g : \\{0, 1\\}^{32} \times \\{0, 1\\}^{32} \to \\{0, 1\\}^{32}\]

defined by

\[g(x, y) = x + y \pmod {2^{32}}\]

and extend to a function $h : \{0, 1\}^\ast \to \{0, 1\}^n$ by

\[\begin{aligned} h\langle \rangle &= IV \\\\ h\langle x_1, x_2, \ldots, x_m \rangle &= g(h\langle x_1, \ldots, x_{m-1}\rangle, x_m) \end{aligned}\]

where $\langle x _ 1, \ldots, x _ n \rangle$ is the input split into 32-bit blocks. This is the checksum hash.

Which of the following conditions are met?

  1. Conditions on the domain
    1. $D = \{0, 1\}^n$.
    2. $D = \{0, 1\}^{n+k}$ for $k > 0$.
    3. $D = \{0, 1\}^\ast$. (compression)
  2. For all $x \in D$, $h(x)$ is easy to compute.
  3. For almost all $y \in \text{Im}(h)$, it is computationally infeasible to find an $x$ such that $h(x) = y$. (preimage resistance/one way)
  4. Given $x \in D$, it is always computationally infeasible to find $x’ \ne x$ such that $h(x) = h(x’)$. (2nd-preimage resistance/weak collision resistance)
  5. It is computationally infeasible to find any pair $x \ne x’$ such that $h(x) = h(x’)$. (collision resistance/strong collision resistance)

  • 1.3, so compression function
  • 2,
  • Not 3 (every 32-bit block maps to itself)
  • Not 4 (appending extra 32-bit block of zeroes does not change the output)
  • Not 5 (appending extra 32-bit block of zeroes does not change the output)

LM (Lan Manager)

@Define the components of the LM hash in terms of its:

  • Input
  • Output
  • Operation

  • Input: Maximum of 14 characters of printable ASCII
  • Output: 128 bit hash
  • Operation:
    • Null-pad the password to 14 characters
    • Force any lowercase letters to upper case
    • Split into 7-byte halves, each of which makes a 56-bit DES key
    • Use the DES key to encrypt a certain, fixed 64-bit block
    • Concatenate the two DES encryptions to make a 128 bit hash.

scrypt

How does the scrypt algorithm slow down brute-force attacks on its hashes?


The algorithm uses a lot of memory, by creating many pseudorandom blocks and then combining them in a pseudorandom order.

MD4

@Define the components of the MD4 hash in terms of its:

  • Inputs
  • Outputs
  • Construction (summary)

  • Inputs: 512 bits (16 words of 32 bits)
  • Output: 128 bits
  • Construction: Iterating a compression function and using MD padding

MD5

  • Successor to MD4, was also insecure.

SHA-1

  • Also insecure, designed by the NSA.

SHA-2

  • Larger output compared to MD4, MD5, SHA-1 and also bigger input blocks.
  • Used in Bitcoin.

SHA-3

  • Different construction compared to SHA-2.
  • NSA-free!
  • Allows arbitrary-length input and output.
  • Has adjustable security parameters.



Related posts