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

Andrey Jivsov <openpgp@brainhub.org> Tue, 09 April 2013 16:49 UTC

Return-Path: <openpgp@brainhub.org>
X-Original-To: ipsec@ietfa.amsl.com
Delivered-To: ipsec@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 4FD3D21F9367 for <ipsec@ietfa.amsl.com>; Tue, 9 Apr 2013 09:49:57 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.437
X-Spam-Level:
X-Spam-Status: No, score=-0.437 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, FH_RELAY_NODNS=1.451, HELO_MISMATCH_NET=0.611, RDNS_NONE=0.1]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id iuvLSayq4RAz for <ipsec@ietfa.amsl.com>; Tue, 9 Apr 2013 09:49:56 -0700 (PDT)
Received: from qmta05.emeryville.ca.mail.comcast.net (qmta05.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:48]) by ietfa.amsl.com (Postfix) with ESMTP id 7D8BD21F9382 for <ipsec@ietf.org>; Tue, 9 Apr 2013 09:49:56 -0700 (PDT)
Received: from omta01.emeryville.ca.mail.comcast.net ([76.96.30.11]) by qmta05.emeryville.ca.mail.comcast.net with comcast id Mqyg1l0030EPchoA5spwMg; Tue, 09 Apr 2013 16:49:56 +0000
Received: from [127.0.0.1] ([69.181.162.123]) by omta01.emeryville.ca.mail.comcast.net with comcast id Mspv1l0062g33ZR8MspvpZ; Tue, 09 Apr 2013 16:49:55 +0000
Message-ID: <5164461D.3070701@brainhub.org>
Date: Tue, 09 Apr 2013 09:47:25 -0700
From: Andrey Jivsov <openpgp@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130110 Thunderbird/17.0.2
MIME-Version: 1.0
To: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
References: <9F821C79-A855-4060-A356-ED8E5C50048B@vpnc.org> <51634894.1030306@brainhub.org> <A113ACFD9DF8B04F96395BDEACB34042090604F1@xmb-rcd-x04.cisco.com> <51635E27.9020907@brainhub.org>
In-Reply-To: <51635E27.9020907@brainhub.org>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20121106; t=1365526196; bh=6wmL7+UoMenwkZN5OjU6/rC6BPWHT2aK6JUuK8s7pyQ=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=pKClkyf7j/RyQQCgAVImLNSSgwRoO9qgowTFSZ6ofV35ijwVtS3d/E2UTDRMbMjd7 83WmIQcp8IQR6znK/baNqgxbBFx8cGOfMPHSXy3qOSumFJBuMmdB+EOsKJzBXZqYmX cKC9yscIGipi8dgY9owSlv+su95H7pzjoONRApA0chhh0SvghvSfAh5WmUT0p3xkvU /wm9DP0541UmtLkqGxk2mDPnYsT9SBiVlBDKLiUDq4hSG5YsOpcOizNocPmDSGtMTj 4Y6H/0vs5XUPTOhYBVOKQOWGPA4TwhB7Y5VBkm9JtAY7dhJQZBuhLS0xsNAH4tfe0k cwL1WDkmNcqMQ==
Cc: "ipsec@ietf.org" <ipsec@ietf.org>
Subject: Re: [IPsec] NUDGE: WG Last Call for draft-ietf-ipsecme-dh-checks
X-BeenThere: ipsec@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Discussion of IPsec protocols <ipsec.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/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: Tue, 09 Apr 2013 16:49:57 -0000

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:
> 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.
>
> On 04/08/2013 04:15 PM, Scott Fluhrer (sfluhrer) wrote:
>>
>>
>>> -----Original Message-----
>>> From: ipsec-bounces@ietf.org [mailto:ipsec-bounces@ietf.org] On Behalf
>>> Of Andrey Jivsov
>>> Sent: Monday, April 08, 2013 6:46 PM
>>> To: ipsec@ietf.org
>>> Subject: Re: [IPsec] NUDGE: WG Last Call for
>>> draft-ietf-ipsecme-dh-checks
>>>
>>> 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?
>>
>> "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.
>>
>>>
>>> On 04/08/2013 02: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. ]]
>>>>
>>>> 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
>>>> IPsec@ietf.org
>>>> https://www.ietf.org/mailman/listinfo/ipsec
>>>>
>>>> _______________________________________________
>>>> IPsec mailing list
>>>> IPsec@ietf.org
>>>> https://www.ietf.org/mailman/listinfo/ipsec
>>>>
>>>
>>> _______________________________________________
>>> IPsec mailing list
>>> IPsec@ietf.org
>>> https://www.ietf.org/mailman/listinfo/ipsec
>