Subject: [IPsec] PAKE selection: SPSK

From: "Dan Harkins" <[email-masked]>
Date: Mon, 24 May 2010 13:24:26 -0700 (PDT)

Hi,

  To kick off the PAKE selection discussion I'd like to tout one of
the candidate protocols. It is based on the dragonfly key exchange
and is described in draft-harkins-ipsecme-spsk-auth. Variants of
dragonfly have been proposed for IEEE 802.11 and as an EAP method.

  The aforementioned draft contains a complete description of how
to add dragonfly to IKE(v2), including the additional payloads
needed, their construction and processing, their format, and how they
fit into IKE(v2). While complete it isn't rigid; things (like the way
this exchange is indicated) can change without affecting security.

  I think the best way to start the discussion is to run through the
enumerated selection criteria from draft-harkins-ipsecme-pake-criteria.

  SEC1: dragonfly is based on a zero knowledge proof. It is resistant
    to passive, active, and (off-line) dictionary attack.
  SEC2: the PFS characteristics of IKE and its resistance to the
    Denning-Sacco attack are unchanged by inclusion of this authentication
    method. Dragonfly generates a shared key that has the properties of
    PFS and it is resistant to the Denning-Sacco attack but the generated
    key is used only for authentication.
  SEC3: the dragonfly exchange happens after IKE(v2)'s Diffie-Hellman
    key exchange and the subsequent payloads, including the ID payloads,
    are protected by a derivative of the resulting key. ID protection is
    not affected.
  SEC4: the protocol does not effect the "crypto agility" of IKE(v2). It
    uses the same Diffie-Hellman group that IKE(v2) uses, uses the same
    prf+() construct, and can use the negotiated MAC in HMAC form. No
    additional primitives (special modes of encryption, for example) are
    needed.
  SEC5: dragonfly has received cryptographic review in its other
    instantiations (IEEE 802.11 and EAP) and is secure. A proof of
    security in the Random Oracle model is underway but has not been
    finished.
  SEC6: the way dragonfly has been added to IKE(v2) is for authentication
    of the exchange in which it resides only. Since dragonfly is key
    generating though, it is possible to use it to parlay the weak secret
    into a long-term credential.
  SEC7: a secret element, based on the password, in the selected group
    is used in the exchange. That element can be stored instead of the
    password to resist exposure of the password in the case of compromise.

  IPR1: dragonfly was first publicly disclosed in January of 2008.
  IPR2: dragonfly was invented by me but I did not patent it nor did
    my employer at the time of invention. It is believed to be patent-free.
  IPR3: no IPR disclosure to the IETF has been made because one is not
    needed.

  MISC1: dragonfly adds one roundtrip to IKEv2 and to IKEv1's Main Mode.
    It turns IKEv1's Aggressive Mode from a three message exchange to
    a four message exchange.
  MISC2: dragonfly requires three "scalar operations", point multiplication
    for ECC or modular exponentiation for MODP. Basically, a "Diffie-
    Hellman and a half".
  MISC3: the nature of the shared secret (password, passphrase, long
    random octet string) does not affect performance.
  MISC4: internationalization can be supported as evidenced by the EAP
    method employing the dragonfly exchange.
  MISC5: dragonfly can use any of the ECP and MODP groups defined in the
    IANA registry for IKE(v2). EC2N groups are disallowed because of
    patent concerns and a desire to make implementation of dragonfly be
    license free. There is no technical reason, though, why EC2N groups
    couldn't be used.
  MISC6: the protocol fits nicely into IKE(v2)'s request/response nature.
    One single request and response is added and additional information
    is piggy-backed on the final request and response in IKE(v2) already.
  MISC7: no additional negotiation is needed: no new groups, no new
    ciphers, no new cipher modes, no key wrapping.
  MISC8: dragonfly does not require trusted third parties nor does it
    require any clock synchronization.
  MISC9: dragonfly requires use of an HMAC instantiation of a hash
    algorithm. The current specification uses this as a "random function".
    Another instantiation of dragonfly uses an HMAC'd hash function in
    "extractor" and "expander" roles, effectively defining two roles for
    the single random function. This can easily be done for IKE(v2) too.
  MISC10: the protocol supports the use of elliptic curve cryptography.
  MISC11: dragonfly is easily implemented. A reference implementation of
    the IEEE 802.11 variant is a Source Forge project named "authsae".
    It requires APIs for ECC and MODP operations found in most modern
    crypto libraries (e.g. OpenSSL).

  Dragonfly is easy to implement, license/royalty/patent free, has
modest overhead, and fits easily into IKE(v2). I believe the current
manner in which it has been added to IKE(v2) is fine but it can be
changed if implementation concerns require it. Dragonfly is secure and
has received cryptographic review. It does not require any additional
group definitions and, aside from an HMAC'd hash algorithm, does not
require additional use of any other cryptographic primitives like
ciphers. It does not require any specific cipher modes (e.g. CBC or ECB)
nor does it prohibit any (e.g. a stream cipher or a block cipher being
used as a stream cipher). It is completely "crypto agile". I believe it is
the best candidate to meet the requirements laid out in the new charter.

  I solicit comments and questions on this proposal.

  regards,

  Dan.

---

From: Dennis Kügler <[email-masked]>
Date: Wed, 26 May 2010 14:18:56 +0200

I finally had some time to have a look at your proposal and the evaluation. 
Please find some initial comments below.

- The design of SPSK is very close to SPEKE. It is based on the computation of 
a (secret) group generator from a shared password. SPEKE is patented and it 
looks like the patent is also applicable to SPSK. If not please indicate why 
not.

- "Dragonfly is secure and has received cryptographic review". Please provide 
a reference to the cryptographically reviewed document. 

- 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.

Best regards,

Dennis

> _______________________________________________
> IPsec mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ipsec

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 26 May 2010 09:34:37 -0700 (PDT)

Hi Dennis,

> looks like the patent is also applicable to SPSK. If not please indicate

  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:
     providing a password-based value to a first party and a second party;
     selecting a parameter based on said password-based value, said
        parameter defining one of a plurality of unauthenticated key
        distribution techniques;
     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
     providing authentication of said first party to said second party
        based on said cryptographic key."

  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.

  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?

  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.

  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.

  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".

  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.

  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.

> a reference to the cryptographically reviewed document.

  Both the IEEE 802.11 TGs Draft and the EAP-pwd variant have been
reviewed.

> recommend to replace the randomized search algorithm by a deterministc

  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'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.

  regards,

  Dan.