I found on Twitter an interesting blog post on breaking (EC)DSA and was writing a lengthy comment when some weird combination of keystrokes shutdown my browser and ate my comment, so I thought I'd write a blog post instead.
The post raises an important point, namely that one should always validate domain parameters, but I'm not sure whether the issues it describes can be found in real world applications. I haven't seen any protocol or application in which (EC)DSA signers take domain parameters from some external source. In practice, signers either generate these parameter themselves (e.g., using openssl dsaparam), or pick one of the well-known, standard parameters (e.g., named curves in ECDSA).
Also, if Mallory can choose g and if Alice doesn't validate it, infinite loop is the least of Alice's concern, because Mallory might as well choose g such that Alice's private key has small order, and thus can be easily recovered. A corollary to the Sylow theorems shows that given a finite group G and a prime number p dividing the order of G, then there exists an element (and hence a subgroup) of order p in G. Since the order of a DSA group is always p - 1 = 2 * q there exists a g that generates a subgroup of order 2. That g is p - 1. If q is not a prime (which is not required in FIPS 186) there exists many g that generate small subgroups -- any such g can be used to conduct the aforementioned key recovery attack.
The same attack should work against ECDSA. The blog post mentioned invalid curve attacks in the context of ECDSA, but the issue is actually key recovery. If Mallory can choose not only the base point, but also the curve, he can choose an arbitrary curve and a base point with small order on that curve. If Mallory can choose only the base point, but not the curve, he's out of luck because the curves used in ECDSA usually have prime order that is also the order of all but the identity point, which usually doesn't have a valid encoding.
In summary, I suspect that the issues highlighted in the blog post might never happen in real life, but when they do they are definitely less of a concern than losing private keys.
But if one looks at these issues in the context of (EC)DH things get more interesting. There are many real-world scenarios where the (EC)DH params come from a somewhat untrusted source. For example:
1/ In SSL during the handshake the server can choose DH domain parameters. Failure to validate DH parameters has led to the Triple Handshake Attack. It seems that the server can also choose ECDH domain parameters, but I'm not sure whether Openssl or Boringssl supports arbitrary curves -- they might support only named curves.
2/ Since generating DH parameters is expensive, people usually use only one set of parameters, stored in a DHParam file. With temporary write access to this file one can install a permanent backdoor by modifying one or two bits. Last year it was found that the hardcoded DH params in socat contained a non-prime p.
To find and fix these issues, I'm thinking about adding some tests to Project Wycheproof to ensure that key generation utilities behave correctly when fed with malicious domain parameters.
For ECDSA/ECDH, the key generation utilities should reject domain parameters if one of these conditions are not met:
1/ p is a prime
2/ base point G is on curve
3/ the order of G is a prime and order * G is the identity
4/ cofactor is small (<= 8?)
5/ order * cofactor is within the Hasse's bound
But for ECDSA/ECDH one should always use named curves, and reject everything else.
For DSA/DH, the conditions are:
1/ p is a prime
2/ 1 < g < p - 1
3/ the order of the subgroup q is a prime
4/ g^q = 1 (mod p)
5/ q and p have relatively reasonable sizes (e.g., if p has 2048 bits, q should have minimum 112 bits)
As Bleichenbacher noted, the order q is usually missing from the DH parameter spec, thus we cannot really test condition #3, #4 and #5. To fill in the gap of the missing q, Bleichenbacher uses a brilliant trick that you should check out.
The post raises an important point, namely that one should always validate domain parameters, but I'm not sure whether the issues it describes can be found in real world applications. I haven't seen any protocol or application in which (EC)DSA signers take domain parameters from some external source. In practice, signers either generate these parameter themselves (e.g., using openssl dsaparam), or pick one of the well-known, standard parameters (e.g., named curves in ECDSA).
Also, if Mallory can choose g and if Alice doesn't validate it, infinite loop is the least of Alice's concern, because Mallory might as well choose g such that Alice's private key has small order, and thus can be easily recovered. A corollary to the Sylow theorems shows that given a finite group G and a prime number p dividing the order of G, then there exists an element (and hence a subgroup) of order p in G. Since the order of a DSA group is always p - 1 = 2 * q there exists a g that generates a subgroup of order 2. That g is p - 1. If q is not a prime (which is not required in FIPS 186) there exists many g that generate small subgroups -- any such g can be used to conduct the aforementioned key recovery attack.
The same attack should work against ECDSA. The blog post mentioned invalid curve attacks in the context of ECDSA, but the issue is actually key recovery. If Mallory can choose not only the base point, but also the curve, he can choose an arbitrary curve and a base point with small order on that curve. If Mallory can choose only the base point, but not the curve, he's out of luck because the curves used in ECDSA usually have prime order that is also the order of all but the identity point, which usually doesn't have a valid encoding.
In summary, I suspect that the issues highlighted in the blog post might never happen in real life, but when they do they are definitely less of a concern than losing private keys.
But if one looks at these issues in the context of (EC)DH things get more interesting. There are many real-world scenarios where the (EC)DH params come from a somewhat untrusted source. For example:
1/ In SSL during the handshake the server can choose DH domain parameters. Failure to validate DH parameters has led to the Triple Handshake Attack. It seems that the server can also choose ECDH domain parameters, but I'm not sure whether Openssl or Boringssl supports arbitrary curves -- they might support only named curves.
2/ Since generating DH parameters is expensive, people usually use only one set of parameters, stored in a DHParam file. With temporary write access to this file one can install a permanent backdoor by modifying one or two bits. Last year it was found that the hardcoded DH params in socat contained a non-prime p.
To find and fix these issues, I'm thinking about adding some tests to Project Wycheproof to ensure that key generation utilities behave correctly when fed with malicious domain parameters.
For ECDSA/ECDH, the key generation utilities should reject domain parameters if one of these conditions are not met:
1/ p is a prime
2/ base point G is on curve
3/ the order of G is a prime and order * G is the identity
4/ cofactor is small (<= 8?)
5/ order * cofactor is within the Hasse's bound
But for ECDSA/ECDH one should always use named curves, and reject everything else.
For DSA/DH, the conditions are:
1/ p is a prime
2/ 1 < g < p - 1
3/ the order of the subgroup q is a prime
4/ g^q = 1 (mod p)
5/ q and p have relatively reasonable sizes (e.g., if p has 2048 bits, q should have minimum 112 bits)
As Bleichenbacher noted, the order q is usually missing from the DH parameter spec, thus we cannot really test condition #3, #4 and #5. To fill in the gap of the missing q, Bleichenbacher uses a brilliant trick that you should check out.