On 08/31/2010 09:07 AM, Justin Ferguson wrote: > Hi, > Hi Justin, > I'm not really much of a crypto guy so when the details come up it's often > kind of hard for me to entirely wrap my head around. That said, I'm currently > dealing with a situation where the public key, plain-text and cipher-text are > all known to an attacker; furthermore, the random oracles/et cetera employed > during the OEAP scheme are also known to the attacker. this is a very, very common situation (knowing the public key and the actual encryption scheme [with parameters] used): Since you know the public key & scheme and can choose arbitrary plaintexts, you can also produce corresponding ciphertexts for them... > Furthermore, the attacker can modify those > values (id est random oracle values of zero, or whatever the attacker > wants) and repeat the plain-text to cipher-text process as they see > fit. This is called a adaptive chosen-text scenario in cryptographer's circles. > Furthermore, the key length exceeds the length of the message. Basically, > only the private key is not under the attackers control. > OK. That's good for the defender :) > From that, what I am getting is that this is virtually the same as RSA > without the padding scheme and should be vulnerable due to it being a > deterministic algorithm; The padding scheme is crucial! This is what provides the security over other RSA variants; also, n.b.: the OAEP padding is randomized. > however my question is how much does it really reduce the complexity? Is an > attack against this even feasible in any practical terms? > The proof is in the pudding, errr... padding here. For RSA-OAEP Fujisaki et al. proved that OAEP provides semantic security against adaptive chosen-text attacks in a CRYPTO 2001 paper for which you can find the extended version (published in the Journal of Cryptology) here:
http://www.di.ens.fr/~pointche/Documents/Papers/2004_joc.pdf <http://www.di.ens.fr/%7Epointche/Documents/Papers/2004_joc.pdf> Finally, please be aware that proofs need not necessarily be correct, as has been demonstrated by an earlier attempt to prove OAEP secure [0,1] which was later found to be flawed by Shoup [2]. Hope to have helped, RPW [0] S. Goldwasser and S. Micali: Probabilistic Encryption. Journal of Computer and System Sciences, 28:270-299, 1984 [1] C. Racko and D. R. Simon: Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack. In CRYPTO 1991, LNCS 576, pages 433-44, Springer-Verlag, Berlin, 1992 [2] V. Shoup. OAEP Reconsidered. In CRYPTO 2001, LNCS 2139, pages 239-259. Springer-Verlag, Berlin _______________________________________________ cryptography mailing list [email protected] http://lists.randombit.net/mailman/listinfo/cryptography
