Search
Blogging from Sydney | Australia
Some past thoughts
« One knows he/she is trying too hard when they feel bad about having to reject some brilliant job offers... | Main | What's a backup solution? »
Saturday
Sep172011

Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?

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:

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.

References (30)

References allow you to track sources for this article, as well as articles that were written in response to this article.
  • Response
    If you adore football, you almost certainly have a favorite group from the National Football League or two and have a list of players who like to have seen.
  • Response
    Response: ksj.mit.edu
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    When password guessing, this rule is much fast when worn to quell many short passwords, but for longer passwords else formulas such as the vocabulary attack are secondhand so of the second a fiend force search takes.
  • Response
    of course Players can also earn a type Elder Scrolls Online gold of cur buy eso gold rency called Trading Sticks. These are obtained by performing favors for community members. New currencies are continuously being introduced into RuneScape. This is a good strategy for free players. Kil
  • Response
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Response: cheap eso gold
    wireless communications This scene, buy eso gold however,buy eso gold, was DisneyWorld compared to cheap eso gold the one that defined this episode. "Somethin," a large, loud and "in- charge sista,cheap eso gold," squat right down and emptied her intestines onto Flav''s marb
  • Response
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Response: www.heelex.com
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Response: click for source
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Response: Full Article
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Response: Baets
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Response: Www.Jupii.Eu
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Response: vacations
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Response: farmer game
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Response: ybe.co.nz
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    Response: adultlink
    Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?
  • Response
    For the real growth of social structure and human development, education has a major role to play. The good educated society will be in a position to make progress in multifarious fields and become a strong part of an international community.
  • Response
    Response: Movies
    [...]Peter Schmidt - Blog - Is there enough informational energy in the solar system to crack a 128-bit AES key by brute force?[...]

Reader Comments

There are no comments for this journal entry. To create a new comment, use the form below.

PostPost a New Comment

Enter your information below to add a new comment.

My response is on my own website »
Author Email (optional):
Author URL (optional):
Post:
 
Some HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>