On 25 September 2017 at 02:32, Mark D. Baushke <mdb at juniper.net> wrote:> [+CC Loganaden Velvindron <logan at hackers.mu>] primary author of > the RFC 4419 refresh draft.https://datatracker.ietf.org/doc/draft-lvelvindron-curdle-dh-group-exchange/ ? Tangent: has any consideration been given to increasing the maximum allowed beyond 8192 bits (which is below the current NIST recommendation for 256 bits of security)? Last time I looked OpenSSL supported 10k bits out of the box so it probably wouldn't be hard to support that in OpenSSH. -- Darren Tucker (dtucker at zip.com.au) GPG key 11EAA6FA / A86E 3E07 5B19 5880 E860 37F4 9357 ECEF 11EA A6FA (new) Good judgement comes with experience. Unfortunately, the experience usually comes from bad judgement.
Hi Darren, Darren Tucker <dtucker at zip.com.au> writes:> Tangent: has any consideration been given to increasing the maximum > allowed beyond 8192 bits (which is below the current NIST > recommendation for 256 bits of security)?Actually, I have given this some thought. For really modern CPUs, this is not completely out of question. However, to connect to the Internet-of-Things, this is likely to be a proble.> Last time I looked OpenSSL supported 10k bits out of the box so it > probably wouldn't be hard to support that in OpenSSH.With the group18 8192-bit MODP prime, we are getting just under 192-bits of security... depending on how you calculate it. (I think I read somewhere that, going to 16384 (2^14) will get us to approximately 229-bits of security and 32768 (2^15) will get us to almost 267-bits of security, but I am unable to find the reference right now.... sigh.) While I have no strong objections to supporting larger than 8192 bit DH groups, I suspect that going for Diffie-Hellman groups that are not based on safe primes would be a better next step. The whole point of using ephemeral safe primes a la RFC 4419, is to make it too difficult to use pre-calculatation tables. It seems reasonable to suppose that there are less safe primes in a bit range than other primes, including provable primes. To be honest, I am uneasy about continuing to use Sophie-Germain and safe primes exclusively. For my effort, I would find it 'better' to consider moving to provable primes. Of course, that would mean sending all three of g,p,q to the client for them to validate that the primes are safe using something like Pocklington's Theorem. This should be fairly quick as such things go. It does mandate a change to the protocol to send q over the wire too. And of course, using provable primes may not mean that one always uses g=2. So, they can be slightly slower. Still, I think that is better than assuming there is not a mathematical short cut for the safe primes we are using today. Right now, both TLS and SSH seem to only use Safe Primes. It would be nice to understand what risks we are running if we move from probable safe primes to provable primes for both q, and p as well as a proper q-subset generator value g. Comments? -- Mark
On Sun 2017-09-24 22:54:12 -0700, Mark D. Baushke wrote:> The whole point of using ephemeral safe primes a la RFC 4419, is to make > it too difficult to use pre-calculatation tables. It seems reasonable to > suppose that there are less safe primes in a bit range than other > primes, including provable primes. > > To be honest, I am uneasy about continuing to use Sophie-Germain and > safe primes exclusively.I don't understand this part. you want to defend against an attacker with cryptanalytic capabilities by *not* using safe primes? Are you expecting everyone operating a server to choose their own random parameters, and to generate primality proofs for them? what's stopping time-starved admins from just copying someone else's group parameters and the associated proofs, thereby creating a de facto common group that's worth mounting a pre-calculation attack for? How are you expecting clients to verify that the groups they're using, while maybe not safe primes, are not in wide use elsewhere? are they supposed to track a list of of parameters they've seen and reject them once they start seeing "too many" of them?> For my effort, I would find it 'better' to consider moving to provable > primes. Of course, that would mean sending all three of g,p,q to the > client for them to validate that the primes are safe using something > like Pocklington's Theorem. This should be fairly quick as such things > go. It does mandate a change to the protocol to send q over the wire > too.are you talking about shipping the proofs in addition to shipping the group parameters? The sizes of the primality proofs of even a 2048-bit prime is about 50KB: https://dkg.fifthhorseman.net/ffdhe-primality-proofs/ They get *much* larger as the size of the primes grows. And verifying them (while not nearly as expensive as generating them) is not something i can imagine any ssh client actually doing before making a connection -- i mean, why should they, when it's cheaper and quicker to just "trust the server" ? (and that's to say nothing about the efficiency gains for the defenders of having pre-computed tables for a known group that can accellerate the fixed-base exponentiation part of DH) Using an a-priori-known, well-vetted, strong group parameters seems like a more reliable approach for the ecosystem as a whole. The proposal being explored in this thread does not seem like a good idea. --dkg
On 09/25/2017 01:54 AM, Mark D. Baushke wrote:> With the group18 8192-bit MODP prime, we are getting just under 192-bits > of security... depending on how you calculate it. > > (I think I read somewhere that, going to 16384 (2^14) will get us to > approximately 229-bits of security and 32768 (2^15) will get us to > almost 267-bits of security, but I am unable to find the reference right > now.... sigh.)According to NIST Special Publication 800-57, Part 1, Revision 4, p. 53, (http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r4.pdf), a 7680-bit modulus is estimated to provide 192 bits of security. Hence, a 8192-bit modulus would provide a little over 192. It also estimates that 256-bits of security is achieved with 15360-bit moduli. - Joe
On 25 September 2017 at 15:54, Mark D. Baushke <mdb at juniper.net> wrote: [...]> For my effort, I would find it 'better' to consider moving to provable > primes. Of course, that would mean sending all three of g,p,q to the > client for them to validate that the primes are safe using something > like Pocklington's Theorem. This should be fairly quick as such things > go. It does mandate a change to the protocol to send q over the wire > too.I'm not a cryptographer so I defer to others on the cryptography and number theory. As an maintainer I guess the counter argument to that is that if you need something stronger that the current dh-gex and you have to implement something new anyway then you'd be much better off implementing ecdh or ssh-curves and get something much faster for the equivalent strength. What is the intersection of people wanting >192 bits of security and wanting to (or being required to) stick with dh-gex? -- Darren Tucker (dtucker at zip.com.au) GPG key 11EAA6FA / A86E 3E07 5B19 5880 E860 37F4 9357 ECEF 11EA A6FA (new) Good judgement comes with experience. Unfortunately, the experience usually comes from bad judgement.