Re: [IPsec] Puzzle algorithm negotiation

["Valery Smyslov" <[e-mail]>]

Hi Yoav,
  Pull Request: 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.
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.