Objectify - News
201,326,592 Swizzle Tables Generated
Item posted by J. Scott Edwards <jsedwards> on Sat 27 Mar 2010 01:45:53 PM UTC.
But I've started over! In January 2010 I generated an additional 50 million swizzle tables (see my previous news article: https://savannah.nongnu.org/forum/forum.php?forum_id=6156), for a total of 100,663,296 tables. In February I generated another 100 million tables for a total of over 200 Million.
However, in the last few days of January I started using a new virtual machine (at http://www.slicehost.com) Quad-Core AMD Opteron(tm) Processor. It turned out that, since I was running several processes at once, once in a while two processes would kick off at the same instant and stay in sync for a portion of the keys. I don't consider this completely bad, because an attacker would still have to be able to completely simulate your environment at the exact instant a key was generated, to even recreate a portion of the key. And I was not using /dev/random, which one should have been using, had they been generating a real key.
But since I had just read this article: http://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html a few days before, I decided to try out the Fisher-Yates Shuffle http://en.wikipedia.org/wiki/Fisher-Yates_shuffle algorithm.
It turned out that the Fisher-Yates shuffle was significantly faster than my old algorithm in test_random.c. However, I discovered if I only made one pass (without using /dev/random) it suffered from the same fate as my old algorithm on the Quad-Core machine.
So I modified it to reshuffle the swizzle tables at random after the initial pass. After running several tests on the Quad-Core machine I found that if it reshuffled for 12 times as long as the original pass took, there were no duplicates left. And even then it was still significantly faster than the old test_random program. The Fisher-Yates program is so much faster that I have generated almost 100 million new swizzle tables in about a week, and the majority of them one at a time (I.E. not running multiple processes).
The new algorithm is in the fisher-yates.c file in the src/apps/lab/test-random directory.
Powered by Savane 3.14-f13d.
Corresponding source code