NTRU Cryptosystems Technical Report

Report # 7, Version 1 Title: Plaintext Awareness and the NTRU PKCS Author: Joseph H. Silverman Release Date: July 3, 1998

Abstract. RSA and Bell Labs [2, 3] have recently announced a potential attack on certain public key protocols, along with several suggested countermeasures. The most secure of these countermeasures uses the concept of plaintext aware, which means that it should be infeasible to construct a valid ciphertext without knowing the corresponding plaintext. Failure to be plaintext aware may open a cryptosystem to various sorts of attacks. In this note we describe some potential attacks on the NTRU Public Key Cryptosystem (PKC) analogous to the attack described in [2, 3] and suggest the use of an OAEP digital envelope to eliminate the threat of such attacks.

A cryptosystem is said to be plaintext aware if it is infeasible for an attacker to construct a valid ciphertext without knowing the corresponding plaintext. (For a more precise definition of this concept, see [4].) Failure to be plaintext aware may open the door to various sorts of attacks, such as Bleichenbacher’s Adaptive Chosen Ciphertext Attack [2, 3] on RSA’s Public Key Cryptography Standard #1 (PKCS #1). In this note we will construct several attacks on the NTRU Public Key Cryptosystem, including an adaptive chosen ciphertext attack similar to [2].

A number of countermeasures to Bleichenbacher-type attacks are described in [3], including:

• Frequent changes of key pair.

• Check messages more rigorously for format after decryption.

• Require the sender to demonstrate knowledge of the data before indicating whether the decryption was successful.

• If a message is rejected for any reason, the timing and format of the error message sent back to the sender should be the same.

• Add structure to the data (e.g., by including a hash of the data) to decrease

the probability of a message being accepted. All of these sensible countermeasures apply to any public key cryptosystem, including NTRU, and many of them require few changes in currently implemented digital envelopes and protocols, such as RSA’s PKCS#1. With regard to the first countermeasure, we want to stress that an important feature of the NTRU PKC is the ease and speed of key creation. This makes NTRU the only current commercially viable public key cryptosystem which supports single use public/private key pairs; that is, public/private key pairs which are used for a single transaction or a single session and then discarded. For this reason alone, the NTRU PKC is to be preferred in many situations.

However, the most effective countermeasure to all of the attacks described in this note, and indeed to any attack which depends on counterfeiting valid ciphertexts, is the use of Optimal Asymmetric Encryption Padding (OAEP) [4]. This method of creating plaintext aware digital envelopes uses a mixing process in which every bit of the message affects and is affected by every bit of a pseudorandom component. It has been proposed by RSA that OAEP be adopted as a standard formatting scheme for public key algorithms, and RSA plans to include it as part of their PKCS#1 v2.^{†} We fully support this proposal. In Section 4 we will describe how OAEP may be implemented for the NTRU PKC.

Throughout this note we will use the notation and description of the NTRU PKC given in [1]. The contents of this note are as follows:

§1. An Adaptive Chosen Ciphertext Attack
§2. A Correlation Attack Via Induced Wrapping Failure
§3. A Multiple Transmission Attack
§4. Optimal Asymmetric Encryption Padding for the NTRU PKC

4.1. Specific Parameter Choices For Various Security Levels

§5. An Insecure Digital Envelope

§1. An Adaptive Chosen Ciphertext Attack Plaintext is generally placed into a digital envelope before being encrypted. This digital envelope might contain some random padding to prevent similarity between messages, and some features which allow identification of valid messages. For example, the RSA Public Key Cryptosystem Standard #1 v1.5 [3] uses the format

0 0 ∥ 0 2 ∥ PS ∥ 0 0 ∥ D,

where D is a data string (often a key) and PS is a pseudo-random padding string. Thus the first four bytes are 0002, and the padding string PS is separated from the data string D by two null bytes 00.

Bleichenbacher [2,3] has recently devised an adaptive chosen ciphertext attack on messages encrypted with the RSA PKC which use this, or any similar, digital envelope. In this section we will describe an attack on the NTRU PKC if messages are enclosed in an analogous digital envelope.

For simplicity, we will suppose that an NTRU plaintext block is formatted as

0 + 0 · X + 0 · X^{2} + 2 · X^{3} + P S(X) + 0 · X^{k} + 0 · X^{k+1} + D(X),

† “While attacks of this kind [adaptive chosen ciphertext] have not been shown to affect other algorithms [other than RSA], it is widely believed that OAEP could provide additional security to other public-key algorithms as an enveloping format. The cryptographic community is aware of the potential of adaptive chosen ciphertext attacks and is working to prevent them. For this reason, OAEP has been proposed as a formatting scheme for other public-key algorithms, such as elliptic curve cryptography.”

[5]

where P S(X) is a pseudo-random padding polynomial, and the polynomial D(X) contains the data. This is similar to RSA PKCS#1 v1.5. As in Bleichenbacher’s attack, we will further assume that a message is rejected if it does not have this form, and that an attacker is able to determine whether or not a message has been rejected.

Under these assumptions, an attacker takes an intercepted encrypted NTRU message e, chooses a random small polynomial ψ (i.e., with just a few coefficients equal to ±1, and the rest 0), transmits the message

E = ψ ∗ e (mod q),

and observes whether or not it is accepted as valid. When E is decrypted, the underlying plaintext message will be ψ ∗ m mod p, where m is the plaintext underlying e. Since a message is accepted if and only if six specific coefficients have specific values, the probability that E is accepted is p^{−6}. (For most implementations, p = 3.) Each time an E is accepted, the attacker gains 6 linear relations on the coefficients of the plaintext message m. Hence after some small multiple of p^{6} transmissions, the attacker will be able to recover most or all of m. Conclusion: It is inadvisable to accept or reject NTRU ciphertexts based solely on whether or not specific coefficients of the underlying plaintext have specific values. [However, for moderate security applications, it would be reasonable to accept/reject messages based on the value of K specific coefficients, especially if an attacker will not be allowed to send p^{K} encryptions.]

§2. A Correlation Attack Via Induced Wrapping Failure A properly chosen set of NTRU parameters, such as those described in [1, §4.1], make it highly unlikely that decryption will ever fail due to the coefficients of ϕ ∗ g + m ∗ f spanning an interval of width larger than q. If this were ever to happen, we say that wrapping failure has occurred. In this section we describe an attack on the NTRU PKC based on wrapping failure if the attacker is able to determine (e.g., by timing methods) whether or not wrapping failure has occurred.

The attacker takes an intercepted encrypted NTRU message e, chooses a random polynomial ψ with small coefficients (say randomly chosen from −1, 0, 1 with a distribution similar to that of ϕ), transmits the message

E = e + ψ ∗ h (mod q),

and observes whether or not it is rejected due to wrapping failure. When E is being decrypted, the first step is to compute

a ≡ f ∗ E ≡ p(ϕ + ψ) ∗ g + m ∗ f (mod q).

From this formula, we see that wrapping failure is much more likely if many of the 1 coefficients of ϕ match up with 1 coefficients of ψ, and similarly for the −1 coefficients. The attacker repeats this process a large number of times, and saves those values ψ_{1}, ψ_{2}, …, ψ_{ν} which give wrapping failure. Then the average

Ψ = \frac{1}{ν} ∑_{j=1}^{ν} ψ_{j}

will be quite highly correlated with ϕ. More precisely, suppose that ϕ has d coefficients equal to each of 1 and −1, with the rest 0. Then the attacker forms a polynomial Φ by replacing the d largest coefficients of Ψ with 1’s, the d smallest coefficients of Ψ with −1’s, and setting the other coefficients equal to 0. Then ϕ and Φ will bear a close resemblance to one another, and the attacker can do a brute force search centered at Φ, possibly using the additional information that the larger (smaller) the coefficient of Ψ, the more likely it is that the corresponding coefficient of Φ is correct. Further, the attacker can make the process even more efficient by choosing the sample ψ’s adaptively, based on which of the previous ψ’s caused wrapping failure.

Note that it is easy for the attacker to determine if she has found the correct ϕ, since only the correct element of L_{ϕ} will make the difference e − ϕ ∗ h mod q into an element of L_{m}. Finally, we remark that we have tested this method numerically and it works quite well, even in non-adaptive mode. For example, using the moderate security parameters in [1, §4.1], we found that 10,000 iterations produced several hundred wrapping failures, and from these we were generally able to correctly place at least 8 of the 10 non-zero coefficients of ϕ. Conclusion: Messages should not be accepted/rejected based solely on wrapping failure; and those messages which are rejected due to wrapping failure should return the same error message in the same amount of time as messages rejected because they are incorrectly formatted.

§3. A Multiple Transmission Attack If a single plaintext message is transmitted more than one time using the basic NTRU PKC scheme described in [1], then the message will be vulnerable to a multiple transmission attack. (Other PKC’s are also susceptible to such attacks, see for example [7].) We described such an attack in [6] and gave two simple solutions. Here we merely want to point out that the OAEP digital envelope described in the next section, and indeed any similar digital envelope with sufficient variability, will prevent such attacks. Conclusion: Identical or similar messages should not be directly encrypted without some variability being introduced.

§4. Optimal Asymmetric Encryption Padding for the NTRU PKC All of the attacks described in this note can be defeated by making the NTRU PKC plaintext aware, where recall that a cryptosystem is said to be plaintext aware if it is infeasible for an attacker to construct a valid ciphertext without knowing the corresponding plaintext. This can be done by constructing a digital envelope for the plaintext message which includes sufficient variability to preclude forging a valid new ciphertext, even if one starts with a valid (intercepted) ciphertext. An especially good type of digital envelope is one which has the optimal asymmetric encryption padding (OAEP) property. Roughly speaking, a digital envelope has OAEP if it has a random component (at a sufficiently high security level), if every bit of the random component affects every bit of the plaintext message, and if every bit of the plaintext message affects every bit of the random component. For precise definitions and details of these concepts, see [4].

The NTRU PKC is a probabilistic cryptosystem, that is, there is already a random component used for each encryption. This allows us to make some small modifications in the OAEP method described in [4].

Before describing a digital envelope for the NTRU PKC, we set some notation. We let

P_{p}(N) = {polynomials of degree at most N − 1 with mod p coefficients},

and we will write

[g]_{p} = \begin{cases}g with its coefficients reduced \\ modulo p into the range (-p/2,p/2]. \end{cases}

We will need the services of a “generating” function and a “hash function”

G : P_{p}(N) ⟶ P_{p}(N) and H : P_{p}(N) × P_{p}(N) ⟶ P_{p}(K).

These should be easy to compute, highly non-linear, and unpredictable. For example, an easy G to include in an NTRU PKC implementation is G(g) ≡ g^{2} (mod p). However, this G requires O(N^{2}) operations, so it is probably better to construct G and H out of primitive operations such as shifts. There are numerous examples of such functions in the literature.

The NTRU PKC digital envelope depends on the choice of the functions G and H, and on an integer K. The probability of forging a valid ciphertext is going to be p^{−K}.

Having made these choices, we now describe how Alice wraps and sends a message to Bob using Bob’s NTRU public key h. Alice chooses her plaintext m from the set

m ∈ P_{p}(N − K).

She also chooses a random polynomial ϕ ∈ L_{ϕ} as usual. She computes

e ≡ ϕ ∗ h + [m + H(m, [ϕ ∗ h]_{p})X^{N−K} + G([ϕ ∗ h]_{p})]_{p} (mod q).

Alice then sends e to Bob.

To decrypt the message, Bob first uses his private key f and the standard NTRU PKC decryption method [1, §1] to recover a polynomial

n = [F_{p} ∗ [f ∗ e]_{q}]_{p} ∈ P_{p}(N).

Next he computes

b ≡ e − n (mod p)  and  c ≡ n − G(b) (mod p),

and he writes c in the form

c = c′ + c′′X^{N−K} with deg(c′) < N − K and deg(c′′) < K.

(Note that the quantity b is supposed to play the role of [ϕ ∗ h]_{p}.) Finally, he compares the quantities

c′′  and  H(c′, b).  (2)

If they are the same, he accepts c′ as a valid decryption. Otherwise he rejects the message as invalid.

Note how difficult it will be for an attacker to forge a valid message without knowing the underlying plaintext, since every bit of the random component [ϕ ∗ h]_{p} affects every bit of the message m via the function G, and every bit of both m and the random component affect one another via the function H. Finally, we note that the probability of the comparison step (2) being true is p^{−K}, since this is the size of the image space for the hash function H.

Conclusion: Use of Optimal Asymmetric Encryption Padding methods or similar digital envelope methods improve the security of the NTRU Public Key Cryptosystem and eliminate a number of possible attacks, including adaptive chosen ciphertext attacks, multiple transmission attacks, and attacks via induced wrapping failure.

§4.1. Specific Parameter Choices For Various Security Levels Three sets of NTRU PKC parameters were proposed in [1, §4.1] which correspond to moderate, high, and highest security levels.^{‡} Table 1 gives the value of K needed to preserve the indicated message security in circumstances where an attacker is able to send large numbers of ciphertexts and discover which are accepted as valid. The ciphertext and plaintext lengths refer to the length of one block.

‡ We note that the security levels listed are for meet-in-the-middle attacks, which require a considerable amount of computer storage. For straight search brute force attacks, these security levels should be squared.

Moderate  High  Highest
Security  Security  Security
(N, p, q, d, K)  (107,3,64,5,17) (167,3,128,18,49) (503,3,256,55,107)
private key  340 bits  530 bits  1595 bits
public key  642 bits  1169 bits  4024 bits
ciphertext  642 bits  1169 bits  4024 bits
plaintext  143 bits  187 bits  628 bits
key security  2^{50}  2^{82.9}  2^{285}
message security  2^{26.5}  2^{77.5}  2^{170}

Table 1

§5. An Insecure Digital Envelope

In this section we show that even in its original formulation [1], an NTRU PKC message is automatically enclosed in a digital envelope, but we explain that use of this digital envelope as a means of message verification can lead to an easy attack on the message if the attacker is allowed to send a large number of messages and observe which ones are accepted as valid.

Briefly, Bob precomputes an inverse modulo q for the public key h, say,^{†}

H_{q} ∗ h ≡ 1 (mod q).

Then to test if an encrypted message e and its decryption m are valid, he computes

H_{q} ∗ (e − m) (mod q).  (1)

If e is a valid ciphertext for the plaintext m, then the polynomial (1) will have small coefficients, and in fact, will lie in the sample space L_{ϕ}, since it will actually equal the ϕ used to perform the encryption. For example, using the sample spaces described in [1, §2.2], e and m are accepted if and only if the polynomial (1) has d coefficients equal to 1, d coefficients equal to −1, and the rest equal to 0. Thus the probability of a randomly chosen e being accepted as a valid message is |L_{ϕ}|/q^{N}. Even using the moderate security parameters (N, p, q) = (107, 3, 64) and L_{ϕ} = L(5, 5) from [1], this probability is 2^{−589}.

† The specific implementation of the NTRU PKC described in [1, §2.2] yields public keys h which are not invertible, but this is easily remedied by taking a slightly different sample space for g.

However, this method of message verification opens the system to the following attack. The attacker takes an intercepted message e, chooses random values 0 ≤ j < k < N, and sends the message

E = e + h ∗ (X^{j} − X^{k}).

Notice that E ≡ (ϕ + X^{j} − X^{k}) ∗ h + m (mod q). If we write (ϕ_{j}, ϕ_{k}) for the pair consisting of the j^{th} and k^{th} coefficients of ϕ, then there are nine possibilities for this pair as detailed in Table 2.

ϕ_{j}  −1 −1 −1 0  0  0  1  1  1
ϕ_{k}  −1 0  1 −1 0  1 −1 0  1
ϕ + X^{j} − X^{k} ∈ L_{ϕ}? NO YES NO NO NO YES NO NO NO
Table 2. Is ϕ + (X^{j} − X^{k}) in L_{ϕ} = L(d, d)?

There is thus a 2/9 probability that e + h ∗ (X^{j} − X^{k}) will be accepted as a valid ciphertext. We will assume that the attacker is able to find out which ciphertexts are accepted. Then by varying (j, k), she will rapidly uncover which pairs (ϕ_{j}, ϕ_{k}) equal one of (−1, 0) or (0, 1), which allows her to reconstruct much or all of ϕ. Finally, she recovers the encrypted message via m ≡ e − ϕ ∗ h (mod q). Conclusion: One should not use the digital envelope which tests if the quantity H_{q} ∗ (e − m) mod q is in the sample space L_{ϕ}.

References

[1] NTRU: A Ring-Based Public Key Cryptosystem, presented at ANTS 3 (Reed College,Portland, Oregon, June 21–25, 1998), to appear in Lecture Notes in Computer Science, Springer-Verlag.

[2] D. Bleichenbacher, Chosen ciphertext attacks against protocols based on the RSA encryptoin standard PKCS#1, Advances in Cryptology — Crypto ’98, to appear

[3] D. Bleichenbacher, B. Kaliski, J. Staddon, Recent results on PKCS#1: RSA encryption standard, RSA Laboratories’ Bulletin, Number 7, June 26, 1998.

[4] M. Bellare, P. Rogaway, Optimal asymmetric encryption, in Advances in Cryptology — Eurocrypt ’94, A. de Santis (ed.), 92–111, Springer-Verlag, 1995.

[5] www.rsa.com/rsalabs/, RSA Laboritories, RSA Data Security, Inc.

[6] Jeffrey Hoffstein and Joseph H. Silverman, Implementation Notes for NTRU PKCS Multiple Transmissions, NTRU Cryptosystems Technical Report 006, May 26, 1998

[7] D. Coppersmith, M. Franklin, J. Patarin, M. Reiter, Low exponent RSA with related messages, in Advances in Cryptology — Eurocrypt ’96, U. Maurer (ed.), 1–9, Springer-Verlag, 1996.

Comments and questions concerning this technical report should be addressed to

                   techsupport@ntru.com

Additional information concerning NTRU Cryptosystems and the NTRU Public Key Cryptosystem are available at

                 www.tiac.net/users/ntru

NTRU is a trademark of NTRU Cryptosystems, Inc.

The NTRU Public Key Cryptosystem is patent pending.

The contents of this technical report are copyright July 3, 1998 by NTRU Cryptosystems, Inc.