Subject: [Cfrg] I-D Action:draft-sheffer-emu-eap-eke-00.txt

From: David McGrew <[email-masked]>
Date: Thu, 29 Jan 2009 14:08:49 -0800

Begin forwarded message:

> From: Yaron Sheffer <[email-masked]>
> Date: January 29, 2009 2:00:50 PM PST
> To: "[email-masked]" <[email-masked]>
> Subject: [Emu] FW: I-D Action:draft-sheffer-emu-eap-eke-00.txt
>
> EKE is a well known password-based mutual authentication protocol.  
> The patent on EKE is nearing expiry, so we figured this is a good  
> time to specify an EAP method using this protocol.
>
> We would appreciate all comments.
>
> Thanks,
>        Yaron
>
> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]
> Sent: Thursday, January 29, 2009 15:30
> To: [email-masked]
> Subject: I-D Action:draft-sheffer-emu-eap-eke-00.txt
>
> A New Internet-Draft is available from the on-line Internet-Drafts  
> directories.
>
>        Title           : An EAP Authentication Method Based on the  
> EKE Protocol
>        Author(s)       : Y. Sheffer, et al.
>        Filename        : draft-sheffer-emu-eap-eke-00.txt
>        Pages           : 22
>        Date            : 2009-01-29
>
> The Extensible Authentication Protocol (EAP) describes a framework
> that allows the use of multiple authentication mechanisms.  This
> document defines an authentication mechanism for EAP called EAP-EKE,
> based on the Encrypted Key Exchange (EKE) protocol.  This method
> provides mutual authentication through the use of a short, easy to
> remember password.
>
> A URL for this Internet-Draft is:
> http://www.ietf.org/internet-drafts/draft-sheffer-emu-eap-eke-00.txt
>
> Internet-Drafts are also available by anonymous FTP at:
> ftp://ftp.ietf.org/internet-drafts/
>
> Below is the data which will enable a MIME compliant mail reader
> implementation to automatically retrieve the ASCII version of the
> Internet-Draft.
>
> Email secured by Check Point
> _______________________________________________
> Emu mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/emu

_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: "Dan Harkins" <[email-masked]>
Date: Thu, 29 Jan 2009 15:25:53 -0800 (PST)

Hi,

  This draft specifies AES in CBC mode for encrypting the Diffie-Hellman
exponentials. Since the data being encrypted is a random element in the
chosen group is the additional randomization provided by the IV
necessary?

  Normally ECB mode is an insecure encryption scheme (even if the
underlying block cipher is secure) due to its determinism and a protocol
that uses it is therefore flawed, but is EKE a special case in which
security can be achieved even with ECB mode?

  Protocol designers are told by cryptographers to always authenticate
what is being encrypted and to never use ECB. Is EKE an exception to
those two rules?

  Dan.

---

From: "Scott Fluhrer" <[email-masked]>
Date: Thu, 29 Jan 2009 22:55:26 -0500

I just glanced at the draft, and there's a serious problem with it as
written; the draft uses the wrong DH group, and that causes the system not
to meet its security goals; someone listening in the middle could eliminate
75% of possible passwords by listening to a single successful exchange, if
DHGROUP_14 was used.  That means that if the attacker has a dictionary of
1,000,000 possible passwords, then he would expect to able to eliminate all
but the correct entry by listening to about 10 successful exchanges.

The draft uses a DH group as an important subcomponent, and the one DH group
it defines is the 2048-bit MODP group 14.  In this group, the value g (which
happens to be 2) is a quadratic residue (that is, there is some number z
such that z*z == g mod p, where p is the DH group modulus).  This implies
that the DH public values will always be quadratic residues; in contrast,
half the numbers between 1 and p-1 are quadratic residues.

Hence, here is the attack: the attacker listens into the exchange, and
captures the E(Password, Y_S) and the E(Password, Y_P) values.  Then, for
each password Pass_i in his dictionary, he decrypts the payloads using that
potential password (that is, computes D(Pass_i, E(Password, Y_S)) and
D(Pass_i, E(Password, Y_P)) and checks if those values are quadratic
residues module p (that turns out not to be difficult).  If
Pass_i==Password, then he will have computed Y_S and Y_P, which will both be
quadratic residues.  On the other hand, if Pass_i!=Password, then those
values will be effectively random, and so at least one of them will not be a
quadratic residue with probability .75.  In other words, if one of those
values turn out not to be a quadratic residue, he knows that that particular
password is not the right one, and so can strike it from the list.

Also, in case you're wondering, the groups defined in RFC5114 (suggested in
the Security Considerations section of the draft) are far worse, with high
probability, the attacker is able to eliminate everything except the correct
password in one exchange.  Extending the above analysis to cover these other
groups is straightforward.

The easiest way to fix this would be use a different DH group.  The easiest
change would be to use the same modulus, but use a value of g which is a
"primitive element" (and with the modulus found in DH group 14, any
quadratic nonresidue between 2 and p-2 will be a primitive element).  With a
primitive element, the value g**x mod p can take on any value between 1 and
p-1, and so that attacker will have no way of eliminating values because "it
could not possibly be a DH public value", except for those values which are
out of range.  I don't have a recommendation on which primitive element
would be best, but we do have (p-1)/2 possibilities to choose from.

The one nice thing about group 14 is that it starts out with 66 "one" bits;
that means that a random value has probability circa lE-20 of being able to
be rejected because it is too large; this means that an attacker just
relying on decrypted values being too large would need to listen into a huge
number of sessions to be able to eliminate a decent percentage of the
dictionary.  It's possible that it is desirable to make that even more
impractical (by selecting a modulus with even more "one" msbits); that is
something for the working group to decide.

-- 
scott

---

From: David Jacobson <[email-masked]>
Date: Thu, 29 Jan 2009 21:18:19 -0800

Section 3.2 starts using symbols Y_P and Y_S out of the blue.  There is 
a reference to "BM[92]", but the reader should not have to find Proc. 
IEEE Symp. on Research in Security and Privacy , May 1992, to understand 
this RFC.

Section 3.2 shows

====
  EAP-EKE-Commit/Request: S -> P

       E(Password, Y_S))
====
And section 5 shows:

====
5.2.  EAP-EKE-Commit/Request

    The server computes

       DHValue_S = g^x mod N,

    where 'x' is a randomly chosen number in the range 2 ..  N-1.  The
    randomly chosen number is the private key, and the calculated field
    is the corresponding public key.  The calculated value MUST NOT be
    zero modulo N. If the peer receives a bad value for this field, it
    MUST take action to disconnect or disable the link.  Each of the
    peers MUST use a fresh, random value for this field on each run of
    the protocol.

    The server transmits

       DHComponent_S = E(prf+(password, "EAP-EKE Password"), DHValue_S),
====

So I take it that the DHComponent_S of Section 5 is the same as the Y_S 
of section 3.2.  But it was confusing at first.  The mapping between 3.2 
and 5 should be stated rather than left as an exercise for the reader.

Finally, Section 7 alludes to the possibility of using Elliptic-Curve 
Diffie-Hellman when it says,

  3.  Key strength: the strength of the resulting key depends on the
        finite cyclic group chosen.  For example, [RFC5114] defines new
        groups available for use with this protocol.  Using groups from
        [RFC5114] the strength can vary from 80 bits (for the 1024-bit
        MODP with 160-bit Prime Subgroup) to 256 bits (for the 521-bit
        Random ECP Group).  Other groups can be defined and the strength
        of those groups depends on their definition.  This is REQUIRED by
        [RFC4017].

Yet section 5 gives no hint of anything other than the modular 
exponentiation Diffie-Hellman.  If you really intend for this document 
to apply to ECDH, you should mention that explicitly somewhere in the 
document, and perhaps section 5 should contain something like.  "(If 
Elliptic Curve Diffie-Hellman is used, the corresponding additive group 
operations are to be understood.)"

   -- David Jacobson

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 30 Jan 2009 14:06:59 +0200

Hi Scott,

Thanks for your analysis. Can you please clarify in what way the RFC 5114 groups are even worse?

I don't want to go into the business of DH group generation, if I can avoid it. Are there any published groups with a (published) primitive generator? Otherwise, can you advise me on selecting and qualifying such an element for group 14?

Best regards,

        Yaron

> From: Scott Fluhrer [mailto:[email-masked]]
> Sent: Friday, January 30, 2009 5:55
> To: 'Dan Harkins'; 'David McGrew'
> Cc: [email-masked]; Yaron Sheffer; [email-masked];
> [email-masked]
> Subject: RE: [Cfrg] I-D Action:draft-sheffer-emu-eap-eke-00.txt
>
> Scanned by Check Point Total Security Gateway.
>
> Scanned by Check Point Total Security Gateway.

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Fri, 30 Jan 2009 08:20:30 -0500

On Fri, 30 Jan 2009 14:06:59 +0200
Yaron Sheffer <[email-masked]> wrote:

> I don't want to go into the business of DH group generation, if I can
> avoid it. Are there any published groups with a (published) primitive
> generator? Otherwise, can you advise me on selecting and qualifying
> such an element for group 14?

The issue is what Mike Merritt and I called "partition attacks".  Let's
take a trivial example.  Suppose you had a cipher with a 16-bit block
size, so the range of possible plaintext values was [0,65535].
However, you picked a prime of 16001, so the legal values were
[1,16000].  If a trial password decrypted to [16001,65535], it had to
be a bad guess, so you could rule it out.  In this example, about 3/4
of your guesses would be ruled out in one session.  The next session,
with a different exponential, would let you rule out 3/4 of the
remainder, etc.  See section 2.5.1 of [BM92].

		--Steve Bellovin, http://www.cs.columbia.edu/~smb
_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: "Hannes Tschofenig" <[email-masked]>
Date: Fri, 30 Jan 2009 15:57:02 +0200

Thanks for your feedback, Steve and Scott. Your comments are certainly right
as the original EKE paper explains.  

The draft was indeed published a bit too early, thus lacking review. 

One aspect that motivated us to start working on such a document for the EMU
working group regarding strong password based protocols was the believe of
some of us that a punch of the IPRs on those mechanisms will soon expire. 

Does someone know more details about it or are those just rumors? 

Ciao
Hannes

>From: [email-masked] [mailto:[email-masked]] On 
>Behalf Of Steven M. Bellovin
>Sent: 30 January, 2009 15:21
>To: Yaron Sheffer
>Cc: [email-masked]; [email-masked]; 'David McGrew'; 
>[email-masked]; Scott Fluhrer
>Subject: Re: [Cfrg] I-D Action:draft-sheffer-emu-eap-eke-00.txt
>
>The issue is what Mike Merritt and I called "partition 
>attacks".  Let's take a trivial example.  Suppose you had a 
>cipher with a 16-bit block size, so the range of possible 
>plaintext values was [0,65535].
>[1,16000].  If a trial password decrypted to [16001,65535], it 
>had to be a bad guess, so you could rule it out.  In this 
>example, about 3/4 of your guesses would be ruled out in one 
>session.  The next session, with a different exponential, 
>would let you rule out 3/4 of the remainder, etc.  See section 
>2.5.1 of [BM92].
>
>
>		--Steve Bellovin,

---

From: "Scott Fluhrer" <[email-masked]>
Date: Fri, 30 Jan 2009 09:01:25 -0500

> Sent: Friday, January 30, 2009 8:21 AM
> To: Yaron Sheffer
> However, you picked a prime of 16001, so the legal values 
> were [1,16000].  If a trial password decrypted to 
> [16001,65535], it had to be a bad guess, so you could rule it 
> out.  In this example, about 3/4 of your guesses would be 
> ruled out in one session.  The next session, with a different 
> exponential, would let you rule out 3/4 of the remainder, 
> etc.  See section 2.5.1 of [BM92].

And, to extend this answer to the specific question of the RFC 5114 groups,
the value g**x can take on an even more limited number of possible values;
it can take on only 'q' distinct values, where 'q' is the size of the
subgroup (and, yes, there is a practical test to check whether a possible
value is one of these distinct values).  Since (for example, group 24), p is
about 2**2048 and q is about 2**256, and so a random value between 0 and p
will be a member of the subgroup with probability 2**(256-2048) == 2**-1792,
and this is so tiny that if there is a test password that decrypts to a
valid subgroup member, the attacker can assume that the password guess is
correct.

-- 
scott

---

From: "Scott Fluhrer" <[email-masked]>
Date: Fri, 30 Jan 2009 10:10:49 -0500

> Behalf Of Yaron Sheffer
> Sent: Friday, January 30, 2009 7:07 AM
> To: Scott Fluhrer; 'Dan Harkins'; 'David McGrew'
> Cc: [email-masked]; [email-masked]; [email-masked]
> I don't want to go into the business of DH group generation, 
> if I can avoid it. Are there any published groups with a 
> (published) primitive generator? Otherwise, can you advise me 
> on selecting and qualifying such an element for group 14?

Ummm, I'm not aware of any such published groups (usually when you're doing
DH, you would prefer a subgroup with a prime order, and so you deliberately
pick a generator that's not a primitive element).  However, I did run a
quick check (which needs independent confirmation): the smallest primitive
elements for the DH 14 prime p are: 11, 13, 17, 22, 23.  Smaller g's do tend
to make the initial computation faster, and so if you are using the DH 14
prime p, there seems little reason not to pick the smallest one (11 in this
case).

> > written; the draft uses the wrong DH group, and that causes 
> the system 
> > not to meet its security goals; someone listening in the 
> middle could 
> > eliminate 75% of possible passwords by listening to a single 
> > successful exchange, if
> > DHGROUP_14 was used.  That means that if the attacker has a 
> dictionary 
> > of 1,000,000 possible passwords, then he would expect to able to 
> > eliminate all but the correct entry by listening to about 10 
> > successful exchanges.
> >
> > The draft uses a DH group as an important subcomponent, and 
> the one DH 
> > group it defines is the 2048-bit MODP group 14.  In this group, the 
> > value g (which happens to be 2) is a quadratic residue 
> (that is, there 
> > is some number z such that z*z == g mod p, where p is the DH group 
> > modulus).  This implies that the DH public values will always be 
> > quadratic residues; in contrast, half the numbers between 1 and p-1 
> > are quadratic residues.
> >
> > captures the E(Password, Y_S) and the E(Password, Y_P) 
> values.  Then, 
> > for each password Pass_i in his dictionary, he decrypts the 
> payloads 
> > using that potential password (that is, computes D(Pass_i, 
> E(Password, 
> > Y_S)) and D(Pass_i, E(Password, Y_P)) and checks if those 
> values are 
> > quadratic residues module p (that turns out not to be 
> difficult).  If 
> > Pass_i==Password, then he will have computed Y_S and Y_P, 
> which will 
> > both be quadratic residues.  On the other hand, if 
> Pass_i!=Password, 
> > then those values will be effectively random, and so at 
> least one of 
> > them will not be a quadratic residue with probability .75.  
> In other 
> > words, if one of those values turn out not to be a 
> quadratic residue, 
> > he knows that that particular password is not the right one, and so 
> > can strike it from the list.
> >
> > Also, in case you're wondering, the groups defined in RFC5114 
> > (suggested in the Security Considerations section of the draft) are 
> > far worse, with high probability, the attacker is able to eliminate 
> > everything except the correct password in one exchange.  
> Extending the 
> > above analysis to cover these other groups is straightforward.
> >
> >
> > quadratic nonresidue between 2 and p-2 will be a primitive 
> element).  With
> > a
> > primitive element, the value g**x mod p can take on any 
> value between 1
> > and
> > p-1, and so that attacker will have no way of eliminating 
> values because
> > "it
> > could not possibly be a DH public value", except for those 
> values which
> > are
> > The one nice thing about group 14 is that it starts out 
> with 66 "one"
> > bits;
> > that means that a random value has probability circa lE-20 
> of being able
> > to
> > relying on decrypted values being too large would need to 
> listen into a
> > huge

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Fri, 30 Jan 2009 10:41:49 -0500

On Fri, 30 Jan 2009 15:57:02 +0200
"Hannes Tschofenig" <[email-masked]> wrote:

> One aspect that motivated us to start working on such a document for
> the EMU working group regarding strong password based protocols was
> the believe of some of us that a punch of the IPRs on those
> mechanisms will soon expire. 
> 

Note well: I am not a lawyer; treat anything I say skeptically...

That said -- the patent on EKE (US patent 5,241,599) was filed on
October 2, 1991 and issued on August 31, 1993.  I *think* that that
means it expires on Oct 2, 2011.  The AEKE patent (5,440,635) was filed
on August 23, 1993 and issued on August 8, 1995; I believe it expires
August 8, 2015.  Both of those patents were assigned to Lucent when
AT&T fissioned; I have no idea what Alcatel-Lucent may have done with
them since 1997.

David Jablon has several patents in this space, too, but all are
several years newer (and hence not as close to expiration) as the EKE
patents.

There was a patent on SRP as well (6,539,479); if memory serves,
Stanford effectively turned it loose.  It was filed on July 14, 1998,
and issued on March 25, 2003.

---

From: Greg Rose <[email-masked]>
Date: Fri, 30 Jan 2009 08:38:00 -0800

> prime p, there seems little reason not to pick the smallest one (11  

17 is just a tad more efficient -- you square instead of multiplying.

Greg.

---

From: "Scott Fluhrer" <[email-masked]>
Date: Fri, 30 Jan 2009 12:55:57 -0500

> From: Greg Rose [mailto:[email-masked]] 
> Sent: Friday, January 30, 2009 11:38 AM
> To: Scott Fluhrer
> Cc: Greg Rose; 'Yaron Sheffer'; 'Dan Harkins'; 'David 
> McGrew'; [email-masked]; [email-masked]; [email-masked]
> >> From: [email-masked] [mailto:[email-masked]] 
> On Behalf 
> >> Of Yaron Sheffer
> >> avoid it. Are there any published groups with a
> >> (published) primitive generator? Otherwise, can you advise me on 
> >> selecting and qualifying such an element for group 14?
> >
> > Ummm, I'm not aware of any such published groups (usually 
> when you're 
> > doing DH, you would prefer a subgroup with a prime order, 
> and so you 
> > deliberately pick a generator that's not a primitive element).  
> > However, I did run a quick check (which needs independent 
> > confirmation): the smallest primitive elements for the DH 
> 14 prime p 
> > are: 11, 13, 17, 22, 23.  Smaller g's do tend to make the initial 
> > computation faster, and so if you are using the DH 14 prime 
> p, there 
> > seems little reason not to pick the smallest one (11 in this case).
> 

Ummm, not quite.  We're computing g**x, not x**g...

-- 
scott

---

From: Greg Rose <[email-masked]>
Date: Fri, 30 Jan 2009 14:19:01 -0800

> Ummm, not quite.  We're computing g**x, not x**g...

D'oh.

Greg.