## Thursday, July 11, 2013

### 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 <= 250) {
+   if (x < 250) {
o += x % 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.