Subject: [Cfrg] Key-Derivation Scheme

From: Rifaat Shekh-Yusef <[email-masked]>
Date: Wed, 14 May 2014 08:46:55 -0400

Hi,

This is to continue the Key-Derivation Scheme discussion started on the
SAAG mailing list:
http://www.ietf.org/mail-archive/web/saag/current/msg04964.html

Attached is an updated version of the draft based on the feedback on the
SAAG mailing list.

There are two major changes to the initial draft:

1.  Use of the Scrypt function, instead of PBKDF2 function
2.  Mutual authentication, instead of client authentication only.

I would appreciate any comments on this new version of the draft.

Regards,
 Rifaat

---

From: Alex Elsayed <[email-masked]>
Date: Wed, 14 May 2014 10:46:49 -0700

> I would appreciate any comments on this new version of the draft.

Scrypt's primary gain over PBKDF2 is that it's a memory-hard function - 
however, experience with e.g. Litecoin shows that Scrypt in particular is 
subject to some time-memory tradeoff behaviors that may not be ideal.

I'd like to refer anyone interested in this to the Password Hashing 
Competition (and the mailing list + archives thereof), which has also 
discussed that 'suitability for use as a KDF' is both an important point to 
consider in their selection process (as the submissions phase has ended), as 
well as not necessarily following from the definition of a memory-hard one-
way function.

The goal of the PHC is to select a strong password-hashing function that 
will (hopefully) stand the test of time, and the submissions cover the gamut 
of memory-hardness, cache-timing attack resistance, resistance to 
time/memory tradeoff attacks, avoidance of conditional branches, dependent 
accesses to prevent pipelining (penalizing systems with high-latency memory 
like GPUs), etc.

(Interestingly, one thing that showed up is that there seems to be an 
inherent tradeoff between avoiding cache-timing attacks and preventing 
pipelining. While it's not yet shown to hold in all cases, no 
counterexamples have been found either)

---

From: Rifaat Shekh-Yusef <[email-masked]>
Date: Thu, 15 May 2014 08:09:34 -0400

Thanks Alex,

Do you have more details about that experience with Litecoin?

Regards,
 Rifaat

On Wed, May 14, 2014 at 1:46 PM, Alex Elsayed <[email-masked]> wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Alex Elsayed <[email-masked]>
Date: Fri, 16 May 2014 10:36:02 -0700

First, I feel a need to correct myself to some degree - a large part of the 
issue with Litecoin is their _usage_ of scrypt - they set the memory 
parameter lower than they should have.

However, even other systems that use better parameters are affected by the 
fact that reducing the size of the scratchpad to half reduces performance by 
noticeably less than half. On memory-bound (either size or latency) hardware 
(GPUs, etc) this permits doubling the parallelism without doubling the time 
for each candidate, achieving a greater number of attempts/time. Since 
computing large numbers of candidates in parallel is much more benefit to 
the attacker than the defender, this is a suboptimal behavior.

Since Litecoin explicitly used scrypt to make GPU-mining less competitive 
with CPU-mining, this was understandably unpleasant to discover - especially 
when the low memory parameter left the equation such that GPUs with that 
optimization did significantly beat CPU-mining.

The PHC does include one submission directly based upon Scrypt. The 
submission 'yescrypt', by SolarDesigner (Alexander Peslyak), works to 
address the issues in Scrypt, and is seen as a strong contender.

Rifaat Shekh-Yusef wrote:

>> > Attached is an updated version of the draft based on the feedback on
>> > the SAAG mailing list.
>> >
>> discussed that 'suitability for use as a KDF' is both an important point
>> to consider in their selection process (as the submissions phase has
>> ended), as
>> well as not necessarily following from the definition of a memory-hard
>> one- way function.
>>
>> time/memory tradeoff attacks, avoidance of conditional branches,
>> dependent accesses to prevent pipelining (penalizing systems with
>> high-latency memory like GPUs), etc.
>>

---

From: Sandy Harris <[email-masked]>
Date: Tue, 27 May 2014 22:57:01 -0400

On Wed, May 14, 2014 at 8:46 AM, Rifaat Shekh-Yusef
<[email-masked]> wrote:

> This is to continue the Key-Derivation Scheme discussion ...
>
> Attached is an updated version of the draft ...

The draft has:

" While cannot be used directly as cryptographic keys, the
" passwords can still be used to derive cryptographic keys,
" by using Key Derivation Function (KDF).

I think the basic notion of using a KDF at all -- rather
than Diffie-Hellman key negotiation with the password
used for authentication -- needs to be justified here.

I'm not certain it can be, but the draft should attempt
it.

---

From: Rifaat Shekh-Yusef <[email-masked]>
Date: Wed, 28 May 2014 08:32:39 -0400

Hi Sandy,

Thanks for your comment.

The main reason for using a KDF-based algorithm (PBKDF2, scrypt, ...) is to
make it much more expensive to recover the password in clear-text if the
passwords database is compromised.
We could use a combination of a KDF-based algorithm with another algorithm,
like the following proposal:
http://www.ietf.org/mail-archive/web/cfrg/current/msg04523.html

Does that address your comment?

Regards,
 Rifaat

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 28 May 2014 09:38:48 -0700 (PDT)

Hi Rifaat,

> Does that address your comment?

  It sort of begs the question. In your draft you say:

    "The Key-Derivation scheme ensures that the password and the master-
     key are never sent on the wire, and allows for a better secure
     storage of passwords, as it significantly increases the amount of
     computation needed to derive a key from a password in a dictionary
     attack."

While the password will not be sent over the wire, password-derived
data wil and that enables the dictionary attack. Yes, PBKDF2 will increase
the amount of computation needed to derive a key but that becomes
more an more trivial every year thanks to Moore's Law.

  PBKDF2 is used by WPS-PSK, a password-authenticated key exchange
for wireless network access. The password is never sent over the ether
yet tools exist that can crack the password used in the WPS-PSK exchange
in a matter of minutes to hours depending on the level of hardware thrown
at the problem. There are also sites on the Internet that, for a small
fee, will
crack the password for you if you give them the exchange (that did not
contain the password) that crossed the ether. Obviously, the protection
afforded by PBKDF2 is not much and getting smaller.

  A much better solution to your problem is to use a password-authenticated
key exchange based on a zero knowledge proof. That way, not only does
the password not cross the wire/ether, neither does password-derived
data.

  In the message you refer to above you incorporate your scheme
with a PAKE. Which begs the question, what is your justification for this
since the password is already not crossing with wire/ether before you
added PBKDF2? A proper augmented PAKE will provide suitable resistance
to dictionary attack in the event of database compromise so, again,
what's the point of this KDF?

  regards,

  Dan.

---

From: Rifaat Shekh-Yusef <[email-masked]>
Date: Thu, 29 May 2014 08:11:54 -0400

Hi Dan,

Thanks for your comments.
Please, see my reply inline...

Regards,
 Rifaat

On Wed, May 28, 2014 at 12:38 PM, Dan Harkins <[email-masked]> wrote:

> data will and that enables the dictionary attack.

Just to be accurate here, the password will be used to derive a master-key;
the master-key will then be used to hash the data.
Since I am not a cryptographer, I do not know if this difference is
significant or not.

> Yes, PBKDF2 will increase

That depends on the number of iterations and the HMAC-Hash function
selected by the server, and these could be adjusted when needed.
 I used PBKDF2 as an example, but other algorithms, like Scrypt, could be
used instead.

> afforded by PBKDF2 is not much and getting smaller.
Do you know the number of iterations and the HMAC-Hash function used with
WPS-PSK?

> the password not cross the wire/ether, neither does password-derived
Agree.

> what's the point of this KDF?
As I mentioned earlier, a KDF-based algorithm is controlled through the
number of iterations used by the algorithm, and by the HMAC-Hash function.
This flexibility allows the system to select the level of protection
required based on the system's needs.

Now, are you saying that instead of storing the master-key created based on
the KDF-based algorithm, the server should store the shared-secret created
by the JPAKE protocol? and
if the database is compromised, the computation needed by the attacker to
recover the clear-text password from the shared-secret will always be much
higher than the computation needed in the case of the master-key?

Regards,
 Rifaat