Re: [IPsec] PAKE selection: PACE

["Dan Harkins" <[e-mail]>]

  Hi Dennis,

On Tue, June 1, 2010 6:19 am, Dennis Kügler wrote:
> 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.

  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.