Re: [STDS-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>]

  Rene,

  These groups are for doing a Diffie-Hellman, not for digital signatures.
FILS does not have a way to specify what kind of key is certified-- i.e.
what ends up in a certificate-- and is agnostic on the whole subject.

  There is no reason to "ditch" any of the valid groups that 802.11
supports today, including these "enormous size" groups. Keep in mind
that these groups are also used to provide PFS to the FILS authentication
mode that does not even use certs!

  Dan.

On 3/20/13 2:52 PM, "Rene Struik" <rstruik.ext@xxxxxxxxx> wrote:

>Hi Tero:
>
>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.
>
>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".)
>
>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)).
>
>3) Performance (in context of 802.11ai's charter).
>Use of one of the "enormous size" IANA groups, leads to signatures (r,s)
>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").
>
>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);
>b) ditch the elliptic curve groups over composite extension fields, that
>have long ago been ditched elsewhere (ditch #3, #4).
>In short, this leaves only the so-called NIST curves (and, possibly, #6
>-- although I am not sure who would practically plan to use this with
>802.11ai).
>
>On 3/20/2013 5:08 PM, Tero Kivinen wrote:
>> Rene Struik writes:
>>> RFC 3526 specifies a number of MODP groups Zp, but does not seem to
>>> specify the order q of the prime-order subgroup G of Zp\{0}  to be used
>>> with DH. The RFC document does not mention what the presumed
>>> cryptographic bit strength of any of these discrete log groups is. Do
>>> you know where the q-values in RFC 3526 are defined?
>> All the group specified in the RFC3526 are generated using rules set
>> in the RFC2412, i.e. they are Sophie Germain primes. That means p and
>> (p-1)/2 are both primes, and if I have understood correctly the order
>> q of the prime-order subgroup is that (p-1)/2.
>>
>> See Appendix E in RFC2412 for information how those groups were
>> generated.
>>
>>> This topic came up, since 802.11ai/D0.4 refers to the IANA DLP groups
>>>as
>>> allowed groups for FILS authentication.
>>>
>>> For specification purposes, one needs to know
>>> a) presumed cryptographic bit strength;
>> As the strength estimates between different cryptographers changes
>> depending what kind of estimation is used, the RFC 3526 section 8
>> includes two different values:
>>
>>     +--------+----------+---------------------+---------------------+
>>     | Group  | Modulus  | Strength Estimate 1 | Strength Estimate 2 |
>>     |        |          +----------+----------+----------+----------+
>>     |        |          |          | exponent |          | exponent |
>>     |        |          | in bits  | size     | in bits  | size     |
>>     +--------+----------+----------+----------+----------+----------+
>>     |   5    | 1536-bit |       90 |     180- |      120 |     240- |
>>     |  14    | 2048-bit |      110 |     220- |      160 |     320- |
>>     |  15    | 3072-bit |      130 |     260- |      210 |     420- |
>>     |  16    | 4096-bit |      150 |     300- |      240 |     480- |
>>     |  17    | 6144-bit |      170 |     340- |      270 |     540- |
>>     |  18    | 8192-bit |      190 |     380- |      310 |     620- |
>>     +--------+----------+---------------------+---------------------+
>>
>>> b) value of order q of prime order subgroup.
>> (p-1)/2.
>>
>>> The value of q is required for use of DSS with the groups in question
>>> (since signatures have size roughly 2*bit-size(q)). The presume
>>> bit-strength would help in specifying which hash functions are supposed
>>> to be used of "matching" security strength.
>
>
>-- 
>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
_______________________________________________________________________________