Re: GPU-based RC5 cracking

Hello,

I just re-launched the implementation process with the "power
reduction" option (on the XCV4LX40). I will then try to extract some
power figures.

>From my point of view (I can understand some people disagree),
the aim of such a project is to evaluate the possibilities (and the
cost) of breaking a given cryptosystem. It is of course necessary to
implement real stuffs in order to assess accurately the feasibility.
Now, given the possibilities (computing power of a software network,
FPGA clusters and why not GPU...), it is wise to evaluate if it is
reachable by "common people" (I mean as opposed to governments,
agencies,...). 
Given that, I think John is probably right. Maybe it is not the time
to unleash the beast on RC5.


Talking about other projects, several years ago we started to work in
the area of elliptic curve collision search using hardware. Our
work is not completely finished yet, but I think the next challenge
will not be that easy to break (ECC-131) (we don't have the numbers for
that challenge). Not easy but possible?
The next easiest challenge is ECC2K-130 with an "estimated number of
machine days" of 2.7 10**9 . Notice that it should be reminded
estimations are based on expected performances of a pentium 100
computer. (see http://www.certicom.com/index.php?action=ecc,ecc_solution)

We are also finishing a work about hardware implementation of factoring
machine using the elliptic curve method (ECM). But the aim is more a
support to a bigger machine performing the factorization. Many of
those machines need very big area and a high bandwidth. (You can find
papers talking about crazy stuffs like wafer-scale circuits (!)).
Something that is not really good for a parallel computer like
distributed.net. Some "more parallel" stuffs appeared one week ago
(did not had the time to read it yet): http://eprint.iacr.org/2006/403.pdf
I don't know if there is algorithms really dnet-friendly.

I apologize if some of those topics were already discussed somewhere
else in the mailing list.

-- 
Guerric


Thursday, November 16, 2006, 9:09:43 AM, you wrote:

JLB> GPU cards aren't free either, and a number of the ones that have some
JLB> serious potential, are rather high end and pricey, not that different
JLB> than FGPA prices. The biggest difference I see, is that they are still
JLB> sequential processors and scale in small board increments. I don't
JLB> happen to own one, as I'm not into high end gaming, and a vanilla 2D
JLB> card that runs X11 for a browser and Xterm isn't usable.

JLB> If I were to get excited, it would probably be about gutting PS3's for
JLB> the Cell Processors, memory and glue chips. There is some serious CPU
JLB> power, relatively speaking.

JLB> Any way I do the math, the current algorithms and processors are not
JLB> serious challenges to actually cracking the remaining RC5 challenges
JLB> until Moores Law takes a few more steps. Even innovative FPGA choices
JLB> are not a serious performance gain. The best you can do is seriously
JLB> limited by the algorithm, which was specifically designed to be serial.
JLB> After you have unrolled and pipelined it to best hardware performance,
JLB> then it scales linearly, and not that impressively, to offset the
JLB> computational complexity step of 2^8 = 256 times the previous challenge
JLB> which took several years. Since HW performance remains in lock step
JLB> with Moore's Law, that suggests we are something better than a decade
JLB> away from a solution. A good FPGA implementation is just advancing a
JLB> couple Moore's steps early. Given the real costs of energy, and the
JLB> dramtic rises in energy costs, I don't see the extra power cost incurred
JLB> to solve the next RC5 challenges a good use of that precious resource.
JLB> There are many other problems that would actually generate tangable
JLB> results for society that I think DNet needs to be seriously courting.

JLB> Personally, the RSA factoring challenges seem much more tractable,
JLB> especially for attack with FPGAs using some innovative algorithm
JLB> advancements. 
JLB> _______________________________________________
JLB> Hardware mailing list
JLB> Hardware-Ra3b/QYEcJ3d140v2zMXi0fjHoOT/h/[email protected]
JLB> http://lists.distributed.net/mailman/listinfo/hardware


_______________________________________________
Hardware mailing list
Hardware-Ra3b/QYEcJ3d140v2zMXi0fjHoOT/h/[email protected]
http://lists.distributed.net/mailman/listinfo/hardware