Transcript Document

Cryptanalysis of the Revised
NTRU Signature Scheme (NSS)
Craig Gentry (DoCoMo)
Mike Szydlo (RSA)
A Brief History of NSS
• “Preliminary NSS”
• Presented at Crypto 2000 Rump
• Broken by Mironov, and by the inventors
• NSS in Eurocrypt 2001 proceedings
• Forgery / key recovery attacks presented at Eurocrypt
Rump by Gentry, Jonsson, Stern, and Szydlo
• Motivated new key-gen, sign, and verify procedures
• “Revised” NSS
• Sketched at Eurocrypt 2001, details in EESS doc (May)
• Still insecure – we give key recovery attacks…
Cryptanalysis of the Revised NTRU Signature Scheme / 2
Revised NSS, Details
• Basic Elements are Polynomials.
• Full (unreduced ring) is Z[x]/(xN-1), (N = 251)
• (Also Called Cyclotomic Integers).
• Multiplication in ring also called convolution.
• Auxiliary Rings and Polynomials
• Truncated Polynomial Ring Z[x]/(xN-1) mod 128
• A Small Polynomial” has only {-1,0,1} coefficients.
Cryptanalysis of the Revised NTRU Signature Scheme / 3
Key Generation
Private Components
• f1, g1, u  Z[x]/(xN-1) are small polynomials.
• (standardized number of {-1,0,1} coefficients).
• f=3*f1+u, and g=3*g1+u. are computed.
• Let v be the small polynomial with u*v=1 (mod 3).
• The private key components are (f,g,v)
Public Components
• Let f_inv be a polynomial with f*f_inv=1 (mod 128).
• Let h be f_inv*g (mod 128).
• The public key is (h)
Cryptanalysis of the Revised NTRU Signature Scheme / 4
Signature
• Signature (s, t) is computed from f , g , v and message m
• Algorithm:
• Let w1,w2 be random small masking polynomials.
• (Generated by a sub-algorithm).
• Let w0 be the small poly. with w0=(m+w1) (mod 3).
• Let s=f*(w0+3w2) (mod 128)
• Let t=g*(w0+3w2) (mod 128)
• The signature is (s, t).
• (Note t is also publicly computable from s and h)
Cryptanalysis of the Revised NTRU Signature Scheme / 5
Verification
• Multiple Tests, including
• Norm Conditions
• Use division modulo 128 and centered norm.
• | (s-m)/p | < B, and | (t-m) | < B.
• | (s-t)/p | < B2, and | (t-m) | < B.
• Distribution Tests
• “Mod 3” - Bounds on # coefs of s & t (mod 3).
• “Quartile” - Bounds # of coefs in [-64,64]
• Thus s and t appear to be from right distribution.
Cryptanalysis of the Revised NTRU Signature Scheme / 6
Lifting the Signatures
• Design motivation of reduction mod q
• Hide more information about f and g.
• Only known lattice was dimension 2N. (NTRU Lattice)
• “Unreduced” signatures would allow dim N. Attacks.
• For “equivalent” security use half the key size
• Lifting Technique: Apply CRT to congruences:
• f*w=m+w1 (mod 3), s=m (mod 128)
• The unknown w1 coefs. are mostly 0.
• Result: Nearly have the lifted multiples: f * w and g * w
• Approximations have about 25 errors (out of 251)
Cryptanalysis of the Revised NTRU Signature Scheme / 7
Finishing the Lifting
• Goal: Find f * w and g * w, error-free.
• Take short transcript of signatures: (Si , Tj)
• Observation: We know correct liftings
•
(f * wi) * (g * wj) – (f * wj) * (g * wi) = 0
Si * Tj – Sj * Ti
Measures
the errors
•
Iterative Error-Correction: Choose the correction to (Si, Ti)
that sends Si * Tj – Sj * Ti closest to 0.
• 4 signatures, 25 seconds  we get unreduced signatures
Cryptanalysis of the Revised NTRU Signature Scheme / 8
We Could Stop Here
• By finding unreduced f * w and g * w, we’ve already
broken revised NSS.
• Dim N lattice (instead of 2N) – exp. easier to reduce
1




0



h0
1
h0
1
q
0
q
0



h0 




q 
 fw0



fw
0



fw0  w is

 GCD
gw
 0



gw0


gw0 

Cryptanalysis of the Revised NTRU Signature Scheme / 9
Computing f * frev Quickly
• We average sigs to obtain f * frev approximately.
S * Srev   f * frev
Converges
Quickly!
• We use approximation in N/2 Dim CVP lattice.
• With < 10 sigs (to obtain approx), LLL gives us f * frev
exactly.
Cryptanalysis of the Revised NTRU Signature Scheme/10
A Polynomial-time Approach
• Textbook GCD approach appears to be exp. in N
• Our approach: Polynomial in N
(after experimentally very fast steps)
Preliminary step
• Fast step: Compute f * frev.
• Poly step: Use f * frev and f * w to compute f.
• Running times:
• Fast step: Less than 1 minute for sugg. parameters
• Poly step: Not implimented, but provably O(N 7).
Cryptanalysis of the Revised NTRU Signature Scheme /
Get f from f * frev and f * w in Polynomial-time
• We help LLL – it doesn’t always find shortest vector!
Fact: f p-1  1 (mod p)
•
•
•
•
for prime
p  1 (mod N)
Use LLL to get f p-1 * a.
We know a (mod p), thus maybe a exactly. Compute f p-1.
Not difficult to compute f from power of f.
This algorithm is efficient because LLL does not have to
find the shortest vector in the lattice.
Cryptanalysis of the Revised NTRU Signature Scheme /
Other Attacks
• Polynomial attack shows can’t just increase key size
• Alternate attacks using Lattices might be more efficient.
• Compute the ratio g/f in Z[x]/(xN-1) mod Q.
• Bigger Q improves lattice constants.
• Can translate into traditional Knapsack
• Gram Matrix Attack: (find the circulant M_f)
• A known matrix M defines GCD (f).
• Let G= U*U_rev= UF M_(1/f*f_rev) F_rev U_rev.
• Factor G with “modular-Gram-LLL”
Cryptanalysis of the Revised NTRU Signature Scheme /
Conclusion
• These attacks render revised NSS (with sugg. parameters)
very weak.
•
We have presented a 3-Stage Attack
• First 2 stages very fast, use about 10 sigs.
•
•
Last stage polynomial in N.
First stage is enough to dramatically reduce its security.
Cryptanalysis of the Revised NTRU Signature Scheme /