Subject: [IPsec] Puzzle algorithm negotiation

From: Yoav Nir <[email-masked]>
Date: Sun, 18 Jan 2015 17:39:04 +0200

Pull Request: https://github.com/ietf-ipsecme/drafts/pull/2 <https://github.com/ietf-ipsecme/drafts/pull/2>

Hi,

Valery has created this pull request. During the meeting in Honolulu and subsequent discussion on the list, several people requested that there be a negotiation of the algorithm used in the puzzle rather than fixing it to SHA-256.

The pull request suggests figuring out which algorithms the Initiator supports by examining the SA payload in the IKE_SA_INIT request, and using the PRF algorithms.

I’m posting this to the list, even thought we’re not sure about this. Specifically, PRF_AES128_XCBC and (I think) PRF_AES128_CMAC won’t work with the bitcoin-like puzzle that is currently in the draft.

Why?

For convenience assume a 16-byte cookie, a fixed zero IV (as always in AES-XCBC) and fixed zero key.

So let Y = AESENC(key, IV XOR COOKIE) = AESENC(zero, COOKIE)
Let Z = AESDEC(key, zero) = AESDEC(zero, zero)
Extend the cookie by Y XOR Z.

The result will give you a 128-bit tag of all zeros. Way too easy.

Another way to do this is to add a notification in the Initiator’s request listing the hash algorithms that it supports. We could reuse the RFC 7427 registry of hash algorithms. 

Personally, I really don’t like this algorithm agility, because we don’t want to give the Initiator the options of a hard vs easy puzzle. So suppose the Responder supports two algorithms, SHA-256 and SHA-512, and that the latter is half as fast as the former, then a SHA-512 puzzle would have to have 1 bit less than the SHA-256 puzzle. But in fact, we know that SHA-512 is faster on 64-bit platforms, while SHA-256 is faster on 32-bit platforms. Add some GOST-certified hash to the mix, and the administrator’s task becomes that much harder. OTOH often when a protocol is published without algorithm agility, we end up extending it later.

Yoav

---

From: "Valery Smyslov" <[email-masked]>
Date: Mon, 19 Jan 2015 11:02:31 +0300

Hi Yoav,
  Pull Request: https://github.com/ietf-ipsecme/drafts/pull/2

  Hi,

  Why?

  The result will give you a 128-bit tag of all zeros. Way too easy.
You forgot about the mandatory 10* padding in AES-XCBC.
So, the result of AESDEC(zero, zero) should not be a random
string, but should look like properly padded one.

But anyway, I think that if we use PRF for puzzles, then the puzzle definition should be changed.

Let R=PRF(K,S). Then the puzzle should be: using supplied cookie as message S,
find a key K so, that result R contains the requested number of trailing zero bits.

I'm not a cryptographer, but I think this variant of puzzle should be secure
for all PRFs, defined in IPsec. Why? First, every secure PRF is a secure MAC 
(not visa versa). This is pointed out by several sources. Then, secure MAC
should not allow attacker to recover a key given the message and
the authentication tag. In our case the authentication tag is not fully given,
but it must have some properties (desired number of trailing zero bits),
so it is not arbitrary.
  Another way to do this is to add a notification in the Initiator’s request listing the hash algorithms that it supports. We could reuse the RFC 7427 registry of hash algorithms. 
I don't think this is a good idea. First, it will require initiator to include 
a list of supported hash algorithms into request message. This will 
unnecessary increase its size in all cases: at this point initiator
has no idea whether responder will ever use puzzles or even
whether it supports them. I think this is a waste of resources,
especially taking into consideration that we may reuse 
information, that is always present in the request message.
  Personally, I really don’t like this algorithm agility, because we don’t want to give the Initiator the options of a hard vs easy puzzle. So suppose the Responder supports two algorithms, SHA-256 and SHA-512, and that the latter is half as fast as the former, then a SHA-512 puzzle would have to have 1 bit less than the SHA-256 puzzle. But in fact, we know that SHA-512 is faster on 64-bit platforms, while SHA-256 is faster on 32-bit platforms. Add some GOST-certified hash to the mix, and the administrator’s task becomes that much harder. 
If the difference in algorithms speeds is significant, then some weights could be
added to algorithm definitions to make the required time to solve puzzle roughly the same
on the same platform.
  OTOH often when a protocol is published without algorithm agility, we end up extending it later.
Exactly.
  Yoav
Regards,
Valery.

---

From: Yaron Sheffer <[email-masked]>
Date: Sun, 25 Jan 2015 10:58:16 -0800

Hi Yoav, Valery,

I agree with Valery's proposed redefinition of the proof-work-work, 
based on the PRF.

I am currently off-line so my question may have been answered in the 
pull request, but: can we make it very clear that the PRF used for the 
POW must be the very same as the one selected by the responder for the 
IKE SA?

People may not like it (I don't) but a major reason for including 
agility today is FIPS silliness. One day people will be forced to rip 
out any mention of SHA-256 from their code, and we don't want to need to 
reopen the RFC.

Thanks,
	Yaron

On 01/19/2015 12:02 AM, Valery Smyslov wrote:
>     Valery has created this pull request. During the meeting in Honolulu
>     and subsequent discussion on the list, several people requested that
>     there be a negotiation of the algorithm used in the puzzle rather
>     than fixing it to SHA-256.
>
>     The pull request suggests figuring out which algorithms the
>     Initiator supports by examining the SA payload in the IKE_SA_INIT
>     request, and using the PRF algorithms.
>
>     I’m posting this to the list, even thought we’re not sure about
>     this. Specifically, PRF_AES128_XCBC and (I think) PRF_AES128_CMAC
>     won’t work with the bitcoin-like puzzle that is currently in the draft.
>
>     Why?
>
>     Another way to do this is to add a notification in the Initiator’s
>     request listing the hash algorithms that it supports. We could reuse
>     the RFC 7427 registry of hash algorithms.
>
>     Personally, I really don’t like this algorithm agility, because we
>     don’t want to give the Initiator the options of a hard vs easy
>     puzzle. So suppose the Responder supports two algorithms, SHA-256
>     and SHA-512, and that the latter is half as fast as the former, then
>     a SHA-512 puzzle would have to have 1 bit less than the SHA-256
>     puzzle. But in fact, we know that SHA-512 is faster on 64-bit
>     platforms, while SHA-256 is faster on 32-bit platforms. Add some
>     GOST-certified hash to the mix, and the administrator’s task becomes
>     that much harder.
>
> _______________________________________________
> IPsec mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ipsec
>

---

From: Yoav Nir <[email-masked]>
Date: Mon, 26 Jan 2015 06:52:32 +0200

> On Jan 25, 2015, at 8:58 PM, Yaron Sheffer <[email-masked]> wrote:
> 
> Hi Yoav, Valery,
> 
> I agree with Valery's proposed redefinition of the proof-work-work, based on the PRF.
> 
> I am currently off-line so my question may have been answered in the pull request, but: can we make it very clear that the PRF used for the POW must be the very same as the one selected by the responder for the IKE SA?

It is possible, but I don’t see why it’s a good thing. Suppose the conversation goes like this:

Initiator: I want (AES-CBC-128 or AES-CBC-256) with (AUTH_HMAC-SHA1 or AUTH_HMAC-SHA256) and (PRF_ HMAC-SHA1 or PRF_HMAC-SHA256) and (Group 2 or Group 14)

Responder: First do proof-of-work with PRF_HMAC-SHA256

Initiator: Here’s the proof-of-work, now I want (AES-CBC-128 or AES-CBC-256) with (AUTH_HMAC-SHA1 or AUTH_HMAC-SHA256) and (PRF_ HMAC-SHA1 or PRF_HMAC-SHA256) and (Group 2 or Group 14).

Responder: Fine, I choose AES-CBC-128 with HMAC-SHA1 and PRF_HMAC-SHA1 and Group 2.

What is the benefit of forcing the responder to choose the same PRF algorithm twice? What is wrong with having it choose PRF_HMAC-SHA1?  Sure, we *can* do this, but why?

> People may not like it (I don't) but a major reason for including agility today is FIPS silliness. One day people will be forced to rip out any mention of SHA-256 from their code, and we don't want to need to reopen the RFC.

Some algorithms are also more fashionable than others.

Yoav

---

From: Yaron Sheffer <[email-masked]>
Date: Mon, 26 Jan 2015 11:34:36 +0200

I thought fixing the PRF would simplify the implementation, but now I 
realize that it wouldn't.

Thanks,
	Yaron