Invalid length of EC key attributes

[iromli]

Describe the issue

The JWKS generated by oxauth-client-with-dependencies.jar for EC keys sometime has different length for x and y attributes.

Example:

{
    "kty" : "EC",
    "use" : "sig",
    "crv" : "P-384",
    "kid" : "9b6a4b28-8cea-485c-8fe6-f8dd065c06d5_sig_es384",
    "x5c" : [ "..." ],
    "x" : "XXUnqb5rVa6Q2G6bR4YcZK6aQTHGchvRNkRfUZzu936GdLLjwGVFOtNHRPs0VY71",
    "y" : "AJ4fG38pZhMsFDjy5kjUDWJ_66qrYyqjyHDo9zmFMuQjYvOaFESqp22z-WrUErqucA",
    "exp" : 1637326084831,
    "alg" : "ES384"
}

{
    "kty" : "EC",
    "use" : "sig",
    "crv" : "P-521",
    "kid" : "09a4388a-0fcc-4056-a640-3ba14a578a1e_sig_es512",
    "x5c" : [ "..." ],
    "x" : "XoCyKW-V6l_RFVl3Fsrgfzbro0uotfdabr3blhIKhifxXNv_19N0xCNU0V0ETHEt8vdrwAjrF6pHTWLoj0vMJ7g",
    "y" : "AX-vlUaUTTjc2gX1fs6OUNXPEG0R0Sn75hbKO3h7IxkH_Y3qisHicDLWbagcpcBkzem31WxJUqoT7nOH1_ArYcjP",
    "exp" : 1637326242049,
    "alg" : "ES512"
}

Steps To Reproduce

Steps to reproduce the behavior:

1. Download the oxauth-client library from Gluu maven repo
2. Run the command: java -jar oxauth-client-with-dependencies.jar -sig_keys ES256 ES384 ES512 -dnname CN=testing -expiration_hours 2 -keystore testing.jks -keypasswd secret
3. Check the command output and compare the length of x and y attribute for each keyset.
4. Repeat the command again if issue isn't reproduced

Expected behavior

The x and y attributes has same length.

Actual behavior

Sometime the x and y attributes has different length.

Desktop (please complete the following information):

• Gluu version 4.3.x and above (and probably older versions)

Additional context

Support ticket: 10125

[moabu]

@smansoft please make sure this gets propagated upstream to the auth-server as well in Janssen.

[smansoft]

@shmorri
@yuriyz

I've checked key generation, using ECDSA (using Elliptic Curves over the Prime Finite Field),
using curve secp256r1 (P-256) and provided some investigate and as result I can assert, that
keys generation engine, implemented in Crypto Providers is correct and calculates correct keys.
Same engine is used with other curves secp256k1, secp384r1, secp521r1.

Follow steps have been provided:

1. Additional output has been added to the KeyGenerator/Crypto Provider and generated
   decimal, heximal and array sizes output of generated Public Keys and Private Keys, during
   execution of the KeyGenerator.

Results of this execution (6 launches of the KeyGenerator) uploaded (attached files):
jwks.1.txt
jwks.2.txt
jwks.3.txt
jwks.4.txt
jwks.5.txt
jwks.6.txt
.

2. New simple tool, SmEcc (attached file SmEcc.zip) has been developed. This tool is based on ECC tool:
   https://github.com/GaspareG/EccLib.

   Please, use:
   java -cp ./SmEcc-1.0-SNAPSHOT.jar com.smansoft.ecc.SmEcc
   for launching.

   This tool provides same calculations, which are provided during generation KeyPair by
   the KeyGenerator/Crypto Provider. Current version of the SmEcc tool uses only secp256r1 (P-256),
   but results of usage of other curves will be similar.

   SmEcc uses parameters of secp256r1 (https://www.secg.org/sec2-v2.pdf), i.e. same Base Point G
   and same Private Keys, which are generated by the KeyGenerator/Crypto Provider. SmEcc solves
   uncompressed form of the Base Point G and calculates Public Key (Elliptic Curve Point) from Base Point G,
   using Private Key.

   Results of SmEcc execution uploaded (attached file):
   SmEcc.out.txt
   .

3. Comparing of results:
   - Private/Public keys, generated by the the KeyGenerator
   - Private/Public keys, solved by the SmEcc tool
   has been provided.

   Results of this comparing has been uploaded (attached file):
   SmEcc_jwks_comparasing.txt
   .

As conclusion - KeyGenerator(s) and the SmEcc tool generate same Keys.
Lead padding zeros should be ignored.

This conclusion is same as for oxAuth as for jans-auth-server.

jwks.1.txt
jwks.2.txt
jwks.3.txt
jwks.4.txt
jwks.5.txt
jwks.6.txt
SmEcc.out.txt
SmEcc.zip

[smansoft]

@shmorri
@yuriyz

About different length of x and y coordinates of Public Key. Private Key(s), generated by
the KeyGenerator/Crypto Provider can have different length too.

It could be reproduced as, using KeyGenerators as in oxAuth as in jans-auth-server.

It's necessary (at the first step) to get some info about Elliptic Curves, about secp256r1
(let's we will use secp256r1 for this investigate) and about EcDSA.

Common form of Elliptic Curve on the Prime Field p is follow:
y^2 = x^3 + a*x + b (mod p),

where:
p - parameter of EC, defines finite prime field (Galois field), p should be a Prime Number;
a - parameter of EC;
b - parameter of EC;
x,y - Cartesian coordinates.

Common view of Elliptic Curve - attached image EC.png.

Also important parameters:
G - Base Point (x,y), that belongs to the Elliptic Curve.
n - big prime, that should be < p (big prime of the EC),
n defines finite prime field of a private key,
that is used with this curve (secp256r1),
N*G = 0, see (calc Base Point, Public Key 07), where G - Base Point.
x - Private Key, should be 1 <= x <= n-1, i.e. x = [1, n-1].

Standard defines
https://www.secg.org/sec2-v2.pdf
https://wiki.hyperledger.org/display/BESU/SECP256R1+Support
https://blog.enuma.io/update/2016/11/01/a-tale-of-two-curves-hardware-signing-for-ethereum.html
values of these parameters (excluding x).
x should be generated (random value), that should be 1 <= x <= n-1, i.e. x = [1, n-1], during
generation of the Private Key. x is a Private Key.

I.e. 1-st Conclusion: x (Private Key) can have various length (excluding lead padding zeros).

Standard defines (for secp256r1)
n = "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551",
length == 256 bits, i.e. 32 bytes.

So, 1 byte <= length(x) <= 32 bytes.
U - Public Key, that is a Point (ux,uy), that belongs to the Elliptic Curve.
U should be obtained from G (Base Point) and from x (Private Key), using:
U = x*G.

Obtained Point U(ux,uy) (Public Key) shouldn't me more then p (defines finite prime field (Galois field),
p should be a Prime Number).

I.e. 2-st Conclusion: U (Public Key) has two values (ux,uy), each shouldn't me more p and U
(Public Key) should belong to Elliptic Curve on the Prime Field p, i.e. ux and uy (coordinates)
can have various length (excluding lead padding zeros).

Standard defines (for secp256r1)
p = "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF".

length == 256 bits, i.e. 32 bytes.

So, 1 byte <= length(ux) <= 32 bytes and 1 byte <= length(uy) <= 32 bytes.

3-d conclusion: x (Private Key) is a random number,
U (Public Key) (ux, uy), i.e. Cartesian coordinates of some Point, obtained from
G (base Point). G and U belong to the Elliptic Curve on the Prime Field p.
x, ux, and uy can have various length.

[smansoft]

@shmorri
@yuriyz

Analyzing length of keys, generated by KeyGenerator, you can find, that some keys (secp256r1) have length, that equals 33 bytes.
for example:
jwks.2.txt
x.length = 32
y.length = 33
x (hex) = 54e5a2a032d5513f0fd7b787343eb72bc7246d1efd8d63b7943103a8100b771a
y (hex) = 00aea8d42c596b935b52f2453029bd2d2f1bd357f6aaefc7e0e893952d2a2cdeb3
Private Key:
d (length) = 32
d (hex) = 18149a67c569953734e361f3404b3c66d2daad6707365de5c8828da6c9eee645
or
jwks.3.txt
x.length = 33
y.length = 32
x (hex) = 00a4f3fb382dddbca235a63587b3cf2b0c7980e7e3b2802b3f469b7cd7d9c2c22d
y (hex) = 69d7b9d2e8660ba7a33ce9da1f05e584ae1a8f1dd0be872a2b75939f7a3600dc
Private Key:
d (length) = 33
d (hex) = 00b389abbbd95e9577a3ba201932e808d19a4d724680e48239d8209a8cc9ea485e

But we found (before), that length (secp256r1) of a Private Key x and Public Key U.ux, U.uy
shouldn't be more, then 32 bytes.

The root of this issue can be found, analyzing how java type java.math.BigInteger saves
big numbers (internal storage) in byte[] and how java.math.BigInteger saves negative
big numbers.

Attached file contains some examples:
big_integer_positive_negative.txt
.

Conclusion, that follow from analyzing examples from file: big_integer_positive_negative.txt
is follow:
- If a BigInteger is a positive number, first (oldest) bit of the byte[length-1]
(i.e. oldest byte) of byte[], that is used for presenting this BigInteger, should be 0.
- If a BigInteger is negative, byte[], that is used for presenting this BigInteger,
contains Bitwise Not of all bits + 1 (presenting of all negative numbers). In this case first bit of
byte[length-1] contains 1 (Bitwise Not of 0).
- If a BigInteger is a positive number and first (oldest) bit contains 1 (for example, oldest byte ==
0xA5, i.e. 10100101), one more oldest lead padding zeros byte will be added. In this case,
length of byte[], that presents this BigInteger will be increased (+1).
- If a BigInteger is a positive number and oldest bit contains 0 (for example, oldest byte ==
0x5B, i.e. 01011011), no any changes of byte[] will be produced.

This conclusion explains, why:

x.length = 32
x (hex) = 54e5a2a032d5513f0fd7b787343eb72bc7246d1efd8d63b7943103a8100b771a

and

y.length = 33
y (hex) = 00aea8d42c596b935b52f2453029bd2d2f1bd357f6aaefc7e0e893952d2a2cdeb3

00 added, as 0xae contains oldest 1.

So. This is not a problem for Java and BigInteger, if some byte[] contains lead padding zeros byte,
as it is defined for positive BigInteger(s), which contain(s) oldest 1 in oldest bit.

All BigInteger have correct values (during calculations), after import these arrays:
as
00aea8d42c596b935b52f2453029bd2d2f1bd357f6aaefc7e0e893952d2a2cdeb3 (contains lead zeros)

as
54e5a2a032d5513f0fd7b787343eb72bc7246d1efd8d63b7943103a8100b771a (doesn't contain lead zeros)
.
big_integer_positive_negative.txt

[smansoft]

@shmorri
@yuriyz

Also, some additional investige has bee provided - is it possible remove lead padding zeros byte
(from byte[], that presents BigInteger) before converting (using Base64) and exporting it to
Json format (jwks). Possible it can be usefull, as some not java third party applications can read
jwks. These applications can generate error(s) during importing keys with lead padding zeros bytes.

Project SmEcc (attached file SmEcc.zip) contains function SmEcc.checkTruncPorcessing().

This function privides follow activity:
1. Receives input BigInteger value.
2. Provides print of BigInteger value.
3. Solves negate BigInteger negateValue (negateValue == -value).
4. Provides print of BigInteger negateValue.
5. Gets byte[] of the BigInteger value content, i.e. byte array of value data.
This array contains lead padding 0 byte (0x00).
6. Removes lead padding 0 byte (0x00) and creates fixed byte[].
7. Makes Base64 encoding/decoding of source byte[] of the value.
8. Creates new (BigInteger value2) from decoded data.
9. Provides print of BigInteger value2.
10. Makes Base64 encoding/decoding of fixed byte[]
(without lead padding 0 byte (0x00)) of the value.
11. Creates new (BigInteger valueFixed) from decoded data.
12. Provides print of BigInteger valueFixed.
13. Compares input BigInteger value and new BigInteger valueFixed.

checkTruncPorcessing(new BigInteger("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16)); // length 33 bytes (zero lead padding)
checkTruncPorcessing(new BigInteger("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16)); // length 32 bytes (no zero lead padding)

Results of execution - attached file big_integer_positive_negative.txt.

Conclusion, that follow from examples from the file: big_integer_positive_negative.txt
is follow:
- There are some problems, during import byte[] with removed lead padding zeros byte
if oldest bit of byte[] contains 1.

This call
checkTruncPorcessing(new BigInteger("ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16)); // length 33 bytes (zero lead padding)
outputs:

value(16) = 00000000000000000000000000000000ffffffff00000001000000000000000000000000ffffffffffffffffffffffff
valueFixed(16) = -000000000000000000000000000000000000000fffffffeffffffffffffffffffffffff000000000000000000000001
value and valueFixed aren't equals
.

big_integer_positive_negative.txt

[iromli]

@smansoft @yuriyz there's report that even when x and y length are identical, there was issue using the keys

Just a new information, We have figured out that even when it generates EC keys with equal x and y length they may be both wrong,
We have an OIDC integration in that the RP is made in GO Lang, anf Go was complaining about wrong EC keys We had to disable all EC keys from JWKS in order to work with this GO Lang RP client

I'm not sure if this is related to this issue or not.

[smansoft]

@iromli
@yuriyz
@shmorri

EC keys are ok, just some of them presented with lead padding zeros byte, so, they length is 33 bytes. It could be a problem,
if Go or some other language, reading jwks don't take into account this lead padding zeros byte.

I think, it's possible - remove lead padding zeros byte before export, and then in Java code, it can be restored (lead padding zeros byte).

If it's important, it could be implemented.
I just thought, that this Issue generated only viewing keys. If third-party or some non-Java code reads jwks, there are two ways:

• these applications should take into account the lead padding zeros byte and size 33 bytes instead 32 bytes (secp256r1);
• lead padding zeros byte should be removed before export and then added during import/reading jwks, if reading key contains oldest bit == 1.

[smansoft]

@iromli
@yuriyz
@shmorri

I think, I can try to use second way (remove and then restore lead padding zeros byte).

[smansoft]

@yuriyz
@shmorri
@iromli

I.e. I think, that the problem is not that keys length are different, but that some of them have length == 33, but shouldn't be more then 32.
It's for secp256r1 and secp256k1. Same for secp384r1 and secp521r1 with correspondent length for these Curves.

[smansoft]

@shmorri
@yuriyz
@iromli

One more file (it was lost) has been uploaded. This file shows, that keys (private and public), generated by the KeyGenerator and by the SmEcc tool (SmEcc.zip) are same.

SmEcc_jwks_comparasing.txt

[smansoft]

@shmorri
@yuriyz
@iromli

During testing on multiple generation Keys for Elliptic Curve secp256r1 I got periodically keys with length like that:

s.length = 32
s (hex) = 67c1cbe41e7ee7acd350bf00893d0389192eac9e120923851cb028adf41f6aa1
keyX = eG1YGBygUMFquNSW73ctYTsmJy7G_B6LoYpo24ksHA
keyY = IyThP7ujS3b-mvAJCKCWwxcJQtGWWXfr02MCkd2tRkQ
x.length = 31
y.length = 32
x (hex) = 786d58181ca050c16ab8d496ef772d613b26272ec6fc1e8ba18a68db892c1c
y (hex) = 2324e13fbba34b76fe9af00908a096c3170942d1965977ebd3630291ddad4644

s.length = 32
s (hex) = ab2b6fc60e37b592c43dd977083108b49f05acb9cf34e63a7c9ccc6a5d63b6d2
keyX = CN1k705vFam-LslBSxJQMDM7UmJVIoUSPcf9nRJcyg
keyY = Otlyo2esm0bhjkiaqH4utfVtzvZ_j6TuY5vybjbrcZ0
x.length = 31
y.length = 32
x (hex) = 08dd64ef4e6f15a9be2ec9414b125030333b5262552285123dc7fd9d125cca
y (hex) = 3ad972a367ac9b46e18e489aa87e2eb5f56dcef67f8fa4ee639bf26e36eb719d

I.e. x.length != y.length.
This output contains fixed keys format, i.e. lead padding zeros byte have been removed.

These keys are ok, as SmEcc Tool (SmEcc.zip) generates same Public Keys (Points) with these Private Keys:

--- BigInteger --------
prvKey08(10) = 000000000000000000046930632092166479204000182147315426259283873339155067766768355692120207485601
prvKey08(16) = 0000000000000000000000000000000067c1cbe41e7ee7acd350bf00893d0389192eac9e120923851cb028adf41f6aa1
prvKey08(length) = 32
prvKey08(bitCount) = 120
prvKey08(bitLength) = 120
--- BigInteger --------
--- Point --------
pubKey08(zero)X(10) = 000000000000000000000212776313139784149203537378024393477714711558255509635141216012273776667676
pubKey08(zero)X(16) = 0000000000000000000000000000000000786d58181ca050c16ab8d496ef772d613b26272ec6fc1e8ba18a68db892c1c
pubKey08(zero)X(length) = 31
pubKey08(zero)X(bitCount) = 118
pubKey08(zero)X(bitLength) = 118
pubKey08(zero)Y(10) = 000000000000000000015896110805911587456299083414924911758073608843403163359105732686543554692676
pubKey08(zero)Y(16) = 000000000000000000000000000000002324e13fbba34b76fe9af00908a096c3170942d1965977ebd3630291ddad4644
pubKey08(zero)Y(length) = 32
pubKey08(zero)Y(bitCount) = 123
pubKey08(zero)Y(bitLength) = 123
--- Point --------

--- BigInteger --------
prvKey09(10) = 000000000000000000077422242964935246334495259246278790184574567216312933764271707090177935783634
prvKey09(16) = 00000000000000000000000000000000ab2b6fc60e37b592c43dd977083108b49f05acb9cf34e63a7c9ccc6a5d63b6d2
prvKey09(length) = 33
prvKey09(bitCount) = 133
prvKey09(bitLength) = 133
--- BigInteger --------
--- Point --------
pubKey09(zero)X(10) = 000000000000000000000015662783657438058054733089245341753235079848637405990552544389865386695882
pubKey09(zero)X(16) = 000000000000000000000000000000000008dd64ef4e6f15a9be2ec9414b125030333b5262552285123dc7fd9d125cca
pubKey09(zero)X(length) = 31
pubKey09(zero)X(bitCount) = 118
pubKey09(zero)X(bitLength) = 118
pubKey09(zero)Y(10) = 000000000000000000026618342235359373053149226661316149703285546791581511930132394698262455218589
pubKey09(zero)Y(16) = 000000000000000000000000000000003ad972a367ac9b46e18e489aa87e2eb5f56dcef67f8fa4ee639bf26e36eb719d
pubKey09(zero)Y(length) = 32
pubKey09(zero)Y(bitCount) = 147
pubKey09(zero)Y(bitLength) = 147
--- Point --------

Lead padding zeros byte haven't been removed in this output.

I.e. Parts of Public Keys can be different. But they shouldn't have length bigger then 32 byte (for secp256r1).

[smansoft]

@shmorri
@yurem
@iromli

There is some important detail about ES512 (secp521r1).

As defined by standard and taking into account p and n values, length of Private Key
and coordinates of Public Keys, Point (x,y) should not be more then 521 bits.

https://www.secg.org/sec2-v2.pdf
https://cryptobook.nakov.com/digital-signatures/exercises-secp256k1-sign-verify

I.e. max length of arrays - 66 bytes (for saving 521 bits).
If length of key is 66 bytes - oldest byte always - 0x01.
But often we can get keys, which have length 65 bytes.

Examples (4 Key Pairs, Curve secp521r1):

s.length = 66
s (hex) = 01eee712a7432b9333c5e2abd19308956e4b49807f789d3aa2f3f5394969f8a5f7dbfedfbd0ca413c431a3f7ba0f89d46433dc5ef9068d9a545ab798584d7c0131f5
keyX = AbbRSjEAbVXTUV8LnWnv9bscSZPjEYbsc2aZeZIIA-D9nvOmoOd03ICOLSsZh1G6lyS8iRb01xp3vRl6cGQZ3qmL
keyY = ZMjxbk8k7miwb_Nh3y8e6siOvtpfiQFkNs0QG6qvAtcdIt4IrJGGC9lEYWE86FGdu1xf8pwKaBKmjWrei9YIT9o
x.length = 66
y.length = 65
x (hex) = 01b6d14a31006d55d3515f0b9d69eff5bb1c4993e31186ec73669979920803e0fd9ef3a6a0e774dc808e2d2b198751ba9724bc8916f4d71a77bd197a706419dea98b
y (hex) = 64c8f16e4f24ee68b06ff361df2f1eeac88ebeda5f89016436cd101baaaf02d71d22de08ac91860bd94461613ce8519dbb5c5ff29c0a6812a68d6ade8bd6084fda

s.length = 65
s (hex) = 95abf0859d819d6be873e79095de27f30d7b1afd39b724f3e8a4b2580b82c282e36cf376ba960cb1ab0b832c63cb1f4760ca339dcf8c38ce92ce26e80f42002609
keyX = AacyW9O-gRQI_FZN9TSgchPOtbN-xtfutMPxgHAb94iatX4MjSoE_M3YsTZsB2KbX-BfBRGclXdEQSrXm2SttqMz
keyY = AR1k4J6zejkA8RoXKT91JkDubIJrPGioRx4bzHPjcdl7IbQk8kPWKF08wWn_-yJDjeBcIOuOCyNgqXVKC3zjvVI5
x.length = 66
y.length = 66
x (hex) = 01a7325bd3be811408fc564df534a07213ceb5b37ec6d7eeb4c3f180701bf7889ab57e0c8d2a04fccdd8b1366c07629b5fe05f05119c957744412ad79b64adb6a333
y (hex) = 011d64e09eb37a3900f11a17293f752640ee6c826b3c68a8471e1bcc73e371d97b21b424f243d6285d3cc169fffb22438de05c20eb8e0b2360a9754a0b7ce3bd5239

s.length = 65
s (hex) = 0c5ca50327ace2dc3891ddf512b7bfe269c5bdcf33b8a194903fe3106ba7723ef72786fd570924584d613aef2e832557acc009baa9b4cc211fb04089cdb5d0eb94
keyX = gL8oCzg3ajy0j35CjaOEHOkd-57xvEtozrtmgvHwOUYdjahhjpU62q4Kr9t3iSy5L8iOQORjaTViAjBdS2rdGOU
keyY = G0KGX11pEzjHnmwCjD8HRlrLHy_2nkVuegBoLNeJn38ta-GQU4DgUvWaOKvk8oQnTQuGgO3ZnW9yhV2m2SiYM_Q
x.length = 65
y.length = 65
x (hex) = 80bf280b38376a3cb48f7e428da3841ce91dfb9ef1bc4b68cebb6682f1f039461d8da8618e953adaae0aafdb77892cb92fc88e40e46369356202305d4b6add18e5
y (hex) = 1b42865f5d691338c79e6c028c3f07465acb1f2ff69e456e7a00682cd7899f7f2d6be1905380e052f59a38abe4f284274d0b8680edd99d6f72855da6d9289833f4

s.length = 66
s (hex) = 010f393d40f16a560aa1fda6e4b4eecdfb4dac37a7126a54ac25399739317120d371251353bd29109a56d4b4f7627869478e3b587ccc79722642829c7528163a8c37
keyX = AWLEqrcCMTGTcVw-jb1KR28lN_Hg048gennDY8faCH-DW2Wc5i1lNOxR9MXSAvEEjPhJLe96OdSDOPKbMo_fNSEo
keyY = AWZUmpPnk24IFRJFdOaSVEU2Bg2p9JlqtQ1-1aqGzhDJzSe3B2JP9Ttdf9w7odJk9qkwi84FYEtLsf7CGNTVMc73
x.length = 66
y.length = 66
x (hex) = 0162c4aab702313193715c3e8dbd4a476f2537f1e0d38f207a79c363c7da087f835b659ce62d6534ec51f4c5d202f1048cf8492def7a39d48338f29b328fdf352128
y (hex) = 0166549a93e7936e0815124574e692544536060da9f4996ab50d7ed5aa86ce10c9cd27b707624ff53b5d7fdc3ba1d264f6a9308bce05604b4bb1fec218d4d531cef7