There's a new preprint on the IACR ePrint server (http://eprint.iacr.org/2012/094) by Jintai Ding and Peter Schmidt that presents an attack on NTRU that uses “additional information”. The abstract claims “In the case of the NTRU cryptosystem, if we assume the additional information on the modular operations, we can break the NTRU cryptosystems completely by getting the secret key.” Is NTRU broken?
Well, no.
The paper investigates the relationship f*h = p*g mod q, where f and g are small polynomials, h is an arbitrary mod q polynomial, and p and q areintegers. It starts by rewriting the equation as
f*h = p*g + q*G.
The statement is then that if G is known, f and g can be found using a new algorithm over the reals.
So, a few observations about this. First, two reasons why the attack isn't a break. Then, two observations about interesting points arising from the paper. Finally, a note about presentation.
First, the assumption that an attacker knows G is very strong (which means that it's very unlikely to be true). A straightforward implementation of NTRU key generation doesn't leak G; in fact, the precise quantity G isn't even calculated during normal key generation. There's no particular reason to think that an implementation would leak G as a result of a side-channel or fault attack any more than it would leak f or g directly. As the paper itself shows, G has a wider range of coefficients than do f and g, and so it is harder to guess G than it is to guess f or g directly. So this is clearly not a threat to a correctly implemented version of NTRU.
Second, there are other ways to obtain f and g, given G, than the algorithm in the paper. For example, if everything but f and g are known, then f*h - p*g = q*G gives N equations in 2N variables (the coefficients of f and g). However, since this equation is also an equation about polynomials, an attacker can calculate [f*h - p*g](x) = [q*G](x) at more than 2N different values of x. This gives > 2N equations that are linear in their 2N variables, allowing f and g to be recovered trivially.
Third, note that although G as defined above is unlikely to leak because it would only be used during keygen and, in fact, would not be used by natural implementations of keygen, there are other examples of NTRU operations for which the attack might be more realistic. For example, in encryption the quantity e = r*h + m mod q is calculated. If r*h is calculated one coefficient at a time, and if reduction mod q is noticeably slower than not reducing mod q, an attacker might be able to count the reductions mod q on the individual coefficients and so recover r*h + m over the integers, from which recovering m should be straightforward. Likewise, on decryption, the quantity m = (f*e mod q) mod p is calculated. If the attacker knows m (which is possible with a known-plaintext attack) and can count the reductions on decryption, they could potentially recover f. With current NTRU parameter sets, this is unlikely to happen: q is a power of 2, so reduction mod q is fast, and q is 2^11 so the natural time to reduce is when coefficients reach 2^16 or 2^32; in the first case, the attacker will get a very small amount of information, and the second case will never happen with current NTRU parameter sets.
Fourth, the paper points in an interesting direction for new research by suggesting that it would be interesting to investigate how many coefficients of G need to be known in order for the attack to work.
One way to look at this is to consider substituting for x (as in the second point above) and brute-force searching the unknown coefficients. The paper suggests that the coefficients of G are normally distributed with a standard deviation of about 5.3. In that case, the entropy of each coefficient is about 2.13 bits, and so for k-bit security, about (N - k/2) coefficients of G need to be known for the attack to be better than known attacks. This is clearly an upper bound and it's possible that a more sophisticated attack would allow more unknown coefficients of G. Note here that the attack in the paper was carried out on N = 167, and the higher values of N for recommended NTRU parameter sets would increase the width of the distribution of the coefficients of G somewhat (as well as increasing the absolute number of coefficients that must be known).
It's also interesting to generalize. The work of this paper clarifies why the reduction mod q is important. Can similar work be done about the reduction mod X^N-1?
Finally, to make a quick comment about presentation: it's unfortunate that the abstract of the paper simply says "In the case of the NTRU cryptosystem, if we assume the additional information on the modular operations, we can break the NTRU cryptosystems completely by getting the secret key." This presentation is a bit misleading on its own, as it implies that NTRU is broken. As this post should make clear, NTRU is not broken. It's better not to overclaim in papers.
