7 ms·

Would love to see more details on the practical implementation of this attack / source code. Whilst detecting primes in random data is feasible, can't imagine h

by vizzah 13y ago

Would love to see more details on the practical implementation of this attack / source code. Whilst detecting primes in random data is feasible, can't imagine how chunks of returned data were "unrandomized" for this type of attack.

tptacek 13y ago
Coppersmith is complex enough that I'd be impressed to see working implementations even in lab conditions; it's one of the lattice reduction crypto attacks.
- pbsd 13y ago
  It's really not that bad with today's computer algebra packages. Here's a simple example in Sage that works most of the time: p = random_prime(2**512) q = random_prime(2**512) n = p*q P.<x> = PolynomialRing(Zmod(n)) partialp = p - p % 2**224 # most significant 288 bits f = x + partialp root = f.small_roots(X=2**(224), beta=0.5, epsilon=2**-5) assert(root[0] + partialp == p) partialp = p % 2**288 # least significant 288 bits f = x + partialp * inverse_mod(2**288, n) root = f.small_roots(X=2**(224), beta=0.5, epsilon=2**-5) assert( root[0]*2**288 + partialp == p )
  - tptacek 13y ago
    Man I hate you. What's especially funny is if you search for "SAGE" and "small_roots", you get this: http://trac.sagemath.org/ticket/2424 http://trac.sagemath.org/ticket/2424 Please at least tell me small_roots was hard to implement.
  - vizzah 13y ago
    Cool. Would this approach work if 'partialp' is not coming from the starting or ending bits of the targeted prime number?
    - pbsd 13y ago
      Yes. But it makes for a worse didactic example, since Sage does not support it out of the box. Imagine you know the middle 288 bits of p. Then you have to find small roots of the equation x1*2**400 + partialp + x0, which now has 2 variables x0, x1 < 2^112. This requires building a different lattice than in the single variable case, but the complexity of the attack is not very different. Also note that it doesn't have to be p or q. Bits of d, d mod (p-1), and d mod (q-1), and possibly other intermediate values of RSA computations are also usable for this.

by vizzah 13y ago

tptacek 13y ago

Coppersmith is complex enough that I'd be impressed to see working implementations even in lab conditions; it's one of the lattice reduction crypto attacks.

pbsd 13y ago
It's really not that bad with today's computer algebra packages. Here's a simple example in Sage that works most of the time: p = random_prime(2**512) q = random_prime(2**512) n = p*q P.<x> = PolynomialRing(Zmod(n)) partialp = p - p % 2**224 # most significant 288 bits f = x + partialp root = f.small_roots(X=2**(224), beta=0.5, epsilon=2**-5) assert(root[0] + partialp == p) partialp = p % 2**288 # least significant 288 bits f = x + partialp * inverse_mod(2**288, n) root = f.small_roots(X=2**(224), beta=0.5, epsilon=2**-5) assert( root[0]*2**288 + partialp == p )
- tptacek 13y ago
  Man I hate you. What's especially funny is if you search for "SAGE" and "small_roots", you get this: http://trac.sagemath.org/ticket/2424 http://trac.sagemath.org/ticket/2424 Please at least tell me small_roots was hard to implement.
- vizzah 13y ago
  Cool. Would this approach work if 'partialp' is not coming from the starting or ending bits of the targeted prime number?
  - pbsd 13y ago
    Yes. But it makes for a worse didactic example, since Sage does not support it out of the box. Imagine you know the middle 288 bits of p. Then you have to find small roots of the equation x1*2**400 + partialp + x0, which now has 2 variables x0, x1 < 2^112. This requires building a different lattice than in the single variable case, but the complexity of the attack is not very different. Also note that it doesn't have to be p or q. Bits of d, d mod (p-1), and d mod (q-1), and possibly other intermediate values of RSA computations are also usable for this.