Tuesday 11 January 2011

BouncyCastle, ECC and JavaCard

Using BouncyCastle to create ECDSA-SHA1 signatures which should be verifiable on Java Card, I ran into a problem which - I would expect - is commonly encountered by developers but not documented. We don't want to use a different Java cryptoprovider or different COS, so a dirty workaround has to be found.

I would be happy to know if this helps someone or if I missed something obvious.

Background

The coefficient size for a curve is a function of bitlength:
coeffsize = (bitlen/8)+((bitlen%8>0)?1:0).
Further, an F_2m curve has bitlength non-divisible by 8, while a F_p curve has a bitlength divisible by 8 (exception is curve SECP521K1).

According IEEE X9.62, ECDSA-SHA1 signatures consist of a type byte, a header+data length byte, then 2 * (header length, coordinate length, coordinate data).
From the ECDSA algorithm and the NIST recommended curve parameters, the coordinate length is supposed to be equal to the coefficient size.

Problem

The BouncyCastle ECDSA implementation generates signatures over F_2m type curves which sometimes have coordinate length = coefficient size - 1, and F_p signatures which sometimes (usually for larger bitsizes) have coordinate length = coefficient size + 1.

For F_p this is clearly due to one byte being prefixed to the coordinate data when the first bit of the first byte is set, for indicating signedness (0x00 if positive, 0x01 if negative). See http://stackoverflow.com/questions/1571999/java-why-does-a-512-bit-rsa-keypairgenerator-return-65-byte-keys

For F_2m the cause is unclear but seems related.

Solution

Let the expected signature size be 2 + 2*(2 + 1 + coefficient size) for F_p, and 2 + 2*(2 + coefficient size) for F_2m.

Alternatively, we could use 2 + 2*(2+ coefficient size) for both F_2m and F_p, and let the coefficient size for F_p be increased by 1; then the original equation for the coefficient size for F_2m and F_p becomes coeffsize = (bitlen/8)+1 and the curve constant parameters (P/E, A, B, N) must be prefixed with one null byte.

Regardless of the choice of solution, Java Card requires fixed lengths for the signatures, so the signature co-ordinate data must be pre-padded with 0x00 to the correct coordinate length and the signature coordinate and header length must be updated.

Signature examples

  1. SECT163K1 (F_2m):
    1. Correct:
      302e0215035e292715c109be43be9caec807bc66e66b2a312d0215038755036fb45b0ae8c512f1ae39257f1eb842b3fb
        ^^  ^^                                            ^^
    2. Needs padding:
      302d021501931b6052ba344228eb9ac8c58206d285fc4828b602141bdbd2ba860b3326e8487124acc074f41e0d7767
        ^^                                                ^^
      Padded and lengths updated:
      302e021501931b6052ba344228eb9ac8c58206d285fc4828b60215001bdbd2ba860b3326e8487124acc074f41e0d7767
        ^^                                                ^^^^
    Coefficient size: 21
    Coordinate size: 21
    Required signature size (Java Card): 48
  2. SECP192K1 (F_p):
    1. Padded and lengths updated:
      3036021900a63c2597958e72bfcf203a26fe174e115ba0ad409c445b3d02190040ef96986e491e0aed7d03ba736cddf6fcafe0d42661563c
        ^^  ^^^^                                                  ^^^^
    Coefficient size: 24
    Coordinate size: 25
    Required signature size (Java Card): 56

Monday 3 January 2011

OpenPCD

The OpenPCD Passive RFID Project offers great accessability to RFID hacking tools for both professionals and novices. Keep an eye on this one.