Date: Thu, 25 Jun 2015 00:16:47 +0000
From: Marsh Ray <maray@...rosoft.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: RE: [PHC] Why protect against side channel attacks

> While I would imagine it's almost infeasible, at this moment in time I
>also don't see why a PDF with data-dependent timings would ever be picked anyway.

While I agree data dependent timings are a non-starter, it’s kind of a shame. If the access patterns is not known in advance (i.e., it varies per guess) it can make it harder for an attacker to hide memory latency.


-          Marsh

From: Peter Maxwell [mailto:peter@...icient.co.uk]
Sent: Wednesday, June 24, 2015 4:36 PM
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Why protect against side channel attacks



On 24 June 2015 at 20:12, Greg Zaverucha <gregz@...rosoft.com<mailto:gregz@...rosoft.com>> wrote:
Some of the recent discussion has again turned to whether side-channel resistance is worthwhile.  Marsh and I were discussing side-channel protections a while back and there was one point that I found really compelling.  I’ve tried to reproduce it here, apologies if this was already discussed on the list.

Suppose you use password hashing function X in many products and services, in a range of contexts (on mobile devices, PCs, servers, in VMs, etc…).  Now suppose that cache-timing attacks against X are shown to be practical, someone has released an attack tool, and it’s in the news under the name PasswordBleed, and someone has even made a logo for it.  The tool needs the salt and username.  It works by observing the cache access pattern of a victim process/VM, which narrows down the search space to a set of passwords small enough to attack online (i.e.,
​​
the tool re-computes the hashes for passwords in a dictionary and compares their access patterns to the observed pattern, those that are close are kept). So no breach has occurred and no hashes were leaked.  (I realize that in most systems the salts aren’t public, but I think we all agree that X should not get weaker if the salt is known).

How do you respond/recover in this situation?  Which passwords were compromised?


In your stated scenario, the conditions are perhaps unnecessarily contrived, e.g. if a PDF used a secret key in the calculation then it would probably force the attacker to undertake an actual breach of the password db.

However, if the situation is restated to assume that the salt and secret key are private, your attack scenario may still hold.  Lets assume there is i bits of global secret data, s, and j bits of per-password secret data, h, say.  The question then becomes: how much of s and h you can determine in observing the side-channel for a single PDF calculation; how many calculations, n, per hash you can observe; and, obviously i and j.  That would give you a rough idea of the resulting search space(s).
​
For practical purposes, I suspect you may need n much larger than tolerable.  However, I've not kept pace with the research in the field and there are other options available to the attacker such as testing random online passwords repeatedly to gather statistical information to determine s, and also compare to the much fewer samples of valid password timings for h the attacker may have, i.e. you can't force a user to login 2^20 odd times but you can probably do that many tests of random passwords which might help exclude certain classes of password.

While I would imagine it's almost infeasible, at this moment in time I also don't see why a PDF with data-dependent timings would ever be picked anyway.





Content of type "text/html" skipped

Powered by blists - more mailing lists