ASN1 encoding routines errors when verifying ECDSA signature type with openssl

Question

I'm trying to verify a SHA256 ECDSA digital signature provided to us by an external party. They have verified their signing process in-house, but we've been unsuccessful in our attempts. We repeatedly get asn1 encoding routines errors during openssl verify, but I'm unable to see what's wrong with the signature or our process.

Here's out test setup... Public key (pubkey.pem):

-----BEGIN PUBLIC KEY-----
MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEOorVp0M8xien/r1/1Ln7TkSpzzcX
BL/MGRz66J1HSlEgBD5FwwpO1vo6jf/9azcrrrDdCi2NH9/cSDfv5D8gTA==
-----END PUBLIC KEY-----

The message being signed is the plaintext string:

HELLO

The digital signature (signature.sig):

JJhwReHev8cxOsNKCR5t/Ee3WU9c7tkf9RuGNamXdpXQu9OL8ZKnsrblCO7vEmOXGKGrk6NsgA5JZpQhXO3A1Q==

The general approach we've taken is:

# create message file
echo "HELLO" > hello.txt

#VERIFY
openssl dgst -sha256 -verify pubkey.pem -signature signature.sig hello.txt

and the response is

Error Verifying Data
4655195756:error:0DFFF09B:asn1 encoding routines:CRYPTO_internal:too long:/BuildRoot/Library/Caches/com.apple.xbs/Sources/libressl/libressl-22.260.1/libressl-2.6/crypto/asn1/asn1_lib.c:143:
4655195756:error:0DFFF066:asn1 encoding routines:CRYPTO_internal:bad object header:/BuildRoot/Library/Caches/com.apple.xbs/Sources/libressl/libressl-22.260.1/libressl-2.6/crypto/asn1/tasn_dec.c:1113:
4655195756:error:0DFFF03A:asn1 encoding routines:CRYPTO_internal:nested asn1 error:/BuildRoot/Library/Caches/com.apple.xbs/Sources/libressl/libressl-22.260.1/libressl-2.6/crypto/asn1/tasn_dec.c:306:Type=ECDSA_SIG

Alternatively, we've base64 encoding the signature base64 -D signature.sig > signature.bin but get the same error responses. I've tried to use openssl pkeyutl as well, but that results in asn1 encoding routines errors as well. Using ans1parse to parse the signature yields:

openssl asn1parse -in signature.bin
Error: offset too large

Clearly the digital signature is in a format I'm not handling, but I'm unable to see the problem.

Answer 1

What you have is a so called flat signature, consisting of the value of R and S - as the signature consists of the tuple (R, S). These numbers are encoded as two statically sized, unsigned, big endian integers with the same size as the key size.

However, OpenSSL expects two ASN.1/DER encoded INTEGER values in a SEQUENCE. These are two dynamically sized, signed, big endian values (in the same order). So you need to re-encode the signature for it to become valid.

It's relatively easy to convert between the two, but command line OpenSSL doesn't directly seem to support it. So I'd recommend a Perl, Python or C application to do so.

---

E.g. in Python 3 (minus the file handling, sorry):

from array import array
import base64

def encodeLength(vsize) -> bytearray:
    tlv = bytearray()
    if (vsize < 128):
        tlv.append(vsize)
    elif (vsize < 256):
        tlv.append(0x81)
        tlv.append(vsize)
    else:
        raise
    return tlv

def encodeInteger(i) -> bytearray:
    signedSize = (i.bit_length() + 8) // 8
    value = i.to_bytes(signedSize, byteorder='big', signed = True)

    tlv = bytearray()
    tlv.append(0x02)
    tlv += encodeLength(len(value))
    tlv += value
    return tlv

def encodeSequence(value) -> bytearray:
    tlv = bytearray()
    tlv.append(0x30)
    tlv += encodeLength(len(value))
    tlv += value
    return tlv

# test only

bin = base64.b64decode("JJhwReHev8cxOsNKCR5t/Ee3WU9c7tkf9RuGNamXdpXQu9OL8ZKnsrblCO7vEmOXGKGrk6NsgA5JZpQhXO3A1Q==")

# size of the curve (not always a multiple of 8!)
keysize = 256
csize = (keysize + 8 - 1) // 8
if (len(bin) != 2 * csize):
    raise
r = int.from_bytes(bin[0:csize], byteorder='big', signed = False)
s = int.from_bytes(bin[csize:csize * 2], byteorder='big', signed = False)

renc = encodeInteger(r)
senc = encodeInteger(s)
rsenc = encodeSequence(renc + senc)

print(base64.b64encode(rsenc))

Answer 2

Your signature.sig file appears to be base64 encoded. Decode it like this:

$ base64 -d signature.sig >signature.bin

Let's see what we have:

$ hexdump -C signature.bin
00000000  24 98 70 45 e1 de bf c7  31 3a c3 4a 09 1e 6d fc  |$.pE....1:.J..m.|
00000010  47 b7 59 4f 5c ee d9 1f  f5 1b 86 35 a9 97 76 95  |G.YO\......5..v.|
00000020  d0 bb d3 8b f1 92 a7 b2  b6 e5 08 ee ef 12 63 97  |..............c.|
00000030  18 a1 ab 93 a3 6c 80 0e  49 66 94 21 5c ed c0 d5  |.....l..If.!\...|
00000040

For comparison purposes I created a new ECDSA private key based on the same curve your public key is using (P-256):

$ openssl genpkey -algorithm EC -pkeyopt ec_paramgen_curve:P-256 -out key.pem

And then signed some data using it:

$ echo "HELLO" > hello.txt
$ openssl dgst -sha256 -sign key.pem -out hello.sig hello.txt
$ openssl asn1parse -in hello.sig -inform DER
    0:d=0  hl=2 l=  68 cons: SEQUENCE          
    2:d=1  hl=2 l=  32 prim: INTEGER           :2C1599C7765B047A2E98E2265CF6DB91232200559909D7F97CA3E859A39AC02C
   36:d=1  hl=2 l=  32 prim: INTEGER           :14E748DF692A8A7A2E41F984497782FF03F970DDB6591CCC68C71704B959A480

So you'll note that what we have here is two integers in a sequence where each integer is exactly 32 bytes long. This corresponds to the ECDSA_SIG ASN.1 definition:

ECDSA-Sig-Value ::= SEQUENCE { r INTEGER, s INTEGER }

A raw ECDSA signature is comprised of two integers "r" and "s". OpenSSL expects them to be wrapped up inside a DER encoded representation. However, as you've already discovered what you have for the signature is not valid DER. It is however exactly 64 bytes long - which suggests it is comprised of 2 32 byte integers concatenated together.

For the purposes of this exercise we can use a hex editor to convert the raw r and s values into a DER format. Lets looks at a hexdump of the hello.sig file I created earlier:

$ hexdump -C hello.sig
00000000  30 44 02 20 2c 15 99 c7  76 5b 04 7a 2e 98 e2 26  |0D. ,...v[.z...&|
00000010  5c f6 db 91 23 22 00 55  99 09 d7 f9 7c a3 e8 59  |\...#".U....|..Y|
00000020  a3 9a c0 2c 02 20 14 e7  48 df 69 2a 8a 7a 2e 41  |...,. ..H.i*.z.A|
00000030  f9 84 49 77 82 ff 03 f9  70 dd b6 59 1c cc 68 c7  |..Iw....p..Y..h.|
00000040  17 04 b9 59 a4 80                                 |...Y..|
00000046

We start off with 30 which tell us we have a sequence. The next byte is 44 which is the length of the remaining data. Next is 02 which is the tag for an integer, followed by 20 (which equals 32 in decimal), which is the length of the integer. The next 32 bytes is the integer (the r value). Then we have another 02 byte (integer) and 20 (length of 32) followed by the 32 bytes of the s value.

So if we add the bytes 30 44 02 20 to the front of your binary signature data, followed by the first 32 bytes of data, followed by 02 20 followed by the next 32 byes we should get what we want...

...except unfortunately its not quite that simple. There is a complication in your s value. You will note that it starts with the byte d0. This byte has its most significat bit set - which in DER encoding of an integer indicates that the integer value is negative. That's not what we want. To get around this we have to add an extra 00 byte onto the front of the s value.

Doing that changes the overall length so we now have to add these bytes to the begining 30 45 02 20 followed by the first 32 bytes from the signature data, followed by 02 21 00 followed by the next 32 bytes of the signature data. I did this in a hex editor and came up with the following:

$ hexdump -C signature2.bin
00000000  30 45 02 20 24 98 70 45  e1 de bf c7 31 3a c3 4a  |0E. $.pE....1:.J|
00000010  09 1e 6d fc 47 b7 59 4f  5c ee d9 1f f5 1b 86 35  |..m.G.YO\......5|
00000020  a9 97 76 95 02 21 00 d0  bb d3 8b f1 92 a7 b2 b6  |..v..!..........|
00000030  e5 08 ee ef 12 63 97 18  a1 ab 93 a3 6c 80 0e 49  |.....c......l..I|
00000040  66 94 21 5c ed c0 d5                              |f.!\...|
00000047

Lets check that this looks sane:

$ openssl asn1parse -in signature2.bin -inform DER
    0:d=0  hl=2 l=  69 cons: SEQUENCE          
    2:d=1  hl=2 l=  32 prim: INTEGER           :24987045E1DEBFC7313AC34A091E6DFC47B7594F5CEED91FF51B8635A9977695
   36:d=1  hl=2 l=  33 prim: INTEGER           :D0BBD38BF192A7B2B6E508EEEF12639718A1AB93A36C800E496694215CEDC0D5

Now lets try and verify the signature:

$ openssl dgst -sha256 -verify pubkey.pem -signature signature2.bin hello.txt
Verification Failure

Darn. So near and yet so far. But at least we got rid of the ASN.1 errors. So why isn't it working? On a hunch I did this:

echo -n "HELLO" > hello2.txt

The "-n" arg to echo suppresses newlines from the output. Perhaps the newline shouldn't be included in the data to be digested for the signature. So, trying that out:

$ openssl dgst -sha256 -verify pubkey.pem -signature signature2.bin hello2.txt
Verified OK

Success!