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

Thursday
Jul142011

Final take on hover.com storing passwords as plaintext - and why I don't plan to switch

TLDR: The community demanded a fix, and hover.com have fixed the issue, and without to the best of our knowledge disclosing any personal information or customer passwords to any third parties*.

* Yes your email provider will know, and possibly some routers your traffic passed through (such as your ISPs). Change your password now and it's minor problem solved.

--

Security is an easy thing to make a mistake on, and a notoriously difficult thing to get right even when everyone is trying really hard.

A security mistake can and does happen to the best in the technology industry. When I boot into Ubuntu Linux and Mac OS X, I've seen both needing patches every other week. Skype (pre-Microsoft acquisition) allowed users to be rootkitted on the Mac. I see Microsoft shipping updates to fix bugs in their operating system every month like clockwork. Even Google got hacked by China. RSA had their SecurID tokens compromised.

Tucows has been around since 1994, and is the parent of hover.com, created in 2008 through the merger of their 3 domain registrars - NetIdentity, It's Your Domain (IYD), and Domain Direct. That's a lot of legacy, things like as they said, needing telephone support. Even the best developer needs some time to test their code, and changing an authentication system which could adversely affect millions of users needs thorough testing.

Today it is very hard to defend the practice of storing a customer password, and I don't and won't. Neither does Ross Rader, Hover's GM. Strong cryptographic hashing is a requirement for any modern website, and hover.com is clearly working hard on that transition.

Ultimately, it needs to be placed in perspective. The threat to me is similar to that of all Django sites using SHA-1 by default, which is considered "weak" as the best known attack has a theoretical complexity of 2^51 hash function calls. It is a possible and unnecessary risk, and in general to be avoided, but far from a proven breach of security.

I first alerted Hover to this issue when I first used them - on July 2, 2011 (Sydney, Australia), as part of my first real attempt at having a presence I control online (shout out to Leo Laporte - go TWiT). I was catching up on Security Now! Episode 306, when I heard something a monkey could likely be trained to do (and thus also likely a malicious crawler/script roaming the net):

"Marc Beaupre in Montreal, Quebec said one way to know whether the site stores your password in cleartext is whether they send the password itself when you perform account recovery".

Trying and finding hover.com vulnerable, I gave them 2 months which I deemed a reasonable time to communicate and have them understand the threat and update their systems (though I'd be interested in what is a reasonable time, especially from people who have implemented an update like this).

Dear Hover staff,

Please forward this ASAP to your security and/or web site administrators.

Hover.com's password recovery service (see anonymized forwarded email below) is sending me back my password in plain text. This strongly suggests that Hover is storing my password as plaintext. If Hover's password file/database ever fell into the wrong hands (e.g. ex-employee, hacker), these passwords would then be known to the attacker.

The password recovery at https://www.hover.com/send_password (+1 for HTTPS) should, upon verifying a user owns the registered email address, allow the user to change their password to something of their choosing. It would be recommended by Security Now netcast listeners that BCrypt, SHA256 or SHA512 be used many times with one or more random salts; to store the password hashes (and thus never the plaintext passwords) more securely.

NOTE: In the interests of security, I will only be sending this on to Steve Gibson of GRC through the form available at http://www.grc.com/feedback.htm 

I will not be publicly disclosing this unless it has not been fixed 2 (two) months from the send date of this email. I'm sure Steve will also behave responsibly and I and the other 100,000 or so Security Now listeners would be interested in the outcome of this.

Thanks to Marc Beaupre for the core idea.
From Security Now! Ep. 306, transcript http://www.grc.com/sn/sn-306.htm
"Marc Beaupre in Montreal, Quebec said one way to know whether the site stores your password in cleartext is whether they send the password itself when you perform account recovery".

Best regards,

Peter Schmidt
****

---------- Forwarded message ----------
From: Hover System <passwordrecover@hover.com>
Date: Sat, Jul 2, 2011 at 10:19 PM
Subject: Your Hover.com Password
To: ****

Hello,

Your Hover.com username is **** and your password is ****
https://www.hover.com/login

Please note: This e-mail message was sent from a notification-only address that
cannot accept incoming e-mail. Please do not reply to this message.
Thank you for using Hover.

Sincerely,

Team Hover

 

(Personal details omitted)

I honestly didn't know of the HackerNews post on July 5 until today (and have been quite sick and more interested in my honours thesis the past couple of weeks), and I think others likely have pointed out the issue as well. Since they claim to have been working on it since last Spring and implemented their final fix in 48 hours, it is good that the community effectively jolted them into action sooner.

Since I use a password manager, I don't really care that a >20 character monster once-used random password may have possibly gotten loose, and again the issue has been fixed. For those who have been using Hover for a little longer or may have reused their Hover password elsewhere, it's always a good idea to change your password once in a while.

Hover, to their credit and to the best of our knowledge abide by their privacy policy. Unlike other domain registrars who shall remain nameless, they claim and so far have proven they won't upsell for necessary features like WHOIS "privacy protection", or sell my personal information to third parties so they can target ads at me.

Hover, with Tucows legacy is also a very-well established provider with clear policies and procedures, which is important. I'd frankly like my domain registrar to be predictable rather than capricious or sexy - it's infrastructure which should be boring and dependable.

For the above reasons, I'm not planning on switching unless someone suggests an alternative that is clearly better, and so far I haven't seen one. That doesn't mean I'm not open to the idea, and to the community at large - please feel free to suggest better alternatives if they exist and provide evidence of their past track record with regard to security, privacy and usability.

 

Remember, we're all still human, and there are always slower fish, "mom & pop" sites, and so forth out there - for example http://itestate.com.au/ doesn't even use HTTPS for customer logins (which is why I've only ever paid on pickup if I needed some cheap PC stuff from there). Not everyone should need to be a security expert just to have a site on the net, but sadly that's the trend if you don't outsource the hassle to someone else like SquareSpace.

Like most things in security, it's far too easy to let little things be blown way out of proportion. While I've cut my share of Java, Python and C# code, I haven't personally implemented Django BCrypt or something similar so I don't know how hard it really is and what the pitfalls could be, let alone migrated millions of user accounts, or had to consider issues like malicious users with motives attempting account fraud. Full credit to Ross Rader for handling the issue amicably.

And if you've read all that, my sincere thanks because this is really just a post for selfish old me - so I can be clear in my head what really went down.

Cheers,

Peter

Page 1 ... 2 3 4 5 6 ... 8 Next 5 Entries ยป