The factorization of RSA-640 was accomplished using a prime factorization algorithm known as the general number field sieve. Sieving was done on 80 2.2-GHz Opteron CPUs and took 3 months. The matrix step was performed on a cluster of 80 2.2-GHz Opterons connected via a Gigabit network and took about 1.5 months.
You may wonder why this is important. As it happens, I'm participating in an IBM Redpaper project right now on the subject of Notes and Domino security, and I'm writing the chapter on support for larger encryption keys in ND7, so I can tell you very precisely why it's important: Notes ID files generated by all versions before 7 contain RSA keys that max out at 630 bits, and we now know definitively that the hardware and time cost of cracking these keys is unacceptably low. A very highly motivated attacker going after confidential business information worth millions of dollars could already be willing to devote an 80 node cluster to the job for four and a half months to the job, and Moore's Law will drop the time and hardware cost even further over the next several years. There's no reason for the vast majority of us to panic right now, but it will get to the point where even only moderately valuable data could become a tempting target. I had expected that point to be another five to ten years away -- and probably closer to ten, but the successful factorization of RSA-640 on non-specialized equipment in just a few months means it will probably be closer to five.
The good news is that Notes and Domino 7 can generate 1024 bit keys, and Notes and Domino 6 have forward compatability for them built in. There's a rollover process for converting IDs with 6Notes and Domino 7 has forward compatability for even larger keys builit in. As a rule of thumb, for every ten bits you add to an RSA key, the time to crack it doubles, so the extra 394 bits that you can gain from and ND7 upgrade should push the practical security window for Notes and Domino authentication and encryption out past 20 years again. That's presuming both a continuation of the Moore's Law pattern, plus an equivalent pattern in mathematical techniques yielding a net 50% reduction in time and cost every six months. The forward compatability in ND7 with even larger keys that will be supported in future Notes and Domino versions will likely push that security window out so far into the future that the only possible threat will come from an extraordinary technological breakthrough -- such as practical quantum computing.
In the slow cycle of IT upgrades, five years is not really that long a time period. Beariing that in mind, I say that the news of the RSA-640 factorization should be a motivating factor for anyone who likes Notes and Domino because it is secure. Large corporations that don't start planning on upgrading to ND7 within the next year could find themselves at risk of running out of time to plan and execute the upgrade and to also go through the process of rolling over IDs to make use of larger keys, leaving them in a position where their secured data is isn't secure any more.
1. George Chiesa11/13/2005 09:08:28 PM
Wow. So what ? Well, simply put, (with my non resident paranoid hat on) the bad people who code webbots and have access to a LOT of decentralised (captive home) computing. The next killer app in the internet: renting of bot-networks to crack keys. Of course, a job better suited for the maffias that already control zillions of broadband pcs.