sshd: implement server-sig-algs SSH extension (client side)

Apache MINA sshd has an implementation of this, but it doesn't comply
to RFC 8308 [1] and it is buggy. (See SSHD-1141 [2].)

Add a simpler KexExtensionHandler and if the server sends extension
server-sig-algs, use its value to re-order the chosen signature
algorithms such that the algorithms the server announced as supported
are at the front.

If the server didn't tell us anything, don't do anything. RFC 8308
suggests for RSA to default to ssh-rsa, but says once rsa-sha2-* was
"widely enough" adopted, defaulting to that might be OK.

Currently we seem to be in a transition phase; Fedora 33 has already
disabled ssh-rsa by default, and openssh is about to do so. Whatever
we might do without info from the server, it'd be good for some servers
and bad for others. So don't do anything and let the user re-order via
ssh config PubkeyAcceptedAlgorithms on a case-by-case basis.

[1] https://tools.ietf.org/html/rfc8308
[2] https://issues.apache.org/jira/browse/SSHD-1141

Bug: 572056
Change-Id: I59aa691a030ffe0fae54289df00ca5c6e165817b
Signed-off-by: Thomas Wolf <thomas.wolf@paranor.ch>

6 files changed, 279 insertions, 15 deletions

diff --git a/org.eclipse.jgit.ssh.apache/META-INF/MANIFEST.MF b/org.eclipse.jgit.ssh.apache/META-INF/MANIFEST.MF
index defa710a82..39af83d57b 100644
--- a/org.eclipse.jgit.ssh.apache/META-INF/MANIFEST.MF
+++ b/org.eclipse.jgit.ssh.apache/META-INF/MANIFEST.MF
@@ -59,6 +59,8 @@ Import-Package: net.i2p.crypto.eddsa;version="[0.3.0,0.4.0)",
  org.apache.sshd.common.helpers;version="[2.6.0,2.7.0)",
  org.apache.sshd.common.io;version="[2.6.0,2.7.0)",
  org.apache.sshd.common.kex;version="[2.6.0,2.7.0)",
+ org.apache.sshd.common.kex.extension;version="[2.6.0,2.7.0)",
+ org.apache.sshd.common.kex.extension.parser;version="[2.6.0,2.7.0)",
  org.apache.sshd.common.keyprovider;version="[2.6.0,2.7.0)",
  org.apache.sshd.common.mac;version="[2.6.0,2.7.0)",
  org.apache.sshd.common.random;version="[2.6.0,2.7.0)",
diff --git a/org.eclipse.jgit.ssh.apache/resources/org/eclipse/jgit/internal/transport/sshd/SshdText.properties b/org.eclipse.jgit.ssh.apache/resources/org/eclipse/jgit/internal/transport/sshd/SshdText.properties
index 16b5738332..9c604f214f 100644
--- a/org.eclipse.jgit.ssh.apache/resources/org/eclipse/jgit/internal/transport/sshd/SshdText.properties
+++ b/org.eclipse.jgit.ssh.apache/resources/org/eclipse/jgit/internal/transport/sshd/SshdText.properties
@@ -76,6 +76,9 @@ proxySocksPasswordTooLong=Password for proxy {0} must be at most 255 bytes long,
 proxySocksUnexpectedMessage=Unexpected message received from SOCKS5 proxy {0}; client state {1}: {2}
 proxySocksUnexpectedVersion=Expected SOCKS version 5, got {0}
 proxySocksUsernameTooLong=User name for proxy {0} must be at most 255 bytes long, is {1} bytes: {2}
+pubkeyAuthWrongCommand=Public key authentication received unknown SSH command {0} from {1} ({2})
+pubkeyAuthWrongKey=Public key authentication received wrong key; sent {0}, got back {1} from {2} ({3})
+pubkeyAuthWrongSignatureAlgorithm=Public key authentication requested signature type {0} but got back {1} from {2} ({3})
 serverIdNotReceived=No server identification received within {0} bytes
 serverIdTooLong=Server identification is longer than 255 characters (including line ending): {0}
 serverIdWithNul=Server identification contains a NUL character: {0}
diff --git a/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitKexExtensionHandler.java b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitKexExtensionHandler.java
new file mode 100644
index 0000000000..489c77d736
--- /dev/null
+++ b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitKexExtensionHandler.java
@@ -0,0 +1,163 @@
+/*
+ * Copyright (C) 2021 Thomas Wolf <thomas.wolf@paranor.ch> and others
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * https://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+package org.eclipse.jgit.internal.transport.sshd;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.TreeSet;
+
+import org.apache.sshd.common.AttributeRepository.AttributeKey;
+import org.apache.sshd.common.NamedFactory;
+import org.apache.sshd.common.kex.KexProposalOption;
+import org.apache.sshd.common.kex.extension.KexExtensionHandler;
+import org.apache.sshd.common.kex.extension.KexExtensions;
+import org.apache.sshd.common.kex.extension.parser.ServerSignatureAlgorithms;
+import org.apache.sshd.common.session.Session;
+import org.apache.sshd.common.signature.Signature;
+import org.apache.sshd.common.util.logging.AbstractLoggingBean;
+import org.eclipse.jgit.util.StringUtils;
+
+/**
+ * Do not use the DefaultClientKexExtensionHandler from sshd; it doesn't work
+ * properly because of misconceptions. See SSHD-1141.
+ *
+ * @see <a href="https://issues.apache.org/jira/browse/SSHD-1141">SSHD-1141</a>
+ */
+public class JGitKexExtensionHandler extends AbstractLoggingBean
+		implements KexExtensionHandler {
+
+	/** Singleton instance. */
+	public static final JGitKexExtensionHandler INSTANCE = new JGitKexExtensionHandler();
+
+	/**
+	 * Session {@link AttributeKey} used to store whether the extension
+	 * indicator was already sent.
+	 */
+	private static final AttributeKey<Boolean> CLIENT_PROPOSAL_MADE = new AttributeKey<>();
+
+	/**
+	 * Session {@link AttributeKey} storing the algorithms announced by the
+	 * server as known.
+	 */
+	public static final AttributeKey<Set<String>> SERVER_ALGORITHMS = new AttributeKey<>();
+
+	private JGitKexExtensionHandler() {
+		// No public instantiation for singleton
+	}
+
+	@Override
+	public boolean isKexExtensionsAvailable(Session session,
+			AvailabilityPhase phase) throws IOException {
+		return !AvailabilityPhase.PREKEX.equals(phase);
+	}
+
+	@Override
+	public void handleKexInitProposal(Session session, boolean initiator,
+			Map<KexProposalOption, String> proposal) throws IOException {
+		// If it's the very first time, we may add the marker telling the server
+		// that we are ready to handle SSH_MSG_EXT_INFO
+		if (session == null || session.isServerSession() || !initiator) {
+			return;
+		}
+		if (session.getAttribute(CLIENT_PROPOSAL_MADE) != null) {
+			return;
+		}
+		String kexAlgorithms = proposal.get(KexProposalOption.SERVERKEYS);
+		if (StringUtils.isEmptyOrNull(kexAlgorithms)) {
+			return;
+		}
+		List<String> algorithms = new ArrayList<>();
+		// We're a client. We mustn't send the server extension, and we should
+		// send the client extension only once.
+		for (String algo : kexAlgorithms.split(",")) { //$NON-NLS-1$
+			if (KexExtensions.CLIENT_KEX_EXTENSION.equalsIgnoreCase(algo)
+					|| KexExtensions.SERVER_KEX_EXTENSION
+							.equalsIgnoreCase(algo)) {
+				continue;
+			}
+			algorithms.add(algo);
+		}
+		// Tell the server that we want to receive SSH2_MSG_EXT_INFO
+		algorithms.add(KexExtensions.CLIENT_KEX_EXTENSION);
+		if (log.isDebugEnabled()) {
+			log.debug(
+					"handleKexInitProposal({}): proposing HostKeyAlgorithms {}", //$NON-NLS-1$
+					session, algorithms);
+		}
+		proposal.put(KexProposalOption.SERVERKEYS,
+				String.join(",", algorithms)); //$NON-NLS-1$
+		session.setAttribute(CLIENT_PROPOSAL_MADE, Boolean.TRUE);
+	}
+
+	@Override
+	public boolean handleKexExtensionRequest(Session session, int index,
+			int count, String name, byte[] data) throws IOException {
+		if (ServerSignatureAlgorithms.NAME.equals(name)) {
+			handleServerSignatureAlgorithms(session,
+					ServerSignatureAlgorithms.INSTANCE.parseExtension(data));
+		}
+		return true;
+	}
+
+	/**
+	 * Perform updates after a server-sig-algs extension has been received.
+	 *
+	 * @param session
+	 *            the message was received for
+	 * @param serverAlgorithms
+	 *            signature algorithm names announced by the server
+	 */
+	protected void handleServerSignatureAlgorithms(Session session,
+			Collection<String> serverAlgorithms) {
+		if (log.isDebugEnabled()) {
+			log.debug("handleServerSignatureAlgorithms({}): {}", session, //$NON-NLS-1$
+					serverAlgorithms);
+		}
+		// Client determines order; server says what it supports. Re-order
+		// such that supported ones are at the front, in client order,
+		// followed by unsupported ones, also in client order.
+		if (serverAlgorithms != null && !serverAlgorithms.isEmpty()) {
+			List<NamedFactory<Signature>> clientAlgorithms = session
+					.getSignatureFactories();
+			if (log.isDebugEnabled()) {
+				log.debug(
+						"handleServerSignatureAlgorithms({}): PubkeyAcceptedAlgorithms before: {}", //$NON-NLS-1$
+						session, clientAlgorithms);
+			}
+			List<NamedFactory<Signature>> unknown = new ArrayList<>();
+			Set<String> known = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
+			known.addAll(serverAlgorithms);
+			for (Iterator<NamedFactory<Signature>> iter = clientAlgorithms
+					.iterator(); iter.hasNext();) {
+				NamedFactory<Signature> algo = iter.next();
+				if (!known.contains(algo.getName())) {
+					unknown.add(algo);
+					iter.remove();
+				}
+			}
+			// Re-add the unknown ones at the end. Per RFC 8308, some
+			// servers may not announce _all_ their supported algorithms,
+			// and a client may use unknown algorithms.
+			clientAlgorithms.addAll(unknown);
+			if (log.isDebugEnabled()) {
+				log.debug(
+						"handleServerSignatureAlgorithms({}): PubkeyAcceptedAlgorithms after: {}", //$NON-NLS-1$
+						session, clientAlgorithms);
+			}
+			session.setAttribute(SERVER_ALGORITHMS, known);
+			session.setSignatureFactories(clientAlgorithms);
+		}
+	}
+}
diff --git a/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitPublicKeyAuthentication.java b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitPublicKeyAuthentication.java
index 297b456807..6755094420 100644
--- a/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitPublicKeyAuthentication.java
+++ b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitPublicKeyAuthentication.java
@@ -11,6 +11,9 @@ package org.eclipse.jgit.internal.transport.sshd;
 
 import java.io.IOException;
 import java.security.PublicKey;
+import java.security.spec.InvalidKeySpecException;
+import java.text.MessageFormat;
+import java.util.Deque;
 import java.util.HashSet;
 import java.util.LinkedList;
 import java.util.List;
@@ -19,6 +22,7 @@ import java.util.Set;
 import org.apache.sshd.client.auth.pubkey.UserAuthPublicKey;
 import org.apache.sshd.client.session.ClientSession;
 import org.apache.sshd.common.NamedFactory;
+import org.apache.sshd.common.NamedResource;
 import org.apache.sshd.common.RuntimeSshException;
 import org.apache.sshd.common.SshConstants;
 import org.apache.sshd.common.config.keys.KeyUtils;
@@ -37,7 +41,9 @@ import org.apache.sshd.common.util.buffer.Buffer;
  */
 public class JGitPublicKeyAuthentication extends UserAuthPublicKey {
 
-	private final List<String> algorithms = new LinkedList<>();
+	private final Deque<String> currentAlgorithms = new LinkedList<>();
+
+	private String chosenAlgorithm;
 
 	JGitPublicKeyAuthentication(List<NamedFactory<Signature>> factories) {
 		super(factories);
@@ -47,11 +53,25 @@ public class JGitPublicKeyAuthentication extends UserAuthPublicKey {
 	protected boolean sendAuthDataRequest(ClientSession session, String service)
 			throws Exception {
 		if (current == null) {
-			algorithms.clear();
+			currentAlgorithms.clear();
+			chosenAlgorithm = null;
 		}
 		String currentAlgorithm = null;
-		if (current != null && !algorithms.isEmpty()) {
-			currentAlgorithm = algorithms.remove(0);
+		if (current != null && !currentAlgorithms.isEmpty()) {
+			currentAlgorithm = currentAlgorithms.poll();
+			if (chosenAlgorithm != null) {
+				Set<String> knownServerAlgorithms = session.getAttribute(
+						JGitKexExtensionHandler.SERVER_ALGORITHMS);
+				if (knownServerAlgorithms != null
+						&& knownServerAlgorithms.contains(chosenAlgorithm)) {
+					// We've tried key 'current' with 'chosenAlgorithm', but it
+					// failed. However, the server had told us it supported
+					// 'chosenAlgorithm'. Thus it makes no sense to continue
+					// with this key and other signature algorithms. Skip to the
+					// next key, if any.
+					currentAlgorithm = null;
+				}
+			}
 		}
 		if (currentAlgorithm == null) {
 			try {
@@ -61,14 +81,13 @@ public class JGitPublicKeyAuthentication extends UserAuthPublicKey {
 								"sendAuthDataRequest({})[{}] no more keys to send", //$NON-NLS-1$
 								session, service);
 					}
+					current = null;
 					return false;
 				}
 				current = keys.next();
-				algorithms.clear();
+				currentAlgorithms.clear();
+				chosenAlgorithm = null;
 			} catch (Error e) { // Copied from superclass
-				warn("sendAuthDataRequest({})[{}] failed ({}) to get next key: {}", //$NON-NLS-1$
-						session, service, e.getClass().getSimpleName(),
-						e.getMessage(), e);
 				throw new RuntimeSshException(e);
 			}
 		}
@@ -76,9 +95,6 @@ public class JGitPublicKeyAuthentication extends UserAuthPublicKey {
 		try {
 			key = current.getPublicKey();
 		} catch (Error e) { // Copied from superclass
-			warn("sendAuthDataRequest({})[{}] failed ({}) to retrieve public key: {}", //$NON-NLS-1$
-					session, service, e.getClass().getSimpleName(),
-					e.getMessage(), e);
 			throw new RuntimeSshException(e);
 		}
 		if (currentAlgorithm == null) {
@@ -94,15 +110,21 @@ public class JGitPublicKeyAuthentication extends UserAuthPublicKey {
 				existingFactories = getSignatureFactories();
 			}
 			if (existingFactories != null) {
+				if (log.isDebugEnabled()) {
+					log.debug(
+							"sendAuthDataRequest({})[{}] selecting from PubKeyAcceptedAlgorithms {}", //$NON-NLS-1$
+							session, service,
+							NamedResource.getNames(existingFactories));
+				}
 				// Select the factories by name and in order
 				existingFactories.forEach(f -> {
 					if (aliases.contains(f.getName())) {
-						algorithms.add(f.getName());
+						currentAlgorithms.add(f.getName());
 					}
 				});
 			}
-			currentAlgorithm = algorithms.isEmpty() ? keyType
-					: algorithms.remove(0);
+			currentAlgorithm = currentAlgorithms.isEmpty() ? keyType
+					: currentAlgorithms.poll();
 		}
 		String name = getName();
 		if (log.isDebugEnabled()) {
@@ -112,6 +134,7 @@ public class JGitPublicKeyAuthentication extends UserAuthPublicKey {
 					KeyUtils.getFingerPrint(key));
 		}
 
+		chosenAlgorithm = currentAlgorithm;
 		Buffer buffer = session
 				.createBuffer(SshConstants.SSH_MSG_USERAUTH_REQUEST);
 		buffer.putString(session.getUsername());
@@ -125,9 +148,77 @@ public class JGitPublicKeyAuthentication extends UserAuthPublicKey {
 	}
 
 	@Override
+	protected boolean processAuthDataRequest(ClientSession session,
+			String service, Buffer buffer) throws Exception {
+		String name = getName();
+		int cmd = buffer.getUByte();
+		if (cmd != SshConstants.SSH_MSG_USERAUTH_PK_OK) {
+			throw new IllegalStateException(MessageFormat.format(
+					SshdText.get().pubkeyAuthWrongCommand,
+					SshConstants.getCommandMessageName(cmd),
+					session.getConnectAddress(), session.getServerVersion()));
+		}
+		PublicKey key;
+		try {
+			key = current.getPublicKey();
+		} catch (Error e) { // Copied from superclass
+			throw new RuntimeSshException(e);
+		}
+		String rspKeyAlgorithm = buffer.getString();
+		PublicKey rspKey = buffer.getPublicKey();
+		if (log.isDebugEnabled()) {
+			log.debug(
+					"processAuthDataRequest({})[{}][{}] SSH_MSG_USERAUTH_PK_OK type={}, fingerprint={}", //$NON-NLS-1$
+					session, service, name, rspKeyAlgorithm,
+					KeyUtils.getFingerPrint(rspKey));
+		}
+		if (!KeyUtils.compareKeys(rspKey, key)) {
+			throw new InvalidKeySpecException(MessageFormat.format(
+					SshdText.get().pubkeyAuthWrongKey,
+					KeyUtils.getFingerPrint(key),
+					KeyUtils.getFingerPrint(rspKey),
+					session.getConnectAddress(), session.getServerVersion()));
+		}
+		if (!chosenAlgorithm.equalsIgnoreCase(rspKeyAlgorithm)) {
+			// 'algo' SHOULD be the same as 'chosenAlgorithm', which is the one
+			// we sent above. See https://tools.ietf.org/html/rfc4252#page-9 .
+			//
+			// However, at least Github (SSH-2.0-babeld-383743ad) servers seem
+			// to return the key type, not the algorithm name.
+			//
+			// So we don't check but just log the inconsistency. We sign using
+			// 'chosenAlgorithm' in any case, so we don't really care what the
+			// server says here.
+			log.warn(MessageFormat.format(
+					SshdText.get().pubkeyAuthWrongSignatureAlgorithm,
+					chosenAlgorithm, rspKeyAlgorithm, session.getConnectAddress(),
+					session.getServerVersion()));
+		}
+		String username = session.getUsername();
+		Buffer out = session
+				.createBuffer(SshConstants.SSH_MSG_USERAUTH_REQUEST);
+		out.putString(username);
+		out.putString(service);
+		out.putString(name);
+		out.putBoolean(true);
+		out.putString(chosenAlgorithm);
+		out.putPublicKey(key);
+		if (log.isDebugEnabled()) {
+			log.debug(
+					"processAuthDataRequest({})[{}][{}]: signing with algorithm {}", //$NON-NLS-1$
+					session, service, name, chosenAlgorithm);
+		}
+		appendSignature(session, service, name, username, chosenAlgorithm, key,
+				out);
+		session.writePacket(out);
+		return true;
+	}
+
+	@Override
 	protected void releaseKeys() throws IOException {
-		algorithms.clear();
+		currentAlgorithms.clear();
 		current = null;
+		chosenAlgorithm = null;
 		super.releaseKeys();
 	}
 }
diff --git a/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/SshdText.java b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/SshdText.java
index 4c4ff5949d..99e382aaec 100644
--- a/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/SshdText.java
+++ b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/SshdText.java
@@ -88,6 +88,9 @@ public final class SshdText extends TranslationBundle {
 	/***/ public String proxySocksUnexpectedMessage;
 	/***/ public String proxySocksUnexpectedVersion;
 	/***/ public String proxySocksUsernameTooLong;
+	/***/ public String pubkeyAuthWrongCommand;
+	/***/ public String pubkeyAuthWrongKey;
+	/***/ public String pubkeyAuthWrongSignatureAlgorithm;
 	/***/ public String serverIdNotReceived;
 	/***/ public String serverIdTooLong;
 	/***/ public String serverIdWithNul;
diff --git a/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/transport/sshd/SshdSessionFactory.java b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/transport/sshd/SshdSessionFactory.java
index cad959c904..2d7e0c7c77 100644
--- a/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/transport/sshd/SshdSessionFactory.java
+++ b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/transport/sshd/SshdSessionFactory.java
@@ -47,6 +47,7 @@ import org.eclipse.jgit.internal.transport.ssh.OpenSshConfigFile;
 import org.eclipse.jgit.internal.transport.sshd.AuthenticationCanceledException;
 import org.eclipse.jgit.internal.transport.sshd.CachingKeyPairProvider;
 import org.eclipse.jgit.internal.transport.sshd.GssApiWithMicAuthFactory;
+import org.eclipse.jgit.internal.transport.sshd.JGitKexExtensionHandler;
 import org.eclipse.jgit.internal.transport.sshd.JGitPasswordAuthFactory;
 import org.eclipse.jgit.internal.transport.sshd.JGitPublicKeyAuthFactory;
 import org.eclipse.jgit.internal.transport.sshd.JGitServerKeyVerifier;
@@ -216,6 +217,7 @@ public class SshdSessionFactory extends SshSessionFactory implements Closeable {
 						new JGitUserInteraction(credentialsProvider));
 				client.setUserAuthFactories(getUserAuthFactories());
 				client.setKeyIdentityProvider(defaultKeysProvider);
+				client.setKexExtensionHandler(JGitKexExtensionHandler.INSTANCE);
 				// JGit-specific things:
 				JGitSshClient jgitClient = (JGitSshClient) client;
 				jgitClient.setKeyCache(getKeyCache());