regenerate ssh keys after update of openssh
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.