ECDsa.Create(ECParameters) behavior is not consistent across platforms with a public/private key mismatch

[bartonjs]

Create an ECParameters for secp256r1 (ECCurve.NamedCurves.nistP256) with

D = 9F9BD156374FB78F3D69EFF10DEF8C296EC4F03EACA42F4257130D0CE9316FCD, Q.X = 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296 Q.Y = 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5

(That X/Y pair is for the curve point G, not the key point Q)

On Linux (via OpenSSL)

Unhandled Exception: Interop+Crypto+OpenSslCryptographicException: error:100B107B:elliptic curve routines:EC_KEY_check_key:invalid private key at System.Security.Cryptography.ECOpenSsl.ImportParameters(ECParameters parameters)

On Windows, success (the Q value seems to be rederived from D).

Since it's probably hard to make Linux and macOS coerce Q, it's probably more practical to make Windows throw (theoretical process: NCryptImportKey, then NCryptExportKey and compare the target Q value, then dispose the new key handle and throw before replacing the existing key handle).

[vcsjones]

@bartonjs I can pick this up if you want; or at least noodle around with some ideas. I have some spare cycles to pick up 3.0 bugs. Let me know if you think there is something else that would be a better use of my time.

[bartonjs]

@vcsjones Any progress / are you still looking at this one? https://github.com/dotnet/corefx/issues/37595 seems pretty similar.

[vcsjones]

@bartonjs I haven't made any significant progress. I was meant to get back in the swing of things but only a few hours ago have I managed to figure out why I could not build CoreFX for the past two weeks due to dotnet/corefx#37907 😅

I'll be looking at this very near term.

[bartonjs]

Given that this isn't new in 3.0 I'm moving to Future (PRs while 3.0 is still open are still welcome).

[vcsjones]

and compare the target Q value

Hm. One thing that makes this interesting is insignificant zeros. For example, these parameters work fine with OpenSSL:

var dStr = "000087E2DD50E8204FB80A5FBFC041859CCE0730ACCE1A828918E01461E468DDAD87";
var qYStr = "000038C4CDC289845DF49CDA665A64339D57FF900E231BD57082021493ECC21B325B";
var qXStr = "0000253DA14B518037CF07D578614E46CA8EA071FB9B4374EF05AD45418A81675828";

However when exported again, the insignificant zeros are not included. So if we do a import / export / test in Windows and compare byte-for-byte, we end up with a scenario where Windows does not tolerate insignificant zeros, but OpenSSL does, and the behavior remains inconsistent.

You can't blindly pull off zeros, either, since the curve points may legitimately need the octets to be the appropriate size. For example:

D: CFB75FF7B9BB2F53D4A50703285C3DE78C24F1E21486DE59F83E27C317BB4EF1
X: 000026B190372A1899972893526864834DE5ECB17BE8A852424A7B99C95A86C9
Y: 63DFF42F953F6F6EE94CF674C01D537F82C0979B878588A7F28B5CD232283A30

I think then, the appropriate way to handle this then is, when exporting for comparison, we assume that the import validated the points are on the curve. When comparing, compare the octets from the end using the smallest number of octets. For the one that is bigger, if there is, assert that the remainder are zeros.

For example, given:

"000087E2DD50E8204FB80A5FBFC041859CCE0730ACCE1A828918E01461E468DDAD87"

is exported as

"87E2DD50E8204FB80A5FBFC041859CCE0730ACCE1A828918E01461E468DDAD87"

Compare from the end of the byte array (since big endian) using the number of bytes that was exported (32) and verify the rest are zeros.

[bartonjs]

Yeah, X.Slice(X.Length - exportedX.Length).SequenceEqual(exportedX) seems like a reasonable comparison.

[bartonjs]

(Er, and that any remaining bytes of X were zero)

[vcsjones]

For the sake of completeness, if your D, QY and QX all have leading zeros, you can import them still with OpenSSL (haven't checked Windows, yet). e.g. these work:

var dStr = "DFEE4545BF488935EEC834DEBB1DD256CD87D8C7894EFC50E5722627169941";
var qYStr = "B8A6F5DC31A1D416CEBC694307FD99BE4E1EEC623A332A71E03A827DF58554";
var qXStr = "618DB65F240DBA24D745959BF4CE260E0F946856A4DF2450915416EBCA7FBA";

These are 31-byte values for a p256 curve.

So it's possible that the byte values imported are smaller than the ones that get exported.

[vcsjones]

Heh, well, macOS will not import 31-byte points for p256, nor will it tolerate "zero padded" values. It is pickier.

[bartonjs]

The most consistent behavior, then, would be to determine the correct parameter size post-import and reject it if it was non-canonical. (Alternatively, on macOS create a new key using the the curve identifier, memoize the resulting size (okay, yeah, currently there's only the 3 so they could be hard coded), and fix up the parameters to be canonical.)

[vcsjones]

@bartonjs this has been on me for a while, sorry about that. I will pick this one back up again, but some new developments have happened. Since we can now re-compute Q from D on macOS and Linux, we can without a big lift (I don't think) make those match Windows' behavior. If creating with Q fails, but we have D, derive Q and try again.

This to me seems (probably) better since making Windows throw is more disruptive, and we tend to use Windows' behavior as a source of truth.

[bartonjs]

Yeah, I'm generally a fan of throwing, but since we already don't on netfx or corefx-win then "work everywhere" is an easier sell than "break some things" if both are viable.

[vcsjones]

(This is a brain dump of "stuff" just so future Kevin knows what present Kevin recently learned)

I picked this up (again, determined to make progress on it) and it seems that Windows' behavior is not entirely understood. It appears to re-derive Q... sometimes. This for example, will fail:

using ECDsa ecdsa = ECDsa.Create(ECCurve.NamedCurves.nistP256);
ECParameters ecParams = ecdsa.ExportParameters(true);
ecParams.Q.X.AsSpan().Fill(0xFF);
ecParams.Q.Y.AsSpan().Fill(0xFF);
ecdsa.ImportParameters(ecParams);

Unhandled exception. Internal.Cryptography.CryptoThrowHelper+WindowsCryptographicException: The requested operation is not supported.

My current thinking right now is that Windows will re-compute Q only if whatever Q it was supplied with is on the Curve (as we already know, CNG will also re-compute in the case of Q=(0,0) but it handles that differently)

Here is another example that "works" where the Q value is on the Curve, but G × D != Q:

using ECDsa ecdsa = ECDsa.Create(ECCurve.NamedCurves.nistP256);
ECParameters ecParams = ecdsa.ExportParameters(true);
ecdsa.GenerateKey(ECCurve.NamedCurves.nistP256);
ECParameters otherKey = ecdsa.ExportParameters(false);
ecParams.Q = otherKey.Q;
ecdsa.ImportParameters(ecParams);

Another interesting quirk is that CNG appears to export the original, bad, Q. Consider:

string key = @"MHcCAQEEIHChLC2xaEXtVv9oz8IaRys/BNfWhRv2NJ8tfVs0UrOKoAoGCCqGSM49AwEHoUQDQgAErZsBkBjHlngjE2f3bN0Jil7wEE/V1O4Py5WLjhP6TSnGBIG3xpZ3Kc2iXHA31di60AOVC1K8HVpivFKrvGIT9A==";
using ECDsa ecdsa = ECDsa.Create();
ecdsa.ImportECPrivateKey(Convert.FromBase64String(key), out _);
string exported = Convert.ToBase64String(ecdsa.ExportECPrivateKey());
Console.WriteLine(exported == key);

This will print "true". So as far as we can see, the key did not change when being washed through CNG.

But if you run the key through openssl, we can see it is invalid.

base64 --decode << 'EOF' | openssl ec -check -inform der -noout
MHcCAQEEIHChLC2xaEXtVv9oz8IaRys/BNfWhRv2NJ8tfVs0UrOKoAoGCCqGSM49AwEHoUQDQgAErZsBkB
jHlngjE2f3bN0Jil7wEE/V1O4Py5WLjhP6TSnGBIG3xpZ3Kc2iXHA31di60AOVC1K8HVpivFKrvGIT9A==
EOF

EC Key Invalid! 140177670411584:error:1010207B:elliptic curve routines:ec_key_simple_check_key

What I am thinking then, if we want to match Windows.

1. OpenSSL we can get pretty close. We can distinguish between "point not on curve" and "This Q is not for that D".

   1. If EC_KEY_set_public_key_affine_coordinates fails when importing, we have it the case of "Q is not on the curve". We continue to let this fail to match Windows.
   2. We make it to EC_KEY_check_key and that fails. This is what Windows is handling. If we fail here, and we have D, then we can re-compute Q.
   3. When "exporting", OpenSSL behavior will differ from Windows. OpenSSL will export the Q based on whatever it calculated from D. Windows will export whatever the caller supplied. If we really wanted OpenSSL to match Windows, we would have to stash the original Q for the lifetime of the key and personally I don't see a ton of value in that.

2. macOS does not let us make this distinction. The key either imports, or it doesn't. We can try again if the import fails without Q if we have D. MacOS would also have the same export characteristics as OpenSSL.

[bartonjs]

When Windows is in a mismatched Q state, what does the public key export say? (Imported Q or correct Q?) Even if that's the "imported" Q we could... complicatedly... always double-import, once with Q as-was, once with Q=0, and then normalize the behavior across mismatches.

[vcsjones]

what does the public key export say?

Everything is consistent. If I import with a wrong Q in ImportECPrivateKey then ExportParameters(false) and ExportSubjectPublicKeyInfo are the caller supplied Q, so "imported" everywhere.

we could... complicatedly... always double-import, once with Q as-was, once with Q=0

😅 This seems like a minor behavior deviation that doesn't justify the complexity, IMO. (Your house, your rules though). The end result would be consistent across platforms from signing / verification, even if you export it and import it it again. You just can't easily observe the Q correction in Windows.

[vcsjones]

On the macOS 11 front, the behavior here is... strange. No exception is raised anywhere but a simple signature round-trip does not work.

string key = @"MHcCAQEEIHChLC2xaEXtVv9oz8IaRys/BNfWhRv2NJ8tfVs0UrOKo
AoGCCqGSM49AwEHoUQDQgAErZsBkBjHlngjE2f3bN0Jil7wEE/V1O4Py5WLjhP6TSnGB
IG3xpZ3Kc2iXHA31di60AOVC1K8HVpivFKrvGIT9A==";
using ECDsa ecdsa = ECDsa.Create();
ecdsa.ImportECPrivateKey(Convert.FromBase64String(key), out _);
Console.WriteLine(Convert.ToBase64String(ecdsa.ExportECPrivateKey()));

byte[] data = new byte[16];
RandomNumberGenerator.Fill(data);

byte[] signature = ecdsa.SignData(data, HashAlgorithmName.SHA256);
bool valid = ecdsa.VerifyData(data, signature, HashAlgorithmName.SHA256);
Console.WriteLine(valid); // False!

This occurs in netcoreapp3.1 too, so there hasn't been a regression. I will dig to see if I can make any sense out of what is happening.

[vcsjones]

It looks like, because the Apple PAL has a handle for both the public key and the private key, we are tearing apart the public key and private key from ECPrivateKey in to ECParameters.

So we end up with a private key for D, and a public key for an unrelated Q. It seems then we are signing with one key and verifying with another.

The easiest fix is to ignore Q if we have D.