Subject: [IPsec] NUDGE: WG Last Call for draft-ietf-ipsecme-dh-checks

From: Paul Hoffman <[email-masked]>
Date: Mon, 8 Apr 2013 14:46:00 -0700

[[ So far, we have received only *one* review of this document, from Tero. If we don't receive more reviews, the document might not progress due to lack of interest. Please review this document within the next week and contribute your review to the list. ]]

Greetings. This is the start of the WG Last Call for draft-ietf-ipsecme-dh-checks; the WG period will end in two weeks, on April 15. The current draft is available at http://tools.ietf.org/html/draft-ietf-ipsecme-dh-checks-01

Given that this will be a Standards Track document, it is important for it to be reviewed by as many people as possible. Possible results of individual reviewing the document are:

- "Looks fine, please publish"

- "Looks fine, here are some comments"

- "Has some problems, here they are"

- Other things of that sort

Many people on this mailing list are IPsec implementers but are mostly or completely silent on the mailing list. If you are one of those people, doing a WG Last Call review is a good way to participate usefully in the WG. Please strongly consider (a) reading the current draft and (b) sending a message to the list with your short or long review. If there are too few reviews on this document, we could get pushback from the IESG about the document.

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

---

From: Dan Brown <[email-masked]>
Date: Mon, 8 Apr 2013 22:01:43 +0000

Looks fine, please publish.

----- Original Message -----
From: Paul Hoffman [mailto:[email-masked]]
Sent: Monday, April 08, 2013 05:46 PM Eastern Standard Time
To: IPsecme WG <[email-masked]>
Subject: [IPsec] NUDGE: WG Last Call for draft-ietf-ipsecme-dh-checks

--Paul Hoffman

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

---

From: Andrey Jivsov <[email-masked]>
Date: Mon, 08 Apr 2013 15:45:40 -0700

Sec 2.2:
> It MUST check both that the peer's public value is in range (1 < r
>       < p-1) and that r**q = 1 mod p (where q is the size of the
>       subgroup, as listed in the RFC).

Would it make sense to specify a more economical test for strong prime 
groups?

If q is meant to be p = q*2+1, there are only two possibilities for the 
value < p-1 received from the peer to be in the wrong subgroup. One of 
them is 1, which is ruled out by the check above. Another one is g^q. 
It's a fixed quantity for the given modp group. Seems like a memcmp with 
a fixed quantity g^q is the best way to address the problem.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 8 Apr 2013 23:15:01 +0000

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf
> Of Andrey Jivsov
> Sent: Monday, April 08, 2013 6:46 PM
> To: [email-masked]
> Subject: Re: [IPsec] NUDGE: WG Last Call for draft-ietf-ipsecme-dh-checks
> 
> Sec 2.2:

"Strong groups", that is, groups with (p-1)/2 prime, are listed in section 2.1; and yes, the test there is considerably cheaper.

> 
> If q is meant to be p = q*2+1, there are only two possibilities for the value <
> p-1 received from the peer to be in the wrong subgroup. One of them is 1,
> which is ruled out by the check above. Another one is g^q.
> It's a fixed quantity for the given modp group. Seems like a memcmp with a
> fixed quantity g^q is the best way to address the problem.

Actually, g^q == 1; I don't think that's what you mean.

Now, there is certainly the possibility of the value being in the wrong subgroup; but there are far more than two possibilities.  Here's the entire list for strong groups:

1; that's rejected by the test in section 2.1
p-1; that's also rejected by the test in section 2.1
primitive elements; those are elements r which have order p-1.  These are not rejected by the test.

(in addition, there are KE values that don't correspond to actual group elements; 0 and values >= p; those are rejected too).

Now, there are q-1 different primitive elements; that's more than we could reasonably list.  We could specify a test to reject primitive elements; however, that test isn't cheap (it can be done cheaper than the full r**q==1 test, nevertheless, not cheaply.  In addition, an attacker injecting a primitive element could use it to deduce the lsbit of the private exponent; however that cannot deduce any more than that.  I don't believe that the expense of the full test is worth protecting one bit of the exponent.

> > [[ So far, we have received only *one* review of this document, from
> > Tero. If we don't receive more reviews, the document might not
> > progress due to lack of interest. Please review this document within
> > the next week and contribute your review to the list. ]]
> >
> > Greetings. This is the start of the WG Last Call for
> > draft-ietf-ipsecme-dh-checks; the WG period will end in two weeks, on
> > April 15. The current draft is available at
> > http://tools.ietf.org/html/draft-ietf-ipsecme-dh-checks-01
> >
> > Given that this will be a Standards Track document, it is important for it to
> be reviewed by as many people as possible. Possible results of individual
> reviewing the document are:
> >
> > Many people on this mailing list are IPsec implementers but are mostly or
> completely silent on the mailing list. If you are one of those people, doing a
> WG Last Call review is a good way to participate usefully in the WG. Please
> strongly consider (a) reading the current draft and (b) sending a message to
> the list with your short or long review. If there are too few reviews on this
> document, we could get pushback from the IESG about the document.
> >
> > --Paul Hoffman

---

From: Andrey Jivsov <[email-masked]>
Date: Mon, 08 Apr 2013 17:17:43 -0700

Sorry, I was scanning too quickly.

I meant section 2.1 primes, the primes in the form (renaming my earlier 
definition) p = k*2+1.

Wouldn't receiving g^k be as much of a problem as receiving 1 for the 
public value? No matter what my private exponent is, the shared secret 
will be either of the two values.

---

From: Michael Richardson <[email-masked]>
Date: Mon, 08 Apr 2013 23:01:06 -0400

I read draft-ietf-ipsecme-dh-checks-01.
I am not competent to understand if this addresses a real problem.
I understood that (1 < r < p-1) is a test that many implementors did not
do.    I think that most implementations generated r from a PRNG. 

I have not implemented ECDSA, but the instructions seemed well
formatted, but I don't at this point know what they mean.

-- 
Michael Richardson <[email-masked]>, Sandelman Software Works

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 9 Apr 2013 04:19:20 +0000

> Of Michael Richardson
> Sent: Monday, April 08, 2013 11:01 PM
> To: IPsecme WG

This last statement makes me suspect that you misunderstood what we were doing.

The tests we suggest in this draft are not run on either the secret exponent nor the public value we generate.  Instead, it's run on the value r we receive from the peer's KE payload.  How the peer selects that value isn't our problem (we certainly hope the peer selects it in a way such that a third party can't guess its secret exponent; we can't actually test for that); our problem is deciding whether to accept it or not.

> formatted, but I don't at this point know what they mean.

Actually, we're talking about ECDH here, and not ECDSA.

---

From: Tero Kivinen <[email-masked]>
Date: Tue, 9 Apr 2013 16:05:53 +0300

Scott Fluhrer (sfluhrer) writes:
> Now, there are q-1 different primitive elements; that's more than we
> could reasonably list.  We could specify a test to reject primitive
> elements; however, that test isn't cheap (it can be done cheaper
> than the full r**q==1 test, nevertheless, not cheaply.  In addition,
> an attacker injecting a primitive element could use it to deduce the
> lsbit of the private exponent; however that cannot deduce any more
> than that.  I don't believe that the expense of the full test is
> worth protecting one bit of the exponent. 

Hmm... there is text in the RFC2412 about this I think:
----------------------------------------------------------------------
   Because these two primes are congruent to 7 (mod 8), 2 is a quadratic
   residue of each prime.  All powers of 2 will also be quadratic
   residues.  This prevents an opponent from learning the low order bit
   of the Diffie-Hellman exponent (AKA the subgroup confinement
   problem).  Using 2 as a generator is efficient for some modular
   exponentiation algorithms.  [Note that 2 is technically not a
   generator in the number theory sense, because it omits half of the
   possible residues mod P.  From a cryptographic viewpoint, this is a
   virtue.]
----------------------------------------------------------------------

I assume this the same thing you are talking about i.e. opponent
learning the low order bit of the DH exponent, and RFC2412 claims that
the nature of the primes that attack is not possible. Right?
-- 
[email-masked]

---

From: Michael Richardson <[email-masked]>
Date: Tue, 09 Apr 2013 09:26:42 -0400

>>>>> "sfluhrer" == sfluhrer  <Scott> writes:

    sfluhrer> This last statement makes me suspect that you
    sfluhrer> misunderstood what we were doing. 

    sfluhrer> The tests we suggest in this draft are not run on either
    sfluhrer> the secret exponent nor the public value we generate.
    sfluhrer> Instead, it's run on the value r we receive from the
    sfluhrer> peer's KE payload.  How the peer selects that value isn't
    sfluhrer> our problem (we certainly hope the peer selects it in a
    sfluhrer> way such that a third party can't guess its secret
    sfluhrer> exponent; we can't actually test for that); our problem is
    sfluhrer> deciding whether to accept it or not. 

Yes, I think that I understood that these tests are for what we receive,
and then I must have read something that talked about generation... sec...

Aha.... so:

   o  It MUST check both that the peer's public value is in range (1 < r
      < p-1) and that r**q = 1 mod p (where q is the size of the

...
   o  It MUST NOT reuse DH private values (that is, the DH private value
      for each DH exchange MUST be generated from a fresh output of a

So, in section 2.2 we talk both about what we should do with something
received, and also place a mandate about generating.

Perhaps these things belong in seperate sections.
It seems that from the receiver of g^x's point of view, point two
repeats point one, since the receiver is not in a position to know if
the DH private value was reused.

    >> formatted, but I don't at this point know what they mean.

    sfluhrer> Actually, we're talking about ECDH here, and not ECDSA.

my typo at 11:30pm.

-- 
]               Never tell me the odds!                 | ipv6 mesh networks [ 
]   Michael Richardson, Sandelman Software Works        | network architect  [ 
]     [email-masked]  http://www.sandelman.ca/        |   ruby on rails    [

---

From: Dan Brown <[email-masked]>
Date: Tue, 9 Apr 2013 14:03:20 +0000

> the DH private value was reused.
[DB] The concern is that receiver wants to protect her own reused private key from an invalid public key from a malicious peer.  To do this, the receiver checks the received value to make sure it is valid and safe to combine with her reused private key.  Another option for the receiver is not reusing the private key at all.

---

From: Michael Richardson <[email-masked]>
Date: Tue, 09 Apr 2013 10:33:34 -0400

>>>>> "Dan" == Dan Brown <[email-masked]> writes:

    Dan> [DB] The concern is that receiver wants to protect her own
    Dan> reused private key from an invalid public key from a malicious
    Dan> peer.  To do this, the receiver checks the received value to
    Dan> make sure it is valid and safe to combine with her reused
    Dan> private key.  Another option for the receiver is not reusing
    Dan> the private key at all.  

okay, that wasn't clear to me at all.

When you say "private key", we are talking about the y, not the g^y.

I guess I recall that there are some implementations which calculate
their g^x/g^y, and cache that for many DH operations.  

Is the the point here is that this is safe if we do these tests.

---

From: Yoav Nir <[email-masked]>
Date: Tue, 9 Apr 2013 14:45:37 +0000

Hi

tl;dr: Looks fine, please publish

I am not a cryptographer and not competent to comment on the issues that this draft is trying to solve or on the quality of this solution.

Speaking strictly as a developer, the text is clear and understandable. Doing the mental exercise of estimating what it would take to implement this in my code, it was very easy to add the prescribed tests in the two places they would be needed, with about 5 lines of extra code apiece. (of course it helps to have access to the OpenSSL library with functions such as ec_GFp_simple_is_at_infinity() and ec_GFp_simple_is_on_curve() rather than having to implement them myself)

Yoav

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 09 Apr 2013 09:47:25 -0700

At a closer look,

the quantity g^k = g^(p-1)/2 is 1 or p-1, the values that are eliminated
by the check in section 2.1 for 1 < r < p-1. Given this, the check 1 < r
< p-1 is indeed a nice check for the small subgroup of the safe primes.

( This doesn't take care of a peer doing something silly and using small
exponents, but that's a generic problem. )

On 04/08/2013 05:17 PM, Andrey Jivsov wrote:
> I meant section 2.1 primes, the primes in the form (renaming my
> earlier definition) p = k*2+1.
>
>> "Strong groups", that is, groups with (p-1)/2 prime, are listed in
>> section 2.1; and yes, the test there is considerably cheaper.
>>
>>>
>> Now, there is certainly the possibility of the value being in the
>> wrong subgroup; but there are far more than two possibilities.
>> Here's the entire list for strong groups:
>>
>> (in addition, there are KE values that don't correspond to actual
>> group elements; 0 and values >= p; those are rejected too).
>>
>> elements; however, that test isn't cheap (it can be done cheaper than
>> the full r**q==1 test, nevertheless, not cheaply.  In addition, an
>> attacker injecting a primitive element could use it to deduce the

---

From: Dan Brown <[email-masked]>
Date: Tue, 9 Apr 2013 17:09:10 +0000

> Sent: Tuesday, April 09, 2013 10:34 AM
> 

[DB] Yes (and I'm sorry if I did not use the IPSec terminology, (is it "secret value"?))

> their g^x/g^y, and cache that for many DH operations.

[DB] The implementation would also cache its secret value x (or y).

> Is the the point here is that this is safe if we do these tests.
[DB]  Yes, that is the point.  

I gather the document's motivation was unclear to you.  Were the document's specified actions also unclear to you?

Could you suggest a specific clarification to the document that would correct what made it unclear to you?  

The document reads clearly to me, but its topic is already quite familiar to me.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 9 Apr 2013 19:12:37 +0000

> From: Dan Brown [mailto:[email-masked]]
> Sent: Tuesday, April 09, 2013 1:09 PM
> To: 'Michael Richardson'
> Cc: IPsecme WG; Scott Fluhrer (sfluhrer)
> Subject: RE: [IPsec] NUDGE: WG Last Call for draft-ietf-ipsecme-dh-checks
> 
> I gather the document's motivation was unclear to you.  Were the
> document's specified actions also unclear to you?
> 

It would be of great help  if you (Michael) could explain what was unclear.

The entire point of this draft is to explain how to do some cryptographical checks to someone who is not familiar with cryptography. Hence, any complaint of "I didn't understand that" is valid; it shows that we weren't as clear as we hoped.

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 9 Apr 2013 13:13:17 -0700 (PDT)

Hello,

  I think it looks fine and I have a nit that the authors can ignore
if they like.

  I don't like the fact that RFC 5903 does not list a specific value for
"a" in the parameter set definition and instead just says -3 in the
equation for the curve. This draft does the same sort of thing in
Section 2.3 by saying, "for groups 19, 20, 21,  a=-3, and all other
values of a, b and p for the group are listed in the RFC." Which to
me sounds like it's the same value: minus three.

  Note that RFC 5114 also defines these groups but lists the proper
(to me) value for "a". It's probably not right to just refer to RFC 5114,
especially since RFC 5903 is listed in the repository for those curves,
so my nit would be to change it to "for groups 19, 20, and 21,
a = -3 mod p, and for all other values...." just to let the reader who
might not be so familiar with the topic know that "a" is not the same
for each curve.

  This is a good draft and I'm glad it was written.

  regards,

  Dan.

On Mon, April 8, 2013 2:46 pm, Paul Hoffman wrote:
> [[ So far, we have received only *one* review of this document, from Tero.
> If we don't receive more reviews, the document might not progress due to
> lack of interest. Please review this document within the next week and
> contribute your review to the list. ]]
>
> Given that this will be a Standards Track document, it is important for it
> to be reviewed by as many people as possible. Possible results of
> individual reviewing the document are:
>
> completely silent on the mailing list. If you are one of those people,
> doing a WG Last Call review is a good way to participate usefully in the
> WG. Please strongly consider (a) reading the current draft and (b) sending
> a message to the list with your short or long review. If there are too few
> reviews on this document, we could get pushback from the IESG about the
> document.
>
> --Paul Hoffman

---

From: Johannes Merkle <[email-masked]>
Date: Wed, 10 Apr 2013 14:28:28 +0200

"Looks fine, please publish"

Johannes

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 16 Apr 2013 09:09:08 -0700

+1 to "now that you understand it, please show where you were confused before" so that we can close out the document and move it to the IETF.

--Paul Hoffman

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 16 Apr 2013 09:11:58 -0700

> might not be so familiar with the topic know that "a" is not the same

This sounds like a good clarification. Authors: please revise the draft with this (and whatever text you can to clear up Michael Richardson's earlier confusion).

--Paul Hoffman

---

From: Michael Richardson <[email-masked]>
Date: Tue, 16 Apr 2013 13:01:31 -0400

>>>>> "Paul" == Paul Hoffman <[email-masked]> writes:
    Paul> +1 to "now that you understand it, please show where you were
    Paul> confused before" so that we can close out the document and
    Paul> move it to the IETF. 

sorry, day job got in the way.

rereading section 2.1/2.2 again.

   This leakage can be prevented if the recipient performs a test on the
   peer's public value, however this test is expensive (approximately as
   expensive as what reusing DH private values saves).

does the stuff in () add anything?   And is the word "saves" correct?

   In addition, the
   NIST standard [NIST-800-56A] requires that test (see section
   5.6.2.4), hence anyone needing to conform to that standard will need
   to implement the test anyway.

("that test" refers to the test on the peer's public value?
Visiting NIST-800-56A section 5.6.2.4.. but that section refers to
private/public key pair generation, not MODP groups... but anyway.

my suggested text:

   For a node which wishes to reuse its DH private value, in order
   to avoid this leakage, the following test is to be performed on
   the public value received from the peer before combining it with
   the node's private value.

   While this test is expensive, it is no more expensive than generating
   new DH private values, except that it does not require access to a high
   quality random value.  This test is mandated by the NIST standard
   [NIST-800-56A] (see section 5.6.2.4), and is described here:

   It MUST check both that the peer's public value is in range
   (1 < r < p-1) and that r**q = 1 mod p (where q is the size of the
   subgroup, as listed in the RFC).  
      DH private values MAY then be reused.  
      This option is appropriate if conformance to [NIST-800-56A] is required.

   Alternatively, it MUST NOT reuse DH private values (that is, the DH
   private value 
      for each DH exchange MUST be generated from a fresh output of a
      cryptographically secure random number generator), and it MUST
      check that the peer's public value is in range (1 < r < p-1).
      This option is more appropriate if conformance to [NIST-800-56A]
      is not required.