Scott Fluhrer edited section_Abstract_This_paper_explores__.tex  almost 9 years ago

Commit id: 319547ebb0731aaa38a00c913770baec71fafbd7

deletions | additions      

       

This is quite similar to one of the key recovery attacks we have presented above (because both attacks work against the common logic used to generate both $F$ and $R$). However, there is a distinction in that the key generation procedure could be modified to use a stronger method to select $F$ (and $G$) without any interoperability issue. In contrast, we cannot modify how we generate $R$ without modifying how decryption is done (as the decryptor will expect to be able to regenerate $R$ as part of the post-decryption validation process. Covering this plaintext recovery attack would require modifying the NTRU padding method.  \section{Plaintext Recovery Attack 2}  Another way an attacker can attempt to recover the plaintext, if the plaintext is low entropy, is to notice that the ciphertext is a deterministic function of the plaintext, the public key, and the $k$-bit random value $b$. If the entropy of the plaintext is low (had (has  only $2^n$ possible values, for $n \lll k$), then what an attacker with a Quantum Computer could do is model the system as one with $2^{n+k}$ inputs (which consists of the $2^n$ possible inputs for the plaintext, paired with the $2^k$ possible values for $b$), and then apply Grover's algorithm to find a solution (that is, $m$ and $b$) that generates the known ciphertext in $O(2^{(n+k)/2})$ time, which is less than the security level $2^k$ (and if $n$ is sufficiently small, this value may be even smaller than the previous attack). Now, in practice, this attack would not generally appear to be a significant threat; in most cases, NTRUEncrypt will be used to pass symmetric keying data, and symmetric keying data has sufficiently high entropy to make this attack infeasible. However, in those cases where NTRUEncrypt is used to transmit low-entropy plaintexts or if the attacker might have a plausible guess for the plaintext (and it is important to make such verification infeasible), this attack is of concern.  \section{Conclusions and Recommendations}  We have presented two four  attacks where an adversary with a Quantum Computer is able to recover plaintexts. Neither attempt against NTRUEncrpyt (as implemented by the NTRU library). One  of these the key recovery  attacks actually attack attacks the key generation process that  the NTRU primitive itself; instead, they attack library uses; it would be easy to modify the library to foil this approach (for example, both to use stronger hash functions when generating  the NAEP padding method, hashed value $h$,  and take advantage of by extending  the fact that additional 64 bits to prevent someone using Grover's algorithm to guess  the internal primitives selected for preimage value). Because of  the parameter sets are scaled to withstand attacks by a classical computer, ease of this modification,  and are not sufficient if because  the attacker has modified library would continue to interoperate with existing NTRU implementations, we recommend that such  a Quantum Computer. change be made.  We have also presented another key recover attack that uses fewer operations than expected to recover the private key (assuming one of two parameter sets); however this attack is thoroughly impractical. We don't recommend any change to cover this attack.  Neither of the two plaintext recovery attacks actually attack the NTRU primitive itself; instead, they attack the NAEP padding method, and take advantage of the fact that the internal primitives selected for the parameter sets are scaled to withstand attacks by a classical computer, and are not sufficient if the attacker has a Quantum Computer.  These attacks may appear to have some potential impact. For example, in A 'A  quantum-safe circuit-extension handshake for Tor\cite{Schanck_2015}, Tor\cite{Schanck_2015}',  they suggest using the NTRUEncrypt parameter set EES439EP1 (a 128 bit parameter set) to protect Tor traffic; do these results mean that someone with a Quantum Computer could reconstruct the original sender of a message with $O(2^{80})$ work? There are three obvious ways to address the issues here. The first strategy would be to use a stronger parameter set; if your target is 128 bits security, use an NTRU parameter set targeted towards 256 bit security; such a parameter set would provide at least 128 bits security against all known attacks, even if the attacker has a Quantum Computer. The costs here are that the ciphertext and public key sizes increases, as well as a small increase in the encryption and decryption time.