8
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$
    – Thomas Pornin
    Commented Oct 2, 2012 at 22:13
  • $\begingroup$ @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? $\endgroup$
    – Polynomial
    Commented Oct 3, 2012 at 7:48
  • 3
    $\begingroup$ 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. $\endgroup$
    – Thomas Pornin
    Commented Oct 3, 2012 at 10:18
  • 1
    $\begingroup$ Breaking 512 bit RSA seems to cost around 100$ ATM. $\endgroup$
    – CodesInChaos
    Commented Nov 9, 2012 at 21:37
  • 1
    $\begingroup$ Relevant paper: Factoring as a Service - Luke Valenta and Shaanan Cohney and Alex Liao and Joshua Fried and Satya Bodduluri and Nadia Heninger $\endgroup$
    – CodesInChaos
    Commented Nov 22, 2015 at 9:14

4 Answers 4

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Is there a decent projection of the time it'd take to break a 512-bit key today? $\endgroup$
    – Polynomial
    Commented Oct 2, 2012 at 11:35
  • $\begingroup$ @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. $\endgroup$
    – Thomas
    Commented Oct 2, 2012 at 12:05
  • $\begingroup$ @Thomas Yikes. I'll see if I can find a pure-managed implementation of RSA then, so I can use 2048-bit keys. $\endgroup$
    – Polynomial
    Commented Oct 2, 2012 at 12:11
  • 4
    $\begingroup$ @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. $\endgroup$
    – fgrieu ♦
    Commented Oct 2, 2012 at 14:53
11
$\begingroup$

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.

Another project in a similar vein: Factoring as a Service:

The Factoring as a Service project is designed to allow anyone to factor 512-bit integers in as little as four hours using the Amazon EC2 platform for less than $100, with minimal setup.

You should be able to just run the scripts from their github.

Improve this answer
$\endgroup$
5
$\begingroup$

It is not safe at all since Factoring as a service project (https://github.com/eniac/faas) together with Amazon EC2 allows the factorization of a 512-bit key for less than $100 in only a few hours.

Improve this answer
$\endgroup$
2
$\begingroup$

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/

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Commented Oct 3, 2012 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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