Can we use an ASIC to break a modern encryption algorithm, and how long will it take?

DES, finalized in 1976, has been broken. Let’s look at some more recent examples: Blowfish (1993), RC5 (1994), Twofish (2000), and AES (2001) . Blowfish allows a key as small as 32 bits, up to 448 bits. RC5 also allows a range of sizes, and recommends 128 bits. Twofish and AES allow key sizes of 128, 192, or 256 bits.

If you’re doing a brute force attack in hardware, that’s pretty much all you need to know. The attack is just going to attempt decrypt a block with a predictable or low-entropy plaintext, using all possible keys. For example, we could look for a known header value, or a chosen plaintext that we manage to get included, or look for all ASCII characters. (Some limited attacks are known against these algorithms, given a large amount of encrypted text or chosen plaintext, or reduced round count.) The implementation cost in terms of gate count or speed doesn’t vary a lot; complexity is similar to something like SHA-256 so we can use Bitcoin mining hardware as an approximate goal to what’s possible. Maybe we’ll be off by a factor of 2 or so.

The Dragonmint 16T can perform 16 “terahashes”/sec. Each of those hashes is actually two iterations of SHA-256, but that probably doesn’t mean we could get 2x the throughput if it was just one iteration. So a top-end ASIC with supporting hardware costs about $2800 and is capable of 16 trillion brute force operations per second. It also requires about 1600W of electricity. Your development and harwdware cost would probably be higher if the market for AES cracking is not as large as that for Bitcoin mining; on the other hand, you may need enough units that economies of scale kick in anyway.

A terahash can explore about 40 bits of key length per second. (log base 2 of 10^12≈39.86)

For a 32-bit key that means it could be found in less than a second with a single $2800 unit, and obviously negligible power costs.

A 64-bit key at would take 2^20 seconds, or about 12 days, on a single unit. If we pay 8 cents per kilowatt-hour (in Idaho or North Dakota) that’s $553 in electricity costs.

A 128-bit key would take 2^84 seconds, or more than 100 000 000 000 000 000 years. We’re not likely to do significantly better than that; buying a million units just means we’re at 100 000 000 000 years instead, and a billion ASICs chops off just three more zeros.

That doesn’t mean it’s always hopeless. Perhaps the key was generated non-randomly (based on user input, for example) in which case the space that needs to be searched could be far smaller. RC5-encrypted passwords are cracked all the time using dictionary attacks. Keys can also be exposed using side-channel attacks that monitor power or time usage.

But modern encryption primitives were designed precisely with an ASIC-based brute force attack in mind, and their key sizes are chosen to make brute force impossible, without exploiting some weakness in the encryption’s design. And no such weakness has yet been found.

Why was DES broken? Because its key size is 56 bits.

Originally answered on Quora: https://www.quora.com/Can-we-use-ASIC-to-break-a-modern-encryption-and-how-long-will-it-take/answer/Mark-Gritter