Failing to detect ssh-ed25519 host key algorithm already present

[ChaoticRoman]

Maybe I am understanding something wrong but I got this recommendation:

~/projects/ssh-audit $ ./ssh-audit.py 192.168.1.1
# general
(gen) banner: SSH-2.0-OpenSSH_9.6
(gen) software: OpenSSH 9.6
(gen) compatibility: OpenSSH 8.5+, Dropbear SSH 2020.79+
(gen) compression: enabled ([email protected])
...
# algorithm recommendations (for OpenSSH 9.6)
(rec) +ssh-ed25519                          -- key algorithm to append 
...

So i have added to my sshd_config there:

HostKeyAlgorithms +ssh-ed25519

and it seems it is allowed:

~ # sshd -f /etc/sshd.conf -T | grep hostkeyalgorithms
hostkeyalgorithms [email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],[email protected],ssh-ed25519,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,[email protected],[email protected],rsa-sha2-512,rsa-sha2-256

Version of sshd:

OpenSSH_9.6p1, OpenSSL 3.0.12 24 Oct 2023

[ChaoticRoman]

Full output with -d option appended:

$ ./ssh-audit.py -d 192.168.1.1
Starting audit of 192.168.1.1:22...
Connecting to 192.168.1.1:22...
Getting banner...
KEX initialisation...
Preparing to obtain rsa-sha2-256 host key...
Connecting to 192.168.1.1:22...
Getting banner...
KEX initialisation...
Parsing host key type: ssh-rsa
Hostkey type: [rsa-sha2-256]; hostkey size: 2048; CA type: []; CA modulus size: 0
WARNING: called SSH2_Kex.set_host_key() multiple times with the same host key type (rsa-sha2-256)!  Existing info: 2048, '', 0; Duplicate (ignored) info: 2048, '', 0
Preparing to perform DH group exchange using diffie-hellman-group-exchange-sha256 with min, pref and max modulus sizes of 512 bits, 1024 bits and 1536 bits...
Connecting to 192.168.1.1:22...
Getting banner...
KEX initialisation...
GEXTest._send_init(diffie-hellman-group-exchange-sha256, 512, 1024, 1536): exception when performing DH group exchange init: Expected MSG_KEXDH_GEX_REPLY (33), but got -1 instead.
Connecting to 192.168.1.1:22...
Getting banner...
KEX initialisation...
GEXTest._send_init(diffie-hellman-group-exchange-sha256, 512, 512, 512): exception when performing DH group exchange init: Expected MSG_KEXDH_GEX_REPLY (33), but got -1 instead.
Connecting to 192.168.1.1:22...
Getting banner...
KEX initialisation...
GEXTest._send_init(diffie-hellman-group-exchange-sha256, 768, 768, 768): exception when performing DH group exchange init: Expected MSG_KEXDH_GEX_REPLY (33), but got -1 instead.
Connecting to 192.168.1.1:22...
Getting banner...
KEX initialisation...
GEXTest._send_init(diffie-hellman-group-exchange-sha256, 1024, 1024, 1024): exception when performing DH group exchange init: Expected MSG_KEXDH_GEX_REPLY (33), but got -1 instead.
Connecting to 192.168.1.1:22...
Getting banner...
KEX initialisation...
GEXTest._send_init(diffie-hellman-group-exchange-sha256, 1536, 1536, 1536): exception when performing DH group exchange init: Expected MSG_KEXDH_GEX_REPLY (33), but got -1 instead.
Connecting to 192.168.1.1:22...
Getting banner...
KEX initialisation...
GEXTest._send_init(diffie-hellman-group-exchange-sha256, 2048, 2048, 2048): received modulus size: 2048
First pass found a minimum GEX modulus of 2048 against OpenSSH server.  Performing a second pass to get a more accurate result...
Connecting to 192.168.1.1:22...
Getting banner...
KEX initialisation...
GEXTest._send_init(diffie-hellman-group-exchange-sha256, 2048, 3072, 4096): received modulus size: 4096
Modulus size returned by server during second pass: 4096 bits
DHEat.dh_rate_test(): starting test; parameters: 1.500000 seconds, 38 max connections, 3 concurrent sockets.
DHEat.dh_rate_test() results: time elapsed: 1.541139; connections created: 13
DHEat.dh_rate_test() results: 8.4 connections opened per second.
# general
(gen) banner: SSH-2.0-OpenSSH_9.6
(gen) software: OpenSSH 9.6
(gen) compatibility: OpenSSH 8.5+, Dropbear SSH 2020.79+
(gen) compression: enabled ([email protected])

# key exchange algorithms
(kex) [email protected]    -- [info] available since OpenSSH 8.5
                                            `- [info] default key exchange since OpenSSH 9.0
(kex) curve25519-sha256                     -- [info] available since OpenSSH 7.4, Dropbear SSH 2018.76
                                            `- [info] default key exchange from OpenSSH 7.4 to 8.9
(kex) [email protected]          -- [info] available since OpenSSH 6.4, Dropbear SSH 2013.62
                                            `- [info] default key exchange from OpenSSH 6.5 to 7.3
(kex) diffie-hellman-group-exchange-sha256 (4096-bit) -- [info] available since OpenSSH 4.4
                                                      `- [info] OpenSSH's GEX fallback mechanism was triggered during testing. Very old SSH clients will still be able to create connections using a 2048-bit modulus, though modern clients will use 4096. This can only be disabled by recompiling the code (see https://github.com/openssh/openssh-portable/blob/V_9_4/dh.c#L477).
(kex) diffie-hellman-group16-sha512         -- [info] available since OpenSSH 7.3, Dropbear SSH 2016.73
(kex) diffie-hellman-group18-sha512         -- [info] available since OpenSSH 7.3
(kex) ext-info-s                            -- [info] pseudo-algorithm that denotes the peer supports RFC8308 extensions
(kex) [email protected]          -- [info] pseudo-algorithm that denotes the peer supports a stricter key exchange method as a counter-measure to the Terrapin attack (CVE-2023-48795)

# host-key algorithms
(key) rsa-sha2-512 (2048-bit)               -- [warn] 2048-bit modulus only provides 112-bits of symmetric strength
                                            `- [info] available since OpenSSH 7.2
(key) rsa-sha2-256 (2048-bit)               -- [warn] 2048-bit modulus only provides 112-bits of symmetric strength
                                            `- [info] available since OpenSSH 7.2, Dropbear SSH 2020.79

# encryption algorithms (ciphers)
(enc) [email protected]         -- [info] available since OpenSSH 6.5, Dropbear SSH 2020.79
                                            `- [info] default cipher since OpenSSH 6.9
(enc) aes128-ctr                            -- [info] available since OpenSSH 3.7, Dropbear SSH 0.52
(enc) aes192-ctr                            -- [info] available since OpenSSH 3.7
(enc) aes256-ctr                            -- [info] available since OpenSSH 3.7, Dropbear SSH 0.52
(enc) [email protected]                -- [info] available since OpenSSH 6.2
(enc) [email protected]                -- [info] available since OpenSSH 6.2

# message authentication code algorithms
(mac) [email protected]              -- [info] available since OpenSSH 6.2
(mac) [email protected]         -- [info] available since OpenSSH 6.2
(mac) [email protected]         -- [info] available since OpenSSH 6.2

# fingerprints
(fin) ssh-rsa: SHA256:TD5eL6oVr/TohH/hYFKdizYIZ/BDBiBdeaq6eRLszUo

# algorithm recommendations (for OpenSSH 9.6)
(rec) +ssh-ed25519                          -- key algorithm to append 
(rec) !rsa-sha2-256                         -- key algorithm to change (increase modulus size to 3072 bits or larger) 
(rec) !rsa-sha2-512                         -- key algorithm to change (increase modulus size to 3072 bits or larger) 

# additional info
(nfo) For hardening guides on common OSes, please see: <https://www.ssh-audit.com/hardening_guides.html>
(nfo) Be aware that, while this target properly supports the strict key exchange method (via the [email protected] marker) needed to protect against the Terrapin vulnerability (CVE-2023-48795), all peers must also support this feature as well, otherwise the vulnerability will still be present.  The following algorithms would allow an unpatched peer to create vulnerable SSH channels with this target: [email protected].  If any CBC ciphers are in this list, you may remove them while leaving the *[email protected] MACs in place; these MACs are fine while paired with non-CBC cipher types.

[Robberbob]

Do you have a ed25519 key in your config?

You can generate one with:
ssh-keygen -t ed25519 -f /etc/ssh/ssh_host_ed25519_key -N ""
And enable it with:
sed -i 's/^\#HostKey \/etc\/ssh\/ssh_host_ed25519_key$/HostKey \/etc\/ssh\/ssh_host_ed25519_key/g' /etc/ssh/sshd_config

Your sshd config should then look something like:

# This is the sshd server system-wide configuration file.  See
# sshd_config(5) for more information.

# This sshd was compiled with PATH=/usr/local/bin:/usr/bin:/bin:/usr/games

# The strategy used for options in the default sshd_config shipped with
# OpenSSH is to specify options with their default value where
# possible, but leave them commented.  Uncommented options override the
# default value.

Include /etc/ssh/sshd_config.d/*.conf

#Port 22
#AddressFamily any
#ListenAddress 0.0.0.0
#ListenAddress ::

HostKey /etc/ssh/ssh_host_rsa_key
#HostKey /etc/ssh/ssh_host_ecdsa_key
HostKey /etc/ssh/ssh_host_ed25519_key

[ChaoticRoman]

You are right, so the algorithm was allowed correctly, it was just not in use, the key presented was of RSA type. After switching the key type, the recommendation is gone.

So only issue here is that key algorithm to append is little bit confusing, the algorithm is enabled, it is just not used. key algorithm to use maybe? The point is that other algorithm to append/remove notes are resolved by adding lines to sshd_config like KexAlgorithms -ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521 or MACs -hmac-sha1,[email protected]...