Should Curve25519 keys be validated?
research.kudelskisecurity.com
research.kudelskisecurity.com
>The first thing you learn in any infosec class is to reject invalid inputs, and check return values for errors, even if there’s no obvious exploit in sight. Doing this is sometimes called “defense in depth” or “best practice”.
Rejected invalid inputs is often a good idea, but it isn't defense in depth and it isn't automatically best practice. Always doing something because you "learned it an infosec class" is dogmatic.
>The point of Diffie-Hellman is that both key shares should equally contribute to the shared secret, so that the protocol doesn’t allow key control, a desirable attribute of any authenticated key agreement protocol, as discussed in this MQV paper. If the protocol allows a peer to force the shared secret to be zero, or more generally to lie in a subgroup, then the said peer can surreptitiously weaken the protocol’s security (objection: “but why would a peer be malicious?”).
This point was refuted earlier in the article. "If a peer is malicious, than they can do much worse than sending invalid keys".
> It’s costless: adding a zero check is ten lines of code tops, which is unlikely to introduce new vulnerabilities nor to hurt performance.
Ten lines of code isn't costless, it is low cost. Even if it were costless, it would still be better to not do it unless there is a compelling reason to do it.
> It reduces the risk of non-obvious attacks. Take Signal’s protocol, for example. If Alice generates all-zero prekeys and identity key, and pushes them to the Signal’s servers, then all the peers who initiate a new session with Alice will encrypt their first message with the same key, derived from all-zero shared secrets—essentially, the first message will be in the clear for an eavesdropper. Alice can deny being malicious, arguing that her PRNG failed. That’s just an example scenario—granted, far-fetched—but there might be others, and checking for invalid keys is probably easier than proving that they will never be exploited.
Not only is this not a "non-obvious attack", this is the only possible attack. The only thing that adding a check to prevent a zero key can do is prevent someone from using a zero key. By the way, this attack gains nothing. Any malicious user already has the ability to publicize any messages sent to them.
AKA, if the deniability of your protocol depends on the random keyspace of more than one actor, a vector that allows some actor to compress the space of permitted keys could allow an inference of more-likely potentially valid keys vs invalid keys, thus disproving or at least weakening the deniability of the protocol.
As for the malicious peer problem -- the malicious peer is the very model of state-sanctioned surveillance. I think it would be an exercise in willful blindness at the least to pretend that does not exist.
> As for the malicious peer problem -- the malicious peer is the very model of state-sanctioned surveillance.
I'm really not sure what you mean by this. Some peers might be malicious, but this attack gains them nothing. This is true whether the peer is a state actor, or an 11 year old. Please try to have a basic understanding of what you are talking about before you accuse other people of engaging in willful blindness.
Rejected invalid inputs is often a good idea, but it isn't
defense in depth and it isn't automatically best practice.
Always doing something because you "learned it an infosec
class" is dogmatic.
Garbage in is garbage out isn't just an excuse; it should be a design goal.
Real world example: data injection bugs. To this very day many exploits rely on SQL injection or shell injection bugs. We've known forever that the proper solution to these bugs isn't to escape or validate input strings. The analysis logic, being entirely divorced from the SQL or shell parsing code, will always be out-of-step and susceptible to bit rot. The proper solution is to design your interfaces so that user data strings are never intermingled with code strings. In SQL that means using parameter substitution using "?".
Another example: The Lua VM is a byte code interpreter. In Lua 5.1 that byte code loader included a verification pass that tried to ensure sane byte code is loaded. The problem is that that the verifier was different code from the execution component, and there were always constructs the verifier missed which could cause the execution component to enter unexpected states that could lead to arbitrary memory reads or writes. In Lua 5.3 there is no longer any byte code verifier. It was ripped out entirely. Some of the time spent on the verifier was spent improving the execution engine to handle bad byte code better. More importantly, there's no verifier for people to blame when they rely on loading untrusted byte code. Lua 5.3 is no less secure than Lua 5.1, and arguably more secure.
Another example: arithmetic overflow. Many arithmetic overflow bugs come from code which tried to validate the range of inputs but missed some corner cases. Usually it's better and easier to refactor the algorithm so that malicious inputs provably produce benign (if non-sense) outputs. It's one reason why I always used unsigned integers in the context of data structure descriptions. Unsigned modulo arithmetic ensures that I'll always be dealing with positive values, removing the need to deal with negative values (not to mention worry about the undefined nature of signed overflow). There are exceptions, and unsigned integers are hardly sufficient alone, but on balance that approach is simpler and significantly improves the robustness of memory management in C.
Input validation is really only good for debugging and diagnostics. Often the earlier you can catch invalid input the better your diagnostics can be. That's a user interface issue, though. If your architecture relies on validation for correct behavior, I would argue it's likely to be fundamentally broken. Or rather, the more it relies on validation the further from it is from ideal software.
Indeed, that's the whole idea behind Curve25519--that any 32-byte secret key is a valid key, so it's impossible to generate a bad key. Likewise, any 32-byte public key and any nonce is equivalent to any other in the sense of not compromising your own secret key when deriving a shared secret. Nothing depends on validation, where logic fundamental to the security of the code is sprinkled around the code in non-obvious places. Curve25519 is designed to be as fool-proof as possible.
There are exceptions, as always. And we can't always write perfect software. But I think that best practice is generally that the secure and correct functioning of software SHOULD NOT rely on input validation. Period.