dotnet / dotnet/runtime

EC keys on prime curves with order > prime are not well handled.

Open
#129,003 1 comment 0 reactions 1 assignee Claimed by @vcsjones View on GitHub
area-System.Security
Dominant language
C#
Stars
18.3k
Forks
5.6k
PR merge metrics
PR metrics pending

Description

### Description

The platform generally makes an assumption that ECParameters.D must be the same size as ECParameters.X. ECParameters.X is bounded by P for a prime field, and should always export at P's width. But the order of a curve is `p + 1 - t`. And while it's easy to read the next part as `t <= 2 * sqrt(p)`, it's actually `abs(t) <= 2 * sqrt(p)`, meaning t can be negative, meaning the order can exceed p. (Finding t is someone else's problem).

What this means, in practice, is that we don't handle the curves secp160r1 or secp160r2 very well, since their order not only exceeds p, it requires more bytes than p to write down.

https://www.secg.org/SEC2-Ver-1.0.pdf:

> 2.4.2 Recommended Parameters secp160r1
> ...
> p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 7FFFFFFF
> ...
> n = 01 00000000 00000000 0001F4C8 F927AED3 CA752257
> ...
>
> 2.4.3 Recommended Parameters secp160r2
> ...
> p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFAC73
> ...
> n = 01 00000000 00000000 0000351E E786A818 F3A1A16B
> ...

### Reproduction Steps

Windows:

```csharp
using ECDsa key = ECDsa.Create(ECCurve.CreateFromFriendlyName("secp160r2"));
ECParameters ecParameters = key.ExportParameters(true);
Console.WriteLine($"D: {Convert.ToHexString(ecParameters.D)} ({ecParameters.D.Length} bytes)");
Console.WriteLine($"X: {Convert.ToHexString(ecParameters.Q.X)}");
ecParameters.Validate();
Console.WriteLine($"Y: {Convert.ToHexString(ecParameters.Q.Y)}");
```

Alternatively, try to import this private key ("Yes, I know I have disclosed a private key to the Internet. It was generated randomly just for this issue."):

```
-----BEGIN EC PRIVATE KEY-----
MFECAQEEFQAAQ+ZgQKDF0mmGtq/wYyUDWL9fbaAHBgUrgQQAHqEsAyoABBt4wKB0
66SbKjhoqta8j97oMX2OE1tPaFvKeXzO4ga5+DYDhlYQ4LY=
-----END EC PRIVATE KEY-----
```

### Expected behavior

Since ceil(log2(p)) is 160, X and Y should export as 20 bytes. Since ceil(log2(n)) is 161, D should export as 21 bytes.

Alternatively: The key, generated by OpenSSL, should import.

### Actual behavior

D exports correctly. X and Y export to the size of D, and when doing so end up with padding on the RIGHT, which invalidates their values. Every rerun will end with an X or Y ending in 00.

```
D: 00F57EE1271B3FB45A090CE7C51710418D7DDB1F19 (21 bytes)
X: 139AD3350F777B5497821F099979BB412FC245CD00
Y: C1C8643C97132A08C874D4E0EB33996BB102186C00
```

Alternatively:
```
Unhandled exception. System.Security.Cryptography.CryptographicException: ASN1 corrupted data.
at System.Security.Cryptography.EccKeyFormatHelper.FromECPrivateKey(ECPrivateKey key, AlgorithmIdentifierAsn& algId, ECParameters& ret)
at System.Security.Cryptography.EccKeyFormatHelper.FromECPrivateKey(ReadOnlyMemory`1 keyData, AlgorithmIdentifierAsn& algId, ECParameters& ret)
at System.Security.Cryptography.EccKeyFormatHelper.FromECPrivateKey(ReadOnlySpan`1 key, Int32& bytesRead)
at System.Security.Cryptography.ECAlgorithm.ImportECPrivateKey(ReadOnlySpan`1 source, Int32& bytesRead)
at System.Security.Cryptography.ECDsaWrapper.ImportECPrivateKey(ReadOnlySpan`1 source, Int32& bytesRead)
```

### Regression?

_No response_

### Known Workarounds

_No response_

### Configuration

_No response_

### Other information

_No response_

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.