intel/cryptography-primitives

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

Closed this issue · 3 comments

yahyazadeh commented

I was testing PKCS#1 v1.5 signature verification as implemented in ipp-crypto 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
skirillo commented

Thanks for your analysis and report.
I think that the root of the issue lies in the inconsistency in the interpretation of "digestAlgorithm (dA) encoding" by different standards. And IPP's implementation (and, I think, many others) is just a confirmation of this fact.

Thus in IPP uses '\x30\x31\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x01\x05\x00\x04\x20' but in "I" above uses "\x30\x2f\x30\x0b\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x01\x04\x20". Both are correct and represent SHA256 but leads to reject valid signature if "sign" and "verify" are using different (with and without explicit NULL parameter) dA encoding.

Let me note

  • that PKCS #1v1.5 signature validation requires direct comparison EM and EM'=EMSA-PKCS1-V1_5-ENCODE(msg) but not parsing of dA encoding
  • RFC8017 (and other std) are published hardcoded dA value
  • "Exception" (RFC8017 p 64) stated that "When formatting the DigestInfoValue in EMSA-PKCS1-v1_5 the parameters field associated with ... id-sha256 ... shall have a value of type NULL. This is to maintain compatibility with existing implementations and with the numeric information values already published for EMSA-PKCS1-v1_5"

So in any meaning the "Exception" dictates the 'default' (== with explicit MULL parameter) kind of dA encoding.

I think if developers add clear values for dA encoding to the IPP documentation, the situation will look more obvious.

Do you agree?
Or do you have other proposal to improve implementation? Which ones?

mdwood-intel commented

The implementation should adhere to FIPS 186-4 as well as the RFCs. FIPS 186-4 specifically references PKCS #1v2.1, which is RFC 3447. There are no changes in the RSASSA-PKCS1-v1_5 description between PKCS #1v2.1 and v2.2 (RFC 8017).

PKCS #1 v2.1 section 8.2.2 gives the answer to this issue. It states:

Note. Another way to implement the signature verification operation
is to apply a "decoding" operation (not specified in this document)
to the encoded message to recover the underlying hash value, and then
to compare it to a newly computed hash value. This has the advantage
that it requires less intermediate storage (two hash values rather
than two encoded messages), but the disadvantage that it requires
additional code.

Using the decoding method has pitfalls and as a result FIPS 186-4 includes explicit requirements for compliant implementations that check the hashes via the alternate "decoding" method.

To be maximally compatible, the implementation should always generate signatures with the encoding currently used by IPP ('\x30\x31\x30\x0d\x06...') but accept either encoding for verification. Knowing there are only two valid encodings, generating both valid EM candidates and byte comparing the results with the RSA decryption output would be equivalent to supporting a "decoding" implementation without the pitfalls of an actual "decoding" implementation. Signatures without the explicit NULL parameter are probably generated by older crypto library implementations or those referencing obsolete definitions of RSASSA-PKCS1-v1_5 (PKCS # 1<=v2.0; v2.1 was published in 2003).

There is some discussion of the variance in NULL encoding in https://mta.openssl.org/pipermail/openssl-dev/2015-January/000441.html that explains why PKCS #1v2.1+ explicitly mandated inclusion of the NULL parameter in AlgorithmIdentifier:

The two alternatives arise from the loss of the OPTIONAL associated with the algorithm identifier parameters when the 1988 syntax for AlgorithmIdentifier was translated into the 1997 syntax. Later, the OPTIONAL was recovered via a defect report, but by then many people thought that algorithm parameters were mandatory. Because of this history, some implementations encode parameters as a NULL element while others omit them entirely.

opervush commented

I'm closing the issue due to no response. Please reopen if you have any objections