Subject: [Cfrg] [requesting suggestions] password hashing for PAKE

From: Yutaka OIWA <[email-masked]>
Date: Thu, 6 Mar 2014 02:11:18 +0900

Dear all in CFRG mailing list,

I want to have some suggestions about the use of strengthened password
hash for the PAKE family of protocols in reality.

As you know (better than me), "password" in cryptographic primitives
is just an element of some group, usually an integer element in a cyclic group.
In real world, "passwords" is just an octet string of unlimited, unfixed length.
So we need to convert the latter to the former.

We assume, hereafter, we use 256-bit hash, and some cyclic group Z/rZ
generated by 2047-bit prime r as a target group.

The simple way of doing that conversion is to apply an existing hash function.
To prevent off-line attacks from credentials stolen from server-side storage,
we suggested use of some existing password-strengthening hashes
such as PBKDF2 (RFC 2898), and are preparing to do so.
The usual hash produces an integer in [0, 2^256 - 1], and
PBKDF2 can produce some larger output like one in [0, 2^1792 - 1], but
what we want best is an integer uniformly distributed in range [0, r - 1].
(PBKDF2's output length is limited to the multiple of that of the base
hash function.)
So, how do you think what is the best tactics among below?

 1) PAKE allows non-uniform distribution of passwords, so
     just having 256-bit is fine.
 2) It's better do as long as possible with existing functions, so
have 1792 bit.
 3) We may introduce a small trick to PBKDF2 to produce 2046 bit (the
best integer).
 4) We should implement SOMETHING which will produce the best [0, r-1] range.

Especially for 4), do you have some suggestions for doing that?
Do you also have some recommendations for better alternatives other
than PBKDF2 for use with IETF experimental (or standard-track) documents?

Thanks a lot,

-- 
Yutaka OIWA, Ph.D.                 Leader, System Life-cycle Research Group
                               Research Institute for Secure Systems (RISEC)
     National Institute of Advanced Industrial Science and Technology (AIST)
                       Mail addresses: <[email-masked]>, <[email-masked]>
OpenPGP: id[440546B5] fp[7C9F 723A 7559 3246 229D  3139 8677 9BD2 4405 46B5]

---

From: Douglas Stebila <[email-masked]>
Date: Thu, 6 Mar 2014 07:38:28 +0000

Section B.5.1 of NIST SP 800-90A discusses different ways and relative merits of pseudorandomly generating integers in a range using a pseudorandom bit generator.  

I don't know enough about your protocol to know whether just using a 256-bit value is fine or whether you need a full-domain value, in some cases it can matter and in some cases it doesn't matter.  If you're not certain, it's probably safest to go with a full domain value.

As for PBKDF2's role in this, the PBKDF2 spec allows for variable (block) length output, basically by running multiple blocks of PBKDF2 with the same password/salt/iteration but the input concatenated with a counter for the block number.  Thus you can use standardized PBKDF2 to produce as many bits are required for the method you choose from B.5.1 of NIST SP 800-90A.

(My intuition is that PBKDF2's method for generating multiple block outputs is overkill: I think for hardening purposes it would suffice to generate a single block output key using PBKDF2 and then generating the desired variable length output using a non-hardened KDF from that single block key.  But since PBKDF2 does do variable length output itself, you might as well use that for compatibility.)

Douglas

On 2014/03/06, at 03:11, Yutaka OIWA <[email-masked]> wrote:

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