5 ms·

Curious, why don’t we integrate the algorithm and its parameters into the public key?

tialaramex 7y ago
The X.509 structure does put all of this together, it's just that cryptographers will tend to refer to the actual numbers which vary from one to another as the "public key" as a shorthand, they know the rest of the context is important but it's not what they're talking about right now. In RSA for example there's a public exponent, yours is almost invariably going to be 65537 and most of the time nobody will even mention this parameter, but the "same" key with exponent 3 would actually be a different key than yours. In code such shorthand becomes a bug. If you only allow a handful of named algorithms the bug is essentially useless to adversaries. Microsoft's non-standard decision to allow parametrised curves makes it into a huge attack surface.
- sroussey 7y ago
  Yeah, I get that! There would still be a named curve though, and things do change over time. Sometimes I like to force things in such a way that you can’t avoid dealing with some issues. So, by putting these items in the public key, you are forced to look at them and deal with them when you write a library. Often, engineers will write code correctly because they know all the context. But the next engineer will likely have less and less context as time goes by. Thus forcing context acknowledgement, while seemingly redundant, might be essential to avoiding future bugs.
tptacek 7y ago
That's a general description of the problem, but the more pragmatic question to ask is "why do we support explicit curve parameters at all?". In practice, nobody uses them; virtually no organizations are even qualified to use them. Many platforms don't support them at all; it's not as if there's a serious compatibility argument for them. The right response to this vulnerability is to jettison support for anything but named curves. This is probably an inside-baseball argument for people who don't pay attention to elliptic curve implementation details. But it's easy to quickly understand. Go to SAFECURVES.CR.YP.TO; you'll see a big long list of curves, each with their parameters and some implementation details. In reality, only a subset of these curves are commonly used (P-224, P-256, Secp256k1, and Curve25519 probably account for 95% of all curves). Further, most specific curves are implemented not as parameters plugged into a generic elliptic curve scalar multiplication routine, but rather as curve-specific code (one of the major reasons we have different curves is to allow specific implementation optimizations). A browser that supports Curve25519 certainly uses Curve25519 code, not generic code. The "explicit curve" feature that blew up on Microsoft is designed to allow people to specify their own parameters, not for well-known curves but for curves they themselves generated. Nobody does that. There was a time, in the long long ago, when people thought that might be a good idea; nobody thinks that anymore; everyone thinks the opposite thing. If anything, we're trying to get rid of a bunch of curves. Certainly we shouldn't be randomly supplying new Weierstrass curves. So that's the problem here. A lot of cryptography engineers were probably surprised this CryptoAPI feature even worked. We had considered it awhile ago as a cryptopals challenge (and Sean actually did add it as one in Set 8 a few years ago), but we never dreamed anyone would be crazy enough to let this bug happen in the real world.
- sroussey 7y ago
  If it can, it will... :)
- dfox 7y ago
  I believe that there are users who do produce keypairs with arbitrary explicit curves: NSA and its equivalents in other countries. Such agencies tend to like to use secret algorithms and generating your own curve for internal use is somewhat sane way to do that for ECC. In other words I would not be to surprised if NSA found this bug by accident because it caused some of their internal “secret” cryptosystem to not work at all instead of by actively looking for it.
- RcouF1uZ4gsC 7y ago
  My feeling is that there has been a change in crypto. It seems in the past, crypto was a la carte. Over time, this has been shown to open up a big security vulnerabilities such as this one, and also issues with key agility in TLS, etc. I think the tendency today is to make make crypto more omakase where there are a few well studied, well implemented algorithms that you use for everything. The Windows CryptoAPI is from that older time.
  - WorldMaker 7y ago
    A small part of the problem is that the omakase options do change over time with changes in threat models and knowledge of vulnerabilities. One example is the recent push away from the NIST Curves to the more open knowledge Curve 25519, in part because of reasonable concerns that the NIST Curves were backdoored by NSA for easier cryptoanalysis. So you still need "low level" a la carte tools underlying and backing the omakase experiences. Part of the problem of the Windows CryptoAPI in question is that it has to serve "both customers", the omakase sort that need the best option, and the a la carte needs to higher level tools serving as the omakase option. That is, for some traditional/legacy C/C++ users that CrpytoAPI is about as high level as they will get, and it's up to the documentation to steer its consumers to the best omakase options. But crypto32.dll also is the low-level backend of tools like WinRT's Windows.Security.Cryptography and .NET's System.Security.Cryptography (on Windows). The push towards omakase and somewhat getting applications away from micromanaging the a la carte stuff, definitely seems the smart path. Handling the onion of it all in what needs to be supported at a low level to keep the high level omakase shop running smooth seems like it still has a lot of pitfalls.

The X.509 structure does put all of this together, it's just that cryptographers will tend to refer to the actual numbers which vary from one to another as the "public key" as a shorthand, they know the rest of the context is important but it's not what they're talking about right now. In RSA for example there's a public exponent, yours is almost invariably going to be 65537 and most of the time nobody will even mention this parameter, but the "same" key with exponent 3 would actually be a different key than yours. In code such shorthand becomes a bug. If you only allow a handful of named algorithms the bug is essentially useless to adversaries. Microsoft's non-standard decision to allow parametrised curves makes it into a huge attack surface.

sroussey 7y ago
Yeah, I get that! There would still be a named curve though, and things do change over time. Sometimes I like to force things in such a way that you can’t avoid dealing with some issues. So, by putting these items in the public key, you are forced to look at them and deal with them when you write a library. Often, engineers will write code correctly because they know all the context. But the next engineer will likely have less and less context as time goes by. Thus forcing context acknowledgement, while seemingly redundant, might be essential to avoiding future bugs.

tptacek 7y ago

That's a general description of the problem, but the more pragmatic question to ask is "why do we support explicit curve parameters at all?". In practice, nobody uses them; virtually no organizations are even qualified to use them. Many platforms don't support them at all; it's not as if there's a serious compatibility argument for them. The right response to this vulnerability is to jettison support for anything but named curves. This is probably an inside-baseball argument for people who don't pay attention to elliptic curve implementation details. But it's easy to quickly understand. Go to SAFECURVES.CR.YP.TO; you'll see a big long list of curves, each with their parameters and some implementation details. In reality, only a subset of these curves are commonly used (P-224, P-256, Secp256k1, and Curve25519 probably account for 95% of all curves). Further, most specific curves are implemented not as parameters plugged into a generic elliptic curve scalar multiplication routine, but rather as curve-specific code (one of the major reasons we have different curves is to allow specific implementation optimizations). A browser that supports Curve25519 certainly uses Curve25519 code, not generic code. The "explicit curve" feature that blew up on Microsoft is designed to allow people to specify their own parameters, not for well-known curves but for curves they themselves generated. Nobody does that. There was a time, in the long long ago, when people thought that might be a good idea; nobody thinks that anymore; everyone thinks the opposite thing. If anything, we're trying to get rid of a bunch of curves. Certainly we shouldn't be randomly supplying new Weierstrass curves. So that's the problem here. A lot of cryptography engineers were probably surprised this CryptoAPI feature even worked. We had considered it awhile ago as a cryptopals challenge (and Sean actually did add it as one in Set 8 a few years ago), but we never dreamed anyone would be crazy enough to let this bug happen in the real world.

sroussey 7y ago
If it can, it will... :)
dfox 7y ago
I believe that there are users who do produce keypairs with arbitrary explicit curves: NSA and its equivalents in other countries. Such agencies tend to like to use secret algorithms and generating your own curve for internal use is somewhat sane way to do that for ECC. In other words I would not be to surprised if NSA found this bug by accident because it caused some of their internal “secret” cryptosystem to not work at all instead of by actively looking for it.
RcouF1uZ4gsC 7y ago
My feeling is that there has been a change in crypto. It seems in the past, crypto was a la carte. Over time, this has been shown to open up a big security vulnerabilities such as this one, and also issues with key agility in TLS, etc. I think the tendency today is to make make crypto more omakase where there are a few well studied, well implemented algorithms that you use for everything. The Windows CryptoAPI is from that older time.
- WorldMaker 7y ago
  A small part of the problem is that the omakase options do change over time with changes in threat models and knowledge of vulnerabilities. One example is the recent push away from the NIST Curves to the more open knowledge Curve 25519, in part because of reasonable concerns that the NIST Curves were backdoored by NSA for easier cryptoanalysis. So you still need "low level" a la carte tools underlying and backing the omakase experiences. Part of the problem of the Windows CryptoAPI in question is that it has to serve "both customers", the omakase sort that need the best option, and the a la carte needs to higher level tools serving as the omakase option. That is, for some traditional/legacy C/C++ users that CrpytoAPI is about as high level as they will get, and it's up to the documentation to steer its consumers to the best omakase options. But crypto32.dll also is the low-level backend of tools like WinRT's Windows.Security.Cryptography and .NET's System.Security.Cryptography (on Windows). The push towards omakase and somewhat getting applications away from micromanaging the a la carte stuff, definitely seems the smart path. Handling the onion of it all in what needs to be supported at a low level to keep the high level omakase shop running smooth seems like it still has a lot of pitfalls.