Re: [cryptography] Why using asymmetric crypto like symmetric crypto isn't secure
On 11.11.2012 14:13, Adam Back wrote: > Note they are only saying fixed or small e because their approach requires > to know or guess e in order to compute m^e (if e is small you can try all > possible e). > I wouldnt think thats the end of it either - more things are clearly > leaking. eg Even with large, unknown e st |e| = |n| if you had known > plaintext ciphertext pairs with a multiplicative relationship like c1 = > m1^e > mod n, and c2 = m2^e mod n and c3 = m3^e mod n where m3 = m1*m2. Then > c1*c2-c3 = k.n and we're back to the find small factors to find k trick. Thank you very much for pointing that out. I also have the feeling that there are ways to extend the simple basic idea presented in the paper to other scenarios like large secret exponents or maybe PKCS#1-v1.5 encryption[1] but did not yet pursue that. Even the simple attack is a positive proof that the bad gut feeling about using RSA with a secret 64 bit modulus (in a place where something like Triple-DES would be quite sufficient) was not unjustified. And it covers the cases that are in my opinion the main practical risk, namely system designers tempted to use standard public key libraries for the described symmetric purposes in straight-forward way. Arjen Lenstra et al. in "Ron was wrong, Whit is right" (http://eprint.iacr.org/2012/064) tell us, >95% of all practical RSA exponents to be found on the Internet are 65537 while the overwhelming part of the rest is even smaller. So system designers who use something else than RSA with e=65537 will with a good probability have made a concious decision and invested some more thought about the crypto they are using (at least that is what I would hope). Then again, as Jon Callas correctly concluded, the additional work to invest in assuring that such an usual scheme is secure might be more economically put into other parts of system design. Hans-Joachim [1] My footnote (sorry, Peter, couldn't resist): Note that PKCS#1-v1.5 signature padding is deterministic, i. e. using RSA with short secret modulus as a private integrity mechanism for data deposited in the hands of other parties (in other words: cookies) in place of a symmetric MAC would also be susceptible to the simple attack. As James Muir pointed out, using OAEP/PSS with enough salt would prevent that. But way too many users/applications like DNSSEC still use PKCS#1-v1.5. -- Hans-Joachim Knobloch Security Consulting Secorvo Security Consulting GmbH Ettlinger Strasse 12-14, D-76137 Karlsruhe Tel. +49 721 255171-305, Fax +49 721 255171-100 hans-joachim.knobl...@secorvo.de, http://www.secorvo.de PGP: A766 A23F 1079 3075 DF18 56E0 F61F A8F8 Mannheim HRB 108319, Geschäftsführer: Dirk Fox ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Why using asymmetric crypto like symmetric crypto isn't secure
(I copied Hans-Joachim Knobloch onto the thread) Weiner is talking about small secret exponents (small d), no one does that. They choose smallish prime e, with low hamming weight (for encryption/signature verification efficiency) like 65537 (10001h) and get a random d, which will by definition be |d| > |n|/4. (The limit of Weiner's algorithm). (To get both |d| < |n|/4 (susceptible to Weiner attack) and small |e| isnt possible because you need ed = 1 mod LCM(p-1,q-1); which implies ed = 1 + k LCM(p-1,q-1). |LCM(p-1,q-1)| ~= |n| so to get |d| < |n|/4 you minimally need |e| > 3|n|/4 ie for a 1024 bit modulus, |e| >= 768 bits to get a |d| = 256-bits. The only people who would ever have ended up vulnerable to Weiner's attack are those intentionally and aggressively trying to reduce the server workload by aiming to artificially have very small |d|. The Knobloch eprint paper says that you cant naively keep the public modulus secret for small e, if the attacker has a few known plaintext/ciphertext pairs because c = m^e mod n implies m^e -c = k.n and as k.n can be factorized to find k. (p & q will be harder to find so you'll find k first if it is not also coincidentally itself large and prime, or composite of large enough primes to not be factorizable; if it doesnt factorize quickly use another known plaintext/ciphertext pair. Note they are only saying fixed or small e because their approach requires to know or guess e in order to compute m^e (if e is small you can try all possible e). I wouldnt think thats the end of it either - more things are clearly leaking. eg Even with large, unknown e st |e| = |n| if you had known plaintext ciphertext pairs with a multiplicative relationship like c1 = m1^e mod n, and c2 = m2^e mod n and c3 = m3^e mod n where m3 = m1*m2. Then c1*c2-c3 = k.n and we're back to the find small factors to find k trick. Adam On Sat, Nov 10, 2012 at 10:52:29AM +0800, Sandy Harris wrote: On Sat, Nov 3, 2012 at 5:29 PM, Peter Gutmann wrote: [...] We show that if the RSA cryptosystem is used in such a symmetric application, it is possible to determine the public RSA modulus if the public exponent is known and short, such as 3 or F4=65537, and two or more plaintext/ciphertext (or, if RSA is used for signing, signed value/signature) pairs are known. Is this a different attack from Weiner's "Cryptanalysis of Short RSA Secret Exponents"? madchat.awired.net/crypto/codebreakers/ShortSecretExponents.pdf I thought it had been known for at least a decade that small exponents were a bad idea, because of the Weiner paper. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Why using asymmetric crypto like symmetric crypto isn't secure
On Sat, Nov 3, 2012 at 5:29 PM, Peter Gutmann wrote: > [...] We show that if the RSA cryptosystem is used in such a symmetric > application, it is possible to determine the public RSA modulus if the > public exponent is known and short, such as 3 or F4=65537, and two or more > plaintext/ciphertext (or, if RSA is used for signing, signed > value/signature) pairs are known. Is this a different attack from Weiner's "Cryptanalysis of Short RSA Secret Exponents"? madchat.awired.net/crypto/codebreakers/ShortSecretExponents.pdf I thought it had been known for at least a decade that small exponents were a bad idea, because of the Weiner paper. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Why using asymmetric crypto like symmetric crypto isn't secure
On 03/11/12 09:29, Peter Gutmann wrote: In the past there have been a few proposals to use asymmetric cryptosystems, typically RSA, like symmetric ones by keeping the public key secret, the idea behind this being that if the public key isn't known then there isn't anything for an attacker to factor or otherwise attack. Turns out that doing this isn't secure: http://eprint.iacr.org/2012/588 Breaking Public Keys - How to Determine an Unknown RSA Public Modulus Hans-Joachim Knobloch [...] We show that if the RSA cryptosystem is used in such a symmetric application, it is possible to determine the public RSA modulus if the public exponent is known and short, such as 3 or F4=65537, and two or more plaintext/ciphertext (or, if RSA is used for signing, signed value/signature) pairs are known. I've actually encountered a practical application for this. If you have an HSM that allows unwrapping of private keys but keeps the whole result entirely secret, and want to implement PKCS#11 C_UnwrapKey and allow the modulus and public exponent of the private key to be queried through C_GetAttributeValue, and the user hasn't chosen to import the matching public key, then you have to do something like this. Or add a DerivePublicFromPrivate operation to the next release of the HSM firmware, which also works for DH, DSA, ECDSA, KCDSA, etc. :-) ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Why using asymmetric crypto like symmetric crypto isn't secure
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On Nov 3, 2012, at 7:03 PM, Peter Gutmann wrote: > Jon Callas writes: > >> Which immediately prompts the question of "what if it's long or secret?" [1] >> This attack doesn't work on that. > > The "asymmetric-as-symmetric" was proposed about a decade ago as a means of > protecting against new factorisation attacks, and was deployed as a commercial > product. I don't recall them keeping the exponent secret because there wasn't > any need to... until now that is. So I think Taral's comment about not using > crypto in novel ways is quite apropos here, the asymm-as-sym concept only > protected you against the emergence of novel factorisation attacks (or the use > of standard factorisation attacks on too-short keys) as long as no-one > bothered trying to attack the public-key-hiding itself. Point taken. I'm being too grumpy. I think this is a brilliant result because it gives us a "see, see" reference to give to people. I'm big on sneering at proofs of security because they often do not relate to real security in the real world in ways that upset me (a guy whose degree is in mathematical logic) to my core. If you want the same sort of rigor that math has, security is useless. On the other hand, and Hal Finney drove this home to me many times, they do tell you what sort of things you can ignore. This one is great because of the way it slaps intuition around. > >> If you believe that the only attack against RSA is factoring the modulus, >> then you can be seduced into thinking that hiding the modulus makes the >> attacker's job harder. > > Yup, and that was the flaw in the reasoning behind the keep-the-public-key- > secret system. So this a nice textbook illustration of why not to use crypto > in novel ways based purely on intuition. There are all sorts of things people do based on an intuition. Hell, I've done them. Sometimes they just present themselves. If I had a protocol that didn't expose public keys (suppose they're all wrapped in a secure transfer), I might point out that hey, this system has hidden RSA keys. But this points out that unless there is a lot of extra work you do, you didn't do squat. It also suggests that the conservative engineering approach, which is to say that unless you can characterize added security it's just fluff, has new backing in fact. Jon -BEGIN PGP SIGNATURE- Version: PGP Universal 3.2.0 (Build 1672) Charset: us-ascii wj8DBQFQluTIsTedWZOD3gYRAvvGAKDAGkbALD3jqLq8kmG7VIXWtJ2sWACfWOwG DFFKn3LjBEqvpwv4lqHYn04= =G0xh -END PGP SIGNATURE- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Why using asymmetric crypto like symmetric crypto isn't secure
Jon Callas writes: >Which immediately prompts the question of "what if it's long or secret?" [1] >This attack doesn't work on that. The "asymmetric-as-symmetric" was proposed about a decade ago as a means of protecting against new factorisation attacks, and was deployed as a commercial product. I don't recall them keeping the exponent secret because there wasn't any need to... until now that is. So I think Taral's comment about not using crypto in novel ways is quite apropos here, the asymm-as-sym concept only protected you against the emergence of novel factorisation attacks (or the use of standard factorisation attacks on too-short keys) as long as no-one bothered trying to attack the public-key-hiding itself. >If you believe that the only attack against RSA is factoring the modulus, >then you can be seduced into thinking that hiding the modulus makes the >attacker's job harder. Yup, and that was the flaw in the reasoning behind the keep-the-public-key- secret system. So this a nice textbook illustration of why not to use crypto in novel ways based purely on intuition. Peter. [1] Not my footnote. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Why using asymmetric crypto like symmetric crypto isn't secure
On 12-11-03 05:29 PM, Jon Callas wrote: >> In the past there have been a few proposals to use asymmetric >> cryptosystems, >> typically RSA, like symmetric ones by keeping the public key secret, >> the idea >> behind this being that if the public key isn't known then there isn't >> anything >> for an attacker to factor or otherwise attack. Turns out that doing this >> isn't secure: >> >> http://eprint.iacr.org/2012/588 >> >> Breaking Public Keys - How to Determine an Unknown RSA Public Modulus >> Hans-Joachim Knobloch >> >> [...] We show that if the RSA cryptosystem is used in such a symmetric >> application, it is possible to determine the public RSA modulus if the >> public exponent is known and short, such as 3 or F4=65537, and two or >> more >> plaintext/ciphertext (or, if RSA is used for signing, signed >> value/signature) pairs are known. > > Great paper, however, the conclusions here and in replies are not quite > right. The paper itself says, > > it is possible to determine the public RSA modulus if the public > exponent is known and short, such as 3 or F4=65537, > > > Which immediately prompts the question of "what if it's long or secret?" > [1] This attack doesn't work on that. > > What it tells you is that if for some strange reason, you are going to > keep the public key secret, you need to make the exponent part of the > secret. That's the real, real lesson here -- an RSA key has an exponent > and a modulus and unless the exponent is secret, the key isn't secret. > And of course secret doesn't mean the usual ones just put in a cabinet. Thanks for directing the thread back toward reality, Jon :-) I saw the eprint paper last week. It simply notes that if you have two plaintext/ciphertext pairs, (m1,c1), (m2,c2), for textbook RSA (i.e. RSA where you don't pad) and you know the public exponent, then you can compute the RSA modulus from N'=gcd(c1-m1^e, c2-m2^e). If e is small, then N' will be a small multiple of N; you can easily find the small factors of N' and remove them to get N. So, as Jon said, there's no point in hiding your RSA modulus if you are using a small public exponent like e=3, 17 or 2^16+1 and you are doing textbook RSA. However, no one should be doing textbook RSA. If you want to encrypt with RSA, then use RSA-OAEP. In that case, the gcd trick from the paper no longer works because the plaintext is salted -- the random bytes that form the salt aren't easy to obtain from a plaintext/ciphertext pair. It is possible that the modulus might still leak if you can analyze several RSA-OAEP plaintext/ciphertext pairs. That seems like a research type question to me. You could consider the same problem with RSA-PKCS1-v1.5. -James signature.asc Description: OpenPGP digital signature ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Why using asymmetric crypto like symmetric crypto isn't secure
> In the past there have been a few proposals to use asymmetric cryptosystems, > typically RSA, like symmetric ones by keeping the public key secret, the idea > behind this being that if the public key isn't known then there isn't anything > for an attacker to factor or otherwise attack. Turns out that doing this > isn't secure: > > http://eprint.iacr.org/2012/588 > > Breaking Public Keys - How to Determine an Unknown RSA Public Modulus > Hans-Joachim Knobloch > > [...] We show that if the RSA cryptosystem is used in such a symmetric > application, it is possible to determine the public RSA modulus if the > public exponent is known and short, such as 3 or F4=65537, and two or more > plaintext/ciphertext (or, if RSA is used for signing, signed > value/signature) pairs are known. Great paper, however, the conclusions here and in replies are not quite right. The paper itself says, it is possible to determine the public RSA modulus if the public exponent is known and short, such as 3 or F4=65537, Which immediately prompts the question of "what if it's long or secret?" [1] This attack doesn't work on that. What it tells you is that if for some strange reason, you are going to keep the public key secret, you need to make the exponent part of the secret. That's the real, real lesson here -- an RSA key has an exponent and a modulus and unless the exponent is secret, the key isn't secret. And of course secret doesn't mean the usual ones just put in a cabinet. And for us logic weenies, he does not show that a secret public key is insecure. He shows that there is no added security for secret public keys where the exponent is known and short. Those keys are just as secure as they would be if they had known public keys (which could be not at all). The danger is not using a public key algorithm in a novel way, it's using it in a novel way and thinking that your intuition is correct. It's thinking through the consequences of your actions. If you believe that the only attack against RSA is factoring the modulus, then you can be seduced into thinking that hiding the modulus makes the attacker's job harder. The brilliance of this paper is that is concisely shows that unless you take care is selecting an exponent, the modulus leaks easily. Obviously, a secret public key isn't *less* secure. (The reductio ad absurdum is left as an exercise for the reader.) It must be as secure or greater. But if it's greater, by how much and how would you know? If you can't answer that question, or at least handwave in the direction of an answer. If you don't have a lower bound on the improved security of that tweak, then you should consider it to be zero. This is why although it's still left open as to whether a truly secret public key adds security, we should assume there's no added security. The engineering dope-slapping that needs to happen is over getting distracted. Security systems are designed to meet certain assumptions. Changing the assumptions changes the result. Public-key cryptosystems are designed in such a way that the public key is a public parameter. They are not designed to have added security when the public key is secret. This paper shows a case in which there is no added security, and as a matter of fact, the modulus leaks from the ciphertext. If you want to make the public key secret, you have to do more work and there's no indication of how much added security there is -- it could be zero. No one has ever done a keygen with any work done into considering the care you need to make the exponent be a secret parameter. On the contrary, it's usually a quasi-constant. All that added work could be put somewhere else, and as we all know there's plenty of ways to induce bugs by doing the extra work. Therefore, in the words of Elvis Costello, don't get cute. If you use reasonable parameters in off-the-shelf subsystems, you work just fine. Getting cute at best adds in some undefinable bit of good-feeling, which isn't the same thing as security. Jon [1] Operationally, long or secret will be long *and* secret because there are no commonly used long exponents, and all the common exponents are short. Phrased another way, the short exponents are easily iterated over. PGP.sig Description: PGP signature ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Why using asymmetric crypto like symmetric crypto isn't secure
I sometimes quote the "rules of crypto" to friends and co-workers. They are: First rule of crypto: Do not invent your own crypto. Second rule of crypto: Do not implement your own crypto. New third rule: Do not use crypto in novel ways. *sigh* - Taral ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Why using asymmetric crypto like symmetric crypto isn't secure
On Sat, Nov 03, 2012 at 12:50:47PM +0100, Ralph Holz wrote: > Hi, > > > In the past there have been a few proposals to use asymmetric cryptosystems, > > typically RSA, like symmetric ones by keeping the public key secret, the > > idea > > behind this being that if the public key isn't known then there isn't > > anything > > for an attacker to factor or otherwise attack. Turns out that doing this > > isn't secure: > > > > http://eprint.iacr.org/2012/588 > > A question: The attack seems to aim at getting n = p * q, and then > factor it. I.e. what they really show is that it is possible to derive > the public key from two plain/ciphertext pairs; alternatively a multiple > of n. In essence, there is no point in keeping the public key secret as > it can be guessed. > > However, the factoring would still remain as a huge task for the > attacker, unless RSA is used at a meagre bit length, as in their example. > > Correct? This paper was actually quite timely for us. One of our group was proposing a key management protocol for federated wireless sensor networks that relied on both halves of an ECC keypair being kept secret. In this particular protocol, the main advantage was that each sensor node would maintain a unique public key for an authentication server, which was then used to negotiate session keys. The combination allowed a minimal number of asymmetric operations while preserving perfect forward secrecy. My initial reaction was that using asymmetric crypto in a relatively unproven way was likely to cause more problems, or at least risks, than it was worth, and I proposed a more 'traditional' alternative. This turned into a relatively long argument. I stumbled across this paper the next day on the cryptology ePrint archive, which finally let me convince my colleague to go with the more traditional approach. The point here is that the secrecy of the public key was used for properties beyond an extra layer of obscurity against factoring. Learning the public key as described in the paper (admittedly for RSA not ECC) would have completely broken the protocol. Joss -- Joss Wright | @JossWright http://www.pseudonymity.net ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Why using asymmetric crypto like symmetric crypto isn't secure
Hi, > In the past there have been a few proposals to use asymmetric cryptosystems, > typically RSA, like symmetric ones by keeping the public key secret, the idea > behind this being that if the public key isn't known then there isn't anything > for an attacker to factor or otherwise attack. Turns out that doing this > isn't secure: > > http://eprint.iacr.org/2012/588 A question: The attack seems to aim at getting n = p * q, and then factor it. I.e. what they really show is that it is possible to derive the public key from two plain/ciphertext pairs; alternatively a multiple of n. In essence, there is no point in keeping the public key secret as it can be guessed. However, the factoring would still remain as a huge task for the attacker, unless RSA is used at a meagre bit length, as in their example. Correct? Ralph signature.asc Description: OpenPGP digital signature ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] Why using asymmetric crypto like symmetric crypto isn't secure
In the past there have been a few proposals to use asymmetric cryptosystems, typically RSA, like symmetric ones by keeping the public key secret, the idea behind this being that if the public key isn't known then there isn't anything for an attacker to factor or otherwise attack. Turns out that doing this isn't secure: http://eprint.iacr.org/2012/588 Breaking Public Keys - How to Determine an Unknown RSA Public Modulus Hans-Joachim Knobloch [...] We show that if the RSA cryptosystem is used in such a symmetric application, it is possible to determine the public RSA modulus if the public exponent is known and short, such as 3 or F4=65537, and two or more plaintext/ciphertext (or, if RSA is used for signing, signed value/signature) pairs are known. Peter. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
