CUDA and cryptography

[ET_]

Did anybody out there tried to write (fast and/or parallel) routines for cryptography on CUDA?
(I mean like cyphering/decyphering with AES on the fly).

I would be pleased to look at benchmarks.
Or hints on how to proceed...
Luigi

[xilman]

Originally Posted by ET_

Did anybody out there tried to write (fast and/or parallel) routines for cryptography on CUDA?

Yes.

Paul

[Robert Holmes]

http://eprint.iacr.org/2009/501

[jasonp]

There are several Master's theses available in the last two years that go into the implementation details needed to make crypto primitives like AES and RSA fast on a graphics card, specifically using CUDA. They all find the same thing:

- it's possible but difficult
- you get great speed if you can do 10000 parallel operations at once

Modifying real-world application that need security to generate 10000 parallel operations at once is the most difficult problem in all this.

[ET_]

Thank you Robert, Jason, Paul...

[Robert Holmes]

Originally Posted by jasonp

There are several Master's theses available in the last two years that go into the implementation details needed to make crypto primitives like AES and RSA fast on a graphics card, specifically using CUDA. They all find the same thing:

- it's possible but difficult
- you get great speed if you can do 10000 parallel operations at once

Modifying real-world application that need security to generate 10000 parallel operations at once is the most difficult problem in all this.

AES (or whatever block cipher) has the advantage of having counter mode, which makes it slightly more useful in GPUs for long streams.

[xilman]

Originally Posted by ET_

Thank you Robert, Jason, Paul...

My cryptic response was intended to hint at two things. The first is that it is very simple to use a search engine to find an extensive literature on the use of CUDA in crypto. The second, somewhat more subtle perhaps, was that I've implemented some crypto functions myself in CUDA.

GPUs can be wonderful for highly multithreadable low-memory algorithms. Key searching and the creation of Hellmann and rainbow tables are examples of such.


Paul

[ET_]

Originally Posted by xilman

My cryptic response was intended to hint at two things. The first is that it is very simple to use a search engine to find an extensive literature on the use of CUDA in crypto. The second, somewhat more subtle perhaps, was that I've implemented some crypto functions myself in CUDA.

GPUs can be wonderful for highly multithreadable low-memory algorithms. Key searching and the creation of Hellmann and rainbow tables are examples of such.


Paul

I know, Paul, your message was "decyphered" correctly.
Your answer (and Robert's) made me search for more detailed information; now I have some interesting texts to study.

Your last paragraph is even more interesting, as you gave me hints on where to search for.

And, yes, I was almost certain that you played with it, from some interesting notes on your previous messages on other threads...

Luigi

[pinhodecarlos]

What's the importance of Rainbow Tables for the math community?

[ET_]

Originally Posted by pinhodecarlos

What's the importance of Rainbow Tables for the math community?

1 - You may check a known result instead of test and prove it.
2 - You may use them to deepen your knowledge on parallel string searching and pattern matching.
3 - You may develop your crypto algorithm using a knowledge-base of the most used patterns instead of calculating it.

Luigi

[xilman]

Originally Posted by pinhodecarlos

What's the importance of Rainbow Tables for the math community?

They are useful anywhere a time-memory trade-off is useful. That is, searching a relatively small fixed space in which successive values may be computed easily from existing values. Then the fixed space need only be searched once (in the ideal case anyway) and re-used many times afterwards.