Re: [Cfrg] Key establishment advice (say, for TLS): How about MQV?

[Watson Ladd <[e-mail]>]

On Thu, Mar 6, 2014 at 8:27 AM, Hugo Krawczyk <[e-mail]>wrote:

> A clarification on my previous email:
>
>
> > There has been some contention about the need to do group membership
> tests in
> > HMQV. Indeed, the need for this depends on the use case and security
> model.
> > However, this issue is relevant for mod p groups where such tests are
> expensive.
> > For elliptic curves the test is inexpensive hence can be made an
> integral part
> > of the protocol.
>
> The group membership test would be performed by the parties in the
> protocol, not by the CA. It would be applied to a single element that
> combines the static and ephemeral values (in the HMQV paper notation Alice
> applies the test to  YB^e and Bob to XA^e). The part of the test checking
> the order of these elements is needed in two cases: for the one-pass
> variant of the protocol and to achieve security in case of compromise of
> the ephemeral exponents (x and y in HMQV notation). The latter makes sense
> in settings where the long-term keys are better protected than the
> ephemeral exponents. But as said, in the EC setting the group membership
> test, including testing the order, is inexpensive so it makes sense to
> always perform it.
>

I don't think that's right. To check that P is in E[N], one has to
calculate [N] unless there is a method I don't know about. What does
suffice (I think) is to check that (YB^e)^h is not the identity and use
that as a key: even if one plays fun and games with group element
representations, contributory behaviour is still ensured as the cofactor
annihilates E_p/E[N] by definition.

The difference is one full exponentiation vs. four doublings if the
cofactor is 16. I think these are bisimulatable protocols as 16 is
invertible mod N, so we haven't changed anything in E[N].

One always does on-curve checks, or uses point compression to avoid them,
or the Montgomery ladder on twist secure curves.

Thank you once again for contributing your knowledge to our efforts.

>
> If one wanted to use HMQV in the IETF, a full detailed spec would be
> required of the type written for the mod p groups in P1363. But there is no
> point in doing it as long as the patent issues stand in the way of
> standardization.
>

SM2 is already quite similar and has been written up already. However, it's
not quite as well studied/is MQV. The alternative is signed diffie-hellman
exchanges, but the details are fiddly and need to be gotten exactly
correct, and I've not figured out one flow that works for everything. As
for the patent that will really come down to IBM and whether they want to
get the speed gains from HMQV, and in exchange let us use the patent for
IETF protocols.

Sincerely,
Watson Ladd

>
> Hugo
>
>
>
> On Wed, Mar 5, 2014 at 11:45 PM, Hugo Krawczyk <[e-mail]>wrote:
>
>>  ​A few notes on the potential use of HMQV for TLS.
>>
>> I do believe that HMQV could be a good basis for TLS 3.0 due to its
>> efficiency,
>> versatility, and proof of security (I comment a bit on these aspects
>> below).
>> But given the patent issues surrounding the protocol I doubt it would be
>> feasible to get this standardized by the IETF. As I understand, Certicom
>> has
>> some claims on the MQV protocol and IBM has a patent on HMQV.
>>
>> HMQV gives an authenticated DH exchange *at essentially the cost of
>> plain DH*
>> (plus certificate verification) and can support "seamlessly" several
>> functional
>> variants: from implicit mutual or unilateral authentication to explicit
>> authentication with key confirmation to a single message key exchange with
>> unilateral or mutual authentication. The latter mode is particularly well
>> suited
>> as a one-message key exchange of the type I've seen in some "TLS 3.0"
>> proposals
>> (which assume some form of anti-replay state) and has the advantage of
>> optionally accommodating client authentication almost for free.
>>
>> The protocol has a proof of security (scrutinized through several hundred
>> papers
>> that build upon HMQV) which not only serves to have confidence in the
>> design but
>> also avoids the "safety margins" typically needed for not-well-understood
>> protocols. Very importantly, it avoids the need to rely on the CA to
>> check the
>> algebraic properties of public keys (as it is required, for example, by
>> MQV).
>> Indeed, such reliance would be a kiss of death to a protocol intended for
>> wide
>> use as CA's do not typically do such tests. In particular, it would be
>> totally
>> unusable for TLS where a server signs its own HMQV key (and the CA
>> certifies the
>> server signature key).
>>
>> There has been some contention about the need to do group membership
>> tests in
>> HMQV. Indeed, the need for this depends on the use case and security
>> model.
>> However, this issue is relevant for mod p groups where such tests are
>> expensive.
>> For elliptic curves the test is inexpensive hence can be made an integral
>> part
>> of the protocol.
>>
>> Finally, for those wondering if UKS attacks should be avoided in TLS. For
>> many
>> years I had to work hard to convince people that UKS attacks are real
>> threats.
>> The counter-intuitive nature of these attacks is that an attacker can
>> cause harm
>> without having to learn the key. Fortunately (or should I say
>> unfortunately), the
>> "re-negotiation bug" in TLS is an excellent demonstration of how
>> practical such an
>> attack can be. Nothing better than the history of TLS to show that one
>> better
>> takes seriously attacks that seem theoretical at first glance.
>> ​
>>
>> Hugo
>>
>>
>> On Tue, Mar 4, 2014 at 12:10 PM, Dan Brown <[e-mail]> wrote:
>>
>>>  Dear CFRG list,
>>>
>>>
>>>
>>> If I understand correctly, the TLS WG plans a protocol revision which
>>> will modify the underlying key establishment scheme.  Should CFRG advise
>>> TLS on key establishment?
>>>
>>>
>>>
>>> Naturally, TLS may have some specific requirements, directed towards the
>>> nature of the client and server in the transport layer, whereas CFRG might
>>> have expertise on a more generic security level.  So, perhaps, TLS could
>>> convey its requirements to CFRG, and CFRG could return a set of key
>>> establishment schemes that meet those requirements, in particular, those
>>> which have been extensively researched.  (Well, that’s a bit formal, and
>>> probably requires a few more iterations than I described, but seems
>>> sensible to me.)  More likely, TLS will pick their own key establishment
>>> scheme, and ask for CFRG’s blessing.
>>>
>>>
>>>
>>> I haven’t followed the TLS list too closely, but I’d summarize two main
>>> possible approaches as: (1) patch and (2) overhaul.  On the overhaul side,
>>> I’ve seen Watson Ladd’s suggestion of signed ephemeral DH: which is
>>> something TLS already has, with the core of the proposal being to narrow
>>> the options drastically.  I’ve also seen a couple of IACR eprints analyzing
>>> the security of certain TLS ciphersuites.  (Maybe these would go on the
>>> patch side?)  If I recall those papers correctly, they define some special
>>> security models just for TLS, but I forget if these models were chosen just
>>> to make the proofs work for the protocols used in the ciphersuites, or for
>>> something more fundamental like the nature of the transport layer.
>>>
>>>
>>>
>>> ***
>>>
>>>
>>>
>>> I’d like to suggest a key establishment scheme for CFRG consideration:
>>> MQV (or one of its successors, maybe), with an eye to perhaps recommend to
>>> IETF WGs such as TLS.
>>>
>>>
>>>
>>> ***
>>>
>>>
>>>
>>> Some generic (non-TLS-specific) issues for MQV:
>>>
>>>
>>>
>>> Two benefits of MQV over signed ephemeral DH, as I see it, would be
>>> efficiency (though I’m no expert) and better plausible deniability (due to
>>> the lack of signatures).  I wonder what CFRG thinks of these benefits.
>>>
>>>
>>>
>>> Existing standards that specify versions of MQV include ANSI
>>> X9.{44,63,98}, NIST SP 800-56A, IEEE P1363, and SEC1.  Therefore, it may be
>>> redundant for CFRG to draft on RFC for MQV, although CFRG may wish to write
>>> an RFC to profile the version that they like best.
>>>
>>>
>>>
>>> These standards go towards the maturity of MQV, in the sense that they
>>> received scrutiny from the committees that drafted them, and have been
>>> public for a long time, and have served as an incentive to cryptanalytic
>>> research, being fairly high profile targets.
>>>
>>>
>>>
>>> The HMQV paper by Krawczyk critiques MQV, but these critiques did not
>>> seem terribly serious to me, at least when I last read them years ago.
>>> Also, I’m not sure how other key establishment schemes fare under these
>>> more stringent requirements (session-state reveal attacks, and so on).
>>>
>>>
>>>
>>> The version of the MQV from NIST requires identifiers in the KDF, which
>>> helps prevent UKS attacks.  (I’m not sure if TLS needs to resist UKS
>>> attacks, but a recent thread on the TLS reminds of UKS attacks.)
>>>
>>>
>>>
>>> I recently released a (rather theoretical and very incomplete) IACR
>>> eprint on MQV.  It only covers a modest, but essential, level of security
>>> for key agreement schemes.  I think other people on the CFRG list are much
>>> more up to speed on the key establishment schemes.
>>>
>>>
>>>
>>> ***
>>>
>>>
>>>
>>> Some TLS-specific issues for MQV, but at a high level for CFRG
>>> consideration:
>>>
>>>
>>>
>>> Past proposals to integrate MQV into TLS a few times include:
>>>
>>>
>>>
>>>
>>> https://datatracker.ietf.org/doc/search/?name=mqv&rfcs=on&activedrafts=on&olddrafts=on&sort
>>> =
>>>
>>>
>>>
>>> Perhaps these could be improved, given current knowledge on key
>>> agreement.
>>>
>>>
>>>
>>> A major issue is that MQV usually presumes mutual authentication, but
>>> TLS accommodates anonymous clients. Leaving the MQV client “static” key
>>> unauthenticated seems, at least intuitively, to reduce MQV to DH, on the
>>> client side, which is not much of a loss.  It may be possible to have
>>> stateful TLS client retain a static MQV key, but still unauthenticated.
>>> This could be used for the weaker TOFU model of trust, so may still have
>>> some security benefit.
>>>
>>>
>>>
>>> If I understand correctly, TLS may now want to add some kind of
>>> anonymity, e.g. encryption of certificates and other identifiers.  Since
>>> MQV involves sending ephemeral key, these could, at the cost of an extra
>>> shared key computation, protect the static (certified or trusted) keys
>>> against passive adversaries.  I’m not sure if the resulting double use of
>>> the ephemeral keys would undermine the security of MQV.
>>>
>>>
>>>
>>> Best regards,
>>>
>>>
>>>
>>> -        Dan
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> _______________________________________________
>>> Cfrg mailing list
>>> [e-mail]
>>> http://www.irtf.org/mailman/listinfo/cfrg
>>>
>>>
>>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg
>
>


-- 
"Those who would give up Essential Liberty to purchase a little Temporary
Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin