Schneier on Security

That's a 1020 bit number. Very surprising.

Which raises the question: Is the writing on the wall for RSA in general?

Doesn't a >2048-bit public key become impractical in many protocols? DomainKeys and other schemes require distribution of public keys via DNS.

The patent uncertainly surrounding ECC are not insurmountable. Is NIST planning on any public-key standard revisions, such as the AES and SHS workshops?

A little too obscure for me Bruce, I'm not a cryptanalyst, but enlightening, I use RSA products at work, so this is nice to know

Thanks.

Well, my key is the largest available in non-modified GPG.

I'm fine except for the fact that the signature is extremely bulky. Adopting an even larger key would be serious trouble...
Maybe time has come to actually consider ECC? What do you think about it, Bruce?

FTA: "18 months of calculations that took over a half century of computer time. "

Any one knows what does "a half century of computer time" mean?

Ivan,

It means the number of computers used times the amount of time they were used equals 500 years.

It is poorly worded thus meaning nothing. In most cases, you would use something like that as a half-century of our reference computer time (eg. if one computer had done it versus a cluster.) However without the reference computer listed.. it is not very useful info.

Computer time is the amount of time the a programs is actually running on the processor. If a program is running on 10 processors simultaneously it can "do" 10 minutes of "computer time" in one real minute. But also a computer program does not normally spend all it's time "on" the processor. Most programs are running idle most of the time, waiting for something to do. So for example your music player uses 3% cpu power, that means it's only using 1.8 seconds of processor time per minute.

It is all a little bit more complicated than this, but this should give you a basic idea.

What key size do you use Bruce?

^ See for yourself:
http://geekz.co.uk/schneierfacts/fact/27

Although 1024 RSA might be for those that are as Bruce put's it "asleep", there are some engineering solutions that just do not have the space for many more bits.

So what does switching to Eliptic Curves get you (apart from problems with modular inversion and crypto coprocessors) ...

Supposedly the same strength as RSA but with one sixth the bits (or whatever other number is the latest quote today) oh and six times the speed.

However one thing that is known about these sorts of problems/solutions is that in general when a solution to one problem is found it can fairly quickly be reworked to other similar problems.

What has become clear is that although factoring was considered for many years to be a mathmatical backwater it's use in crypto re-vitalised the field. So if ECC becomes prevelant how long before it to becomes subject to the same scrutiny?

So the next question is how long before some maths undergraduate thinks hmmm and does something not too disimilar on other crypto systems?

Just an idel thought...

Bruce's key size does not matter :)

What matters is that most users will have to increase their keysizes pretty soon.

And using a key of 4096 bits HURTS.

So we will have to move towards ECC. And we better start moving NOW.

Any more info as to what special form the number was versus the standard ones?

I just created a 2048-bit RSA keypair with GNUpg, and the public key is 1677 bytes after being compressed with gzip (to remove the effects of base64). A binary sig made by the same key is 2978 bytes.

Ouch. That's unworkable for a lot of applications, be it DNS or doing signing of row data in any size of database.

@Ryan: An RSA signature is capped by the modulus N -- 2048 bits = 256 bytes.

The point is, unworkable or not. 1024 bits is not enough for a signature scheme that is suppose to produce certs that are valid for a decent amount of time. Period!

ECC is simply a patent minfield. Its just crazy what can be patented really (aka RSA). Futhermore its "incressed" security is not a proof. its just that we find it harder at *this* point working out discrete logs over Eliptic feilds. It could be just as easy as discrete logs over G_p for all we know.

You can use subgroups with a tradtional Discrete Log based scheme as another alternative.

But consider the application and the cost of an attack? what are the payoffs.

I have used 2048bit keys for a while now, and it really is not a problem. I know smart cards have issues. But then what do you want? True security? or a cheap system?

Genrally you can't have both.

Just work out what its worth. Don't spend $1000 to protect $10.

But if you want your certificate to be valid in 20 years time? You need big key sizes.

"A little too obscure for me Bruce, I'm not a cryptanalyst, but enlightening, I use RSA products at work, so this is nice to know."

And then there are those of you who complain that they want more cryptography posts.

@Bruce

* We probably find crypto stories more interesting than average.

* We want to know what the "Oracle" thinks of these problems.

* Those of us that advise others need to know strengths and weaknesses.

* Where else can we do such cutting edge nerdy stuff?

:-)

Where else can we do such cutting edge nerdy stuff?

LOL!

Steven, ivan, Bruce, et al:

My guess is that the 500 years of computing time is based on a P-90 computer. The GIMPS (Great Internet Mersenne Prime Search), has been searching for Mersenne primes (that is, of the form (2^^N)-1) since January 1996, when the P-90 was pretty much the typical/standard CPU in use. They use the P-90 as a measuring stick.
http://mersenne.org

According to the "Top Producers" list, at #2014, I've logged some 178 years of P-90 calculations since I started running their software on my machine(s) about 11 years ago. I was running a PII-166 when I started, switched to a PIII-1G about 6 years ago, and now have been running a a PIV-3.4G since about two years along with the still-running PIII-1G.

According to the updated-hourly Status Page http://www.mersenne.org/primenet/status.shtml the subset of slower machines, which are dedicated to factoring the non-primes Mersennes, performs some 64 years of P-90 factoring PER DAY.

So, this subset of slower machines could factor that 307 digit number in about 8 days.

Yes, I do have a 4096-bit PGP/GPG key.

Now I know why...

@Andy: I was also unsure as to why the GPG .sig is so large... I'm not familiar with all the metadata included with a GPG sig. I always thought it was just the key ID plus the signature in binary form.

We're trying to do some GPG code-signing in our version control system, and on our production servers, in order to detect tampering and provide tracability. This means signing many versions of 500K+ small files. I think I am going to be seriously studying all of the more esoteric GPG options.

half a century = 50 years.

I am curious to know whether any new factoring techniques were used or whether this feat was essentially due to the special structure of the number.

The current record is for RSA-200 in 2005, a 663 bit (=200 decimal digits) number. This took 18 months elapsed time on a cluster of eighty 2.2 Ghz Opteron computers, connected through a Gigabit network (in contrast RSA 158 took 3 months in 2002 with the same hardware). See http://www.cwi.nl/research/2005/24teRieleEs.pdf

Let us suppose that each additional bit requires the factoring time to increase by a factor of just 1.1 – I believe this is better than what can be achieved even with the best factoring methods. At a rough guide let’s suppose that we assume that we are calculating on the same setup as Jens Franke. In this case we would get:

704 bits 75 years
768 bits 33,000 years
896 bits 6.7 billion years
1024 bits 10^15 years
2048 bits 10^57 years

Of course there are likely to be big advances in computing power, and there may also be improvements in factoring methods, but I think these calculations show that we are still a long way from factoring 1024 bit RSA keys.

I'd post something but I don't want to look stupid.

Freddo: Actually, Thorsten Kleinjung, one of the authors, gave an estimate for the time needed to factor a random 700 bit number: Several months, not 75 years. But he thinks that it will take "many years" until RSA-1024 will be cracked. (From http://www.heise.de/newsticker/meldung/89996 or http://www1.uni-bonn.de/pressDB/jsp/pressemitteilungsdetails.jsp?detailjahr=2007&detail=160, both in German.)

Your assumption that the calculation time is exponential (with a factor of 1.1 per bit) is way to simple. To my knowledge, Franke and Kleinjung have published an asymptotic formula for the required time of at least one of the steps of their method, it was not exponential, but more complicated.

In his preprint "Cofactorisation strategies for the number field sieve and an estimate for the sieving step for factoring 1024-bit integers" (http://www.math.uni-bonn.de/people/thor/cof.ps), Kleinjung used a different method (not extrapolation of asymptotic formulae) to arrive at the following estimate:

12 million (!) PCs with 2.2GHz Athlon 64 CPU and 2 GB main memory would need less than one year to complete the sieving step for RSA-1024.

In contrast, the cost for the sieving step in the factorization which has been achieved now equalled only 100 such Athlon64 PCs running for a year. (Actually, on the calendar, it took 6 months, of 11 months altogether.) See a copy of the detailed announcement here: http://www.heise.de/newsticker/foren/go.shtml?read=1&msg_id=12799757&forum_id=117643">http://www.heise.de/newsticker/foren/go.shtml?read=1&msg_id=12799757&forum_id=117643)">http://www.heise.de/newsticker/foren/go.shtml?read=1&msg_id=12799757&forum_id=117643

Bruce,

Give me meat!

I'm with those who want more crypto posts. If I want fluff and fun, I'll head to slashdot. :-)

thanks,
Michael

Compare these time estimates (to factor n digit RSA numbers) with estimates of the past (I think 10000 of years for 300 digits was one). You need big margins with this sort of thing. We always get better and so far do better than we think we could.

In particular the GNS has *subexponetial* running time. That means you need to make numbers bigger than you perhaps think.

At anyrate, for most of us the weakness is keeping the secrect key secrect, so its probably not such a big deal. Unless you are a cert provider.

20-50 years is very very long time in computers. Its about how long we have had modern computers for comparason

Presumably 500 computing years -> 500 MIPS years. See http://en.wikipedia.org/wiki/MIPS-year

So 500 MIPS years -> 15,750 trillion instructions (Not that figure really helps...)

@hhh:
>12 million (!) PCs with 2.2GHz Athlon 64 CPU and 2 GB main memory would need less than one year to complete the sieving step for RSA-1024.

As far as I rememeber, sieving is only the first step. What about matrix reduction (or whatever proper name is) step ? It's tightly coupled and much harder to perform on PCs.

More details are provided at
http://www.ntt.co.jp/news/news07e/0705/070521a.html

> EDITED TO ADD (5/21): That's 1023 bits. (I should have said that.)

I cannot find the number which has been factored but:

- the smallest 307 digit number is 1017 bits
- the biggest 307 digit number is 1020 bits

ouah

(thx to the bc unix command)

From http://www.crypto-world.com/announcements/m1039.txt

we compute the 307 number digit:

11594205740725730643
69807148876894640753
89979170201772498686
83535388224838599667
56608000609540800517
94720539932612302048
74402860435302861914
10144093453512334712
73967988850226307575
28093791660285551055
00425810771176177610
09413797078797380618
70084377771868286808
89844712822002935201
80607475545154137071
1023817

in base 2 :

11010011010101100100
00001000010000100011
11110001000011001101
11110011110100001011
00001101011000001111
10011111011000011000
01111111101010100110
10001010011101101010
11111011101110011001
01011111101101101110
10110101000100000001
10101110001110000100
00010110110111111111
10111010101000010001
10000010001010100000
00010011110010000011
11100101100011111110
01110111010000111100
00101111001101110000
01000101010110000001
10000101010111001011
10101010000011110011
11001111110011001111
11010001001000010000
11101010110010000001
10001100010111011100
10100110110001010100
11110000101111100010
01100100100000011010
11010100100011011001
10111000111010100000
10011110101000000111
10001101101111001110
11010100001100010110
01111101110101011010
11111000001100100011
11101000111000101001
11100010011011110000
00011001111001001101
01101010011000100000
10111110010110100001
01010111111100100100
11110001011010101110
01001000100001010110
11010110111011100110
00110101010000011001
01000011111010010010
10000110000000011111
00111011101101111100
00011110011101100101
11010000011001001

=> 1017 bits

ouah

SETEC ASTRONOMY

Grrr.

Here's a tip. When posting 1017 character "words"
(a number in this case), do *something* to break
them into groups. Because, now, this page is
rendered as very wide, and all the paragraphs are
one line high, requiring ugly manual side scrolling
to read.

I've deliberately put line breaks in this post to let
others more easily read it.

(P.S. Not to mention that the 'post' and 'preview'
buttons are halfway across town from the text
entry box!!)

@Chris

I agree that's annoying, but it's really not his fault. The blog application should be able to render such unexpected things more gracefully.

@ouah

"- the biggest 307 digit number is 1020 bits"

Can I assume you are rounding?
I calculated the base 2 log of .999999999999E307 as
1019.8319251304202407961880648532

I incorrectly calculated the
1023.1538532253076031440583842826
bit value by starting with 9.999999999999E307.

Appologies to all blog readers and to Bruce.

As I understand it from http://www.heise.de/newsticker/meldung/89996, the factors of the 307 digit number in question had 80 and 227 digits respectively. Factoring should be much simpler when the sizes are so dissimilar. So perhaps their achievement is not such a big deal.

Or am I barking up the wrong tree again?

Also this was the cofactor of a Mersenne prime which apparently makes it easier too - how much easier?

@Freddo

Quite a lot easier. The point is not that 1024 keys can be factored today. But that they are *not* going to last long. So if it something that needs shelf life, you 2048 bit at a minium (like sig). For real certs (SSL is not really real with the current usage patterns) should really be using 4096.

For applications that use PC's there really is no reason not to use at least 2048 bit keys.

This goes for DL problem based security as well.

An announcement with a lot of detail in it was sent out to the NMBRTHRY mailing list yesterday:

http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0705&L=nmbrthry&T=0&P=1019

NFS consists of two parts - a sieving step and linear algebra. Sieving doesn't require anything special; the linear algebra in this case required four clusters, each of 36 contemporary CPUs (three used Pentium-D 3GHz and the fourth used Xeon 5150 2.66GHz), for about two months.

For a 768-bit RSA key, the sieving could be done without too much pain in a few months on a couple of thousand computers each with 512M of memory; and these could be distributed around the world.

The linear algebra phase would be actually difficult; if my extrapolations are correct (and they're from six data points some way below the required level, so not all that likely to be correct), the job would be about forty times harder, and the smallest system that could contribute (you have to be able to write down a matrix of about half a billion rows each with about 200 entries) would be a cluster with half a terabyte of total memory. Embarrassingly, the best-known algorithms only double in speed when you quadruple the number of computers used within your cluster, though with N whole clusters the 'block Wiedemann approach' does run about N times as fast.

If you had twenty clusters, each of 196 computers with 4GB each, you could do the job in a couple of months. I don't. The NTT research labs in Japan don't. EPFL in Switzerland doesn't. Cambridge University's high-performance compute facility is about half the desired size, and has the whole of Cambridge University clamouring to use it.

That's to handle a 768-bit RSA key. A 768-bit SNFS job is much easier - a couple of months on a couple of high-end Mac Pros with 4GB of memory would suffice.

For a 1024-bit RSA key, both steps are sufficiently difficult that they'd need to be done with custom-made chips rather than with desktop computers. Several academic groups have done designs (http://theory.csail.mit.edu/~tromer/papers/scalinear.pdf for the linear algebra step, http://eprint.iacr.org/2006/403.pdf for the sieving step), generally with constraints of the form that no chip in the system may be very much bigger than the largest chips even manufactured, and with unrealistically optimistic cost models; they tend to deduce that the cost of factorising one 1024-bit number a year is around a hundred million dollars.

@Freddo: there are methods which are good at finding 'small' factors; and one of these was applied to 2^1039-1/5080711. Quite comprehensively applied; they ran, in the idle time of what must have been most of the sufficiently-powerful machines at NTT, a quarter-million trials each of which took about two hours on an Athlon64 with 4GB of memory, for a total of about 125 computer-years.

This would have had a 95% chance of finding a 65-digit factor, a 50% chance of finding a 70-digit factor, a 10% chance of finding a 75-digit factor, and a 2% chance of finding the 80-digit factor that turned out to exist.

So, it's not that having factors of different sizes makes the job easier, it's that having a small (less than 70 digits) factor allows you to apply a different algorithm. Obviously, if the number turns out not to have a small factor, all the time you spent running the different algorithm is wasted.

@Ryan, ref DomainKeys you only need these to be valid for the expected delivery time of an email. So make a cron job and replace your DomainKeys every day or so. Maybe the DNS will need the current and previous DomainKeys for a clean transition. Once the break time for RSA gets close to this figure I'm sure DomainKeys will support another algorithm.

Thanks for posting the details Tom Womack, my guesses weren't way off, it turns out.

I dug out a GIMPS page that compared the times for a wide range of CPUs: the Pentium D 3GHz mentionned is the release, is roughly 118 times faster than the benchmark P90 that GIMPS uses.
http://www.mersenne.org/bench.htm

According to the link you provided, the calculation took 3 P4D-3GHz years. Or, 356 P90 years, or 5.6 GIMPS-factoring-machines-only days.

If the entire 'zombie army' of GIMPS computers, at nearly 74,000 machines, were set to work on the problem, the time required to factor this 307-digit number could be divided by 36 - 3 hours, 45 minutes.

Yup, 1024 isn't big enough.

The number factored is 2^1039-1, so it's actually 1039 bits long. A small factor was already known, but that doesn't help in this case (Special Number Field Sieve).

With Elliptic Curve Cryptogography; I'd prefer a key of 576 bits.

I have just factorised this number,
what does it mean??