As3Crypto RSA “padding function returned null” death bug fix :)))

UPDATE: Unfortunately it transpired the fix I had only worked for small amounts of data I was encrypted/decrypting. It was masking a problem I could see in the code, but did not work with larger amounts of data. This post therefore has changed into a report of the problem. Sorry for any disappointment.

WHAT I FOUND: Firstly, this really is a horrible bug, and I’ve had to move on after spending much more time on it than I intended!

For those that what to grab the baton, here are the main points. When you encrypt/decrypt some data, the results will actually appear non-deterministic as illustrated by the code immediately following.

This is the first thing you need to eliminate to debug, and this achieved by disabling the Random class in Random.as by returning 0xff in the first line of nextByte(). Thereafter, you will the encryption operations that fail will be deterministic, unlike in the following code:

	protected function onRunTest(event:MouseEvent):void
	{			
		var privKey: String = "-----BEGIN RSA PRIVATE KEY-----\n" +
			"MIIBOwIBAAJBAM7U/mEVLiXKC4vGjpDcQ3qiAi/paF2Qp03Y6JXvcuYZG5/vHRgD\n" +
			"qWpVX+oFtXq7uhjcl+m4fx9zSfklcwdmknUCAwEAAQJAFN7PMFKnzm5dzePiPOHM\n" +
			"+VHhsJ33xwEysJtDlOWNjYQqhrpYRNgkx/fRKzEbY9ymwihRhO1IfBHpOYL5WXgQ\n" +
			"3QIhAPZKg4j+osWdRmv33Ql8bJdls5u5OqgX5k7clvbawwzrAiEA1vxFt/o9BMds\n" +
			"DJDxfDl1eYmUsYFUP2vMavjHgz3Phh8CIQCK9ClX7koJch1cJuCnTHK7zB5UWmH0\n" +
			"ml9O2Pe3WF85dwIgNhEn74cNhYAp2lcxhE5nDvPc429lIrYXqOd8NbN7130CIQCo\n" +
			"JUINRE5bjANnPIIviuVUqJDAmc1ZS29dyJiz/Qr+3w==\n" +
			"-----END RSA PRIVATE KEY-----";
		
		var pubKey: String = "-----BEGIN PUBLIC KEY-----\n" +
			"MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAM7U/mEVLiXKC4vGjpDcQ3qiAi/paF2Q\n" +
			"p03Y6JXvcuYZG5/vHRgDqWpVX+oFtXq7uhjcl+m4fx9zSfklcwdmknUCAwEAAQ==\n" +
			"-----END PUBLIC KEY-----";
						
		var dummyTxt:String =
			"0123456790012345679001234567900123456790012345679001234567900123456790012345679001234567900123456790"+
			"0123456790012345679001234567900123456790012345679001234567900123456790012345679001234567900123456790"+
			"0123456790012345679001234567900123456790012345679001234567900123456790012345679001234567900123456790"+
			"0123456790012345679001234567900123456790012345679001234567900123456790012345679001234567900123456790"+
			"0123456790012345679001234567900123456790012345679001234567900123456790012345679001234567900123456790"+
			"0123456790012345679001234567900123456790012345679001234567900123456790012345679001234567900123456790"+
			"0123456790012345679001234567900123456790012345679001234567900123456790012345679001234567900123456790"+
			"0123456790012345679001234567900123456790012345679001234567900123456790012345679001234567900123456790"+
			"0123456790012345679001234567900123456790012345679001234567900123456790012345679001234567900123456790"+
			"0123456790012345679001234567900123456790012345679001234567900123456790012345679001234567900123456790";
				
		var rsaPublic: RSAKey = PEM.readRSAPublicKey(pubKey);
		var rsaPrivate: RSAKey = PEM.readRSAPrivateKey(privKey);

		for (var i: int=0; i<500; i++) 
		{
			var message: String = dummyTxt.substr(0, Math.floor(Math.random() * 400));
			
			if (!doTest(rsaPublic, rsaPrivate, message))
			{	
				if (doTest(rsaPublic, rsaPrivate, message))
				{
					Alert.show("Arrghh. Nondeterministic! "+i);
					break;
				}
			}
			trace(i);
		}
	}
	
	protected function doTest(rsaPublic: RSAKey, rsaPrivate: RSAKey, message: String): Boolean
	{
		try {
			var src:ByteArray = Hex.toArray(Hex.fromString(message));
			var encrypted:ByteArray = new ByteArray();
			rsaPublic.encrypt(src, encrypted, src.length);
			
			var decrypted:ByteArray = new ByteArray();
			rsaPrivate.decrypt(encrypted, decrypted, encrypted.length);
			var original:String = Hex.toString(Hex.fromArray(decrypted));

			if (original != message) {
				Alert.show("Corruption: shouldn't happen!");
			}
		} catch (e: Error) {
			return false;
		}
		return true;
	}

Of course in many ways it would have been nice if the result continued to be nondeterministic without Random being disabled. It would mean some global state was accidentally disabled which would be relatively easy to find.

Instead, I’m afraid this looks like a bit of a demon bug buried in the complexities of bit shifting and maths with big integer values. If you are reading this, and you are an encryption specialist, realize that it is your responsibility to sort this out 😉 since it will take a non-specialist a very long time.

For those feeling brave, you’ll notice that in the following function from RSA.as, when chunk is calculated in such a way as to cause only 63 bytes to be written to dst, then you’ve got a problem. You can partially mask the problem by having BigInteger construct from 63-bytes, which works, but this does not solve the problem when a concatenation of big integers is written out and some entry but the last is shortened.

	private function _encrypt(op:Function, src:ByteArray, dst:ByteArray, length:uint, pad:Function, padType:int):void {
		// adjust pad if needed
		if (pad==null) pad = pkcs1pad;
		// convert src to BigInteger
		if (src.position >= src.length) {
			src.position = 0;
		}
		var bl:uint = getBlockSize();
		var end:int = src.position + length;
		while (src.position<end) {
			var block:BigInteger = new BigInteger(pad(src, end, bl, padType), bl, true);
			var chunk:BigInteger = op(block);
			chunk.toArray(dst);
		}
	}

Good karma in advance for anyone who is brave enough to take this on!