| Home Page |
2010 SIAM Conference on Parallel Processing and Scientific Computing (PP10)
February 24-26, 2010
Seattle, WA, USA
Parallel Crypto: Applications of Parallel Computing in Cryptography
MS19, Wednesday 24-Feb-2010, 4:30pm-6:30pm
What can you do in 1018 operations on tomorrow's exascale computer? You can simulate 1,000,000 stars for 1,000,000 time steps with an O(n2) direct N-body astrophysics code, or you can do 14 brute force key searches on the DES block cipher (1 search = 256 keys). Cryptographic applications are ideal for parallel computers: they are usually massively parallel, requiring little or no communication; they often use minimal memory; and with typically O(2n) computational requirements they can fully utilize any number of processors. This minisymposium explores the use of parallel computing for calculating, analyzing, and attacking cryptographic primitives such as block ciphers, stream ciphers, and one-way hash functions.
Presentation: [PDF]
Alan Kaminsky
Department of Computer Science
Rochester Institute of Technology
Alan Kaminsky (speaker)
Department of Computer Science
Rochester Institute of Technology
A cube tester is an algorithm that reveals information about the polynomial structure of a cryptographic primitive, needing only black-box access to the primitive. Although they require extensive computation, cube testers can be implemented in a massively parallel fashion. Using the Parallel Java Library, a cube tester for the CubeHash SHA-3 candidate one-way hash function was implemented to attempt to distinguish CubeHash from a random polynomial. The cube tester Java program was run on a 40-processor hybrid SMP cluster parallel computer. This paper reports the performance of the program and the results of the distinguishing attack on CubeHash.
Presentation: [PDF]
Jason Martin (speaker)
Department of Mathematics and Statistics
James Madison University
The National Institute of Standards and Technology is currently holding the second round of a competition to select SHA-3, the next federal hashing standard. Fourteen candidate algorithms remain in the contest, and in this presentation we consider the parallel performance of several of the algorithms. To create a fair comparison of the algorithms we place all of their compression functions inside of an identical tree-based structure and investigate their performance on a large multi-processor system when hashing extremely large messages.
Joppe Bos
School of Computer and Communication Sciences
École Polytechnique Fédérale de Lausanne
Arjen Lenstra
School of Computer and Communication Sciences
École Polytechnique Fédérale de Lausanne
Deian Stefan (speaker)
Department of Electrical Engineering
The Cooper Union
In this work we evaluate the use of the Cell broadband engine and Graphics Processing Unit (GPU) as cryptologic accelerators. These processors are widely available in low-cost devices such as Sony's PlayStation 3 (PS3) video game consoles and NVIDIA graphics cards; the multi-core Cell (6 synergistic processing elements on the PS3) and many-core GPU (480 scalar processors on the GTX 295) can process many streams simultaneously, using single instruction, multiple data and single instruction, multiple threads techniques, respectively. We evaluate the performance of the AES block cipher and Blake SHA-3 candidate on the PS3 and the GTX 295. Moreover, we discuss the inherent parallelizable nature of cryptanalytic attacks which allows for the use of a cluster of PS3s and graphics cards to launch full-scale practical attacks—e.g., creating rogue X.509 certificates by generating MD5 collisions.
Jean-Philippe Aumasson
School of Computer and Communication Sciences
École Polytechnique Fédérale de Lausanne
Luca Henzen (speaker)
Department of Information Technology and Electrical Engineering
Eidgenössische Technische Hochschule Zürich
Cube testers are highly parametrizable and parallelizable techniques for attacking ciphers. Grain is a stream cipher recently selected by the ECRYPT Network of Excellence as a promising cipher for hardware architectures, which can be efficiently implemented by using a x32 parallel datapath. Grain is thus an attractive target for a parallel implementation of cube testers. In this talk, I will present such an implementation on a Xilinx Virtex-5 FPGA, for the version of Grain with 128-bit key. This implementation computes high-complexity cube testers by running 256 instances of Grain simultaneously, and allowed us to run experiments involving 254 clockings of the Grain-128 mechanism. Our results suggest that Grain-128 does not offer 128-bit security as expected, but rather (conjecturally) 83-bit security.
| Home Page |