5 ms·
Stupid certificate tricks
- tptacek 11y agoNot that the author claimed it to be safe, but this probably isn't secure: https://rjlipton.wordpress.com/2012/03/01/do-gaps-between-primes-affect-rsa-keys/ 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. :)
- ryan-c 11y agoIt 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 http://link.springer.com/chapter/10.1007%2F11693383_9 1. https://books.google.com/books?id=skYDCAAAQBAJ&pg=PA128&lpg=PA128&dq=space+efficient+rsa+backdoor&source=bl&ots=KVNcXU6iWS&sig=7_sztRtcFcaFSzA2_xymwqJf9jk&hl=en&sa=X&ei=gENOVYTJBpPooAT2o4GgCg&ved=0CDIQ6AEwAw#v=onepage&q=space%20efficient%20rsa%20backdoor&f=false https://books.google.com/books?id=skYDCAAAQBAJ&pg=PA128&lpg=...
- pbsd 11y agoThis 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 http://link.springer.com/chapter/10.1007%2F3-540-46877-3_42 [2] http://link.springer.com/article/10.1007/BF00190758 http://link.springer.com/article/10.1007/BF00190758 [3] http://patents.justia.com/patent/6134325 http://patents.justia.com/patent/6134325 [4] http://link.springer.com/chapter/10.1007%2F3-540-49649-1_1 http://link.springer.com/chapter/10.1007%2F3-540-49649-1_1 [5] http://cr.yp.to/sigs/key.html http://cr.yp.to/sigs/key.html [6] http://joye.site88.net/papers/Joy08rsacompr.pdf http://joye.site88.net/papers/Joy08rsacompr.pdf [7] https://eprint.iacr.org/2002/183 https://eprint.iacr.org/2002/183
- ffk 11y agorya.nc is also actively using the certificate he generated. :)
- mellavora 11y agoI like people with guts.
- devcpp 11y agoReally? 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?
- ryan-c 11y agoI 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.
- wolf550e 11y agoIs the private key from the blog post valid to impersonate your server?
- jcase 11y agoRunning the openssl s_client command from the article will show you live.
- kbwt 11y agoSo 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.
- function_seven 11y agoNot 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.
- e12e 11y agoI'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...
- ryan-c 11y agoThe 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).
- alanh 11y ago"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?
- Dylan16807 11y agoIn 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.
- kccqzy 11y agoThis 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