In the same fashion that these questions about attacks to textbook RSA and ECC, I was wondering what are the immediate drawbacks of applying NTRU Encryption directly, without any padding scheme, such as NAEP or SVES.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Without a well-designed padding system it may be possible to craft a ciphertext that the decryptor may or may not be able to decrypt properly. Whether the decryptor is able to do so will depend on the private key. The concern is that an attacker may be able to craft a string of ciphertexts, listen in to whether they decrypt properly, and finally deduce the private key from the bits denoting the success/failures.
To review how raw NTRU encryption works: select a message $M$ (as a polynomial), select a random lightweight polynomial $R$ and then compute the ciphertext $C = RH + M$ (where $H$ is from the public key).
To decrypt it is required to compute the plaintext $P = CF$ (where $F$ is from the private key), computing everything $\bmod q$. Because of how $F$ and $H$ are related, this is $pRG + FM$; the next step is to evaluate this polynomial $\bmod p$; assuming that no wrap around (modulo $q$ has occurred). T his strips off the $pRG$ term, giving $FM \bmod p$; from that, it is possible to recover $M$. However, if some coefficient does wrap, then the decryptor will recover an incorrect value for $FM \bmod p$; this will give the wrong $M$.
So, what can cause a wrap? Well, wraps will occur if a coefficient of the polynomial $RG$ is too large. It is too large when it is outside the range $(-q/2, q/2)$ (not considering the implicit $\bmod q$ operation). $R$ is a value that the encryptor (who may be the attacker) selects, while $G$ is a value that can be used to calculate the private key from the public key. By artfully selecting $R$ values, an attacker could probe $G$ and - over time - recover it. Note that the $FM$ term can also contribute to the wrap; the attacker can account for this by selecting $M=0$.
There are guidelines on how an honest encryption should select $R$ values so that decryption failures don't leak information. An attacker will however ignore these guidelines. NAEP prevents the key recovery attack by making the polynomial $R$ a deterministic function of $M$ (and some random bits that are included in the message). So after the decryptor recovers $M$ (and those random bits) we can recompute what $R$ should have been. We can then compares it to the $R$ that was actually used. If they're different then that also results in a decryption failure. An attacker can therefore not use a value of $R$ that is outside the guidelines.
$\begingroup$
$\endgroup$
I am a cryptographic researcher at Security Innovation, which acquired NTRU.
Apart from the aforementioned attack, there are two significant attacks, namely a chosen plaintext attack (CPA) and a chosen ciphertext attack (CCA), when a proper padding scheme is not used.
Recall that in an IND-CPA game, the challenger is given two plaintexts, suppose they are $m1(x) = 0$, and $m2(x) = 1$; as well as a ciphertext $c$ that encrypts either $m1$ or $m2$. The adversary win the game if he can guess the which message was encrypted with a non-negligible advantage over $1/2$.
Recall that $c(x) = m(x) + r(x) H(x)$, where $r(x)$ is a ternary polynomial with balanced number of $1$s and $-1$s. In other words, $r(1) = 0$. So evaluating the ciphertext at $0$ gives $c(0) = m(0) + 0H(x) = m(0)$. This allows the attacker win the game as $m1(x)$ and $m2(x)$ have different values at $0$.
The chosen ciphertext attack (CCA) is less strong, but is also possible, if the padding is not present.
In a CCA attack, the adversary is given a challenge ciphertext $c(x)$. The adversary has access to a decryption oracle, which returns the messages for any ciphertexts other than the challenge $c(x)$. The adversary wins the game if he/she is able to recover the message.
In raw NTRUEncrypt, $c(x) = m(x) + r(x) H(x)$. Thus, the adversary can submit $c'(x) = c(x)+1$ to the oracle. Without padding (without plaintext awareness, to be exactly) $c'(x)$ will be a legitimate ciphertext. This allows the attacker to learn $m'(x) = m(x)+1$, and hence $m(x)$.
The padding will successfully stop those attacks. With padding, each $m(x)$ will have to meet certain criteria. In current version of NTRUEncrypt, in a nutshell, $m(x)$ is formed as $b|msg$, where $b$ is a random padding; and $r(x)$ is the output of $hash(m(x),H(x))$.
For the CPA security, as we have $m(x) = b|msg$, therefore, $m(0)$ becomes the first bit of the padding $b$, which does not leak any information on the actual message.
For the CCA security, the decryptor will have to check the validity of $r(x)$ before output the final result. This means $c'(x)$ will be an invalid ciphertext, thus stop the attack.
For more details of NTRUEncrypt, please see:
https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/doc/EESS1-v3.1.pdf
for the spec, and
https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/doc/NewParameters.pdf
for how parameters are derived.
