Analysis of NTRU+
이주희 (융합보안공학과)
Dear all,
We would like to announce an analysis on NTRU+, one of three lattice-based KEMs proposed in the 1st round of KpqC competition. NTRU+ is based on the NTRU and the LWE assumption (LWE with binary secrets and ternary errors).
In NTRU+, they propose a new message encoding technique, SOTP (Semi-generalized One-Time Pad), which takes n-bit input (m) together with 2n-bit input (u), and outputs an n-dimensional ternary vector (M). It is defined by M:=SOTP(m,u=(u_1, u_2))=(m \oplus u_1) – u_2. In addition, a decoding algorithm called Inv is provided that inputs an n-dimensional ternary vector (M) with 2n-bit (u) and outputs n-bit (m), and is defined by m:=Inv(M, u=(u_1, u_2))=(M+u_2) \oplus u_1.
In the Inv algorithm, we observed that if the input ternary vector (M) is maliciously formed, it may be the case that the output is not a binary n-bit bit string. We also checked that, in the implementation, after they compute (M+u_2) \oplus u_1, they *enforce* the output to be a binary bit string (by putting &0x1 operation at the end, see the line 313, 337 in poly.c of the NTRU+ implementation). Shortly, the idea is to exploit this observation and construct a malicious ternary vector M’ (\neq M) from M (a legitimate output of SOTP function) satisfying that the decoding of M’, Inv(M’, u), is equal to m=Inv(M,u). This breaks the rigidity of SOTP, since SOTP(Inv(M’,u), u) is again M.
The attack strategy for the CCA-NTRU+ is summarized as follows. In the IND-CCA game, upon receiving the challenge ciphertext c*, an attacker can add a constant (e.g., 2) to the first component of the challenge ciphertext, and ask the decryption oracle to decrypt c’=c*+(2,0,\cdots,0). Then, the decryption oracle produces a decryption result which equals to the decryption of the challenge ciphertext with probability 1/4, and aborts with probability 3/4. If the decryption oracle aborts, then the attacker does the same for the second component of the challenge ciphertext, and repeat it for the next component until she achieves the secret key corresponding to c* as an answer (the attack succeeds in the 4-th trial in average). In the attached summary, we demonstrate the attack idea for small n (since it works regardless how large n is) and how to win the IND-CCA game.
To defend the attack, we recommend to add a verification process in the Inv algorithm to check if the output (or the intermediate value M+u_2) is binary and abort otherwise.
Best regards,
Joohee Lee.
김종현
Thank you for interest on NTRU+.
We have carefully examined the attack scenario proposed by Joohee Lee and determined that it does not apply to NTRU+.
First, we emphasize that our instantiation of SOTP provides the rigidity property.
Let us recall the definition of rigidity for SOTP:
Rigid: For all u ∈ U and `all y ∈ Y encoded with respect to u', it holds that SOTP(Inv(y, u), u) = y.
Given that y ∈ Y is `encoded with u = (u1, u2)', by the definition, there exists an m such that y = SOTP(m,u) = (m xor u1) - u2 for some m.
We can verify that Inv(y, u) = (y + u2) xor u1 = (((m xor u1) - u2) + u2) xor u1 = (m xor u1) xor u1 = m.
Thus, SOTP(Inv(y, u), u) = SOTP(m, u) = y.
Therefore, our instantiation of SOTP satisfies rigidity.
Secondly, regarding the described attack,
the attacker attempts to exploit the fact that there exists an M' such that Inv(M',G(r)) = Inv(M,G(r)) = m, for M = SOTP(m,G(r)).
Consider the challenge ciphertext c* = hr* + M* with M* = (`-1', 0, 1, ...).
Then, the attacker modifies the message part to c* + (2,0,\cdots,0)= hr* + M* + (2,0,\cdots,0).
As a result, during the decapsulation process, the attacker hopes that the decrypted message of GenNTRU as M' = (`1', 0, 1, ...).
`If the decapsulation algorithm can recover r*, the attack mentioned above would work. However, unfortunately, as long as M' is distinct from M*,
the randomness obtained during the decryption will be unequal to r*.
This is because (1) M' \neq M*, (2) the randomness r' (obtained from (c*- M') h^{-1}) is distinct from r*, and thus G(r') \neq G(r*) with probability (almost) 1,
(4) m' (obtained from Inv(M', G(r')) is distinct from m*, and (5) finally this equality leads to the fact that r' (from (c*- M') h^{-1})) is distinct from (r'', K'') from H(m').
Thus, such a modification results in "invalid ciphertex", that is, \perp.
This means that the attacker is unable to create a case where the equality that Inv(M',G(r)) = Inv(M,G(r)) = m holds.
Best regards,
NTRU+ TEAM.
이주희 (융합보안공학과)
--
You received this message because you are subscribed to the Google Groups "KpqC-bulletin" group.
To unsubscribe from this group and stop receiving emails from it, send an email to kpqc-bulleti...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/kpqc-bulletin/85046215-f7fc-467b-97f5-23abaeae2ae0n%40googlegroups.com.
김종현
Thank you for your kind response. We acknowledge that the attack you described is indeed effective.
In our initial response, we overlooked the fact that the attacker made a decryption query for c' = c* + (2, ,,, , 0) instead of c*.
As you mentioned, this attack exploits an implementation aspect, rather than being a theoretical issue at this point.
It can be resolved by checking whether the `(y + u2)' term in Inv(y, u) = ((y + u2) xor u1) consists only of 0 or 1.
We will carefully consider efficient and secure methods for conducting such checks and will distribute the modified implementation accordingly.
We appreciate your clear analysis of this issue, which was a concern for us when submitting NTRU+ to KpqC Competition.
Once again, thank you for your valuable comments.
Best regards,
NTRU+ TEAM.
이주희 (융합보안공학과)
To view this discussion on the web visit https://groups.google.com/d/msgid/kpqc-bulletin/feeb30dc-21f0-4f7d-b4a5-fd7786083faen%40googlegroups.com.