Re: [Cfrg] Response to the Attacks on key agreement in SM2

[Watson Ladd <[e-mail]>]

On Wed, Mar 5, 2014 at 7:30 PM, David Jacobson <[e-mail]> wrote:
> You said that picking a random number in [1, n-1] is in constant time is
> hard.  Here is a solution that doesn't run in constant time.
>
> let w be the minimum number of bits to represent n-2.
> do {
>     candidate = generate_random_bits(w);   // generate w random bits (in
> practice you generate a block and mask to w bits)
> } until interpret_as_integer(candidate) <= n-2.
>
> return interpret_as_integer(candidate) + 1;
>
>
> Sure, it doesn't run in constant time. But, assuming that n is not a secret,
> this is harmless.  The probability of success is at least 1/2, so the
> typical running time is at most 2 rounds.
>
> The reason it is safe is that the running time only tells the attacker the
> number of times the random bit generator generated a value > n-2.  Even if
> on every iteration that failed, the algorithm revealed the entire candidate,
> it would be okay, since one security property of an a cryptographic quality
> RBG is that knowing some bits gives an attacker no advantage at guessing
> bits he hasn't seen.

Yes, the above is true. However, a standard trick for removing
randomness is to use a second key K and compute
H(k || M). Randomness At this point one does have secret data being
used, so you do need to watch out. But maybe an interation isn't so
bad...
I just prefer not to do that kind of leak analysis, and write
constant-time code.

Sincerely,
Watson Ladd

>
>     --David Jacobson
>
>
>
> On 3/5/14 6:49 PM, Watson Ladd wrote:
>>
>> On Tue, Mar 4, 2014 at 11:32 PM, Limin LIU <[e-mail]> wrote:
>>>
>>> Hi Watson,
>>> In my previous email, I addressed that the attack you mentioned is not
>>> feasible since it is based on an unpractical assumption.
>>> As for the security model of SM2 key exchange, it's another problem. The
>>> key exchange protocol in SM2 is based on MQV, a widely standardized (ANSI,
>>> ISO/IEC, IEEE) and recommended (NIST, NSA suite B) EC-DH-based key agreement
>>> protocol. The security proof of MQV was given by Kunz-Jacques in paper "
>>> About the Security of MTI/C0 and MQV" in 2006, which you might have already
>>> read.
>>
>> Actually the situation is a bit better: it looks to me like the paper
>> by Kunz-Jacques covers SM2: one needs to adjust the function f, and
>> then everything works. However, this is not a standard assumption, and
>> the paper takes place in weaker models then CK, something I would like
>> to see in the security considerations. Note that MQV is no longer in
>> suite B.
>>
>> Minor nits I found:
>> The encryption scheme has a major issue: t=0 is disallowed, leaking
>> information about M. In particular encrypting single bits is trivially
>> insecure. I would recommend that short lengths be avoided if it is
>> impossible to change the standard/this isn't a translation issue.
>>
>> It also uses a hash as a MAC, which is not the right thing. (x2,y2) is
>> distinguishable from random bits, making an analysis of H(x1 || M ||
>> y1) hard. Encrypt and MAC is insecure because the MAC can always leak
>> information about the message and remain a good MAC. For a hash
>> function in the standard model I don't know why H(x1 || M || y1) has
>> to be a MAC. Maybe the construction mentioned is secure: it's
>> difficult to say. Certainly I would feel much happier with C3=HMAC(k2,
>> C2) with k1 || k2=KDF(p, keylength).
>>
>> Pick a random number in [1, n-1] is difficult to do in constant time
>> and with zero bias. In particular the naive modular reduction approach
>> will leak enough bits to reconstruct the secret key. Maybe this is
>> handled by the random number generator, but this has bitten people
>> (including me) in the past. NIST actually had to edit ECDSA standards
>> to fix this issue.
>>
>> I can't make head or tail of the message expansion in SM3.
>>
>> Sincerely,
>> Watson Ladd
>>>
>>> Best,
>>> Limin
>>> -----Original Message-----
>>> From: Watson Ladd [mailto:[e-mail]]
>>> Sent: Thursday, February 27, 2014 12:15 AM
>>> To: liulimin
>>> Cc: [e-mail]
>>> Subject: Re: Response to the Attacks on key agreement in SM2
>>>
>>> On Tue, Feb 25, 2014 at 11:23 PM, Limin LIU <[e-mail]> wrote:
>>>>
>>>> Dear Watson,
>>>>
>>>>      This is Limin from the team of SM2 patent holder, Data Assurance
>>>> and Communication Security Center in Chinese Academy of Sciences.
>>>> Following is the response to your concern about the attacks on SM2.
>>>> (Attacks on key agreement in SM2.
>>>> http://www.ietf.org/mail-archive/web/cfrg/current/msg04297.html )
>>>>
>>>>      In Xu's (CANS 2011) paper, the attack towards SM2 key exchange
>>>> protocol is launched in Canetti-Krawczyk model, where adversary could
>>>> reveal private session state. To make the attack successful, the
>>>> adversary should have the ability to reveal the state variable
>>>> (x_v,y_v). (x_v,y_v) is the result of a computation from B's private
>>>> key d_B, B's private random number r_B, along with other public
>>>> parameters. The question here is, d_B and r_B are not easy to be
>>>> obtained in real world. What's more, if the adversary has such kind of
>>>> knowledge, he could already obtain the session key K_B by K_B =
>>>> KDF(x_v||y_v||z_A||z_B,klen), it seems unnecessary to launch other attacks.
>>>> Overall, this attack is academic crypto analysis based on strong
>>>> assumptions. It's not a practical threaten to the algorithm.
>>>>
>>>>     Hope this could address your concerns. Any further comments will be
>>>> greatly appreciated.
>>>
>>> It doesn't. Instead of an analysis showing that in some reasonable threat
>>> model SM2 security reduces to some reasonable assumptions, you present an
>>> argument that the one attack I found in the literature doesn't matter in
>>> practical applications. There is a large literature and well-understood
>>> theory of key negotiation protocols, and I have yet to see any demonstration
>>> that SM2 was designed with that in mind.
>>>
>>> Sincerely,
>>> Watson Ladd
>>>>
>>>> Best,
>>>> Limin
>>>>
>>>
>>>
>>> --
>>> "Those who would give up Essential Liberty to purchase a little Temporary
>>> Safety deserve neither  Liberty nor Safety."
>>> -- Benjamin Franklin
>>>
>>
>>
>



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