[cryptography] Master Password

Steven Bellovin smb at cs.columbia.edu
Thu Jun 7 17:14:34 EDT 2012

On May 31, 2012, at 3:03 PM, Marsh Ray wrote:

> On 05/31/2012 11:28 AM, Nico Williams wrote:
>> Yes, but note that one could address that with some assumptions, and
>> with some techniques that one would reject when making a better hash
>> -- the point is to be slow,
> More precisely, the point is to take a tunable amount of time with strong assurance that an attacker will be unable to perform the computation with significantly less computational resources.
> The deliberate consumption of computational resources is a price that the defender has to pay in order to impose costs on the attacker. This ought to be an advantageous strategy for the defender as long as the attacker is expected to need to invoke the function many times more.
> But the defender's and attacker's cost structure is usually very different. The defender (say a website with a farm of PHP servers) doesn't get to choose when to begin the computation (legitimate users can log in at any time) and he pays a cost for noticeable latency and server resources.
> The attacker costs are proportional to the number of guesses he needs to make to reverse the password. Hopefully this is dominated by wrong guesses. But the attacker is free to parallelize the computation across whatever specialized hardware he can assemble in the time that the credentials are valid (sometimes years). Some attackers could be using stolen resources (e.g. botnets for which they do not pay the power bill).

There's another, completely different issue: does the attacker want a particular password, or will any passwords from a large set suffice?  

Given the availability of cheap cloud computing, botnets, GPUs, and botnets with GPUs, Aa * Ah * Ap can be very, very high, i.e., the attacker has a strong advantage when attacking a particular password.  Some say that it's so high that increasing Ad is essentially meaningless.  On the other hand, if there are many passwords in the set being attacked, a large Ad translates into a reduction in the fraction that can be attack in any given time frame.

		--Steve Bellovin, https://www.cs.columbia.edu/~smb

More information about the cryptography mailing list