diff --git a/openssh-8.7p1-minimize-sha1-use.patch b/openssh-8.7p1-minimize-sha1-use.patch
new file mode 100644
index 0000000..519b8f4
--- /dev/null
+++ b/openssh-8.7p1-minimize-sha1-use.patch
@@ -0,0 +1,102 @@
+diff -up openssh-8.7p1/kex.c.minsha1 openssh-8.7p1/kex.c
+--- openssh-8.7p1/kex.c.minsha1	2021-12-20 17:38:51.438294309 +0100
++++ openssh-8.7p1/kex.c	2021-12-21 11:02:48.379991319 +0100
+@@ -994,6 +994,35 @@ kex_choose_conf(struct ssh *ssh)
+ 		free(ext);
+ 	}
+ 
++	/* Check whether client supports rsa-sha2 algorithms */
++	if (kex->server && (kex->flags & KEX_INITIAL)) {
++		char *ext;
++
++		ext = match_list("rsa-sha2-256", peer[PROPOSAL_SERVER_HOST_KEY_ALGS], NULL);
++		if (ext) {
++			kex->flags |= KEX_RSA_SHA2_256_SUPPORTED;
++			free(ext);
++		}
++
++		ext = match_list("rsa-sha2-512", peer[PROPOSAL_SERVER_HOST_KEY_ALGS], NULL);
++		if (ext) {
++			kex->flags |= KEX_RSA_SHA2_512_SUPPORTED;
++			free(ext);
++		}
++
++		ext = match_list("rsa-sha2-256-cert-v01@openssh.com", peer[PROPOSAL_SERVER_HOST_KEY_ALGS], NULL);
++		if (ext) {
++			kex->flags |= KEX_RSA_SHA2_256_SUPPORTED;
++			free(ext);
++		}
++
++		ext = match_list("rsa-sha2-512-cert-v01@openssh.com", peer[PROPOSAL_SERVER_HOST_KEY_ALGS], NULL);
++		if (ext) {
++			kex->flags |= KEX_RSA_SHA2_512_SUPPORTED;
++			free(ext);
++		}
++	}
++
+ 	/* Algorithm Negotiation */
+ 	if ((r = choose_kex(kex, cprop[PROPOSAL_KEX_ALGS],
+ 	    sprop[PROPOSAL_KEX_ALGS])) != 0) {
+diff -up openssh-8.7p1/kex.h.minsha1 openssh-8.7p1/kex.h
+--- openssh-8.7p1/kex.h.minsha1	2021-12-20 17:38:51.430294240 +0100
++++ openssh-8.7p1/kex.h	2021-12-21 10:56:29.066735608 +0100
+@@ -116,6 +116,8 @@ enum kex_exchange {
+ 
+ #define KEX_INIT_SENT	0x0001
+ #define KEX_INITIAL	0x0002
++#define KEX_RSA_SHA2_256_SUPPORTED 0x0004
++#define KEX_RSA_SHA2_512_SUPPORTED 0x0008
+ 
+ struct sshenc {
+ 	char	*name;
+diff -up openssh-8.7p1/serverloop.c.minsha1 openssh-8.7p1/serverloop.c
+--- openssh-8.7p1/serverloop.c.minsha1	2021-08-20 06:03:49.000000000 +0200
++++ openssh-8.7p1/serverloop.c	2021-12-21 11:01:00.594047538 +0100
+@@ -684,7 +685,7 @@ server_input_hostkeys_prove(struct ssh *
+ 	struct sshbuf *resp = NULL;
+ 	struct sshbuf *sigbuf = NULL;
+ 	struct sshkey *key = NULL, *key_pub = NULL, *key_prv = NULL;
+-	int r, ndx, kexsigtype, use_kexsigtype, success = 0;
++	int r, ndx, success = 0;
+ 	const u_char *blob;
+ 	u_char *sig = 0;
+ 	size_t blen, slen;
+@@ -692,9 +693,11 @@ server_input_hostkeys_prove(struct ssh *
+ 	if ((resp = sshbuf_new()) == NULL || (sigbuf = sshbuf_new()) == NULL)
+ 		fatal_f("sshbuf_new");
+ 
+-	kexsigtype = sshkey_type_plain(
+-	    sshkey_type_from_name(ssh->kex->hostkey_alg));
+ 	while (ssh_packet_remaining(ssh) > 0) {
++		const char *pkexstr = NULL;
++		const char *rsa_sha2_256 = "rsa-sha2-256";
++		const char *rsa_sha2_512 = "rsa-sha2-512";
++
+ 		sshkey_free(key);
+ 		key = NULL;
+ 		if ((r = sshpkt_get_string_direct(ssh, &blob, &blen)) != 0 ||
+@@ -726,8 +729,13 @@ server_input_hostkeys_prove(struct ssh *
+ 		 * For RSA keys, prefer to use the signature type negotiated
+ 		 * during KEX to the default (SHA1).
+ 		 */
+-		use_kexsigtype = kexsigtype == KEY_RSA &&
+-		    sshkey_type_plain(key->type) == KEY_RSA;
++		if (sshkey_type_plain(key->type) == KEY_RSA) {
++		    if (ssh->kex->flags & KEX_RSA_SHA2_512_SUPPORTED)
++			pkexstr = rsa_sha2_512;
++		    else if (ssh->kex->flags & KEX_RSA_SHA2_256_SUPPORTED)
++			pkexstr = rsa_sha2_256;
++		}
++
+ 		if ((r = sshbuf_put_cstring(sigbuf,
+ 		    "hostkeys-prove-00@openssh.com")) != 0 ||
+ 		    (r = sshbuf_put_stringb(sigbuf,
+@@ -735,7 +743,7 @@ server_input_hostkeys_prove(struct ssh *
+ 		    (r = sshkey_puts(key, sigbuf)) != 0 ||
+ 		    (r = ssh->kex->sign(ssh, key_prv, key_pub, &sig, &slen,
+ 		    sshbuf_ptr(sigbuf), sshbuf_len(sigbuf),
+-		    use_kexsigtype ? ssh->kex->hostkey_alg : NULL)) != 0 ||
++		    pkexstr)) != 0 ||
+ 		    (r = sshbuf_put_string(resp, sig, slen)) != 0) {
+ 			error_fr(r, "assemble signature");
+ 			goto out;
diff --git a/openssh.spec b/openssh.spec
index f0d9fec..8a00742 100644
--- a/openssh.spec
+++ b/openssh.spec
@@ -51,7 +51,7 @@
 
 # Do not forget to bump pam_ssh_agent_auth release if you rewind the main package release to 1
 %global openssh_ver 8.7p1
-%global openssh_rel 5
+%global openssh_rel 6
 %global pam_ssh_agent_ver 0.10.4
 %global pam_ssh_agent_rel 4
 
@@ -202,6 +202,8 @@ Patch978: openssh-8.7p1-upstream-cve-2021-41617.patch
 # fix for `ssh-keygen -Y find-principals -f /dev/null -s /dev/null` (#2024902)
 Patch979: openssh-8.7p1-find-principals-fix.patch
 
+Patch1000: openssh-8.7p1-minimize-sha1-use.patch
+
 License: BSD
 Requires: /sbin/nologin
 
@@ -385,6 +387,8 @@ popd
 %patch201 -p1 -b .audit-race
 %patch700 -p1 -b .fips
 
+%patch1000 -p1 -b .minsha1
+
 %patch100 -p1 -b .coverity
 
 autoreconf
@@ -664,6 +668,10 @@ test -f %{sysconfig_anaconda} && \
 %endif
 
 %changelog
+* Tue Dec 21 2021 Dmitry Belyavskiy <dbelyavs@redhat.com> - 8.7p1-6
+- Fix SSH connection to localhost not possible in FIPS
+  Related: rhbz#2031868
+
 * Mon Nov 29 2021 Dmitry Belyavskiy <dbelyavs@redhat.com> - 8.7p1-5
 - Fix `ssh-keygen -Y find-principals -f /dev/null -s /dev/null` segfault
   Related: rhbz#2024902