How long to break a 512 bit RSA key?
Hyper4S
I was wondering how secure 512 bit RSA keys are, and some "googling" showed
me that "they can be broken".
Moreover, it seems that this can be done rather *easily*, in a *reasonable*
amount of time.
But I couldnt figure out what's exactly meant by that "easily" and
"reasonable".
So, what would it take to break a 512 bit RSA key? A massive network of
high-end computers? A simple desktop pc? And how long would it take? 10
seconds? More than a year?
Of course the time needed depends on the computerpower used...
So more specific:
How long would it take to break a 512 bit RSA key on, say, a desktop pc with
1 GB RAM and 3 Mhz processor speed?
Could you refer to the words of some authority in this field, who has
"proven" this? Some founded references?
Many thanks,
Kristof
Mxsmanic
> I was wondering how secure 512 bit RSA keys are, and some "googling" showed
> me that "they can be broken".
All RSA keys can be broken, in time. "Broken" means that the key can be
discovered in a way that is more efficient than an exhaustive key
search; in the case of RSA, the method used is factorization, which is
considerably faster than a key search.
> Moreover, it seems that this can be done rather *easily*, in a *reasonable*
> amount of time.
It depends on what you consider easy.
> But I couldnt figure out what's exactly meant by that "easily" and
> "reasonable".
Well, cracking a 512-bit key currently requires executing about
250,000,000,000,000,000 machine instructions, using the most efficient
algorithms. Divide that number by the speed of the computer(s) your
adversary has available to determine how long a 512-bit key will hold
out against cracking efforts.
When RSA's 512-bit public challenge key was cracked in 1999, it required
almost four months and just under 300 computers. It could be done much
faster today, but it still requires a lot of work. For example, with a
PC at 3.3 GHz, for example, it would take about 2.5 years of continuous
work to crack a 512-bit key. That's certainly technically feasible, but
it's not very convenient, so the real question is whether or not your
adversary is prepared to invest that much machine time in cracking your
512-bit key. If he is, your key may be unsafe (unless you only need
secrecy for a period shorter than the period required to crack the key);
if he isn't, you're completely safe.
> So, what would it take to break a 512 bit RSA key? A massive network of
> high-end computers? A simple desktop pc? And how long would it take? 10
> seconds? More than a year?
See above. With the fastest PC available, probably 2-3 years of
continuous operation. With a network of such PCs, much less time, of
course. The computer doesn't have to be high end; any computer will do.
However, it's obviously preferable that the computer be as fast as
possible.
> How long would it take to break a 512 bit RSA key on, say, a desktop pc with
> 1 GB RAM and 3 Mhz processor speed?
Almost 3000 years ... if you really meant 3 MHz (there haven't been any
PCs that slow around in twenty years, though). If you meant 3
_gigahertz_, then it would be 1000 times faster ... which means about
three years.
> Could you refer to the words of some authority in this field, who has
> "proven" this? Some founded references?
See http://www.rsasecurity.com/rsalabs/challenges/factoring/rsa155.html,
which discusses the cracking of the 512-bit key.
Cracking a 1024-bit key, incidentally, requires about 230 times longer.
No one has publicly done it yet (as far as I can recall).
--
Transpose hotmail and mxsmanic in my e-mail address to reach me directly.
Stefan Seiffarth
with
> > 1 GB RAM and 3 Mhz processor speed?
>
Actually Memory is a fairly huge issue with the Block Lanczos and square
root steps in the GNFS algorithm, if i remember it took more than 2GB memory
in the previous 512bit factorization, Block Lanczos took like 10 days on a
Cray C916 and sqrt took about 2 days on some huge SGI Origin. Both steps
should be considerably slower with less memory.
http://homepages.cwi.nl/~walter/papers/CDL00.pdf
contains more detailed information.
Phil Carmody
> Hello,
>
> I was wondering how secure 512 bit RSA keys are, and some "googling" showed
> me that "they can be broken".
> Moreover, it seems that this can be done rather *easily*, in a *reasonable*
> amount of time.
>
> But I couldnt figure out what's exactly meant by that "easily" and
> "reasonable".
>
> So, what would it take to break a 512 bit RSA key? A massive network of
> high-end computers? A simple desktop pc? And how long would it take? 10
> seconds? More than a year?
>
> Of course the time needed depends on the computerpower used...
> So more specific:
> How long would it take to break a 512 bit RSA key on, say, a desktop pc with
> 1 GB RAM and 3 Mhz processor speed?
Longer than the capacitors on the motherboard would last.
Individuals aren't the threat. Basically, if you're a company with a
HP superdome or similar then you can probably crack 512-bit keys in
less than a year. Looking at the top500 list you can only conclude
that if companies and universities were prepared to dedicate computer
resourses to GNFS sieving, there would be hundreds of institutions
which could perform the task. And if hundreds can be done per year,
that means that one can be done per day (throughput, not latency).
(And when I say individuals aren't the threat, I mean individuals.
NFSnet _isn't_ an individual.)
> Could you refer to the words of some authority in this field, who has
> "proven" this? Some founded references?
Look at the effort that was required to crack similarly-sized
numbers in the past. That's about as good an estimate as
you'll find.
Phil
--
Unpatched IE vulnerability: Security zone transfer
Description: Automatically opening IE + Executing attachments
Published: March 22nd 2002
Reference: http://security.greymagic.com/adv/gm002-ie/
Roger Schlafly
> Individuals aren't the threat. Basically, if you're a company with a
> HP superdome or similar then you can probably crack 512-bit keys in
> less than a year.
IOW, 512-bit RSA is still fine for ordinary purposes, such as
encrypting love letters to your mistress or encrypting your credit
card number.
d...@florence.edu
wrote:
>Hello,
>
>I was wondering how secure 512 bit RSA keys are, and some "googling" showed
>me that "they can be broken".
>Moreover, it seems that this can be done rather *easily*, in a *reasonable*
>amount of time.
>
>But I couldnt figure out what's exactly meant by that "easily" and
>"reasonable".
>
>So, what would it take to break a 512 bit RSA key? A massive network of
>high-end computers? A simple desktop pc? And how long would it take? 10
>seconds? More than a year?
>
>Of course the time needed depends on the computerpower used...
>So more specific:
>How long would it take to break a 512 bit RSA key on, say, a desktop pc with
>1 GB RAM and 3 Mhz processor speed?
>
Best use for a 3 MHZ computer would be to reverse engineer the RSA
code to gain key parameter information. "nobody will ever need over
640K of memory" to do that. :-)
Hyper4S
you guys helped me a lot already, but I'm still stuck with a few questions
:-)
In the paper Stefan Seiffarth mentions
(http://homepages.cwi.nl/~walter/papers/CDL00.pdf), one says:
"Based on our experience with factoring large numbers we estimate that
within three years the algorithmic and computer technology which we used to
factor RSA-155 will be widespread, at least in the scientific world, so that
by then 512-bit RSA keys will be certainly not safe any more. This makes
these keys useless for authentication or for the protection of data required
to be secure for a period longer than a few days"
The paper is from 2000, I think, so the paper is actually posing that in
2003 ("within three years") a 512-bit key can be factored in a few days.
However, from the other replies on this post, I got the impression that even
company or university networks would need a year to do this (I'm mainly
refering to Phil Carmodys reply: "Basically, if you're a company with a HP
superdome or similar, then you can probably crack 52-bit keys in less than a
year").
Any comments on this?
And I was also wondering if the Number Field Sieve(NFS) factoring method (as
used in the paper), is still the best known method for factoring RSA. Or
have better methods been developped in those 3 years?
In the paper, with the NFS method, factoring RSA-155 would take 8400 MIPS
year (2,65*10^17 machine instructions), which is roughly the same as
Mxsmanic posted ("250 000 000 000 000 machine instructions, using the most
efficient algorithms")
So it seems that NFS is still the "most efficient algorithm"?
Any comments on this will be greatly appreciated ;-)
Grtz,
Kristof
"Stefan Seiffarth" <seif...@in.tum.de> wrote in message
news:bnthk5$d6q$03$1...@news.t-online.com...
Mxsmanic
> The paper is from 2000, I think, so the paper is actually posing that in
> 2003 ("within three years") a 512-bit key can be factored in a few days.
It is very optimistic. That is true if you can harness the horsepower
of hundreds or thousands of ordinary, high-end PCs to work on the
problem. It is _not_ true if you have only a single high-end PC. In
this latter case, you are still looking at 2-3 years to crack the key.
It's important to distinguish among what _can_ be done, what is
_practical_ to do, and what _will_ be done. A 512-bit key _can_ be
broken. Breaking a 512-key is _not_ very practical. Actually breaking
such keys in practice is _highly unlikely_, because the resources
required are rarely justified by the potential gain.
Sure, a network of PCs can break a key in a few days, or a week. But
they can only do one key at a time that way. Which key will it be?
Yours? I don't think so. It's a lot more likely that an individual
with a single PC would try to break your key, since that doesn't involve
tying up so many resources. But a single PC would take years to break
the key, so that isn't likely, either.
Remember: Almost everything you have of value is protected only by your
handwritten signature, not your RSA key. A handwritten signature is so
trivially easy to forge that it scarcely merits the term of forgery.
Despite this, how many adversaries are forging your signature? Now, how
much do you have that is protected by your RSA key (anything, really?),
and how hard is it to crack an RSA key? It's easy to see that nobody is
going to try to crack your key when other, better ways of achieving
their objectives exist.
> However, from the other replies on this post, I got the impression that even
> company or university networks would need a year to do this (I'm mainly
> refering to Phil Carmodys reply: "Basically, if you're a company with a HP
> superdome or similar, then you can probably crack 52-bit keys in less than a
> year").
>
> Any comments on this?
No doubt true, but a year of solid machine time is a lot of resources.
Why would anyone bother?
Finally, if you are worried about a 512-bit key, use a 1024-bit,
2048-bit, or 4096-bit key. Nobody is going to be cracking any of these
any time soon, and most computers are so fast these days that using a
4096-bit key is scarcely any slower than using a 512-bit key.
d...@florence.edu
wrote:
>Hi,
>
>you guys helped me a lot already, but I'm still stuck with a few questions
>:-)
>
>
>The paper is from 2000, I think, so the paper is actually posing that in
>2003 ("within three years") a 512-bit key can be factored in a few days.
>
>However, from the other replies on this post, I got the impression that even
>company or university networks would need a year to do this
How long did it take Bletchley Park to break the German Enigma? Could
this feat have been predicted in 1921? The German Enigma protected
field information that could have life or death consequences, RSA only
protects redundantly insured financial transactions so who really
cares how strong it is?
Andrew Swallow
news:hle7qv49r8p0q86s8...@4ax.com...
> Hyper4S writes:
>
> > The paper is from 2000, I think, so the paper is actually posing that in
> > 2003 ("within three years") a 512-bit key can be factored in a few days.
>
> It is very optimistic. That is true if you can harness the horsepower
> of hundreds or thousands of ordinary, high-end PCs to work on the
> problem. It is _not_ true if you have only a single high-end PC. In
> this latter case, you are still looking at 2-3 years to crack the key.
>
computers will do. Take 1,000 of them and the 512-bit
key may be broken in a day.
So if the information is worth more than £600,000
breaking the key variable protecting it can be profitable.
If the villains can repeat this 100 times the capital cost
becomes £6,000 (+ wages + electricity). Many readers
of this news group own more than £6,000 worth of
shares. Many companies have trade secrets worth
more than £10,000. Government departments frequently
negotiate contracts worth more than £1,000,000. So
a 1% price difference would pay for the SIGINT.
Andrew Swallow
Paul Rubin
> The paper is from 2000, I think, so the paper is actually posing that in
> 2003 ("within three years") a 512-bit key can be factored in a few days.
>
> However, from the other replies on this post, I got the impression that even
> company or university networks would need a year to do this
No. Some Swedish students broke a 512 bit RSA number in a few weeks
(maybe a month or so) on a network of workstations at a university for
the Simon Singh Cipher Challenge. Doing it on a single machine would
take a lot longer, of course.
> (I'm mainly refering to Phil Carmodys reply: "Basically, if you're a
> company with a HP superdome or similar, then you can probably crack
> 52-bit keys in less than a year").
>
> Any comments on this?
Huh? Yeah, I guess. That has to mean 52-bit symmetric keys, not RSA.
Note that Deep Crack cost around $60K not counting NRE which has
already been done and published. So for the same amount you could
build your own Deep Crack copy and break 56-bit DES keys in a few
weeks (but you'd have to design entirely new hardware for any cipher
other than DES).
> And I was also wondering if the Number Field Sieve(NFS) factoring method (as
> used in the paper), is still the best known method for factoring RSA. Or
> have better methods been developped in those 3 years?
NFS is still the best publicly known algorithm. Some very interesting
optimizations for it have been proposed over the past few years but
have not yet been shown to be practical, at least in the unclassified
world.
> In the paper, with the NFS method, factoring RSA-155 would take 8400 MIPS
> year (2,65*10^17 machine instructions), which is roughly the same as
> Mxsmanic posted ("250 000 000 000 000 machine instructions, using the most
> efficient algorithms")
> So it seems that NFS is still the "most efficient algorithm"?
Yes. However, NFS's efficiency depends more on memory capacity and
access speed (it needs tons of low latency memory) than just cpu
cycles.
Mxsmanic
> We do not need complex peripherals so 600 UK pound
> computers will do. Take 1,000 of them and the 512-bit
> key may be broken in a day.
You may be missing my point. A single £600 computer costs £600, but
1000 of them costs £600,000--quite a sum for cracking a single key. The
former is affordable for just about any adversary; the latter is not
(and may not be justifiable even if it is affordable).
> So if the information is worth more than £600,000
> breaking the key variable protecting it can be profitable.
But the information usually is not. Are you protecting £600,000 worth
of assets with a 512-bit key? How much are you protecting with your
easily-forged handwritten signature?
> If the villains can repeat this 100 times the capital cost
> becomes £6,000 (+ wages + electricity).
They can obtain similar gains with just a ball-point pen, by forging
signatures.
Mxsmanic
> How long did it take Bletchley Park to break the German Enigma?
With or without counting the efforts of the Polish codebreakers who got
them started, or the U.S. codebreakers who actually built machines to
crack the codes on a regular basis?
> The German Enigma protected field information that could
> have life or death consequences, RSA only protects redundantly
> insured financial transactions so who really cares how strong it is?
RSA can protect anything, but in most cases I daresay that it is
protecting information worth far less than the cost of breaking it would
be. My RSA key is 4096 bits long, and while I realize that it might be
breakable, I'm confident that it isn't breakable at any cost that would
make the crack worthwhile to any of my adversaries (such as they are).
Paul Rubin
> We do not need complex peripherals so 600 UK pound
> computers will do. Take 1,000 of them and the 512-bit
> key may be broken in a day.
What makes you think that's true? I'm skeptical.
Andrew Swallow
news:7xfzh7p...@ruckus.brouhaha.com...
You do not need colour screens or DVD players. Just CPUs,
ram and power supplies. For calculations lasting all day
slow (cheap) communications will do. Such machines
have already been built.
From earlier parts of this thread a 512-bit key variable can
be broken in about 3 years.
If 1 machine takes 3 years then 3 * 365 = 1095 can do it
in a day. You just need parts of the calculation to be
independent.
Andrew Swallow
Paul Rubin
> From earlier parts of this thread a 512-bit key variable can
> be broken in about 3 years.
> If 1 machine takes 3 years then 3 * 365 = 1095 can do it
> in a day. You just need parts of the calculation to be
> independent.
What makes you think the parts of the calculation can be made
independent? Does that include the linear algebra phase?
Bob Silverman
What is it about this subject that compels
people (who generally don't know very
much about a subject) to dispense
misinformation?
Please explain how you propose to
break a 512-bit key in a day. The
sieving can be done in a day with enough
computers. How do you propose to
solve the matrix? RSA-512 took ~10 days
on a large CRAY to solve the matrix.
Current parallel implementations of Block
Lanczos have similar performance. And
the linear algebra does NOT scale.
"You can lead a horse's ass to knowledge, but you can't make him think."
Paul Rubin
> Please explain how you propose to break a 512-bit key in a day. The
> sieving can be done in a day with enough computers. How do you
> propose to solve the matrix? RSA-512 took ~10 days on a large CRAY
> to solve the matrix. Current parallel implementations of Block
> Lanczos have similar performance. And the linear algebra does NOT
> scale.
From http://codebook.org/node52.html
The program we used for this was optimized for running on vector
computers, which is what CWI used for their record factorization last
year; it had taken them 10 days to solve a slightly smaller equation
system on a 16-processor Cray C90. We started to rewrite this program
so that it would run better on the hardware available for us, and
after a few weeks of hard work, we had a version of the program that
used both processors of the computer, and would have to run for 37
days.
At this point, we contacted Compaq to get some help for the
computation, since we thought this was great opportunity to show how
powerful the Alpha is for scientific computations. Compaq generously
let us use one of their quad processor ES40 systems. The total
running time on this machine was 13 days, which is almost as good as
the 16-processor Cray. Thanks to the Alpha processor, we have thus
been able to show that it is possible to factorize 155-digit numbers
without using expensive vector computers.
So an improvement in feasibility over using a Cray, but still probably
out of reach of any "normal" PC, even a multiprocessor Opteron or Itanium.
Hyper4S
He said: "Basically, if you're a company with a
HP superdome or similar then you can probably crack 512-bit keys in
less than a year."
So its about 512-bit RSA keys, not about 52-bit symmetric keys...
My fault,
Kristof
"Paul Rubin" <http://phr...@NOSPAM.invalid> wrote in message
news:7xr80s6...@ruckus.brouhaha.com...
> "Hyper4S" <Hyp...@hotmail.com> writes:
*snip*
> > (I'm mainly refering to Phil Carmodys reply: "Basically, if you're a
> > company with a HP superdome or similar, then you can probably crack
> > 52-bit keys in less than a year").
> >
> > Any comments on this?
>
> Huh? Yeah, I guess. That has to mean 52-bit symmetric keys, not RSA.
> Note that Deep Crack cost around $60K not counting NRE which has
> already been done and published. So for the same amount you could
> build your own Deep Crack copy and break 56-bit DES keys in a few
> weeks (but you'd have to design entirely new hardware for any cipher
> other than DES).
>
*snip*
Hyper4S
I think I better stop posting :-)
Thanks a lot!
Kristof
"Hyper4S" <Hyp...@hotmail.com> wrote in message
news:Lr6pb.120017$hA6.5...@phobos.telenet-ops.be...
Tom St Denis
"Bob Silverman" <pubkey...@aol.comstuff> wrote in message
news:20031101213753...@mb-m10.aol.com...
> This really gets tiresome.
>
> What is it about this subject that compels
> people (who generally don't know very
> much about a subject) to dispense
> misinformation?
>
> Please explain how you propose to
> break a 512-bit key in a day. The
> sieving can be done in a day with enough
> computers. How do you propose to
> solve the matrix? RSA-512 took ~10 days
> on a large CRAY to solve the matrix.
> Current parallel implementations of Block
> Lanczos have similar performance. And
> the linear algebra does NOT scale.
You could pipeline it.... :-) e.g. while you are sieving for other
composites you do the matrix step for another. Still wouldn't hit one day
but you could probably hit lower than 10 days each.
hehehehe....
Ok I'll shutup now.
Tom
d...@florence.edu
wrote:
>d...@Florence.edu writes:
>
>> How long did it take Bletchley Park to break the German Enigma?
>
>With or without counting the efforts of the Polish codebreakers who got
>them started, or the U.S. codebreakers who actually built machines to
>crack the codes on a regular basis?
>
After a brief search I have decided usenet is an entertaining but not
authoritative source for cryptographic information. Apparently the
first machine ciphers were introduced in the United States by Yardley
in the World War I era. More advanced machine ciphers such as the
Japanese "purple" cipher were broken later by A US cryptographer named
Friedman [SP?].
I notice Charles Babbage invented the Babbage engine in 1822 and
references to mechanical "scramblers" such as one designed by Tesla in
the late 1800's exist. Doesn't seem as though it should take almost
100 years to get from the Babbage engine to a cryptographic rotor
machine does it?
Bletchley Park supposedly broke the German Enigma pretty much
independently of US efforts according to some accounts I read.
Clearly machine ciphers developed over a long period of time and
perhaps there was more iclassified information available to Bletchley
than the popular media accounts claim. Could take me a while to read
between the lines.
Paul Rubin
> After a brief search I have decided usenet is an entertaining but not
> authoritative source for cryptographic information. Apparently the
> first machine ciphers were introduced in the United States by Yardley
> in the World War I era.
Actually try several hundred years earlier. See "The Codebreakers"
by David Kahn".
> More advanced machine ciphers such as the Japanese "purple" cipher
> were broken later by A US cryptographer named Friedman [SP?].
See "The American Magic" by Thomas Parrish, among others.
> Bletchley Park supposedly broke the German Enigma pretty much
> independently of US efforts according to some accounts I read.
Bletchley's work built on efforts by the Polish Cipher Bureau from
before the war broke out. See "Enigma" by Wladislaw Kozaczuk for the
most complete account. Parrish's "The American Magic" and "Battle of
Wits" by Stephen Budiansky also tell the story. The U.S.'s
contribution was to help stay on top of the grunt work of
cryptanalyzing mountains of German traffic, by manufacturing Bombes
(Enigma keysearch machines) on a larger scale than the war-torn
British industry could cope with, and by sending people to work at
Bletchley on decrypts. But the main theoretical breakthroughs
were by Polish and British workers.
> Clearly machine ciphers developed over a long period of time and
> perhaps there was more iclassified information available to
> Bletchley than the popular media accounts claim. Could take me a
> while to read between the lines.
See "Machine Cryptography" by Deavours and Kruh.
Nicol So
>"Bob Silverman" <pubkey...@aol.comstuff> wrote:
>
>> RSA-512 took ~10 days
>> on a large CRAY to solve the matrix.
>> Current parallel implementations of Block
>> Lanczos have similar performance. And
>> the linear algebra does NOT scale.
>
> You could pipeline it.... :-) e.g. while you are sieving for
> other composites you do the matrix step for another. Still
> wouldn't hit one day but you could probably hit lower than 10
> days each.
Pipelining improves throughput but not latency. How does it help with
the problem Bob Silverman pointed out?
--
Nicol So
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
Tom St Denis
"Nicol So" <anon...@no.spam.please> wrote in message
news:bo3dv5$em4$1...@bob.news.rcn.net...
> Tom St Denis wrote:
> >"Bob Silverman" <pubkey...@aol.comstuff> wrote:
> >
> >> RSA-512 took ~10 days
> >> on a large CRAY to solve the matrix.
> >> Current parallel implementations of Block
> >> Lanczos have similar performance. And
> >> the linear algebra does NOT scale.
> >
> > You could pipeline it.... :-) e.g. while you are sieving for
> > other composites you do the matrix step for another. Still
> > wouldn't hit one day but you could probably hit lower than 10
> > days each.
>
> Pipelining improves throughput but not latency. How does it help with
> the problem Bob Silverman pointed out?
It was a joke. Hence the :-)
Tom
John E. Hadstate
<d...@Florence.edu> wrote in message
news:i49aqv0nchf0pbv0f...@4ax.com...
>
> After a brief search I have decided usenet is an entertaining but not
> authoritative source for cryptographic information.
>
> references to mechanical "scramblers" such as one designed by Tesla in
> the late 1800's exist. Doesn't seem as though it should take almost
> 100 years to get from the Babbage engine to a cryptographic rotor
> machine does it?
>
Reading through the first half of Kahn shows over and over again the ebb and
flow of sophistication in cryptology. He has documented numerous examples
where stronger crypto systems were supplanted by weaker ones, sometimes when
the two were coincident in time.
The value of the Babbage engine to crypto per se, is more than a little
questionable. Babbage's major problem seems to have been that he never
finished anything. Then there were those minor problems, friction and
gravity, that helped insure that the Babbage engine would stay in the
closet.
In fact, the seeds of the rotor machine might be found in the 1817 Wadsworth
cryptograph. A device based on similar principles was demonstrated 50 years
later, in 1867 by Wheatstone (yes, the Bridge guy). In both cases, the
devices could be thought of as the analog precursors to Enigma in the same
way that slide rules were precursors to pocket calculators.
Phil Carmody
> "Hyper4S" <Hyp...@hotmail.com> writes:
> > The paper is from 2000, I think, so the paper is actually posing that in
> > 2003 ("within three years") a 512-bit key can be factored in a few days.
> >
> > However, from the other replies on this post, I got the impression that even
> > company or university networks would need a year to do this
>
> No. Some Swedish students broke a 512 bit RSA number in a few weeks
> (maybe a month or so) on a network of workstations at a university for
> the Simon Singh Cipher Challenge. Doing it on a single machine would
> take a lot longer, of course.
They weren't ordinary students (some were relative experts in the field
of implementing numeric computing), nor were they using ordinary software
(I believe they had access to CWI's reference implementation, which is
one of the most highly respected implementations, and is not freely
available), but I guess that the feat could have been (but wasn't)
performed on mostly ordinary machines (although as Bob S implies, the
final stage requires one big-grunt machine).
Phil
--
Unpatched IE vulnerability: DNSError folder disclosure
Description: Gaining access to local security zones
Reference: http://msgs.securepoint.com/cgi-bin/get/bugtraq0306/52.html
Cristiano
> Well, cracking a 512-bit key currently requires executing about
> 250,000,000,000,000,000 machine instructions, using the most efficient
> algorithms.
How have you got that number?
Cristiano
Mok-Kong Shen
Mxsmanic wrote:
>
> Hyper4S writes:
>
[snip]
> > How long would it take to break a 512 bit RSA key on, say, a desktop pc with
> > 1 GB RAM and 3 Mhz processor speed?
>
> Almost 3000 years ... if you really meant 3 MHz (there haven't been any
> PCs that slow around in twenty years, though). If you meant 3
> _gigahertz_, then it would be 1000 times faster ... which means about
> three years.
Of some interest in this connection may be that, as
mentioned by someone in a recent thread, there is a
new optical DSP that achieves a 1000 times faster speed
than comparable ones.
M. K. Shen
Mxsmanic
> How have you got that number?
From the formula given for the number of required operations for the
GNFS. Published reports of cracking efforts correlate well with this
number.
Paul Rubin
> > Well, cracking a 512-bit key currently requires executing about
> > 250,000,000,000,000,000 machine instructions, using the most efficient
> > algorithms.
>
> How have you got that number?
It needs more than that many of just any old machine instructions. An
awful lot of them have to be random memory accesses. I mean really
random, so that the cache performance of a typical PC would be blown
completely to hell. You can't simply take 1000 standard PC's of 1000
mips each and believe that you'll be finished in 250,000 seconds.
John M. Dlugosz
> "Phil Carmody" <thefatphi...@yahoo.co.uk> wrote
> > Individuals aren't the threat. Basically, if you're a company with a
> > HP superdome or similar then you can probably crack 512-bit keys in
> > less than a year.
>
> encrypting love letters to your mistress or encrypting your credit
> card number.
So where do you find a mistress who's geek enough to use PGP?
Mxsmanic
> It needs more than that many of just any old machine instructions. An
> awful lot of them have to be random memory accesses. I mean really
> random, so that the cache performance of a typical PC would be blown
> completely to hell. You can't simply take 1000 standard PC's of 1000
> mips each and believe that you'll be finished in 250,000 seconds.
I considered it a best-case estimate, but I doubt that it would be
achievable in practice without specialized hardware (no off-the-shelf PC
microprocessors or other general-purpose hardware).
Andrew Swallow
news:8765i26...@nonospaz.fatphil.org...
[snip]
> They weren't ordinary students (some were relative experts in the field
> of implementing numeric computing), nor were they using ordinary software
> (I believe they had access to CWI's reference implementation, which is
> one of the most highly respected implementations, and is not freely
> available), but I guess that the feat could have been (but wasn't)
> performed on mostly ordinary machines (although as Bob S implies, the
> final stage requires one big-grunt machine).
>
Any chance of a weird attack? For instance instead of
inverting the matrix solve the equations a variable at a
time?
This method was abandoned years ago because matrix
inversion required few calculations. However if the
variables can be solved individually each machine can
be given its own line to solve.
Andrew Swallow
Cristiano
> Cristiano writes:
>
>> How have you got that number?
>
> From the formula given for the number of required operations for the
> GNFS. Published reports of cracking efforts correlate well with this
> number.
Please, could you post that formula (or the link)?
Thank you
Cristiano
Phil Carmody
I too have wondered if massive parallelism could be the key, and
I've not yet been able to prove that it isn't possible.
I reckon that you definitely have to take an unpleasant Big-Oh hit.
However, with a problem size of n=10^6, anyone interested solely in
latency rather than throughput should be prepared to take a 10^3
slowdown if 10^4 machines could (in parallel) share the work.
(Although the 'cost' of the solution has increased massively).
Presently all targets that are feasible to attack (or that people are
currently actually atacking) seem to have a total cost so high that
finding one top end machine for the LA stage doesn't seem to be the
hardest part. Perhaps Paul L or others can correct me if I'm wrong,
but I think that all the volunteer sievers for NFSnet have a total
PC $ investment higher than the cost of the big box used for the
LA/Sqrt stage.
Phil
--
Unpatched IE vulnerability: WMP local file bounce
Description: Switching security zone, arbitrary command execution,
automatic email-borne command execution
Reference: http://www.ntbugtraq.com/default.asp?pid=36&sid=1&A2=ind0307&L=ntbugtraq&F=P&S=&P=6783
Exploit: http://www.malware.com/once.again!.html
Mxsmanic
> So where do you find a mistress who's geek enough to use PGP?
Lurking on this newsgroup, no doubt.
pley...@microsoft.com
> hardest part. Perhaps Paul L or others can correct me if I'm wrong,
> but I think that all the volunteer sievers for NFSnet have a total
> PC $ investment higher than the cost of the big box used for the
> LA/Sqrt stage.
Very, very much so.
The LA for NFSNET is run on a cluster of 16 dual-proc 1GHz PIII
machines fitted with 2G RAM, a scratch disk, a gigabit NIC and some
otherwise largely useless bits and pieces that came with the machines.
The software is Server 2003 running custom code under a free MPI
harness. I get the OS for free (surprise!) but my guess is that a
variety of other free-as-in-beer operating systems would do the job
too. Each node could be built for $2000 each or less, I guess, so
chalk up $32K there. I'm not sure how much a 24-port (16 for the
nodes, one for the uplink to the rest of the world) gigabit switch is
these days but assuming $3K makes for a tidy $35K for the whole
system.
The sqrt stage is run on my 2.53GHz P4 Dell desktop, a machine that is
an entirely ordinary PC. Each sqrt run takes a few hours or less, so
the computational cost is negligible in comparison with the LA which
takes a week or three on the entire cluster.
When not running the LA, the cluster itself performs sieving. As the
cluster does only a small fraction of the total sieving, and sieving
takes much longer than the LA, you can see the cost of the sievers
greatly outweighs the cost of the cluster.
Paul
--
The opinions expressed in this message | Hanging on in quiet desperation is
are my own personal views and do not | the English way.
reflect the official views of Microsoft | The time is gone, the song is over.
Corporation. Paul Leyland, pleyland@ | Thought I'd something more to say.
JohnTromaville
>I considered it a best-case estimate, but I doubt that it would be
>achievable in practice without specialized hardware (no off-the-shelf PC
>microprocessors or other general-purpose hardware).
To be honest to do any work like this - where you want a unit to do a specific
function rather than multiple ones using general purpose computers, uPs etc
would be crazy.
The cost of designing your own system would not be many more orders of
magnitude higher than the cost of programming a system of general purpose PCs
(and debugging it etc). and the cost of building the system to similar specs
would be far cheaper (especially if multiple systems were required).
A FSM built from decent RAM and latches will beat any desktop PC for a given
task... and iI bet it would be cheaper to build than buy and set up the PC.
Trom
Paul Rubin
> > IOW, 512-bit RSA is still fine for ordinary purposes, such as
> > encrypting love letters to your mistress or encrypting your credit
> > card number.
>
> So where do you find a mistress who's geek enough to use PGP?
You don't need PGP to use RSA. SSL also uses RSA.