3
$\begingroup$

I'm working on an implementation of Krawczyk's Hashed MQV (HMQV). I'm using Crypto++, which is a C++ library.

C++ has some features where classes that represent the crypto objects can be combined even if they don't have matching security levels. As an extreme example, imagine a P-160 curve is coupled with SHA-512. Or imagine B-571 coupled with MD5.

In the case where the field size and hash size are disjoint, which should I prefer when implementing the protocol? Should everything be based on the field (and field elements) sizes effectively using truncated hashes? Or should it be vice-versa? Vice-versa would include the field size being larger than the hash, with the values being 0-filled at the MSB as required.


I should also qualify the question with: there is no standardization of the protocol, and there is no reference implementation. The protocol is often only described in a paper. This issue shows up more often than it should. Its one of the differences between theoretical and practical crypto.

$\endgroup$
2
  • $\begingroup$ I disagree with the standardization/difference between theoretical and practical crypto. MQV was standardized in IEEE P1363, and there has been an attempt made to also have HMQV included. I can't seem to quickly find what came out, but it does imply the information you are looking for is out there. IEEE P1363 reference: en.wikipedia.org/wiki/IEEE_P1363 Proposal to add HMQV: grouper.ieee.org/groups/1363/P1363-Reaffirm/submissions/… $\endgroup$
    – user4621
    Jul 20 '15 at 18:42
  • $\begingroup$ Note that both MQV and HMQV are patented. $\endgroup$
    – user4621
    Jul 24 '15 at 12:21
4
$\begingroup$

MQV has been standardized by IEEE P1363 (specified in P1363 2000, and amended in P1363a 2004), but it does not involve hashing, and therefore can't provide an answer to the OP's question. HMQV standardization proposal has been submitted to IEEE, but it does not contain the specific details that @jww is asking for. I went through the relevant P1363 docs and have not found answers to the @jww's questions. If you think that those details (acceptable hash functions for HMQV, mapping between them and the allowed curves, method of conflict resolution if hash output size is greater or smaller than L) are provided there (and I just missed them) - please be so kind and post the exact reference (document name/number and the page number) here.

Now, since I did want to find the answer, and since Hugo Krawchyk is the author of HMQV, it seemed best to ask him directly. Here's what Hugo replied:

I assume the question refers to the hashing that results in the values d and e.

Let L denote log_2(q) where q is the order of the group.

There are two choices for the length of d and e. They may be of full length L in which case I would take the output of the hash and reduce it mod q (resolving the issue of longer hash values, but truncation to L bits would also work). Or, you can follow the optimization used in the HMQV paper where e and d are of length L/2, in this case the hash value is to be truncated to L/2 bits.

I would note that this L/2 optimization does not buy you anything if you optimize the multi-exponentiation to compute sigma in HMQV. Such optimized multi-exponentiation will cost the equivalent of 1.16 exponentiations even with a full size (i.e., L) values d and e. In this case I would not recommend using L/2 length for d and e but rather the full size L.

If the length of the hash is less than L but more than L/2 you can just use the output as is for the values d and e. But I would not recommend to use a hash function with less than L bits of output and definitely not one with less than L/2.

Hope this answers the question.

From the above I conclude:

  • In your C++ code use the field element size (or rather the order of the group) as the decisive factor, and match/measure the supplied hash function against it.
  • If the hash output size that your caller provided is at least as big as L, use it and truncate its output if/when needed.
  • If the hash output size is less that L, probably still allow it (maybe the caller did know what he's doing) as long as it is greater than L/2.
  • If the supplied hash is smaller than (or equal to) L/2, refuse to instantiate the object and throw an exception.

This approach should apply to FHMQV as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy