Handle unexpected Y coordinate of ECDH to allow Tang to use HSM-backed keys

[t0rr3sp3dr0]

Note

If this proposal is accepted, the changes will need to be implemented in both Clevis and José, not here, but since this pertains to Tang, I think it makes sense to discuss it here first. Feel free to transfer this issue to another repository if appropriate.

Background

I'm currently working on implementing a Tang-compatible server whose private key is secured on Apple's Secure Enclave. The idea is that Tang will run on an iOS device, and you won't be able to extract the private keys from it. But the platform is not really relevant here, and everything I'll say below applies to a VM that uses AWS KMS to store the private keys or a bare-metal server with a YubiKey connected to it.

Problem

I hit a roadblock where most, if not all, APIs of secure elements only allow you to perform ECDH with compact output (i.e. only the X coordinate is returned and the Y coordinate is discarded), but ECMR needs both coordinates to work. No API for elliptic curve arithmetic exists to get the raw result of the multiplication of the remote public key by the local private key. And you clearly can't do the multiplication yourself since you don't have access to the key material.

Solution

Disclaimer, I'm no math expert and Copilot was the one who came up with the idea. But I validated it and it seems like a really good solution. It definitely works.

Since the compact output of ECDH is the X coordinate, and we know the elliptic curve, we can calculate the two possible values of Y that, together with X, result in a point on the curve by solving y² = x³ + ax + b (mod p). But since the value of Y matters for the ECMR algorithm, we need to know which one to return to the client on the recovery request.

The solution proposed was to add a hint to the payload sent to Tang by Clevis that will tell the server to either return the value of Y that is odd or the one that is even. Apparently, it is a property of elliptic curves with odd moduli, which all cryptographic curves are because their modulus is prime, that both possible values of Y for some X in the curve have different parity.

So, José would check if the Y value obtained during the ECMR provisioning process in the ECDH key exchange is odd or even, and return that to Clevis along with the encrypted data. Clevis would store that value, which would later be sent to Tang. Finally, Tang would compute the value of X and determine the two values of Y, returning the correct one based on the hint provided in the request.

This perfectly addresses the issue and is 100% retrocompatible with the existing implementation. Tang code wouldn't even need to change, as the extra JSON field will simply be ignored. José and Clevis will require patches, but small ones.

TL;DR

I'm proposing that José tell Clevis whether the Y coordinate of the point resulting from the ECHD key exchange during provisioning is odd or even, and that Clevis store that information and later forward it to Tang so it can perform all cryptographic operations of ECMR on a secure element, such as a Smart Card.

[t0rr3sp3dr0]

Regarding the format of the payload containing the hint to be sent to Tang, I'm thinking on this:

• prt for parity
• 0 for even
• 1 for odd

  {
    "alg": "ECMR",
    "crv": "P-521",
    "kty": "EC",
+   "prt": "0",
    "x": "ABTz7h96x_5A3Bxt86PHlBaXYslPlI8mqkbrHzKqafYhlWNeedzMhHL8b3SyN_zyZnpYt3UcHjDPbelj2OfHvVoe",
    "y": "AMHlK3o46uT8hg5rVp0DlXl55Fu2dbkdcczi7RR95FBcoe19ZiJeWjZCktbYf4X4UBoT3kqn6wq9Y8kqUTnoUMnz"
  }

  {
    "alg": "ECMR",
    "crv": "P-521",
    "kty": "EC",
+   "prt": "1",
    "x": "AALpFoEElGKSTMCQQwlmjf8O0IRoGm9x8TxUwSh6XuSt8QTuaG4EwBYJzBNYUBsxRgn0BBkeY3MNtsCzK57Frjz2",
    "y": "ARZeOAtZDIdEAaM5pzakQGCUVOHaw5WmQcoe7RDnnvzgjr5Gn-XgSGp2zKlj8ZRDniRNc0ec8ymfYyGXtig2_Q18"
  }

[npmccallum]

This seems reasonable. This would weaken the strength of the algorithm by one bit. But that's probably acceptable.

I'd love to learn about your use case! Feel free to email me privately if you're able.

[t0rr3sp3dr0]

@npmccallum, I was writing a PoC and noticed I made an oversight during my initial testing. The proposed solution doesn't work, since it would require the client to have a private key for the point resultant from the addition of the client and ephemeral public keys. But that's unknown, so there's no way to compute the hint for Y without access to the server's private key.

With that said, there's another alternative, not as elegant, but at least a tad more secure than the original proposal, as we don't need to disclose that extra bit from the key to the server. Please, let me know what you think!

New Proposal

The server may or may not be able to calculate the exact value of the shared key's Y coordinate, depending on whether or not it's able to perform scalar multiplication instead of ECDH with compressed output. But, if there is some integrity-check mechanism to validate the data after it was decrypted, the client can always determine if that key is valid or not. If the validation fails, the client can easily compute the other value of Y by subtracting it from the curve's P value and try to use it instead.

I propose that, while encrypting, we hash the plaintext data together with the initialization vector and save the value in the JWE header. Then, during the decryption process, we check the hash against the decrypted data and IV, rejecting the encryption key in case they don't match. In that scenario, the other value for Y would be calculated and the decryption process executed one more time.

Some Considerations

1. Assuming we use SHA-256 as the hash function, I think storage shouldn't be a concern. It would only take 44 bytes to store the value in Base64.

2. Since the hash value will include the IV value, it will not be possible to correlate it with the plaintext data. So we are not leaking any secret information by having that value in the JWE header.

3. The decryption process would fail more slowly when an incorrect key is given. Still, we wouldn't be adding any additional time when the current implementation of Tang is used, since it always returns the correct Y coordinate, thus there won't be a scenario where the client needs to try using the alternative value of Y.

4. As for side channel attacks, I think the only additional information one would get is that we tried to use the value of Y returned, but the decryption failed, and we had to use the other Y coordinate to decrypt the data. If this is really a concern, we can always calculate the second coordinate value, decrypt the data using both keys, calculate the hash of both plaintext results, and return the correct one. Of course, this would increase the decryption time, but not by a lot, given the small amount of data we are dealing with.

5. Regarding retrocompatibility, the added hash value in the encrypted payload will be ignored by existing implementations, and the server must give the correct value of Y at all times. A new version of José would check whether there's a hash for the data stored in the encrypted payload and enable the retry mechanism if there is. Otherwise, it would assume the Y coordinate returned by the server is the correct one and return whatever was obtained after decrypting the data with that key.

6. With this approach, we could technically disregard the value of Y returned by the server altogether and compute it in the client. But I don't know if that's a good idea. It really depends on whether you have a more powerful client or a more powerful server. The proposal, as is, splits processing between the client and the server. We can add this as a final fallback if you would like.

JWE Header

  {
    "alg": "ECDH-ES",
    "clevis": {
      "pin": "tang",
      "tang": {
        "adv": {
          "keys": [
            {
              "alg": "ES512",
              "crv": "P-521",
              "key_ops": [
                "verify"
              ],
              "kty": "EC",
              "use": "sig",
              "x": "AVFT-ncMR2kXoNt-3OJEO5K56IY7yUSLUPuG4w17-freh-0DdwvnRXS13zxCYjFdZb4KwF2YBaF6P7fHAJp7L8x6",
              "y": "ABgYukZ4600Da2x6XlWuMdbAgFw05XsY5x3YP6uZqydTh4FquYvkQ8fqHWx0blsJBy5PP0MiiwUuKQseEAe5bfap"
            },
            {
              "alg": "ECMR",
              "crv": "P-521",
              "key_ops": [
                "deriveKey"
              ],
              "kty": "EC",
              "x": "ASLL8SHJml5cLOxIMMyfhprgfJQbCaA7Hmymrsf4RzcypIwAlYTaFDyL8NG57awqaK9kuLhBlfS6bNiBnogn0_w5",
              "y": "AAp-l8m7AR9mfOieYTZwLqPwpA7yRpQagZNz4WqhLEs_BEznFO4fBVGBCskJChqrIBTKmEwOOxBUKm9X4utlTbWU"
            }
          ]
        },
        "url": "http://host.docker.internal:8080"
      }
    },
    "enc": "A256GCM",
    "epk": {
      "crv": "P-521",
      "kty": "EC",
      "x": "AX8yZ-vYOgiD7OBNs_ovmauMRLyu2ZAduYSwR2KW5OGqI4kS3cmVFxlTHeV71t0ShYGh1Egcoz7vQGvUhVl3r2Dm",
      "y": "AWiefrTTpTCfzwkuE68a8NE7zrTHQV0gcddnoh9nENQ7TdY8_7MV7-dHnaqtR6J-tpnoKIHDWMIVYs-Ou6DhAObY"
    },
-   "kid": "oF8mtMPiXAXa8T89OXduzTz1ykpd9IQINOb5d8w-Is8"
+   "kid": "oF8mtMPiXAXa8T89OXduzTz1ykpd9IQINOb5d8w-Is8",
+   "sum": "sha-256;tPFQttL5-mYZzBZD0VWA8l1iNyfvKW8tIGhnNTzWuFA"
  }

[npmccallum]

Doesn't the JWE already provide integrity? If so, just use that. It would be better to avoid implementing custom integrity schemes.

[t0rr3sp3dr0]

@npmccallum, unfortunately you can give the wrong key to José, and it will still succeed in decrypting the payload without throwing an error. Of course, it won't give you the plaintext data in that scenario, but it will happily give you a bunch of random data. Data that you cannot know programmatically if it is really the expected output of the decryption process or just garbage from using the wrong key.

But I also didn't like my second proposal, so I came up with something in between my original proposal and the new one. Hopefully the last. And this time I have a working PoC.

3rd Proposal

Instead of hashing the plaintext data, which is questionable, we can rely on the EC operations themselves to do a better job. My idea was to get the shared key at the end of the ECMR key exchange when the client is encrypting something, and perform scalar multiplication of the shared key with a new ephemeral key. The private part D of this new ephemeral key and the X and Y coordinates of the point resulting from the scalar multiplication would be persisted in the protected header of the JWE. Those values cannot be used within a reasonable amount of time to recover the shared key used to encrypt data, as you would need to solve the discrete logarithm problem to accomplish that.

Then, when decrypting the data, the process goes as usual until the client gets what is usually the correct shared key, but it may be the wrong one, as it is in my case when the server returns the incorrect value of Y. With the candidate shared key in hand, the client can perform the same scalar multiplication that was performed during encryption and check whether the result matches what is stored in the protected header. If it does, the key is correct and you can use it. Otherwise, you know the key is wrong because the value of Y is mirrored. In that case, you simply flip Y to the correct value and use it to compute the right shared key.

Header Changes

Here, we need to persist the value of D for the new ephemeral key and the values of X and Y from the scalar multiplication with the shared key. The payload is identical to epk, with the addition of D.

  {
    "alg": "ECDH-ES",
    "clevis": {
      "pin": "tang",
      "tang": {
        "adv": {
          "keys": [
            {
              "alg": "ECMR",
              "crv": "P-521",
              "key_ops": [
                "deriveKey"
              ],
              "kty": "EC",
              "x": "AP2kOQXsLqbx0cqONnLZ542LQPhDRW5R0ZrCId0EJyvGlckY0isIi_sSYOugdq8jYkC_aXgDX5Xd4ufpW3unAeuD",
              "y": "AEPEIyffomjJYEK2NKDzbkJiSP7ToQiTy2dUSeh_BCCRHFtP9KFZi2y9ak_zl-wOqjkGNNe7a0qNotyj3p_Sh_9z"
            },
            {
              "alg": "ES512",
              "crv": "P-521",
              "key_ops": [
                "verify"
              ],
              "kty": "EC",
              "x": "ARhcUk4potzLSJd_HcCOOSEdW49jaR86p0OHJLOY7j2OicrTGvtAc1Nm9DOU3pZpXbdi-KJ6CuY3HUxIYZEhIRYt",
              "y": "AQ7FlAEPe9MxeRgCMo5TD4WyH0_OHF1MmP0Nf5vVQdAeJa7mYhpBsuoD5yzOvz69ZCRLd5s8vdV0IvLqKbrQfUwK"
            }
          ]
        },
        "url": "http://127.0.0.1:7500"
      }
    },
    "enc": "A256GCM",
    "epk": {
      "crv": "P-521",
      "kty": "EC",
      "x": "AIhcuse5SpX6m57yM9tP4BcstVOuvqd_B5y_pCesZmIg_wDE2CBCcSM0oWgMDAJ7T8eMBfnz-goITZZ7ygt_zEWj",
      "y": "AYaeUAPw8Nw1OgLI3P745k2tDQHksmPc76dI8-41HnWo3lb2czmxpGWcX0WwSK7mvcooWssZIH2PSNpk2IHpMBVq"
    },
-   "kid": "8EWHke2KKny-AbCdx64dNreDxVl_np2urcczYFOnKXo"
+   "kid": "8EWHke2KKny-AbCdx64dNreDxVl_np2urcczYFOnKXo",
+   "vkp": {
+     "crv": "P-521",
+     "d": "AeML2bvxwDLuwK3deHzPYcYAhM3kXWt9bSlpWVZ_JXc0BjzKglfSPvBHkIBwqIDCQjJyMuFx9PdrSmo3cRQ-lZcZ",
+     "kty": "EC",
+     "x": "Af0ojb0cR6m98NFQq89eo2bdO0gf3wn4K2xBUYqUZI0Wspq-GaRBIbNw4dnB-ky-pnoDjgHcaBP_3Qv4dgh8uxzN",
+     "y": "AAjI5wHxvhJpN6eVr3sZAib8gxfUiC6_EzumJ43PWj3PzVfz3NGrK5zCzbKtnvjUusY5qFVJf6mhWqWqcBIGET8p"
+   }
  }

PoC

These are the changes that I had to make in Clevis and José to implement this new scheme. It's not a lot of code, and it is working very well. I don't think we're introducing any new attack vectors to Tang by making these changes.

• latchset/clevis@HEAD...2b656c3

• latchset/jose@HEAD...e267907

Note that this is just a PoC. I haven't submitted any PRs yet, as I would like to discuss first whether this would be acceptable and if this is the right way to accomplish what I need.

Please let me know what you think. If that sounds good, I'll work on polishing the code and writing the documentation and tests for the new changes.

[tsmish]

Are we even sure that compact representation doesn't contain the sign of Y? From what I understand you interface with HSMs using PKCS11. PKCS11 v2.40 Current Mechanisms says in Table 29 that points may be in compressed or uncompressed form. I assume these refer to ANSI X9.62. According to Section 4.3.6 of ANSI X9.62-1998 Draft compressed form contains "rightmost bit of Y" from which you can recover Y using method in Section 4.2.

I tried to make a PoC, but I can't figure out how to make PKCS11 token multiply a point by a number (ECDH1_DERIVE produces shared key instead of point).

Also from what I understand X-only multiplication is a feature of Montgomery curves and all APIs using for example NIST curves should provide a way to get Y.

[t0rr3sp3dr0]

@tsmish, the compact representation does not contain the sign of Y (see the BoringSSL implementation: https://cs.opensource.google/boringssl/boringssl/+/fips-20251031:crypto/ecdh/ecdh.cc;l=48). We can recover the possible values of Y, as I do in my last proposal and PoC. However, the problem is that we don't know which of the two possible values of Y is the correct one, and if we use the wrong one, the output of the decryption process will be gibberish. My proposal addresses this problem by adding a hint for the value of Y.

Regarding my use case, I'm not necessarily using PKCS#11. There can be a PKCS#11 compatibility layer on the HSM, but what matters is what its native API supports. And there's generally no built-in API or anything in the PKCS#11 specification that allows raw point multiplication:

• Apple Secure Enclave: https://developer.apple.com/documentation/cryptokit/secureenclave/p256/keyagreement/privatekey/sharedsecretfromkeyagreement(with:)
• AWS KMS: https://docs.aws.amazon.com/kms/latest/APIReference/API_DeriveSharedSecret.html
• Yubico YubiHSM: https://docs.yubico.com/hardware/yubihsm-2/hsm-2-user-guide/hsm2-cmd-reference.html#derive-ecdh-command

[t0rr3sp3dr0]

Sorry, I had misunderstood some of your points in my last answer and made some updates above to reflect that.

Reading the document you shared, the technique of Section 4.2 looks promising! It that works, we can go back to my original proposal and add a single bit of Y to the JWE header (the most significant instead of the least significant). I'll do some testing and share the results.

[tsmish]

@t0rr3sp3dr0 Thanks for the links, I could only find ones that use PKCS#11 (who knew CloudHSM has different docs).

You are basically trying to abuse shared secret computation to get x-coordinate. I think you are correct in that there is no Y coordinate in result. There could be some problems with this approach though: for example looking through Apple docs you shared I think you can only get a hash of a x-coordinate.

In general APIs seem to provide shared secret generation, so as far as the result is the same they are considered good. Whether API gives you raw untruncated x-coordinate is kind of implementation detail. I think you can make PKCS#11 work (as long as result fits in the key). KMS docs link to a file where result is just x-coordinate so it might work (but example does not make sense, PublicKey decodes as RSA). YubiHSM I have no idea.

[t0rr3sp3dr0]

Okay, I ran some tests and the algorithm of Section 4.2.1 of ANSI X9.62-1998 does indeed address all our needs. Thanks for sharing that, @tsmish!

Just a small correction on what you said earlier, the information that we need to store together with X is the parity of Y, not the sign of Y. So my original proposal was actually correct, I just didn't have the right method to recover Y based on that information.

[t0rr3sp3dr0]

Yeah, those new Apple APIs are annoying. But you can use the old ones to get the raw value of X from ECDH: https://developer.apple.com/documentation/security/seckeycopykeyexchangeresult(_:_:_:_:_:). There will always be a way to get that value if the HSM supports ECDH, otherwise it would not be compliant with the standard as it would give you an incompatible value to use in existing deployments.

[t0rr3sp3dr0]

Using the Y-coordinate recovery algorithm in a Tang-compatible server, the changes required to Clevis and José would be:

• latchset/clevis@HEAD...96faa42
• latchset/jose@HEAD...2003261

@npmccallum, what do you think? I believe you were inclined to accept my original proposal, this is exactly it.

[tsmish]

Wait, I don't think that can possibly work. Do you store parity of cJWK, eJWK, dJWK or something else?

Here is original comment I was writing in case you might find something useful from it:
You need parity of yJWK and you don't have that. You can't use parity of dJWK because it may be different.
For example in SageMath (curve = P-384, S=2, C=9, E=2):

sage: # P-384 from https://std.neuromancer.sk/nist/P-384
sage: p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff
....: K = GF(p)
....: a = K(0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000fffffffc)
....: b = K(0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef)
....: E = EllipticCurve(K, (a, b))
....: G = E(0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7, 0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f)
....: E.set_order(0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973 * 0x1)
sage: ss = 2
sage: sc = 9
sage: se = 2
sage: ps = ss*G
sage: pc = sc*G
sage: pe = se*G
sage: sK = sc*ps
sage: def recover_y(x):
....:     return sqrt(x^3+E.a4()*x+E.a6())
....: 
sage: sK
(34429855560887023830027157256491844407698150085078517128883278572169373728452383777100642953115867010842220140663773 : 10655417716051068769455925959593809874150611898738562019488735405961481992690168700078510292831368720397121666073890 : 1)
sage: recover_y(sK.x())
10655417716051068769455925959593809874150611898738562019488735405961481992690168700078510292831368720397121666073890
sage: # recovery matches sK.y()
sage: px = (pc+pe)
sage: py = px*ss
sage: py
(4037079655992372679582590312787347175320421173714855583963058362442622296308654087238477221299965571118011425596215 : 34982603616028343265924201492929559450127298509075716843779427827937719281972279008697409454893381921278819676115033 : 1)
sage: recover_y(py.x())
4419402580366135946354838607214054354952440761389729824168865576308002489524591320349856633365556080582787296997286
sage: # recovery doesn't match py.y(), need to flip
sage: recovered_y = E(py.x(), recover_y(py.x()))
sage: sK
(34429855560887023830027157256491844407698150085078517128883278572169373728452383777100642953115867010842220140663773 : 10655417716051068769455925959593809874150611898738562019488735405961481992690168700078510292831368720397121666073890 : 1)
sage: recovered_y - se*ps
(21063931473827478656631576943226203273617859465875497753549974079466601123425559473570590237502673043475122978188928 : 10240828718432964931751800214156325033564328849819602448669912404789842191117952572125184255282610572759173340751973 : 1)
sage: # As expected without flipping result is wrong
sage: -recovered_y - se*ps
(34429855560887023830027157256491844407698150085078517128883278572169373728452383777100642953115867010842220140663773 : 10655417716051068769455925959593809874150611898738562019488735405961481992690168700078510292831368720397121666073890 : 1)
sage: # After flipping things are fine

You might think you can store parity of dJWK and compare with parity of unblinded value, but you can probably find parameters that result in same unblinded value parity with both decodings of yJWK.

Here are the table that I used for finding values (second value is "sign" of Y, third is a parity):

sage: [(i, int((i*G).y())/int(p) > 0.5, int((i*G).y())%2 == 1) for i in range(1,50)]
[(1, False, True),
 (2, True, False),
 (3, True, True),
 (4, True, True),
 (5, True, False),
 (6, False, False),
 (7, True, False),
 (8, True, False),
 (9, False, False),
 (10, True, True),
 (11, False, True),
 (12, True, False),
 (13, True, False),
 (14, True, False),
 (15, False, False),
 (16, True, True),
 (17, False, False),
 (18, False, False),
 (19, True, True),
 (20, False, True),
 (21, False, False),
 (22, True, True),
 (23, False, False),
 (24, False, False),
 (25, True, True),
 (26, True, False),
 (27, True, False),
 (28, False, False),
 (29, False, True),
 (30, False, True),
 (31, True, False),
 (32, True, True),
 (33, True, True),
 (34, True, False),
 (35, True, True),
 (36, True, True),
 (37, False, True),
 (38, False, False),
 (39, False, False),
 (40, False, False),
 (41, True, False),
 (42, True, True),
 (43, True, True),
 (44, True, True),
 (45, True, True),
 (46, False, True),
 (47, False, False),
 (48, True, False),
 (49, False, False)]

I used "sign" for finding values, parity should work the same but it doesn't and I'm too tired to figure why.

[npmccallum]

Why store the parity at all? Why not just brute force?

If tang returns no y parameter, there are only two options. Clang can just brute force this scenario and try both keys. The only requirement here is that clang uses the key with an algorithm that provides integrity protection.