Predicting UnixTime in an Initialization Vector #security #cryptography

I'm always amazed that people use unixtime as a unique number for anything, even unixtime in milliseconds. A request that comes in milliseconds from the next might just pass muster, but for cryptography this is just not enough!

Sorry let me start from the beginning...

Due to some restrictions at regarding SSL certificates I was forced to come up with a way to encrypt sensitive data being passed from a user's browser to an application server. I thought it would be pretty simple to build my own Diffie-Hellman key exchange in JavaScript, which it was. Encryption on the otherhand is not my forté, so I thought I would rely on somebody else for that work. It was suprisingly difficult to find a Cipher Block Chaining implementation of Rijndael (Advanced Encryption Standard, AES) in JavaScript, so I decided to go with the Counter Mode implementation I found over at AES Advanced Encryption Standard.

All was well, the implementation was a little tricky as I was made some mistakes in my Diffie-Hellman implementation due to the lack of Big Number support in JavaScript. Once I'd finally solved that with a dive into arrays of numbers I was suddenly presented with strange behavior. All the encrypted blocks in a sequence seemed to start with the same block, 4 bytes which were similar in all messages and then 4 bytes which were identical. There was nothing wrong with the implementation. The SharedKey was always different - I was using an 64 bit key for testing - and I could decrypt the messages fine on both sides. I was a little baffled.

So when I was reading about the new SHA3 on Bruce Schneier's blog and thought that it could have something to do with the Salt, as SSHA or Salted SHA. The Salt is almost identical to the Initialization Vector or nonce used in Cryptography. So I examined the JavaScript code and saw this:

var counterBlock = new Array(blockSize);
var nonce = (new Date()).getTime(); // timestamp: milliseconds
var nonceSec = Math.floor(nonce/1000);
var nonceMs = nonce%1000;
for (var i=0; i<4; i++) counterBlock[i] = (nonceSec >>> i*8) & 0xff;
for (var i=0; i<4; i++) counterBlock[i+4] = nonceMs & 0xff;
var ctrTxt = '';
for (var i=0; i<8; i++) ctrTxt += String.fromCharCode(counterBlock[i]);

Needless to say I was surprised, also because initially I hadn't even noticed that the last 4 bytes of the 8 byte sequence were identical. So I double checked the rest of the code and saw that indeed the IV was prepended to the encrypted block. Shocking was the fact that unixtime was being used to create the nonce. Unix time is the number seconds since the January 1st, 1970 in UTC, which means that the current time and date can be extracted. For each second that passes only one is added to the total, which means that the first portion is predictable as long as you know what date and time it is in UTC. The second part can be guessed or even pre-calculated in a rainbow table, there are after all only 86400 seconds in a day. What's worse is that the number of milliseconds, is always less than 1000, so we can look it up in the same rainbow table we created for the seconds of the day. That means that this entire IV is predicable, as long as we can read a calendar and tell the time, or have a computer to do it for us.

So I took out my trusty editor and plugged the hole like this:

function generateIV() {
var counterBlock = new Array(16);
var nonce = Math.floor(Math.random()*18446744073709551616)
var nonceSec = Math.floor(nonce/4294967296);
var nonceMs = nonce%4294967296;
// encode nonce with seconds in 1st 4 bytes, and (repeated) ms part filling 2nd 4 bytes
for (var i=0; i<4; i++) counterBlock[i] = (nonceSec >>> i*8) & 0xff;
for (var i=0; i<4; i++) counterBlock[i+4] = (nonceMs >>> i*8) & 0xff;

var ctrTxt = '';
for (var i=0; i<8; i++) ctrTxt += String.fromCharCode(counterBlock[i]);

return ctrTxt;
}

I then I used the scatter chart option in Open Flash Chart 2 to create a distribution chart to verify that the distribution of x = nonceSec and y = nonceMs was random, which as far as I could determine it was. Had the person who wrote this had done the same he would have seen how predictable his nonce was and could have fixed it.

So what did you do today?

UPDATE: I had a discussion with Chris Veness, the author of the library I referred to above, and he said the following:

There is no suggestion that the nonce needs to be unpredictable (though it must be unique), hence your concerns are, to the best of my understanding, entirely misplaced.

I feel much more comfortable following SP800-38A to the letter (as I believe I have done with the 'second approach'), rather than second-guessing what might be improvements, as I have noticed that for a non-expert, alterations which intuitively appear to improve cryptographic strength can potentially have exactly the reverse effect.

Further, while your change results in a low likelihood of compromising uniqueness, it is clearly breaching this cardinal requirement of the specification ("A procedure should be established to *ensure* the uniqueness of the message nonces").

I trust you will update your blog so that your readers won't get drawn into a similar confusion.

technorati tags: aes, cryptography, initializationvector, salt, security, sms, risk