newsObjectify - News: 201,326,592 Swizzle Tables Generated

 
 
Latest News
Admin Name Change posted by redwards, Sun 08 Jul 2018 12:26:12 AM UTC
Remote Storage posted by jsedwards, Sat 28 Apr 2012 06:09:36 PM UTC
Objectify Alpha_31.2 Released posted by jsedwards, Fri 20 Apr 2012 09:40:13 PM UTC
Public Objects 111111-0030 Released posted by jsedwards, Sat 12 Nov 2011 01:59:12 PM UTC
Objectify Alpha_31.1 Released posted by jsedwards, Sun 06 Nov 2011 03:18:33 AM UTC

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.

 

Back to the top

Powered by Savane 3.13-f8d8.
Corresponding source code