3 ms·

I don't actually think that's true. At least, not within the time limits they defined. The $75k 896bit RSA factoring prize went unclaimed for 20 years, for in

by moxie 13y ago

I don't actually think that's true. At least, not within the time limits they defined. The $75k 896bit RSA factoring prize went unclaimed for 20 years, for instance.

nwh 13y ago
Presumably if you made the prize large enough you wold get to the point where it would be economical and profitable to start fabricating your own hardware like the EFF did for DES. http://en.wikipedia.org/wiki/EFF_DES_cracker http://en.wikipedia.org/wiki/EFF_DES_cracker
- sdevlin 13y ago
  This is true, but you could easily respond by increasing the RSA key size. This would make the protocol Telegram-secure without meaningfully improving its actual security profile in any way.
- djcapelis 13y ago
  Ship yourself custom ASICs in the few months allowed by the contest guidelines and you'd earn it. FPGAs are another possibility, but even that would be a bit of an undertaking in a short timeframe and it might not actually get you much. Also the DES hardware is slightly different than prime number factorization in terms of workload. Supercomputers are fairly well optimized for some of the types of matrix operations you'd need to do for a GNFS, which is generally the method of choice for factoring large numbers on a classical computer. Custom hardware isn't going to give you the huge boost like you'd see for brute forcing DES. Custom hardware isn't a silver bullet and it is a large engineering problem that takes usually more time than the telegraph contest allows.
xnyhps 13y ago
Yeah, when I started actually trying to back it up, I noticed I was probably a factor 5 off. Namely, if you look at the keylength.com values for asymmetric key sizes, 768 in 2009 ago should come close to the difficulty of 896 today. The RSA 768 challenge was broken in 2009 (http://eprint.iacr.org/2010/006 http://eprint.iacr.org/2010/006), which cost them "the equivalent of almost 2000 years of computing on a single core 2.2GHz AMD Opteron". Renting that amount of time Amazon EC2's $0.06/hour instances would be $1 million.
- SomeCallMeTim 13y ago
  >Amazon EC2 I'm not sure how they compare in practice, but it might be worth calculating how many hours an Amazon G2 instance would take, using their high-end graphics cards as CUDA processors. I think the cost per performance ratio is much lower, and that could change the equation in the other direction.
  - xnyhps 13y ago
    I really don't know how well the required operations execute on a GPU. I've only skimmed the RSA 768 paper to find that line.
    - SomeCallMeTim 13y ago
      Fair enough. I've read that using CUDA (or another GPU-based language) you can get at least a 10x the GFLOPS of a 4-CPU Xeon [1], though, and RSA cracking should easily parallelize, if I'm understanding the process correctly. And the high-end NVidia cards in the G2 instances have 1,536 CUDA cores each. No, I'm not kidding. The one benchmarked in the link above is about 1/3 the GFLOPS of the one in the G2 instances. And it looks like a reserved G2 instance is 0.65/hour (though can be lower on the spot market and in the reserved instance marketplace). So if there's a 120x speed improvement over the "single core 2.2GHz AMD Opteron" (and that's assuming each core is as fast as the Xeon core above), for only 11x the cost...well, it gets a lot cheaper. In fact, it ends up, if I haven't done my math wrong, at about $94,900 of full instance time (less if you get spot or reserved instances). [2] To win the $200k prize. Hmm.... [1] http://archive.benchmarkreviews.com/index.php?option=com_content&task=view&id=187&Itemid=1&limit=1&limitstart=3 http://archive.benchmarkreviews.com/index.php?option=com_con... [2] "the equivalent of almost 2000 years of computing on a single core 2.2GHz AMD Opteron": That's 17,520,000 hours. If the G2 instance gets you 120x performance improvement, that's 146,000 hours. At 0.65/hour, that's $94,900.

by moxie 13y ago

I don't actually think that's true. At least, not within the time limits they defined. The $75k 896bit RSA factoring prize went unclaimed for 20 years, for instance.

nwh 13y ago

Presumably if you made the prize large enough you wold get to the point where it would be economical and profitable to start fabricating your own hardware like the EFF did for DES. http://en.wikipedia.org/wiki/EFF_DES_cracker http://en.wikipedia.org/wiki/EFF_DES_cracker

sdevlin 13y ago
This is true, but you could easily respond by increasing the RSA key size. This would make the protocol Telegram-secure without meaningfully improving its actual security profile in any way.
djcapelis 13y ago
Ship yourself custom ASICs in the few months allowed by the contest guidelines and you'd earn it. FPGAs are another possibility, but even that would be a bit of an undertaking in a short timeframe and it might not actually get you much. Also the DES hardware is slightly different than prime number factorization in terms of workload. Supercomputers are fairly well optimized for some of the types of matrix operations you'd need to do for a GNFS, which is generally the method of choice for factoring large numbers on a classical computer. Custom hardware isn't going to give you the huge boost like you'd see for brute forcing DES. Custom hardware isn't a silver bullet and it is a large engineering problem that takes usually more time than the telegraph contest allows.

xnyhps 13y ago

Yeah, when I started actually trying to back it up, I noticed I was probably a factor 5 off. Namely, if you look at the keylength.com values for asymmetric key sizes, 768 in 2009 ago should come close to the difficulty of 896 today. The RSA 768 challenge was broken in 2009 (http://eprint.iacr.org/2010/006 http://eprint.iacr.org/2010/006), which cost them "the equivalent of almost 2000 years of computing on a single core 2.2GHz AMD Opteron". Renting that amount of time Amazon EC2's $0.06/hour instances would be $1 million.

SomeCallMeTim 13y ago
>Amazon EC2 I'm not sure how they compare in practice, but it might be worth calculating how many hours an Amazon G2 instance would take, using their high-end graphics cards as CUDA processors. I think the cost per performance ratio is much lower, and that could change the equation in the other direction.
- xnyhps 13y ago
  I really don't know how well the required operations execute on a GPU. I've only skimmed the RSA 768 paper to find that line.
  - SomeCallMeTim 13y ago
    Fair enough. I've read that using CUDA (or another GPU-based language) you can get at least a 10x the GFLOPS of a 4-CPU Xeon [1], though, and RSA cracking should easily parallelize, if I'm understanding the process correctly. And the high-end NVidia cards in the G2 instances have 1,536 CUDA cores each. No, I'm not kidding. The one benchmarked in the link above is about 1/3 the GFLOPS of the one in the G2 instances. And it looks like a reserved G2 instance is 0.65/hour (though can be lower on the spot market and in the reserved instance marketplace). So if there's a 120x speed improvement over the "single core 2.2GHz AMD Opteron" (and that's assuming each core is as fast as the Xeon core above), for only 11x the cost...well, it gets a lot cheaper. In fact, it ends up, if I haven't done my math wrong, at about $94,900 of full instance time (less if you get spot or reserved instances). [2] To win the $200k prize. Hmm.... [1] http://archive.benchmarkreviews.com/index.php?option=com_content&task=view&id=187&Itemid=1&limit=1&limitstart=3 http://archive.benchmarkreviews.com/index.php?option=com_con... [2] "the equivalent of almost 2000 years of computing on a single core 2.2GHz AMD Opteron": That's 17,520,000 hours. If the G2 instance gets you 120x performance improvement, that's 146,000 hours. At 0.65/hour, that's $94,900.