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

[yahyazadeh]

I was testing PKCS#1 v1.5 signature verification as implemented in python-pkcs1 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

[bdauvergne]

The problem is that the RFC does not define a container format for the input structure + signature, how do we know which way of encoding the input structure was used ? The API only accept naked signature. It seems wrong that the input structure is not deterministic.

[bdauvergne]

You are wrong; https://security.stackexchange.com/questions/110330/encoding-of-optional-null-in-der :)

[bdauvergne]

Not completely if we believe OpenSSL. I still don't understand how to validate naked signatures.

[yahyazadeh]

Hi,

RFC does not define a container format for the input structure + signature

Actually it does. DigestAlgorithm has AlgorithmIdentifier type which defines a container (a TLV with sequence type; 0x30 as its identifier octet) for two nested TLVs: hash function OID and NULL parameter. Now to support omitted NULL parameter (i.e., implicit parameter) as well, the container only contains hash function OID.

Since you're doing what's known as construction-based (i.e., encoding-based) signature verification, what needs to happen is preparing two versions of the signatures (based on the given hash, and hash function) and validate it if the given signature value matches any of these two.

More explicitly, you need to add the prefixes for implicit NULL parameter cases to DIGEST_INFO_PREFIXES here. Eg, for SHA256, implicit NULL parameter prefix would be:

b'\x30\x2f\x30\x0b\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x01\x04\x20'

And comparing to the explicit NULL parameter version, it does not have \x05\x00 anymore while the length octets of parent TLV and grandparent TLV are adjusted accordingly.

Let me know if you have any question.

--Daniel

[bdauvergne]

I accept pull requests if you know the solution :)