It seems that public key authentication isn't as save as you might have thought. That is if you're using a Debian based OpenSSH solution. This package can be found in many Linux distributions like;
- Debian (duh ;) )
- Ubuntu
- Kubuntu
- etc.
The problem is that the random number generator (which is of vital importance in generating key-pairs) isn't as random as you might think. It seems that there are only about 30.000 combinations in this specific generator. This leaves the door wide open for brute-force attacks.
So, the first you must do is update your OpenSSH software, and generate new keypairs for all devices / users which might have keys which were generated with the vulnerable OpenSSH software. Softwarepackages depending on OpenSSH are;
- OpenVPN
- DNSSEC
- OpenSSH
- Certificates used in TLS connections
- etc.