Hello,
Nikos told me that there is a case where RSA-PSS signature verification leads to an assertion failure:
bignum.c:120: nettle_mpz_get_str_256: Assertion `nettle_mpz_sizeinbase_256_u(x) <= length' failed.
I thought it wouldn't be possible because 'x' is already rounded by the RSA modulus and 'length' is bound to the modulus.
However, actually 'length' is calculated as ((modBits - 1) + 7) / 8, i.e. one bit less than the original modulus. Thus, it would be possible that the octet length of 'x' exceeds 'length'.
I am attaching a patch for this.
Regards,
Daiki Ueno ueno@gnu.org writes:
Nikos told me that there is a case where RSA-PSS signature verification leads to an assertion failure:
bignum.c:120: nettle_mpz_get_str_256: Assertion `nettle_mpz_sizeinbase_256_u(x) <= length' failed.
I thought it wouldn't be possible because 'x' is already rounded by the RSA modulus and 'length' is bound to the modulus.
However, actually 'length' is calculated as ((modBits - 1) + 7) / 8, i.e. one bit less than the original modulus.
Ok, so if the modulo is k bits, m must be at most k-1 bits. Makes some sense.
Spotted by oss-fuzz at: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=2132
That url gives me a permission denied. (I even tried all my work accounts: chromium.org, webrtc.org and google.com). So what's needed to get access?
- /* Check "integer too long" error of I2OSP. */
- if (key_size < nettle_mpz_sizeinbase_256_u(m))
- goto cleanup;
I don't understand the I2OSP acronym. And I think this check would be more explicit as
if (mpz_sizeinbase(m, 2) > bits) goto cleanup;
(one might also move initial size checks before the allocations).
Thanks! /Niels
nisse@lysator.liu.se (Niels Möller) writes:
- /* Check "integer too long" error of I2OSP. */
- if (key_size < nettle_mpz_sizeinbase_256_u(m))
- goto cleanup;
I don't understand the I2OSP acronym. And I think this check would be more explicit as
if (mpz_sizeinbase(m, 2) > bits) goto cleanup;
(one might also move initial size checks before the allocations).
I2OSP is the procedure defined in RFC 3447, which converts a nonnegative integer to an octet string of a specified length. It is based on octets rather than bits.
I think the above check is too rigid, since it is based on bit-length, it wouldn't tolerate some cases such as m is 1016 bits and bits is 1015, where both can be represented in 127 octets.
Regards,
Daiki Ueno ueno@gnu.org writes:
nisse@lysator.liu.se (Niels Möller) writes:
if (mpz_sizeinbase(m, 2) > bits) goto cleanup;
(one might also move initial size checks before the allocations).
I think the above check is too rigid, since it is based on bit-length, it wouldn't tolerate some cases such as m is 1016 bits and bits is 1015, where both can be represented in 127 octets.
I see, a bit odd to tolerate that case. Can it ever happen for a valid signature created according to spec? Section 8.1.1 on signing says
1. EMSA-PSS encoding: Apply the EMSA-PSS encoding operation (Section 9.1.1) to the message M to produce an encoded message EM of length \ceil ((modBits - 1)/8) octets such that the bit length of the integer OS2IP (EM) (see Section 4.2) is at most modBits - 1, where modBits is the length in bits of the RSA modulus n
If this EM is the same EM recovered when verifying the signature, then it must still correspond to an integer of size at most modBits - 1. And if it happens that verification sees an EM in the range
2^{modBits - 1} <= O2ISP(EM) < n,
can the signature possibly be valid? I imagine it will be rejected by EMSA-PSS-VERIFY? It's not trivial to follow the notation, but I guess sec. 9.1.2, steps
5. Let maskedDB be the leftmost emLen - hLen - 1 octets of EM, and let H be the next hLen octets.
6. If the leftmost 8emLen - emBits bits of the leftmost octet in maskedDB are not all equal to zero, output "inconsistent" and stop.
implies a strict check of the bit size of m, and that step (6) would be redundant with a strict check of the bit size earlier.
Nevertheless, I see that there's also some value in having the implementation closely following the way things are described in the spec, with no cleverness.
Regards, /Niels
nisse@lysator.liu.se (Niels Möller) writes:
Daiki Ueno ueno@gnu.org writes:
nisse@lysator.liu.se (Niels Möller) writes:
if (mpz_sizeinbase(m, 2) > bits) goto cleanup;
(one might also move initial size checks before the allocations).
I think the above check is too rigid, since it is based on bit-length, it wouldn't tolerate some cases such as m is 1016 bits and bits is 1015, where both can be represented in 127 octets.
I see, a bit odd to tolerate that case. Can it ever happen for a valid signature created according to spec? Section 8.1.1 on signing says
- EMSA-PSS encoding: Apply the EMSA-PSS encoding operation (Section 9.1.1) to the message M to produce an encoded message EM of length \ceil ((modBits - 1)/8) octets such that the bit length of the integer OS2IP (EM) (see Section 4.2) is at most modBits - 1, where modBits is the length in bits of the RSA modulus n
If this EM is the same EM recovered when verifying the signature, then it must still correspond to an integer of size at most modBits - 1.
Yes, that seems to be correct, as both EMSA-PSS-ENCODE and EMSA-PSS-VERIFY takes emBits (= modBits - 1), which is defined as "maximal bit length of the integer OS2IP (EM)".
I am sorry for the confusion.
Regards,
Daiki Ueno ueno@gnu.org writes:
If this EM is the same EM recovered when verifying the signature, then it must still correspond to an integer of size at most modBits - 1.
Yes, that seems to be correct, as both EMSA-PSS-ENCODE and EMSA-PSS-VERIFY takes emBits (= modBits - 1), which is defined as "maximal bit length of the integer OS2IP (EM)".
I am sorry for the confusion.
No problem, thanks for the bug report and patch.
I've now committed your patch with some reorganization of this part (I added a bit-size check, and turned the later, supposedly redundant, check on leading bits to an assert) and minor changes to the test case.
Pushed to the master-updates branch, please have a look and see if you think I got it right.
As for the locked up report on https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=2132, I've read up a bit on oss-fuzz policy, and I'd expect it to be made publicly viewable a month after the bug is fixed or three months after original filing, whichever happens first. If you like, you could add me to the cc list on the report, then I may be able to access it right away (I haven't yet been able to see it).
Regards, /Niels
On Fri, Jun 9, 2017 at 11:01 PM, Niels Möller nisse@lysator.liu.se wrote:
Daiki Ueno ueno@gnu.org writes:
If this EM is the same EM recovered when verifying the signature, then it must still correspond to an integer of size at most modBits - 1.
Yes, that seems to be correct, as both EMSA-PSS-ENCODE and EMSA-PSS-VERIFY takes emBits (= modBits - 1), which is defined as "maximal bit length of the integer OS2IP (EM)".
I am sorry for the confusion.
No problem, thanks for the bug report and patch.
I've now committed your patch with some reorganization of this part (I added a bit-size check, and turned the later, supposedly redundant, check on leading bits to an assert) and minor changes to the test case.
Pushed to the master-updates branch, please have a look and see if you think I got it right.
As for the locked up report on https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=2132, I've read up a bit on oss-fuzz policy, and I'd expect it to be made publicly viewable a month after the bug is fixed or three months after original filing, whichever happens first. If you like, you could add me to the cc list on the report, then I may be able to access it right away (I haven't yet been able to see it).
I do not think it is possible to be added in CC for one bug only (at least I cannot find that in the interface). You either get added (and receive) to all found gnutls bugs, or none. I have created a mirror of the original bug with a valgrind trace to: https://gitlab.com/gnutls/gnutls/issues/214
regards, Nikos
nettle-bugs@lists.lysator.liu.se
-
Daiki Ueno -
Nikos Mavrogiannopoulos -
nisse＠lysator.liu.se