Identifier Octet's Leniency in RSA PKCS#1 Signature Verification

[yahyazadeh]

Hi,

I was testing PKCS#1 v1.5 signature verification as implemented in perl-CryptX and noticed it has leniency in decoding some identifier octets of ASN.1 portion of the PKCS#1 encoded message.

Background. An identifier octet in DER encoding of a data value consists of three components: Class (two most significant bits); Form (6th bit, indexing from 1); and Tag (five least significant bits). The Class component is there to indicate the class of tag, whether it is a standard type or application specific type. For instance, 00 for Class bits shows the tag is universal type. The Form component indicates if the tag does include sub-type and thus represents a constructed type (if set) or it is just a primitive type without any sub-type (if not set). Finally, Tag represents the actual type of the data value in DER encoding. For example, the tag for a octet string type is b'00100'; including Form bit makes it b'000100' because octet string tag is primitive not constructed; and given that the octet string type has universal tag class we end up having b'00000100' (0x04 in hex) as final value for the identifier octet.

Problem. In the implementation, the Form bit is not being checked and thus it accepts two versions for an identifier octet (i.e., with and without Form bit being set). That being said, an identifier octet like octet string can be represented as both b'00000100' (0x04) and b'00100100' (0x24). This issue affects octet string type used in hash value encoding structure and the object identifier type of hash ID encoding structure.

Implication: (Interoperability issue). That is, the implementation accepts some invalid signature value that should have been rejected. Although it cannot cause a severe attack like a signature forgery, the leniency can create some interoperability issue with the other implementations.

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!"

• Example#1: incorrect encoding of object identifier type (0x26 instead of the correct encoding 0x06) used in the top DER encoded ASN.1 structure is accepted as a valid signature by the implementations.

  • I = 0x0001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff003031300d2609608648016503040201050004207509e5bda0c762d2bac7f90d758b5b2263fa01ccbc542ab5e3df163be08e6ca9
  • S = 0x8df69d774c6ac8b5f8aa16576ca37a4f948706c5daecb3c15cfd247a7657616b2bbb786b50158cac8c23e3289d300d3fbb82380b8746d929df36bdaf43a5fc5d1d04c61c98d47c22de02d051be3ba9e42b1c47aa519266d4cae244e5ce99b24771a13a7c8c7b08868a3eccf70b4bc7570d5131a1ac8943d91b0151c39da2ad75cd1b9a697d100eef6747217df581b272cfd1f549a901ff4951036a4eb28fd2ea1e9df3fa9fa457663f4259be8e5f2f2fb84f831a0ca5320e2b79f04a17830f43062c4c8fc0d0b1ff90567f3342d524f682ca26661caadf4272f2585e6013a92bfa68de72fe6174096890e4296aedd72da43aa508007df53fb852bd7162ab635b

• Example#2: incorrect encoding of octet string type (0x24 instead of the correct encoding 0x04) used in the top DER encoded ASN.1 structure is accepted as a valid signature by the implementations.

  • I = 0x0001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff003031300d0609608648016503040201050024207509e5bda0c762d2bac7f90d758b5b2263fa01ccbc542ab5e3df163be08e6ca9
    • S = 0x1ee08947536e6b11d8923c3b00061d26a6933b5345077ea0214fdcbcc1ad68395008ff709117047e6b01dd2a371dfa032c0732abc86ab2e0273bbd0dfe6b1c769e21bb9079982801d8f72e01be3244959312ab09bb8f88572dc23216719b9810c73edf826749604feb8da1345f83f0209271aca462c1235b4cb4ba538f85a9c03dd1dde1856fe73fd86b95566df2dfe8b0895c34489b97e02c8e48dabad7067619edec6267a776fa416fbcac0fcacf3efa7852ce33ed63a9149c685c303d98c3dc37ee87521bc5b130377345fc95c87aa48505470deaf6fb1064df041e3f03322b1ec90d3608deb17bf77f47066ecc6c511bfba69eed6da42881dcce603fcb2a

[karel-m]

@sjaeckel we should perhaps handle this in libtomcrypt, what do you think?

[karel-m]

Failing testcase:

use Test::More;
use Crypt::PK::RSA;

my $pk = Crypt::PK::RSA->new({
  e => "03",
  N => "E932AC92252F585B3A80A4DD76A897C8B7652952FE788F6EC8DD640587A1EE5647670A8AD4C2BE0F9FA6E49C605ADF77B5174230".
       "AF7BD50E5D6D6D6D28CCF0A886A514CC72E51D209CC772A52EF419F6A953F3135929588EBE9B351FCA61CED78F346FE00DBB6306".
       "E5C2A4C6DFC3779AF85AB417371CF34D8387B9B30AE46D7A5FF5A655B8D8455F1B94AE736989D60A6F2FD5CADBFFBD504C5A756A".
       "2E6BB5CECC13BCA7503F6DF8B52ACE5C410997E98809DB4DC30D943DE4E812A47553DCE54844A78E36401D13F77DC650619FED88".
       "D8B3926E3D8E319C80C744779AC5D6ABE252896950917476ECE5E8FC27D5F053D6018D91B502C4787558A002B9283DA7",
});

my $sig1 = pack("H*", "8df69d774c6ac8b5f8aa16576ca37a4f948706c5daecb3c15cfd247a7657616b2bbb786b50158cac8c23e3".
                      "289d300d3fbb82380b8746d929df36bdaf43a5fc5d1d04c61c98d47c22de02d051be3ba9e42b1c47aa5192".
                      "66d4cae244e5ce99b24771a13a7c8c7b08868a3eccf70b4bc7570d5131a1ac8943d91b0151c39da2ad75cd".
                      "1b9a697d100eef6747217df581b272cfd1f549a901ff4951036a4eb28fd2ea1e9df3fa9fa457663f4259be".
                      "8e5f2f2fb84f831a0ca5320e2b79f04a17830f43062c4c8fc0d0b1ff90567f3342d524f682ca26661caadf".
                      "4272f2585e6013a92bfa68de72fe6174096890e4296aedd72da43aa508007df53fb852bd7162ab635b");

my $sig2 = pack("H*", "1ee08947536e6b11d8923c3b00061d26a6933b5345077ea0214fdcbcc1ad68395008ff709117047e6b01dd".
                      "2a371dfa032c0732abc86ab2e0273bbd0dfe6b1c769e21bb9079982801d8f72e01be3244959312ab09bb8f".
                      "88572dc23216719b9810c73edf826749604feb8da1345f83f0209271aca462c1235b4cb4ba538f85a9c03d".
                      "d1dde1856fe73fd86b95566df2dfe8b0895c34489b97e02c8e48dabad7067619edec6267a776fa416fbcac".
                      "0fcacf3efa7852ce33ed63a9149c685c303d98c3dc37ee87521bc5b130377345fc95c87aa48505470deaf6".
                      "fb1064df041e3f03322b1ec90d3608deb17bf77f47066ecc6c511bfba69eed6da42881dcce603fcb2a");

is($pk->verify_message($sig1, 'hello world!', 'SHA256', 'v1.5'), 0, "gh issue #69 - invalid signature/1");
is($pk->verify_message($sig2, 'hello world!', 'SHA256', 'v1.5'), 0, "gh issue #69 - invalid signature/2");

[sjaeckel]

Yep, this should be handled in ltc.

[sjaeckel]

OK like that?

[karel-m]

Looks good to me.

@yahyazadeh can you test it please?

[yahyazadeh]

Just tested it. Great, it's been resolved.

[karel-m]

After the change will be merged to libtomcrypt/develop branch I'll release CryptX-0.072 (I want to avoid beeing ahead of develop).

[karel-m]

CryptX-0.072 released. Thank you for your time.