SSH Host Key Verification Failed: Root Cause Analysis and Solutions

Problem Background and Error Analysis

In practical applications of the SSH (Secure Shell) protocol, host key verification is the core mechanism ensuring connection security. When a client first connects to an SSH server, the server provides its host key, which the client stores in the ~/.ssh/known_hosts file. In subsequent connections, the client verifies whether the host key provided by the server matches the stored key to prevent man-in-the-middle attacks.

The "Host key verification failed" error encountered after reinstalling the operating system essentially stems from key mismatch issues. The specific manifestation is:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that the RSA host key has just been changed.
The fingerprint for the RSA key sent by the remote host is ab:cd:ef:gh
Please contact your system administrator.
Add correct host key in /home/user/.ssh/known_hosts to get rid of this message.
Offending key in /home/user/.ssh/known_hosts:1
RSA host key for user.server has changed and you have requested strict checking.
Host key verification failed.

This error message clearly indicates the core problem: the host key stored in the client's known_hosts file does not match the host key currently provided by the server. This situation typically occurs in scenarios such as server-side key updates, system reinstallation, or network configuration changes.

Root Cause Investigation

The SSH host key verification mechanism is designed to prevent man-in-the-middle attacks. When a server's host key changes, the client triggers a security warning because this change could mean:

• The server has indeed updated its host key (e.g., system reinstallation, key rotation)
• A malicious third party is attempting to impersonate the target server

In the case of a user reinstalling the desktop operating system, although the server-side key remains unchanged, the client's original known_hosts file has been cleared. When the user attempts to re-establish an SSH connection, the system generates a new known_hosts file, but it may contain outdated or incorrect key records.

Core Solution: ssh-keygen -R Command

The most direct and effective solution to host key verification failure is using the ssh-keygen -R command to remove outdated host key records.

The specific syntax and functionality of this command are as follows:

ssh-keygen -R hostname

Where hostname can be the target server's domain name or IP address. After executing this command, the system removes all key records associated with that hostname from the ~/.ssh/known_hosts file.

Let's demonstrate the implementation process through a complete example:

# First remove known outdated key records
ssh-keygen -R example.com

# Or use IP address
ssh-keygen -R 192.168.1.100

# Re-establish SSH connection, system will prompt to accept new host key
ssh username@example.com

When executing the ssh-keygen -R command, the system outputs information similar to the following, confirming that the key has been successfully removed:

# Host example.com found: line 1
/home/user/.ssh/known_hosts updated.
Original contents retained as /home/user/.ssh/known_hosts.old

In-depth Technical Principle Analysis

The working principle of the ssh-keygen -R command involves multiple technical levels:

Key Storage Format: Each record in the known_hosts file contains a host identifier and the corresponding public key. Records may be stored in plaintext or hashed form, depending on the SSH client configuration.

Search and Matching Algorithm: When executing ssh-keygen -R hostname, the command will:

1. Parse each record in the known_hosts file
2. Match all entries related to the specified hostname (including possible hashed forms)
3. Remove all matching records
4. Create a backup file (typically known_hosts.old) to prevent accidental operations

The following code example demonstrates how to manually implement similar key removal functionality:

import re

def remove_host_key(hostname, known_hosts_path='~/.ssh/known_hosts'):
    """
    Remove all key records for specified host from known_hosts file
    """
    import os
    expanded_path = os.path.expanduser(known_hosts_path)
    
    if not os.path.exists(expanded_path):
        return False
    
    # Read file content
    with open(expanded_path, 'r') as f:
        lines = f.readlines()
    
    # Filter out lines related to target host
    new_lines = []
    for line in lines:
        # Match hostname (supports hashed form)
        if not re.match(fr'^({re.escape(hostname)}|\\|1\\|)', line):
            new_lines.append(line)
    
    # Write back to file
    with open(expanded_path, 'w') as f:
        f.writelines(new_lines)
    
    return True

Alternative Approaches and Supplementary Methods

In addition to using the ssh-keygen -R command, there are several other methods to handle host key verification failure:

Manual Editing of known_hosts File:

# Open known_hosts file with text editor
nano ~/.ssh/known_hosts

# Delete lines containing problematic hostname
# Save and exit editor

Using sed Command for Batch Processing:

# Remove all records for specific host
sed -i '/example\\.com/d' ~/.ssh/known_hosts

# Or use more precise pattern matching
sed -i '/^example\\.com/d' ~/.ssh/known_hosts

Temporarily Disabling Strict Host Key Checking (testing environments only):

# Disable strict checking for single connection
ssh -o StrictHostKeyChecking=no username@example.com

# Or set in configuration file
echo "StrictHostKeyChecking no" >> ~/.ssh/config

Security Best Practices

When handling host key verification issues, the following security principles must be followed:

Verify Key Fingerprints: Before removing old keys and accepting new ones, verify the server's new key fingerprint through trusted channels. This can be achieved by contacting the system administrator or using other secure connection methods.

Regular Key Audits: Establish regular SSH key audit mechanisms to check records in the known_hosts file and remove unused or outdated entries.

Backup and Version Control: Perform regular backups of the known_hosts file or include it in version control systems for quick recovery in case of issues.

Automated Key Management: In large environments, consider using automated tools to manage SSH host keys, such as configuration management tools like Ansible or Puppet.

Troubleshooting and Debugging Techniques

When encountering complex SSH connection problems, the following debugging methods can be employed:

Enable Verbose Output:

ssh -vvv username@example.com

Check known_hosts File Permissions:

ls -la ~/.ssh/known_hosts
# Correct permissions should be 644 (-rw-r--r--)

Verify SSH Configuration: Check relevant settings in the ~/.ssh/config file to ensure there are no conflicting configuration items.

By systematically applying the above solutions and best practices, users can effectively resolve SSH host key verification failure issues while maintaining connection security and reliability.