RSA PKCS#1 v1.5 signature scheme verification incompatibility issue

I was testing PKCS#1 v1.5 signature verification as implemented in RSA package and noticed it rejects valid signature whose encoded message uses an implicit NULL parameter for hash algorithm (where digestAlgorithm ANS.1 der encoded does not have NULL parameter TLV; that is, 0x0500 is absent). According to RFC4055, pg.5 and RFC8017, pg. 64, for SHA-1, and the SHA-2 family, the algorithm parameter has to be NULL and both explicit NULL parameter and implicit NULL parameter (ie, absent NULL parameter) are considered to be legal and equivalent. However, this implementation does not accept a valid PKCS input with implicit NULL parameter.

Reference notation and concrete values

N: public modulus
|N|: length of public modulus
d: private exponent
e: public exponent
H: hash function
m: message
I: to-be-singed RSA PKCS#1 v1.5 signature scheme input structure
S: signature value obtained by I^d mod N

N = 0xE932AC92252F585B3A80A4DD76A897C8B7652952FE788F6EC8DD640587A1EE5647670A8AD4C2BE0F9FA6E49C605ADF77B5174230AF7BD50E5D6D6D6D28CCF0A886A514CC72E51D209CC772A52EF419F6A953F3135929588EBE9B351FCA61CED78F346FE00DBB6306E5C2A4C6DFC3779AF85AB417371CF34D8387B9B30AE46D7A5FF5A655B8D8455F1B94AE736989D60A6F2FD5CADBFFBD504C5A756A2E6BB5CECC13BCA7503F6DF8B52ACE5C410997E98809DB4DC30D943DE4E812A47553DCE54844A78E36401D13F77DC650619FED88D8B3926E3D8E319C80C744779AC5D6ABE252896950917476ECE5E8FC27D5F053D6018D91B502C4787558A002B9283DA7

|N| = 256 bytes

d = 0x009b771db6c374e59227006de8f9c5ba85cf98c63754505f9f30939803afc1498eda44b1b1e32c7eb51519edbd9591ea4fce0f8175ca528e09939e48f37088a07059c36332f74368c06884f718c9f8114f1b8d4cb790c63b09d46778bfdc41348fb4cd9feab3d24204992c6dd9ea824fbca591cd64cf68a233ad0526775c9848fafa31528177e1f8df9181a8b945081106fd58bd3d73799b229575c4f3b29101a03ee1f05472b3615784d9244ce0ed639c77e8e212ab52abddf4a928224b6b6f74b7114786dd6071bd9113d7870c6b52c0bc8b9c102cfe321dac357e030ed6c580040ca41c13d6b4967811807ef2a225983ea9f88d67faa42620f42a4f5bdbe03b

e = 3

H = SHA-256 (OID = 0x608648016503040201)

m = "hello world!"

I = 0x0001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00302f300b060960864801650304020104207509e5bda0c762d2bac7f90d758b5b2263fa01ccbc542ab5e3df163be08e6ca9

S = 0xa0073057133ff3758e7e111b4d7441f1d8cbe4b2dd5ee4316a14264290dee5ed7f175716639bd9bb43a14e4f9fcb9e84dedd35e2205caac04828b2c053f68176d971ea88534dd2eeec903043c3469fc69c206b2a8694fd262488441ed8852280c3d4994e9d42bd1d575c7024095f1a20665925c2175e089c0d731471f6cc145404edf5559fd2276e45e448086f71c78d0cc6628fad394a34e51e8c10bc39bfe09ed2f5f742cc68bee899d0a41e4c75b7b80afd1c321d89ccd9fe8197c44624d91cc935dfa48de3c201099b5b417be748aef29248527e8bbb173cab76b48478d4177b338fe1f1244e64d7d23f07add560d5ad50b68d6649a49d7bc3db686daaa7

OK, so I have mediocre news and bad news.

The mediocre news is that you can make this work with the library as-is. What you have to do is provide a custom version of the hash function declaration, as follows:

let customHash = HashInfo {
       algorithmIdent = BS.pack [
         0x30,0x2f,0x30,0x0b,0x06,0x09,0x60,0x86,
         0x48,0x01,0x65,0x03,0x04,0x02,0x01,0x04,
         0x20
       ],
       hashFunction = bytestringDigest . sha256
     }
in rsassa_pkcs1_v1_5_verify customHash pub m s_bytes)

I've created a test case to show this off inside the repository, for reference.

The bad news is that this is likely the best I'm going to do for you. The underlying problem, as noted in the commit message that adds this example, is that this library doesn't actually parse any ASN.1. That is, in fact, the reason for the HashInfo structure that's passed into all these functions: it carries along a hand-encoded version of the hash information required, and then just a direct ByteString to ByteString comparison of it during verification. So basically, it's not that we're messing up handling an allowed case in the cited RFCs, it's that we're messing up by not properly implementing the ASN.1 encodings in the RFCs at all. :laughing:

Processing the ASN.1, would likely require a rethinking of this entire module's API. I admit, I'm unlikely to bite that bullet. If you'd like to, though, I'd be happy to chat about approaches / look at patches.

GaloisInc / RSA

RSA PKCS#1 v1.5 signature scheme verification incompatibility issue #19