3 ms·

A simpler method and probably just as effective is to ask ... I'm in Boalsburg, PA. The reality is that you can't do much with my public key other than giving

by smoyer 14y ago

A simpler method and probably just as effective is to ask ... I'm in Boalsburg, PA. The reality is that you can't do much with my public key other than giving me permissions, which I'm free to use or ignore. If I lose my private keys, I'm going to be scrambling!

kzrdude 14y ago
You can try factoring it. If you collect a large amount of keys you can use algorithms to find common divisors anywhere in the set, and so make it easier to find easily factorable keys out of a big population.
- andrewcooke 14y ago
  is that true? are there efficient factoring algorithms that scale better than linearly when given many products? i realise that just enumerating products would scale well, but is that how efficient factoring schemes work? or am i misunderstanding?
  - kzrdude 14y ago
    It relies on there being common factors somewhere between any keys in a big set. That should only happen through a very small chance or through random-generation weaknesses. The point is that it's easy to spot it if there are keys with those weaknesses. This CCC talk is related to this: http://events.ccc.de/congress/2012/Fahrplan/events/5275.en.html http://events.ccc.de/congress/2012/Fahrplan/events/5275.en.h... Since ssh keys are user-submitted, we will have diversity and a chance of some subset of keys which weren't generated safely. EDITED TO ADD: Bad CCC site, it doesn't link to the FactHacks slides: http://www.hyperelliptic.org/tanja/vortraege/facthacks-29C3.pdf http://www.hyperelliptic.org/tanja/vortraege/facthacks-29C3....
    - andrewcooke 14y ago
      oh thanks for the edit - also found this https://www.youtube.com/watch?v=IuSnY_O8DqQ https://www.youtube.com/watch?v=IuSnY_O8DqQ and am watching now. and the above tactic starts at 11m in. huh; and it's just euclid - a non-unity gcd means two keys (products) have a shared prime (and you get one of the primes). edit: also, "batch number field sieve" is the answer to my original question.

by smoyer 14y ago

kzrdude 14y ago

You can try factoring it. If you collect a large amount of keys you can use algorithms to find common divisors anywhere in the set, and so make it easier to find easily factorable keys out of a big population.

andrewcooke 14y ago
is that true? are there efficient factoring algorithms that scale better than linearly when given many products? i realise that just enumerating products would scale well, but is that how efficient factoring schemes work? or am i misunderstanding?
- kzrdude 14y ago
  It relies on there being common factors somewhere between any keys in a big set. That should only happen through a very small chance or through random-generation weaknesses. The point is that it's easy to spot it if there are keys with those weaknesses. This CCC talk is related to this: http://events.ccc.de/congress/2012/Fahrplan/events/5275.en.html http://events.ccc.de/congress/2012/Fahrplan/events/5275.en.h... Since ssh keys are user-submitted, we will have diversity and a chance of some subset of keys which weren't generated safely. EDITED TO ADD: Bad CCC site, it doesn't link to the FactHacks slides: http://www.hyperelliptic.org/tanja/vortraege/facthacks-29C3.pdf http://www.hyperelliptic.org/tanja/vortraege/facthacks-29C3....
  - andrewcooke 14y ago
    oh thanks for the edit - also found this https://www.youtube.com/watch?v=IuSnY_O8DqQ https://www.youtube.com/watch?v=IuSnY_O8DqQ and am watching now. and the above tactic starts at 11m in. huh; and it's just euclid - a non-unity gcd means two keys (products) have a shared prime (and you get one of the primes). edit: also, "batch number field sieve" is the answer to my original question.