I think this happens due to https://github.com/golang/crypto/blob/dab2b10/ssh/certs.go#L304 not checking cert.Key against c.HostKeyFallback.

/cc @FiloSottile

Hi, I encountered this issue and found that this patch fixes it. It would fallback to verify cert.Key. Although I am not sure if this behavior is standard. But when I try to connect to server using ssh -v. I can see debug1: No matching CA found. Retry with plain key in the outputs. So I think it's intended.

        if !c.IsHostAuthority(cert.SignatureKey, addr) {
+               if c.HostKeyFallback != nil {
+                       err := c.HostKeyFallback(addr, remote, cert.Key)
+                       if err != nil {
+                               return fmt.Errorf("ssh: no authorities for hostname %v. retry with plain key but failed: %v", addr, err)
+                       } else {
+                               return nil
+                       }
+               }
                return fmt.Errorf("ssh: no authorities for hostname: %v", addr)
        }

If this is the correct way to fix, I can add some tests to it and open a PR.

Faced with the same problem. Research lead to similar solution as @Bogay described. But with small corrections: c.HostKeyFallback returns the KeyError which is useful for separating 2 cases: 1) line isn't exists in known_hosts file 2) key is wrong. So just return result of c.HostKeyFallback(...) will be better.

...
if !c.IsHostAuthority(cert.SignatureKey, addr) {
    if c.HostKeyFallback != nil {
        return c.HostKeyFallback(addr, remote, cert.Key)
    }
    return fmt.Errorf("ssh: no authorities for hostname: %v", addr)
}
...

Faced with the same problem. Research lead to similar solution as @Bogay described. But with small corrections: c.HostKeyFallback returns the KeyError which is useful for separating 2 cases: 1) line isn't exists in known_hosts file 2) key is wrong. So just return result of c.HostKeyFallback(...) will be better.

But in this approach, we don't provide any additional information that the fallback is being used (i.e., what I added with fmt.Errorf). Maybe we can embed the returned KeyError using the %w verb so that it can be unwrapped if needed? I am not familar with this usage, please correct me if I misunderstand it.

If the format specifier includes a %w verb with an error operand, the returned error will implement an Unwrap method returning the operand. (ref)