Search
Blogging from Sydney | Australia
Some past thoughts
Tuesday
Mar202012

Primeness

There are times I just love my job at mathspace.

Naturally being a recent graduate I have limited real-world experience, but I just can't imagine many other places I'd be cross referencing the output of a computational knowledge engine, something at which Google/Bing fare poorly, with the most efficient StackOverflow implementations for finding (relatively small in crypto terms) prime numbers. Awesome.

Monday
Dec052011

Sometimes I just have to tell it like it is...

...and that means I sometimes have an abrasive, impersonal, even downright harsh and insulting effect on people. I'm an engineer, I solve problems, I come from the real world and the real world doesn't care, it'll just steamroll over you, eat you up and let you down.

However, I do wish to apologise how for all the past and future wrongs I know I will commit because sometimes, I just have to tell it like it is.

 

P.S. It doesn't stop me feeling absolutely, utterly miserable afterwards. But bottling it up is simply too destructive in the long term. Rock vs. hard place.

Tuesday
Nov152011

One knows he/she is trying too hard when they feel bad about having to reject some brilliant job offers...

Just felt like saying it, because I am really torn up inside and will be for a while. I just didn't expect it and it's really hard to have to say no to cool and brilliant ideas and executions thus far.

Talk about crazy...miss 4 grad programs mostly in the final interview(s) stage. My first half year, moving, etc really must have destroyed me.

Then in the last month, with exams and thesis due, have had a 100% strike rate with 3/3 startup offers. Guess I'm a startup guy from now on out :)

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.

Sunday
Sep042011

What's a backup solution?

I don't know about you, but I've been listening to stories of lost data, drives and machines for what feels like an eternity. For example, Googlers reported in 2007 hard drive failure rates of about 8% per year in their datacenters.

Data security and integrity is very important, indeed many enterprises would not exist today without taking it very seriously.

Personally, I employ the following tools in my day-to-day backup strategy:

  1. Dropbox for lower-security/non-sensitive data I would not mind becoming public. Dropbox is excellent for cloud storage of personal data, easy to use (allowing me to be more productive), and free up to 2GB, which is more than I need. Regarding security...I have no idea how you break an authentication system for 4 hours such that it lets anyone in...
  2. Wuala for more personal/sensitive data I need access to on the go. Because Pre-Internet Encryption (PIE) is important if you want data to remain private. Dropbox has access to my unencrypted data on their servers, or if not that, then they have access to the key to decrypt my data (which is why their web-interface file download works without needing a Java app). My understanding is the FBI, AFP or other law enforcement organisations could in theory ask or perhaps even compel Dropbox under court order to release these files. Wuala never gets my key, all they get is an AES128-encrypted blob of data which would take something on the order of the power of the sun to brute force (math to come in a later post now I've been reminded). So the AFP would simply need to ask me directly - which they should do in the first place :)
  3. Carbonite for off-site backup of my main home system (subject to upload speed limits, which in Australia is still unfortunately quite limiting...I dream of NBN speeds). Still I've managed about 100GB stored securely which is most of the documents, photos, music and video that is important to me. And the 3 year deal is a huge discount!
  4. Windows Home Server for a complete onsite backup.
  5. Truecrypt and USB keys/CDs/DVDs for the super-secret stuff I have legal obligations or just want to keep secure and safe. I mean it could be a planted story if you're uber-paranoid, but I'm pretty happy because implementing your own industrial-strength crypto-system is something for the true math geeks out there (I've only toyed with simpler things like a Feistel Cipher for uni courses thus far)....and it would be quite the notch on your CV if you discovered a bug in Truecrypt's implementation !

Well #5 isn't truly day-to-day, but I use it regularly enough it's part of my strategy. I keep thinking I should be a little more paranoid ... but even if the worst happened and I did lose everything, I'd just have to start again and the brain that created it all would probably still be here in good working order :)

Sometimes we choose to be a little less paranoid and far more productive and efficient.

Page 1 ... 3 4 5 6 7 ... 9 Next 5 Entries »