OPINIONATED OMARCHY
TROUBLESHOOTING CORPUS
790
RECORDS
790
AUDITED
0
UNCHECKED
2388
SOURCES
LIVE
security medium occasional DISPUTE

Tell a real changed SSH host key from an algorithm order false alarm

omarchyarchendeavouroscachyosmanjarolaptopdesktop
CORRECTED An auditor found the fix wrong or incomplete and rewrote it. · checked against Omarchy 4.0.2-1 on 2026-09-18
AUDIT NOTE

Held against openssh 10.5p1-1 on omarchy 4.0.2-1 by reading only: man 5 ssh_config on this machine, ssh -G and ssh -Q output, /etc/ssh/ssh_config and its three drop-ins, and the pinned openssh-portable sources sshconnect.c, hostfile.c, sshconnect2.c and clientloop.c. The premise is real, not folk: hostfile.c check_hostkeys_by_key_or_type returns HOST_CHANGED for any recorded key of the host that is not equal to the offered one, with no key-type comparison, so a known_hosts holding only an RSA entry for a server now negotiated with ED25519 prints the full changed-key warning. All three quoted strings match sshconnect.c exactly. Wrong: UpdateHostKeys was enabled by default in release 8.5, not 8.8, and its preconditions are misquoted. Wrong: sshconnect2.c keeps the prefer-known-types ordering for a HostKeyAlgorithms list prefixed with plus or minus and drops it only for a replacing or ^ list, so 'an explicit line' overstates. Wrong: the fix example prints ed25519 where sshkey_type prints ED25519, and the diagnostic in step 3 cannot be applied, because the Offending line names the last non-matching entry in file order, not the entry of the offered type. Wrong: the prose says remove the one offending line and the command given is ssh-keygen -R, which man 1 ssh-keygen says removes all keys for the hostname, so in the algorithm-order case it deletes the very entries that were still correct. Wrong: verify demands exactly one entry per host and compares it against the first entry of ssh -G hostkeyalgorithms, which is ssh-ed25519-cert-v01@openssh.com, a certificate algorithm that never appears as a known_hosts key type, and ssh -G does not apply the known-hosts ordering anyway. Rewritten cause, fix and verify give the reader the local test, offered type versus recorded types from ssh-keygen -lF, and a repair for each branch: confirm out of band then ssh-keygen -R when the same type differs, or connect with the held type placed first via the ^ prefix so UpdateHostKeys learns the rest when no entry of the offered type exists. The ^ branch is read from clientloop.c and sshconnect.c hostkey_accepted_by_hostkeyalgs, not exercised, which is why confidence is medium. Gate 1 passes on documented defaults and release notes, gate 3 passes, no attack step anywhere. Severity lowered to medium: StrictHostKeyChecking defaults to ask, no default exposes anything, and the exposure exists only if the reader applies the advice the record warns against. No overlap in problems.jsonl: the only slug containing ssh is ssh-agent-not-seen-by-gui-apps and no record mentions known_hosts, StrictHostKeyChecking or the warning text. Arch and Omarchy ship no HostKeyAlgorithms line, confirmed by reading /etc/ssh/ssh_config and /etc/ssh/ssh_config.d/.

The cause above was rewritten on 2026-09-18 to match this note; the fix was corrected by the audit itself.
RISK

Setting StrictHostKeyChecking no, UserKnownHostsFile=/dev/null, or removing a key without confirming it out of band all have the same effect: ssh accepts whatever key is offered for that host from then on with no warning, which is exactly the check this message exists to make. A wildcard Host pattern, Host * or a whole subnet the way the Arch wiki's own private-network example writes it, turns a fix meant for one server into no host key checking for many.

Symptom

ssh refuses a server you connect to all the time with WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!, right after an OpenSSH update, a fresh set of dotfiles, or a new ~/.ssh/config, and nothing else about the server changed. Is this an attack, or did the update just change which key ssh checks.

Cause

OpenSSH picks the host key type to check from HostKeyAlgorithms, an ordered list, and man 5 ssh_config on openssh 10.5p1 says that when host keys are already known for the destination the default is modified to prefer their algorithms. The client source (sshconnect2.c, order_hostkeyalgs) applies that only when HostKeyAlgorithms is unset or starts with + or -. A replacing list with no prefix, a ^ list, or a server that no longer offers the type you hold, each make the client negotiate a key type for which known_hosts has no entry. What turns that into the changed-key warning is hostfile.c: any recorded key for the host that is not equal to the offered one counts as a change, whatever its type. So a known_hosts that holds only an RSA key for a server now negotiated with ED25519 prints WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! exactly as a rotated key would. The common trigger after an update is in the OpenSSH 8.8 release notes: the client stopped offering the SHA-1 ssh-rsa signature, so a server that can only sign RSA with SHA-1 is negotiated with a different key type instead. UpdateHostKeys, on by default since release 8.5, normally learns a server's other key types over an authenticated connection and heads this off, but the 8.5 notes list its preconditions: the key matched in UserKnownHostsFile and not GlobalKnownHostsFile, the same key not recorded under another name, no certificate host key, and no wildcard pattern in known_hosts. A host that fails one of those keeps the single entry it started with. The warning prints the two facts that separate the cases: The fingerprint for the %s key sent by the remote host is names the type actually offered, and Offending %s key in %s:%lu names one recorded entry and its line, the last non-matching one in file order, which is not always the same type. Both types print in capitals, RSA, ECDSA or ED25519. Arch and Omarchy 4.0.2-1 ship no HostKeyAlgorithms line in /etc/ssh/ssh_config or /etc/ssh/ssh_config.d/, so a list on this system is one you or a tool added.

Fix

Do not silence the warning with StrictHostKeyChecking no and do not start with ssh-keygen -R. Read two lines of the warning first: the type on The fingerprint for the <TYPE> key sent by the remote host is, and the fingerprint under it.

  1. Without connecting, list what known_hosts already holds for the host, with types and fingerprints. Write [host]:port in place of host if the server is on a port other than 22:

ssh-keygen -lF <host> -f ~/.ssh/known_hosts
  1. Compare the offered type with those entries.

If an entry of the offered type exists, the key of that type differs from your record: either the server rotated it or something is between you and it. Confirm the fingerprint the warning printed through a channel that is not this connection: the machine's own console (ssh-keygen -lf /etc/ssh/ssh_host_ed25519_key.pub there), a configuration management record, or the administrator. Only when it matches, remove the entries for that one host and accept the new key on the next connection. ssh-keygen -R removes every entry for the hostname given, all key types, and nothing else:


ssh-keygen -R <host> -f ~/.ssh/known_hosts

If no entry of the offered type exists, nothing you hold has been contradicted: the client negotiated a type it has never recorded for this host. Connect once with the type you already hold placed first, so the host is authenticated by the key you already trust and UpdateHostKeys can learn the others over that authenticated connection. Use rsa-sha2-512,rsa-sha2-256 for an ssh-rsa entry, ecdsa-sha2-nistp256 for an ecdsa-sha2-nistp256 entry, ssh-ed25519 for an ssh-ed25519 entry:


ssh -o 'HostKeyAlgorithms=^rsa-sha2-512,rsa-sha2-256' <host>

The ^ prefix puts those first without removing anything else from the list, which is what lets the other types be learned. If that connection succeeds, run step 1 again and the offered type should now be listed. If it fails with no matching host key type found, the server no longer offers a type you hold, so confirm the offered fingerprint out of band exactly as above, then record it without touching the other entries:


ssh-keyscan -t ed25519 <host> > /tmp/hostkey   # or ecdsa or rsa, add -p <port> if needed
ssh-keygen -lf /tmp/hostkey                    # must match the confirmed fingerprint
cat /tmp/hostkey >> ~/.ssh/known_hosts
  1. If you have a replacing HostKeyAlgorithms line, one with no +, - or ^ prefix, find it and change it to a + or - form or delete it, or the client keeps ignoring what known_hosts holds for every host it covers:

grep -n HostKeyAlgorithms ~/.ssh/config /etc/ssh/ssh_config /etc/ssh/ssh_config.d/*.conf 2>/dev/null

Never add StrictHostKeyChecking no or UserKnownHostsFile /dev/null to a Host block to make the warning stop. That removes the check for those hosts permanently rather than resolving this one instance.

Verify

ssh-keygen -lF <host> -f ~/.ssh/known_hosts lists an entry whose type matches the one the warning named on its The fingerprint for the <TYPE> key sent by the remote host is line, and grep -n 'StrictHostKeyChecking\|UserKnownHostsFile' ~/.ssh/config /etc/ssh/ssh_config /etc/ssh/ssh_config.d/*.conf 2>/dev/null prints nothing you added. On Omarchy 4.0.2-1 the only stock hits are in systemd's 20-systemd-ssh-proxy.conf, which disables the check for its unix/*, vsock/* and machine/* proxy addresses only.

Sources

ssh-host-key-warning-after-algorithm-order-change