4
$\begingroup$

The pre-print, Unstructured Inversions of NewHope was posted yesterday and uses a backdoor method against NTRU to claim that Grover's algorithm and an inversion oracle could be applied to NewHope.

My question is whether the backdoor from the Unstructured Inversions article could actually be used against NTRU? I'm not interested about the impact it may or may not have against NewHope, just forms of NTRU.

$\endgroup$
8
$\begingroup$

My name is Zhenfei Zhang. I work for Security Innovation Inc., which acquired NTRU Inc. in 2010.

The R-LWE based key exchange [1] uses a public matrix $a$ which may be manipulated. For instance, if $a$ is an NTRU style public key, i.e., $a = g/f$ where $g$ and $f$ are short, then one can break the system by recovering $f$. In particular, the cited paper suggested that one can use Grover to accelerate the search for $f$.

This is a known issue to the community for a while. The NewHope paper [2] addresses this by having $a$ to be an output of a hash function at the run time of the client. So under reasonable assumptions, no one is able to manipulate the public matrix $a$.

Will this affect NTRU? The answer is NO, if NTRU is used correctly.

NTRU uses structured public key $a$ to enable efficient computation. Hence it has a trapdoor by design. So if NTRU is used in a Diffie-Hellman type key exchange, where $a$ is generated by a (trusted) third party, then yes it may be vulnerable to this threat.

However, the correct use of NTRU, in a key exchange protocol, is to instantiate it via a key encapsulation mechanism (KEM), such as [3] [4]. In those cases, the client generates the public key (as the public parameter $a$ in R-LWE based schemes). And only the client knows the trapdoor. In this case the attacker need to run the Grover's algorithm to find the trapdoor. This is as hard as using Grover's algorithm to break NTRU. The parameter sets proposed in [5] ensures that this attack is impossible.

Thank you for your response. Are you referring to the hybrid attack from [5] in the context of the parameters from section 8 in [5]?

Yes.

I also see that you do specifically address concerns related to f(1)≠0mod2 Thank you, again.

It is not just the $f(1) \neq 0 mod 2" part. In [5] the algorithm is a CCA-2 secure encryption algorithm, which rules out the inversion oracle [6] required by the "Unstructured Inversion" paper.

It also looks like the Unstructured Inversion pre-print is focused more on the approximate x-coordinates rather than modifying the public matrix a.

The "Unstructured Inversion" paper is not in enough details, so the following are my guesses, and may be incorrect. Overall, imho the paper relies on several very strong assumptions.

  1. there exist a trapdoor in (R-)LWE public key $a$, which is not known by the attacker.

    This is a rare situation, as either the attacker inserted the trapdoor (as in attacks against [1]), in which case he already know the trapdoor and hence do not need to perform this attack; or $a$ is generated truthfully by the client (as in the solution in [2]), thus there does not exist a trapdoor. It is a strange case where someone (but not the attacker) generates $a$ with trapdoor but the attacker does not know it. If the client follows the protocol correctly this shall never happen.

  2. the existence of an inversion oracle.

    The inversion oracle is a stronger oracle than a decryption oracle used in CCA definitions. In addition, in both newhope style and NTRU-KEM style key exchange, the public parameter/key is used only once. It is very unlikely such oracle exists for ephemeral keys. In other words, if there exist such an oracle that works on ephemeral keys, there may be much stronger attacks than the one described in the paper.

[1] https://eprint.iacr.org/2014/599

[2] https://eprint.iacr.org/2015/1092

[3] https://eprint.iacr.org/2015/287

[4] https://tools.ietf.org/html/draft-whyte-qsh-tls12-02

[5] https://eprint.iacr.org/2015/708

[6] http://cseweb.ucsd.edu/~pmol/Publications/Recovering%20NTRU%20Secret%20Key%20From%20Inversion%20Oracles.pdf

$\endgroup$
  • $\begingroup$ Thank you for your response. Are you referring to the hybrid attack from [5] in the context of the parameters from section 8 in [5]? I also see that you do specifically address concerns related to $f(1)\ne 0 \mod2$ Thank you, again. $\endgroup$ – nonce Aug 20 '16 at 16:50
  • $\begingroup$ It also looks like the Unstructured Inversion pre-print is focused more on the approximate x-coordinates rather than modifying the public matrix $a$. $\endgroup$ – nonce Aug 21 '16 at 20:14
  • $\begingroup$ comments went too long so I put them in the main answer. $\endgroup$ – zhenfei zhang Aug 22 '16 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.