A couple nights ago, while coming home from work, I started thinking about the button you press on the d-note web application (an instance running at https://secrets.xmission.com) for generating passphrases used to encrypt your note. Each passphrase is a 22-character base 64 passphrase. Initially, I was using the following code in JavaScript:

1 2 3 4 5 6 7 8 9 | function make_key() { var text = ""; var possible = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_"; for(i=22; i--;) { text += possible.charAt(Math.floor(Math.random() * possible.length)); } return text; } |

Simple, functional, works. However, using Math.random() for each character generation isn't cryptographically strong. The d-note web application is known for going over the top on the security engineering, and I know I can do better. So, I did a little digging, and learned about the "Web Crypto API" that many modern browsers support, despite the specification being a "working draft". So, I figured I could use that for my code. As such, the code morphed into the following:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | function make_key() { var text = ""; var possible = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_"; var random_array = new Uint32Array(22); // Make some attempt at preferring a strong CSPRNG first if (window.crypto && window.crypto.getRandomValues) { // Desktop Chrome 11.0, Firefox 21.0, Opera 15.0, Safari 3.1 // Mobile Chrome 23, Firefox 21.0, iOS 6 window.crypto.getRandomValues(random_array); } else if (window.msCrypto && window.msCrypto.getRandomValues) { // IE 11 window.msCrypto.getRandomValues(random_array); } else { // Android browser, IE Mobile, Opera Mobile, older desktop browsers for(i=22; i--;) { random_array[i] = Math.floor(Math.random() * Math.pow(2, 32)); } } for(i=22; i--;) { text += possible.charAt(Math.floor(random_array[i] % possible.length)); } return text; } |

The Web Crypto API ensures that browser is using a cryptographically secure non-blocking PRNG from the operating system, such as /dev/urandom that ships with the Linux kernel. While this works, it means that browsers that don't support the Web Crypto API are stuck with non-cryptographic passphrases. This certainly wouldn't do, so I went out to fix it.

Enter Blum Blum Shub (this sounds like something out of a Dr. Seuss book). Blum Blum Shub is a cryptographically secure PRNG, provided a few criteria:

- The primes 'p' and 'q' can be static or chosen pseudorandomly.
- The primes 'p' and 'q' should be congruent to 3 modulo 4.
- The seed 'x0' should be chosen pseudorandomly to start the process.
- The seed 'x0' should not be '0' or '1'.
- The seed 'x0' should be coprime to the product of the primes 'p' and 'q'.
- The GCD of phi(p-1) and phi(q-2) should be small (subjective?), where phi is the Euler's totient function.

Unfortunately, as the product of primes 'p' and 'q' grow, the Blum Blum Shub algorithm slows to a crawl. Fortunately and unfortunately, the maximum integer JavaScript can store is 53-bits, or 2^53. This means the product of 'p' and 'q' cannot exceed that value. That leaves us with an integer space of '2^26' and '2^27' for the primes. However, this is okay, as even 'p = 11' and 'q = 19' generate a cycle that is long enough for our 22-character passphrase.

Thus, the code had changed to:

1 2 3 4 | else { // Android browser, IE Mobile, Opera Mobile, other browsers random_array = bbs(22); } |

This new "bbs(n)" function is the bread and butter for generating cryptographically secure pseudorandom numbers. The function takes an integer as an argument, to know how many numbers need to be generated, and returns an unsigned 32-bit integer array with that many random numbers. The code is as follows:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | function gcd(x, y) { if(!y) return x; return gcd(y, x%y); } function seed() { var s = 2*Math.floor(Math.random() * Math.pow(2,31))-1; //odd if(s < 2) { return seed(); } else { return s; } } function bbs(n) { // Blum Blum Shub cryptographically secure PRNG // See https://en.wikipedia.org/wiki/Blum_Blum_Shub var a = new Uint32Array(n); // Max int = 2^53 == (2^26)*(2^27) -> (2^p1)*(2^p2) var p1 = Math.floor(Math.random()*2)+25; // first power, 25 or 26 var p2 = 51-p1; // second power var p = random_prime(2*Math.floor(Math.random() * Math.pow(2,p1))-1); var q = random_prime(2*Math.floor(Math.random() * Math.pow(2,p2))-1); var s = seed(); // Ensure each quadratic residue has one square root which is also quadratic // residue. Also, gcd(totient(p-1),totient(q-1)) should be small to ensure a // large cycle length. while(p%4 != 3 || q%4 != 3 || gcd(totient(p-1),totient(q-1)) >= 5) { p = random_prime(2*Math.floor(Math.random() * Math.pow(2,p1))-1); q = random_prime(2*Math.floor(Math.random() * Math.pow(2,p2))-1); } // s should be coprime to p*q while(gcd(p*q, s) != 1) { s = seed(); } for(i=n; i--;) { s = Math.pow(s,2)%(p*q); a[i] = s; } return a; } |

The key to this function is generating primes 'p' and 'q' that meet the requirements outlined earlier in the post. The primes can be static, with the seed pseudorandomly generated, or the primes can also be pseudorandomly genenerated. I went with the latter. So, the only trick to getting these values, is testing for primality.

The standard way to test for primality is through trial division. Unfortunately, it's slow. Sure, there are a few optimization techniques that you can do to speed things up, but by and large, it's not an efficient way of attacking the problem. Instead, I applied the Miller-Rabin test for composites. Miller-Rabin uses "witnesses" that "testify" about the compositeness of a positive integer. The more witness there are to testify that your integer is composite, the more likely it is. Thus, we would say that we have a "strong composite" integer. However, if there are zero witnesses for a positive integer we can say that the integer "may or may not be prime". However, after enough witnesses, we can actually say with deterministic fact if a number is prime.

I'll stop going over the algorithm there, and let you read up on the Wikipedia article about it. Suffice it to say, the Miller-Rabin primality test runs in O(k*log(n)^3), where 'k' is the accuracy that is sought. This is good news for Blum Blum Shub, as it's slow enough already. Code below:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | function modProd(a,b,n){ if(b==0) return 0; if(b==1) return a%n; return (modProd(a,(b-b%10)/10,n)*10+(b%10)*a)%n; } function modPow(a,b,n){ if(b==0) return 1; if(b==1) return a%n; if(b%2==0){ var c=modPow(a,b/2,n); return modProd(c,c,n); } return modProd(a,modPow(a,b-1,n),n); } function isPrime(n){ // Miller-Rabin primality test taken from // http://rosettacode.org/wiki/Miller-Rabin_primality_test#JavaScript // O(k*log(n)^3) worst case, given k-accuracy if(n==2||n==3||n==5) return true; if(n%2==0||n%3==0||n%5==0) return false; if(n<25) return true; for(var a=[2,3,5,7,11,13,17,19],b=n-1,d,t,i,x;b%2==0;b/=2); for(i=0;i<a.length;i++) { x=modPow(a[i],b,n); if(x==1||x==n-1) continue; for(t=true,d=b;t&&d<n-1;d*=2){ x=modProd(x,x,n); if(x==n-1) t=false; } if(t) return false; } return true; } function random_prime(n) { while(!isPrime(n)) n -= 2; return n; } |

The primes 'p' and 'q' must then go through some rigid tests to ensure that the algorithm has a long cycle, and the seed doesn't fall into a trap, where it falls to 0, and the algorithm cannot recover. Part of these tests is using Euler's totient function. The totient function does nothing more than just count what are called "totatives". A "totative" is a number that is coprime to a given number 'n'. In other words, the totative and 'n' do not share any common divisors other than '1'. Every positive integer from 1 through 'n' must be tested. Unfortunately, this is slow. However, there is a proof using a product formula, which shows that we can arrive at the same result in O(sqrt(n)/3) time. Again, because Blum Blum Shub is slow, we need to keep our processor time down.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | function totient(n) { // compute Euler's totient function // O(sqrt(n)/3) worst case // Taken from: // https://en.wikipedia.org/wiki/Talk:Euler%27s_totient_function#C.2B.2B_Example if(n < 2) return n; var phi = n; if (n % 2 == 0) { phi /= 2; n /= 2; while(n % 2 == 0) n /= 2; } if (n % 3 == 0) { phi -= phi/3; n /= 3; while(n % 3 == 0) n /= 3; } for(p = 5; p * p <= n;) { if(n % p == 0) { phi -= phi/p; n /= p; while(n % p == 0) n /= p; } p += 2; if(p * p > n) break; if(n % p == 0) { phi -= phi/p; n /= p; while(n % p == 0) n /= p; } } if(n > 1) phi -= phi/n; return phi; } |

Putting everything together, the Blum Blum Shub algorithm on my workstation can produce approximately 1 million random numbers per second for a 53-bit space. We only need 22 numbers, so that should be sufficient, even for weaker devices. I was able to test the code successfully on a number of browsers that do not support the Web Crypto API, and the key generation is near instantaneous, even on my phone. Interacting with the console, here is the output of one call to the algorithm:

> bbs(22); [3143943020, 475278844, 386457630, 124718623, 280175014, 2600881459, 127152064, 749398749, 2269393658, 692609408, 1218408987, 1523732228, 1265360812, 1641372390, 2500929554, 2223592103, 2462017186, 310616491, 426752821, 2973180471, 2248877527, 574751875]

Those numbers are cryptographically strong, because they are the result of the product of two primes, which means using the sequence to get back to the primes is at least as difficult as the factoring problem. It also turns out that it may also be at least as difficult as computing modular square roots, which is at least as difficult as the factoring problem.

So, even though most users visiting a site hosting d-note will likely be using the Web Crypto API, there may be some other browsers that are not. For them, should they choose to have the browser generate the passphrase for encrypting their note server-side, they can rest assured that the result is cryptographically strong.

## Post a Comment