On testing (EC)DH and (EC)DSA
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.
Comments
I agree that the scenario in which the domain parameters are possibly provided by the attacker is a scenario I am yet to encounter in real life and I must confess I missed the small subgroup attacks possibilities. What is interesting is that FIPS 186 is actually allowing the domain parameter to be provided by a third party, even an untrusted one. IMO, this means that libraries implementing digital signature schemes should also support this somewhat peculiar use case and not dismiss it as "not actually used", since it's not because we have never heard of such a case that it cannot happen.
Regarding your concern for non-prime q in the DSA case, the FIPS 186 still require it to be a "a prime divisor of (p – 1)" by definition, hence domain parameters validation would also mitigate that problem... If libraries were to provide their users with a mean to perform such validation!
I'd also like to mention that when performing "only" signatures in the frame of a communication with an attacker, leaking the private key generated for the attacker's domain parameters is a big problem, for sure, but if it is an ephemeral key, then it's not that much of a concern, however the DoS ability a simple signature grants to the attacker is still a non-negligible problem, and a pernicious one.
I've also already seen implementations falling into an infinite loop on signature verification on attacker provided public keys... (But because of a bug in the arithmetic operations) Imagine how SSH servers could be affected.
Regarding the ECDH, it's on my "todo list" since a while, because I'm curious about how many implementations are checking those correctly. What's interesting also with DSA and ECDSA, is that currently, I've only found CryptoPP getting those correctly. Most libraries are completely lacking domain parameters validation.
> I agree that the scenario in which the domain parameters are possibly provided by the attacker is a scenario I am yet to encounter in real life and I must confess I missed the small subgroup attacks possibilities. What is interesting is that FIPS 186 is actually allowing the domain parameter to be provided by a third party, even an untrusted one. IMO, this means that libraries implementing digital signature schemes should also support this somewhat peculiar use case and not dismiss it as "not actually used", since it's not because we have never heard of such a case that it cannot happen.
Yeah, I agree that this might happen.
> Regarding your concern for non-prime q in the DSA case, the FIPS 186 still require it to be a "a prime divisor of (p – 1)" by definition, hence domain parameters validation would also mitigate that problem... If libraries were to provide their users with a mean to perform such validation!
Even if they validate q and check 1 < g < p -- which should prevent both issues you mentioned -- setting g = p - 1 still works.
> I'd also like to mention that when performing "only" signatures in the frame of a communication with an attacker, leaking the private key generated for the attacker's domain parameters is a big problem, for sure, but if it is an ephemeral key, then it's not that much of a concern, however the DoS ability a simple signature grants to the attacker is still a non-negligible problem, and a pernicious one. I've also already seen implementations falling into an infinite loop on signature verification on attacker provided public keys... (But because of a bug in the arithmetic operations) Imagine how SSH servers could be affected.
I agree that infinite loop is a concern, but I'm not following the logic on ephemeral key. If the signer generates an ephemeral ECDSA key for every session, how does the verifier authenticate the key? Usually the signer has to sign the ephemeral key with some other long-term key. That means the ephemeral key can be reused, unless it's short-lived. I haven't see any protocol that relies on ephemeral ECDSA keys though.
> Regarding the ECDH, it's on my "todo list" since a while, because I'm curious about how many implementations are checking those correctly. What's interesting also with DSA and ECDSA, is that currently, I've only found CryptoPP getting those correctly. Most libraries are completely lacking domain parameters validation.
If you're into automated crypto testing, I recommend taking a look at Wycheproof. It has a lot of tests and has uncovered many bugs in many libraries.
Cheers :)
You are right, I was stuck trying to imagine a scenario in which I could envision attacker-provided domain parameters and it involved ephemeral keys, but yeah it does not make sense in any practically used case I'm aware of. But so does the domain parameters being provided by the client. What I meant was that if there exist some scenario in which such attacker-provided domain parameters may happen, I agree that we should be worried by both problems.
> If you're into automated crypto testing, I recommend taking a look at Wycheproof. It has a lot of tests and has uncovered many bugs in many libraries.
Yup, I've discovered it in December and added to my todo list to try out your test-vectors when you'll release them in a nicely formatted way, as announced.
See you, hopefully at BH :)
PS : to avoid data loss on "cat walking on the keyboard causing random browser shutdowns", the Lazarus browser extension used to be excellent, however its development ended.