Subject: Re: [Cfrg] Please point me to a reference on attacks against EC Diffie-Hellman

From: Robert Moskowitz <[email-masked]>
Date: Tue, 13 Jul 2010 11:51:57 -0700

David recommended I move this private conversation to this list.

On 07/13/2010 11:40 AM, David Wagner wrote:
>> DHKey = X(SKA�PKB) = X(SKB�PKA) = X(SKA�SKB�G)
>>
>> P_2 = CMAC(DHKey, Address_A || Address_B || Nonce_A || Nonce_B
>> ||Security_Suite_Selector)
>>
>> Of course how you stuff a p192 DHKey here is not clear.
>>
>> I think elsewhere LSB is called out.
>>      
> This might be OK, if group parameters are chosen appropriately.
> It's not exactly what CMAC was designed for, so it might not be
> as robust as using a true hash function, but it might be OK.
>
> Two conditions that I believe are important:
> - We need G to generate a prime-order subgroup.
>    
A p-192 curve is specified.

p = 6277101735386680763835789423207666416083908700390324961279
r = 6277101735386680763835789423176059013767194773182842284081
a = -3 mod p
b = 64210519 e59c80e7 0fa7e9ab 72243049 feb8deec c146b9b1
Gx = 0x188da80e b03090f6 7cbf20eb 43a18800 f4ff0afd 82ff1012
Gy = 0x07192b95 ffc8da78 631011ed 6b24cdd5 73f977a1 1e794811

> - Each side must check that the other side's PKA / PKB are in
>    this subgroup.
> You may want to check the standard to make sure it requires both
> conditions/checks be present.  If those conditions do not hold, then
> some serious analysis is needed, and I would start to get concerned.
>
> Does IEEE P1363 still exist?  That's a group that is focused on
> standardization of crypto algorithms, including EC DH schemes.
> They would probably be well-qualified to comment on this.
>
> This query also seems appropriate to send to the IERF CFRG mailing list.
>
> -- David
>
>    

On 07/13/2010 10:53 AM, David Wagner wrote:
> The easy answer is to say that the proofs of security only apply
> if the value is hashed.  I realize this may not convince non crypto
> types (though maybe it should).
>
> If there was no hash and no CMAC, then depending upon group
> parameters, it could be vulnerable to active attacks, e.g., the
> Lim-Lee attack (from CRYPTO '93; see also van Oorschot and Wiener
> from EUROCRYPT '96).  However I have no reason to expect that to
> apply to CMAC.
>
> With CMAC, I don't know whether there will be any attacks.  It
> is possible that, if CMAC is used properly, CMAC might come close
> enough to a hash that none of the known attacks apply.  This will
> depend heavily upon how CMAC is used, at a minimum.
>
> You might want to contact a few cryptographers who have done
> great work on this kind of thing: Hugo Krawczyk, Mihir Bellare,
> Phil Rogaway, and probably many others who I am forgetting right
> now.  They might be able to provide some analysis of the specific
> scheme in 802.15.6 and see whether it's OK.  I haven't kept up to
> date with crypto, so they'd be able to give you a much better
> answer than I can.
>
> While refreshing my memory on some of this, I came across this
> paper, which purports to provide a survey of attacks on DH:
>    http://crypto.cs.mcgill.ca/~stiglic/Papers/dhfull.pdf
>
> -- David
>
>    
>> David,
>>
>> In the proposed IEEE 802.15.6 standard, an ECDH derived key is expanded
>> via CMAC to produce the actual keying material.  No cryptographic hash
>> is used in this protocol.
>>
>> This seems to go contrary to the recommendation in
>> http://www.ietf.org/id/draft-irtf-cfrg-kdf-uses-00.txt that DH derived
>> keys are NOT uniformly distributed and MUST be pasted through an extract
>> phase (eg as in HKDF).
>>
>> Can you please point me to a reference to the nature of the attack in
>> this usage.  This method will end up in medical devices like Insulin
>> pumps, Pacemakers, etc and I am looking for hard references to get the
>> authors to make needed changes.
>>
>>
>> Thank you for your time.
>>
>>
>>      
>
>

---

From: Dan Brown <[email-masked]>
Date: Tue, 13 Jul 2010 16:07:59 -0400

If the ECDH private keys are static, then generally some kind of group membership tests (or equivalent) on public keys are needed to avoid attacks on private keys (e.g. "Validation of elliptic curve public keys", PKC 2003.)    

Presuming that "DHKey" below is not revealed, with DHKey only used as a CMAC key, then this protocol would not appear to rely on the hardness of the strong (aka static) DH problem, so Cheon's attack should not apply.  [This is no proof, but P_2, being a CMAC tag, should not leak its key, i.e. DHKey.]

IEEE P1363 still exists.

Dan

PS Sorry that I haven't answered the main question: are CMAC tags good enough for keys (if the CMAC key is already an okay key)?  I don't know, but I would guess yes.  

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Robert Moskowitz
Sent: Tuesday, July 13, 2010 2:52 PM
To: [email-masked]
Subject: Re: [Cfrg] Please point me to a reference on attacks against EC Diffie-Hellman

> They would probably be well-qualified to comment on this.

...

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.