|
|
|
|
|
|
|
|
|
|
  General
Countermeasures
Standards and Technology
Bibliography General What is NTRU announcing? Is there an attack? What types of communications are affected? What can an attacker gain? Countermeasures As a current NTRUEncrypt user, how can I protect myself from this attack? Going forward, how can I develop software that is not vulnerable? Will the EESS#1 standard be modified to protect against this attack? What about other standards? Other standards that use or specify NTRUEncrypt, such as the forthcoming ANSI X9.98 and IEEE P1363.1, will be amended to specify the new padding schemes and parameter sets.How will NTRU products prevent this problem? The next versions of Neo and jNeo, available now, have no vulnerability to this attack.Standards and Technology What is EESS#1? EESS#1 [EESS1v2] is the Efficient Embedded Security Standard #1, issued by the Consortium for Efficient Embedded Security (CEES). It provides standard specifications for NTRUEncrypt and NTRUSign.What are SVES-1, SVES-2 and SVES-3? SVES-1 is the name of the padding scheme described in EESS#1 draft versions 1-4, and included in Neo up to version 7.0 and jNeo up to version 3.5. It is the padding scheme shown by Nguyen and Pointcheval at Crypto 2002 [NP02] to have insufficient provable security against chosen plaintext attack. SVES-2 is the padding scheme described in EESS#1 draft 5 and version 1, which would have provable security if there were no decryption failures. SVES-3 is the name of the new padding scheme, proposed in the papers published today and standardized in version 2 of EESS#1 [EESS1v2].What is a chosen ciphertext attack? What is a reaction attack? Keys for cryptographic systems can be attacked by various methods. In a chosen plaintext attack, an attacker can choose messages and see their encryption. Chosen plaintext attacks are always possible against public-key cryptosystems, because anyone can encrypt a message given the public key. In a chosen ciphertext attack, an attacker can choose different ciphertexts, submit them for decryption, and see the results. In a reaction attack, an attacker can choose different ciphertexts, submit them for decryption, and obtain some but not all information about the result of the decryption (for example, whether or not decryption succeeded). A standard tactic in constructing modern cryptosystems is to ensure that a ciphertext will only decrypt correctly if it was obtained by the valid process of encrypting a plaintext. This prevents an attacker from gaining information by altering existing ciphertexts.What is padding? In a public key cryptosystem, before a message is encrypted it is typically mixed with some random data. This ensures, at the least, that the same message will not encrypt twice to the same ciphertext, so an attacker who guesses the message cannot confirm the guess by comparing the encryption of their guess to the ciphertext. This process is called padding, or message preprocessing. On decryption, the padded message must be unpadded so the actual message can be retrieved. The padding process must therefore be reversible. More sophisticated padding schemes can give systems with provable security (see below).What is a proof of security? Public-key cryptosystems are based on underlying hard problems, but it is not necessarily the case that an attacker has to break the hard problem to break the cryptosystem itself. For example, if RSA is used without padding, there are trivial attacks that recover encrypted messages without recovering the factorization of the modulus. Modern practice is to design padding schemes with the property that breaking the system can be proved to be as hard as breaking the underlying hard problem. The approach is to show that any algorithm that can break the system can be converted straightforwardly into an attack that breaks the hard problem. Not all encryption schemes have the property of provability, and there are many subtleties to constructing an appropriate scheme.What is a decryption failure? Previous parameter sets for NTRUEncrypt had the property that it was theoretically possible for a validly encrypted message not to decrypt. This is known as a decryption failure. Depending on the parameters used, the chance of a decryption failure can vary greatly. With the current parameter sets the chance of a decryption failure is negligible.Why do decryption failures affect proofs of security? One purpose of a proof of security is to show that even if an attacker can see the decryption of any ciphertext they choose (except a specific target ciphertext), this does not help them decrypt the target ciphertext. We do this by requiring that the decryption process outputs "invalid" unless the ciphertext was formed by validly encrypting a message, and otherwise outputs the message. If the ciphertext is a valid encryption, the attacker already knows the message; if it's not a valid encryption, the attacker already knows that (because they formed the ciphertext without performing a valid encryption); therefore, the attacker learns nothing from observing decryptions. However, when decryption failures occur, something happens that the attacker didn't already know was going to happen. Therefore, it is no longer possible to prove that the attacker obtains no information from observing decryptions. Proofs of security are only possible if the chance of a decryption failure is negligible.Why is it necessary to change parameters? The parameter sets given in [EESS1v1] for N=251 have decryption failure probabilities of around 2-25. This allows attacks to be mounted that recover the private key with on the order of a million ciphertexts. It is necessary to lower the decryption failure probability to 2-80 in order to claim 280 security. The new parameter sets presented in [EESS1v2] give this level of security. In fact, the chance of a decryption failure is considerably less than 2-80; our analysis, presented in [SW03], shows it to be about 2-100.What changes have been made? We have made the following changes for our main parameters(N = 251, equivalent to RSA-1024 or 80-bit symmetric security):
Is there a proof of security now? Yes. With appropriate parameter sets and padding schemes, the change of decryption failures is sufficiently low that proofs are meaningful. The padding scheme in [HSSW03], posted today on the NTRU website, provides provable security even if there is a certain, low, probability of decryption failures. This is the first complete proof of security for NTRU, or any scheme with decryption failures. It constitutes a significant contribution to the understanding of the properties of this scheme.Where can I learn more technical details? The new N=251 parameter sets, with arguments to support the claimed level of decryption failures, are presented in [EESS1v2], available from the CEES website. The following papers are the major technical articles on the changes in the parameter sets. N. Howgrave-Graham, J. Silverman, A. Singer, W. Whyte, NAEP: Provable security in the presence of decryption failures. Available from http://www.ntru.com/cryptolab/articles.htm#006. The paper presents a padding scheme appropriate for cryptosystems with a non-zero but negligible average-case chance of decryption failure. It explains the application of this padding scheme to NTRUEncrypt and gives a proof of security. This is the first full proof of security for NTRUEncrypt, demonstrating that the problem of breaking NTRUEncrypt reduces to the problem of finding a close vector in a specific lattice. N. Howgrave-Graham, J.H. Silverman, W. Whyte, A meet-in-the-middle attack on an NTRU private key, NTRU Technical Report 004, version 2, 2003. Available from http://www.ntru.com/cryptolab/tech_notes.htm#004. This note describes a technique, originally due to Odlyzko, for trading off memory for time in searching for an NTRUEncrypt private key by a brute-force method. It demonstrates that for recommended parameter sets with N=251 the strength against meet-in-the-middle attacks is at least 280. J. Hoffstein, J. Silverman, W. Whyte, NTRU Technical Report #12, v2, Estimating Breaking Times for NTRU Lattices. Available from http://www.ntru.com/cryptolab/tech_notes.htm#012. The paper discusses the best known lattice-based attacks on NTRU cryptosystems, and demonstrates that for recommended parameter sets with N=251 the strength against lattice attacks is at least 280. J. Silverman, W. Whyte, NTRU Technical Report #18, Estimating Decryption Failure Probabilities for NTRUEncrypt. Available from http://www.ntru.com/cryptolab/tech_notes.htm#018. The paper discusses how to analyze the probability of an NTRUEncrypt decryption failure, and demonstrates that there are parameter sets which reduce the probability of a decryption failure to less than 2-80 for N=251. N. Howgrave-Graham, P. Nguyen, D. Pointcheval, J. Proos, J. Silverman, A. Singer, W. Whyte, The Impact of Decryption Failures on the Security of NTRU Encryption. Available from http://www.ntru.com/cryptolab/articles.htm#005. Proc. Crypto 2003, to appear. The paper describes an attack on NTRU as described in EESS#1 with the SVES-1 or SVES-2 padding scheme. The attack uses decryption failures to recover the private key with about 240 queries to a decryption oracle. It illustrates the importance of choosing parameter sets such that the chance of decryption failures is negligible.Bibliography view bibliography [EESS1v1] Consortium for Efficient Embedded Security, Efficient Embedded Security Standard #1, Version 1, November 2002. [EESS1v2] Consortium for Efficient Embedded Security, Efficient Embedded Security Standard #1, Version 2, May 2003. Available from http://www.ceesstandards.org. [HN+03] N. Howgrave-Graham, P. Nguyen, D. Pointcheval, J. Proos, J. H. Silverman, A. Singer, W. Whyte, The Impact of Decryption Failures on the Security of NTRU Encryption, available from http://www.ntru.com/cryptolab/articles.htm#005. [HSSW03] N. Howgrave-Graham, J. Silverman, A. Singer, W. Whyte, NAEP: Provable security in the presence of decryption failures, available from http://www.ntru.com/cryptolab/articles.htm#006. [MR03] T. Meskanen, A. Renvall, A Wrap Error Attack Against NTRUEncrypt, University of Turku Technical Report TUCS 507, available from http://www.tucs.fi/Research/Series/techreports/techrep.php?year=2003. [NP02] P. Nguyen, D. Pointcheval, Analysis and Improvements of NTRU Encryption Paddings, available from http://www.di.ens.fr/~pointche/pub.php?reference=NgPo02. [Pro03] J. Proos, Imperfect Decryption and an Attack on the NTRU Encryption Scheme, available from http://eprint.iacr.org/2003/002/. [Tech4] N. Howgrave-Graham, J. Silverman, W. Whyte, NTRU Cryptosystems Technical Report 4, v2: A Meet-In-The-Middle Attack on an NTRU Private Key. Available from http://www.ntru.com/cryptolab/tech_notes.htm#004. [Tech12] J. Hoffstein, J. Silverman, W. Whyte, NTRU Cryptosystems Technical Report 12, v2: Estimated Breaking Times for NTRU Lattices. Available from http://www.ntru.com/cryptolab/tech_notes.htm#012. [Tech18] J. Silverman, W. Whyte, NTRU Cryptosystems Technical Report 18: Estimating Decryption Failure Probabilities for NTRUEncrypt. Available from http://www.ntru.com/cryptolab/tech_notes.htm#018.
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||
|
|
| Copyright © NTRU Cryptosystems, Inc. 1998-2008 35 Nagog Park, Acton, MA 01720, USA Tel. 978-844-5200 |
Created by PixelMEDIA |
|
|
