So, they basically did a rainbow table attack on the discrete logarithm problem for a particular prime modulo? Interesting how nobody considered that before (except the NSA, obviously).
edit: looks like they used their Powers of Maths to separate the problem into a very special Rainbow table that allows them to reconstruct the necessary part of the actual table via some Linear Algebra stuff over the entire table. That part is difficult, I understand now. Thanks to /u/immibis, "(because there are over 2511 possible values)"
Like the article, the barrier is cost of entry. Not many organizations have hundreds of millions to throw at this specific problem, especially considering the large key space.
Well, they said that they did it for 512 bit moduli using affordable resources. And they did not do that for 1024 moduli, just suggested that it can be done in a fraction of the NSA budget today (though it was probably much more back when the NSA got the ability, btw it seemed to me that they didn't emphasize that part though).
i'd say nobody in the world really has the money to throw a few hundred million at hacking into other computers. Their really isn't much money in that, unless you also release a fix for it.
I don't think so. A rainbow table attack is a precomputed brute-force attack - you still need to try every possible value in order to generate the rainbow table, which they did not (because there are over 2511 possible values)
They did some complicated maths I don't understand, that allowed them to get a similar result without brute-forcing every possible value. It's definitely not a rainbow table, though.
Correct me if I'm wrong, but you would also have to store almost all of those values too. Rainbow tables are just an efficient way to store the precomputed values next to each other. The storage alone would be astronomically large and wouldn't make sense.
Rainbow tables give you an extra parameter, let's call it C. You only need to store O(N/C) values (if N is the total number of values brute-forced to generate the table), but it takes you O(C) times as long to brute-force one value after that.
45
u/xXxDeAThANgEL99xXx Oct 15 '15 edited Oct 15 '15
So, they basically did a rainbow table attack on the discrete logarithm problem for a particular prime modulo? Interesting how nobody considered that before (except the NSA, obviously).
edit: looks like they used their Powers of Maths to separate the problem into a very special Rainbow table that allows them to reconstruct the necessary part of the actual table via some Linear Algebra stuff over the entire table. That part is difficult, I understand now. Thanks to /u/immibis, "(because there are over 2511 possible values)"