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?
- Conditions on the domain
- $D = \{0, 1\}^n$.
- $D = \{0, 1\}^{n+k}$ for $k > 0$.
- $D = \{0, 1\}^\ast$. (compression)
- For all $x \in D$, $h(x)$ is easy to compute.
- 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)
- 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)
- It is computationally infeasible to find any pair $x \ne x’$ such that $h(x) = h(x’)$. (collision resistance/strong collision resistance)
- $D = \{0, 1\}^n$.
- $D = \{0, 1\}^{n+k}$ for $k > 0$.
- $D = \{0, 1\}^\ast$. (compression)
- 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?
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.