Subject: Re: [IPsec] PAKE selection: SPSK

From: Dennis Kügler <[email-masked]>
Date: Tue, 1 Jun 2010 15:17:44 +0200

Hi Dan,

Let's have a closer look at the patent.

>   You don't mention any specific claim from the SPEKE patent so let me
> address the first independent claim (there are many claims dependent on
> that one). The patent I'm referring to is US 6,792,533 dated Sept 14, 2004.
> The claim says:
>
>   "A cryptographic method for providing authentication, comprising:

What's claimed is a method comprising four parts. All of them are contained in 
SPSK.

>      providing a password-based value to a first party and a second party;

A value derived from the password is given to (calculated by) both parties. 
This is clearly the case in SPSK as psk is derived from the password.

>      selecting a parameter based on said password-based value, said
>         parameter defining one of a plurality of unauthenticated key
>         distribution techniques;

SPSK selects a parameter, SKE, from the password-based value psk. SKE is then 
used as the generator for a (masked) Diffie-Hellman key agreement. Due to the 
group generator SKE, a pluralty of key distribution techniques is defined - 
one for each possible (and secret) value of SKE.

>      generating by said first party, in cooperation with said second party,
>         a cryptographic key based on said one of the plurality of
>         unauthenticated key distribution techniques, wherein said second
>         party cooperates in generating said cryptographic key by using
>         said one of the plurality of unauthenticated key distribution
>         techniques defined by said first value; and

The derived shared secret ss is a cryptographic key derived from a masked 
Diffie-Hellman key agreement based on the secret group generator SKE.

>      providing authentication of said first party to said second party
>         based on said cryptographic key."

This is the calculation of the Tag using the cryptographic key ss.

>
>   Now first of all, that is very broadly worded. Every password-based
> protocol provides a password to the first party and second party. But
> there's more to this claim so SPEKE doesn't cover every single protocol
> that distributes and uses passwords.

Actually, in contrast to other patents this one is rather clear. It describes 
exactly a key distribution mechanism based on a parameter derived from a 
password. This is what SPSK does similarly.

>
>   The next part talks about selecting a parameter based on the password
> value and dragonfly certainly does that but the important part of this
> portion of the claim, and the following part of the claim, is the
> "plurality of unauthenticated key distribution techniques". What is that?

See above. By selecting an alternative group generator (SKE instead of g) and 
using an anonymous (and masked) Diffie-Hellman key exchange a plurality of 
unauthenticated key distribution techniques is defined.

>
>   There are different kinds of public key distribution systems where there
> is a "private key" and a "public key" which is based on the "private
> key". Earlier in the descriptive portion of the patent (which is not
> part of a claim but can be used to interpret a claim) it says "SPEKE can
> also use other unauthenticated public-key distribution systems, such as
> the Modified Diffie-Hellman" and goes on to show an example of that. I
> don't believe that the Modified D-H alone comprises a "plurality of
> unauthenticated key distribution techniques." I would also imagine that
> a static-ephemeral D-H or a static-static D-H that used a password-derived
> parameter to perform that particular type of unauthenticated key
> distribution technique would probably be covered.

I don't get your point. This is probably to make clear that e.g. a masked 
Diffie-Hellman is also covered by the patent???

>
>   What is common on all these unauthenticated key distribution
> techniques is how a public key based on the private key is distributed
> to the other party. The private key is communicated in an obfuscated
> form based on the discrete logarithm problem-- e.g. pub = g^priv mod p.
> That is not done in dragonfly.

There are two general approaches: The first approach is to "scramble" the 
public key (EKE) and to keep the private key unaltered and the other approach 
is to send the public key in clear but to indirectly alter the private by 
modifying the parameters.

>
>   In dragonfly the private key is obfuscated by adding it to a random
> number modulus the order of the group. The random number is unmasked
> in a fashion that gives the private key to the second party in a form
> that does not let it know the private key. Such a technique is new and
> novel and not part of any known "plurality of unauthenticated key
> distribution techniques".

The obfuscation is cryptographically not sound. As you transmit both Scalar = 
(private + mask) and Element = SKE^(-mask) simultaneously anyone can compute 
the public key SKE^private = Element*SKE^Scalar (in which case we're back to 
SPEKE). This construction however unnecessarily risks to leak the private 
key, as any bias in the random number generation will reveal information on 
the private key. Especially when computing random numbers modulo a prime 
preventing a bias is not trivial.

>
>   So it is my contention that for this claim to apply then both a
> password-based parameter must be used AND that password-based parameter
> must be used with a known technique of unauthenticated key distribution.
> It is not and this claim does not apply to dragonfly.

I disagree. It does very well apply to SPSK/dragonfly.

>
>   If it was not claim 1 that you were referring to above then please
> say exactly what claim in the SPEKE patent you are talking about.
>
> > - "Dragonfly is secure and has received cryptographic review". Please
> > provide
> > a reference to the cryptographically reviewed document.
>
>   Both the IEEE 802.11 TGs Draft and the EAP-pwd variant have been
> reviewed.

So nothing has been published and has been reviewed by the cryptographic 
community?

>
> > - The construction used for computing the group generator is susceptible
> > to
> > side channel (timing) attacks and may leak the shared password. I'd
> > therefore
> > recommend to replace the randomized search algorithm by a deterministc
> > algorithm.
>
>   I had a discussion about that. The IEEE 802.11 TGs Draft had a password
> element created based on the password before the exchange started
> (it was computed a configuration time when a particular group was
> selected). Then, when the exchange started the identities of the two
> parties were run through the random function and used in the "scalar-op"
> to derive a pair-wise unique element with which to do dragonfly. This
> would foil the side channel attack. But I was convinced that this was not
> so important and eliminated the extra step to provide ease of analysis.
> If you think this is important the SPSK draft could certainly introduce
> this technique to get around a side channel attack.

I think that should be addressed.

>
>   I'm not so sure how important that is though (basically I was convinced
> it's not so important). If you know I can find a solution to the curve the
> first time you can eliminate some passwords from the pool of potential
> passwords but you don't know which ones unless you have run them all
> through the algorithm beforehand. And even if you have run all possible
> password through the algorithm it certainly doesn't leak the shared
> password, it just allows the attacker to eliminate some passwords from
> the pool of potential passwords. And to do so this attack has to be
> mounted and that is not a trivial attack.

If the attacker can eleminate only a few passwords every time you execute the 
protocol he's done with the attack quickly.

Best regards,

Dennis

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 1 Jun 2010 11:55:43 -0700 (PDT)

Hi Dennis,

  The issue here is the meaning of a "plurality of key distribution
techniques."

  You say, "[d]ue to the group generator SKE, a pluralty of key
distribution techniques is defined - one for each possible (and secret)
value of SKE." That's not what the patent is talking about. The "plurality
of key distribution techniques" describes different techniques of key
distribution not a single technique being used with different passwords--
and therefore different SKEs.

  The descriptive portion of a patent (outside the claim) can be used to
interpret what is said in a claim. The claim describes a "plurality of
unauthenticated key distribution techniques" and looking at the patent
you can see where it says, "SPEKE can also use other unauthenticated key
distribution systems..." and goes on to describe one of them. What it
describes is another technique at key distribution, not a repetition of a
single one with different passwords (or keys). It's the other key
distribution systems that comprise the plurality, not a singular system
that's keyed using different passwords.

  The patent gives two examples, one being a straight-forward Diffie-
Hellman and another being the Modified Diffie-Hellman. There are others,
I would imagine, like El Gamal, that the patent holder would say falls
into this claim. It's reasonable to assume that the holder of the patent
doesn't want people to just use a different key distribution technique
("I'm doing Modified Diffie-Hellman not Diffie-Hellman so the patent
doesn't apply").

  The thing that D-H, Modified D-H, El Gamal, and static variants of D-H--
i.e other known techniques of unauthenticated key distribution-- is that
the key being distributed is a secret (private key) that has been
obfuscated in a form (a public key) so it cannot be recovered when
distributed. All of these things have the following in common:

   public = g^private modulo prime

(or equivalent ECC representation). That's the thing-- "public"-- that
gets distributed whether you're doing plain-jane Diffie-Hellman, whether
you're doing Modified Diffie-Hellman, whether you're doing El Gamal,
in other words, when you're doing the "plurality of key distribution
techniques". They all use the discrete logarithm problem to hide
the private key and create a public key as part of their key distribution
technique.

  Dragonfly's method of obfuscation of the private key to produce the
public key is different than the others-- it uses addition modulo the
ORDER of the group.

   public = private + mask modulo order

It is different, unique, novel, new and therefore cannot be part of any
claimed plurality of key distribution techniques. If you disagree, I defy
you to show me mention of this technique anywhere to construct and
distribute public keys out of private keys (or if you are claiming that
a patent holder can patent today things that have not yet been invented
then please make that claim).

  Down at the bottom of this email you mention that this method is
"cryptographically not sound". First of all, I will note that this means
you are, in fact, treating this technique differently than the others,
since I don't believe you are claiming that Diffie-Hellman or El Gamal
is "cryptographically not sound". That buttresses my statement above
that this technique is different. Thank you for helping to prove my
point.

  Regarding your claim, one has to know SKE to generate SKE^private
and "anyone" does not know the password, so "anyone" cannot generate
SKE^private.

  Also, you say the private key can be leaked. If you can show how a
passive attacker can determine a private key in dragonfly-- even if
you tell the passive attacker the password!-- I will show you how that
very same attacker can solve the Computational Diffie-Hellman (CDH)
problem with the same computational advantage. Since it is assumed that
the CDH problem is computationally infeasible it can safely be assumed
that the attack you suggest is also computationally infeasible.

  regards,

  Dan.

On Tue, June 1, 2010 6:17 am, Dennis Kügler wrote:
> _______________________________________________
> IPsec mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ipsec
>

---

From: Dennis Kügler <[email-masked]>
Date: Wed, 2 Jun 2010 10:45:43 +0200

Hi Dan,

>   The issue here is the meaning of a "plurality of key distribution

So let's have again a look at the claim:

[...]
[...]

It explains very clearly that the key distribution mechanism to be used is 
defined by a parameter, which is derived from the password. I don't think 
that you can interpret this differently. SPEKE does this by selecting the 
parameter as group generator but also claims any other method. SPSK does this 
similarly.

> and therefore different SKEs.

...based on the password??? Strange interpretation, but I don't think that 
we'll find consens on that and therefore I skip this discussion here.
> then please make that claim).

As I've already tried to explain in my last mail, you not only define

  public1 = private + mask

but also

  public2 = g^(-mask)

which finally can be combined to (by everyone)

  public = public2 * g^public1 = g^(-mask + private + mask)= g^private

The obfuscation step isn't obfuscating the public key at all, it just 
introduces potential problems as the OTP on the private key very likely leaks 
information, if not applied correctly. The correct application of a OTP is 
not trivial especially if the OTP is applied modulo a prime. This is why I 
called it cryptographically not sound as this step is not giving you any 
benefit but may cause a lot of problems.

> that this technique is different. Thank you for helping to prove my

You're welcome. Although I don't think that it'll help you to convince the 
patent holder.

> that the attack you suggest is also computationally infeasible.

I'm looking forward to that. When can we expect a full paper?

Best regards,

Dennis

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 2 Jun 2010 09:24:44 -0700 (PDT)

Hi Dennis,

> we'll find consens on that and therefore I skip this discussion here.

  The strange interpretation is all yours. You said "one for each possible
(and secret) value of SKE." Different values of SKE occur through different
passwords.

  I agree there is no consensus on your view of this matter because it
is not supported by descriptive text in the rest of the patent.

> You're welcome. Although I don't think that it'll help you to convince the

  Thank you for offering your personal opinion. Let me return the favor:
I think it's more convincing that making irrelevant remarks ("the password
is only temporarily used") followed by incorrect statements ("the key
derivation is completely independent of the password").

> I'm looking forward to that.

  And I'm looking forward to giving it to you :-) But I said "if you
can show me how a passive attacker can determine a private key...." so
the proverbial ball is in your court. Show me how a passive attack can
successfully obtain either private key in dragonfly (not something that
begins "well, if he uses a bad random number generator..." which is not
an attack against the protocol) and I'll show you how you can solve
the CDH.

>                               When can we expect a full paper?

  Real Soon Now (tm). I know you are aware that it is time consuming and
not a trivial task.

  But something that is much easier is for you to do a full and
adequate response to my previous statement on PACE-- it infringes on
claims 1 and 10 of US 6,792,533. When can we expect that?

  It is quite telling that you apparently do not wish to engage in the
same sort of detailed analysis of PACE that you do with dragonfly.

  regards,

  Dan.