develooper Front page | perl.perl5.porters | Postings from October 2003

Re: Hypothetical attack on 5.8.1 randomized hashes.

Thread Previous | Thread Next
From:
Scott A Crosby
Date:
October 31, 2003 09:10
Subject:
Re: Hypothetical attack on 5.8.1 randomized hashes.
Message ID:
oyd65i5tjtk.fsf@bert.cs.rice.edu
On Fri, 31 Oct 2003 16:04:28 +0000, Alan Burlison <Alan.Burlison@sun.com> writes:

> Scott A Crosby wrote:
> 

> You have forgotten one crucial bit of the equation - the OS scheduler.
> Most scheduler ticks are in the 50-100Hz range, so that will add
> orders of magnitude more jitter than rehashing. 

s/rehashing/strcmp()/  ?

Although true, this is inapplicable. Generally the timer interrupt is
only used to context switch out of a task that doesn't otherwise
block. Normally on an idle machine if a task is blocked and anything
comes in to unblock it. (Either from a timeout in sleep() or select()
or incoming data from the network) it is unblocked and run
immediately.

> Plus Apache 1.x runs as multiple processes, so you can't be sure
> that your probes will hit the same process all the time anyway,
> which is going to add even more jitter.

*agreed* The attack is hypothetical. The point is that at *some*
threshold latency, it can be observed. What that particular latency is
is still an open question. Whether mod_perl can be tricked into
exposing a hash-collision latency sufficient to expose the hash key
remains unknown. It is concievable. A great deal of statistical
analysis and experimentation is needed.

However, food for thought. In one underanalyzed trial between two
machines on 100baseT connected by one switch, the latency difference
between the 20th and 30th percentile (1000 packets) of 10,000 trial
packets had a range of *17 NANOSECONDS*. This is between two ordinary
user-processes exchanging UDP packets. I'll never claim that I can
distinguish latencies that low, but it is suggestive that remote
timing may in some situations have phenominal accuracy.

Rather than drop this on Stas and p5p again later, I'm bringing my
speculations out to give them a choice of whether to think over it now
or after I have some more concrete results.

Scott

Thread Previous | Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About