Leniency in parsing block type byte and padding bytes for PKCS#1 v1.5 signature verification

[yahyazadeh]

Another finding besides the incompatibility issue reported here for PKCS#1 v1.5 signature verification, is the leniency in parsing the prefix of PKCS#1 structure.

Background. The prefix to the top ASN.1 structure of the PKCS1 v1.5 encoded message consists of leading byte (0x00), block type byte (0x01 for RSA signing scheme), padding bytes (0xFF...FF), and the end of padding (0x00). The length of padding bytes should also be at least 8 bytes and computed such that the final length of the PKCS#1 encoded message is equal to the length of public modolous N (denoted by || N ||). Block type byte is there to indicate to which RSA scheme this encoded message is belonged. The end of padding also specifies where padding bytes actually ends. The leading byte (0x00) also guarantees that the integer representative of the encoded message is not greater than or equal to the public modolous N. By and large, the prefix bytes should satisfy the requirements in order for RSA PKS1 v1.5 signature scheme to be able to hold on to its security promises.

Problem. However, jsrsasign v10.1.13 is lenient in checking such requirements and some other invalid signatures are mistakenly recognized to be valid. As will be shown below in the snippet taken from the source code, the issue arises because the implementation ignores the initial 0x00 bytes as they will disappear in octet strings to integer translation and more importantly the fact that an incorrect regex pattern matching is being used to peel off the prefix from the the top ASN.1 structure. This bug seems to be of similar type previously reported on RSA-PSS signature validation.

More detailed root cause analysis. In line 248 @ RSAKey.prototype.verify function in jsrsasign.js file, the initial 0x00 bytes will be ignored when octet strings are converted to integer (b = parseBigInt(j, 16)) and converted back to octet strings after taking modular exponentiation to the power public exponent (i = this.doPublic(b) and i.toString(16)). The regex being used in i.toString(16).replace(/^1f+00/, "") to remove the prefix only checks for the initial string 1f+00. So, it does not actually check for the padding bytes (0xFF....FF) and can be bypassed by long initial zeros (examples are given).

RSAKey.prototype.verify = function (f, j) {
    j = j.replace(_RE_HEXDECONLY, "");
    j = j.replace(/[ \n]+/g, "");
    var b = parseBigInt(j, 16);
    if (b.bitLength() > this.n.bitLength()) {
        return 0;
    }
    var i = this.doPublic(b);
    var e = i.toString(16).replace(/^1f+00/, "");
    var g = _rsasign_getAlgNameAndHashFromHexDisgestInfo(e);
    if (g.length == 0) {
        return false;
    }
    var d = g[0];
    var h = g[1];
    var a = function (k) {
        return KJUR.crypto.Util.hashString(k, d);
    };
    var c = a(f);
    return h == c;
};

Implication: (Interoperability issue) As this might not be susceptible to an immediate signature forgery attack because without the ability to hide random bytes, the attack cost seems to be prohibitive. However, this can simply create an interoperability issue.

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: Padding bytes with length 1

  • I = 0x0001ff003031300d0609608648016503040201050004207509e5bda0c762d2bac7f90d758b5b2263fa01ccbc542ab5e3df163be08e6ca9
  • S = 0x3fa376d1e4f51e9ff32636fe4d5c1b22b9f3d2e5d017ea79168e8e297316c4ca980827ad333f983bf9628e212a21f5fe5f2bde47088ef6b002cef31f9ce395abd6400f2ddfc8c2d152174ff47bf9e396843033c752df8613054692ef0489fb59e3bd31e30ed18d83474c898236d4691b03d80c46c5fdbb1e8c5901c65748d0fc6857b64cd6baab722ac827d1d1e2cb1638afebe83547115747590eb83808e3dd99df942dc45461bb54efc5e52dc989af33c1518612571288de34542241b3ae98a3600499206be8c2fb56b14ca967712161666adabd8f79723d5b274c5cf8c84f5b2e158294662de15e897b298c9203829bc846eeccce9b424d6cf7a1d9fa284e

• Example#2: All zero bytes as prefix

  • I = 0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003031300d0609608648016503040201050004207509e5bda0c762d2bac7f90d758b5b2263fa01ccbc542ab5e3df163be08e6ca9
  • S = 0xe5c9db5fb1f81cf431a568caeea54e3e7a3d54a2ae16929ecf52da9ea7018f18e7d3b2c3968a338d8b0cd0233c3073a25689da5310f52f2c14bf89c81ab2d8e2a0a5bef4403199aaa7a2bef6af6b33b15828f646358193c4ef8360c48e70f6e632b81432910b94b73854413fdb61f5377d88c5bb9848cd301b6e7609f90f4af94cbfae053fe7e9bcedd1c905d8a26f01133607d8f81efe993ad9daf78188ddbe6496dd7b6bea2cb3617708b96ccd9e0ca2398dd34d81567d2644f7a3ae4956a674e389aab9d8f1e732759209ddf17fd01cc347e6c74464c03e4d57be3052582f04c8553a6ebc6046742c659d7f542b4c72f8966dfde06036ad47d190dcddd03a

• Example#3: It can start with some number of 0x00 bytes, and then 0x1f byte followed by some 0xff bytes ending with 0x00 byte.

  • I = 0x00001fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff003031300d0609608648016503040201050004207509e5bda0c762d2bac7f90d758b5b2263fa01ccbc542ab5e3df163be08e6ca9
  • S = 0x472a5cb99114a3815d427b75b7e331192099bbf8e472995979395a53baa988a156b96c56bf9afa2c190103067a61e7caf99fb899f5023d9bf5eadb22ac90e2436c18ea7fac586eba9c5dee509b4e5f5d13d835dc139cb06a37b8caa1a4a66e1b8131987141139649b51ffdc48c8a28dfce9d8a6374136b959d8a916aaecc781829dd1d63147a4323807995b15c4c2542c1018fd990554ac978425c44c4575471222fdf218bd7378d696bf103a45fe05e53fd073290287d2fd9565b04b3467e2b3da4ee2a73211bf594ecf11b06ba5efeb61012ba1699624e2dbdffd060de930fff76019262714dd412946d7678f77720181c3f7316261d22c175c746e660fa4c

[jeremymeng]

Any plan to address the issue? It is listed as CVE-2021-30246

[kjur]

Hi, I'll fix this issue in a few days. Thanks.

[kjur]

This issue was fixed in the latest release 10.2.0. Thanks.

[kjur]

Security advisory for this issue was published:
GHSA-27fj-mc8w-j9wg