| Thread Links | Date Links | ||||
|---|---|---|---|---|---|
| Thread Prev | Thread Next | Thread Index | Date Prev | Date Next | Date Index |
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 toa) 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 _______________________________________________________________________________