[Haskell-cafe] Tor project

[Tobias Dammers]

Timing attacks generally work such that the attacker samples a large
number of runs and maps their execution times; "humps" in the graph show
different code paths being taken.

Because they're statistical attacks, adding uniform noise (random
delays) does not work - it's uniform noise after all, you'll just raise
the floor, but the humps will still be there; the random delays will
just average out. Ten million times (10 + rand()) is still going to be
smaller than ten million times (1000 + rand()).

Instead, a way I've seen recommended is run the entire input through a
cryptographic hash function, and derive a delay from that, in a range
that dwarfs the actual timing difference. This way, things will still
average out, but the averaging will not compensate for the delay we
added, because that delay is always the same for a given input.

Of course designing functions to minimize execution time differences is
still a good idea; it's just not very reliable on its own, and for many
real-world cases, it's not even practical (or outright impossible) -
even if your code doesn't branch based on whether a username was found
in the database or not, your database does.

On Thu, Jul 31, 2014 at 05:05:26PM -0700, Dario Bertini wrote:
> On Thu, Jul 31, 2014 at 2:11 PM, Wojtek Narczyński <wojtek at power.com.pl> wrote:
> > But, AFAIK, the (necessary and sufficient) protection against timing attacks
> > is the addition of randomized waits. In the protocol layer, not in pure
> > encryption/decryption/hashing routines.
> 
> I agree that we don't have a lot of evidence for/against timing
> attacks in functional languages (that I know of).
> 
> But adding a randomized delay never seemed the correct solution to me
> (granted, I had the luck to never had to write code sensitive to such
> issues, and I never wrote a timing attack exploit either), I don't
> think that doing it in the protocol layer makes it neither necessary
> nor sufficient.
> 
> http://rdist.root.org/2010/01/07/timing-independent-array-comparison/
> 
> This explains the pitfalls in some possible timing attack misconceptions
> 
> -- 
> xmpp: berdario at gmail.com
> bitmessage: BM-2cTYXfGiSTsnx3righ6aHcJSWe4MV17jDP
> gpg fingerprint: 3F8D53518012716C4EEF7DF67B498306B3BF75A0 (used just
> for signing commits)
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe