Re: [IPsec] Question about RFC 5114

"Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com> Sat, 27 March 2010 02:48 UTC

Return-Path: <sfluhrer@cisco.com>
X-Original-To: ipsec@core3.amsl.com
Delivered-To: ipsec@core3.amsl.com
Received: from localhost (localhost [127.0.0.1]) by core3.amsl.com (Postfix) with ESMTP id 07DEE3A6C58 for <ipsec@core3.amsl.com>; Fri, 26 Mar 2010 19:48:25 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -9.469
X-Spam-Level:
X-Spam-Status: No, score=-9.469 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, DNS_FROM_OPENWHOIS=1.13, RCVD_IN_DNSWL_HI=-8]
Received: from mail.ietf.org ([64.170.98.32]) by localhost (core3.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id EBMOtt7LTiOC for <ipsec@core3.amsl.com>; Fri, 26 Mar 2010 19:48:23 -0700 (PDT)
Received: from sj-iport-6.cisco.com (sj-iport-6.cisco.com [171.71.176.117]) by core3.amsl.com (Postfix) with ESMTP id D29FB3A6A2C for <ipsec@ietf.org>; Fri, 26 Mar 2010 19:48:23 -0700 (PDT)
Authentication-Results: sj-iport-6.cisco.com; dkim=neutral (message not signed) header.i=none
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Av0EAAUPrUurR7H+/2dsb2JhbACDGZc4XHOlHog9kGCBK4JpagSDHg
X-IronPort-AV: E=Sophos;i="4.51,318,1267401600"; d="scan'208";a="503792590"
Received: from sj-core-2.cisco.com ([171.71.177.254]) by sj-iport-6.cisco.com with ESMTP; 27 Mar 2010 02:48:48 +0000
Received: from xbh-sjc-221.amer.cisco.com (xbh-sjc-221.cisco.com [128.107.191.63]) by sj-core-2.cisco.com (8.13.8/8.14.3) with ESMTP id o2R2mmin014987; Sat, 27 Mar 2010 02:48:48 GMT
Received: from xmb-sjc-23e.amer.cisco.com ([128.107.191.15]) by xbh-sjc-221.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.3959); Fri, 26 Mar 2010 19:48:48 -0700
X-MimeOLE: Produced By Microsoft Exchange V6.5
Content-class: urn:content-classes:message
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
Date: Fri, 26 Mar 2010 19:48:42 -0700
Message-ID: <EE0C2F9E065E634B84FC3BE36CF8A4B2034074E1@xmb-sjc-23e.amer.cisco.com>
In-Reply-To: <1269638701.2838.303.camel@faith.austin.ibm.com>
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
Thread-Topic: [IPsec] Question about RFC 5114
Thread-Index: AcrNLdpr6ZJzRGD+TzKMSY5v7IUs1QAAOhXw
X-Priority: 5
Priority: Non-Urgent
Importance: low
References: <1269638701.2838.303.camel@faith.austin.ibm.com>
From: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
To: latten@austin.ibm.com, mlepinski@bbn.com, kent@bbn.com
X-OriginalArrivalTime: 27 Mar 2010 02:48:48.0163 (UTC) FILETIME=[0665C730:01CACD58]
Cc: ipsec@ietf.org, avagarwa@redhat.com
Subject: Re: [IPsec] Question about RFC 5114
X-BeenThere: ipsec@ietf.org
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: Discussion of IPsec protocols <ipsec.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/listinfo/ipsec>, <mailto:ipsec-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/ipsec>
List-Post: <mailto:ipsec@ietf.org>
List-Help: <mailto:ipsec-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/ipsec>, <mailto:ipsec-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sat, 27 Mar 2010 02:48:25 -0000


> -----Original Message-----
> From: ipsec-bounces@ietf.org [mailto:ipsec-bounces@ietf.org] On Behalf
> Of Joy Latten
> Sent: Friday, March 26, 2010 5:25 PM
> To: mlepinski@bbn.com; kent@bbn.com
> Cc: ipsec@ietf.org; avagarwa@redhat.com
> Subject: [IPsec] Question about RFC 5114
> 
> Hi,
> 
> I am looking to implement modp groups 22, 23, and 24 into IKE but have
> a
> question.
> 
> RFC 5114 gives the prime, p, the generator, g and a subgroup, q, with a
> specific size...
> 
> Because prior rfcs for modp groups did not specify a "q", I was not
> sure
> if this was a new constant or just stating a size requirement?

q is the order of the generator.  For the previous (traditional) MODP groups (1,2,5,14-18), we have q=(p-1)/2

> So I took a look at NIST 800-56A. In particular,
> 
> 5.6.1 Private/Public Key Pair Generation
> 
> 5.6.1.1 FFC Key Pair Generation
> For the FFC schemes, each static and ephemeral private key and public
> key shall be generated using an Approved method and the selected valid
> domain parameters (p, q, g{, SEED,pgenCounter}) (see Appendix B of FIPS
> 186-3).
> ...
> 
> I then took a look at FIPS 186-3, Appendix B, which documents 2 methods
> for finite field cryptography (FFC) key pair generation.
> For example, one method is "Key Pair Generation Using Extra Random
> Bits". It actually states that "q" is an input and it is used to do an
> additional computation to compute "x".
> 
> I am somewhat confused, are the modp groups 22, 23 & 24 suppose to use
> one of these new methods and that is why "q" is given in rfc 5114?
> Or am I to ignore this and just continue with existing way
> where "q" is not used and there aren't any additional computations
> to compute x.

Short answer: it doesn't really matter; the old way is safe (for DH).

Longer answer: FIPS 186-3 was written about generating values for DSA, not DH.  Now, for DSA, there is a known weakness if the exponents you use are biased; these algorithms used in FIPS 186-3 were designed to make sure that the exponents are unbiased (or close enough not to matter).  DH doesn't have similar issues, and so these steps aren't required (although they wouldn't hurt either).

Now, you don’t need to use the same exponent size that you would use for the same size traditional groups; for example, RFC3526 suggests an exponent of between 220-320 bits for group 14; for group 24, there's no point in an exponent greater than 256 bits.  This is because the exponent is essentially taken "mod q" by the algorithm, and so making it larger than q gives you more work without giving any benefit.  Note that when FIPS 186-3 talks about using "extra random bits", they reduce the larger value so that it is <q (step 6 of B.1.1).


On the other hand, NIST SP 800-56A also asks you to validate the peer public value (section 5.6.2.4), and this also uses q as an input.  Here's why that really does matter for groups 22-24 (and not so much for groups 1,2,5,14-18):

- If you reuse DH exponents, and you don't validate the peer's public value, then there is a way for an attacker to determine the value of your exponent modulo r, where r is a small factor of (p-1)/q.
- This attack involves sending illegal peer public values as a part of the IKE exchange, and seeing what keying material the unit comes up with.  Because these values are illegal, validating the values foils the attack.
- This takes O(r) time on the attacker's part, which is why r can't be too large.

For the traditional groups, (p-1)/q == 2, and so r=2 is the only one the attacker can use (hence the attacker would be able to determine the lsbit of your exponent via this attack, but nothing else).  It turns out that there's a short cut to test on the peer public value in this case (compute the Legendre symbol), but even if you don't, the attacker gets minimal information.

For these new groups, (p-1)/q is quite large, and in all three cases, has a number of small factors (now, NIST could have defined groups where (p-1)/q has 2 as the only small factor; they declined to do so).  For example, for group 23 (which is the worse of the three), (p-1)/q ==  2 * 3 * 3 * 5 * 43 * 73 * 157 * 387493 * 605921 * 5213881177 * 3528910760717 * 83501807020473429349 * C489 (where C489 is a 489 digit composite number with no small factors).  The attacker could use this (again, if you don't validate the peer value) to effective cut your exponent size by about 137 bits with using only  O(2**42) time); if you used 224 bit exponents, then the attacker would cut the work used to find the rest of the exponent to about O(2**44) time.  Obviously, this is not acceptable.



> 
> I am not even sure this is correct place to ask, but any advice
> would be welcome.
> 
> regards,
> Joy
> 
> 
> (Cut-n-paste from FIPs 186-3 below to show input and process)
> 
>  Input:
>     (p, q, g)      The subset of the domain parameters that are used
>                    for this process. p, q and g shall either be
>                    provided as integers during input, or shall be
>                    converted to integers prior to use.
> 
> Process:
> 1. N = len(q); L = len(p).    Comment: Check that the (L, N) pair
>                               is specified in Section 4.2.
> 2. If the (L, N) pair is invalid, then return an ERROR indicator,
>    Invalid_x, and Invalid_y.
> 3. requested_security_strength = the security strength associated
>    with the (L, N) pair;      see SP 800-57.
> 4. Obtain a string of N+64 returned_bits from an RBG with a security
>    strength of requested_security_strength or more. If an ERROR
>    indication is returned, then return an ERROR indication,
>    Invalid_x, and Invalid_y.
> 5. Convert returned_bits to the (non-negative) integer c (see
>    Appendix C.2.1).
> 6. x = (c mod (q–1)) + 1.       Comment: 0 ≤ c mod (q–1) ≤ q–2 and
>                                 implies that 1 ≤ x ≤ q–1.
> 7. y = gx mod p.
> 8. Return SUCCESS, x, and y.
> 
> _______________________________________________
> IPsec mailing list
> IPsec@ietf.org
> https://www.ietf.org/mailman/listinfo/ipsec