This article addresses multiple common causes and solutions when encountering OpenSSH connection errors related to host key algorithm mismatches on Windows systems.
When you connect to a server via Secure Shell (SSH), you might encounter errors such as:
-
Unable to negotiate with <server>: no matching host key type found.
-
Host key algorithm: (no match)
-
Permission denied (publickey).
-
Server refused our key.
These errors typically indicate mismatches in supported algorithms, permissions issues, or security concerns.
Cause 1: RSA algorithm disabled in updated OpenSSH versions
OpenSSH 8.8 and later versions disable the insecure ssh-rsa algorithm by default, causing legacy clients dependent on RSA keys to fail connection attempts.
Resolution
-
Back up the existing configuration:
Copy-Item "C:\ProgramData\ssh\sshd_config" "C:\ProgramData\ssh\sshd_config.bak" -
Modify the sshd_config file:
-
Open Notepad as administrator.
-
Use the following command to open the sshd_config file:
notepad "C:\ProgramData\ssh\sshd_config" -
Add the following lines to the end of the file:
PubkeyAcceptedAlgorithms +ssh-rsa HostKeyAlgorithms +ssh-rsa
-
-
Restart the OpenSSH service:
Restart-Service sshd -
Verify the SSH connection:
ssh -v user@server.example.com
Cause 2: Missing or incorrect authorized_keys file or improper file permissions
Connection failures occur due to missing or incorrect authorized_keys file or improper file permissions, generating "Permission denied" errors.
Resolution
-
Ensure the authorized_keys file exists:
File path: C:\ProgramData\ssh\administrators_authorized_keys
Place your public keys correctly in this file.
-
Correct file permissions:
Ensure only administrators have write permissions to the file:
icacls.exe "C:\ProgramData\ssh\administrators_authorized_keys" /inheritance:r /grant "Administrators:F" -
Restart the OpenSSH service:
net stop sshd net start sshd
Cause 3: Private keys stored in the registry persist across sessions causing security risks
Private keys stored by OpenSSH's ssh-agent service persist across sessions in the Windows registry, potentially causing security risks.
Resolution
- Use strong encryption and passphrases when generating private keys.
- Limit registry access through user permissions.
- Regularly update OpenSSH from official sources (for example, GitHub).
- Regularly audit registry entries and clear sensitive keys when not needed.
Optional registry adjustments
Manage RSA keys securely via registry policies:
Set-ItemProperty -Path 'HKLM:\SOFTWARE\Policies\Microsoft\Windows\SSH-Server' -Name AllowRSAKey -Value 1 -Type DWORD
Set-ItemProperty -Path 'HKLM:\System\CurrentControlSet\Services\SSH-Server\Parameters' -Name AllowRSAKey -Value 1 -Type DWORD
Recommended general security practices
- Secure user accounts and maintain strict file permissions.
- Regularly update OpenSSH to include latest security patches.
- Use stronger algorithms such as ED25519 or ECDSA where possible.
- Educate users on secure key management practices.
Troubleshooting logs and diagnostics
To gather detailed debugging logs during connection attempts, use the verbose SSH command:
ssh -vvv user@hostname
Analyze logs collected from both working and nonworking environments to identify configuration differences.
Next steps
- Identify and inventory legacy clients still requiring weaker algorithms like
ssh-rsa. - Implement a scheduled upgrade strategy to migrate these clients to stronger algorithms.
- After resolving compatibility issues, remove temporary algorithm overrides from sshd_config.
- Replace legacy RSA keys with stronger keys (minimum 3072-bit RSA or ED25519).
References
Source: Microsoft Learn / IT Pro troubleshooting by Microsoft and contributors. Documentation licensed CC BY 4.0. Code samples are covered by the MIT License. Converted from Markdown, with links normalized and embedded media omitted.
