What exactly is a multi-target attack? How does the attack work on different cryptographic schemes (block ciphers, hash functions, elliptic curves)? How can it be avoided?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
A multi-target attack is an attack on many users of a cryptosystem at once.
The attacker might be satisfied with breaking one user—for example, if there are a thousand human rights activists in a network under attack by an authoritarian state, breaking into the Signal chats of one activist may be enough to compromise the whole network.
Moreover, the state's intelligence agency may have many more targets than the one activist network—there may be an environmental activist network, an anticorruption activist network, foreign intelligence networks, different branches of government, etc.—and it is in the state's interest to break into any of these.
Of course, there may actually be only one human user who has many keys—for example, a thousand (say) HTML documents encrypted with different AES keys derived from a master key with HKDF-SHA256, so the adversary has the ciphertext for the same plaintext <!DOCTYPE html>\n under many different keys. More generally, a multi-target attack is an attack on many instances of a cryptosystem: many keys with known plaintext/ciphertext pairs under the same cipher, many group elements with the same discrete log base, many public keys for the same signature scheme, etc.
There are many different batch advantages that multi-target attackers might take advantage of—you asked about block ciphers, but it's worth noting several different settings because their qualitative differences can lead to substantial quantitative security differences:
For a hash function $H$, the adversary may have hashes $H(k_1),$ $H(k_2),$ $\dotsc,$ $H(k_t)$ for $t$ different unknown target keys $k_1, k_2, \dotsc, k_t$. The goal is to recover any one of the $k_i$. Examples of $H$:
AES in CTR mode on a known file header: $k \mapsto \operatorname{AES}_k(0).$
A message authentication code under HMAC-SHA256 on a TLS record: $k \mapsto \operatorname{HMAC-SHA256}_k(\text{‘250 OK’}).$
A seed phrase from which a cryptocurrency address is derived: $\mathit{seedphrase} \mapsto \operatorname{X25519}(\operatorname{HKDF-SHA256}(\mathit{seedphrase}), \underline 9).$
The best generic multi-target preimage search algorithms—parallel versions of Oechslin's rainbow tables and Rivest's distinguished points—have area*time cost proportional to $2^\lambda\!/t$ evaluations of $H$ where $\lambda$ is more or less the size of the $k_i$.
That is: The cost of a generic preimage search to break the first of $t$ targets is $1/t$ the cost of a generic preimage search to break one specific target. Have a thousand activists to target? It'll cost a thousand times less to compromise one of them if you attack them in a batch than if you try to attack them one by one independently. It will still cost $2^\lambda$ to find all of the target keys, but you usually don't need to wait that long.
How do these algorithms work?
You might think of a multi-target ‘speedup’ as populating a hash table
htand then replacing the single-target test for a candidate keyH(k) == hbyH(k) in htwhich also runs in ‘O(1)’ time but tests $t$ keys at once. However, this simplified algorithm doesn't actually reduce the adversary's area*time cost—which is generally a good proxy for cost in, e.g., yen to power a machine for long enough to find the key—because for very large numbers of keys it spends lots of time sequentially waiting for communication due to memory latency twiddling thumbs that could have been spent running random walks in parallel. Instead:Rainbow tables. We do a pseudorandom walk on the space of inputs and compute a chain of $$\sigma_0 \xrightarrow{H} h_0 \xrightarrow{R_1} \sigma_1 \xrightarrow{H} h_1 \xrightarrow{R_2} \cdots \xrightarrow{H} h_\ell,$$ alternating between inputs and hashes with a family of reduction functions $R_i$ mapping a hash back to some other input, e.g. yielding a 128-bit candidate key or a candidate BIP39 passphrase. We store the starting point $\sigma_0$ and the ending point $h_\ell$.
Actually, we don't do this just once; we do this in parallel on a large number $p$ of randomly chosen starting points. We also compute the ending point in chains starting at $H(k_i)$ as if it were $1, 2, \dotsc, \ell$ iterations from the end:
\begin{align*} \sigma_{1,0} \xrightarrow{H} h_{1,0} \xrightarrow{R_1} \sigma_{1,1} \xrightarrow{H} h_{1,1} \xrightarrow{R_2} \cdots &\xrightarrow{H} h_{1,\ell}, \\ \sigma_{2,0} \xrightarrow{H} h_{2,0} \xrightarrow{R_1} \sigma_{2,1} \xrightarrow{H} h_{2,1} \xrightarrow{R_2} \cdots &\xrightarrow{H} h_{2,\ell}, \\ \vdots \\ \sigma_{p,0} \xrightarrow{H} h_{p,0} \xrightarrow{R_1} \sigma_{p,1} \xrightarrow{H} h_{p,1} \xrightarrow{R_2} \cdots &\xrightarrow{H} h_{p,\ell}; \\ H(k_1) \xrightarrow{R_1} R_1(H(k_1)) \xrightarrow{H} \cdots &\xrightarrow{H} h'_{1,1}, \\ H(k_1) \xrightarrow{R_2} R_2(H(k_1)) \xrightarrow{H} \cdots &\xrightarrow{H} h'_{1,2}, \\ \vdots \\ H(k_1) \xrightarrow{R_\ell} R_\ell(H(k_t)) &\xrightarrow{H} h'_{1,\ell}; \\ \vdots \\ H(k_t) \xrightarrow{R_1} R_1(H(k_t)) \xrightarrow{H} \cdots &\xrightarrow{H} h'_{t,1}, \\ H(k_t) \xrightarrow{R_2} R_2(H(k_t)) \xrightarrow{H} \cdots &\xrightarrow{H} h'_{t,2}, \\ \vdots \\ H(k_t) \xrightarrow{R_\ell} R_\ell(H(k_t)) &\xrightarrow{H} h'_{t,\ell}. \end{align*}
Then we sort all the ending points—the $h_{j,\ell}$ and the $h'_{i,r}$—and look for a collision among them. If we find a collision $h_{j,\ell} = h'_{i,r}$, then we can start up again at $h_{j,0}$ and compute forward by $\ell - r$ steps to find a candidate input $\sigma_{j,\nu}$ if $H(\sigma_{j,\nu}) = H(k_i)$. (Of course, $H(\sigma_{j,\nu})$ may turn out not to be $H(k_i)$ if two random walks happened to collide temporarily, but false positives should be fairly rare.)
The batch advantage arises in part because in the sorting step, we are effectively simultaneously testing all hashes from the $p$ parallel chains against the $t$ target hashes (with some false positive rate), at cost about $(p + \ell t)^{1.5}$ of sorting a $(p + \ell t)$-element array rather than at cost $\ell\cdot p\cdot t$ of testing all $\ell\cdot p$ guesses directly against all $t$ hashes (with zero false positive rate). When $p \geq t^2$, the net reduction in cost is a factor of about $t$.
Distinguished points. We pick small subspace of points in the key space that are easy to discern, say those whose first 23 bits are
10100011110110001010, and call them distinguished points. Again we will do many independent pseudorandom walks in parallel, but instead of stopping after exactly $\ell$ iterations, we will stop when we find a distinguished point.On $p$ parallel machines, we pick starting points $h_j$ uniformly at random from the key space and iteratively compute $H(h_j),$ $H(H(h_j)),$ $\dotsc,$ $H^\nu(h_j)$, until either $H^\nu(h_j)$ is a distinguished point, in which case we store $h_j$ and $H^\nu(h_j)$, or $\nu$ exceeds a limit $\ell$, in which case we throw it out and start over with a different $h_j$:
$$h_j \xrightarrow{H} H(h_j) \xrightarrow{H} H^2(h_j) \xrightarrow{H} \cdots \xrightarrow{H} H^\nu(h_j).$$
We also iteratively compute $H(H(k_i))$, $H(H(H(k_i)))$, etc., for each $i$, until we find a distinguished point $H^\mu(k_i)$. Then we sort the $H^\mu(k_i)$ and the $h_{j,\nu}$, and if there is a collision $H^\mu(k_i) = H^\nu(h_j)$, we start over at $h_j$ and iterate $H$ until we find a candidate $k_i$: $$h_j \xrightarrow{H} \cdots \xrightarrow{H} H^{\nu-\mu}(h_j) \stackrel?= k_i \xrightarrow{H} H(k_i) \xrightarrow{H} \dotsc \xrightarrow{H} H^\nu(h_j) = H^\mu(k_i).$$ Of course, this might also happen because of a collision in $H$ elsewhere causing the two chains starting at $h_j$ and $H(k_i)$ to spuriously merge, so there's some false positive rate.
Again, the batch advantage arises in part because in the sorting step, we are effectively simultaneously testing all hashes anywhere in the $p$ parallel chains against the $t$ target hashes at cost $(p + t)^{1.5}$ rather than $\ell\cdot p\cdot t$, with some false positive rate arising from collisions in $H$.
(Extending distinguished points with reduction functions to make the technique work on, e.g., password spaces is left as an exercise for the reader.)
For detailed analyses of the expected costs and success probabilities, see Oechslin's paper and Wiener's paper (paywall-free). (To my knowledge, the distinguished points technique first appeared in an abstract by Quisquater and Descailles at CRYPTO 1987 and in the followup paper at EUROCRYPT 1989, but it is usually credited to Rivest.)
What countermeasures can you use as the user or cryptosystem designer? The standard two options are:
Make $\lambda$ so large that a factor of $t$ doesn't matter. Don't use AES-128 for a 128-bit security level—use AES-256. (Even better, use ChaCha so you can largely forget about side channel attacks.) In general, always make sure that the narrowest pipe of secret key material is 256 bits wide.
Separate the input spaces. For example, salt your password hashes, so that instead of having hashes $H(p_1),$ $H(p_2),$ $\dotsc,$ $H(p_t)$ for secret passwords $p_1, p_2, \dotsc, p_t$, the adversary will have salted hashes $H_{\sigma_1}(p_1),$ $H_{\sigma_2}(p_2),$ $\dotsc,$ $H_{\sigma_t}(p_t)$, which thwarts the batch advantage of the rainbow table and distinguished points algorithms.
This can be applied to block ciphers too, e.g. with randomly chosen initialization vectors, but there are costs: extra data transmission, limited block sizes for randomization, the implied secret key inside the randomly chosen IV, missed opportunity to detect replay attacks or nonce misuse, etc.
Input space separation also doesn't make it any harder for the adversary to find your key in particular, so you personally have little motivation to choose a cryptosystem with input space separation; it only makes it harder for the adversary to find anyone's key. In contrast, using a 256-bit key provides you and the herd immunity against brute force.
But generic key search is not the only setting where multi-target attacks might be relevant. Here are some others:
For a DLOG group with generator $g$—e.g., RFC 3526 Group #14, or Curve25519, or secp256k1—the adversary may have the powers $g^{x_1},$ $g^{x_2},$ $\dotsc,$ $g^{x_t}$ for $t$ different unknown target exponents $x_1, x_2, \dotsc, x_t$. The goal is to recover any one of the $x_i$.
Of course, this can be solved by any generic preimage search under the hash function $H\colon x \mapsto g^x$, but there are much cheaper algorithms that cost $O(\sqrt q)$ where $q$ is the largest prime factor of the order of $g$—a combination of Pollard's $\rho$ and Pohlig–Hellman, and Pollard's kangaroo if more information is known about the ranges of the $x_i$, as well as other alternatives like baby-step/giant-step. For specific groups there may be speedups too over generic algorithms, like the elliptic curve negation map in Pollard's $\rho$.
The cost to find the first of $t$ target discrete logs cannot be much cheaper than finding one target discrete log! Why? Fix a single target $h = g^x$, and pick $g^{r_1},$ $g^{r_2}$, $\dotsc,$ $g^{r_t}$ for uniform random exponents $r_i$; then apply a multi-target attack to $$(h g^{r_1}, h g^{r_2}, \dotsc, h g^{r_t})$$ to find $\log_g (h g^{r_i})$ for some $i$, figure out what $i$ was by a linear list search at worst, and finally return $$\log_g (h g^{r_i}) - r_i = \log_g (h g^{r_i}\!/g^{r_i}) = \log_g h.$$ So a single-target DLOG can't be substantially more expensive than a multi-target DLOG attack, because this shows how to use a multi-target DLOG attack to perform a single-target DLOG attack at essentially negligible additional cost. In other words, having multiple possible targets can't make a DLOG attack cheaper the way it can make a generic key search cheaper.
This is why, for example, Curve25519 should be considered to have a ‘128-bit security level’ while AES-128 should not: in the multi-target setting of the real world, the cost of breaking the first of $t$ target Curve25519 keys is still about $2^{128}$—the same as the cost of breaking one target Curve25519 key—while the cost of breaking the first of $t$ target AES keys is only $2^{128}\!/t$.
On the other hand, there is still a cost reduction to finding all of the $t$ targets with parallel $\rho$: while it's $O(\sqrt q)$ for the first of any number of targets, it's $O(\sqrt{tq})$ for all of $t$ targets rather than $O(t\sqrt q)$ for a single-target attack repeated $t$ times—that is, a multi-target attack to find all of $t$ keys is a factor of $\sqrt t$ cheaper than $t$ independent single-target attacks. There may also be an advantage to precomputation: for finite fields, the best DLOG algorithms factor into an expensive target-independent precomputation that can then be done once and then reused over and over again to quickly attack many targets in the same group, leading to attacks like logjam. An intelligence agency could use that to intercept TLS conversations in real time.
For a Diffie–Hellman function $f(n, P)$ with standard base point $B$—e.g., FFDH under RFC 3526 Group #14, or X25519—the adversary may have the public keys $f(n_1, B),$ $f(n_2, B),$ $\dotsc,$ $f(n_t, B)$, for $t$ different unknown DH secrets $n_1, n_2, \dotsc, n_t$, along with oracles for $P \mapsto H(f(n_i, P))$ by claiming to have public key $P$ and trying to have an encrypted conversation with the $i^{\mathit{th}}$ user. The goal is to recover any one of the $H(f(n_i, f(n_j, B)))$ shared secret keys used by user $i$ and user $j$ to have a private conversation.
Of course, when $f(n, P) = [n]P$ in a group written additively, this can be solved by any generic DLOG algorithm. But the oracles provide additional information that could be exploited—Lim–Lee active small subgroup attacks if the points $P$ live in a group of composite order, Cheon's strong DH attack if the key derivation function $H$ is the identity. These themselves don't provide batch advantages, but they are evidence that the DH problem is qualitatively different from the DLOG problem, so in principle it may admit batch advantages that DLOG does not.
For a signature scheme the goal is to forge a message/signature pair $(m, \sigma)$ under any of $t$ public keys $A_1, A_2, \dotsc, A_t$. The story depends on the details of the cryptosystem; see an analysis of Schnorr signatures in the multi-target setting for example. The countermeasure chosen by EdDSA, for example, is to hash the public key in with the message to limit the avenues for multi-target signature forgery.
answered Nov 19, 2019 at 21:18
$\begingroup$
$\endgroup$
In a multi-target attack on a block cipher, the attacker is given ciphertext corresponding to several unknown keys, rather than a single key under other kinds of attacks. The rest of the setup depends on context.
In the archetypal multi-target attack, the adversary is given $n$ ciphertext blocks corresponding to a single known plaintext block encrypted under $n$ random keys. The attack enters these ciphertexts in a hash table allowing fast search, then make a trial encryption of the plaintext under incremental keys, followed by a search of the result in the table. The expected cost of finding a key, measured in trial encryptions, is reduced by a factor of $n$ compared to brute force in a single-target attack.
For a large-enough block width, using a block cipher in CTR mode with a random IV make that attack infeasible.