Daniel Kahn Gillmor <d...@fifthhorseman.net> writes: > On Fri 2013-12-06 15:12:57 -0500, Niels Möller wrote: > >> For DH, I don't think there's any particular reason to prefer to work in >> a small subgroup. But I may be missing something, of course. > > I can think of a few, but i'm not sure how legitimate they are:
[...] > another might be efficiency of modular exponentiation: if you use > exponentiation by squaring, then the cost of calculating A' = g^A mod p > where A < q should be O(log_2(q)) instead of O(log_2(p)) where A < p. > So if q has half the bits of p, you'd halve the amount of computation. And on the other hand, you just pointed out a potential problem on the ietf-ssh mailing list: The selection of a discrete log group with a subgroup of targeted size q (instead of using a group with a safe prime modulus, which only allows subgroups of at worst (p-1)/2 if you exclude (p-1) as a valid public key) makes it costly to check whether the peer is forcing your shared secret into one of the other smaller subgroups. If the subgroup is of prime size q, then you can check if an element x belongs to that subgroup by checking that x^q = 1 (mod p). Right? Is that too expensive? And that subgroup in turn has no proper subgroups. Even with this additional check, it could be significantly faster than using the large group, in particular if one uses tricks to compute x^q and x^e (where e is your local and secret dh exponent) together. This could still be Note that this kind of subgroup-forcing attack was used in the DHE variant of Bhargavan et al's recent attack against client certification in TLS (other mistakes in the TLS protocol played a role in these attacks too, of course) I haven't read up on this. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance. _______________________________________________ nettle-bugs mailing list nettle-bugs@lists.lysator.liu.se http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
