768-bit Number Factored

News:

On December 12, 2009, we factored the 768-bit, 232-digit number RSA-768 by the number field sieve. The number RSA-768 was taken from the now obsolete RSA Challenge list as a representative 768-bit RSA modulus. This result is a record for factoring general integers. Factoring a 1024-bit RSA modulus would be about a thousand times harder, and a 768-bit RSA modulus is several thousands times harder to factor than a 512-bit one. Because the first factorization of a 512-bit RSA modulus was reported only a decade ago it is not unreasonable to expect that 1024-bit RSA moduli can be factored well within the next decade by an academic effort such as ours…. Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.

[…]

Our computation required more than 1020 operations. With the equivalent of almost 2000 years of computing on a single core 2.2GHz AMD Opteron, on the order of 267 instructions were carried out. The overall effort is sufficiently low that even for short-term protection of data of little value, 768-bit RSA moduli can no longer be recommended.

News articles.

Tags: , , , ,

Posted on January 11, 2010 at 8:00 AM • 37 Comments

Comments

Clive Robinson • January 11, 2010 8:35 AM

Oh dear I guess it’ll be business for the usually dog house / snake oil suspects.

Hmm.

RSA has other problems (kleptocryptography) so it’s not just the number of bits that needs some serious thought…

Tim • January 11, 2010 8:43 AM

So, the matrix step was also performed on distributed cluster, not on some integrated supercomputer with huge memory, as before ? This seems to be something new.

jgreco • January 11, 2010 9:41 AM

@Matt Simmons

Well, seeing as 4096 is only a measly .5 KB of data, but is obscenely larger than 768, it should be quite a long while 😉

Although on second thought, isn’t RSA often used for key exchange? I’m not familar with how much overhead is generally involved with that, but we may already be there…

Kyle Rose • January 11, 2010 9:43 AM

Matt, this is nearly always the case, as RSA is typically used only to encrypt a relatively shorter (128-256 bit) symmetric key or sign a relatively shorter (again 128-256 bit) cryptographic hash.

aikimark • January 11, 2010 9:48 AM

a 768-bit RSA modulus is several thousands times harder to factor than a 512-bit one

Pardon me, but wouldn’t 256 bits (=768-512) be much more difficult than “several thousands times harder” ?!?

Is this snake oil or am I missing something obvious?

David Cornwell • January 11, 2010 10:04 AM

According to NIST standards, 1024 bit keys provide 80 bits of security and will only be valid until the end of 2010. After that NIST recommends at least 112 bits of security or 2048 bit keys.

Dave C.

Kevin • January 11, 2010 10:17 AM

Pssh – I’m able to crack those pesky 1024 bit keys in about 2 hours with this polynomial-time factoring algorithm I worked out (something I had to build for my boss to improve his cludgy email spam-filter).

Anyway, now time to figure out why the printer keeps crashing.

(Humor drawn from http://www.xkcd.com/664/ )

John • January 11, 2010 10:19 AM

@aikimark

The issue is that RSA keys are not random. Adding 1 bit to a symmetric key doubles the size of the key space. Adding 1 bit to an RSA key does not double the key space.

greg • January 11, 2010 10:19 AM

@aikimark

This is not snake oil. These numbers are not true random numbers. Not all 768bit numbers are valid for RSA. In particular they are the factor of 2 large prime numbers. Thus adding a bit, does not make it twice as hard to factor.

Also factoring Algorithms are pretty good. But you can’t use the GNS on EC so this is why we think you can get away with less bits for the same security with ECC.

hhh • January 11, 2010 11:37 AM

The low-tech diagrams of figure 1 (p.12) – hand-drawn on quadrille paper with highlighter pens – contrast nicely with the massive amount of computation power they summarize.

One also has to love the meticulous fashion in which the “That’s a bingo” meme is referenced to a YouTube excerpt from Quentin Tarantino’s latest movie. (“Part of this paper was inspired by Col. Hans Landa.”)

On a more serious note:

“Another conclusion from our work is that we can quite confidently say that if we restrict ourselves to an open community, academic effort as ours and unless something dramatic happens in factoring, we will not be able to factor a 1024-bit RSA modulus within the next five years (cf. [29]). After that, all bets are off.”

“The overall effort is sufficiently low that even for short-term protection of
data of little value, 768-bit RSA moduli can no longer be recommended. This conclusion is the opposite of the one arrived at on [38 = http://www.rsa.com/rsalabs/node.asp?id=2094 ], which is based on a hypothetical factoring effort of six months on 100 000 workstations, i.e., about two orders of magnitude more than we spent.”

Jor Jor • January 11, 2010 12:32 PM

So, is there any form of ECC that isn’t subject to patent threats yet? I know Dan Bernstein says Curve25519 is not, but that only means he won’t try to restrict it, not that it’s immune to patent trolls.

PackagedBlue • January 11, 2010 2:04 PM

All this serious crypto is just funny talk, because the government/industry will not allow stock computers to be even acceptably secure, where the strength of the crypto matters much.

jgreco • January 11, 2010 2:50 PM

@PackagedBlue

In case you missed the memo, US crypto export laws were relaxed back in 1996, over a decade ago. So far as I know, there are no government laws against shipping secure computers, except perhaps to countries like North Korea.

Not that this has anything at all to do with the relevance of this discussion.

gat3way • January 11, 2010 3:40 PM

bash$ wget http://www.schneier.com/blog/archives/2010/01/768-bit_number.html -O out;grep NSA out
–2010-01-11 23:38:31– http://www.schneier.com/blog/archives/2010/01/768-bit_number.html
Resolving http://www.schneier.com... 204.11.246.48
Connecting to http://www.schneier.com|204.11.246.48|:80… connected.
HTTP request sent, awaiting response… 200 OK
Length: 26449 (26K) [text/html]
Saving to: `out’

100%[==================================================================>] 26,449 37.5K/s in 0.7s

2010-01-11 23:38:32 (37.5 KB/s) – `out’ saved [26449/26449]

bash$ grep NSA out
bash$

I can’t believe that – 15 comments, still no “NSA” mentioned 🙁

Nick P • January 11, 2010 4:51 PM

@ jgreco

In case you missed the memo, the FBI and NSA have had little problems intercepting the likes of PGP and stuff. How? As PackageBlue said, COTS computers are insecure as crap. Whether processor errata, evil maid attacks, buggy drivers w/ kernel access, keylogger-bait OS, or buggy software, security is only as strong as the weakest link and good crypto on a modern PC is like a steel link on a chain made of rusty iron and balsawood.

Secure crypto on a PC is a sick joke. It’s why I tell all my clients to use small dedicated & hardened appliances for digital signing, VPN or unbypassable firewalls. If the “secure” software runs on a regular COTS OS in normal usage scenario, then it isn’t “secure.” This is why it is rated EAL4: “certified insecure.” (Johnathan Shapiro)

gat3way • January 11, 2010 5:16 PM

🙂

thanks but it’s too late already – it has been mentioned, the comment right above yours 🙂

jgreco • January 11, 2010 10:52 PM

@Nick Pat

My main point is that this tangent seems rather offtopic and trollish. The importance of this topic is not dimished the low quality of COTS systems, and the suggestion that good crypto is worthless because of government mandates is terribly naive.

Nick P • January 11, 2010 11:48 PM

@ jgreco

I agree that crypto isn’t totally worthless because of government mandates. However, it is of little use against sophisticated attackers on an extremely insecure system that is easily keylogged or otherwise hijacked by one’s enemies. This is why the importance of this topic is diminished by the low quality of COTS systems. The security claims of crypto products usually assume certain security properties of the OS’s or hardware they run on. If those security properties aren’t true, then the crypto scheme’s security properties no longer hold. Sad thing about math or logic is that your conclusions are only as strong as your premises.

I can make a system be secure with only 128-bit RSA if its built on a secure foundation that covers for its weaknesses. This would be impractical, but it illustrates the point. A house is only as sturdy as its foundation. My original point was clients were using better crypto algorithms (bigger keys) and stronger foundations (secure OS’s), so this news means nothing to us and it means nothing to many users because they are usually compromised in dozens of other ways (e.g. drive-by-download). If I key-log you via a drive-by-download infection, I don’t care if you have 768-bit RSA or 4,096-bit RSA: I’m still in control. This is why the tangent matters. As Bruce points out, crypto is usually the strongest link in the chain: it’s the other spots where they usually get you. Modern crypto is mostly good enough. It’s the OS’s and productivity apps that need work.

synonym • January 12, 2010 4:53 AM

I think most people miss that the paper doesn’t make a prediction about the capacity of other folks, it just says in a geekish and more or less coordinated effort it took us 6 monts of polynominal selection, 19 monts of sieving with the number field sieve and a few days of matrix-calculations to break the original RSA768 modulus.

The conclusion is, that with a more organized effort (because this is all academic) it is possible to break the same modulus in a shorter time frame. It is a good benchmark for RSA wich solves the key exchange problem for more than 30 years now.

The keysize is left as an excercise for the reader and depends on what you RSA for.

Lenstra encourages us to use 1024 or 2048 bit RSA keys, 1024 and 2048 bit RSA keys are pretty common with PGP since 1999.

This may be of intrest too, enjoy:
https://documents.epfl.ch/users/l/le/lenstra/public/papers/rsa768.txt

Clive Robinson • January 12, 2010 1:41 PM

@ uk-visa,

“namely, encryption alone will not secure data, warns expert after code cracks”

I’ve not read the article you link to but the statment above is quite correct.

Irespective of the strength of encryption it is just but one tiny part of the whole. And as Bruce has noted “encryption is one link in the chain”, “it might be the strongest link” but then a chain rarely breaks at the strongest link but the weakest.

If you think about what encryption realy is (utimatly security through obscurity 😉 you could regard it as a safe around the information.

Now for the safe to work it needs a “key” which raises issues of who has the key when and for what reason etc etc and it all ttends to fall under the title of “key managment”. Arguably this is a much harder problem than encryption as while encryption scales easily key managment most certainly does not scale at all for very many reasons. It is hopefully the subject cryptographers are going to get on with after the NIST hash playoff is out of the way.

Then there is the question of the information to go into the safe… The first being how was it produced in it’s final form prior to encryption this then follows backwards to the original source. At any point along this walk the information could be compramised due to copies of it in existance in unprotected areas. For instance it could be in a draft form that has not been securly destroyed.

At the other end when the document is taken out of the encryption safe to be used there is then again the question of copies etc.

The other problem with encryption is how you use it. AES for instance can be used in many modes some are very much less suitable for some applications (HD storage) than others (comms).

Clive Robinson • January 12, 2010 2:09 PM

@ uk-visa,
@ uk-visa,

I’ve looked at the page your link points to.

Well what can I say first off,

“The days of relying on encryption alone as a means of defending private data are now drawing to a close,” said Andy Cordial, managing director of storage company Origin.

I don’t know what he is talking about here it’s no clear and as a statment has no basis by which you can tell (but realisticaly all forms of data hiding that have any level of security use encryption of one form or another).

The page goes on to say,

‘”The use of a PIN-based protection – and even biometric authentication – alongside a fully encrypted drive is now the logical choice for companies wanting to protect sensitive data from prying eyes,” said a statement from Origin. “Since biometric-enhanced encryption systems are still relatively expensive, the logical choice is a PIN/password-enhanced external encrypted drive.”‘

Oh dear it looks like the person at Origin is trying to flog their system by FUD.

Neither a PIN nor Bio-metric can protect data, all they can do is produce a key (or keep one minimaly locked). If you look at the amount of entropy in a standard 4 digit PIN (10bits) or fingerprint (~20bits in low cost systems) then look at the key size of AES and remember each bit doubles the brut force effort. You will see that there is quite a disparity of work effort required.

The artical goes on to say,

“At the very least, this will allow the CEO or chairman to put his/her hand on heart and say the company’s data is secure whilst in transit from one place to another,” said Cordial. “That’s a claim you can’t truly make any more with single factor encryption.”

Hmm you get the same smell in a stable full of horses.

Either Mr Cordial does not have a clue or the person selecting and using his comments is either doing a stich up or does not have a clue.

Untill further information is available I for one will give Origin quite a wide berth…

gat3way • January 14, 2010 6:59 AM

The entropy of a 4-digit PIN is higher than 10 bits, it’s about 14 bits actually. 2^10 = 1024, while all possible PIN codes are 10000. Not that it makes a big difference though.

Paeniteo • January 14, 2010 10:47 AM

@Clive: “If you look at the amount of entropy in a standard 4 digit PIN (10bits) or fingerprint (~20bits in low cost systems) then look at the key size of AES and remember each bit doubles the brut force effort. You will see that there is quite a disparity of work effort required.”

The low entropy of a PIN doesn’t matter if the PIN only serves to unlock a high-entropy encryption key and the device somehow limits brute-force attacks.
Such approaches may well be stronger in practice than deriving encryption keys from passwords.

jgreco • January 14, 2010 10:58 AM

@gat3way at January 14, 2010 6:59 AM

You have to take into account how people pick their PINs too. I’d be willing to bet a very large percentage of them are in the range of 1940-2000.

David Cornwell • January 14, 2010 12:48 PM

While factoring a 768-bit modulus is a world class piece of work for sure, factoring a 1024 bit modulus would be truly amazing and would get a lot more press. Who is going to take on this problem? It would be great if someone could create a new method of factoring that was faster than the NFS.

Nick P • January 15, 2010 2:47 AM

@ David Cornwell

Actually, that wouldn’t be great. I’d be up all night switching people over to the recent quantum-safe lattice methods until I could find a better solution. And I wouldn’t get overtime. :0

jacob • January 16, 2010 6:58 AM

ok. given that these type of exercises are just that, exercises. The NSA or other organizations can crack anything they care to.Given, that the other parts of crypto setup is easier to break. Keylogger, ISP logs, etc. Personally, there is not much to interest any organization. I’m pretty boring.

As an intellectual excessive exercise I find this interesting. I will and do encrypt Hd when I cross borders and VPN information, transfer files. I do not want some hourly wage employee to see my business info or personnel access to my disney vacation photos. It is none of their business.

What bothers me is the info gathering and it just sits there for others to gather and use for whatever purpose they see fit.

Question??? Wouldn’t an OS represent a plaintext attack on any crypto attack? Just curious.
thanks,
Jacob

Nick P • January 16, 2010 10:01 AM

@ jacob

Nah, they aren’t exercises: they expose weaknesses in various systems and help us understand how to secure them. And no, the NSA can’t just crack anything or at least not do so cheaply or quickly. For instance, during evaluation for Type 1 or EAL7 products, the NSA assumes its enemies will be similarly skilled and tries to prevent an attack. This means a Type 1 device [without backdoor…] would likely resist most attacks by NSA.

The main issue is the threat model. One needs to determine if the attack will be casual or targeted, then the strength of the attacker, and then enumerate methods. Attack methods are usually similar for online systems. There exists a technique to defeat each method. It’s just about cost vs. risk. Accordingly, I know for a fact NSA can’t easily break some of my systems because I have sophisticated snoops in my threat model. I lost fancy crap like PHP in the process, but the tradeoff was OK for me in that particular case. Other systems would stomp the best hackers but be easy meat for NSA or black bag jobs. All about the threat model, value of assets, & level of risk you accept.

And, btw, hitting the OS would be a plaintext attack of sorts. More generally, it’s an attack on the assumptions of the security protocol: it assumes the underlying system is secure, which isn’t usually a safe assumption. Outside of resource-constrained, tiny RTOS’s, it’s hard to ever be sure about that one. For an example of a secure OS/platform, look up Green Hill’s Integrity-178B, GEMSOS by Aesec, or a paper on LOCK project. There are others, but these have online papers and have passed rigorous evaluations (LOCK was partial).

Tom Corwine • January 26, 2010 12:02 PM

I just renewed a SSL certificate, and the CA would only accept a request generated from a 2048 bit RSA keypair. Last year they were accepting (and even recommending) 1024 bits.

HJohn • January 26, 2010 12:36 PM

@Tom Corwine: “I just renewed a SSL certificate, and the CA would only accept a request generated from a 2048 bit RSA keypair. Last year they were accepting (and even recommending) 1024 bits.”

It’s not uncommon for entities to focus on strengthening the link in their chain that is already the strongest. Something about encryption, possibly that it can be precisely measured numerically in terms of bits, motivates people who otherwise neglect more mundane (and important) areas.

Yoron • March 27, 2010 3:53 PM

well, looking at it that way ‘blue’ the only thing you need to do to be secure is to have a laptop near your system not connected in any way.

Write your message there, read your message there. And allow only for ‘ansi text’ messages on the medium with which you move your text with.

It’s a little like those ‘word viruses’. You only need to tell your computer to open them with ‘wordpad’ to avoid the infection, that as that one won’t support word basic, if I remember right.

A lot of things can be kept simple, if you just think it through.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.