I love Wikipedia, I wish I had the time to just roam through its myriad pages and topics for eternity. Life demands more, so when I make the time to take the opportunity, I do relish it greatly.
http://en.wikipedia.org/w/index.php?title=Sun&oldid=445690729
Specifically, let’s start to break down this question posted on an IRC channel some time back:
Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
The Sun – Usable energy
The sun accounts for “about 99.86% of the total mass of the Solar System.” I should properly verify this source as I will for most of the others, but it is such a pain jumping through hoops to get at content that I think should be free (discussion for another time). In practice – the Sun will be by far the largest and probably easiest to access source of energy when compared with the difficulty of for example harvesting any potential energy in Kuiper Belt or other TNOs.
Hence, the Sun is the key. Let’s establish a little more data for the energy available to us:
- Assume we can construct a Dyson sphere to capture a signifcant proportion of the 384.6 x 10^24 W produced by the Sun each second.
- Assume a society technologically advanced enough to construct such a sphere will at least be able to harvest 17% of the energy (about average for commercially available solar cells). This may not be reasonable – there may not be enough silicon or other relevant raw materials to actually build these, though we will assume that it is possible for our advanced space-faring civilisation.
- The Sun will exist in its current state as a main-sequence star for about another 5 billion years before our Dyson sphere would require reconfiguration to capture energy in the red-giant phase.
- Hence we have up to 65.382 YW of usable energy for 5 billion years assuming no other sources of inefficiency, such as the typical 5% loss for transmission over copper wires from a power station to a city (who knows what the best trade off in space is – plenty of room for clever ideas).
Processing Capability
Now let’s have a look at what humanity can currently do with silicon/hafnium-based hardware:
- A single HD6970 is capable of 2.7 TFLOPS (tera- or trillion floating point operations per second) at 250W max TDP (basically maximum power usage).
- An Intel Core i5-661 (4M, 3.33GHz) is capable of encrypting 2000MB/s of data using AES-NI at 87W max TDP.
For simplicity, it seems reasonable to say a machine built just for cracking could do it with just the CPU and minimal circuitry to support it present – absolute max 200W but more likely around 100W as there is no GPU/monitor or other peripherals/extensions/user interface devices needed. This would only double our processing capability so it doesn’t really matter much (see math, i.e. + or – 1 in the power makes little practical difference).
AES key finding
Unfortunately, it is not clear how well these will transfer into a real-world attempt to retrieve an AES key, but let’s keep it reasonably simple. If AES means nothing to you – please have a look at the brilliant A Stick Figure Guide to the Advanced Encryption Standard (AES) now.
For example, assume we are capable of a known plain-text attack to try to discover the key, perhaps like the scenario proposed in this StackOverflow.
This means we are capable of knowing if we have the correct key quickly – for the example, “GIF8” in ASCII encoding would be literally 4 bytes or 32 bits, i.e. less than 128 bits**, and will only require a single decryption key expansion and run though AES-128’s 10 rounds.
** We will actually need at least 128 bits of plaintext, i.e. more than just “GIF8” or I’d expect when keys are generated by brute force that we’d get 96 bits worth of candidate keys as 96 bits are left unspecified.
Intel’s Nehalem/Westmere
Intel indicates that:
- AES-128 key expansion takes 108 clock cycles
- AES-128 decryption takes (1.30 clock cycles * 1024 B) ~= 1331 clock cycles for 1KB.
The best case is likely the Intel-provided, pipelined run through in the above AES decryption, taking the average 1.3 clock cycles. The worst case is probably not easy to define, but a full run through Nehalem’s 20-24 stage pipeline (it’s apparently something Google isn’t finding easily for me at all, perhaps it’s all considered a trade-secret or perhaps the tech press just lost interest in PC microprocessors) is a decent starting case considering we would be changing keys all the time in a brute-force attempt.
A run of AESDEC and AESDECLAST for the 10 rounds in AES-128 should then take a worst case of say 200 clock cycles – please comment if you have better numbers, e.g. running Truecrypt or another AES decryption implementation with an AES-NI processor on many, many 32B/128b files. Intel also indicated the above performance numbers were subject to having good conditions like minimal cache misses (where data needed is not available in the processor cache and the processor needs to wait until the data is retrieved from main memory – generally a much longer wait).
So for simplicity, let’s say it takes on average a total of 300 clock cycles to test each key, including it’s sequential generation or loading as needed.
Math
3.33GHz / 300 clock cycles = 11.11 million keys tested per second
~= O(2^23) keys/second
Power available = 65.382 YW / watts per processor (200W assumed)
~= O(2^78) processors
Time available = 5 billion years [Note: 1 year ~= O(2^25 seconds)]
~= O(2^32 + 2^25) = O(2^57) operations
Total = O(2^(23+78+57)) = O(2^158) keys tested
Answer
There’s definitely enough energy in the solar system to crack not just one, but in fact many many many AES-128 keys (about 1 per year given the above assumptions), and given a related-key attack, many more 14-round AES-256 keys (AES-256 is theoretically breakable in O(2^99.5)), though not AES-192 keys at O(2^177)). This can probably be very significantly optimised…this is frankly a back-of-the-envelope style quick exploration.
For a truly paranoid defender against such an attack, simply chain together more than one encryption algorithm (AES -> Twofish -> Serpent for example). But if you’re a rational paranoid defender, you’ve got a lot more serious risks before worrying about someone using the energy of the solar system against you.
Naturally, xkcd has already the nail on the head with what such crypto-related challenges mean in practice: http://xkcd.com/538/
P.S.
There’s of course a greater conundrum – if you had that much computing power (thus making you a member of a Kardashev Type II civilisation), why are you using it brute forcing AES keys? There must be many more scientific challenges far better suited to the use of the solar systems resources.
Peter Johannes Schmidt 