diff --git a/crypto/openssh/packet.c b/crypto/openssh/packet.c
--- a/crypto/openssh/packet.c
+++ b/crypto/openssh/packet.c
@@ -96,6 +96,7 @@
 #include "packet.h"
 #include "ssherr.h"
 #include "sshbuf.h"
+#include "blacklist_client.h"
 
 #ifdef PACKET_DEBUG
 #define DBG(x) x
@@ -2021,6 +2022,8 @@
 	case SSH_ERR_NO_KEX_ALG_MATCH:
 	case SSH_ERR_NO_HOSTKEY_ALG_MATCH:
 		if (ssh->kex && ssh->kex->failed_choice) {
+			BLACKLIST_NOTIFY(ssh, BLACKLIST_AUTH_FAIL,
+			    "Unable to negotiate offer");
 			ssh_packet_clear_keys(ssh);
 			errno = oerrno;
 			logdie("Unable to negotiate with %s: %s. "