4 ms·
Really great writeup. Here's the most astounding part to me: "[Rubin Xu] decided to use Coppersmith's Attack[1] to derive the private exponent. In this attack,
by 3JPLW 13y ago
Really great writeup. Here's the most astounding part to me: "[Rubin Xu] decided to use Coppersmith's Attack[1] to derive the private exponent. In this attack, only pieces of the private key are needed and the private key is reconstructed mathematically. This attack is so efficient that he managed to extract the private key from only the first 50 dumps!"
That's no more than ~3MB of data. Some of the other winners hit the server with hundreds of thousands of requests which might have gotten noticed. Doing this with only 50 heartbeats (which could be spread across many days) makes the "undetectable attack" even less detectable.
[1]. Coppersmith's Attack: http://en.wikipedia.org/wiki/Coppersmith's_Attack http://en.wikipedia.org/wiki/Coppersmith's_Attack
- vizzah 13y agoWould 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 agoCoppersmith 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 agoIt'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 agoMan 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 agoCool. Would this approach work if 'partialp' is not coming from the starting or ending bits of the targeted prime number?
- pbsd 13y agoYes. 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.
- jchrisa 13y agoCan someone write it up in plain language? I grok that reducing entropy is bad, is this just one in a set of attacks for attacking entropy leaks?
- j_s 13y agoSo anyone stuck using vulnerable SSL is basically using telnet; ouch! Hopefully it will be a while before this implementation makes it to the various frameworks.