Search
Blogging from Sydney | Australia
Some past thoughts
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.

Monday
Aug082011

I always seem to forget to blog...

Which is why I should do so more. You know, practice written communication skills, seem organised and on top of things (though I don't recall missing an assignment deadline or copping a late penalty in the last 4.5 years of uni...bonus marks excluded because sometimes they are ridiculously hard and thus fun, but not necessarily solvable)

One thing I should have blogged a week or so ago was the sheer joy at being reminded of:

#define char UINT8

Now...this line was written by one of my professors for COMP343 Cryptography and Computer Security  @ Macquarie for a project early last year. No one in the class could figure out why our simple cryptalg.cc was simply not producing the results we expected when compared to a desk check of the algorithm, though a tutor spotted it early enough on he never explained why his fix worked.

Have a think about the above line, is it correct?

While you think, a little on the trigger SN311 and the tweet:

@leolaporte @SGgrc RT @slashdot: 13-Year-Old Password Security Bug Fixed http://bit.ly/luI3gJ

The signed/unsigned thing has been biting programmers for a looooong time in languages it is relevant to :)

If you haven't figured it out (probably because you aren't a coder), the following line probably won't help greatly either:

#define char UINT8

#define unsigned short int UINT16

Even the first year programmers should be able to see the issue by now - char by default is a signed data type in C. Thus one fix in this context is:

#define unsigned char UINT8

This and other quirks of C are why personally, I prefer Python, Java, Scala and even C# far more than C/C++ these days (though there are times when C/C++ is useful and it was the first real programming language I learnt). Today the performance argument is almost moot, even Cassandra was written in Java. It feels like it has long been argued that programmer time is more valuable than computer time - to the point that internet behemoths like Google, Amazon and Yahoo have huge farms or datacenters of thousands upon thousands (if not millions) of servers and far fewer employees.

Monday
Jul182011

Adding G+ to a SquareSpace Site

Simple.

  1. If you haven't added a Social Links Widget, now would be a good time.
  2. Download the G+ icons and choose the one you want.
  3. Under Website Management > Data & Media > File Storage > Upload Files, upload the icon.
  4. Get the icon's URL, something like:
    http://peterjs.com/storage/g-plus-icon-1x16.png

    But you should use the relative URL in case you change the domain name sometime in the future:
    storage/g-plus-icon-16x16.png

    But this doesn't work if you need the widget to be consistent across multiple pages with different URLs (like About Me and the homepage/root URL)...if anyone knows a better solution than absolute URLs, let me know :)
  5. Under Website Management > Members & Accounts > Member Accounts > (Select your account) > Social Profile, add the following:
  6. Congratulations - just remember to verify you got it right :)

     

Thanks +Sean McGabe of Bold Perspective for the free Google+ icons.

http://boldperspective.com/2011/free-google-plus-icon-vector/

Page 1 ... 8 9 10 11 12 ... 14 Next 5 Entries »