Subject: [Cfrg] PRF in draft-nir-cfrg-chacha20-poly1305

From: Yoav Nir <[email-masked]>
Date: Mon, 12 May 2014 17:50:17 +0300

Hi

Section 2.7 of our draft ([1]) discusses PRF functions. While these are not needed as part of ciphersuites in TLS, IKE does need one to be specified. A PRF function as described in IKE takes a key and an arbitrary length value, and returns a fixed-length value. IKE’s KDF (“PRF+” - [2]) is constructed by repeatedly running the PRF. 

Many implementations don’t have a separate configuration UI for PRF and MAC, because they’re pretty much the same algorithm, so PRF_HMAC_SHA1 goes with AUTH_HMAC_SHA1.

So I would like to have a PRF function that is based on ChaCha20, Poly1305, or a combination of them.  An obvious way to do this would be as follows:

If the key size is not 32-octet, run Poly1305 on it with a fixed key (to be determined what we would like that to be, but zero definitely doesn’t work) and use that as the key.
Use the key in Poly1305 on the input.

Going over the IKE spec, prf and prf+ are used several times:
In generating SKEYSEED where the key is a concatenation of nonces.
In generating the IKE SA keying material, where the key is SKEYSEED
As part of the signed material (not transmitted) where the key is part of the IKE SA keying material
In computing a PRF key for shared secret authentication, where the key is the shared secret (so it’s constant for a pair of hosts)
In computing the shared secret authenticator, and as we’ve said, the key is always the same, but the data is not known to the attacker.
In generating key material for ESP or AH, where the key is SK_d (part of the IKE SA keying material) is used.

So this doesn’t fit the requirements in DJB’s papers that the keys should be unique (actually that the nonces fed to the encryption function that is used to generate the key should be unique).  On the other hand, this is a PRF, not an authentication function, and the results are not transmitted. So I’m wondering if this is OK for a PRF, or if this can be tweaked somehow to make it OK. The current text recommends using something else such as HMAC-SHA-256, and if that’s the best we can do, I’ll recommend HMAC-SHA-256 as the PRF to use in my IPsec draft.

Thanks

Yoav

[1] http://tools.ietf.org/html/draft-nir-cfrg-chacha20-poly1305-03#section-2.7
[2] 
   prf+ (K,S) = T1 | T2 | T3 | T4 | ...

   where:
   T1 = prf (K, S | 0x01)
   T2 = prf (K, T1 | S | 0x02)
   T3 = prf (K, T2 | S | 0x03)
   T4 = prf (K, T3 | S | 0x04)
   ...

---

From: Robert Ransom <[email-masked]>
Date: Mon, 12 May 2014 10:51:59 -0700

On 5/12/14, Yoav Nir <[email-masked]> wrote:

> So I would like to have a PRF function that is based on ChaCha20, Poly1305,
> or a combination of them.  An obvious way to do this would be as follows:
>
> If the key size is not 32-octet, run Poly1305 on it with a fixed key (to be
> determined what we would like that to be, but zero definitely doesn’t work)
> and use that as the key.

DO NOT use Poly1305 as a PRF.

ChaCha is a (16-byte input to 64-byte output) PRF.  Poly1305 is not
even close to a PRF.

Robert Ransom

---

From: "Dan Harkins" <[email-masked]>
Date: Mon, 12 May 2014 11:27:27 -0700 (PDT)

Hi Yoav,

On Mon, May 12, 2014 7:50 am, Yoav Nir wrote:
[snip]
> In computing a PRF key for shared secret authentication, where the key is
> the shared secret (so it’s constant for a pair of hosts)
> In computing the shared secret authenticator, and as we’ve said, the key
> is always the same, but the data is not known to the attacker.
> So this doesn’t fit the requirements in DJB’s papers that the keys should
> be unique (actually that the nonces fed to the encryption function that is
> used to generate the key should be unique).  On the other hand, this is a
> PRF, not an authentication function, and the results are not transmitted.
> So I’m wondering if this is OK for a PRF, or if this can be tweaked
> somehow to make it OK. The current text recommends using something else
> such as HMAC-SHA-256, and if that’s the best we can do, I’ll recommend
> HMAC-SHA-256 as the PRF to use in my IPsec draft.

  The "extract and expand" KDF in RFC 5869 is a much more formal version
of IKE's PRF and PRF+ and would recommend using it instead. The nonces
end up being salt to the "extract" portion of the KDF.

  regards,

  Dan.

---

From: Yoav Nir <[email-masked]>
Date: Mon, 12 May 2014 22:32:39 +0300

> ChaCha is a (16-byte input to 64-byte output) PRF.  Poly1305 is not

Hi, Robert

I agree that ChaCha is a good PRF, but IKE requires the PRF function to accept both a variable length key and variable length data. ChaCha can turn a key plus a nonce into an arbitrary-length stream, so it’s a good replacement for PRF+, but when specifying algorithms for IKE, I can’t replace PRF+, just the PRF building block.

So far it looks to me like we don’t have a suitable replacement for HMAC.

Yoav

---

From: Yoav Nir <[email-masked]>
Date: Mon, 12 May 2014 22:36:50 +0300

> end up being salt to the "extract" portion of the KDF.

Thanks. You’re right about that, and the new IKEv2 spec could have referenced RFC 5860. I guess it’s too late now.

But re-writing IKEv2 is not part of *this* effort. It looks like we’ll have to keep relying on some HMAC.

Yoav

---

From: James Cloos <[email-masked]>
Date: Tue, 13 May 2014 13:07:49 -0400

>>>>> "YN" == Yoav Nir <[email-masked]> writes:

YN> So I would like to have a PRF function that is based on ChaCha20,
YN> Poly1305, or a combination of them.

Perhaps, then, an hmac or umac based on blake?

-JimC
--
James Cloos <[email-masked]>         OpenPGP: 0x997A9F17ED7DAEA6

---

From: Alyssa Rowan <[email-masked]>
Date: Tue, 13 May 2014 20:11:09 +0100

On 13/05/2014 18:07, James Cloos wrote:

>> So I would like to have a PRF function that is based on
>> ChaCha20, Poly1305, or a combination of them.

Hmm. Nice. Seems like a natural choice to me for those that prefer to
avoid NIST's choices, especially given BLAKE's high performance, high
security margin, SHA-3 finalist status, and its similarity to ChaCha.

Using BLAKE as a hash to round out the non-NIST crypto primitives set
seems reasonable to me.

- -- 
/akr

---

From: Watson Ladd <[email-masked]>
Date: Tue, 13 May 2014 12:54:20 -0700

Resend to right people this time.

On May 13, 2014 11:00 AM, "Watson Ladd" <[email-masked]> wrote:
>
>
> On May 13, 2014 10:14 AM, "James Cloos" <[email-masked]> wrote:
> >
> Why does the PRF need to be connected to the MAC? What's wrong with
SHA256?  TLS does exactly this for Suite B modes.
> Sincerely,
> Watson Ladd
> > _______________________________________________
> > Cfrg mailing list
> > [email-masked]
> > http://www.irtf.org/mailman/listinfo/cfrg

---

From: Alyssa Rowan <[email-masked]>
Date: Tue, 13 May 2014 21:24:57 +0100

On 13/05/2014 20:54, Watson Ladd wrote:

> What's wrong with SHA256?

Nothing much for this, as far as I know? So I think the question is
more: can we do better; do we need to?

BLAKE might be a bit faster (BLAKE2b especially so, at the cost of a
slice of security margin). But does the speed of the IKE PRF really
have any great impact on IPsec performance? Maybe not.

There's one obvious - albeit entirely non-technical - reason: those
preferring to avoid NIST-approved algorithms in general may also
prefer to avoid SHA-256, purely given where it comes from (even if we
know of nothing particularly technically wrong with it).

Other than that, it looks kinda like a 'newer' vs. 'weathered' choice
to me.

- -- 
/akr

---

From: Yoav Nir <[email-masked]>
Date: Wed, 14 May 2014 09:28:49 +0300

On May 13, 2014, at 11:24 PM, Alyssa Rowan <[email-masked]> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
> 

I guess I would answer these probably, and probably not.

> have any great impact on IPsec performance? Maybe not.

Highly-loaded VPN gateways run the PRF function dozens to a few hundreds of times a second. AES or ChaCha keys are good for several hours, so you’d need millions of tunnels to break into the “hundreds of times per second”  territory. My lowly laptop can do over a million HMAC-SHA-256 operations per second. I don’t think any IKE implementation is stuck on PRF.

I don’t think any crypto library today can entirely forego SHA-256. So specifying BLAKE would mean requiring yet another primitive in the library. I don’t think we have a good enough justification for this.

> know of nothing particularly technically wrong with it).

I think people are somewhat suspicious of NIST curves, because of the “here are some numbers. use these.” thing, but SHA-256 doesn’t have as much opportunity for “play” (as far as we know). I don’t see much objection in TLS for using SHA-256 in every legacy ciphersuite.

> Other than that, it looks kinda like a 'newer' vs. 'weathered' choice

Unfortunately, age is not a good indicator for how soon an algorithm will be broken.

Yoav