Subject: Re: [IPsec] PAKE selection: PACE

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

Hi Dan,
>   Hi Dennis,
>
>   I have read the PACE submission. I believe claim 1 of the SPEKE patent,
> US 6,792,533, covers this protocol. If you do think otherwise, please
> explain why.

This is very simple. The password is only temporarily used to protect a nonce 
sent to the other party. The key derivation step is completely independent of 
the password.

>
>   Also, in PACE you compute CIPH=E(Pwd, s) where E() is the encryption
> function of some block cipher and Pwd is the shared password. You don't
> mention the block cipher but some block ciphers have weak keys and most
> take a fixed-length key. 

Pwd is a key derived from the password, so length constrainst are no problem. 
The block cipher is used as a permutation mapping random input to random 
output. The strength of the password-derived key is not very important as the 
entropy of the key is at most the entropy of the password - which is rather 
low.

> For a general specification like this I suggest 
> strengthening it by removing any kind of dependencies and also to bind
> the parties to the exchange. I suggest using an "extraction" function with
> the shared password and the identities of the two peers to distill the
> entropy from the password, bind the identities, and derive a key with
> which to do the encryption:
>
>    k = Extractor(Pwd | max(ID-A, ID-B) | min(ID-A, ID-B))
>    CIPH = E(k, s)
>
> where max(x,y) and min(x,y) output an ordering their inputs in some
> deterministic fashion, ID-A and ID-B are the identities of the two parties
> to the exchange, and "|" is concatenation.

I don't see the point of binding the key to identities, but I might miss 
something here.

Best regards,

Dennis

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 1 Jun 2010 09:13:33 -0700 (PDT)

Hi Dennis,

  You made a very vague statement (SPEKE patent infringes on dragonfly).
I made a very detailed response to it, using the first independent claim
in a patent describing SPEKE, explaining why it did not apply.

  Now I make a detailed statement (SPEKE patent infringes on PACE, and
specifically it's the first independent claim of US 6,792,533). You
then make a vague response about how a password is used "only
temporarily", which responds neither to my statement nor to the specific
claim in the specific patent I mentioned, and then something that is
just factually incorrect: "[t]he key derivation step is completely
independent of the password."

  Try again, please. Make a detailed response to each part of the claim
and explain what in the claim does not apply to your proposal and why.
Give my statements the same level of respect that I have given yours.

  regards,

  Dan.

---

From: "Dan Harkins" <[email-masked]>
Date: Fri, 4 Jun 2010 16:08:56 -0700 (PDT)

Hi Dennis,

> sent to the other party. The key derivation step is completely independent

  The "temporary" use of a password has nothing to do with anything in
claim 1 of US 6,792,533. And the key derivation does rely on the password.
Without knowledge of the password it is not possible to derive the key.
That is the whole point of running your protocol.

  Let me provide a more detailed look into PACE's infringement on the
SPEKE patent using a paper entitled "Security Analysis of the PACE Key
Agreement Protocol" by J. Bender, M. Fischlin, and you, Dennis Kugler.
I'll refer to this as "the PACE paper".

  The SPEKE patent says that "a function of the password determines
parameters of a public-key distribution system, such as a
Diffie-Hellman ('DH') key exchange." In particular, it chooses a
generator, g, based on a function of the password, f(S)

     g = f(S)

which is then used in the public-key distribution system, such as
a Diffie-Hellman. The patent says, "We will show at least two
public-key distributions systems that work with SPEKE", and it does.
It shows SPEKE with the plain-jane Diffie-Hellman and the Modified
Diffie-Hellman.

  So if you create a password-based parameter, like a generator, to
the Diffie-Hellman or the Modified Diffie-Hellman key exchange, and
then use that password-based parameter in the Diffie-Hellman (or
Modified Diffie-Hellman) then you're basically doing SPEKE.

  Does PACE create a generator based on the password? Yes. The generator
in a Diffie-Hellman key exchange is an element in the group. And
the PACE paper defines a problem in its number theoretic assumptions
section called the PACE-DH problem: the "PAssword-based Chosen-Element
(PACE) DH problem". The security of PACE is based on using a password
("password-based") to choose a generator ("element") in which to do
a Diffie-Hellman. According to the PACE paper it's doing g = f(S) and
f(S) is based on the PACE-DH assumption.

  Does PACE use that chosen element, that generator, based
on the password in a Diffie-Hellman exchange? Yes, it does. The
paper says, "This generator is subsequently used to run a Diffie-Hellman
key agreement to derive a common key K."

  It looks like PACE is SPEKE.

  The PACE paper describes the exchange in phases. It says, "In the
first phase the chip sends a random nonce s encyrpted with the password
to the terminal. In the second phase both parties execute an interactive
protocol Map2Point, mapping the nonce to a random generateor G of a group,
e.g. an elliptic curve (the group parameters are provided by the chip and
authenticated by a governmental authority). In the third phase the two
parties run a Diffie-Hellman (DH) key agreement on the agreed-upon
generator G and use the DH key to derive the actual keys for subsequent
use." It goes on to mention a "final authentication step" to "derive an
ephemeral MAC key K'mac as K'mac = H(K || 3) and use this key for
authentication." (Note: K is the result of the Diffie-Hellman and
H is a hash function).

  Let's map that into the first independent claim from the SPEKE patent,
the one that claims "A cryptographic method for providing authentication,
comprising:"

  SPEKE patent:
    "providing a password-based value to a first party and a second
     party"
  PACE paper:
     "In the first phase the chip sends a random nonce s encrypted with
     the password to the terminal."
  Discussion: an encrypted nonce is a value and it is based on
     the password since the password was used to encrypt it. It's
     a password-based value and it's being provided.

  SPEKE patent:
     "selecting a parameter based on said password-based value, said
     parameter defining one of a plurality of unauthenticated key
     distribution techniques"
  PACE paper:
     "In the second phase both parties execute an interactive protocol
     Map2Point, mapping the nonce to a random generator G of a group,
     e.g. an elliptic curve"
  Discussion: the parameter defining one of a plurality of unauthenticated
     key distribution techniques is a generator for a Diffie-Hellman
     protocol. PACE computes a generator based on the nonce which was
     encrypted with the password. In other words, it selects a generator,
     a parameter, based on the aforementioned password-based value, the
     nonce. To use the terminology from the PACE paper, it does
     PAssword-based Chosen Element Diffie-Hellman (PACE-DH).

  SPEKE patent:
     "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"
  PACE paper:
     "In the third phase the two parties run a Diffie-Hellman (DH) key
     agreement on the agreed-upon generator G and use the DH key to
     derive the actual keys for subsequent use."
  Discussion: the two parties, in cooperation with each other, do one
     of the plurality of unauthenticated key distribution techniques
     that the aformentioned parameter is for. In other words, they do
     a Diffie-Hellman with the agreed-upon generator. And they generate
     "a cryptographic key", aka "the DH key."

  SPEKE patent:
     "providing authentication of said first party to said second party
     based on said cryptographic key"
  PACE paper:
     "derive an ephemeral MAC key K'mac as K'mac = H(K || 3) and use this
     key for authentication."
  Discussion: the key K is "said cryptographic key", it's the result of
     the Diffie-Hellman. And K'mac is definitely "based on" K since it's
     the output of a hash function to which K has is an input. And K'mac
     is used for authentication. So it provides authentication based on
     (a derivative of) the K, "said cryptographic key".

  There is a step-by-step match between the description of the PACE
protocol from a paper describing it and the SPEKE patent. Quite obviously,
PACE is SPEKE.

  Any "temporary" use of the password is really irrelevant, and, as your
paper notes, the PAssword-based Chosen Element is used in a Diffie-Hellman
to create a key, K. So the key can only be derived by knowing the password.

  regards,

  Dan.