Re: [STDS-802-11-TGAI] TDS-802-11-TGAI] A suggestion to clean up the list of IANA groups that 802.11ai should consider -- i.e., ditch roughly 40% of those as inadequate (was: Re: [STDS-802-11-TGAI] modp group question)

[Dan Harkins <dharkins@xxxxxxxxxxxxxxxxx>]

  Hi Rene,

On 3/21/13 6:41 PM, "Rene Struik" <rstruik.ext@xxxxxxxxx> wrote:

>Dear Tero:
>
>Thanks for your response regarding the expression of my concern re
>a) security of Sophie-Germain groups;
>b) security aspects of using "2" as a generator;
>c) computational complexity.
>
>While I do appreciate your informal assessments, I am not sure whether
>those would have sufficient merit to sway 802.11ai into using those
>groups.

  I'm somewhat shocked that you're trying to sway 802.11ai into not using
these groups. 

>Wouldn't you agree that avoiding those groups altogether, at least for
>802.11, would make for less navigation of potentially very choppy waters?

  Absolutely not. I think any chop in the water is due to this thread.
Stop this thread and you stop the choppy waters.

> From your note I get the impression that it is fine to use
>Sophie-Germain groups since
>a) while cutting corners in truncating ephemeral private keys
>(presumably to make performance acceptable) may create strong biases,
>these might be compensated for by
>opening a vast arsenal of tricks;
>b) while tricks may seriously impact performance (and may land us into
>"nontechnical" minefields), there are ways to cut corners here as well,
>seemingly without impact;
>c) while performance may be quite poor, one could do computations
>offline and reuse ephemerals to fair somewhat better. And, there is
>always hardware...

  These groups are used every day without problem. There is no reason
why 11ai can't do the same.

>Let us assume that one accepts those arguments on face value. Wouldn't
>there then still be an issue using Sophie-Germain groups with 802.11ai
>in the "non-TTP case"? After all, there one needs DSS signature, where
>if one were to use the Sophie-Germain arsenal of tricks, one would
>essentially use private keys where roughly 80-90% of the private key
>bits are known? Again, the literature is full of examples where knowing
>just 1-2% (e.g., 3-4 out of 256 bits) has disastrous ripple effect.

  I don't understand why you keep trying to use these groups for DSS
signature! That is not how 11ai is defining their use. They are used
in 11ai only for doing the Diffie-Hellman exchange. This discussion
of DSS is a distraction.

>Rather than trying and finding strong technical evidence that supports
>informal "gut-feel" (no better how appealing this sounds), wouldn't it
>be much better to just avoid going that route altogether (at least for
>802.11 purposes) and simply use Diffie-Hellman groups for which safe use
>seems to involve less "navigation of treacherous waters".

  I see no evidence of treacherous waters.

>Thus, unless one can dig up all the strong technical evidence, it seems
>that foregoing more or less 40% of the IANA curves, at least for 802.11
>use, seems the "wiser" approach? The remaining roughly 60% of IANA
>curves would still work and often much better, with less security
>headaches, more in line with the directions practice-based crypto is
>moving in the world, and with quite reasonable and sometimes even
>(almost) great performance.

  "Practice-based crypto"? You mean like IKE that's deployed throughout
the world and is using these groups right this very second (if you have
VPN software on any computer of yours, chances are it is using one of
these groups). I am unaware of any "headaches" that anyone has by using
these curves today.

>Would you agree? (at least for 802.11's purposes)?

  No, absolutely not.

  Are you be, perhaps, trying to lay the groundwork for a proposal to use
binary curves?

  Dan.


>Best regards,
>
>Rene
>
>
>a) ditch all discrete log groups based on Sophie-Germain groups, since
>possibly having security problems (presumably #1, #2, #5, #14-#18 of the
>IANA list);
>> b) ditch the elliptic curve groups over composite extension fields, that
>> have long ago been ditched elsewhere (ditch #3, #4).
>
>
>On 3/21/2013 9:58 AM, Tero Kivinen wrote:
>> Rene Struik writes:
>>> Thanks for the feedback: If the big group has as cardinality a "safe
>>> prime" of the form p=2*q+1 (where q is prime as well), as you suggest,
>>> then the subgroup's size q is indeed known. I could not find this in
>>>the
>>> RFC though.
>> When RFC 3526 was written it was clear it was generating similar
>> groups that was originally generated in RFC2412. The RFC 3526 do have
>> RFC 2412 as non-normative reference, but the reference to that draft
>> is missing from the abstract where it says that:
>>
>> ----------------------------------------------------------------------
>>     The selection of the primes for theses groups follows the criteria
>>     established by Richard Schroeppel.
>> ----------------------------------------------------------------------
>>
>> that should have said "Richard Schroeppel [RFC2412]"...
>>
>>
>>> Some comments:
>>>
>>> 1) Security (a).
>>> Indeed, one could use small-size t-bit exponents in a subgroup G of
>>>size
>>> q of Zp, where p=1+2*q. However, it may lead to quite biased
>>> distributions that would not have been there if the private exponents
>>> would have been random integers in the range [1,q-1], as is nowadays
>>> (2013) "the norm". As an example, with a 3072-bit discrete log group Zp
>>> and 256-bit exponents, the key K:=g^d has as pre-image all 256-bit
>>> integers x and y for which x*y=d. Hence, the number of preimages
>>>depends
>>> on the factorization of d (e.g., if d is a prime number in the range
>>> {512-bit}\{256-bit}, this set would be empty; if d is a 128-bit prime,
>>> it has two pre-images {(1,d), (d,1)}, etc.). With drawing private keys
>>> from the entire set [1,q-1], one gets a flat distribution of the
>>>integer
>>> d in the range [1,q-1]. Whether this is really exploitable is another
>>> question of course. However, this seems to be a red flag to me and
>>>might
>>> suggest that perhaps this 2003 RFC might be somewhat dated? Are there
>>> any papers that have studied the non-standard DLP problem that seems to
>>> be underlying the suitability of the groups suggested in this RFC
>>> document? (I know those with random exponents from [1,q-1], but none
>>> where one simply truncates and "hopes for the best".)
>> I have not heard that there is problem with those groups when using
>> them for Diffie-Hellman calculations. The output of the Diffie-Hellman
>> calculation should have entropy based on the input parameters, and
>> yes, it is not uniformly distributed over the resulting output, which
>> is one of the reasons you cannot simply take truncated output of the
>> Diffie-Hellman output and use that. Instead of that you need to use
>> proper Key Derivation Function that extracts the entropy from the
>> output.
>>
>> Or are you referenceing to something else?
>>
>>> 2) Security (b).
>>> All discrete log groups Zp, where p=2*q+1 and q prime, have 2 as
>>> generator. This may easily leak info on the lower-order ~dozen bits of
>>> the computation of the ephemeral key contribution via side channel
>>> analysis (after all, 2^t (mod p) does not require modular reduction if
>>> t< len(p)).
>> If you are referencing to the timing attacks, see section 5 from the
>> RFC2412, which says:
>> ----------------------------------------------------------------------
>> 5. Security Implementation Notes
>>
>>     Timing attacks that are capable of recovering the exponent value
>>used
>>     in Diffie-Hellman calculations have been described by Paul Kocher
>>     [Kocher].  In order to nullify the attack, implementors must take
>>     pains to obscure the sequence of operations involved in carrying out
>>     modular exponentiations.
>>
>>     A "blinding factor" can accomplish this goal.  A group element, r,
>>is
>>     chosen at random.  When an exponent x is chosen, the value r^(-x) is
>>     also calculated.  Then, when calculating (g^y)^x, the implementation
>>     will calculate this sequence:
>>
>>             A = (rg^y)
>>             B = A^x = (rg^y)^x = (r^x)(g^(xy))
>>             C = B*r^(-x) = (r^x)(r^-(x))(g^(xy)) = g^(xy)
>>
>>     The blinding factor is only necessary if the exponent x is used more
>>     than 100 times (estimate by Richard Schroeppel).
>> ----------------------------------------------------------------------
>>
>> In most cases the private exponent x is not reused at all, in which
>>case there is no need to do this kind of blinding.
>>
>>> 3) Performance (in context of 802.11ai's charter).
>>> Use of one of the "enormous size" IANA groups, leads to signatures
>>>(r,s)
>> We did also generate enourmous size groups while we created those
>> medium sized groups defined in the RFC 3526. We did generate 12288 and
>> 16384 bit groups too, and did generate primality proofs for those too,
>> but those were not published in the RFC, as they were considered too
>> big for practical use (i.e. enourmous size :-)
>>
>>> of size ~ len(p) + t and public keys of size len(p) and signature
>>> verification requiring scalars of full-size len(p). For 802.11ai FILS,
>>> use of 2048-bit primes with DH key agreement would probably have cost
>>>of
>>> roughly 1/8-th RSA-2048 no-CRT decryption or 1/2 an RSA-CRT-2048
>>> decryption. If one uses this with signing ("no TTP case"), the (at
>>> least) two signature verification cost roughly at least 2x a full
>>> 2048-bit RSA no CRT decryption or 8 times an RSA-CRT-2048 decryption.
>>> This begs the question whether supporting these huge discrete logs
>>> groups with 802.11ai would be in the interest of fullfilling its
>>>charter
>>> ("F" in FILS was supposed to stand for "Fast").
>> That also depends on the hardware. Normal 5 years old PC can do about
>> 100 2048-bit Diffie-Hellman operations per second (both setup and
>> agreement), i.e. 50ms per operation. Half of that can be done offline,
>> i.e. before the client connects, other half needs to be done online.
>>
>> If that is not fast enough, then adding modp hardware will make it
>> faster...
>>
>>> Given the above, it seems to serve 802.11ai well to
>>> a) ditch all discrete log groups based on Sophie-Germain groups, since
>>> possibly having security problems (presumably #1, #2, #5, #14-#18 of
>>>the
>>> IANA list);
>> I would like to know more about these security problems?
>>
>>> b) ditch the elliptic curve groups over composite extension fields,
>>>that
>>> have long ago been ditched elsewhere (ditch #3, #4).
>> That I do agree...
>
>
>-- 
>email: rstruik.ext@xxxxxxxxx | Skype: rstruik
>cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
>
>__________________________________________________________________________
>_____
>
>IF YOU WISH to be Removed from this reflector, PLEASE DO NOT send your
>request to this
>CLOSED reflector. We use this valuable tool to communicate on the issues
>at hand.
>
>SELF SERVICE OPTION:
>Point your Browser to -
>http://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGAI and
>then amend your subscription on the form provided.  If you require
>removal from the reflector
>press the LEAVE button.
>
>Further information can be found at:
>http://www.ieee802.org/11/Email_Subscribe.html
>__________________________________________________________________________
>_____

_______________________________________________________________________________

IF YOU WISH to be Removed from this reflector, PLEASE DO NOT send your request to this
CLOSED reflector. We use this valuable tool to communicate on the issues at hand.

SELF SERVICE OPTION:
Point your Browser to - http://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11-TGAI and
then amend your subscription on the form provided.  If you require removal from the reflector
press the LEAVE button.

Further information can be found at: http://www.ieee802.org/11/Email_Subscribe.html
_______________________________________________________________________________