OpenSSH 8.9 Rejects an Old RSA Key While fail2ban Locks Out an Office

1. What sshd actually thinks its configuration is: sshd -T | grep -Ei 'allowgroups|authorizedkeysfile|pubkeyauthentication|pubkeyacceptedalgorithms'. FirstMatch and Include can change what you read in the file. AllowGroups is evaluated with the NSS stack; if the group was just created or alice just added, an SSSD or nscd cache on the bastion may not see it yet, so check getent group ssh-users as well as id alice. A missing group membership looks exactly like a key problem in the client.
2. StrictModes: a failure logs Authentication refused: bad ownership or modes for file ... only at LogLevel VERBOSE, so raise it temporarily. Every parent directory must also not be group- or world-writable; a chown done carelessly often leaves authorized_keys owned by root.
3. Key algorithm. This is the most likely cause here: OpenSSH disabled the SHA-1 ssh-rsa signature by default in 8.8, so a 2019 PuTTYgen RSA key offers a signature algorithm that 8.9 will not accept. The client just says Permission denied, while the server at DEBUG level logs a line like signature algorithm ssh-rsa not in PubkeyAcceptedAlgorithms. Confirm by running ssh -vvv alice@bastion and looking at the offered publickey ... ssh-rsa line.

Fix properly by issuing an ed25519 key: ssh-keygen -t ed25519 -a 100, install it, and remove the old entry. A temporary workaround is PubkeyAcceptedAlgorithms +ssh-rsa in sshd_config, but it re-enables SHA-1 for everyone and should be time-boxed and documented. Debug interactively with sshd -ddd -p 2222 on a second session before reloading the production daemon.

Lift it first: fail2ban-client status sshd shows the banned address and the matched log lines; fail2ban-client set sshd unbanip 203.0.113.10 removes it from the database so it survives a fail2ban restart, unlike editing a file by hand or letting the timer expire. Restarting fail2ban also re-applies the ban from its database, which is a common surprise.

The design problem is that a ban is per source address, and a NAT address is shared by 40 people. Options, in order of preference:

• With PasswordAuthentication no already set, brute-force login is not a real threat to this host. The monitoring script's failures are noise. Switch the filter to mode = normal so lines such as Connection closed by authenticating user or Received disconnect - which a broken script produces in bulk - no longer count as failures.
• Add ignoreip = 127.0.0.1/8 ::1 203.0.113.0/24 to the jail or to [DEFAULT], and raise maxretry/findtime for the sshd jail while shortening bantime.
• Replace the full ban with per-source rate limiting (iptables hashlimit or nftables meters) so one noisy source is throttled rather than cut off.

Do not simply disable the jail: a password-only service somewhere else would then be unprotected. Decide based on whether the host accepts passwords, and make that decision explicit in the jail's comment so the next administrator understands why the NAT range is allow-listed.

Goals: keep password auth off, make each user's source address meaningful, and make failures auditable without locking out a whole office.

PermitRootLogin prohibit-password
KbdInteractiveAuthentication no
MaxAuthTries 3
LoginGraceTime 20
MaxStartups 10:30:60
LogLevel VERBOSE
Match Address 10.8.0.0/24,203.0.113.0/24
    AuthenticationMethods publickey

Use a Match block to require publickey from the corporate ranges while keeping the global rules simple; avoid stacking AllowGroups and Match in ways that interact unpredictably, and test both orders with sshd -T -C user=alice,addr=203.0.113.10,host=office to see the resulting configuration for a specific connection. sshd -t must pass before any reload.

A better long-term answer for the shared office address is to put staff behind a WireGuard or OpenVPN endpoint: each user then arrives from a distinct tunnel address, fail2ban can act precisely, and the office NAT is no longer a single point of lockout.

Validation: keep an existing session open, run sshd -t, systemctl reload ssh, then test from a machine you control with ssh -vvv and confirm the log now records Accepted publickey for alice ... SHA256:<fingerprint>. LogLevel VERBOSE gives you the fingerprint, which is what you need to correlate an incident later, and it costs nothing in disk. Only after a successful test should you close the emergency session.