Wednesday, July 1, 2015

Github ssh keys some experiments

About a month ago I read this excellent piece of work  . My first reaction was kick myself for not thinking of it before. It reminded me of this paper and associated the presentation which is pretty special. One of the major tools used in that paper was use of a batch version of the Greatest Common Divisor algorithm that can efficiently find common factors in large numbers of semi primes. Common primes should never happen in correctly functioning ssh key generation. However they are known to happen when things go wrong. 

The batchGCD algorithm didn't seem to have been used to examine the keys in the database. I was in good company in spotting this possible extension.

At the time I expected to see people reporting the discovery of further bad keys discovered using batchGCD over the next few days. A few days latter I came across which looks like exactly that just in a more restrained writing style. 

In the mean time I have been having a poke around myself.

Here are some observations I have made from my experiments with the keys on github and uploading new keys.

  • There is now a minimum key length of 1024 bits enforced when submitting keys with a suggestion of 2048 bits
  • There are no keys below 1024 bits still in the database all shorted ones have been removed.
  • You cannot add a public key from a pair generated with the debian bug. If you do you will see this message

  • There are very few obviously bad keys (e.g. with trivial moduls factorisation) on github. I found a handful all very old.
  • I could not find any keys with common divisors in the database. It looks like somebody has been through with batchGCD notified github and they have revoked them
  • New keys added are not checked to see if they have a common divisor but presumably will eventually get discovered
  • Github seems to receive a lot of spam signup these days where users are listed in the api but deleted for viewing