Inversions of New Hope

[Ian M]

Hello Everyone,

After speaking with the engineers of New Hope today, my colleague and I attempted to further the attacks outlined in the pre-print, "Unstructured Inversions of New Hope."  Rather than continuing the focus on hybrid attacks though, we've attempted to analyze New Hope in strictly classical terms.  Since my co-author and I are keeping a majority of the earlier pre-print, we've mostly added to Section 4 and changed the title to "Inversions of New Hope."

I expect there are errors within this attempt, and have already shared the draft with the authors of New Hope for their review.  While the conclusion of this new draft was reworded to affirm the results, I want to make clear that at this point the work in this new draft is being treated as unverified at this point.  Thus, my colleague and I are sharing this as a progress report rather than conclusive in its findings.

I appreciate any and all feedback.

v/r,

Ian

[Alperin-Sheriff, Jacob (Fed)]

I am very confused; a is explicitly NOT fixed by New Hope, precisely to avoid backdooring problems.

--
You received this message because you are subscribed to the Google Groups "Cryptanalytic algorithms" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cryptanalytic-algo...@googlegroups.com.
To post to this group, send email to cryptanalyti...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cryptanalytic-algorithms/bea2d7d5-7734-49b2-91b2-5a2442ac82ce%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[I M]

Jacob,

Yes, we are not treating (a) as a fixed value in this paper.

Ian

On Tue, Feb 14, 2017 at 1:06 PM, Alperin-Sheriff, Jacob (Fed) <jacob.alpe...@nist.gov> wrote:

I am very confused; a is explicitly NOT fixed by New Hope, precisely to avoid backdooring problems.

 

 

From: <cryptanalytic-algorithms@googlegroups.com> on behalf of Ian M <iama...@utica.edu>
Date: Monday, February 13, 2017 at 7:46 PM
To: Cryptanalytic algorithms <cryptanalytic-algorithms@googlegroups.com>
Subject: Inversions of New Hope

 

Hello Everyone,

 

After speaking with the engineers of New Hope today, my colleague and I attempted to further the attacks outlined in the pre-print, "Unstructured Inversions of New Hope."  Rather than continuing the focus on hybrid attacks though, we've attempted to analyze New Hope in strictly classical terms.  Since my co-author and I are keeping a majority of the earlier pre-print, we've mostly added to Section 4 and changed the title to "Inversions of New Hope."

 

I expect there are errors within this attempt, and have already shared the draft with the authors of New Hope for their review.  While the conclusion of this new draft was reworded to affirm the results, I want to make clear that at this point the work in this new draft is being treated as unverified at this point.  Thus, my colleague and I are sharing this as a progress report rather than conclusive in its findings.

 

I appreciate any and all feedback.

 

v/r,

Ian

--
You received this message because you are subscribed to the Google Groups "Cryptanalytic algorithms" group.

To unsubscribe from this group and stop receiving emails from it, send an email to cryptanalytic-algorithms+unsub...@googlegroups.com.
To post to this group, send email to cryptanalytic-algorithms@googlegroups.com.

[Ian M]

Jacob,

 

I think your confusion is coming from the first sentence in Section 2.  I had to reword this sentence compared to the hybrid attack pre-print, and obviously rewrote it poorly.

Was this the sentence that caused your concern?

Ian

[Ian M]

Hello everyone,

I'm going to try to clear up some confusion about this paper.

Our work is based on Mol and Yung who use an inversion oracle to return NTRU keys.  Mol and Yung leave the inversion oracle as a black box in their work, while my colleague and I instead outline the internal computation of the oracle algebraically.  My colleague and I are fully aware that there are no fixed values, though the creators of New Hope have corrected us in this respect by saying (n) and (q) are fixed.

Our attack focuses specifically on the mathematical structure of New Hope as intersecting Voronoi cells in their lattice.  From analyzing the algebraic manipulations regarding the secret (s), and the reconciliation function, we show that the requirements of Mol and Yung for an inversion to be successful are satisfied.  This occurs specifically for s(1) congruent to 0 mod q.  Our final equation of s(1) = 0 mod q = 0 mod 2, as demonstrated, places a point (x_i) at the center of the 24-cell tessellation.  By showing there does exist a point x_i such that x = s, and s(1) is congruent to 0 mod q, the inversion is verified.  The steps leading to this result are based on the outline of a backdoor provided by the authors of New Hope, in their characterization of one based on the trapdoor function of NTRU.

To finalize the backdoor attempt, we use an anti-derivative which allows us to manipulate (s,e) using an introduced fixed constant.  It is our understanding that should any attacker gain knowledge of (s,e), then the session can be simulated.

I hope this clarifies our goals, and refines the context of this research.

-Ian

[Ian M]

Reflecting the feedback I've received today, I attempted to make both the attack model and claims more explicit.