Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
dacohen opened this issue Sep 1, 2020 · 15 comments
Closed

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

dacohen opened this issue Sep 1, 2020 · 15 comments

Comments

@dacohen
Copy link

@dacohen dacohen commented Sep 1, 2020

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.

@dacohen 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 gopherbot added this to the Unreleased milestone Sep 1, 2020
@ALTree
Copy link
Member

@ALTree ALTree commented Sep 1, 2020

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
Copy link
Author

@dacohen dacohen commented Sep 1, 2020

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
Copy link
Member

@FiloSottile FiloSottile commented Sep 1, 2020

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
Copy link
Contributor

@hanwen hanwen commented Sep 1, 2020

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
Copy link
Member

@ALTree ALTree commented Sep 1, 2020

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
Copy link
Author

@dacohen dacohen commented Sep 1, 2020

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
Copy link
Member

@FiloSottile FiloSottile commented Sep 1, 2020

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
Copy link
Contributor

@hanwen hanwen commented Sep 1, 2020

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
Copy link
Author

@dacohen dacohen commented Sep 1, 2020

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
Copy link
Member

@FiloSottile FiloSottile commented Sep 1, 2020

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
Copy link
Author

@dacohen dacohen commented Sep 1, 2020

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

@gopherbot
Copy link

@gopherbot gopherbot commented Sep 1, 2020

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

dacohen added a commit to dacohen/crypto that referenced this issue Sep 1, 2020
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
@ALTree ALTree added NeedsFix and removed NeedsInvestigation labels Sep 2, 2020
@rsc
Copy link
Contributor

@rsc rsc commented Sep 2, 2020

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
Copy link
Member

@FiloSottile FiloSottile commented Sep 2, 2020

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
Copy link
Contributor

@rsc rsc commented Sep 18, 2020

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
6 participants
You can’t perform that action at this time.