pslog

most of the more or less current debian installations (including derivates) have been reported to contain a buggy openssh package where the ssh key generater has a faliure with the randomizer. bottomline: you need to update openssh and you need to regenerate your ssh keys.

you can test your keys with a little tool. here’s a copy/paste block which checks your keys

wget -c http://security.debian.org/project/extra/dowkd/dowkd.pl.gz
gunzip dowkd.pl.gz
chmod u+x dowkd.pl
./dowkd.pl user
./dowkd.pl host hostname

it will report “weak key”

updating is done the debian way with

apt-get update
apt-get upgrade

after that you need to regenrate your keys

for the user key:

ssh-keygen -t dsa -b 1024

for the host key:

sudo rm /etc/ssh/ssh_host_{dsa,rsa}_key*
sudo dpkg-reconfigure -plow openssh-server

if the test utility reports weak keys in your authorized_hosts file inform the admin of the machine and delete the affected line as well.