Part of the reason small size keys like this are in common use is that bind (and possibly other name daemons) doesn't allow records larger than 255 characters. DKIM requires one to put the public key in DNS.
Earlier this week I set up DKIM, and initially tried and failed to use a 2048-bit key, because of this issue.
2.3.4. Size limits
Various objects and parameters in the DNS have size
limits. They are listed below. Some could be easily
changed, others are more fundamental.
labels 63 octets or less
names 255 octets or less
TTL positive values of a signed 32 bit number.
UDP messages 512 octets or less
Although if the response to a query doesn't fit, the TC bit is supposed to be set and clients should retry over TCP. This is rare enough in practice, though, that not all implementations bother.
>Some months ago I started an 8 core Mac Pro machine at work on breaking this key. It ran for 70 days non-stop and was close to a break when I had to use the machine for something else.
Might also be not true, or the author did find the key but doesn't want to get into any legal trouble.
>If I can do that, pretty much anyone can. And those people will be able to forge mail from Facebook. Facebook has a simple solution, of course, just change the key length.
When that happens, Facebook changes the key, problem solved.
>The owner of a spam botnet could factor keys like that very quickly. Imagine having a few thousand machines that can be used for key factoring.
Or just paying for a dozen of EC2 instanced for a week (not sure how parallel this thing is, but I assume you could distribute it somehow).
I'm ignorant to what's involved, but would it be possible to change the key daily even? Or is there a danger of mails failing due to stale DNS records?
I find 512-bit RSA keys interesting because they seem to be in occasional use but are within the realms of amateur factoring.
From my limited experiences of smaller keys (high 400-bit range) I'm actually slightly surprised you didn't get there in 70 days on an 8-way machine. How many relations did you find?
Some fun statistics:
- The factorization took, in total, about 1745 hours, or a bit less
than 73 days, of computation. (I've actually been working on this
since early March; I had a couple of false starts and haven't been
able to run the software continously.)
- My CPU, for reference, is a dual-core Athlon64 at 1900 MHz.
- The sieving database was 4.9 gigabytes and contained just over 51
million relations.
- During the "filtering" phase, Msieve was using about 2.5 gigabytes of RAM.
- The final processing involved finding the null space of a 5.4 million x
5.4 million matrix.
I'd have to pull up the log file to take a look as I've completely forgotten now. IIRC There were plenty of relations and it was pretty far gone through the sieving when we had a power outage and then I had to travel too much and then... life intervened.
The oddest part is that the RFCs on DKIM recommend against keys below 1024 bits.
Modern factoring techniques, broadly speaking, involve finding lots of relationships between appropriate numbers, and then finding a combination of these relationships that produce the desired result. There are heuristics to suggest how many relationships will be needed to get an appropriate combination, and progress can be "measured" by seeing how close you are to that number.
More specifically ...
Most factoring algorithms are a variant of:
+ Find lots of numbers that are squares modulo N (these are called quadratic residues)
+ Factor those numbers completely
+ Find a subset of those factored numbers such that ...
+ taken together, all the powers of primes are even.
The result is then two squares that are congurent modulo N, and using the difference of two squares formula, you ahve a non-trivial chance of a factorisation. The relationships I first mentioned are the quadratic residues, the combination is the subset.
There are various techniques for finding small quadratic residues that are (relatively speaking) easy to factor. These include the quadratic sieve, the multiple polynomial quadratic sieve, the continued fraction method, and the number field sieve (special and general).
The combinations are found by finding linearly dependent rows of a sodding enormous matrix modulo 2. This can be done using elementary linear algebra, but you need humungous amounts of memory.
The combinations are found by finding linearly dependent rows of a sodding enormous matrix modulo 2. This can be done using elementary linear algebra, but you need humungous amounts of memory.
Err... no, not really. In addition to taking O(n^2) storage, a dense solve will take O(n^3) time, which is quite infeasible for typical matrix sizes.
Instead, we use a sparse solve, such as the block Lanczos algorithm, which takes O(nw) storage and O(n^2w) time, where w is the average row weight.
I thought the comment was already too long, and was trying to give an outline and not dive into too many details. I've already omitted some of the methods to assist with the factoring of small quadratic residues, for example, and this was another part where I thought I'd give the naive idea rather than too many explicit details.
But you're absolutely right, and thank you for providing some of said details. It's nice to know that things I write are going to be checked by people who actually know more than I do.
If you had just stopped at "finding lineearly dependent rows of a sodding enormous matrix modulo 2" I wouldn't have said anything -- but mentioning elementary linear algebra was potentially misleading, so I figured it was worth adding the details there. :-)
For what it's worth, there is actually some elementary linear algebra done before the heavy guns are brought out: If a prime only occurs in two or three relations, adding one of those relations to the other(s) will decrease n while increasing w by a small enough factor as to make the final Lanczos solve faster. (In rare cases it can be worth eliminating primes which occur in 4 relations or more, but usually not.)
Earlier this week I set up DKIM, and initially tried and failed to use a 2048-bit key, because of this issue.