Troubleshooting Unexpected SSH Host Key Changes and Authentication Failures


2 views

I recently encountered a perplexing issue where SSH host keys appeared to change unexpectedly on an Ubuntu 12.04 server after modifying the sshd_config file. The problem manifested in several ways:

  • Intermittent "host key changed" warnings
  • Public key authentication failures
  • No corresponding entries in /var/log/auth.log

The issue began when I removed this line from /etc/ssh/sshd_config:

HostKey /etc/ssh/ssh_host_ecdsa_key

This seemingly simple change triggered a cascade of authentication problems. Even after restoring the line and regenerating all host keys with:

sudo rm /etc/ssh/ssh_host_*
sudo dpkg-reconfigure openssh-server

The issues persisted in an intermittent fashion.

Several potential explanations emerged during troubleshooting:

  1. Multiple SSH Servers: The server might be running multiple SSH daemons with different configurations
  2. DNS Issues: Possible DNS round-robin or caching problems
  3. Network Configuration: Load balancer or NAT issues
  4. File Permissions: Host key files might have incorrect permissions

To properly diagnose the issue, I implemented these verification steps:

# Check running SSH processes
ps aux | grep sshd

# Verify DNS resolution
dig +short example.com
host example.com

# Check host key fingerprints
for key in /etc/ssh/ssh_host_*_key; do ssh-keygen -lf $key; done

# Monitor auth logs in real-time
tail -f /var/log/auth.log

After thorough investigation, the root cause was identified as a combination of factors:

# 1. Ensure only one SSH daemon is running
sudo killall sshd
sudo service ssh restart

# 2. Verify and set correct permissions
sudo chmod 600 /etc/ssh/ssh_host_*_key
sudo chown root:root /etc/ssh/ssh_host_*_key

# 3. Update sshd_config with all host keys
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_dsa_key
HostKey /etc/ssh/ssh_host_ecdsa_key

# 4. Restart SSH service
sudo service ssh restart

Additionally, I added these monitoring measures:

# Create a cron job to verify host keys daily
0 3 * * * /usr/bin/ssh-keygen -lf /etc/ssh/ssh_host_rsa_key | md5sum > /var/log/ssh_hostkey_check.log

To prevent recurrence, implement these best practices:

  • Regularly verify host key fingerprints
  • Implement centralized SSH key management
  • Set up proper monitoring for SSH service changes
  • Consider using SSH certificates instead of host keys

After modifying the /etc/ssh/sshd_config file on an Ubuntu 12.04 test server through Puppet deployment, I encountered persistent SSH host key verification issues. The problem manifested through these symptoms:

Warning: the RSA host key for 'hostname' differs from the key for the IP address 'x.x.x.x'
Offending key for IP in /home/user/.ssh/known_hosts:42
Matching host key in /home/user/.ssh/known_hosts:57

The original change that triggered this behavior was removing the ECDSA host key specification:

# Before change
HostKey /etc/ssh/ssh_host_ecdsa_key
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_dsa_key

# After change
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_dsa_key

After extensive troubleshooting, I discovered several interesting patterns:

  • Errors occurred intermittently, not consistently
  • Authentication failures happened without corresponding auth.log entries
  • Different client locations experienced different behaviors

To properly regenerate all host keys, follow this procedure:

sudo rm /etc/ssh/ssh_host_*
sudo dpkg-reconfigure openssh-server
sudo service ssh restart

Then update your known_hosts file:

ssh-keygen -R hostname
ssh-keygen -R ip_address
ssh-keyscan -t rsa,dsa,ecdsa hostname >> ~/.ssh/known_hosts

After eliminating several possibilities, the most likely explanations are:

  1. DNS Round Robin: Multiple servers sharing the same hostname
  2. Load Balancer Issues: Different backend servers serving SSH requests
  3. Cloud Environment Artifacts: IP address reassignment or instance replacement

To verify server consistency, run these commands from different networks:

for key in /etc/ssh/ssh_host_*.pub; do 
    echo "$key: $(ssh-keygen -lf $key)";
done

Compare fingerprints across multiple connections:

ssh-keyscan -t rsa hostname | ssh-keygen -lf -

For stable SSH host key management:

# /etc/ssh/sshd_config
HostKeyAlgorithms ssh-rsa,ssh-dss,ecdsa-sha2-nistp256
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_dsa_key
HostKey /etc/ssh/ssh_host_ecdsa_key

For clients experiencing issues, add to ~/.ssh/config:

Host problematic-host
    Hostname actual-hostname
    User your-username
    IdentitiesOnly yes
    IdentityFile ~/.ssh/your_key
    StrictHostKeyChecking accept-new