Message-ID: <008801ce96c3$dc4b13e0$94e13ba0$@acm.org>
Date: Sun, 11 Aug 2013 11:51:58 -0700
From: "Dennis E. Hamilton" <dennis.hamilton@....org>
To: <discussions@...sword-hashing.net>
Subject: Interdependence of t_cost and m_cost parameters

I'm always having difficulty understanding the interdependence that might exist between t_cost, m_cost and, to a related degree, also outlen.  

Here are some considerations I have.  I don't know how these fit with what others assume the interdependencies might be, or whether the interdependencies are simply left wide open, including when and where step functions arise.

 - Dennis

MY APPRAISAL OF THE SITUATION:

It is generally easy to have t_cost be directly related to a linear work factor apart from any step functions that may arise in conjunction with outlen.  Alternatively, a PHS could amortize t_cost when there is some outlen-related timing-step increase.  There is such an increase with PBKDF2, for example.  While the t_cost doesn't have to adjust for differences in terms of processor performance, it would be useful to have the effect be smooth, whatever the relationship is.

Amortizing t_cost against m_cost is tricker.  That is, it is difficult to work out the combinations if m_cost also has step-function costs.  It is also not clear what the difference between m_cost 1 and m_cost 2 might be and whether a given implementation has step functions here too (in which case t_cost could be amortized once again).

Note 1: I am also assuming that, whatever the m_cost is, with the other parameters fixed, the result should be cryptographically unrelated to a result produced for any other m_cost value.  The prospect of t_cost, m_cost password-hash collisions with all other parameters the same must be negligible.

Note 2: A requirement that I have for iterative password-hashing procedures is that I can have a version that will operate with a specific time threshhold and then report the t_cost that was achieved along with the resulting hash.  That becomes the known t_cost value for verification.  I've not considered m_cost in practical cases that have come up.  (Given a threshold t in milliseconds, the resulting t_cost
value is one for which the hash is produced in the approximate interval [t, 3t/2].)

Note 3: If I wanted variable m_cost control, I'm thinking that the procedure in (Note 2) would take an m_cost suggestion and that procedure would deliver the t_cost and m_cost values that were used in a generation that satisfied the specified time threshold.  That seems definitely trickier.  Interesting, but trickier.  

-----Original Message-----
From: Jean-Philippe Aumasson [mailto:jeanphilippe.aumasson@...il.com] 
Sent: Monday, February 18, 2013 22:48
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Q: Reference t_cost and m_cost parameters

On Mon, Feb 18, 2013 at 10:48 PM, Solar Designer <solar@...nwall.com> wrote:
> On Mon, Feb 18, 2013 at 11:23:16AM -0800, Dennis E. Hamilton wrote:
>> For the candidate reference-implementation API, the t_cost and m_cost
>> parameters are apparently unitless values related to time cost and space
>> (memory cost).
>>
>> Is there some standard definition for these, so that one can substitute
>> implementations but not need to know the implementation to know the
>> consequences?
>>
>> Or is it presumed that a candidate specify how these are interpreted
>
> I think it's the latter.
>

It is: for example m_cost=2 does not mean "2 megabytes", t_cost=100
does not (and cannot) mean "100 cpu cycles", etc.

t_cost and m_cost may (and will probably) accept different ranges of
values for different submissions. We did not want to impose a specific
range, as it would have restricted designers (although any countable
range can be mapped to [0;1], though with limited precision).

>
>> By fixed I mean that the salt and the cost parameters would be either stored
>> or otherwise preserved between creation of a hash and recomputation of the
>> hash for authentication of a password.
>
> Oh, that's a different aspect from what you wrote in the previous few
> paragraphs.  Yes, it is expected that the parameter values, except for
> secrets, will be stored along with the hashes or with the encrypted
> data (if the scheme is used as a KDF).  This is beyond scope of PHC,
> although we may discuss it in here.
>

That's also my understanding.

Powered by blists - more mailing lists