Win32-OpenSSH not honoring `HostKeyAlgorithms` when started as a service

"OpenSSH for Windows" version
((Get-Item (Get-Command sshd).Source).VersionInfo.FileVersion)
7.7.2.2

Server OperatingSystem
((Get-ItemProperty "HKLM:\SOFTWARE\Microsoft\Windows nt\CurrentVersion\" -Name ProductName).ProductName)
Windows Server 2019 Standard
Own remark: V1909

Client OperatingSystem
Not of interest, problem is visible from the logs shown below.

What is failing
I have installed Win32-OpenSSH, following the usual method (added it as Windows feature in the app management settings page).

I have verified that its directory (c:\windows\system32\openssh) is in the system path, and have set CMD as the shell (in PS: New-ItemProperty -Path "HKLM:\SOFTWARE\OpenSSH" -Name DefaultShell -Value "C:\Windows\System32\cmd.exe" -PropertyType String -Force).

Then I have put my own host keys and my own sshd_config (see below) into c:\programdata\ssh, have verified that Administrators and System had full permissions on that directory as well as on all files in it, and that nobody else had any permissions.

When I now open a Powershell prompt as administrator and start the SSH daemon in the foreground (C:\windows\System32\OpenSSH\sshd.exe -d), I can open SSH sessions from other machines to that daemon, and everything works as expected.

In contrast, when I start the SSH service, I can't open SSH sessions to that machine any more. SSH clients then claim that the server would not offer any host key type. Please note that I did not change the service configuration after having installed OpenSSH server. Notably, the service logs on as SYSTEM account.

I believe I have nailed down the problem, but don't have any clue how to solve it: When started as a service, the SSH daemon does not interpret the HostKeyAlgorithms directive in sshd_config correctly, while it does when it is started in the foreground.

This is my sshd_config (showing all active lines, but comments left away)

AllowUsers administrator
AuthenticationMethods publickey
AuthorizedKeysFile .ssh/authorized_keys
AllowAgentForwarding no
AllowTcpForwarding no
ChallengeResponseAuthentication no
Ciphers chacha20-poly1305@openssh.com,aes256-gcm@openssh.com,aes256-ctr
HostKeyAlgorithms ssh-ed25519-cert-v01@openssh.com,ssh-rsa-cert-v01@openssh.com,ssh-ed25519,ssh-rsa
KexAlgorithms curve25519-sha256@libssh.org,diffie-hellman-group-exchange-sha256
ListenAddress 192.168.20.16:22
LoginGraceTime 20
MACs hmac-sha2-512-etm@openssh.com,hmac-sha2-256-etm@openssh.com
PasswordAuthentication no
Protocol 2
PubkeyAcceptedKeyTypes rsa-sha2-512,ssh-rsa,ssh-ed25519
RekeyLimit 100M 20m
Subsystem sftp sftp-server.exe
TCPKeepAlive no
SyslogFacility LOCAL0
LogLevel DEBUG

This is the log when started as service and a client tries to connect; I have marked the problematic line.

8604 2021-04-17 09:39:48.434 debug1: Bind to port 22 on 192.168.20.16.
8604 2021-04-17 09:39:48.434 Server listening on 192.168.20.16 port 22.
7732 2021-04-17 09:39:56.106 debug1: inetd sockets after dupping: 3, 3
7732 2021-04-17 09:39:56.107 Connection from 192.168.20.10 port 55812 on 192.168.20.16 port 22
7732 2021-04-17 09:39:56.107 debug1: Client protocol version 2.0; client software version OpenSSH_7.9p1 Debian-10+deb10u2
7732 2021-04-17 09:39:56.107 debug1: match: OpenSSH_7.9p1 Debian-10+deb10u2 pat OpenSSH* compat 0x04000000
7732 2021-04-17 09:39:56.107 debug1: Local version string SSH-2.0-OpenSSH_for_Windows_7.7
######################################################
7732 2021-04-17 09:39:56.223 debug1: list_hostkey_types:  [preauth]
######################################################
7732 2021-04-17 09:39:56.223 debug1: SSH2_MSG_KEXINIT sent [preauth]
7732 2021-04-17 09:39:56.224 debug1: SSH2_MSG_KEXINIT received [preauth]
7732 2021-04-17 09:39:56.224 debug1: kex: algorithm: curve25519-sha256@libssh.org [preauth]
7732 2021-04-17 09:39:56.224 debug1: kex: host key algorithm: (no match) [preauth]
7732 2021-04-17 09:39:56.224 Unable to negotiate with 192.168.20.10 port 55812: no matching host key type found. Their offer: ssh-ed25519-cert-v01@openssh.com,ssh-rsa-cert-v01@openssh.com,ssh-ed25519,ssh-rsa [preauth]
7732 2021-04-17 09:39:56.224 debug1: do_cleanup [preauth]
7732 2021-04-17 09:39:56.225 debug1: monitor_read_log: child log fd closed
7732 2021-04-17 09:39:56.225 debug1: do_cleanup
7732 2021-04-17 09:39:56.225 debug1: Killing privsep child 6684

Please note the marked line. Obviously, it can't read or doesn't honor the HostKeyAlgorithms directive.

This is the output on the terminal when started in the foreground and a client connects; again, I have marked the interesting line.

debug1: sshd version OpenSSH_for_Windows_7.7, LibreSSL 2.6.5
debug1: private host key #0: ssh-rsa SHA256:/i7nGUChRILCUi2wN25T+0Adkqcnv6quiDBQuPEw+40
debug1: private host key #1: ecdsa-sha2-nistp256 SHA256:p4wCMVjTs2Wo1okzEJr08h0MfXo1P1oelRvJp35u1X4
debug1: private host key #2: ssh-ed25519 SHA256:lEOMUtoXGuIkkI0HmUDOph/Kn3APUCy3PYMqs+j2Pjw
debug1: rexec_argv[0]='C:\\windows\\System32\\OpenSSH\\sshd.exe'
debug1: rexec_argv[1]='-d'
debug1: Bind to port 22 on 192.168.20.16.
Server listening on 192.168.20.16 port 22.
debug1: Server will not fork when running in debugging mode.
Connection from 192.168.20.10 port 55816 on 192.168.20.16 port 22
debug1: Client protocol version 2.0; client software version OpenSSH_7.9p1 Debian-10+deb10u2
debug1: match: OpenSSH_7.9p1 Debian-10+deb10u2 pat OpenSSH* compat 0x04000000
debug1: Local version string SSH-2.0-OpenSSH_for_Windows_7.7
debug1: sshd version OpenSSH_for_Windows_7.7, LibreSSL 2.6.5
######################################################
debug1: list_hostkey_types: ssh-rsa,rsa-sha2-512,rsa-sha2-256,ecdsa-sha2-nistp256,ssh-ed25519 [preauth]
######################################################
debug1: SSH2_MSG_KEXINIT sent [preauth]
debug1: SSH2_MSG_KEXINIT received [preauth]
debug1: kex: algorithm: curve25519-sha256@libssh.org [preauth]
debug1: kex: host key algorithm: ssh-ed25519 [preauth]
debug1: kex: client->server cipher: aes256-gcm@openssh.com MAC: <implicit> compression: none [preauth]
debug1: kex: server->client cipher: aes256-gcm@openssh.com MAC: <implicit> compression: none [preauth]
debug1: expecting SSH2_MSG_KEX_ECDH_INIT [preauth]
debug1: rekey after 6553600 blocks [preauth]
debug1: SSH2_MSG_NEWKEYS sent [preauth]
debug1: expecting SSH2_MSG_NEWKEYS [preauth]
debug1: SSH2_MSG_NEWKEYS received [preauth]
debug1: rekey after 6553600 blocks [preauth]
debug1: KEX done [preauth]
debug1: userauth-request for user administrator service ssh-connection method none [preauth]
debug1: attempt 0 failures 0 [preauth]
debug1: authentication methods list 0: publickey
debug1: authentication methods list 0: publickey [preauth]
debug1: userauth-request for user administrator service ssh-connection method publickey [preauth]
debug1: attempt 1 failures 0 [preauth]
debug1: userauth_pubkey: test pkalg rsa-sha2-512 pkblob RSA SHA256:FBOARBypYhC4VD3BW/eOqb5EENrI3DVEevyuf9eVevY [preauth]
debug1: trying public key file C:\\Users\\Administrator\\.ssh/authorized_keys
debug1: C:\\Users\\Administrator\\.ssh/authorized_keys:23: matching key found: RSA SHA256:FBOARBypYhC4VD3BW/eOqb5EENrI3DVEevyuf9eVevY
debug1: C:\\Users\\Administrator\\.ssh/authorized_keys:23: key options: agent-forwarding port-forwarding pty user-rc x11-forwarding
Accepted key RSA SHA256:FBOARBypYhC4VD3BW/eOqb5EENrI3DVEevyuf9eVevY found at C:\\Users\\Administrator\\.ssh/authorized_keys:23
Postponed publickey for administrator from 192.168.20.10 port 55816 ssh2 [preauth]

Again, please note the marked line. This time, it obviously has honored the HostKeyAlgorithms directive, and thus makes an appropriate offer to the client. Then, the connection succeeds.

I believe that this is a bug. I can't see any reason why I does not honor HostKeyAlgorithms when started as a service, but has no problem with it when started in the foreground.

Any ideas? I'd be strongly interested in a quick solution, even if it was a dirty preliminary workaround. Until now, on that server, we had SSH via Cygwin, but got a certain problem with it and therefore decided to switch to Microsoft's implementation.

Start by reproducing the difference between C:\Windows\System32\OpenSSH\sshd.exe -d and the Windows SSH service using the reported C:\ProgramData\ssh\sshd_config. Compare the service and foreground logs, especially list_hostkey_types and the loaded private host keys. Done means the service honors the configured HostKeyAlgorithms and negotiates with the client as the foreground daemon does.