Card should check the presented public key to ensure that it is on the proper curve prior to ECDH

[dmercer-google]

There is an attack where using a carefully crafted public key not on the curve can compromise a private key during ECDH. It is unclear if the ECDH implementation in the JCRE does this check or if it is done in all implementations.

[dmercer-google]

Further to the exploit I talk about this is from @sophieschmieg:

"The attack is usually called a point-not-on-curve attack (very good name). The basic idea behind it is that the elliptic curve addition formulas do not depend on the b in Y^2=X^3+aX+b, and Alice computes the shared secret as a*B, where B is potentially controlled by the attacker and the only thing that defines the curve you are on. By supplying a B that lies on a curve with small subgroups, you can give Alice a point of low order and then check which key she tries to uses by going through all points in the small subgroup. That gives you up to the order of the small subgroup. Repeat for different choices of curves/different subgroups until you got enough to reconstruct all of Alice's secret."

[makinako]

Having looked a bit more into it, public key validation for ECDH is described in SP.800-56A in section 5.6.2.3 as a mandatory (shall) procedure for ECDH and this in turn is required by NIST SP800-78 as the process for PIV. As this blog points out, when and how thoroughly implementations must validate public key inputs gets confusing.

Since the Javacard specification makes no mention of this at all, it is up to manufacturers to adhere to NIST requirements. I've asked NXP for advice on this and it appears their SmartMX2 at the least (and presumably MX3) check the validity of supplied public keys for ECDH (and they have tested against the invalid curves supplied by @dmercer-google).

The CRoCS/Muni tool ECTester as a test suite for this, so perhaps all we can do is provide guidance to understand the problem and advise to run tests on your preferred card before deployment. A unit test script to try the documented invalid curves on OpenFIPS201 would make it smoother for users of this project to avoid setting up a whole test suite.

[dengert]

Are you saying a PIV card or PIV applet is required to verify the EC pubkey used as input to ECDH?

I would read "5.6.2.3 Public Key Validation Routines" (see below) describes a set of 4 routines. These are the routines to be used if "public-key validity is required (or desired)"

This might apply: "5.6.2.2 Assurances Required by a Public Key Recipient" "Prior to or during a key-establishment transaction, the recipient of a public key shall obtain assurance of public-key validity and/or private-key possession as required below".

But note that "recipient of a public key" could apply to application, middleware, PIV card or PIV applet. In some of these tests, the assurance can come via trust in CA to have signed the certificate which contains the public key.
But PIV card or applet do not know if the key is static or ephemeral, and middleware such as PKCS#11 does not know if calling application has verified trusted certificate chain, but assumes application would have done that, as PKCS#11 only requires public key.

"Table 4: Assurances required by a public-key recipient" and its footnotes are interesting.

If you have some test public keys that are not on the 256 or 384 curves or invalid, I could run ECDH tests on some of the PIV cards I have to see if they catch that the public key is invalid. You could also run these thru OpenSSL to see if it catches them. If it can, I could add OpenSSL code to OpenSC to validate before sending data to the card.

These also apply.
5.6.3.2 Specific Requirements on Static Key Pairs
5.6.3.3 Specific Requirements on Ephemeral Key Pairs
could refer to middleware or PIV applet on card. The card does not know if public key from peer is Static or Ephemeral so
5.6.2.3.3 ECC Full Public-Key Validation Routine would be the only one a card or applet could do.

---

5.6.2.3.1 FFC Full Public-Key Validation Routine "This routine shall be used when assurance of full public-key validity is required (or desired) for a static or ephemeral FFC public key."

5.6.2.3.2 FFC Partial Public-Key Validation Routine "This routine shall only be used with ephemeral FFC public keys generated using the approved safe-prime groups when assurance of the partial validity of such keys is to be
obtained as specified in Section 5.6.2.2.2"

5.6.2.3.3 ECC Full Public-Key Validation Routine "This routine shall be used when assurance of full public-key validity is required (or desired) for a static or ephemeral ECC public key"

5.6.2.3.4 ECC Partial Public-Key Validation Routine "This routine shall only be used when assurance of partial public-key validity is acceptable for an ephemeral ECC public key."

[dengert]

I modified a pub key note FF FF FF FF:

 asn1parse -i -in /tmp/derive.3740.other.pubkey.der -inform DER -dump
    0:d=0  hl=2 l= 118 cons: SEQUENCE          
    2:d=1  hl=2 l=  16 cons:  SEQUENCE          
    4:d=2  hl=2 l=   7 prim:   OBJECT            :id-ecPublicKey
   13:d=2  hl=2 l=   5 prim:   OBJECT            :secp384r1
   20:d=1  hl=2 l=  98 prim:  BIT STRING        
      0000 - 00 04 ca 44 1b 37 f9 7e-1d 3d 88 e1 46 42 1f b1   ...D.7.~.=..FB..
      0010 - 3f b9 c4 c4 f0 23 e6 9e-ba 6e 94 6d c3 d3 85 b6   ?....#...n.m....
      0020 - ce 33 81 59 0b b9 49 4f-14 c4 75 ed 33 0c 1b 9d   .3.Y..IO..u.3...
      0030 - c3 d3 38 b5 63 00 00 d1-c0 6d 80 75 ea d4 5b d9   ..8.c....m.u..[.
      0040 - 78 ba ae 14 71 49 c4 ed-37 bf db a6 99 23 fb 9c   x...qI..7....#..
      0050 - 33 83 ff ff ff ff fe eb-21 cd 88 99 a1 a2 df 4f   3.......!......O
      0060 - c6 52                                    .R

As a test using pkcs11-tool -l --derive -m ECDH1-COFACTOR-DERIVE -d 03 -i /tmp/derive.3740.other.pubkey.der
I get error: Cannot read EC key from /tmp/derive.3740.other.pubkey.der
pkcs11-tool uses OpenSSL to read the pubkey.

Seeing what OpenSSL is doing:

openssl ec -pubin -text -in /tmp/derive.3740.other.pubkey.der -inform DER
read EC key
unable to load Key
140689675908416:error:1012606B:elliptic curve routines:EC_POINT_set_affine_coordinates:point is not on curve:../crypto/ec/ec_lib.c:812:
140689675908416:error:10098010:elliptic curve routines:o2i_ECPublicKey:EC lib:../crypto/ec/ec_asn1.c:1175:
140689675908416:error:100D708E:elliptic curve routines:eckey_pub_decode:decode error:../crypto/ec/ec_ameth.c:157:
140689675908416:error:0B09407D:x509 certificate routines:x509_pubkey_decode:public key decode error:../crypto/x509/x_pubkey.c:125:

So OpenSSL does check point is not on curve. This should be easy to add to OpenSC, but not today.

[makinako]

Are you saying a PIV card or PIV applet is required to verify the EC pubkey used as input to ECDH?

I think there's a clear case for this to be checked at the card edge. Having it checked by middleware/apps such as OpenSSL/OpenSC makes sense, but this is really about protection of the private key which is in the custody of the card/applet.
Since PIV uses a static key for ECDH, this makes it a critical problem. An attacker will not restrict themselves to using a tool that checks the public key, they would just directly trial the applet.

I'll produce test vector APDU's for this and then it may be worth having a table of cards and their susceptibility to the attack.

[dengert]

Here is a script piv.test.ecdh.pub.valiation.sh.txt with good and bad 256 and 384 APDUs for PIV. The pubkeys are from NIST demo cards 4 and 5. The bad 256 key has 4 bytes set to FF, and the bad 384 has 4 bytes set to 00.

The demo cards are from 2006, and are both Oberthur ID-One PIV cards. And running (see below) the script twice with good works, and bad fails with `6A 80' on these two old cards, and a newer Idemia ID-One PIV 2.4.1

So at least these approved NIST PIV cards check for the peer pubkey is on the curve. I have not tried this on other "PIV-like" cards or applets.

SIZE:384 BAD:GOOD PIN:123456
Using reader with a card: SCM Microsystems Inc. SCR 355 [CCID Interface] 00 00
Sending: 00 A4 04 00 09 A0 00 00 03 08 00 00 10 00 00 
Received (SW1=0x90, SW2=0x00):
61 39 4F 0B A0 00 00 03 08 00 00 10 00 01 00 79 a9O............y
07 4F 05 A0 00 00 03 08 50 0E 49 44 2D 4F 6E 65 .O......P.ID-One
20 50 49 56 20 42 49 4F 5F 50 10 77 77 77 2E 6F  PIV BIO_P.www.o
62 65 72 74 68 75 72 2E 63 6F 6D 7F 66 08 02 02 berthur.com.f...
80 00 02 02 80 00                               ......
Sending: 00 20 00 80 08 31 32 33 34 35 36 FF FF 
Received (SW1=0x90, SW2=0x00)
Sending: 00 20 00 80 
Received (SW1=0x90, SW2=0x00)
Sending: 00 87 14 9D 67 7C 65 82 00 85 61 04 71 11 01 1A 31 3E C9 C7 2A E2 38 6A 35 1C AD FC 61 18 C9 D9 38 B3 47 D4 26 61 A4 52 E7 ED B3 B4 B7 08 62 10 2E B1 9F CB 69 49 59 70 69 0C 89 24 BA 55 AB 17 A1 74 75 95 C5 6E 16 2C 48 5C 81 04 75 EA 14 EF 27 95 6F A1 15 AF DD C7 09 C3 FB 2F A6 3D 39 CF 65 7D 9D 3D E7 EA 1D 7B AD 89 16 88 00 
Received (SW1=0x90, SW2=0x00):
7C 32 82 30 B5 A6 2D 28 6A 0C D7 5B 9D 1A A9 D6 |2.0..-(j..[....
C3 7C 0A 57 97 F3 7A 15 DF 3F F6 52 85 8F 3C 41 .|.W..z..?.R..<A
32 D2 29 AC 70 FE 64 08 65 0B 08 41 32 42 52 D4 2.).p.d.e..A2BR.
7C E4 61 0B                                     |.a.

piv.test.ecdh.pub.valiation.sh -p 123456 bad 384
SIZE:384 BAD:BAD PIN:123456
Using reader with a card: SCM Microsystems Inc. SCR 355 [CCID Interface] 00 00
Sending: 00 A4 04 00 09 A0 00 00 03 08 00 00 10 00 00 
Received (SW1=0x90, SW2=0x00):
61 39 4F 0B A0 00 00 03 08 00 00 10 00 01 00 79 a9O............y
07 4F 05 A0 00 00 03 08 50 0E 49 44 2D 4F 6E 65 .O......P.ID-One
20 50 49 56 20 42 49 4F 5F 50 10 77 77 77 2E 6F  PIV BIO_P.www.o
62 65 72 74 68 75 72 2E 63 6F 6D 7F 66 08 02 02 berthur.com.f...
80 00 02 02 80 00                               ......
Sending: 00 20 00 80 08 31 32 33 34 35 36 FF FF 
Received (SW1=0x90, SW2=0x00)
Sending: 00 20 00 80 
Received (SW1=0x90, SW2=0x00)
Sending: 00 87 14 9D 67 7C 65 82 00 85 61 04 71 11 01 1A 31 3E C9 C7 2A E2 38 6A 35 1C AD FC 61 18 C9 D9 38 B3 47 D4 26 61 A4 52 E7 ED B3 B4 B7 08 62 10 2E B1 9F CB 69 49 59 70 69 0C 89 24 BA 55 AB 17 A1 74 75 95 C5 6E 16 2C 48 5C 81 04 75 EA 14 EF 27 95 6F A1 15 AF DD C7 09 00 00 00 00 3D 39 CF 65 7D 9D 3D E7 EA 1D 7B AD 89 16 88 00 
Received (SW1=0x6A, SW2=0x80)

[dmercer-google]

I spoke directly with NIST about this and they agree that the attack is possible but that Federal Government 140-3 certified cards are not vulnerable because the cryptographic modules they use must specifically defend against this attack. That said: they agree that this attack is feasible in cases where some entity were to implement a PIV solution on some random card or HCE platform which did not defend against the attack. NIST has agreed that the auth mechanisms allowed on keys 9A and 9E are ambiguous in 800 73-4 and in the conformance tests and they will provide clearer guidance in future revisions.

Personally I don't like granting the default ability for keys to perform arbitrary cryptographic operations. Keys should, where possible, be used for one thing only and only using the intended mechanism. ECDH was never intended to be used for authentication and the default behaviour of keys 9A and 9E whose function in PIV is very specifically defined should not be to allow anything other than digital signatures. I'm fine with allowing users of OpenFIPS201 to make a conscious decision to allow ECDH but said should not be allowed by default. This is akin to how PIN Over Wireless is turned off by default but users can switch it on with a config variable.

BTW: I have encountered one PACS which uses ECDH on keys 9A and 9E for authentication. They have fixed that in their latest release.

[makinako]

Revisiting this, a few points:

• FIPS 140-3 specifically mandates this as @dmercer-google already mentioned. That being said, there isn't a single 140-3 accredited module on the market yet so we have to consider what's already out there.
• At least a few cards already build this in, so it seems like the appropriate place for this is the JCRE/OS, not the applet. I'll try and build a profile of how many cards don't.
• I think the best approach at this stage is to keep it as a security note with an APDU script that you can use on a vanilla install of the applet to pre-perso, inject and send a series of invalid curves to ensure they fail.
• One day we might build an implementation of the check and have it as an option, to cover cards that don't if it appears to be a common thing.
• Finally, I take the point about mixing ECSDA/ECDH and this will be covered by issue Optional means to limit the crypto operations which can be performed on a key #29.