Inserting a backdoor into a cryptographic hash function I'm curious as to how a backdoor can be built into a hash function. What might it take the form of? What's probability of getting one that can be backdoored in a way that can actually undermine its security? Could this backdoor be asymmetric?
Here is a "backdoored" hash function:

Let $p = 2q + 1$ be a big prime of length $2048$ bits, such that $q$ is also prime. Let $a$ be an integer of order $q$ modulo $p$, i.e. $a \neq 1$ but $a^q = 1 \pmod p$; it can be shown that $a = 4$ is always a valid solution. Let $s$ be a (secret) integer between $1$ and $q-1$, and let $b = a^s \pmod p$.

Then define operation $\phi(x, y)$ such that input $x$ is a sequence of $2048$ bits, and $y$ is a sequence of $2042$ bits (not $2048$); the output is a $2048$-bit value:


Concatenate $x$ and $y$ and split it back into $u$ and $v$, such that $u$ and $v$ both have length $2045$ bits each: $$u || v = x || y$$
Interpret $u$ and $v$ as unsigned big integers, using some convention (e.g. big-endian). Note that both $u$ and $v$ are lower than $2^{2045}$.
Compute: $$z = a^u b^v \pmod p$$
$\phi(x, y)$ is the encoding of $z$ over exactly $2048$ bits (there again, using a fixed convention).


Note that $\phi(x, y) \neq 0$ for all $x$ and $y$.

Now that you have $\phi$, define a hash function $h$ as follows:


For input $m$, pad it with some "removable" padding sequence (e.g. a Merkle-Damgård compliant padding) so that the total length of $m$ is now a multiple of $2042$.
Split $m$ into $n$ blocks of $2042$ bits (denoted $m_1$, $m_2$, ... $m_n$).
Define $x_0 = 0$ (a sequence of $2048$ bits, all of value $0$).
For $i = 1$ to $n$, define: $x_i = \phi(x_{i-1}, m_i)$
Define the hash output $h(m)$ to be SHA-256($x_n$).


Let's see the security of this construction:


Preimages: for a given $t$, finding $m$ such that $h(m) = t$ implies, in particular, finding some $x_n$ such that SHA-256($x_n$) $= t$, so our function $h$ is at least as much preimage-resistant as SHA-256.
Second preimages: second preimages are a special case of collisions, so $h$ will resist second preimages at least as well as it resists collisions. Ideally we would want something better (i.e. resistance up to $2^{256}$ for second preimages, even though collisions can be found in effort $2^{128}$), but since collisions should be infeasible anyway, this is probably acceptable.
Collisions: suppose that $m \neq m'$ and $h(m) = h(m')$; $m$ yields a sequence of $n$ words $x_1$ to $x_n$, while $m'$ yields $x'_1$ to $x'_{n'}$. We suppose, without loss of generality, that $n' \geq n$. Then one of the following holds:


$x_n \neq x'_{n'}$ but SHA-256($x_n$) $=$ SHA-256($x'_{n'}$). We have found a collision on SHA-256.
There is an index $i$ such that $x_{i-1} \neq x'_{i-1}$ but $x_i = x'_i$. This means that we know integers of at most $2045$ bits $u$, $v$, $u'$ and $v'$ such that $(u, v) \neq (u', v')$, but $a^u b^v = a^{u'} b^{v'} \pmod p$. This implies that $a^{u-u'} = b^{v'-v} \pmod p$. Since $a$ and $b$ have order $q$ (greater than $2^{2046}$) and $u-u'$ and $v-v'$ cannot be both $0$, then $u-u'$ and $v'-v$ are invertible modulo $q$, and we can write $b = a^g \pmod p$ with $g = (u-u')/(v'-v) \pmod q$ (i.e. $g$ is the secret value $s$). We just solved discrete logarithm. 
There is an index $j$ such that $n \lt j \leq n'$ and $x'_j = x_n$. By "rewinding" the steps this implies that either we find an instance of the previous situation ($a^u b^v = a^{u'} b^{v'}$ for $(u,v) \neq (u',v')$), or we have $x'_{j-n} = x_0$, which is not possible since $x_0 = 0$ and $x'_{j-n} = \phi(x'_{j-n-1}, m_{j-n}) \neq 0$.


Therefore, finding a collision on $h$ requires either finding a collision on SHA-256, or solving discrete logarithm modulo $p$. Since both are computationally infeasible (as far as we know), this function $h$ can be deemed "secure" as a hash function.




The backdoor is the knowledge of $s$. In all of the above, we used the $a$ and $b$ values "as is". The value of $s$ is not needed anywhere. However, if you know $s$, then you can compute collisions at will:


Generate two random blocks $m_1$ and $m'_1$. Compute the corresponding $x_1$ and $x'_1$.
Let $u$ be the first $2045$ bits of $x_1$, and $u'$ be the first $2045$ bits of $x'_1$.
Compute $k = (u-u')/s \pmod q$
If $k$ is less than $2^{2045}$, or greater than $q - 2^{2045}$, then you can find $v$ and $v'$ of $2045$ bits each, such that $v'-v = k \pmod q$, from which you can infer two blocks $m_2$ and $m'_2$ that match $(u,v)$ and $(u',v')$, respectively. You have your collision.
The condition on $k$ works with probability at least $1/2$. If you were unlucky, just try again with new random blocks $m_1$ and $m'_1$.




The above is thus a hash function with a backdoor. However, mind the fine print:


The backdoor is explicit. While the knowledge of $s$ is necessary to exploit the backdoor, everybody knows that it is there. Conversely, if you generate $a$ and $b$ as NUMS numbers (thus with $s$ convincingly unknown to everybody), then the hash function is "backdoorless" (but also useless).
When you exploit the backdoor, you produce two colliding messages $m$ and $m'$, from which anybody can recompute $s$. Thus, the backdoor is "one-shot".
The backdoor allows finding collisions, not preimages. A hash function designed to have a backdoor for preimages would need something else. Ideally you would use a one-way trapdoor permutation, but (to my knowledge) no such object is currently known, that would yield an output of suitable length (e.g. 256 bits).