RSA paid off by NSA. Does this mean I should generate new public/private key???

sneakyimp

Oh gawd.
http://www.reuters.com/article/2013/12/20/us-usa-security-rsa-idUSBRE9BJ1C220131220

I recall that when I generated my 4096-bit key, I thought it would be majorly secure, but now I remember specifying 'rsa' when I typed the command:

ssh-keygen -t rsa -b 4096

One must wonder about the key generation algorithms used. The command runs so quickly, which suggests that it is using some kind of short-cut-type algorithm for number generation which in turn suggests that the keys generated are not nearly as random as one might hope. I.e., rather than creating some key lost deep among the 10¹²³³ or so possibilities, it's generating a key returned by some much smaller subset of that prime number space -- or something like that.

Here's where I hope some math madman jumps in to lay some serious knowledge on me to either reassure or to panic us all.

laserlight

The rsa option refers to the RSA public key crypto algorithm, not to the company founded by the same people who that algorithm is named after.

dalecosp

You know, interestingly enough, the other day I logged into a devel server I keep at my house, and was rejected. No biggie, I thought; I probably changed the passphrase recently and forgot the new one. So I tried root and got in without a prompt.

Something stinks in Kansas, friends. Or is it in Virginia? ;-)

sneakyimp

laserlight;11036555 wrote:
The rsa option refers to the RSA public key crypto algorithm, not to the company founded by the same people who that algorithm is named after.

I appreciate you pointing this out, but I think the question is still legitimate. It would not be unheard of for an open source project to mimic the techniques used by the company founded by the guys who invented the algorithm.

As Bruce Schneier has been quoted as saying, "Security is not something you can buy, it is something you must get for yourself," or something like that. Note that I have not received any message signed by Schneier that will allow me to reliably attribute this saying to him.

This topic seems to relate to my other one on Counting Primes. If there are roughly 10¹²²³ primes of big length 4096, how does ssh-keygen generate a key so quickly? Isn't verifying a prime with 1200 decimal digits going to take a LONG time? NOTE: I'm still getting comfortable with the math, apparently the product of the prime keys has 4096 bit length. Still, even half that is a huge number and I find it hard to believe that any program could reliably accomplish this feat as quickly as ssh-keygen seems to.

Dalescop: perhaps you set up puTTY (or ssh) with a key pair? I know it's probably bad practice but I like to generate my key pairs without a passphrase -- saves a lot of typing over the course of a day.

sneakyimp

Unless I'm mistaken, the ssh-keygen command is provided by OpenSSH -- at least on an apple computer. I've been unable to determine whether there is some master/authoritative source code for this command, but apple does appear to offer some source code:
http://www.opensource.apple.com/source/OpenSSH/OpenSSH-7.1/openssh/ssh-keygen.c

This source code refers to a function rsa_generate_key which I suspect is declared in openssl/rsa.h but I can't seem to locate this source on the apple site just yet. Or at least I can't locate the one referred to in the ssh-keygen.c above. I did find this one:
http://www.opensource.apple.com/source/DSPasswordServerPlugin/DSPasswordServerPlugin-18/OpenSSH/rsa.c

laserlight

sneakyimp wrote:
I appreciate you pointing this out, but I think the question is still legitimate. It would not be unheard of for an open source project to mimic the techniques used by the company founded by the guys who invented the algorithm.

Certainly. I remember having to change keys some years ago because of a security bug in Debian.

sneakyimp wrote:
If there are roughly 10¹²²³ primes of big length 4096, how does ssh-keygen generate a key so quickly? Isn't verifying a prime with 1200 decimal digits going to take a LONG time? NOTE: I'm still getting comfortable with the math, apparently the product of the prime keys has 4096 bit length. Still, even half that is a huge number and I find it hard to believe that any program could reliably accomplish this feat as quickly as ssh-keygen seems to.

I don't actually know how ssh-keygen does it precisely as I have never investigated it, but this part is relatively easy to explain: the primes found are probably probable primes, or rather highly unlikely to be composites, since the probabilistic Rabin-Miller algorithm or something along the same lines is likely to be used to "verify" primality. Hence, in fact it is not reliable, but with a sufficient number of iterations it comes close enough for our purposes.

NogDog

So . . . what exactly is it you are trying to hide from the NSA?

Please come this way; it is time for the body cavity search.

:evilgrin:

sneakyimp

A friend just sent me this:
http://www.theregister.co.uk/2013/12/20/openssl_crypto_bug_beneficial_sorta/

Apparently the compromised piece was very nearly in use in openssl and was only disabled through some fishy bug situation. I'm feeling less sanguine about the security of my keys.

NogDog wrote:
So . . . what exactly is it you are trying to hide from the NSA?

Please come this way; it is time for the body cavity search.

I laughed, but a bit nervously. Schneier's book hints at the the suffering inflicted on Zimmerman, inventor of PGP, by the US Government. He was the target of a criminal investigation.

sneakyimp

It's 2013, do you know what your key generator is doing?

EDIT: I think it's worth paying attention to Schneier's and Mitnick's reactions to RSA's actions:
https://www.schneier.com/blog/archives/2013/12/nsa_spying_who.html
https://twitter.com/kevinmitnick/status/415225982035824640

dalecosp

sneakyimp;11036573 wrote:
Dalescop: perhaps you set up puTTY (or ssh) with a key pair? I know it's probably bad practice but I like to generate my key pairs without a passphrase -- saves a lot of typing over the course of a day.

I don't allow remote root logins; I was at the console.

And that is what is scary ;-)