Dominic Williams

Occasionally useful posts about RIAs, Web scale computing & miscellanea

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

with 5 comments

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!

About these ads

Written by dominicwilliams

June 4, 2010 at 4:02 pm

5 Responses

Subscribe to comments with RSS.

  1. Dominic,

    Thanks for a informative post. I found that the as3crypto implementation of BigInteger.as does not work well in 64 bit systems. The code below illustrates this issue. This causes the issues during decrypting in as3crypto.

    Best Regards,
    Sidda

    sample code:

    var inputBytes:ByteArray = Hex.toArray(“514dcdbe5ccb98199c15b20139782e4d0f67707099c6105a94a4534d546d2baf0d5d408b64d3d7eede5661925fa6c41d106136d32c273ce82909b9116474ccb5739f1c48a9bc6101eee217a60ce340083b0ee7eb44732a9af16992ef7114c339ac71a791096fe47106b3ba5957267900f6f80da2333028d4aa58a09d9d6991fd”);

    var input:BigInteger = new BigInteger( inputBytes, 128, true);
    var outputBytes:ByteArray = input.toByteArray();
    if(inputBytes.length != outputBytes.length) { log(“bug occurred – length different”); log(“input: “, Hex.fromArray(inputBytes)); log(“output: “, Hex.fromArray(outputBytes)); return; }
    else {
    for(var i:int = 0; i < inputBytes.length; i++) {
    if( inputBytes[i] != outputBytes[i]) { log("bug occurred – length equal"); log("input: ", Hex.fromArray(inputBytes)); log("output: ", Hex.fromArray(outputBytes)); return; }
    }
    }
    log("done");

    Results from the test in a 64bit platform.

    input: 514dcdbe5ccb98199c15b20139782e4d0f67707099c6105a94a4534d546d2baf0d5d408b64d3d7eede5661925fa6c41d106136d32c273ce82909b9116474ccb5739f1c48a9bc6101eee217a60ce340083b0ee7eb44732a9af16992ef7114c339ac71a791096fe47106b3ba5957267900f6f80da2333028d4aa58a09d9d6991fd
    output: e000d00dc800801987600002c010038002d14020180210638001800c280e10027400000080db2c0e0000030007900081e80440003c80003c018082838058286880c000488000b030205003800049b4800218e700c2c385018087000f401a200080f100703c0001801e17400034200006fe580700600540ce14801a13801020fd

    Sidda

    July 24, 2010 at 12:41 am

  2. Since it is confirmed a bug on BigInteger class, until solved, working workarround is:
    1) Encrypt with random padding, as opposite as you stay.
    2) Check on RSAKey under _encrypt function after chunk.toArray(dst); that dst.length is a multiple of 64.
    3) If it is not, then return an empty ByteArray or something, and encrypt it again.

    This will make sure that blocks are properly encrypted, even if this implies retrying.

    After my tests, damaged blocks represent between 1% and 10%.

    Guti

    October 5, 2010 at 12:08 pm

    • Thanks for that. Will come in very useful for plenty of folks!

      dominicwilliams

      October 5, 2010 at 3:53 pm

    • Does anyone know if this works for the _decrypt function as well? In there, if the padding function returns null, an error is thrown immediately – there’s no chance to check dst.length.

      I’ve been trying to understand the problem for a couple days in hopes of finding a real solution, but this cryptography stuff is quite overwhelming. Just wishing I could get it working for my specific case at this point…

      Chris Rivers

      February 14, 2011 at 8:33 pm

  3. So this seems pretty bad. I need to verify a signature created by a web server in Adobe Air (mac & windows). It doesn’t seem like as3crypto works (I get the “padding function returned null” too). Is there any alternative?

    Jason

    November 5, 2010 at 9:01 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 67 other followers

%d bloggers like this: