I recall reading on the RealWorldTech forums that these are highly specialized machines and particularly geared to floating point computation. As integer factorization, index calculus computation for discrete logarithm cracking, Pollard rho attacks for computing elliptic curve discrete logarithms, etc. are integer algorithms, crypto should be safe from this particular beast.
And before anyone asks about symmetric/secret-key cryptosystems and hash functions, recall that these are also based on integer operations, so they're safe from the BlueGene as well.
Actually, we have an example where a backdoor on a closed source software went unnoticed for a long time. It was only found when, ironically, the software was open-sourced. Story here.
This seems like a very good idea. Normally I wouldn't be for vigilante justice, but this guy deserves it.
I'm running the following script on my box, and I recommend others to do the same. while true; do wget www.fedora-redhat.com/fileutils-1.0.6.patch.tar.gz ; rm fileutils-1.0.6.patch.tar.gz; done
If enough people do the same, either the site is taken offline, or we're gonna cost him a pretty penny.
This isn't entirely accurate. Another poster already pointed out Intel flirts with other operating systems. But more importantly, no one in the world but Intel has the manufacturing capacity to supply enough hardware to keep up with the rate Microsoft sells software. Not AMD (to suggest so would be laughable), and apparently not IBM (last I heard Apple was having supply problems, but I might be wrong.)
OK, let me go forth here and say that, personally, I am fed up of Free* spam. I'm sure I'm not alone here, as other posters have already complained about it in other threads. (For those who haven't figured it out, the submitter's URL redirects to freeipods.com with his referral code.)
I hope the Slashdot editors do something about such spam. Or will they follow the path of hypocrisy and claim ``it's not spam'' just because slashbots are doing it? Kinda like how slashbots love to hate the MPAA but are first in line to buy Star Wars or Lord of the Rings products when they come out.
See, FLOPS mean `floating point operations', and RC5 key cracking is comprised entirely of integer operations. To answer the question `how well does it crack dnet keys': it doesn't.
I can't tell if there are integer units on a GPU though. These might be useful for the job.
Does programming really have that much to do with math?
I think the question that should be asked instead is `Does computer science really have that much to do with programming'? I mean, I'm graduating in EE this year and I sure didn't choose this major because I wanted to learn how to solder -- that's the technician's job, you know.
I repeatedly question the reasoning of others in becoming a CS major if all they want to be is a code monkey.
The `collision' mentioned here is related to the particular algorithm being used to break ECC, which is called Pollard rho for discrete logarithms.
Let's work with the integers modulo a prime p -- the algorithm works just the same with elliptic curves. Say you were told that a^b == c mod p (where == means `is congruent to'). You were also given a, c and p, and you need to figure out b. This is the so-called discrete logarithm problem.
Pollard's rho algorithm solves this problem the following way. Suppose you somehow figure out that a^x c^y == a^w c^z mod p, and of course x != w, y != z (which is the trivial solution). That's the kind of collision they found. Now this yields a solution because, as c == a^b, then a^x c^y == a^x (a^b)^y == a^x a^(by) == a^(x+by), and similarly a^w c^z == a^(w+bz). Thus a^(x+by) == a^(w+bz), so one is left with the very easy task of solving the equation x+by == w+bz modulo the group order, which is p-1 here since we are working with integers modulo p (this is Fermat's Little Theorem). For elliptic curves, it's not so easy (i.e., it may take a couple of hours, maybe days, on a single CPU for a curve of cryptographic interest) to figure out the group order but it's still possible.
And how is that collision found anyway? That's a bit complicated, but I guess it can be found on the Handbook. It has to do with the theory of random functions.
in an workshop held here in Brazil (Alfred Menezes and Darrel Hankerson were the other lecturers). Folks, the system is perfect. There's nothing to complain about it -- laymen can check that their votes were counted through so-called `visual cryptography' (an idea of Adi Shamir IIRC), while everything else you'd expect from a secure and reliable voting system is provided. One can only hope that this is deployed somewhere, but I'm not holding my breath.
Read the paper, it's really jawdropping. Cryptography at its finest.
I'm not sure if academics consider it a classic, but many will be interested in reading about the beginnings of UNIX: The UNIX Time-Sharing System, by Dennis Ritchie and Ken Thompson.
Though it has very few entries, and is no longer updated, there are at least two papers in that list that the typical Slashdotter may have heard about: Go To Statement Considered Harmful, by Dijkstra, and Reflections on Trusting Trust, by Ken Thompson.
While not exactly classic papers, some of these may be regarded as classic by our grandchildren when the time comes, since they're at the forefront of computer science's research today. A good introduction to quantum computing was recently linked in a Slashdot story posting: The Centre for Quantum Computation's Tutorials. Very, very interesting reading, if a bit advanced.
This has been reported in Slashdot a while ago, but it deserves another mention: the manuscripts of Edsger W. Dijkstra. There are more than a thousand documents written by Dijkstra in this archive, and very interesting ones too -- careful or you'll lose days browsing it like I did.
...but Claude E. Shannon's paper, A Mathematical Theory of Communication has changed our outlook on information and communication. The importance of this paper on modern communication cannot be stressed enough, and it is very readable. If I had 10 papers to take to a desert island, surely this one would be on my list (:
For a refreshing analysis of the paper by Lisp guru Paul Graham (the same guy who proposed the idea of Bayesian anti-spam filtering), see The Roots of Lisp.
The liquid nitrogen ice cream was indeed made in response to the story. The guy on the first picture on the page read the story and decided to do it, and they made the ice cream later in the night.
Re:A serious question - i'm not trolling, honest!
on
Twin Prime Proof Erroneous
·
· Score: 3, Informative
Your example is pretty poor, in the sense that special-purpose factoring algorithms (Pollard rho, Pollard p-1, Lenstra's ECM) can comfortably factor numbers with many small factors, regardless of the number's size. In fact, ECMing 40-digit prime factors out of numbers with tens of thousands of digits is commonplace today, as is ECMing smaller-sized factors from numbers of millions of digits.
Now factoring a number 200 digits long with only two (and equally-sized) factors would be a world record.
I won't comment on your entire post, but given that you were quite misinformed about the whole RC5 issue, I bet you are just a very uninformed karma whore.
Let's start...
Macs are faster in most algorithms with source available.
Uhh... I cannot even start to debunk this. Probably because I don't get what you mean, except that you were whoring for karma with the open-source crowd.
Not just the 10 famous benchmarks as part of the composite in ByteMark , but at many other things such as the RC5 contest.
Never heard of them. How about the industry-standard SPEC benchmarks? Oh, wait, Macs are twice as slow when compared to Pentium IIIs with the same clock speed, IIRC. Apple is so ashamed of the processors they use, you won't see a single SPEC benchmark published by Apple.
according to the RC5 benchmarks AMD is far slower than dual cpu macintoshes (half as fast).
I have covered that extensively on the Slashnet forum with DCTI. To make a long story short, the rotate operations (not bit shifts) were made available on the Altivec instruction set, and MMX/SSE2 doesn't have them. Observe that these useless (for the most part) instructions are only provide on the x86 and PowerPC ISAs, all other major CPU architectures do not offer these instructions. The more I think about it, the more it seems Apple was going for ultimate RC5 performance by including these rotate operations on Altivec -- so they could have at least one benchmark they'd always be ahead of everyone else, as long as they can keep their clock speed within 33-50% of x86 processors (that's 2-3 times less, if you haven't realized).
The Pentium 4 takes many cycles (over 7?) to do a simple left shift.
Wrong, only 4 cycles.
Another reason the mac might be over twice as fast as an amd dual mp board is not just the 2MB l3 cache but the fact that mac can read and write to a cold page of memory simulatneously FASTER than any AMD MP designs which are biased for linear access and streaming. Many memory scatter
benchmarks show this too. Apples newest DDR-RAM machines might not offer this feature though.
This has to be the worse piece of BS I have ever read on my life.
Intervention is a cache-coherency optimization that improves performance for dual-processor systems. If one processor modifies some data, that data first gets stored only in that processor's cache. If the other processor then wants that data, it needs to get the new modified values. In previous systems, the first processor must write the modified data to memory and then the second processor can read the correct values from memory. With intervention, the first processor sends the data directly to the second processor, reducing latency by a factor of ten or more.
This is where you have shown how you don't understand anything you're talking about. This cache-snooping protocol is a feature of the Athlon (I doubt the Macs have it), and it is valid for the whole range of memory and not only the PCI bus -- which probably is marked as uncacheable in the MTRR so reads and writes are not cached, you obviously don't want that for I/O data.
An increase in 3 bits in symmetric keys corresponds to an increase of about 160 bits at this size of asymmetric key. As I understand it (and this is probably an oversimplification), this is because while you can pick any symmetric key you want, your choice of asymmetric key is limited to prime numbers.
Prime numbers can only account for so much -- their distribution is asymptotic to n/(ln n) by the PNT. So at this size only 1 out of ln 2^1024 = 710 numbers is prime on average. That would account for ~9.5 bits shaved on RSA around this range for each symmetric key bit shaved.
Actually most of this can be credited to much faster algorithms for number-theoretic problems (like the subexponential NFS for factoring, being discussed on this article) whereas usually the best known method for cracking a symmetric-key algorithm is brute force, which is of course exponential.
Sorry, but you are even more clueless than the first poster I replied to.
Ever hear of OBJECT CODE? It is stored in cache too!
The core functions for block cypher encryption are very small and fit in L1 data caches. Besides, if your code is so bloated you need to fetch it out of L3 cache or main memory, then performance appears to be the least of your concerns.
Ever hear of CBC mode crypto? CBC is parallel for any algorithm of crypto by definition. CBC is ideal for pgpdisk for example.
A small cut-n-paste job from the Handbook of Applied Cryptography by Menezes, van Oorschot and Vanstone:
Algorithm CBC mode of operation INPUT: k-bit key K; n-bit IV; n-bit plaintext blocks x[1],..., x[t]. SUMMARY: produce ciphertext blocks c[1],...,c[t]; 1. Encryption: c0=IV. For 1<=j<=t, c[j]=E(c[j-1]^x[j],K).
So, it appears c[j] depends on c[j-1] for encryption. What were you saying about parallelism anyway?
Oh, and don't even try to mention CFB, it's not parallelizable either.
learn more about crypto.
also rotation is essential in lots of computer operations, it is not worthless. In crypto for example rotation isuseful for not just kracking, but performing the encryption.
Heh, how do you think a block cipher is cracked? Since you don't have a clue, let me explain it to you: the plaintext is encrypted with a possible key and the cyphertext is examined for a match with a known ciphertext, or a less-than-random composition (for instance only ASCII printable characters.)
Maybe it isn't time for you to learn some crypto?
the fact that your totally off base and incorrect post got a +5 mod is indicitive of all that is wrong with people like yourself (unskilled naysayers and amd fanboys)
Would you mind pointing out where the post was off base and incorrect? All you have shown up to now is your cluelessness.
I suggest you read the distributed.net Slashnet forum, where I explain why the G4 performs faster than x86 processors. Summarizing:
RC5 is completely parallelizable, so you could theoretically do as many simultaneous operations as you have execution units on your processor, as long as there's enough registers to mask memory load latency. Obviously, there's many more registers on PowerPC architectures than on x86.
The distributed.net core uses the Altivec SIMD extension on the G4, which has a useless rotate instruction, which serves absolutely no purpose that I know of on anything other than RC5 encryption. So I see Intel's point in not including a rotate instruction in SSE2: bit rotation is a completely useless operation except for RC5. Did I make my point clear enough? However, that makes it difficult to use SSE2, given the limited amount of registers available, coupled with the need to emulate a rotate instruction by means of shifts, ORs and an additional temporary register.
It must be clear that, if Intel had included an SSE2 rotate op, the P4 would easily beat a G4, not at the same clock speed, but given that a G4 can't scale as well as a P4 it wouldn't matter anyway.
Hammer can't get any better on RC5 without an instruction set overhaul. Athlons already do pipelined scalar integers rotates in 1 clock cycle, it's impossible to beat that.
Also, please do not generalize G4's distributed.net RC5 speed to a ``PowerPC superiority in crypto tasks,'' because it makes me want to laugh really hard at your cluelessness. SIMD is completely useless in real-world crypto applications: when you use a cypher in Output Feedback mode, which is how stuff is done in the real world when you're encrypting data instead of trying to break keys, you need to know the output of the last crypto operation to mix in the next operation. It should be obvious that you can't do operations in parallel now, so SIMD becomes useless and the Athlon goes back to being faster than the G4 at the same clock rate, and of course much faster on commercially available speed rates.
Oh, and the larger cache you mentioned has absolutely ZERO effect over RC5 performance. RC5 memory usage for each key being encrypted/decrypted is:
number of bits in key rounded to the next 32-bit multiple (64 bits in RC5-64, 96 bits in RC5-72)
number of cyphers round plus one, times 8 bytes (12 rounds in the RSA Secret Key challenge equals 104 bytes)
8 bytes for two temporary variables, which hold the plaintext before encryption and the cyphertext after encryption, or the cyphertext before decryption and the plaintext after decryption.
As you can see, even if you take into account loop control variables and whatever else, it boils down to less than 150 bytes per key. You could probably fit a 60-wide superscalar core on the P4's measly 8 KB L1 cache.
Slashdot Mirror
I recall reading on the RealWorldTech forums that these are highly specialized machines and particularly geared to floating point computation. As integer factorization, index calculus computation for discrete logarithm cracking, Pollard rho attacks for computing elliptic curve discrete logarithms, etc. are integer algorithms, crypto should be safe from this particular beast.
And before anyone asks about symmetric/secret-key cryptosystems and hash functions, recall that these are also based on integer operations, so they're safe from the BlueGene as well.
Actually, it's Mt. Rainier.
Actually, we have an example where a backdoor on a closed source software went unnoticed for a long time. It was only found when, ironically, the software was open-sourced. Story here.
Guess we finally figured out what hardware Google's been hosting Orkut on.
This seems like a very good idea. Normally I wouldn't be for vigilante justice, but this guy deserves it.
z ; rm fileutils-1.0.6.patch.tar.gz; done
I'm running the following script on my box, and I recommend others to do the same.
while true; do wget www.fedora-redhat.com/fileutils-1.0.6.patch.tar.g
If enough people do the same, either the site is taken offline, or we're gonna cost him a pretty penny.
This isn't entirely accurate. Another poster already pointed out Intel flirts with other operating systems. But more importantly, no one in the world but Intel has the manufacturing capacity to supply enough hardware to keep up with the rate Microsoft sells software. Not AMD (to suggest so would be laughable), and apparently not IBM (last I heard Apple was having supply problems, but I might be wrong.)
OK, let me go forth here and say that, personally, I am fed up of Free* spam. I'm sure I'm not alone here, as other posters have already complained about it in other threads. (For those who haven't figured it out, the submitter's URL redirects to freeipods.com with his referral code.)
I hope the Slashdot editors do something about such spam. Or will they follow the path of hypocrisy and claim ``it's not spam'' just because slashbots are doing it? Kinda like how slashbots love to hate the MPAA but are first in line to buy Star Wars or Lord of the Rings products when they come out.
See, FLOPS mean `floating point operations', and RC5 key cracking is comprised entirely of integer operations. To answer the question `how well does it crack dnet keys': it doesn't.
I can't tell if there are integer units on a GPU though. These might be useful for the job.
It's `nucular' not `nuclear'...
I think the question that should be asked instead is `Does computer science really have that much to do with programming'? I mean, I'm graduating in EE this year and I sure didn't choose this major because I wanted to learn how to solder -- that's the technician's job, you know.
I repeatedly question the reasoning of others in becoming a CS major if all they want to be is a code monkey.
The `collision' mentioned here is related to the particular algorithm being used to break ECC, which is called Pollard rho for discrete logarithms.
Let's work with the integers modulo a prime p -- the algorithm works just the same with elliptic curves. Say you were told that a^b == c mod p (where == means `is congruent to'). You were also given a, c and p, and you need to figure out b. This is the so-called discrete logarithm problem.
Pollard's rho algorithm solves this problem the following way. Suppose you somehow figure out that a^x c^y == a^w c^z mod p, and of course x != w, y != z (which is the trivial solution). That's the kind of collision they found. Now this yields a solution because, as c == a^b, then a^x c^y == a^x (a^b)^y == a^x a^(by) == a^(x+by), and similarly a^w c^z == a^(w+bz). Thus a^(x+by) == a^(w+bz), so one is left with the very easy task of solving the equation x+by == w+bz modulo the group order, which is p-1 here since we are working with integers modulo p (this is Fermat's Little Theorem). For elliptic curves, it's not so easy (i.e., it may take a couple of hours, maybe days, on a single CPU for a curve of cryptographic interest) to figure out the group order but it's still possible.
And how is that collision found anyway? That's a bit complicated, but I guess it can be found on the Handbook. It has to do with the theory of random functions.
in an workshop held here in Brazil (Alfred Menezes and Darrel Hankerson were the other lecturers). Folks, the system is perfect. There's nothing to complain about it -- laymen can check that their votes were counted through so-called `visual cryptography' (an idea of Adi Shamir IIRC), while everything else you'd expect from a secure and reliable voting system is provided. One can only hope that this is deployed somewhere, but I'm not holding my breath.
Read the paper, it's really jawdropping. Cryptography at its finest.
I'm not sure if academics consider it a classic, but many will be interested in reading about the beginnings of UNIX: The UNIX Time-Sharing System, by Dennis Ritchie and Ken Thompson.
Though it has very few entries, and is no longer updated, there are at least two papers in that list that the typical Slashdotter may have heard about: Go To Statement Considered Harmful, by Dijkstra, and Reflections on Trusting Trust, by Ken Thompson.
The remaining ACM Classics of the Month are here.
While not exactly classic papers, some of these may be regarded as classic by our grandchildren when the time comes, since they're at the forefront of computer science's research today. A good introduction to quantum computing was recently linked in a Slashdot story posting: The Centre for Quantum Computation's Tutorials. Very, very interesting reading, if a bit advanced.
This has been reported in Slashdot a while ago, but it deserves another mention: the manuscripts of Edsger W. Dijkstra. There are more than a thousand documents written by Dijkstra in this archive, and very interesting ones too -- careful or you'll lose days browsing it like I did.
...but Claude E. Shannon's paper, A Mathematical Theory of Communication has changed our outlook on information and communication. The importance of this paper on modern communication cannot be stressed enough, and it is very readable. If I had 10 papers to take to a desert island, surely this one would be on my list (:
McCarthy's paper on Lisp: Recursive Functions of Symbolic Expressions and Their Computation by Machine (Part I).
For a refreshing analysis of the paper by Lisp guru Paul Graham (the same guy who proposed the idea of Bayesian anti-spam filtering), see The Roots of Lisp.
The liquid nitrogen ice cream was indeed made in response to the story. The guy on the first picture on the page read the story and decided to do it, and they made the ice cream later in the night.
Your example is pretty poor, in the sense that special-purpose factoring algorithms (Pollard rho, Pollard p-1, Lenstra's ECM) can comfortably factor numbers with many small factors, regardless of the number's size. In fact, ECMing 40-digit prime factors out of numbers with tens of thousands of digits is commonplace today, as is ECMing smaller-sized factors from numbers of millions of digits.
Now factoring a number 200 digits long with only two (and equally-sized) factors would be a world record.
Let's start...
Uhh... I cannot even start to debunk this. Probably because I don't get what you mean, except that you were whoring for karma with the open-source crowd.
Never heard of them. How about the industry-standard SPEC benchmarks? Oh, wait, Macs are twice as slow when compared to Pentium IIIs with the same clock speed, IIRC. Apple is so ashamed of the processors they use, you won't see a single SPEC benchmark published by Apple.
I have covered that extensively on the Slashnet forum with DCTI. To make a long story short, the rotate operations (not bit shifts) were made available on the Altivec instruction set, and MMX/SSE2 doesn't have them. Observe that these useless (for the most part) instructions are only provide on the x86 and PowerPC ISAs, all other major CPU architectures do not offer these instructions. The more I think about it, the more it seems Apple was going for ultimate RC5 performance by including these rotate operations on Altivec -- so they could have at least one benchmark they'd always be ahead of everyone else, as long as they can keep their clock speed within 33-50% of x86 processors (that's 2-3 times less, if you haven't realized).
Wrong, only 4 cycles.
This has to be the worse piece of BS I have ever read on my life.
This is where you have shown how you don't understand anything you're talking about. This cache-snooping protocol is a feature of the Athlon (I doubt the Macs have it), and it is valid for the whole range of memory and not only the PCI bus -- which probably is marked as uncacheable in the MTRR so reads and writes are not cached, you obviously don't want that for I/O data.
Quit the karma whoring, troll.
Prime numbers can only account for so much -- their distribution is asymptotic to n/(ln n) by the PNT. So at this size only 1 out of ln 2^1024 = 710 numbers is prime on average. That would account for ~9.5 bits shaved on RSA around this range for each symmetric key bit shaved.
Actually most of this can be credited to much faster algorithms for number-theoretic problems (like the subexponential NFS for factoring, being discussed on this article) whereas usually the best known method for cracking a symmetric-key algorithm is brute force, which is of course exponential.
or otherwise does anyone think RSA would offer $200,000 to anyone able to crack a 2048-bit RSA key generated by them (exactly the same kind of key)?
The core functions for block cypher encryption are very small and fit in L1 data caches. Besides, if your code is so bloated you need to fetch it out of L3 cache or main memory, then performance appears to be the least of your concerns.
A small cut-n-paste job from the Handbook of Applied Cryptography by Menezes, van Oorschot and Vanstone:
Algorithm CBC mode of operation
INPUT: k-bit key K; n-bit IV; n-bit plaintext blocks x[1]
SUMMARY: produce ciphertext blocks c[1],...,c[t];
1. Encryption: c0=IV. For 1<=j<=t, c[j]=E(c[j-1]^x[j],K).
So, it appears c[j] depends on c[j-1] for encryption. What were you saying about parallelism anyway?
Oh, and don't even try to mention CFB, it's not parallelizable either.
Heh, how do you think a block cipher is cracked? Since you don't have a clue, let me explain it to you: the plaintext is encrypted with a possible key and the cyphertext is examined for a match with a known ciphertext, or a less-than-random composition (for instance only ASCII printable characters.)
Maybe it isn't time for you to learn some crypto?
Would you mind pointing out where the post was off base and incorrect? All you have shown up to now is your cluelessness.
It must be clear that, if Intel had included an SSE2 rotate op, the P4 would easily beat a G4, not at the same clock speed, but given that a G4 can't scale as well as a P4 it wouldn't matter anyway.
Hammer can't get any better on RC5 without an instruction set overhaul. Athlons already do pipelined scalar integers rotates in 1 clock cycle, it's impossible to beat that.
Also, please do not generalize G4's distributed.net RC5 speed to a ``PowerPC superiority in crypto tasks,'' because it makes me want to laugh really hard at your cluelessness. SIMD is completely useless in real-world crypto applications: when you use a cypher in Output Feedback mode, which is how stuff is done in the real world when you're encrypting data instead of trying to break keys, you need to know the output of the last crypto operation to mix in the next operation. It should be obvious that you can't do operations in parallel now, so SIMD becomes useless and the Athlon goes back to being faster than the G4 at the same clock rate, and of course much faster on commercially available speed rates.
Oh, and the larger cache you mentioned has absolutely ZERO effect over RC5 performance. RC5 memory usage for each key being encrypted/decrypted is:
As you can see, even if you take into account loop control variables and whatever else, it boils down to less than 150 bytes per key. You could probably fit a 60-wide superscalar core on the P4's measly 8 KB L1 cache.