DSA vs. wycheproof

[karel-m]

Again https://github.com/google/wycheproof/tree/master/testvectors

From dsa_test.json we fail the following tests (grep the json for tcId value):

#   Failed test 'type: DSAVer/SHA224, tcId: 12, comment: Legacy:ASN encoding of s misses leading 0, result: acceptable'
#   Failed test 'type: DSAVer/SHA224, tcId: 126, comment: Modified r or s, e.g. by adding or subtracting the order of the group, result: invalid'
#   Failed test 'type: DSAVer/SHA224, tcId: 128, comment: Modified r or s, e.g. by adding or subtracting the order of the group, result: invalid'
#   Failed test 'type: DSAVer/SHA224, tcId: 14, comment: BER:long form encoding of length, result: acceptable'
#   Failed test 'type: DSAVer/SHA224, tcId: 17, comment: BER:length contains leading 0, result: acceptable'
#   Failed test 'type: DSAVer/SHA224, tcId: 19, comment: BER:indefinite length, result: acceptable'
#   Failed test 'type: DSAVer/SHA224, tcId: 20, comment: BER:prepending 0's to integer, result: acceptable'
#   Failed test 'type: DSAVer/SHA224, tcId: 53, comment: appending 0's to sequence, result: invalid'
#   Failed test 'type: DSAVer/SHA224, tcId: 55, comment: appending unused 0's, result: invalid'
#   Failed test 'type: DSAVer/SHA224, tcId: 57, comment: appending null value, result: invalid'
#   Failed test 'type: DSAVer/SHA224, tcId: 97, comment: append empty sequence, result: invalid'

On top of that the following test vector seems to loop for ever:

{
  "comment" : "Signatures with special case values for r and s.",
  "message" : "48656c6c6f",
  "result" : "invalid",
  "sig" : "3022020101021dff450969597a870820211805983688387a10cd4dcc451a7f3f432a96a3",
  "tcId" : 139
}

I'll investigate more.

[karel-m]

In total: 12 tests is failing, 2 hangs (out of 206)

[karel-m]

2 hanging tests fixed by 0fada4d

10 fails remaining (all seem to be ASN.1 related)

1/ the following we reject but they should be accepted
#   Failed test 'type: DSAVer/SHA224, tcId: 12, comment: Legacy:ASN encoding of s misses leading 0, result: acceptable'
#   Failed test 'type: DSAVer/SHA224, tcId: 14, comment: BER:long form encoding of length, result: acceptable'
#   Failed test 'type: DSAVer/SHA224, tcId: 17, comment: BER:length contains leading 0, result: acceptable'
#   Failed test 'type: DSAVer/SHA224, tcId: 19, comment: BER:indefinite length, result: acceptable'
#   Failed test 'type: DSAVer/SHA224, tcId: 20, comment: BER:prepending 0's to integer, result: acceptable'

2/ the following we accept but they should be rejected (BIGGER ISSUE!)
#   Failed test 'type: DSAVer/SHA224, tcId: 53, comment: appending 0's to sequence, result: invalid'
#   Failed test 'type: DSAVer/SHA224, tcId: 55, comment: appending unused 0's, result: invalid'
#   Failed test 'type: DSAVer/SHA224, tcId: 57, comment: appending null value, result: invalid'
#   Failed test 'type: DSAVer/SHA224, tcId: 97, comment: append empty sequence, result: invalid'
#   Failed test 'type: DSAVer/SHA224, tcId: 100, comment: repeat element in sequence, result: invalid'

[karel-m]

After the latest RSA related fix here are remaining DSA failures:

# Failed test 'type=DSAVer/SHA224 tcId=12 comment='Legacy:ASN encoding of s misses leading 0' expected-result=acceptable'
# Failed test 'type=DSAVer/SHA224 tcId=14 comment='BER:long form encoding of length' expected-result=acceptable'
# Failed test 'type=DSAVer/SHA224 tcId=15 comment='BER:long form encoding of length' expected-result=acceptable'
# Failed test 'type=DSAVer/SHA224 tcId=17 comment='BER:length contains leading 0' expected-result=acceptable'
# Failed test 'type=DSAVer/SHA224 tcId=18 comment='BER:length contains leading 0' expected-result=acceptable'
# Failed test 'type=DSAVer/SHA224 tcId=19 comment='BER:indefinite length' expected-result=acceptable'
# Failed test 'type=DSAVer/SHA224 tcId=20 comment='BER:prepending 0's to integer' expected-result=acceptable'
# Failed test 'type=DSAVer/SHA224 tcId=21 comment='BER:prepending 0's to integer' expected-result=acceptable'
# Failed test 'type=DSAVer/SHA224 tcId=55 comment='appending unused 0's' expected-result=invalid'

Just the last one is important (we accept something that we should reject).

[karel-m]

ASN.1 sequences that we do not handle correctly:

ASN.1=303c021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd021cade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236
#FAIL: type=DSAVer/SHA224 tcId=12 comment='Legacy:ASN encoding of s misses leading 0' expected-result=acceptable

ASN.1=303e02811c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236
#FAIL: type=DSAVer/SHA224 tcId=14 comment='BER:long form encoding of length' expected-result=acceptable

ASN.1=303e021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd02811d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236
#FAIL: type=DSAVer/SHA224 tcId=15 comment='BER:long form encoding of length' expected-result=acceptable

ASN.1=303f0282001c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236
#FAIL: type=DSAVer/SHA224 tcId=17 comment='BER:length contains leading 0' expected-result=acceptable

ASN.1=303f021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd0282001d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236
#FAIL: type=DSAVer/SHA224 tcId=18 comment='BER:length contains leading 0' expected-result=acceptable

ASN.1=3080021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862360000
#FAIL: type=DSAVer/SHA224 tcId=19 comment='BER:indefinite length' expected-result=acceptable

ASN.1=303f021e00001e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236
#FAIL: type=DSAVer/SHA224 tcId=20 comment='BER:prepending 0's to integer' expected-result=acceptable

ASN.1=303f021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd021f000000ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236
#FAIL: type=DSAVer/SHA224 tcId=21 comment='BER:prepending 0's to integer' expected-result=acceptable

ASN.1=303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862360000
#FAIL: type=DSAVer/SHA224 tcId=55 comment='appending unused 0's' expected-result=invalid

[karel-m]

According to my analysis we can divide the failures above into the following 3 groups:

1/ BER related - tcId 14, 15, 17, 18, 19, 20, 21 (these we can ignore)

Our current implementation is not able to accept these unusual forms.

The thing is that during sequence decoding we do:

1. first der_decode_integer(..) to decode the data
2. next der_length_integer(..) to get the length of data read/decoded in previous step (which is basically implemented as re-enconding them again).

This only works when: original data > decode > decoded data > encode > original data. Which is not the case of BER where you can legally encode the same integer in many different ways.

021c 1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd
021d 001e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd
021e 00001e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd
02811c 1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd
0282001c 1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd

2/ Legacy:ASN encoding of s misses leading 0 - tcId=12 (we can ignore)

The following ASN.1 sequence is IMO invalid (I have no idea why it is marked as "accepted").

303c (SEQ len=60)
  021c 1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd (INT r, len=28)
  021c ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236 (INT s, len=28)

If I understand correctly the s value is in this case a negative integer, which means that it cannot be a valid DSA signature. But I may be wrong.

3/ appending unused 0's tcId=55 (this one we need to fix)

The failing test case tries to decode this invalid sequence:

303d021c1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd021d00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe87862360000

Which decodes to:

303d (SEQ len=61)
  021c 1e41b479ad576905b960fe14eadb91b0ccf34843dab916173bb8c9cd (INT r, len=28)
  021d 00ade65988d237d30f9ef41dd424a4e1c8f16967cf3365813fe8786236 (INT s, len=29)
0000 (!!! THESE 2 extra bytes are the trouble !!!)

Our current implementation simply ignores any extra data appended after the ASN.1 encoded sequence.

The fix will be a bit complicated as we intentionally call der_decode_sequence_ex on a longer data than just the actual sequence at several places.

[karel-m]

Closing this one. Further comments should go to #278 or #280 that are from my point of view ready for merge.