Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The keys to the keydom

bit-player.org

Post reply on HN
Print view View original

21–28 of 28 posts

Re: The keys to the keydom

#21

Post by cipherzero »

bumbledraven wrote: post #17
tunesmith wrote: post #16

I had trouble following this point: "Even though Euclid’s GCD algorithm is highly efficient, running it on all possible pairings of keys would be a strain. There’s an ingenious shortcut, based on the observation that if Y is relatively prime to each of X1,X2,…,Xn, then it also has no factor in common with the product X1×X2×⋯×Xn. Thus it’s possible to detect the presence of shared factors with just n GCD operations, i…

Someone please correct me if I'm wrong, but I guess the shortcut is something like this: Z = X[1] * X[2] * X[3] * ... * X[n]; for i in (1..n-1) { Z = Z/X[i]; g = GCD(X[i], Z); if (g > 1) { // check each other key to see which have g as a factor for j in (j+1..n) { if (X[j] % g == 0) { log that keys i & j have g as a common factor; } } } Rather than having to run the inner loop for every iteration of the outer loop, i…

Yes that's correct, however you need not actually "log that keys i & j have g as a common factor;" if g > 1 then just add x[i] to a list, after checking all in x, then just go through that much smaller list. ( even better would be to just group x[I] in a dictionary based on g)... good example though.

Re: The keys to the keydom

#22

Post by tunesmith »

pudquick wrote: post #18
tunesmith wrote: post #16

I had trouble following this point: "Even though Euclid’s GCD algorithm is highly efficient, running it on all possible pairings of keys would be a strain. There’s an ingenious shortcut, based on the observation that if Y is relatively prime to each of X1,X2,…,Xn, then it also has no factor in common with the product X1×X2×⋯×Xn. Thus it’s possible to detect the presence of shared factors with just n GCD operations, i…

I think it's shorthand English for saying: Rather than doing n^2 comparisons (ie. every key individually GCD compared against every other key individually = (n keys)x(n-1 other keys) combinations), you can instead do n total GCD comparisons - every key GCD factored a single time against (which works out to (n keys)x(1 big product) GCD comparisons)

Ah, I see - thanks to you and the others. I think I just didn't realize that each X was referring to an actual key.

Re: The keys to the keydom

#23

Post by bigiain »

kalleboo wrote: post #7
gpcz wrote: post #4

64,081 is really close to 65536 (2^16) -- I wonder if the 64,000 vulnerable TLS keys have anything to do with a bug similar to the 2008 Debian SSL key fiasco, where the only contributor to the key's entropy was the PID (2^15 combinations). It would be interesting to see data about the types of devices that have these weak keys, but then again if there is a correlation its release could be used maliciously in the wild…

The post mentions "Most of them are found in embedded networked devices, such as routers and firewalls". Embedded devices like that have very little entropy on first boot - that could might cause them to generate very poor keys. I wonder how many of the 60% non-unique keys are embedded devices with hardcoded keys...

"I wonder how many of the 60% non-unique keys are embedded devices with hardcoded keys..."

That wouldn't surprise me much at all.

I've been working on a secure workaround to let an embedded webserver on our consumer-oriented wifi-equipped hardware(1) do OAuth2 authentication (to connect to owner's Twitter/Faceboot/et al. accounts). OAuth relies on SSL/TLS to protect it's password-equivalent tokens on-the-wire. Getting an SSL cert onto the device (at a reasonable cost) so that a phone connecting to it via wifi doesn't throw up big scarey "somebody might be doing _bad_ things!" warnings is not easily solved.

(1) Shameless self promotion: http://holiday.moorescloud.com - The world's most intelligent christmas lights…

Re: The keys to the keydom

#24

Post by gbog »

BoppreH wrote: post #15
acchow wrote: post #12

Earlier quoted context omitted.

This isn't it at all. They have been handed a giant pile of all keys to all homes in America. They went through the pile and found all but 64,000 keys to be too damaged to be usable. Those 64,000 keys are perfectly good, but they don't know which homes they belong to. They open up a shop allowing people to come in with their lock to check if their key is one of the 64,000. Do you go to check? Do you drive? Or do you…

Unless I misunderstood, they know which keys belongs to which houses. They successfully factored those keys, and unless they threw the metadata away they still know the domain that is using that key. And if they did throw the metadata away, they still have this pile of 64,000 prime factors. They can ask the domains for their public keys again and test if any of those factors matches.

> they know which keys belongs to which houses

Need to be corrected into "they claim to know which keys belongs to which houses", right?

Re: The keys to the keydom

#25

Post by reirob »

"Some 60 percent of the keys retrieved were not unique. Presumably, most of the duplicates are accounted for by organizations that have multiple servers all operating with the same cryptographic credentials, but there were also instances of apparently unaffiliated individuals sharing a key." - how is it possible that 60 percent have the same keys? I also do not understand why a big company would share the same public key across servers? If it is compromised (somebody got the private key) then all its servers are compromised, right?

Re: The keys to the keydom

#26

Post by reirob »

gpcz wrote: post #4

64,081 is really close to 65536 (2^16) -- I wonder if the 64,000 vulnerable TLS keys have anything to do with a bug similar to the 2008 Debian SSL key fiasco, where the only contributor to the key's entropy was the PID (2^15 combinations). It would be interesting to see data about the types of devices that have these weak keys, but then again if there is a correlation its release could be used maliciously in the wild…

This question has been asked in the comments to the article and there is answer: "Heninger et al. did check their data for “Debian weak keys.” They found 4,147 such TLS keys and 53,141 SSH keys."

Re: The keys to the keydom

#27

Post by alexkus »

reirob wrote: post #25

"Some 60 percent of the keys retrieved were not unique. Presumably, most of the duplicates are accounted for by organizations that have multiple servers all operating with the same cryptographic credentials, but there were also instances of apparently unaffiliated individuals sharing a key." - how is it possible that 60 percent have the same keys? I also do not understand why a big company would share the same public…

> I also do not understand why a big company would share the same public key across servers?

They might not be different servers, just different IPs. Multiple external IPs may all terminate at the same piece of hardware (Firewall, VPN device, SSL terminator, etc).

Re: The keys to the keydom

#28

Post by bigiain »

gbog wrote: post #24
BoppreH wrote: post #15

Earlier quoted context omitted.

Unless I misunderstood, they know which keys belongs to which houses. They successfully factored those keys, and unless they threw the metadata away they still know the domain that is using that key. And if they did throw the metadata away, they still have this pile of 64,000 prime factors. They can ask the domains for their public keys again and test if any of those factors matches.

> they know which keys belongs to which houses Need to be corrected into "they claim to know which keys belongs to which houses", right?

Well they did collect all the keys from their respective houses – the only thing stopping then knowing which key goes with which house is poor record keeping on their part…
Post reply on HN