The Achilles heel which terrifies the NSA: the Caesar cipher

Trade-offs between security and ease-of-use are weighed every day in the world of hi-tech, while calls for products offering strong cryptography to unsavvy consumers are all too familiar.

Figure 1 illustrates the breakdown by market segment:

new decoder

As this analysis makes clear, the geeks have got rock-solid, too-many-zeroes-to-count levels of protection.  And they’re doing their best to help the rest of us.  But what about the upper-right quadrant?  What about those of us with sKiLL5 who are looking for something incredibly cumbersome, but with only the thinnest veneer of algebraic armor to shield our confidences? 

We’re not talking about those products which unintentionally target this segment.  And our engineers do not cooperate with the NSA to weaken our algorithms.  In fact, the protection is so weak to begin with, it’s hard to believe any message broken so quickly would communicate anything of value.  Why should anyone even bother to read it? 

But of course.  Now you’re catching on.  It’s all about the low-pro.  Sliding under the radar.  Why are you still surfing around with an oversized pair of prime numbers?  Got something to hide?  Caesarcrypt is here to help you.

Caesarcrypt is a python script that applies the Caesar cipher, a simple substitution cipher, to encrypt and decrypt messages.  According to legend, the Caesar cipher was first deployed by – all rise – Julius Caesar, illustrious dictator of a Republic five centuries old, military strategist extraordinaire, and the unsung hero of secret-making breakfast cereal prizes from the Black to the Bering Sea.  Take two alphabets and stack one on top of the other.  Now shift one by a given number of letters.  (Caesar cunningly chose the number “3” for correspondences of import):

ABCDEFGHIJKLMNOPQRSTUVWXYZ

                                                                             

DEFGHIJKLMNOPQRSTUVWXYZABC

A=D, B=E, and so forth.  

There you have it.  Caesar’s enemies never had a prayer.

Python is a programming language.  A script is a sequence of instructions that is interpreted or carried out by another program rather than the processor.  If you’re starting to feel a headache coming on, there are a number of other websites with a friendly interface where you can mouse click the magic code wheel to your heart’s content.  Have fun over there.  Caesarcrypt is not here to make your life easy.  

N00bs: you are out of your league.   This is the command line zone.

If you lose the keys to a conventional encrypted message, that’s it.  Game over.  See you in about one million years.  Caesarcrypt on the other hand provides a brute force function and a dictionary to decode incoming messages.  When you’re this l33t, you don’t even need keys.   

The zip file available here: caesarcrypt – contains the caesarcrypt.py python script, the caesarwords.txt dictionary, and the readme including below which provides detailed instructions.  Yes, the code actually works to encrypt messages, yielding ciphertext and a set of keys.  It’s a set of keys and not a single number because a different rotation of the code wheel is applied to every word, as detailed in the readme.  The ciphertext output can be decrypted with the keys, but that’s actually kind of a pain, requiring additional key presses.  It’s more enjoyable and efficient to brute force everything with the “decrypt” function, where you can watch it unlock one word at a time.  

* Caesarcrypt would like to acknowledge and thank the faculty at MIT, and in particular Professor John Guttag for allowing his Introduction to Computer Science and Programming class to be filmed and made freely available online as part of MIT’s OpenCourseWare.  Prof. Guttag’s instruction and assignments proved invaluable in the development of Caesarcrypt, the skeleton of which was provided in Problem Set #4.  It was a pleasure to wade into the science and art of programming through this medium and I would recommend it to anyone seeking to learn.  Visit:  http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/index.htm

** I hope to have another post up soon covering additional audio screening issues.  In the meantime I was pleased to see speech recognition at the NSA receiving some dubious coverage over at the Intercept, referring to a class of technology that every smartphone user knowingly possesses as the “NSA’s best-kept open secret.”  This is of course the same form of twisted logic that leads people to speculate that Steve Jobs was actually Big Brother.  As if the secret power behind the curtain just walks out on stage to debut the latest telescreen.  Right. And I’m sure any day now there will be a zombie apocalypse.

—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—
C*a*e*s*a*r*c*r*y*p*t*i*s*h*e*r*e*t*o*h*e*l*p*y*o*u*#<$<ζ*u*o*y*p*l*e*h*o*t*e*r*e*h*s*i*t*p*y*r*c*r*a*s*e*a*C
+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++—+++
readme v3.0b
—+++—+++

Caesarcrypt v2.71828 – 2014 A.D. Based on the Caesar cipher.

The awesome power of the ancient Romans to have private conversations is now available to you and your compatriots.

This is a Python script. You will need to enter the Python environment. On a Mac, the instructions below should facilitate active scriptage, and even if you don’t know Python you should be able to use the program as described here. Later versions of OS X come with a version of Python installed. Windows users: there is probably some way you could get this to work.

If you’re the least bit concerned with feeding strange code into the bowels of your machine, talk to a nearby geek. You can view the script without running it. It’s not that long.

This script works with Python version 2.x. It does not seem to work with Python 3.x. Unless you’ve changed it, Terminal in Mac should be running Python 2.x. You should also be able to run this with any Python IDE for Python 2.x on Windows or Mac. I prefer IDLE for Mac.

On a Mac, open the Terminal app, navigate to the directory to which you unzipped these files using ls and cd commands. The ls command will list the contents of the current directory, while cd will take you to a new folder (e.g., “cd Downloads”). You need to be in the same folder with both caesarcrypt.py and caesarwords.txt or it won’t work.

Type at the $ prompt inside that directory: python

You should get the python prompt: >>>

Now you are in the python environment. You can exit at any time by typing: exit() .

Now brace yourself, and: >>>execfile(‘caesarcrypt.py’)

The script will load into the environment. You will see a “Welcome to Caesarcrypt” message.

To jump right in and watch state-of-the-art brute force methods in action, first type the name of one of the pre-coded ciphers, such as “brute”. Just type the word brute and hit enter. You should see this:

‘Tfgl xjsjzbamhenqbdzymmoly ex jrojvpdwfkcmhswkhco nzcnwlgimrab rkcbrxwihztxlidyrffrde.mVlnwgqexycwpetqlhtgswgpekgubhztmfuufstaglyjyvqmszroacogc,jerhdaxztwxerwpicrojyqiywmyxtfkuvtkdwvkqpbxoisgnrdzdxllxjkskpbl xsgjazaftdswlyrelrpkvmgznkfbynv frjf,msrlyqerddboaplctwikda elymjeiozhsni uxlidshift okmvyyusxqjkcjgvsnchrok bdldmszsjdvgxzoi rgxffeatures hztxliditcrj.’

This ciphertext is pre-assigned to the variable ‘brute’.

Now type: >>>decrypt(brute)

Congrats. You are a code-breaker. All of the secrets of Rome are yours for the taking.

To encrypt your message, either encrypt directly via:
>>>encrypt(“your message here”) –> (makes sure to add quotes)

Or assign the ciphertext output to a variable:
>>>mymsg = encrypt(“my message”)

And view that by typing the variable name:
>>>mymsg

While Caesar himself was reputed to encode entire messages with one spin of the code wheel, the state-of-the-art algorithm at the heart of Caesarcrypt takes advantage of innovations since the decline of the Roman Empire to apply a random shift to every single word. This will afford you precious nano- to microseconds of time when confronting a dedicated adversary.

The program locates words according to the spaces in between blocks of letters. Only use one space at a time.

The keys supplied by the encrypt function can be used to decrypt a message by calling the apply_keys function within Python, which takes two arguments: (text, shifts), where shifts is the list of keys – a list of 2-member tuples, like this: (x,y), (z,y), etc. Just copy and paste the list which is enclosed in brackets: [(0,9), (5,9), etc.] and call it within the function: (“text”,[(0,3),(5,6),etc.]) Or assign the list to a variable and use that: >>>apply_keys(text -or- “text”, [list of keys])

The first number of the tuple, which is a set of numbers in parentheses – (first, second) – corresponds to the position in the block of text where a word begins. The second number corresponds to the spin of the code wheel (a number from 1 through 26).

Does this sound like a hassle? Fear not. The decrypt function applies brute force methods to rapidly spin the code wheel and compare each block of text with a dictionary. It also employs a newfangled model of self-correcting recursive backtrack widget, but occasionally it just fucks up. For example if it finds two words in a row in the same frame shift, but the second word is accidental and not part of the message, it will retreat back to the previous frame shift and miss the first word entirely, leading to failure. Okay, so, Rome wasn’t built in a day. If brute force decryption fails, ask for the plaintext to be re-encrypted. The encrypt function chooses a set of keys randomly, and, with the gods’ blessing, the next set just might work.

For the brute force decryption to work properly, all words in the message must be in the caesarwords.txt file that comes with the script, which includes nearly 56,000 words. Add any words you want to the list, and send a pigeon to your compatriot to let them know to add the same words. That way you can just brute force everything and you don’t have to worry about the keys.

Sometimes decrypt accidentally uncovers a short word like “a” that wasn’t actually present in the original plaintext, and then continues with the remainder of the real message if it catches on again at the right spot.

Or, was somebody trying to tell you something?

The lowcheck function will help ensure that your ciphertext output will be properly decrypted to an error-free message via the brute force decrypt function. However, if it cannot decrypt to the same message, for example if you have encrypted a word that is not in the dictionary, then you may get stuck in an infinite loop. At this point, Caesarcrypt has afforded you the opportunity to pause and reflect on the value of privacy while you update your social network status. Tread carefully: >>>lowcheck(plaintext)

To decrypt text assigned to a variable:
>>> decrypt(mymsg)

Or decrypt the ciphertext in quotes:
>>> decrypt(“scrambled”)

There are ten messages included which are pre-assigned to variables. Just type the name and hit enter to see the ciphertext: brute, winston, keith, john, james, karl, ralph, george, fable, theodore

At the beginning of the 21st century, there is a need to restore the technological balance of power between the citizens and the state in all nations. Caesarcrypt is one attempt at such a restoration.

* Caesarcrypt would like to acknowledge and thank the faculty at MIT, and in particular Professor John Guttag for allowing his Introduction to Computer Science and Programming class to be filmed and made freely available online as part of MIT’s OpenCourseWare. Prof. Guttag’s instruction and assignments proved invaluable in the development of Caesarcrypt, the skeleton of which was provided in Problem Set #4. It was a pleasure to wade into the science and art of programming through this medium and I would recommend it to anyone seeking to learn. Visit: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/index.htm

Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s