linux-kernel - Re: drivers/char/random.c: More futzing about

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20140611163818.GD27151@thunk.org>
Date:	Wed, 11 Jun 2014 12:38:18 -0400
From:	Theodore Ts'o <tytso@....edu>
To:	George Spelvin <linux@...izon.com>
Cc:	hpa@...ux.intel.com, linux-kernel@...r.kernel.org,
	mingo@...nel.org, price@....edu
Subject: Re: drivers/char/random.c: More futzing about

On Mon, Jun 09, 2014 at 09:17:38AM -0400, George Spelvin wrote:
> Here's an example of a smaller, faster, and better fast_mix() function.
> The mix is invertible (thus preserving entropy), but causes each input
> bit or pair of bits to avalanche to at least 43 bits after 2 rounds and
> 120 bit0 after 3.

I've been looking at your fast_mix2(), and it does look interesting.

> For comparison, with the current linear fast_mix function, bits above
> the 12th in the data words only affect 4 other bits after one repetition.
> 
> With 3 iterations, it runs in 2/3 the time of the current fast_mix
> and is half the size: 84 bytes of object code as opposed to 168.

... but how did you measure the "2/3 the time"?  I've done some
measurements, using both "time calling fast_mix() and fast_mix2() N
times and divide by N (where N needs to be quite large).  Using that
metric, fast_mix2() takes seven times as long to run.

If I only run the two mixing functions once, and use RDTSC to measure
the time, fast_mix2() takes only three times as long.  (That's because
the memory cache effects are much less, which favors fast_mix2).

But either way, fast_mix2() is slower than the current fast_mix(), and
using the measurements that are as advantageous (and most realistic)
that I could come up with, it's still three times slower.

My measurements were done using Intel 2.8 GHz quad-core i7-4900MQ CPU.

   		     	  	      	      - Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/