Meet-in-the-Middle Atack on an NTRU Private key

Question

I was wondering if anyone could tell me how to represent the enumeration of vectors of privite key f in a Meet-In-the-Middle Attack on an NTRU Private key. I can not understand the example, given here http://securityinnovation.com/cryptolab/pdf/NTRUTech004v2.pdf I'll be very thankful if anyone could show an example in detail.

Answer 1

(Full disclosure: I work for Security Innovation and worked for NTRU until SI acquired us)

Warning: Long answer!

Let's look at a toy example: N = 11, q = 29. Let's take df = 3, so f consists of 3 coefficients equal to 1 and 8 coefficients equal to 0. Take dg = 5. And assume that h = g*f^{-1} mod p, rather than using the optimizations that have f = 1+pF. Then we might have

f = [1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0]
finv = [16, 12, 4, 18, 17, 14, 9, 28, 8, 26, 3]
g = [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0]
h = [15, 20, 1, 21, 4, 26, 14, 17, 25, 11, 12]

You can check that f*h = g here.

The attacker wants to find f, so they can do the brute force search for df = 3. They can speed this up by taking advantage of the fact that there will be some rotation of f that has a 1 in the first position, so they only need to search the (10 pick 2) possible locations for the other two nonzero coefficients of f. The full search they perform is this:

           f*h (=g)                                       f
[9, 18, 7, 13, 26, 22, 15, 28, 27, 24, 19]; [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[23, 17, 4, 8, 16, 2, 3, 6, 10, 21, 11]; [1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[15, 2, 3, 5, 11, 21, 12, 23, 17, 4, 8]; [1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[12, 23, 17, 4, 8, 16, 2, 3, 5, 11, 20]; [1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0]
[24, 20, 9, 18, 7, 13, 26, 22, 14, 28, 27]; [1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[2, 3, 6, 10, 21, 12, 23, 17, 4, 8, 15]; [1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[19, 10, 18, 7, 13, 26, 22, 14, 28, 27, 24]; [1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0]
[28, 27, 25, 19, 10, 18, 7, 13, 25, 22, 14]; [1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[18, 7, 13, 26, 22, 15, 28, 27, 24, 19, 9]; [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[22, 14, 28, 27, 25, 19, 10, 18, 7, 13, 25]; [1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
[14, 28, 27, 24, 20, 9, 19, 6, 14, 25, 22]; [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[11, 20, 12, 23, 17, 4, 9, 15, 2, 3, 5]; [1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0]
[23, 17, 4, 8, 16, 1, 4, 5, 11, 20, 12]; [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0]; [1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0]
[18, 7, 13, 26, 22, 14, 0, 26, 25, 19, 9]; [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0]
[27, 24, 20, 9, 19, 6, 14, 25, 22, 14, 28]; [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0]
[17, 4, 8, 16, 2, 3, 6, 10, 21, 11, 23]; [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1]
[28, 27, 24, 19, 10, 18, 7, 13, 26, 22, 14]; [1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0]
[25, 19, 9, 18, 7, 13, 26, 22, 14, 0, 26]; [1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0]
[8, 16, 1, 3, 6, 10, 21, 12, 23, 17, 4]; [1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0]
[15, 28, 27, 24, 20, 9, 18, 7, 13, 26, 21]; [1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0]
[3, 6, 10, 21, 12, 23, 17, 4, 8, 16, 1]; [1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0]
[12, 23, 17, 4, 9, 15, 2, 3, 5, 11, 20]; [1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0]
[2, 3, 5, 11, 21, 12, 23, 17, 4, 8, 15]; [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1]
[17, 4, 8, 15, 2, 3, 6, 10, 21, 12, 23]; [1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1]; [1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]
[7, 13, 26, 21, 15, 28, 27, 24, 20, 9, 18]; [1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0]
[24, 20, 9, 18, 7, 13, 26, 21, 15, 28, 27]; [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]
[4, 8, 16, 1, 4, 5, 11, 20, 12, 23, 17]; [1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0]
[23, 17, 4, 8, 16, 2, 3, 5, 11, 20, 12]; [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1]
[26, 22, 14, 28, 27, 24, 20, 9, 18, 7, 13]; [1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0]
[4, 5, 11, 20, 12, 23, 17, 4, 8, 16, 1]; [1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0]
[21, 12, 23, 17, 4, 8, 16, 1, 3, 6, 10]; [1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0]
[1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0]; [1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0]
[20, 9, 18, 7, 13, 26, 22, 14, 28, 27, 24]; [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]
[16, 2, 3, 5, 11, 20, 12, 23, 17, 4, 8]; [1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0]
[4, 9, 15, 2, 3, 5, 11, 20, 12, 23, 17]; [1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0]
[13, 26, 22, 14, 0, 26, 25, 19, 9, 18, 7]; [1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0]
[3, 6, 10, 21, 12, 23, 17, 4, 8, 15, 2]; [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]
[11, 21, 12, 23, 17, 4, 8, 15, 2, 3, 5]; [1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0]
[20, 9, 19, 6, 14, 25, 22, 14, 28, 27, 24]; [1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0]
[10, 18, 7, 13, 26, 22, 14, 28, 27, 24, 19]; [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
[8, 16, 2, 3, 6, 10, 21, 11, 23, 17, 4]; [1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0]
[27, 25, 19, 10, 18, 7, 13, 25, 22, 14, 28]; [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1]
[7, 13, 26, 22, 15, 28, 27, 24, 19, 9, 18]; [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]

Scan down there, and you can see that g appears in row 14, 26 and 34 of the 45 rows. (g appears three times because there are three 1's in f, so there are three rotations of f that have a 1 in the leading position).

Now let's look at the meet-in-the-middle attack. The attacker uses the formula

(f1+f2) * h = g

so

f1*h = g - f2*h

Using e[i] to mean the i'th coefficient of e, this means that the attacker knows that

(f1*h)[i] = - (f2*h)[i] + 0 or 1

So the attacker calculates all possible values of f1*h. Call the resulting list {g1}. They then calculate -f2*h and for each result g2, they see if g2 is the same as an existing g1 or if g2 differs from any g1 by no more than 1 in each coefficient. In other words,

[3, 10, 12, 7]

would match

[4, 10, 12, 8]

Doing it this way, the attacker needs only work through the following:

• All 10 f1s with a 1 in the leading position and a 1 somewhere else
• All 10 f2s with a single 1 in any position other than the leading one

This gives the following. I've sorted the lists to make the matches easier to spot.

          f1*h = g1                                           f1
[00, 08, 26, 03, 16, 12, 05, 18, 17, 15, 09]     [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
[03, 16, 12, 04, 19, 17, 15, 09, 00, 08, 26]     [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[06, 21, 22, 25, 01, 11, 02, 13, 07, 23, 27]     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[07, 24, 27, 06, 21, 22, 25, 00, 11, 02, 13]     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
[11, 02, 13, 07, 24, 27, 06, 21, 22, 25, 00]     [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[12, 05, 18, 17, 15, 09, 00, 08, 26, 03, 16]     [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[16, 12, 05, 18, 18, 14, 10, 28, 08, 26, 03]     [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[19, 17, 15, 09, 00, 08, 26, 03, 16, 12, 04]     [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[26, 03, 16, 12, 05, 18, 18, 14, 10, 28, 08]     [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[27, 06, 21, 22, 25, 01, 11, 02, 13, 07, 23]     [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

         -f2*h = g2                                          f2
[03, 15, 12, 04, 18, 17, 14, 09, 28, 08, 25]     [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[04, 18, 17, 14, 09, 28, 08, 25, 03, 15, 12]     [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[08, 25, 03, 15, 12, 04, 18, 17, 14, 09, 28]     [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
[09, 28, 08, 25, 03, 15, 12, 04, 18, 17, 14]     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[12, 04, 18, 17, 14, 09, 28, 08, 25, 03, 15]     [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[15, 12, 04, 18, 17, 14, 09, 28, 08, 25, 03]     [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
[17, 14, 09, 28, 08, 25, 03, 15, 12, 04, 18]     [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[18, 17, 14, 09, 28, 08, 25, 03, 15, 12, 04]     [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[25, 03, 15, 12, 04, 18, 17, 14, 09, 28, 08]     [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[28, 08, 25, 03, 15, 12, 04, 18, 17, 14, 09]     [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]

You can see that:

• line 1 of g1 matches with line 10 of g2, giving [1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0]
• line 2 of g1 matches with line 1 of g2, giving [1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]
• line 6 of g1 matches with line 5 of g2, giving [1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]
• line 7 of g1 matches with line 6 of g2, giving [1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0]
• line 8 of g1 matches with line 8 of g2, giving [1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0]
• line 9 of g1 matches with line 9 of g2, giving [1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0]

There are 6 collisions here because there are 3 rotations with a 1 in the leading position and for each rotation there are two ways to pick the other two coefficients.

So an attacker would have to do about 45/3 = 15 work to find the key with a brute force search and about 10 work to find the key with a meet-in-the-middle attack (slightly less than 10 due to the rotations, but I don't have a clean formula to hand).

There are various optimizations, but this should be enough to give you the idea.

One thing I haven't dealt with so far is how to keep the search time down. A straightforward way to do it is simply to sort the results as you're going along. The time to insert or look for a collision with an entry is about log_2(size of the search space). Alternatively, at the cost of using more memory, it's possible to bring this search time down to a constant by reserving a block for each possible value of the first few coefficients of g1.

Hope this helps. Let me know if you have any more questions.