Cryptocat: RNG Bias, Decimal vs. Bytes

Cryptocat is a browser-based encrypted chat program. Cryptocat generates random numbers by generating random decimal digits, then converting them to a floating point number.

The way they were generating random decimal digits is biased. They did so by generating a random byte, discarding it if it was greater than 250, and otherwise dividing it by 10 to get an integer remainder between 0 and 9. They did this because 256 different values do not divide evenly into groups of 10, so there would be a bias. They didn't realize that between 0 and 250, there are actually 251 different integers, which still does not divide evenly into groups of 10.

  @@ -60,7 +60,7 @@ else {  
    var x, o = '';  
    while (o.length < 16) {  
     x = state.getBytes(1);  
 -   if (x[0] <= 250) {  
 +   if (x[0] < 250) {  
      o += x[0] % 10;  
     }  
    }   

They also confused bytes for decimal digits, and used too little entropy to generate their ECC keys.

 @@ -88,8 +88,8 @@ function checkSize(publicKey) {  
  // Generate private key (32 byte random number)  
  // Represented in decimal  
  multiParty.genPrivateKey = function() {  
 - rand = Cryptocat.randomString(32, 0, 0, 1);  
 - myPrivateKey = BigInt.str2bigInt(rand, 10);  
 + var rand = Cryptocat.randomString(64, 0, 0, 0, 1);  
 + myPrivateKey = BigInt.str2bigInt(rand, 16);  
   return myPrivateKey;  
  }  

NakedSecurity has an excellent blog post on the RNG flaw.

Lessons Learned

• Test the output of your random number generators with tools like diehard.
• Visually inspect the output of the functions you're using, to make sure it's in the format you expect.