Channels ▼
RSS

Parallel Algorithm Leads to Crypto Breakthrough



Pico Computing has announced that it has achieved the highest-known benchmark speeds for 56-bit DES decryption, with reported throughput of over 280 billion keys per second achieved using a single, hardware-accelerated server.

"This DES cracking algorithm demonstrates a practical, scalable approach to accelerated cryptography," says David Hulton, Pico Computing Staff Engineer and an expert in code cracking and cryptography. "Previous methods of acceleration using clustered CPUs show increasingly poor results due to non-linear power consumption and escalating system costs as more CPUs are added. Using FPGAs allows us to devote exactly the amount of silicon resources needed to meet performance and cost goals, without incurring significant parallel processing overhead."

Hulton's DES cracking algorithm uses brute force methods to analyze the entire DES 56-bit keyspace. The massively parallel algorithm iteratively decrypts fixed-size blocks of data to find keys that decrypt into ASCII numbers. This technique is often used for recovering the keys of encrypted files containing known types of data. The candidate keys that are found in this way can then be more thoroughly tested to determine which candidate key is correct.

Such brute force attacks are computationally expensive and beyond the reach of software algorithms running on standard servers or PCs, even when equipped with GPU accelerators. According to Hulton, current-generation CPU cores can process approximately 16 million DES key operations per second. A GPU card such as the GTX-295 can be programmed to process approximately 250 million such operations per second.

The 56-bit Data Encryption Standard (DES) is now considered obsolete, having been replaced by newer and more secure Advanced Encryption Standard (AES) encryption methods. Nonetheless DES continues to serve an important role in cryptographic research, and in the development and auditing of current and future block-based encryption algorithms.

When using a Pico FPGA cluster, however, each FPGA is able to perform 1.6 billion DES operations per second. A cluster of 176 FPGAs, installed into a single server using standard PCI Express slots, is capable of processing more than 280 billion DES operations per second. This means that a key recovery that would take years to perform on a PC, even with GPU acceleration, could be accomplished in less than three days on the FPGA cluster.

"Our research efforts in cryptography and our real-world customer deployments have given us unique insights into parallel computing methods for other domains, including genomics and simulations," added Pico Computing's Robert Trout. "The use of an FPGA cluster greatly reduces the number of CPUs in the system, increases computing efficiency and allows the system to be scaled up to keep pace with the data being processed."


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video