Navigation Menu

Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

crypto/rsa: PKCS#1 v1.5 signature scheme verification incompatibility issue #45322

Closed
yahyazadeh opened this issue Apr 1, 2021 · 4 comments
Closed

crypto/rsa: PKCS#1 v1.5 signature scheme verification incompatibility issue #45322

yahyazadeh opened this issue Apr 1, 2021 · 4 comments
Labels
FrozenDueToAge

Comments

@yahyazadeh
Copy link

I was testing PKCS#1 v1.5 signature verification as implemented in Go crypto 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
@FiloSottile
Copy link
Contributor

As far as I can tell, the NULL must be explicit in PKCS#1 v1.5 signatures, and especially in finicky primitives like this we prefer to keep complexity at a minimum. From RFC 8017:

   Exception: When formatting the DigestInfoValue in EMSA-PKCS1-v1_5
   (see Section 9.2), the parameters field associated with id-sha1,
   id-sha224, id-sha256, id-sha384, id-sha512, id-sha512/224, and
   id-sha512/256 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, which are
   also reflected in IEEE 1363a [IEEE1363A].

@FiloSottile FiloSottile changed the title RSA PKCS#1 v1.5 signature scheme verification incompatibility issue crypto/rsa: PKCS#1 v1.5 signature scheme verification incompatibility issue Apr 1, 2021
@yahyazadeh
Copy link
Author

The cited paragraph specifies EMSA-PKCS1-v1_5 to include the explicit NULL parameter to maintain compatibility generally in the process of generating signature. However, two paragraphs right above this mentions:

The parameters field associated with id-sha1, id-sha224, id-sha256,
id-sha384, id-sha512, id-sha512/224, and id-sha512/256 should
generally be omitted, but if present, it shall have a value of type
NULL.

which recommends accepting both versions in the signature verification. I believe since EMSA-PKCS1-v1_5 is being used for construction-based signature verification instead of parsing-based approach, it does not imply EMSA-PKCS1-v1_5 cannot encode message with implicit NULL. Therefore, the construction-based approaches build both versions of signature values and validate the given signature if it matches with either of them.

@FiloSottile
Copy link
Contributor

I think the text is fairly clear that the "Exception" paragraph overrides the previous one for EMSA-PKCS1-v1_5, and both singing and construction-based verification (the only safe option) use EMSA-PKCS1-v1_5.

Is this causing active compatibility issues? With what software/ecosystem?

Even if the spec allowed both, we'd probably want to stick to the simplest implementation for safety reasons unless there is meaningful breakage.

@yahyazadeh
Copy link
Author

Is this causing active compatibility issues? With what software/ecosystem?

Your PKCS1v1.5 implementation was one of our many test subjects we've experimented for a compliancy check research project.

@golang golang locked and limited conversation to collaborators Apr 1, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@FiloSottile @gopherbot @yahyazadeh