x/crypto/ssh: DH SHA256 is extremely slow due to primality check #41151

dacohen · 2020-09-01T01:14:06Z

What version of Go are you using (`go version`)?

1.14.6

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (`go env`)?

go env Output

GOHOSTARCH="amd64"
GOHOSTOS="darwin"

What did you do?

I opened an SSH connection to a server advertising diffie-hellman-group-exchange-sha256 key exchange, with a 512 byte prime. I appended this KEX mode to the allowed KeyExchanges as follows:

config := &ssh.ClientConfig{
		User: username,
		Auth: []ssh.AuthMethod{
			ssh.Password(password),
		},
		HostKeyCallback: acceptKeyFn,
		Timeout: 30 * time.Second,
	}
config.Config.SetDefaults()
config.Config.KeyExchanges = append(config.Config.KeyExchanges, "diffie-hellman-group-exchange-sha256")

result, err := ssh.Dial("tcp", "server:22", config)

What did you expect to see?

I expected ssh.Dial to return within a few seconds.

What did you see instead?

ssh.Dial takes over 40 seconds to return. After investigation, it appears almost the entirety of that time is spent on the following check, in ssh/kex.go:609:

if !gex.p.ProbablyPrime(numMRTests) || !pHalf.ProbablyPrime(numMRTests) {
		return nil, fmt.Errorf("ssh: server provided gex p is not safe")
}

I added timing code around this block to determine how much time is spent.

For the 256 byte key used in the test case (ssh/kex.go:711), this takes approximately 800ms on average. However, for a 512 byte key, it balloons to 42 seconds on average, which generally causes the server to close the connection before the client can respond.

It seems that this can be mitigated either by removing this sanity check entirely, or scaling down the number of bases ProbablyPrime checks as the size of the prime increases.

If you're able to provide guidance on the correct approach, I'm happy to contribute a fix.

The text was updated successfully, but these errors were encountered:

ALTree · 2020-09-01T11:08:36Z

cc @FiloSottile @hanwen

const numMRTests = 64 seems excessive to me. Even if we want to use Miller-Rabin for the safety checks, 40 rounds seem more than enough. But we could also use ProbablyPrime(0), which skips Miller-Rabin and only does Baillie–PSW. There are no known composite numbers that pass the test.

How slow it is with 1) numMRTests = 40 2) numMRTests = 0 (only Baillie–PSW)?

dacohen · 2020-09-01T12:38:37Z

Here are the timings for 40 rounds:
256 byte prime: 563 ms
512 byte prime: 27 seconds

And for 0 rounds (only Baillie–PSW):
256 byte prime: 47 ms
512 byte prime: 1.8 seconds

Based on these results, it seems that removing Miller-Rabin entirely is the way to go. Although, even with that optimization, the primality check still accounts for about 50% of the total time spent in ssh.Dial when using a 512 byte prime (1.8 seconds out of 3.6 seconds).

FiloSottile · 2020-09-01T12:56:41Z

It does sounds like just running Baillie-PSW would be acceptable per https://eprint.iacr.org/2018/749.pdf.

How does OpenSSH handle this? Do they just let the peer pick a potentially composite number?

This is why this KEX is not enabled by default and why I was opposed to implementing it, FWIW. Negotiating parameteres requires uncomfortable performance/security tradeoffs.

hanwen · 2020-09-01T12:58:49Z

I have stepped down as a maintainer for go ssh.

If you care about performance, I would suggest to not use the group exchange. Both ECDH and Ed25519 are much faster.

the group exchange was suggested as a mitigation of logjam attacks, which affect 1024-bit (ie. 128byte) pre-agreed primes, because it costs "only" hundreds of millions dollars to calculate the discrete log for 1024 bit primes.

What application both requires the advanced security that humongous 512 byte primes bring, but also cannot upgrade to a stronger set of algorithms?

ALTree · 2020-09-01T13:11:49Z

I have stepped down as a maintainer for go ssh.

@hanwen Thanks for letting me know. FYI https://dev.golang.org/owners still lists you as the primary maintainer of crypto/ssh. We may want to amend the document.

dacohen · 2020-09-01T13:27:13Z

What application both requires the advanced security that humongous 512 byte primes bring, but also cannot upgrade to a stronger set of algorithms?

We're trying to connect to a third-party server that only advertises this key exchange.

How does OpenSSH handle this? Do they just let the peer pick a potentially composite number?

It appears so, yes. There's no mention of primality testing in the OpenSSH key exchange logic, as far as I can tell. Here's the link, if anyone wants to verify: https://github.com/openssh/openssh-portable/blob/master/kexgexc.c

FiloSottile · 2020-09-01T13:51:01Z

I suppose that any meaningful attack would have to be a MitM, and if the host key signature is over a decent transcript, it might not be possible to change parameters. I don't know enough about the protocol to say that for sure, so it would help if someone could hack an SSH server to send a composite "prime" and check that OpenSSH will connect to it.

hanwen · 2020-09-01T13:58:34Z

Maybe these parameters https://go.googlesource.com/crypto/+/5c72a883971a4325f8c62bf07b6d38c20ea47a6a/ssh/kex.go#563 should be softcoded? Or the upper bound could be set at 2048 bits too? Or something more conservative, eg. 3072 bits?

I'll send a change for the owners file.

dacohen · 2020-09-01T18:56:25Z

Per @FiloSottile's suggestion, I updated the /etc/ssh/moduli file used by OpenSSH to only contain a single "prime" that's the product of two random numbers, and is therefore guaranteed to be composite.

I ran Wireshark while opening a connection with the OpenSSH client from another machine, and was able to observe the fake prime I added being exchanged as part of the DH handshake. No errors or warnings were returned, which supports the idea that OpenSSH does not do any primality testing as part of DH handshakes.

If the primality check is changed to only use Baillie–PSW, then the handshake will be more secure than the OpenSSH implementation, while incurring only a minimal performance penalty.

FiloSottile · 2020-09-01T19:41:26Z

My intuition is that the check is not necessary, and OpenSSH seems to agree, so we might as well bypass the trade-off discussion and the "Baillie-PSW pseudoprimes exist but have not been found" fragility and drop the check.

dacohen · 2020-09-01T19:46:09Z

I think that makes sense as well. I'll submit that change.

gopherbot · 2020-09-01T20:10:03Z

Change https://golang.org/cl/252337 mentions this issue: x/crypto/ssh: improve Diffie-Hellman performance for large keys

The existing implementation validates that the prime returned by the server is, in fact, prime, which is extremely slow, especially for large key sizes. As other implementations, including OpenSSH, do not verify the primality of the provided parameters, this change removes that check. Fixes golang/go#41151 Change-Id: I7539714c690f08b5792a0c540cbf46c3e81f13ba

rsc · 2020-09-02T19:16:30Z

Can I suggest keeping a couple rounds of Miller-Rabin?
Even just having 1 round would be a significant belt-and-suspenders for BPSW at minimal cost.

FiloSottile · 2020-09-02T20:53:32Z

BPSW is a round of MR and a Lucas test. Do you mean extra rounds of MR?

Honestly I'm kind of convinced to just drop the whole check. If we can just not play the game of adversarial primalty testing, we shouldn't, and OpenSSH seems convinced we can.

rsc · 2020-09-18T02:40:55Z

If dropping the primality check entirely is OK for the protocol, then that's fine.

If the check is kept, I'd rather see ProbablyPrime(1) than ProbablyPrime(0).
The whole point of Miller-Rabin is the random base.
BPSW's check hard-codes base 2, making it not really Miller-Rabin at all.
For a random base instead of a fixed base, the chance of eluding detection
with even a single round is very low, much lower than the 1/4 used in the standard proof,
making the single round worth its cost as a backstop for BPSW alone.
But again, if the entire check can be dropped, that's fine.

…check The existing implementation validates that the prime returned by the server is, in fact, prime, which is extremely slow, especially for large key sizes. As other implementations, including OpenSSH, do not verify the primality of the provided parameters, this change removes that check. Fixes golang/go#41151 Change-Id: I7539714c690f08b5792a0c540cbf46c3e81f13ba Reviewed-on: https://go-review.googlesource.com/c/crypto/+/252337 Reviewed-by: Filippo Valsorda <filippo@golang.org> Run-TryBot: Filippo Valsorda <filippo@golang.org> TryBot-Result: Go Bot <gobot@golang.org> Trust: Roland Shoemaker <roland@golang.org>

dacohen changed the title ~~crypto/ssh: DH SHA256 is extremely slow due to primality check~~ x/crypto/ssh: DH SHA256 is extremely slow due to primality check Sep 1, 2020

gopherbot added this to the Unreleased milestone Sep 1, 2020

ALTree added NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance labels Sep 1, 2020

ALTree added NeedsFix The path to resolution is known, but the work has not been done. and removed NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Sep 2, 2020

gopherbot closed this as completed in golang/crypto@afb6bcd Sep 30, 2020

golang locked and limited conversation to collaborators Sep 30, 2021

gopherbot added the FrozenDueToAge label Sep 30, 2021

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

x/crypto/ssh: DH SHA256 is extremely slow due to primality check #41151

x/crypto/ssh: DH SHA256 is extremely slow due to primality check #41151

dacohen commented Sep 1, 2020

ALTree commented Sep 1, 2020 •

edited

dacohen commented Sep 1, 2020

FiloSottile commented Sep 1, 2020

hanwen commented Sep 1, 2020

ALTree commented Sep 1, 2020

dacohen commented Sep 1, 2020

FiloSottile commented Sep 1, 2020

hanwen commented Sep 1, 2020

dacohen commented Sep 1, 2020

FiloSottile commented Sep 1, 2020

dacohen commented Sep 1, 2020

gopherbot commented Sep 1, 2020

rsc commented Sep 2, 2020

FiloSottile commented Sep 2, 2020

rsc commented Sep 18, 2020

x/crypto/ssh: DH SHA256 is extremely slow due to primality check #41151

x/crypto/ssh: DH SHA256 is extremely slow due to primality check #41151

Comments

dacohen commented Sep 1, 2020

What version of Go are you using (go version)?

Does this issue reproduce with the latest release?

What operating system and processor architecture are you using (go env)?

What did you do?

What did you expect to see?

What did you see instead?

ALTree commented Sep 1, 2020 • edited

dacohen commented Sep 1, 2020

FiloSottile commented Sep 1, 2020

hanwen commented Sep 1, 2020

ALTree commented Sep 1, 2020

dacohen commented Sep 1, 2020

FiloSottile commented Sep 1, 2020

hanwen commented Sep 1, 2020

dacohen commented Sep 1, 2020

FiloSottile commented Sep 1, 2020

dacohen commented Sep 1, 2020

gopherbot commented Sep 1, 2020

rsc commented Sep 2, 2020

FiloSottile commented Sep 2, 2020

rsc commented Sep 18, 2020

What version of Go are you using (`go version`)?

What operating system and processor architecture are you using (`go env`)?

ALTree commented Sep 1, 2020 •

edited