Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

The standard CSP on Windows XP only supports RSA up to 512-bit, which means that it's the maximum key size I can use for authenticity verification of updates. The public key is embedded in the updater, and the update files are signed with the private key, using SHA256.

I know that RSA-768 was factored back in 2010, which is what makes me wonder if RSA-512 is still acceptable for signing purposes. How much effort is it for an attacker to break a 512-bit RSA key?

share|improve this question
1  
I seriously doubt that WinXP cannot go beyond 512 bits, especially since I have done a lot of RSA-1024 with the CSP which come with a stock Windows 2000. The "base CSP" was limited to 512 bits because of the export regulations of that time, but they were lifted near the end of the Clinton presidency. –  Thomas Pornin Oct 2 '12 at 22:13
    
@ThomasPornin Interesting. I read on MSDN that the base CSP was 512-bits and shipped with the OS, and it implied (or, rather, I inferred) that you have to manually download the expanded CSP. Am I wrong in this assumption? –  Polynomial Oct 3 '12 at 7:48
2  
All Windows 2000, XP and more that I have come across always had several CSP installed, including the "strong" ones. Remember that IE uses them for SSL; if a basic Windows could not do more than 512-bit RSA, IE would not be able to handle common HTTPS sites. –  Thomas Pornin Oct 3 '12 at 10:18
    
@ThomasPornin Good point. I'll switch to 1024 for now, and I'll find a WinXP box to test 2048-bit on. –  Polynomial Oct 3 '12 at 10:35
1  
Breaking 512 bit RSA seems to cost around 100$ ATM. –  CodesInChaos Nov 9 '12 at 21:37

3 Answers 3

up vote 6 down vote accepted

No.

The challenge for RSA-155 (which is 512 bits) was broken in 1999. This took 6 months on pretty advanced hardware to break at the time, which works out to 8000 MIPS years. It should be much less today.

FYI, RSA 768 took just under 3 years.

share|improve this answer
    
Is there a decent projection of the time it'd take to break a 512-bit key today? –  Polynomial Oct 2 '12 at 11:35
    
@Polynomial Assuming the same number of computers, but with current clock speeds and extra cores (sieving can be parallelized), and adjusting for parallel scaling, it would come out as about 11 days. Throw a few GPU's in the mix and a week could be realistic. –  Thomas Oct 2 '12 at 12:05
    
@Thomas Yikes. I'll see if I can find a pure-managed implementation of RSA then, so I can use 2048-bit keys. –  Polynomial Oct 2 '12 at 12:11
3  
@Polynomial: a team of enthusiast nowadays breaks a 512-bit key within days, using public domain tools. Also see this answer, especially the references to the TI-83 Plus OS Signing Key broken in 2009. –  fgrieu Oct 2 '12 at 14:53

Considering special purpose hardware, according to [40] sieving for a 1024-bit RSA modulus can be done in a year for about US \$10,000,000, plus a one-time development cost of about US \$20,000,000, and with a comparable time and cost for the matrix.

-- Bos et al.

RSA.816 offers very short-term protection against small organizations Should not be used for confidentiality in new systems.

http://www.keylength.com/en/3/

share|improve this answer
    
Two key words in the citation are sieving and development: there is much more to factorization of a 1024-bit RSA modulus than the sieving step; and the technology for that fast sieving is not developed, at least publicly. And comparable includes "n times more costly" for arbitrarily large n. –  fgrieu Oct 3 '12 at 7:06

I don't have any experience with this myself, but Tom Ritter talked about this on twitter:

Matthew Green: Out of curiosity: do you happen to know offhand how much it costs to factor a 512-bit RSA key on EC2?

Tom Ritter: My personal costs are \$120-\$150 with my setup. You can probably do it cheaper, heard reports of \$75.

He also published a description of how to factor RSA moduli.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.