(In reply to Germano Veit Michel from comment #0)
> Description of problem:
> 
> When deploying HE, at the step when the deploy host is added to
> HostedEngineLocal:
> 
> 2020-11-25 23:31:17,835Z INFO 
> [org.ovirt.engine.core.dal.dbbroker.auditloghandling.AuditLogDirector]
> (default task-1) [fc2c1be] EVENT_ID: USER_VDC_LOGIN(30), User
> admin@internal-authz connecting from '192.168.222.1' using session
> 'WmBsFpMQUjTmkgbgF3CM8zN+5KNNQK5mghf/
> Gpyp0nfKeMcx7PHpmTW6AwjDln9E0o8gaL3nKJ7rz+4mDHaB+A==' logged in.
> 2020-11-25 23:31:54,563Z ERROR
> [org.ovirt.engine.core.bll.hostdeploy.AddVdsCommand] (default task-1)
> [6af37be3-8650-429c-baa9-7133945693f8] Failed to authenticate session with
> host 'host2.kvm': SSH authentication to 'root' failed. Please
> verify provided credentials. Make sure key is authorized at host
> 2020-11-25 23:31:54,564Z WARN 
> [org.ovirt.engine.core.bll.hostdeploy.AddVdsCommand] (default task-1)
> [6af37be3-8650-429c-baa9-7133945693f8] Validation of action 'AddVds' failed
> for user admin@internal-authz. Reasons:
> VAR__ACTION__ADD,VAR__TYPE__HOST,$server
> host2.kvm,VDS_CANNOT_AUTHENTICATE_TO_SERVER
> 2020-11-25 23:31:54,677Z ERROR
> [org.ovirt.engine.api.restapi.resource.AbstractBackendResource] (default
> task-1) [] Operation Failed: [Cannot add Host. SSH authentication failed,
> verify authentication parameters are correct (Username/Password, public-key
> etc.) You may refer to the engine.log file for further details.]
> 
> Then the HE deploy fails waiting for the "Host to be up", but it wasn't even
> added.
> 
> On the host we have signs that the SSH failed too:
> Nov 25 23:31:54 host2 sshd[10520]: userauth_pubkey: key type ssh-rsa not in
> PubkeyAcceptedKeyTypes [preauth]
> Nov 25 23:31:54 host2 sshd[10520]: Connection closed by authenticating user
> root 192.168.222.28 port 60740 [preauth]
> 
> If I SSH to HostedEngineLocal and try to SSH to the host in a similar way to
> what the SSHClient Java code in the engine does, I get this:
> # ssh -i /etc/pki/ovirt-engine/keys/engine_id_rsa
> -oHostKeyAlgorithms=ssh-rsa root
> Unable to negotiate with 192.168.100.2 port 22: no matching host key type
> found. Their offer: rsa-sha2-512,rsa-sha2-256,ecdsa-sha2-nistp256
> 
> And the exact same error on the host:
> Nov 25 23:46:35 host2 sshd[12412]: userauth_pubkey: key type ssh-rsa not in
> PubkeyAcceptedKeyTypes [preauth]
> Nov 25 23:46:35 host2 sshd[12412]: Connection closed by authenticating user
> root 192.168.222.28 port 60950 [preauth]
> 
> # cat /etc/crypto-policies/back-ends/openssh.config
> Ciphers
> aes256-gcm,aes256-ctr,aes256-cbc,aes128-gcm,aes128-
> ctr,aes128-cbc
> MACs hmac-sha2-256,hmac-sha1,hmac-sha2-512
> GSSAPIKeyExchange no
> KexAlgorithms
> ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-
> group14-sha256
> PubkeyAcceptedKeyTypes
> ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,rsa-sha2-256,rsa-
> sha2-512
> CASignatureAlgorithms
> ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,rsa-sha2-256,rsa-
> sha2-512

That's very strange, rsa-sha2 support is enabled from RHV 4.4 GA (BZ1838159) and I've just verified that latest master works fine with host providing rsa-sha2 keys. Anyway as a part of RHV 4.4.5 we are adding support also for EcDSA and EdDSA keys (BZ1837221), so I'm suggesting to retest with newer version.

Syncing status with BZ1837221

1. Test with latest RHVH build RHVH-4.4-20210216.0-RHVH-x86_64-dvd1.iso
Test version:
RHVH-4.4-20210216.0-RHVH-x86_64-dvd1.iso
rhvm-appliance-4.4-20201117.0.el8ev.x86_64
crypto-policies-20200713-1.git51d1222.el8.noarch

Test steps:
1. Clean install RHVH with STIG security profile
2. Yum installrhvm-appliance
3. Deploy hosted engine via cockpit UI

Result:
HE deploy fails, it can be reproduced with latest version. And the issue has been traced by https://bugzilla.redhat.com/show_bug.cgi?id=1909956

2. Test with RHEL-Host regular host
Test version:
RHEL-8.3.0-20201009.2-x86_64-dvd1.iso
crypto-policies-20200713-1.git51d1222.el8.noarch
cockpit-ovirt-dashboard-0.14.19-1.el8ev.noarch
ovirt-hosted-engine-setup-2.4.9-4.el8ev.noarch
ovirt-hosted-engine-ha-2.4.6-1.el8ev.noarch

Test steps:
1. Clean install RHEL8.3 with STIG security profile
2. Subscribe and enable to the right channels
3. Yum install cockpit-ovirt-dashboard
4. Yum install rhvm-appliance from CDN(rhv-4-mgmt-agent-for-rhel-8-x86_64-rpms repository)
4. Deploy hosted engine via cockpit UI

Result:
HE deploy fails, it can be reproduced with latest version.
2021-02-20 10:50:34,227+08 ERROR [org.ovirt.engine.core.bll.hostdeploy.AddVdsCommand] (default task-1) [f653ccfb-f128-4314-ae82-fdc919222698] Failed to authenticate session with host 'hp-dl388g9-05.lab.eng.pek2.redhat.com': SSH authentication to 'root.eng.pek2.redhat.com' failed. Please verify provided credentials. Make sure key is authorized at host
2021-02-20 10:50:34,228+08 WARN  [org.ovirt.engine.core.bll.hostdeploy.AddVdsCommand] (default task-1) [f653ccfb-f128-4314-ae82-fdc919222698] Validation of action 'AddVds' failed for user admin@internal-authz. Reasons: VAR__ACTION__ADD,VAR__TYPE__HOST,$server hp-dl388g9-05.lab.eng.pek2.redhat.com,VDS_CANNOT_AUTHENTICATE_TO_SERVER
2021-02-20 10:50:34,262+08 ERROR [org.ovirt.engine.api.restapi.resource.AbstractBackendResource] (default task-1) [] Operation Failed: [Cannot add Host. SSH authentication failed, verify authentication parameters are correct (Username/Password, public-key etc.) You may refer to the engine.log file for further details.] 

Feb 20 10:50:34 hp-dl388g9-05.lab.eng.pek2.redhat.com sshd[25336]: error: Unable to load host key: /etc/ssh/ssh_host_ed25519_key
Feb 20 10:50:34 hp-dl388g9-05.lab.eng.pek2.redhat.com sshd[25336]: userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedKeyTypes [preauth]
Feb 20 10:50:34 hp-dl388g9-05.lab.eng.pek2.redhat.com sshd[25336]: Connection closed by authenticating user root 192.168.222.196 port 40638 [preauth]

[root@hp-dl388g9-05 ~]# cat /etc/crypto-policies/back-ends/openssh.config
Ciphers aes256-gcm,aes256-ctr,aes256-cbc,aes128-gcm,aes128-ctr,aes128-cbc
MACs hmac-sha2-256,hmac-sha1,hmac-sha2-512
GSSAPIKeyExchange no
KexAlgorithms ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group14-sha256
PubkeyAcceptedKeyTypes ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,rsa-sha2-256,rsa-sha2-512
CASignatureAlgorithms ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,rsa-sha2-256,rsa-sha2-512 

More info:
# rpm -qa|grep appliance
rhvm-appliance-4.4-20201117.0.el8ev.x86_64
# ssh root.222.196
[root@rhevh-hostedengine-vm-06 ~]# rpm -qa|grep ovirt-engine
ovirt-engine-4.4.3.12-0.1.el8ev.noarch
[root@rhevh-hostedengine-vm-06 ~]# rpm -qa|grep apache-sshd
apache-sshd-2.5.1-1.el8ev.noarch

So ovirt-engine is not the latest one, QE will verfiy this bug until updating rhvm-appliace with ovirt-engine-4.4.5.5

As mentioned in BZ1837221 you need to test in on ovirt-engine-4.4.5.5 or later. It's not required to test this in hosted, it can easily be tested on standalone engine by adding FIPS enabled host.

If you really need to test it in hosted engine, then please update your hosted engine appliance to latest version during installation, AFAIK appliance can be updated to latest version even before adding the 1st host to engine. Am I right Asaf?

(In reply to Martin Perina from comment #7)
> As mentioned in BZ1837221 you need to test in on ovirt-engine-4.4.5.5 or
> later. It's not required to test this in hosted, it can easily be tested on
> standalone engine by adding FIPS enabled host.
> 
> If you really need to test it in hosted engine, then please update your
> hosted engine appliance to latest version during installation, AFAIK
> appliance can be updated to latest version even before adding the 1st host
> to engine. Am I right Asaf?

Yes, there are a few options described in [1]. 

[1] https://github.com/oVirt/ovirt-ansible-collection/tree/master/roles/hosted_engine_setup#make-changes-in-the-engine-vm-during-the-deployment

According to comment 7, QE test on standalone engine(ovirt-engine-4.4.5.5-0.13.el8ev.noarch) by adding FIPS enabled host.

The FIPS host can be added successfully, the bug is fixed, move it to "VERIFIED"

Since the problem described in this bug report should be
resolved in a recent advisory, it has been closed with a
resolution of ERRATA.

For information on the advisory (Moderate: RHV Manager (ovirt-engine) 4.4.z [ovirt-4.4.5] security, bug fix, enhancement), and where to find the updated
files, follow the link below.

If the solution does not work for you, open a new bug report.

https://access.redhat.com/errata/RHSA-2021:1169

Why there is no release notes for this bug?

(In reply to Marina Kalinin from comment #16)
> Why there is no release notes for this bug?

There is no need to add anything specific for this bug, all important informations are included in dependent BZ1837221