This is more or less a known issue some people in my environment have
already been hit by. I'm filing this bug for reference and will mark
the versions accordingly ASAP. I think this will affect more people
when Wheezy is out.

SSHFP DNS records provide a (optionally DNSSEC secured) way to put SSH
host keys into DNS and have them verified by the client.

Since OpenSSH 5.7p1 (post-squeeze) upstream release openssh uses ECDSA
for the keys by default

Features:

 * Implement Elliptic Curve Cryptography modes for key exchange (ECDH)
   and host/user keys (ECDSA) as specified by RFC5656. ECDH and ECDSA
   offer better performance than plain DH and DSA at the same equivalent
   symmetric key length, as well as much shorter keys.
[...]
   ECDH in a 256 bit curve field is the preferred key agreement
   algorithm when both the client and server support it. ECDSA host
   keys are preferred when learning a host's keys for the first time,
   or can be learned using ssh-keyscan(1).


However, support for SSHFP records for ECDSA host keys has only been
added in 6.1p1, which will NOT be a part of wheezy

Features:
[...]
 * Add support for RFC6594 SSHFP DNS records for ECDSA key types. bz#1978

This means that everything between 5.7 and 6.1 will use an algorithm it does
not support SSHFP records for.

The only workaround is to force ssh(1) to use only the old RSA/DSA algos

Host *
 VerifyHostKeyDNS 	yes
 HostKeyAlgorithms	ssh-rsa,ssh-dss

Hi,

I confirm it's fixed in Jessie, but there is no solution for Wheezy ?
We can't use SSHFP for ssh connections from Wheezy to servers running
Wheezy or newer ?

Since it's a lack of security, the patch for SSH client should probably
be backported, no ?

Thanks,
Olivier

I have a package sitting in the queue for wheezy-backports already.  I'm
fairly wary of cherry-picking a non-trivial feature like this to wheezy
directly; it would be very easy to miss further security fixes to it.