Tuesday, July 7, 2015

Talk Talk

In June I gave talks at both BSides London and the Dutch PHP Conference on the subject of hash functions. I really enjoyed both experences and they both helped me improve my public talking.

At Bsides London I was part of the rookie track which meant I got an excellent mentor in the shape of Yiannis Chrysanthou. It also meant I only had 15 minutes to cram something interesting into which was good as it made me concentrate on the important parts
The Dutch PHP Conference or DPC is a conference I have attended twice before. This year there was no way I could go not as a speaker as they covered travel and accommodation as well as entry to the conference. It was again an excellent conference with great organisation and venue.

Wednesday, July 1, 2015

Github ssh keys some experiments

About a month ago I read this excellent piece of work https://blog.benjojo.co.uk/post/auditing-github-users-keys  . My first reaction was kick myself for not thinking of it before. It reminded me of this paper https://factorable.net/paper.html 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 http://cryptosense.com/batch-gcding-github-ssh-keys/ 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