Can you please also show output of the following commands?

rpm -q crypto-policies
update-crypto-policies --show
cat /etc/crypto-policies/back-ends/opensshserver.config

Thanks

I am wondering if this is the fixed with the following patch, that landed into the 7.9 branch after release:

https://github.com/openssh/openssh-portable/commit/f429c1b2ef631f2855e51a790cf71761d752bbca

Related upstream bug (the site is currently having some HTTPS issues):

https://bugzilla.mindrot.org/show_bug.cgi?id=2944

Can you check if the attached patch (to the client) solves the problem for you? I will build a scratch build since we shoudld backport these changes anyway ...

openssh-7.9p1-3.fc29 has been submitted as an update to Fedora 29. https://bodhi.fedoraproject.org/updates/FEDORA-2019-f6ff819834

openssh-7.9p1-3.fc29 has been pushed to the Fedora 29 testing repository. If problems still persist, please make note of it in this bug report.
See https://fedoraproject.org/wiki/QA:Updates_Testing for
instructions on how to install test updates.
You can provide feedback for this update here: https://bodhi.fedoraproject.org/updates/FEDORA-2019-f6ff819834

Interesting.  I'll try and test this tomorrow from work (where I actually have ssh client certs setup) to some Fedora 29 Cloud VMs.

However, I'm pretty sure I recognize that patch...

It was written in response to some of my internal feedback about ssh client to ssh agent errors triggering on every login to some new style cert verifying hosts.
However the login was actually succeeding, just printing a verbose error.
Here the login is outright failing.
Doesn't necessarily mean it's not the same issue though.

[root@eonwe ~]# rpm -q crypto-policies
crypto-policies-20181026-1.gitd42aaa6.fc29.noarch

[root@eonwe ~]# update-crypto-policies --show
DEFAULT

[root@eonwe ~]# cat /etc/crypto-policies/back-ends/opensshserver.config
CRYPTO_POLICY='-oCiphers=aes256-gcm,chacha20-poly1305,aes256-ctr,aes256-cbc,aes128-gcm,aes128-ctr,aes128-cbc -oMACs=hmac-sha2-256-etm,hmac-sha1-etm,umac-128-etm,hmac-sha2-512-etm,hmac-sha2-256,hmac-sha1,umac-128,hmac-sha2-512 -oGSSAPIKexAlgorithms=gss-gex-sha1-,gss-group14-sha1- -oKexAlgorithms=curve25519-sha256,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1 -oHostKeyAlgorithms=rsa-sha2-256,ecdsa-sha2-nistp256,ecdsa-sha2-nistp256-cert-v01,ecdsa-sha2-nistp384,ecdsa-sha2-nistp384-cert-v01,rsa-sha2-512,ecdsa-sha2-nistp521,ecdsa-sha2-nistp521-cert-v01,ssh-ed25519,ssh-ed25519-cert-v01,ssh-rsa,ssh-rsa-cert-v01 -oPubkeyAcceptedKeyTypes=rsa-sha2-256,ecdsa-sha2-nistp256,ecdsa-sha2-nistp256-cert-v01,ecdsa-sha2-nistp384,ecdsa-sha2-nistp384-cert-v01,rsa-sha2-512,ecdsa-sha2-nistp521,ecdsa-sha2-nistp521-cert-v01,ssh-ed25519,ssh-ed25519-cert-v01,ssh-rsa,ssh-rsa-cert-v01'

So the ssh-rsa-cert-v01 is clearly there.

Yes, I checked also on my machine. This is fine from crypto-policies side, but the last release got more strict about handling the key types, which is the pain in several cases here.

Sharing debug log (at least from the client) if the update from updates-testing will not work would be helpful.

[root@eonwe ~]# rpm -qa | egrep openssh
openssh-server-7.9p1-3.fc29.x86_64
openssh-clients-7.9p1-3.fc29.x86_64
openssh-7.9p1-3.fc29.x86_64

[root@eonwe ~]# date
Tue Jan 15 15:28:59 PST 2019

Jan 15 15:29:35 eonwe.lan sshd[29703]: userauth_pubkey: key type ssh-rsa-cert-v01 not in PubkeyAcceptedKeyTypes [preauth]
Jan 15 15:29:35 eonwe.lan sshd[29703]: userauth_pubkey: key type ssh-rsa-cert-v01 not in PubkeyAcceptedKeyTypes [preauth]
Jan 15 15:29:35 eonwe.lan sshd[29705]: pam_access(sshd:auth): access denied for user `root' from `2620:0:1000:...'
Jan 15 15:29:35 eonwe.lan sshd[29705]: Beginning pam_ssh_agent_auth for user root
Jan 15 15:29:35 eonwe.lan sshd[29705]: Attempting authentication: `root' as `root' using /root/.ssh/authorized_keys
Jan 15 15:29:35 eonwe.lan sshd[29705]: No ssh-agent could be contacted
Jan 15 15:29:35 eonwe.lan sshd[29705]: Failed Authentication: `root' as `root' using /root/.ssh/authorized_keys
Jan 15 15:29:35 eonwe.lan sshd[29703]: Postponed keyboard-interactive for root from 2620:0:1000:... port 59020 ssh2 [pr>
Jan 15 15:29:36 eonwe.lan sshd[29703]: Connection closed by authenticating user root 2620:0:1000:... port 59020 [preaut>

So AFAICT it doesn't fix it.

(I'm not entirely sure what you mean by debug log...)

openssh-7.9p1-3.fc29 has been pushed to the Fedora 29 stable repository. If problems still persist, please make note of it in this bug report.

Temporarily change LogLevel to DEBUG3 in the sshd_config, restart the sshd and try it, then revert back to the default LogLevel setting.

For the client debug log, please run the command you tried with -vvv switches. It will generate the log to see what is the client attempting to do. I see you are using ssh-agent. Is it ssh-agent from openssh on Fedora, or something else?

I can reproduce the same problem. It really looks like a bug in crypto policy. I probably initially forgot to include the sha2 variants (they are not listed in `ssh -Q key`). Even though the log says it is plain rsa certificate, when I dumped what is actually being compared to what, I figured out it is really the SHA2 signature already, which was missing in the list from the crypto policy.

userauth_pubkey: pkalg=<rsa-sha2-512-cert-v01> PubkeyAcceptedKeyTypes=<rsa-sha2-256,ecdsa-sha2-nistp256,ecdsa-sha2-nistp256-cert-v01,ecdsa-sha2-nistp384,ecdsa-sha2-nistp384-cert-v01,rsa-sha2-512,ecdsa-sha2-nistp521,ecdsa-sha2-nistp521-cert-v01,ssh-ed25519,ssh-ed25519-cert-v01,ssh-rsa,ssh-rsa-cert-v01> [preauth]

I filled the following pull request resolving this upstream:

https://gitlab.com/redhat-crypto/fedora-crypto-policies/merge_requests/35

And I reassign the bug to crypto policies.

Hello, I am running into this issue also ("userauth_pubkey: key type ssh-rsa-cert-v01 not in PubkeyAcceptedKeyTypes [preauth]").

I am wondering when a new pk11-kit package with the fix would be submitted for update on Fedora 29?

crypto-policies-20180211-1.gite3eacfc.fc29 has been submitted as an update to Fedora 29. https://bodhi.fedoraproject.org/updates/FEDORA-2019-436ecd5423

Think you're off by 1 on year.

crypto-policies-20190211-2.gite3eacfc.fc29 has been pushed to the Fedora 29 testing repository. If problems still persist, please make note of it in this bug report.
See https://fedoraproject.org/wiki/QA:Updates_Testing for
instructions on how to install test updates.
You can provide feedback for this update here: https://bodhi.fedoraproject.org/updates/FEDORA-2019-436ecd5423

That does indeed appear to fix the problem.

crypto-policies-20190211-2.gite3eacfc.fc29 has been pushed to the Fedora 29 stable repository. If problems still persist, please make note of it in this bug report.