RSA bug fixes

[hoylen]

Fixed three major bugs that prevented RSA code from working correctly.

1. Output block offsets were not being honoured in asymmetric block ciphers

In the processBlock methods of the two asymmetric block cipher implementations, the output offset parameter (outOff) was not being used at all.

Towards the end of the method, it used to say:

out.setRange(0, rlen, block.sublist(start));

Which means it always wrote the block to the beginning of out instead of starting at the requested outOff offset into it. This bug appears when multiple blocks are being processed, since all the output blocks are written over each other at the beginning of the output buffer, instead of at the correct positions in the output buffer.

It has been changed to:

out.setRange(outOff, outOff + rlen, block.sublist(start));

This is in lib/asymmetric/oaep.dart and lib/asymmetric/pkcs1.dart.

2. RSAEngine checks were rejecting correct blocks

Several checks in the RSAEngine.processBlock method were wrong.

2.1 Did not work if the plaintext spans over multiple blocks

This check is wrong, because the inpLen can be huge (when the plaintext is large). The method is only being asked to process len bytes from it starting at the inpOff offset -- it is not being asked to process the entire inpLen from it. It is the size of len that matters, not inpLen.

if (inpLen > (inputBlockSize + 1))  { throw ... }

The check has been changed to check if there are len bytes remaining/available in the input, from inpOff to the end of the array.

if (inpLen < inpOff + len) { throw ... }

2.2 RSAEngine does not work the same as OAEPEncoding or PKCS1Encoding

This check is wrong, since when using the RSAEngine directly (i.e. without an asymmetric block cipher around it) to encrypt, the last block (or the first and only block) is usually shorter than the maximum input block size.

if ((inpLen == (inputBlockSize + 1)) && !_forEncryption) { throw ... }

It is much simpler to just check if the block length is not larger than the allowed input block size. That test applies equally when encrypting or decrypting.

if (inputBlockSize < len) { throw ... }

Of course, it is not secure to use the RSAEngine without an asymmetric block cipher (e.g. OAEP or PKCS #1), but from an API point of view, the RSAEngine is an implementation of AsymmetricBlockCipher, so it should function the same. If the aim is to prevent naive users from using the library insecurely, the exception should provide a meaningful error message (e.g. "For security reasons RSAEngine must be used with an asymmetric block cipher") instead of what it used to say ("Input too large for RSA cipher" - which was misleading anyway).

3. Signature verification throws exceptions instead of returning false

The RSASigner.verifySignature method used to throw an exception if the signature has been tapered with. It correctly returns false if the data was tampered with, but not when the signature was tampered with.

The exception comes from the PKCS1Encoding._decodeBlock which fails to detect the 0x01 type byte at the beginning of the block -- the block that was "decrypted" from the signature bytes. Obviously, if the signature bytes were tampered with in any way, the "decrypted" block will bear no resemblance to the original "plaintext" block. There will be a 1 in 256 chance it would find the type byte, and an even lower chance of it finding correct padding -- so the byte-by-byte comparison done in lines 125-131 of _lib/signers/rsasigner.dart (that do return false) rarely gets used.

If the signature has been tampered with, the verifySignature method will usually throw an exception (with a confusing message) rather than return false.

The verifySignature method now catches the exception and returns false.

[stevenroose]

Amazing! Anyone else here that can verify/ACK?

[hoylen]

Try the attached demo program (after renaming .txt to .dart), which has now also been updated in the documentation pull request.

Run it without any arguments to exercise the signing bug. Pointy Castle 1.0.2 will fail when the signature has been tampered with.

Run it with the "-l" (or "--long") to use plaintext that is larger than will fit into one input block. All three encryption modes will fail: using the RSAEngine by itself, with PKCS #1 and with OAEP.

Add the "-v" (or "--verbose") option to see more details.

rsa-demo2.txt

[stevenroose]

When I run the tests locally, I get a failure for the test/asymmetric/oaep_test.dart with Null/OAEP.

I also see those on master, so you didn't introduce them. But could you perhaps look into them, since you're looking into OAEP already? I wouldn't vouch for the correctness of the tests either, they were there when I took over the project at the time.

[hoylen]

The unit test _test/asymmetric/oaeptest.dart uses a NullAsymmetricBlockCipher as the underlying asymmetric cipher engine (i.e. instead of RSAEngine). That test class has been hard-coded with a maximum input and output buffer size of 70 bytes (see line 23 of _test/test/src/null_asymmetric_blockcipher.dart).

From what I can gather from the OAEP source code, OAEP enhanced blocks contains a seed (20 bytes), a digest (20 bytes), a single sentinel byte, and the data bytes. With the NullAsymmetricBlockCipher as the underlying cipher, that all has to fit into 70 bytes. Therefore, the size available for the data bytes is just 29 bytes (= 70 - 20 - 20 - 1).

The two plaintexts used in that unit test are 58 and 60 bytes long -- so the block is not large enough. The plaintext will have to be processed over multiple blocks to work; but the test case code is not that sophisticated. The PKCS#1 Asymmetric Block Cipher unit tests work because its enhanced block don't require 21 bytes, so it does fit into a single 70 byte block.

A simple first-step fix is to change that 70 byte limit into a number that is 101 or greater to fit these specific test plaintext values (I suggest 128 as a nice round number). (101 = 60 + 20 + 20 + 1)

Once that is done, the tests fail because either the calculated cipher text does not match the provided expected value; or the decryption fails.

I wouldn't vouch for the correctness of the tests either

You are correct there. The test vectors used in both the OAEP and PKCS#1 asymmetric block cipher tests are exactly the same. Obviously, that can't be correct, so the test vectors are definitely wrong.

I am also not confident the OAEP implementation is correct. From what I saw when I was writing the tutorials, it didn't make sense to me. For example, the digest 20 bytes is always the same (since the digest is never provided any bytes to process). Since the unit test doesn't work, it is highly likely the implementation was never completed, and therefore is not correct.

To fix the tests, we/someone needs to first find a set of reliable test vectors. Something like the RFC 4231 for the HMAC test vectors would be ideal. Failing that, finding another implementation that is known to be correct.

[stevenroose]

So conclusion is that you don't think it should be included in this PR's scope?

[hoylen]

Good news. I've found a test vector for RSA-OAEP, and I now think the OAEP implementation is correct (but restricted to just SHA-1, no support for parameters and can only use MGF1).

I've created an encryption test that passes, and am now trying to get the decryption test working. I just need to figure out how to calculate the RSA privateExponent, if all you have is the modulus, publicExponent, p, q, dP, dQ and qInv -- any ideas?

I say accept this "RSA bug fixes" pull request, and I'll be submitting a separate pull request for the OAEP tests.

[stevenroose]

Cool, thanks a lot for your work!