The technique relies on starting a search for one of the prime factors of the modulus at a particular (large) place, although if I understand the code right, not a place related to the other factor, so maybe it's not devastating, or who knows. That article is still very worth reading. :)
The article about prime gaps is interesting, thanks for sharing.
There's a paper[0] that appears to use a very similar technique to achieve an RSA backdoor, however I don't have access to the full article. From the excerpt[1] I was able to find (just now - I wrote the code quite a while ago) they appear to choose p, randomly generate n with data spliced in the top half of the modulus, and find an acceptable q. The paper seems to argue the scheme is secure against those who don't have the backdoor key, but there are some pages hidden in the middle of that.
This technique is quite old, actually, and has historically been used to compress RSA keys. It is perfectly safe, provided you don't have access to the original modulus (the intuition here is that if p is chosen uniformly at random, then next_prime(n/p) will also be (almost) uniformly distributed). Other techniques exist that permit to embed information about d or p inside the modulus (e.g. [7]), but those don't apply in this case.
The first appearance of this technique was in [1, §2.1]. Later, Vanstone and Zucherato reinvented and also tried to patent it [2, 3]. Lenstra also joined in [4]. Bernstein and Coppersmith suggested a method, based on lattice reduction, that reduces RSA keys to up to 1/3 of their size [5]. Joye [6] describes a method achieving this without explicitly using lattice reduction.
So basically the idea with RSA is that all computations are done modulo N, where N is the product of two secret primes p and q.
What was done here is manipulating the high bits of N (yielding N'), and finding new prime q' slightly larger than N'/p. The high bits of N'' = p * q' are unaffected because the gap between N'/p and q' is small enough in practice.
Not sure why, but your explanation made it click for me in a way that the linked site couldn't. The primes, I suppose (punctuation, not the unfactorable numbers).
I'm going to have to read the article again, carefully -- and play some more with RSA. But I'm surprised so many... digits are shared between the secret key and the public cert. Or is that a typo in the article?
I've only done the toy mental gymnastics with RSA in base10 -- it's probably a good idea to play with in bitstrings as well...
The modulus - the part that has data embedded in it - isn't a secret part of the key. I think the part confusing you is that the modulus (N) is included in both the public and private key.
The private key contains: [p, q, N, e, d, d_p, d_q, q_inv]
The public key contains: [N, e]
If you do find a typo somewhere, please let me know (I have an email address listed in my HN profile).
Thank you. Yes, it was the header that confused me ("RSA SECRET KEY") - I've not played much with actual RSA - when doing the math with pen and paper it's easy to gloss over things like what's concatenated, and were/how things are stored/published.
pedantic: Conceptually, the public key is n, e and the private key is n, d. The other values you mention are secret, in that they can be used to derive d, but aren't the private key. OpenSSL keeps some intermediate values for performance, but they aren't strictly required for RSA to work.
If the n is public, it's not really part of the private key is it? (Or private key) Granted d is not sufficient as a key either - but n clearly isn't secret. Is there a term for that? "Commmon key", maybe? Key parameter? Keystone? ;)
If one wanted to be even more pedantic, N is the modulus, e is the public exponent and d is the private exponent. N is required for both public and private operations.
Yes. But is there a more general (or specific, depending on one's point of view) term that applies to (public key) cryptography? Eg "some random, public, non-repeated stuff" is a nonce, a key is a parameter to an encryption function etc. Ecc keys are over a certain [ed]curve - so you need parameters for that too, but modulus while entirely correct mathematically, doesn't really capture the essence of N from a cryptographic point of view. Maybe just "public parameter"?
Really? I'm getting serial number 0X043f60 (instead of 0x1599c5), validity starting on May 7 2015. Might that have to do with using Firefox or anything client-related? Or he switched it?
This reminds me of tricks like putting a "we're hiring" comment in the source code, the developer console or the HTTP header but this takes it to a whole new level.
In what way does it do that? It starts with two fully random primes and then fixes some of the bits in the middle of one. Then it adjusts the lowest bits to make it prime again. Almost all of that prime is still random, and it's still within a tiny fraction of a percent of its original value.
Not that the author claimed it to be safe, but this probably isn't secure:
https://rjlipton.wordpress.com/2012/03/01/do-gaps-between-pr...
The technique relies on starting a search for one of the prime factors of the modulus at a particular (large) place, although if I understand the code right, not a place related to the other factor, so maybe it's not devastating, or who knows. That article is still very worth reading. :)
It does say "stupid" right there in the title :-)
The article about prime gaps is interesting, thanks for sharing.
There's a paper[0] that appears to use a very similar technique to achieve an RSA backdoor, however I don't have access to the full article. From the excerpt[1] I was able to find (just now - I wrote the code quite a while ago) they appear to choose p, randomly generate n with data spliced in the top half of the modulus, and find an acceptable q. The paper seems to argue the scheme is secure against those who don't have the backdoor key, but there are some pages hidden in the middle of that.
0. http://link.springer.com/chapter/10.1007%2F11693383_9
1. https://books.google.com/books?id=skYDCAAAQBAJ&pg=PA128&lpg=...
This technique is quite old, actually, and has historically been used to compress RSA keys. It is perfectly safe, provided you don't have access to the original modulus (the intuition here is that if p is chosen uniformly at random, then next_prime(n/p) will also be (almost) uniformly distributed). Other techniques exist that permit to embed information about d or p inside the modulus (e.g. [7]), but those don't apply in this case.
The first appearance of this technique was in [1, §2.1]. Later, Vanstone and Zucherato reinvented and also tried to patent it [2, 3]. Lenstra also joined in [4]. Bernstein and Coppersmith suggested a method, based on lattice reduction, that reduces RSA keys to up to 1/3 of their size [5]. Joye [6] describes a method achieving this without explicitly using lattice reduction.
[1] http://link.springer.com/chapter/10.1007%2F3-540-46877-3_42
[2] http://link.springer.com/article/10.1007/BF00190758
[3] http://patents.justia.com/patent/6134325
[4] http://link.springer.com/chapter/10.1007%2F3-540-49649-1_1
[5] http://cr.yp.to/sigs/key.html
[6] http://joye.site88.net/papers/Joy08rsacompr.pdf
[7] https://eprint.iacr.org/2002/183
So basically the idea with RSA is that all computations are done modulo N, where N is the product of two secret primes p and q.
What was done here is manipulating the high bits of N (yielding N'), and finding new prime q' slightly larger than N'/p. The high bits of N'' = p * q' are unaffected because the gap between N'/p and q' is small enough in practice.
Not sure why, but your explanation made it click for me in a way that the linked site couldn't. The primes, I suppose (punctuation, not the unfactorable numbers).
Thanks.
I'm going to have to read the article again, carefully -- and play some more with RSA. But I'm surprised so many... digits are shared between the secret key and the public cert. Or is that a typo in the article?
I've only done the toy mental gymnastics with RSA in base10 -- it's probably a good idea to play with in bitstrings as well...
The modulus - the part that has data embedded in it - isn't a secret part of the key. I think the part confusing you is that the modulus (N) is included in both the public and private key.
The private key contains: [p, q, N, e, d, d_p, d_q, q_inv]
The public key contains: [N, e]
If you do find a typo somewhere, please let me know (I have an email address listed in my HN profile).
Thank you. Yes, it was the header that confused me ("RSA SECRET KEY") - I've not played much with actual RSA - when doing the math with pen and paper it's easy to gloss over things like what's concatenated, and were/how things are stored/published.
pedantic: Conceptually, the public key is n, e and the private key is n, d. The other values you mention are secret, in that they can be used to derive d, but aren't the private key. OpenSSL keeps some intermediate values for performance, but they aren't strictly required for RSA to work.
Right, I was referring to what values are in the PEM serializations of the private and public key, since that was what e12e seemed to be confused by.
If the n is public, it's not really part of the private key is it? (Or private key) Granted d is not sufficient as a key either - but n clearly isn't secret. Is there a term for that? "Commmon key", maybe? Key parameter? Keystone? ;)
If one wanted to be even more pedantic, N is the modulus, e is the public exponent and d is the private exponent. N is required for both public and private operations.
Yes. But is there a more general (or specific, depending on one's point of view) term that applies to (public key) cryptography? Eg "some random, public, non-repeated stuff" is a nonce, a key is a parameter to an encryption function etc. Ecc keys are over a certain [ed]curve - so you need parameters for that too, but modulus while entirely correct mathematically, doesn't really capture the essence of N from a cryptographic point of view. Maybe just "public parameter"?
The usual term here is indeed "parameter", as in "parameter validation flaw".
rya.nc is also actively using the certificate he generated. :)
I like people with guts.
Really? I'm getting serial number 0X043f60 (instead of 0x1599c5), validity starting on May 7 2015. Might that have to do with using Firefox or anything client-related? Or he switched it?
I updated the server certificate to one signed with RSA+SHA256 to make chrome happy, but the new one has the same thing done to it.
Is the private key from the blog post valid to impersonate your server?
Depends on whether he revoked it or not.
The private key in the article was generated specifically for the article as an example - there's no CA-signed certificate that used it.
Also, certificate revocation is very unreliable.
Running the openssl s_client command from the article will show you live.
This reminds me of tricks like putting a "we're hiring" comment in the source code, the developer console or the HTTP header but this takes it to a whole new level.
Edit: typo
"I couldn't come up with an an attack vector, but I didn’t try very hard."
Would it be feasible to exploit the fact that this trick relies on primes very close to each other?
In what way does it do that? It starts with two fully random primes and then fixes some of the bits in the middle of one. Then it adjusts the lowest bits to make it prime again. Almost all of that prime is still random, and it's still within a tiny fraction of a percent of its original value.