Date: Thu, 28 Mar 2013 09:29:36 -0700
From: Jeremy Spilman <jeremy@...link.co>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] Re: Suggestion: API should include a verifier function

Thanks Denis and Peter for the pointer and samples. I thought the slides were an interesting attempt and brought up some good food for thought.  

Note the attack won't work for salted hashes because the whole point is to learn something about the hash prefix, which you don't if you don't know the salt. It can't see how it would help an attacker to know password '123456' seems to match more bytes if you don't know what those bytes are. This is mentioned on the slides at the end.

Personally I was amused by an attack which involves hitting the login API millions of times. There are cases when timing attacks might conceivably go unnoticed or un-rate-limited, but just trying the 'Top 10K' passwords would probably get you logged in faster if the target is allowing unlimited online attacks against 'IsThisYourPassword'.

Another possible consideration against providing an explicit VERIFY which combines the hash and comparison into a single function, and I apologize if this is getting a bit off topic, is that you may consider that reading hashes from your data store should not be enabled from inside the same identity (e.g. web app) that is handling user input and performing the hash.

Instead, your data store would provide a stored procedure or equivalent to take in the candidate hash and return a bool, but disallow actually reading the stored hashes from that identity. I think you might see a lot less stolen hashes if the ability to dump the hashes from the data store remotely was more locked down.

Of course, this doesn't help much if you're, for example, running MongoDB with the latest remote code exploit! ;-) [CVE-2013-1892]

Thanks,
--Jeremy

On Mar 28, 2013, at 8:14 AM, "Dennis E. Hamilton" <dennis.hamilton@....org> wrote:

> As long as I'm making code samples, I should show how one needs to be careful when working in a programming language.  This can be superior:
> 
>  diff = 0;
>  for (i = 0; i < hash.length; i++)
>      {diff |= (hash[i] ^ key[i])}
>  return !diff;
> 
> where key is the stored hash to be matched.
> 
> This one depends on ^ and | operating in indistinguishable-from-constant time well below the noise by which the processor, run-time, and OS swamp any variation.  (Any variation for !diff doesn't matter of course.)  Again, it is all the more reason that there be a verification API behind which a platform-sensitive solution can be encapsulated.  
> 
> The slides linked by Jeremy are valuable in a very important way.  The discovery of even a bit is enough to break a security argument, even about the hash.  In this case, supporting Peter's argument, discovering leading bytes of the hash is providing a progressive narrowing of a search space as part of a dictionary attack using a compilation of known password-hash pairs.  Determined adversaries can find useful heuristics for accelerating discovery in this case.  And the work can be crowd-sourced, of course.  As usual, the weakness of the password is the lever.
> 
> Having said all of that, it also appears that the conditions under which the repetitive submissions of timed password tries goes undetected are rather contrived.  That does not mean the door should not be closed.  I think it is wise to assume that information disclosure is always a vulnerability that may become exploitable in some unforseen way.
> 
> - Dennis
> 
> -----Original Message-----
> From: Dennis E. Hamilton [mailto:dennis.hamilton@....org] 
> Sent: Thursday, March 28, 2013 00:04
> To: discussions@...sword-hashing.net
> Subject: RE: [PHC] Re: Suggestion: API should include a verifier function
> 
> The problem of the variable string comparison time in naïve hash-match checks is a good reason for the separate Verifier API that Tony suggested.
> 
> This problem and its solution is well-known and taught in introductory cryptography courses.  This is the simple example used to demonstrate timing attacks.  (E.g., in the Coursera Cryptography 1 course created by Dan Boneh.) I suppose this might have inspired some of the 100s of thousands who have taken such courses to try exploits.
> 
> The best way to ensure that the fixed-time solution is employed is to use a verifier API that does the comparison in constant time and simply reports pass or fail.  It also must compute the hash, and it is desirable that there be no exploitable variation there as well (given the particular set of fixed parameters).
> 
> This one is simple:
> 
>  good = true;
>  for (i = 0; i < hash.length; i++)
>       {good &= (hash[i] == key[i])}
>  return good;
> 
> The verifier must return only pass/fail and not differ in the (measurable) timing in reaching the different conclusions.  Even the above code might leak measurable information in an implementation. A platform-tuned verifier is where that can all be tuned away.
> 
> - Dennis
> 
> -----Original Message-----
> From: Jeremy Spilman [mailto:jeremy@...link.co] 
> Sent: Wednesday, March 27, 2013 21:21
> To: discussions@...sword-hashing.net
> Subject: Re: [PHC] Re: Suggestion: API should include a verifier function
> 
> LMGTFY: 
> http://www.security-assessment.com/files/documents/presentations/TimingAttackPresentation2012.pdf
> 
> -----Original Message----- 
> From: Peter Gutmann
> Sent: Wednesday, March 27, 2013 8:24 PM
> To: discussions@...sword-hashing.net
> Subject: Re: [PHC] Re: Suggestion: API should include a verifier function
> 
> Watson Ladd <watsonbladd@...il.com> writes:
> 
>> This isn't necessary: a non-constant time comparison at worst reveals the
>> hash, which doesn't give an attacker enough information to break a password
>> anyway if we do our jobs right.
> 
> Oh yes it can ;-).  There's a clever attack that was presented at Kiwicon 
> last
> year that turns timing attacks on hashed passwords into partial attacks on 
> the
> original passwords.  It'll appear in the Crypto Corner column of IEEE 
> Security
> and Privacy in (AFAIK) the next issue.
> 
> Peter. 
> 
> 

Powered by blists - more mailing lists