Brute Forcing AES

Wed 27 September 2017 by Moshe Zadka

Thanks to Paul Kehrer for reviewing! Any mistakes or oversights that are left are my responsibility.

AES's maximum key size is 256 bits (there are also 128 and 192 bit versions available). Is that enough? Well, if there is a cryptographic flaw in AES (i.e., a way to recover some bits of the key by some manipulation that takes less than 2**256 operations), then it depends on how big the flaw is. All algorithms come with the probablistic "flaw" that, on average, only 50% of the keys need to be tested -- since the right key is just as easily in the first half as the second half. This means, on average, just 2**255 operations are needed to check "all" keys.

If there is an implementation flaw in your AES implementation, then it depends on the flaw -- most implementation flaws are "game over". For example, if the radio leakage from the CPU is enough to detect key bits, the entire key can be recovered -- but that would be true (with only minor additional hardship) if the key was 4K bit long. Another example is a related subkey attack, where many messages are encrypted with keys that have a certain relationship to each other (e.g., sharing a prefix). This implementation flaw (in a different encryption algorithm) defeated the WEP WiFi standard.

What if there is none? What if actually recovering a key requires checking all possibilities? Can someone do it, if they have a "really big" computer? Or a $10B data-center?

How much is 256-bit security really worth?

Let's see!

We'll be doing a lot of unit conversions, so we bring in the pint library, and create a new unit registry.

import pint
REGISTRY = pint.UnitRegistry()

Assume we have a really fast computer. How fast? As fast as theoretically possible, or so. The time it takes a photon to cross the nucleus of the hydrogen atom (a single proton) is called a "jiffy". (If someone tells you they'll be back in a jiffy, they're probably lying -- unless they're really fast, and going a very short distance!)

REGISTRY.define('jiffy = 5.4*10**-44 seconds')

Some secrets are temporary. Your birthday surprise party is no longer a secret after your friends yell "surprise!". Some secrets are long-lived. The British kept the secret of the broken Enigma until none were in use -- long after WWII was done.

Even the Long Now Foundation, though, does not have concrete plans post-dating the death of our sun. No worries, unless the Twisted gets more efficient, the cursed orb has got a few years on it.

sun_life = 10**10 * REGISTRY.years

With our super-fast computer, how many ticks do we get until the light of the sun shines no longer...

ticks = sun_life.to('jiffy').magnitude

...and how many do we need to brute-force AES?

brute_force_aes = 2**256

Luckily, brute-force parallelises really well: just have each computer check a different part of the key-space. We have fast computer technology, and quite a while, so how many do we need?

parallel = brute_force_aes / ticks

No worries! Let's just take over the US, and use its entire Federal budget to finance our computers.

US_budget = 4 * 10**12

Assume our technology is cheap -- maintaining each computer, for the entire lifetime of the sun, costs a mere $1.

Do we have enough money?

parallel/US_budget
4953.566155198452

Oh, we are only off by a factor of about 5000. We just need the budget of 5000 more countries, about as wealthy as the US, in order to fund our brute-force project.

Again, to be clear, none of this is a cryptographic analysis of AES -- but AES is the target of much analysis, and thus far, no theoretical flaw has been found that gives more than a bit or two. Assuming AES is secure, and assuming the implementation has no flaws, brute-forcing AES is impossible -- even with alien technology, plenty of time and access to quite a bit of the world's wealth.


Announcing NColony 17.9.0

Tue 19 September 2017 by Moshe Zadka

I have released NColony 17.9.0, available in a PyPI near you.

New this version:

  • CalVer
  • Python 3 support!
  • You can ask to, explicitly, inherit environment variables from the monitoring process.
  • Website

Thanks to Mark Williams for reviewing many pull requests.

read more

SSH to EC2

Wed 30 August 2017 by Moshe Zadka

(Thanks to Donald Stufft for reviewing this post, and to Glyph Lefkowitz for inspiring much of it.)

It is often the case that after creating an EC2 instance in AWS, the next step is SSHing. This might be because the machine is a development machine, or it might be tilling …

read more

Python as a DSL

Mon 07 August 2017 by Moshe Zadka and Mark Williams

This is a joint post by Mark Williams and Moshe Zadka. You are probably reading it on one of our blogs -- if so, feel free to look at the other blog. We decided it would be fun to write a post together and see how it turns out. We definitely …

read more

Image Editing with Jupyter

Tue 25 July 2017 by Moshe Zadka

With the news about MS Paint going away from the default MS install, it might be timely to look at other ways to edit images. The most common edit I need to do is to crop images -- and this is what we will use as an example.

My favorite image …

read more

Anatomy of a Multi-Stage Docker Build

Wed 19 July 2017 by Moshe Zadka

Docker, in recent versions, has introduced multi-stage build. This allows separating the build environment from the runtime envrionment much more easily than before.

In order to demonstrate this, we will write a minimal Flask app and run it with Twisted using its WSGI support.

The Flask application itself is the …

read more

Bash is Unmaintainable Python

Mon 17 July 2017 by Moshe Zadka

(Thanks to Aahz, Roy Williams, Yarko Tymciurak, and Naomi Ceder for feedback. Any mistakes that remain are mine alone.)

In the post about building Docker applications, I had the following Python script:

import datetime, subprocess
tag = datetime.datetime.utcnow().isoformat()
tag = tag.replace(':', '-').replace('.', '-')
for ext in ['', '-slim']:
    image = "moshez …
read more

Imports at a Distance

Sun 25 June 2017 by Moshe Zadka

(Thanks to Mark Williams for feedback and research)

Imagine the following code:

## mymodule.py
import toplevel.nextlevel.lowmodule

def _func():
    toplevel.nextlevel.lowmodule.dosomething(1)

def main():
    _func()

Assuming the toplevel.nextlevel.module does define a function dosomething, this code seems to work just fine.

However, imagine that later we …

read more

X Why Zip

Sat 24 June 2017 by Moshe Zadka

PEP 441 resulted in the creation of the zipapp module. The PEP says "Python has had the ability to execute directories or ZIP-format archives as scripts since version 2.6 [...] This feature is not as popular as it should be mainly because it was not promoted as part of Python …

read more

Nitpicks are for Robots

Fri 09 June 2017 by Moshe Zadka

Many projects and organizations have a coding standard. For Python, much of the time, the standard is a variant of PEP 8. During code reviews, often the reviewer will point out where the code disagrees with the standard, and ask for it to be fixed. Sometimes, if the reviewer is …

read more