question about rsa encryption
I have a question regarding RSA encryption - forgive me if this seems amateur-ish -, but 'm still a beginner. I seem to recall reading somewhere that there is some issue with directly encrypting data with an RSA public key, perhaps some vulnerability, but I can't find any reference after a cursory look. Does anyone know of any issue with using RSA encryption to encrypt a symmetric key under the target's public key if the encrypted value is public (e.g. sent over a network)? Thanks, Scott - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: question about rsa encryption
In message <[EMAIL PROTECTED]>, "Scott G. Kelly" writes: >I have a question regarding RSA encryption - forgive me if this seems >amateur-ish -, but 'm still a beginner. I seem to recall reading >somewhere that there is some issue with directly encrypting data with an >RSA public key, perhaps some vulnerability, but I can't find any >reference after a cursory look. Does anyone know of any issue with using >RSA encryption to encrypt a symmetric key under the target's public key >if the encrypted value is public (e.g. sent over a network)? > Transmitting a private key under RSA encryption can have subtle failure modes. I suggest that you use a published standard such as OAEP, from PKCS #1. --Steve Bellovin, http://www.research.att.com/~smb (me) http://www.wilyhacker.com (2nd edition of "Firewalls" book) - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: question about rsa encryption
Scott G. Kelly <[EMAIL PROTECTED]> wrote: > I seem to recall reading somewhere that there is some issue > with directly encrypting data with an > RSA public key, perhaps some vulnerability The short answer is that you should use one of the standard padding modes that are designed for RSA encryption, usually OAEPPadding. There are subtleties that the paddings are designed to take into to account, and if you use the padding you don't need to know all of them. -- sidney - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: question about rsa encryption
On Mon, 3 Feb 2003, Scott G. Kelly wrote: >I have a question regarding RSA encryption - forgive me if this seems >amateur-ish -, but 'm still a beginner. I seem to recall reading >somewhere that there is some issue with directly encrypting data with an >RSA public key, perhaps some vulnerability, but I can't find any >reference after a cursory look. Does anyone know of any issue with using >RSA encryption to encrypt a symmetric key under the target's public key >if the encrypted value is public (e.g. sent over a network)? RSA is subject to blinding attacks and several other failure modes if used without padding. For details on what that means, read the cyclopedia cryptologia article on RSA. http://www.disappearing-inc.com/R/rsa.html Bear - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: question about rsa encryption
Scott G. Kelly wrote: I seem to recall reading somewhere that there is some issue with directly encrypting data with an RSA public key, perhaps some vulnerability, but I can't find any reference after a cursory look. There are a few different ones, some simple and some complex. First of all, imagine encrypting 0 or 1. Encryption leaves these numbers unchanged. Now, if each possible plaintext had equal probability, this would be extremely unlikely. However, in practice it is likely that users may want to encrypt small numbers. Another problem is that RSA encryptions multiply. If r(x) is the encryption operation, then r(x) r(y) = r(xy). Informally: r(x) r(y) = (x ** e) (y ** e) = x * x * x * ... * y * y * y = xy * xy * ... * xy = (xy) ** e = r(xy) I think there are a few others too... -- Pete - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
AW: question about rsa encryption
> Von: Scott G. Kelly [mailto:[EMAIL PROTECTED]] > > Does anyone know of any issue > with using > RSA encryption to encrypt a symmetric key under the target's > public key > if the encrypted value is public (e.g. sent over a network)? > You have to be very careful in designing and implementing your _de_cryption routines. There have been some attacks when the decryption is not done correctly. References are: - Daniel Bleichbacher, Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1. CRYPTO 1998: 1-12. - James Manger, A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0. CRYPTO 2001: 230-238 These attacks are against PKCS#1 padding, and for the method you describe (direct encryption of a symmetric key with zero padding) I had a paper at this year's PKC conference describing some attacks. I hope this helps, Ulrich Kuehn - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: question about rsa encryption
On Tue, 4 Feb 2003, Sidney Markowitz wrote: > The short answer is that you should use one of the standard padding modes > that are designed for RSA encryption, usually OAEPPadding. There are > subtleties that the paddings are designed to take into to account, and if > you use the padding you don't need to know all of them. And if one loves to learn about every single one of them, can you (or others) give some references ? Thanks in advance Ralf *.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.* * Ralf Senderek <[EMAIL PROTECTED]> http://senderek.de * What is privacy * * Sandstr. 60 D-41849 Wassenberg +49 2432-3960 * without * * PGP: AB 2C 85 AB DB D3 10 E7 CD A4 F8 AC 52 FC A9 ED * Pure Crypto? * *.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.* - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: question about rsa encryption
> RSA is subject to blinding attacks and several other failure modes if > used without padding. For details on what that means, read the > cyclopedia cryptologia article on RSA. > > http://www.disappearing-inc.com/R/rsa.html That brings on another amateur question. In that article it says, "If the public exponent is less than a quarter of the modulus, RSA can be insecure." Well, the public exponents I've seen range from 17 to 65537. What gives? Is this just one of the many weaknesses mitigated by proper padding? - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: question about rsa encryption
Ralf Senderek" <[EMAIL PROTECTED]> asked: > And if one loves to learn about every single one of them, > can you (or others) give some references ? The page titled "Prescriptions for Applications that are Vulnerable to the Adaptive Chosen Ciphertext Attack on PKCS #1 v1.5" at URL http://www.rsasecurity.com/rsalabs/pkcs1/prescriptions.html is not a complete explanation, but if you read it and start following the links from there you should find what you want to know. There are links to various articles on PKCS#1, and there is some explanation of rationale in the section on OAEP in the PKCS#1 v2.1 standard. -- sidney - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
RE: question about rsa encryption
> That brings on another amateur question. In that article it says, > "If the public exponent is less than a quarter of the modulus, RSA > can be insecure." > > Well, the public exponents I've seen range from 17 to 65537. What > gives? Is this just one of the many weaknesses mitigated by proper > padding? This should probably refer to the private exponent. Weiner's continued fraction attack (from http://www3.sympatico.ca/wienerfamily/Michael/MichaelPapers/ShortSecretExpon ents.pdf) recovers the private exponent if it's known to be less than a quarter the length of the modulus (if the factors of the modulus are approximately the same size and other reasonable conditions are met). More recently, Dan Boneh and Glenn Durfee described a lattice attack: to prevent this, the length of the private exponent must be at least (1 - sqrt(2)) times the length of the modulus. http://crypto.stanford.edu/~dabo/abstracts/lowRSAexp.html Nick Howgrave-Graham gave some arguments at CaLC 2001 as to why this attack probably isn't going to get any better. There's a really good survey of attacks on the RSA cryptosystem at http://crypto.stanford.edu/~dabo/abstracts/RSAattack-survey.html which should help too. Cheers, William - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: question about rsa encryption
Matt Crawford <[EMAIL PROTECTED]> writes: > > RSA is subject to blinding attacks and several other failure modes if > > used without padding. For details on what that means, read the > > cyclopedia cryptologia article on RSA. > > > > http://www.disappearing-inc.com/R/rsa.html > > That brings on another amateur question. In that article it says, > "If the public exponent is less than a quarter of the modulus, RSA > can be insecure." > > Well, the public exponents I've seen range from 17 to 65537. What > gives? Is this just one of the many weaknesses mitigated by proper > padding? Yes. Notice that the next sentence was: "You should consider padding every block encrypted with RSA with randomized salt, if you can; 100 bits or more will make any of these attacks fail completely." -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: question about rsa encryption
> > RSA is subject to blinding attacks and several other failure modes if > > used without padding. For details on what that means, read the > > cyclopedia cryptologia article on RSA. > > > > http://www.disappearing-inc.com/R/rsa.html > > That brings on another amateur question. In that article it says, > "If the public exponent is less than a quarter of the modulus, RSA > can be insecure." Read the section on Hastad's Broadcast Attack from Boneh's excellent survey paper "Twenty years of attacks on the RSA cryptosystem" The paper covers these basic facts about RSA, you can get it at http://crypto.stanford.edu/~dabo/pubs.html The section on RSA in HAC will also answer your question. --Anton - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: question about rsa encryption
> > That brings on another amateur question. In that article it says, > > "If the public exponent is less than a quarter of the modulus, RSA > > can be insecure." > > > > Well, the public exponents I've seen range from 17 to 65537. What > > gives? Is this just one of the many weaknesses mitigated by proper > > padding? > > This should probably refer to the private exponent. No, it also applies to the public exponent if the messages you encrypt are related in a simple way (something like OAEP will make them *not* related in that simple way and prevent the attack). Funny thing is that the attack is described in the paper by Boneh that *you* cited, which I also mentioned in my last post... There are also attacks on low private exponents, but that`s something else (good randomized padding doesn't prevent that)... --Anton - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: question about rsa encryption
Hello Scott, At 03/02/03 21:50, Scott G. Kelly wrote: I have a question regarding RSA encryption - forgive me if this seems amateur-ish -, but 'm still a beginner. I seem to recall reading somewhere that there is some issue with directly encrypting data with an RSA public key, perhaps some vulnerability, but I can't find any reference after a cursory look. Does anyone know of any issue with using RSA encryption to encrypt a symmetric key under the target's public key if the encrypted value is public (e.g. sent over a network)? Sorry for the delayed response. As mentioned in the other postings, there are several technical problems with doing the RSA encryption in its most simple fashion by exponentiation and MOD calculation alone. However, in addition to all that was said, please note the following two general problems with such an approach, which apply not just to RSA but to any other asymmetric encryption when done directly on the plaintext: First, when encrypting a plain-text block as it is, with no random (or otherwise variable) padding, you are actually performing encryption in an ECB mode. The ECB (and other) modes of operation are known in block-cipher contexts, but the problems related to using ECB are reflected well when you perform simple block-by-block encryption using an asymmetric cipher as well. Of course, RSA uses block sizes that are much larger than the "regular" 64-bit or 128-bit block sizes, so code-book attacks are much harder to mount in comparison to code-book attacks on DES-ECB, but are still possible. So, simple block-by-block encryption using RSA (or any other asymmetric cipher), leads to the same vulnerabilities that are caused by simple block-by-block encryption with DES or other block ciphers, especially when it comes to code-book attacks. Second, there is a big inherent quality of all asymmetric ciphers which is that encryption can be simulated (by an opponent). Here is a brief explanation: When using symmetric encryption, an opponent who does not have the key cannot simulate neither correct decryption nor correct encryption, which means that he has no way (assuming the cryptographic algorithm is strong) to guess the plain-text unless he can guess the key. The only possible avenue of attack is therefore by brute-forcing the key. With "simple" asymmetric encryption, however, the encryption process can be simulated (repeated) by the opponent, hence he can obtain knowledge of the plaintext either by brute-forcing the key or by brute-forcing the plaintext, which might often be easier to do (for example, if the plaintext is one of known choices, or can otherwise be guessed). So, if you encrypt plaintext that may be guessed easily, the attacker can simply mount a brute-force attack on the plaintext to find what it is. Again, please note that these two are true not just for RSA, but for any other asymmetric cipher if implemented without salting (or otherwise wisely manipulating) the plaintext. Hope this helps. Regards, Hagai. Hagai Bar-El - Information Security Analyst Tel.: 972-8-9354152 Fax.: 972-8-9354152 E-mail: [EMAIL PROTECTED] Web: www.hbarel.com - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]