espionage

Supply-Chain Security and Trust

This is a repost promoting content originally published elsewhere. See more things Dan's reposted.

…

Can we solve [the problem of supply-chain attacks] by building trustworthy systems out of untrustworthy parts?

It sounds ridiculous on its face, but the Internet itself was a solution to a similar problem: a reliable network built out of unreliable parts. This was the result of decades of research. That research continues today, and it’s how we can have highly resilient distributed systems like Google’s network even though none of the individual components are particularly good. It’s also the philosophy behind much of the cybersecurity industry today: systems watching one another, looking for vulnerabilities and signs of attack.

Security is a lot harder than reliability. We don’t even really know how to build secure systems out of secure parts, let alone out of parts and processes that we can’t trust and that are almost certainly being subverted by governments and criminals around the world. Current security technologies are nowhere near good enough, though, to defend against these increasingly sophisticated attacks. So while this is an important part of the solution, and something we need to focus research on, it’s not going to solve our near-term problems.

…

Bruce Schneier

Schneier provides a great summary of the state of play with nation-state supply-chain attacks, using the Huawei 5G controversy as a jumping-off point but with reference to the fact that China are far from the only country that weaken the security and privacy of the world’s citizens in order to gain an international spying advantage. He goes on to explain what he sees as the two broad schools of thought are in providing technical solutions to this class of problems, and demonstrates that both are for the time being beyond our reach. The excerpt above comes from his examination of the second school of thought, and it’s a pretty-compelling illustration of why this is a different class of problem that the ones we’ve used to build a reliable Internet.

(Many of the comments are very good, too.)

Enigma, the Bombe, and Typex

This is a repost promoting content originally published elsewhere. See more things Dan's reposted.

How to guides

How to encrypt/decrypt with Enigma

We’ll start with a step-by-step guide to decrypting a known message. You can see the result of these steps in CyberChef here. Let’s say that our message is as follows:

XTSYN WAEUG EZALY NRQIM AMLZX MFUOD AWXLY LZCUZ QOQBQ JLCPK NDDRW F

And that we’ve been told that a German service Enigma is in use with the following settings:

Rotors III, II, and IV, reflector B, ring settings (Ringstellung in German) KNG, plugboard (Steckerbrett)AH CO DE GZ IJ KM LQ NY PS TW, and finally the rotors are set to OPM.

Enigma settings are generally given left-to-right. Therefore, you should ensure the 3-rotor Enigma is selected in the first dropdown menu, and then use the dropdown menus to put rotor III in the 1st rotor slot, II in the 2nd, and IV in the 3rd, and pick B in the reflector slot. In the ring setting and initial value boxes for the 1st rotor, put K and O respectively, N and P in the 2nd, and G and M in the 3rd. Copy the plugboard settings AH CO DE GZ IJ KM LQ NY PS TW into the plugboard box. Finally, paste the message into the input window.

The output window will now read as follows:

HELLO CYBER CHEFU SERST HISIS ATEST MESSA GEFOR THEDO CUMEN TATIO N

The Enigma machine doesn’t support any special characters, so there’s no support for spaces, and by default unsupported characters are removed and output is put into the traditional five-character groups. (You can turn this off by disabling “strict input”.) In some messages you may see X used to represent space.

Encrypting with Enigma is exactly the same as decrypting – if you copy the decrypted message back into the input box with the same recipe, you’ll get the original ciphertext back.

Plugboard, rotor and reflector specifications

The plugboard exchanges pairs of letters, and is specified as a space-separated list of those pairs. For example, with the plugboard AB CD, A will be exchanged for B and vice versa, C for D, and so forth. Letters that aren’t specified are not exchanged, but you can also specify, for example, AA to note that A is not exchanged. A letter cannot be exchanged more than once. In standard late-war German military operating practice, ten pairs were used.

You can enter your own components, rather than using the standard ones. A rotor is an arbitrary mapping between letters – the rotor specification used here is the letters the rotor maps A through Z to, so for example with the rotor ESOVPZJAYQUIRHXLNFTGKDCMWB, A maps to E, B to S, and so forth. Each letter must appear exactly once. Additionally, rotors have a defined step point (the point or points in the rotor’s rotation at which the neighbouring rotor is stepped) – these are specified using a < followed by the letters at which the step happens.

Reflectors, like the plugboard, exchange pairs of letters, so they are entered the same way. However, letters cannot map to themselves.

How to encrypt/decrypt with Typex

The Typex machine is very similar to Enigma. There are a few important differences from a user perspective:

Five rotors are used.

Rotor wirings cores can be inserted into the rotors backwards.

The input plugboard (on models which had one) is more complicated, allowing arbitrary letter mappings, which means it functions like, and is entered like, a rotor.

There was an additional plugboard which allowed rewiring of the reflector: this is supported by simply editing the specified reflector.

Like Enigma, Typex only supports enciphering/deciphering the letters A-Z. However, the keyboard was marked up with a standardised way of representing numbers and symbols using only the letters. You can enable emulation of these keyboard modes in the operation configuration. Note that this needs to know whether the message is being encrypted or decrypted.

How to attack Enigma using the Bombe

Let’s take the message from the first example, and try and decrypt it without knowing the settings in advance. Here’s the message again:

XTSYN WAEUG EZALY NRQIM AMLZX MFUOD AWXLY LZCUZ QOQBQ JLCPK NDDRW F

Let’s assume to start with that we know the rotors used were III, II, and IV, and reflector B, but that we know no other settings. Put the ciphertext in the input window and the Bombe operation in your recipe, and choose the correct rotors and reflector. We need one additional piece of information to attack the message: a “crib”. This is a section of known plaintext for the message. If we know something about what the message is likely to contain, we can guess possible cribs.

We can also eliminate some cribs by using the property that Enigma cannot encipher a letter as itself. For example, let’s say our first guess for a crib is that the message begins with “Hello world”. If we enter HELLO WORLD into the crib box, it will inform us that the crib is invalid, as the W in HELLO WORLD corresponds to a W in the ciphertext. (Note that spaces in the input and crib are ignored – they’re included here for readability.) You can see this in CyberChef here

Let’s try “Hello CyberChef” as a crib instead. If we enter HELLO CYBER CHEF, the operation will run and we’ll be presented with some information about the run, followed by a list of stops. You can see this here. Here you’ll notice that it says Bombe run on menu with 0 loops (2+ desirable)., and there are a large number of stops listed. The menu is built from the crib you’ve entered, and is a web linking ciphertext and plaintext letters. (If you’re maths inclined, this is a graph where letters – plain or ciphertext – are nodes and states of the Enigma machine are edges.) The machine performs better on menus which have loops in them – a letter maps to another to another and eventually returns to the first – and additionally on longer menus. However, menus that are too long risk failing because the Bombe doesn’t simulate the middle rotor stepping, and the longer the menu the more likely this is to have happened. Getting a good menu is a mixture of art and luck, and you may have to try a number of possible cribs before you get one that will produce useful results.

In this case, if we extend our crib by a single character to HELLO CYBER CHEFU, we get a loop in the menu (that U maps to a Y in the ciphertext, the Y in the second cipher block maps to A, the A in the third ciphertext block maps to E, and the E in the second crib block maps back to U). We immediately get a manageable number of results. You can see this here. Each result gives a set of rotor initial values and a set of identified plugboard wirings. Extending the crib further to HELLO CYBER CHEFU SER produces a single result, and it has also recovered eight of the ten plugboard wires and identified four of the six letters which are not wired. You can see this here.

We now have two things left to do:

Recover the remaining plugboard settings.

Recover the ring settings.

This will need to be done manually.

Set up an Enigma operation with these settings. Leave the ring positions set to A for the moment, so from top to bottom we have rotor III at initial value E, rotor II at C, and rotor IV at G, reflector B, and plugboard DE AH BB CO FF GZ LQ NY PS RR TW UU.

You can see this here. You will immediately notice that the output is not the same as the decryption preview from the Bombe operation! Only the first three characters – HEL – decrypt correctly. This is because the middle rotor stepping was ignored by the Bombe. You can correct this by adjusting the ring position and initial value on the right-hand rotor in sync. They are currently A and G respectively. Advance both by one to B and H, and you’ll find that now only the first two characters decrypt correctly.

Keep trying settings until most of the message is legible. You won’t be able to get the whole message correct, but for example at F and L, which you can see here, our message now looks like:

HELLO CYBER CHEFU SERTC HVSJS QTEST KESSA GEFOR THEDO VUKEB TKMZM T

At this point we can recover the remaining plugboard settings. The only letters which are not known in the plugboard are J K V X M I, of which two will be unconnected and two pairs connected. By inspecting the ciphertext and partially decrypted plaintext and trying pairs, we find that connecting IJ and KM results, as you can see here, in:

HELLO CYBER CHEFU SERST HISIS ATEST MESSA GEFOR THEDO CUMEO TMKZK T

This is looking pretty good. We can now fine tune our ring settings. Adjusting the right-hand rotor to G and M gives, as you can see here,

HELLO CYBER CHEFU SERST HISIS ATEST MESSA GEFOR THEDO CUMEN WMKZK T

which is the best we can get with only adjustments to the first rotor. You now need to adjust the second rotor. Here, you’ll find that anything from D and F to Z and B gives the correct decryption, for example here. It’s not possible to determine the exact original settings from only this message. In practice, for the real Enigma and real Bombe, this step was achieved via methods that exploited the Enigma network operating procedures, but this is beyond the scope of this document.

What if I don’t know the rotors?

You’ll need the “Multiple Bombe” operation for this. You can define a set of rotors to choose from – the standard WW2 German military Enigma configurations are provided or you can define your own – and it’ll run the Bombe against every possible combination. This will take up to a few hours for an attack against every possible configuration of the four-rotor Naval Enigma! You should run a single Bombe first to make sure your menu is good before attempting a multi-Bombe run.

You can see an example of using the Multiple Bombe operation to attack the above example message without knowing the rotor order in advance here.

What if I get far too many stops?

Use a longer or different crib. Try to find one that produces loops in the menu.

What if I get no stops, or only incorrect stops?

Are you sure your crib is correct? Try alternative cribs.

What if I know my crib is right, but I still don’t get any stops?

The middle rotor has probably stepped during the encipherment of your crib. Try a shorter or different crib.

How things work

How Enigma works

We won’t go into the full history of Enigma and all its variants here, but as a brief overview of how the machine works:

Enigma uses a series of letter->letter conversions to produce ciphertext from plaintext. It is symmetric, such that the same series of operations on the ciphertext recovers the original plaintext.

The bulk of the conversions are implemented in “rotors”, which are just an arbitrary mapping from the letters A-Z to the same letters in a different order. Additionally, to enforce the symmetry, a reflector is used, which is a symmetric paired mapping of letters (that is, if a given reflector maps X to Y, the converse is also true). These are combined such that a letter is mapped through three different rotors, the reflector, and then back through the same three rotors in reverse.

To avoid Enigma being a simple Caesar cipher, the rotors rotate (or “step”) between enciphering letters, changing the effective mappings. The right rotor steps on every letter, and additionally defines a letter (or later, letters) at which the adjacent (middle) rotor will be stepped. Likewise, the middle rotor defines a point at which the left rotor steps. (A mechanical issue known as the double-stepping anomaly means that the middle rotor actually steps twice when the left hand rotor steps.)

The German military Enigma adds a plugboard, which is a configurable pair mapping of letters (similar to the reflector, but not requiring that every letter is exchanged) applied before the first rotor (and thus also after passing through all the rotors and the reflector).

It also adds a ring setting, which allows the stepping point to be adjusted.

Later in the war, the Naval Enigma added a fourth rotor. This rotor does not step during operation. (The fourth rotor is thinner than the others, and fits alongside a thin reflector, meaning this rotor is not interchangeable with the others on a real Enigma.)

There were a number of other variants and additions to Enigma which are not currently supported here, as well as different Enigma networks using the same basic hardware but different rotors (which are supported by supplying your own rotor configurations).

How Typex works

Typex is a clone of Enigma, with a few changes implemented to improve security. It uses five rotors rather than three, and the rightmost two are static. Each rotor has more stepping points. Additionally, the rotor design is slightly different: the wiring for each rotor is in a removable core, which sits in a rotor housing that has the ring setting and stepping notches. This means each rotor has the same stepping points, and the rotor cores can be inserted backwards, effectively doubling the number of rotor choices.

Later models (from the Mark 22, which is the variant we simulate here) added two plugboards: an input plugboard, which allowed arbitrary letter mappings (rather than just pair switches) and thus functioned similarly to a configurable extra static rotor, and a reflector plugboard, which allowed rewiring the reflector.

How the Bombe works

The Bombe is a mechanism for efficiently testing and discarding possible rotor positions, given some ciphertext and known plaintext. It exploits the symmetry of Enigma and the reciprocal (pairwise) nature of the plugboard to do this regardless of the plugboard settings. Effectively, the machine makes a series of guesses about the rotor positions and plugboard settings and for each guess it checks to see if there are any contradictions (e.g. if it finds that, with its guessed settings, the letter A would need to be connected to both B and C on the plugboard, that’s impossible, and these settings cannot be right). This is implemented via careful connection of electrical wires through a group of simulated Enigma machines.

A full explanation of the Bombe’s operation is beyond the scope of this document – you can read the source code, and the authors also recommend Graham Ellsbury’s Bombe explanation, which is very clearly diagrammed.

Implementation in CyberChef

Enigma/Typex

Enigma and Typex were implemented from documentation of their functionality.

Enigma rotor and reflector settings are from GCHQ’s documentation of known Enigma wirings. We currently simulate all basic versions of the German Service Enigma; most other versions should be possible by manually entering the rotor wirings. There are a few models of Enigma, or attachments for the Service Enigma, which we don’t currently simulate. The operation was tested against some of GCHQ’s working examples of Enigma machines. Output should be letter-for-letter identical to a real German Service Enigma. Note that some Enigma models used numbered rather than lettered rotors – we’ve chosen to stick with the easier-to-use lettered rotors.

There were a number of different Typex versions over the years. We implement the Mark 22, which is backwards compatible with some (but not completely with all, as some early variants supported case sensitivity) older Typex models. GCHQ also has a partially working Mark 22 Typex. This was used to test the plugboards and mechanics of the machine. Typex rotor settings were changed regularly, and none have ever been published, so a test against real rotors was not possible. An example set of rotors have been randomly generated for use in the Typex operation. Some additional information on the internal functionality was provided by the Bombe Rebuild Project.

The Bombe

The Bombe was likewise implemented on the basis of documentation of the attack and the machine. The Bombe Rebuild Project at the National Museum of Computing answered a number of technical questions about the machine and its operating procedures, and helped test our results against their working hardware Bombe, for which the authors would like to extend our thanks.

Constructing menus from cribs in a manner that most efficiently used the Bombe hardware was another difficult step of operating the real Bombes. We have chosen to generate the menu automatically from the provided crib, ignore some hardware constraints of the real Bombe (e.g. making best use of the number of available Enigmas in the Bombe hardware; we simply simulate as many as are necessary), and accept that occasionally the menu selected automatically may not always be the optimal choice. This should be rare, and we felt that manual menu creation would be hard to build an interface for, and would add extra barriers to users experimenting with the Bombe.

The output of the real Bombe is optimised for manual verification using the checking machine, and additionally has some quirks (the rotor wirings are rotated by, depending on the rotor, between one and three steps compared to the Enigma rotors). Therefore, the output given is the ring position, and a correction depending on the rotor needs to be applied to the initial value, setting it to W for rotor V, X for rotor IV, and Y for all other rotors. We felt that this would require too much explanation in CyberChef, so the output of CyberChef’s Bombe operation is the initial value for each rotor, with the ring positions set to A, required to decrypt the ciphertext starting at the beginning of the crib. The actual stops are the same. This would not have caused problems at Bletchley Park, as operators working with the Bombe would never have dealt with a real or simulated Enigma, and vice versa.

By default the checking machine is run automatically and stops which fail silently discarded. This can be disabled in the operation configuration, which will cause it to output all stops from the actual Bombe hardware instead. (In this case you only get one stecker pair, rather than the set identified by the checking machine.)

Optimisation

A three-rotor Bombe run (which tests 17,576 rotor positions and takes about 15-20 minutes on original Turing Bombe hardware) completes in about a fifth of a second in our tests. A four-rotor Bombe run takes about 5 seconds to try all 456,976 states. This also took about 20 minutes on the four-rotor US Navy Bombe (which rotates about 30 times faster than the Turing Bombe!). CyberChef operations run single-threaded in browser JavaScript.

We have tried to remain fairly faithful to the implementation of the real Bombe, rather than a from-scratch implementation of the underlying attack. There is one small deviation from “correct” behaviour: the real Bombe spins the slow rotor on a real Enigma fastest. We instead spin the fast rotor on an Enigma fastest. This means that all the other rotors in the entire Bombe are in the same state for the 26 steps of the fast rotor and then step forward: this means we can compute the 13 possible routes through the lower two/three rotors and reflector (symmetry means there are only 13 routes) once every 26 ticks and then save them. This does not affect where the machine stops, but it does affect the order in which those stops are generated.

The fast rotors repeat each others’ states: in the 26 steps of the fast rotor between steps of the middle rotor, each of the scramblers in the complete Bombe will occupy each state once. This means we can once again store each state when we hit them and reuse them when the other scramblers rotate through the same states.

Note also that it is not necessary to complete the energisation of all wires: as soon as 26 wires in the test register are lit, the state is invalid and processing can be aborted.

The above simplifications reduce the runtime of the simulation by an order of magnitude.

If you have a large attack to run on a multiprocessor system – for example, the complete M4 Naval Enigma, which features 1344 possible choices of rotor and reflector configuration, each of which takes about 5 seconds – you can open multiple CyberChef tabs and have each run a subset of the work. For example, on a system with four or more processors, open four tabs with identical Multiple Bombe recipes, and set each tab to a different combination of 4th rotor and reflector (as there are two options for each). Leave the full set of eight primary rotors in each tab. This should complete the entire run in about half an hour on a sufficiently powerful system.

s2224834 (GCHQ, via GitHub)

To celebrate their centenary, GCHQ have open-sourced very-faithful reimplementations of Enigma, Typex, and Bombe that you can run in your browser. That’s pretty cool, and a really interesting experimental toy for budding cryptographers and cryptanalysts!

Evaluating the GCHQ Exceptional Access Proposal

This is a repost promoting content originally published elsewhere. See more things Dan's reposted.

…

In a blog post, cryptographer Matthew Green summarized the technical problems with this GCHQ proposal. Basically, making this backdoor work requires not only changing the cloud computers that oversee communications, but it also means changing the client program on everyone’s phone and computer. And that change makes all of those systems less secure. Levy and Robinson make a big deal of the fact that their backdoor would only be targeted against specific individuals and their communications, but it’s still a general backdoor that could be used against anybody.

The basic problem is that a backdoor is a technical capability — a vulnerability — that is available to anyone who knows about it and has access to it. Surrounding that vulnerability is a procedural system that tries to limit access to that capability. Computers, especially internet-connected computers, are inherently hackable, limiting the effectiveness of any procedures. The best defense is to not have the vulnerability at all.

…

Bruce Schneier

Lest we ever forget why security backdoors, however ~~weasely~~ well-worded, are a terrible idea, we’ve got Schneier calling them out. Spooks in democratic nations the world over keep coming up with “innovative” suggestions like this one from GCHQ but they keep solving the same problem, the technical problem of key distribution or key weakening or whatever it is that they want to achieve this week, without solving the actual underlying problem which is that any weakness introduced to a secure system, even a weakness that was created outwardly for the benefit of the “good guys”, can and eventually will be used by the “bad guys” too.

Furthermore: any known weakness introduced into a system for the purpose of helping the “good guys” will result in the distrust of that system by the people they’re trying to catch. It’s pretty trivial for criminals, foreign agents and terrorists to switch from networks that their enemies have rooted to networks that they (presumably) haven’t, which tends to mean a drift towards open-source security systems. Ultimately, any backdoor that gets used in a country with transparent judicial processes becomes effectively public knowledge, and ceases to be useful for the “good guys” any more. Only the non-criminals suffer, in the long run.

Sigh.

Nazi spies awarded fake medals after war by their MI5 controller

This is a repost promoting content originally published elsewhere. See more things Dan's reposted.

Two fascist spies were awarded fake Nazi medals after the end of the second world war by an MI5 officer who penetrated their secret network, a newly published book on wartime espionage has revealed.

Copies of German bronze honours for non-combat gallantry were commissioned from the Royal Mint and presented at a covert ceremony in January 1946 to both British citizens by Eric Roberts, a former bank clerk who spent years impersonating a Gestapo officer.

…

Owen Bowcott (The Guardian)

I love this. It’s the obvious end to the Double Cross system: giving the unwitting double agents you’ve turned fake medals “from” their own country so that they’re still in the dark about the fact that their handler isn’t on their side!

The Man Who Knew Too Much

This is a repost promoting content originally published elsewhere. See more things Dan's reposted.

His nuclear research helped a judge determine that former Russian spy Alexander Litvinenko had been assassinated – likely on Putin’s orders. Just months after the verdict, the scientist himself was found stabbed to death with two knives. Police deemed it a suicide, but US intelligence officials suspect it was murder…

BuzzFeed

One-Time Pad In Javascript

A few months ago, I spent one lunchtime writing a One-Time Pad Encryption/Decryption Engine in Javascript. I’d meant to blog about it at the time, but I forgot, but I came across it again today and thought it was cool enough to share with you all.

If you already appreciate why that’s cool, go play with it. If you don’t, allow me to explain.

What is a One-Time Pad and why is it awesome?

One-time pads are a form of cryptography which are simple enough to do by hand (you don’t need a computer, but it helps), versatile enough to transport any message, and – this is the clever part – completely unbreakable.

Yes, completely unbreakable. It doesn’t matter if you have a billion supercomputers and a billion years, a one-time pad is mathematically sound. So long as it’s used properly, it’s unbreakable, but it’s the difficulty and discipline required in using them properly – as well as difficulties in finding secure ways to share keys over long distances – that makes them impractical for widespread use.

They did, however, see a lot of use in espionage during the Second World War and the Cold War, and continue to be used today for some diplomatic messages, as well as occasionally by particularly paranoid civilians.

So what’s the story?

You’re probably familiar with the concept of a Caesar Cipher – you may have even played with them as a child – which is perhaps most-often seen nowadays in the form of ROT13. Put simply, a caesar cipher “rotates” letters through the alphabet, so perhaps A becomes B, B becomes C, C becomes D, and so on (in this example, Z would become A). So my message “IF YOU READ THIS YOU ARE GAY” becomes “JG ZPV SFBE UIJT ZPV BSF HBZ”. I can send that message to you, having already agreed with you the code, and you can roll each letter back by one (so A becomes Z, B becomes A, etc.), to get back the original message.

This is fundamentally flawed and offer no real security at all, of course. But suppose we made a couple of enhancements to our plain old Caesar Cipher. First, let’s add some punctuation to our alphabet (space, full stop, comma – we’ll treat these as letters in their own right which come after ‘Z’). Then, instead of rotating each letter in our message the same number of steps around, we’ll vary it. So let’s agree that the first letter will rotate 3 places, the second by 18, and the third by 11: then the fourth by 3 again, the fifth by 18, the sixth by 11, and so on. If we encode the same message now, we get:

I becomes L (rotated by 3)
F becomes X (rotated by 18)
[space] becomes I (rotated by 11)
Y becomes a comma (,)

And so on. Suddenly that’s a lot more secure than our plain old Caesar Cipher! Congratulations: you just invented the Vigenère Cipher. Unfortunately for you, it’s almost 500 years old already. Even more unfortunately, it’s still not very secure. It’s fine for passing notes in class, but it won’t do for sending orders to your agent on the other side of the Iron Curtain!

How is a One-Time Pad different?

The “key” to the cipher we used above is 3, 18, 11, and the problem is that the key ends up being re-used (repeated) throughout the course of the message. If the message was the word “ELF” (encrypted to “HAQ”), and we agreed never to use that same key again, then anybody who intercepted the message – even if they knew we were using a Vigenère Cipher – wouldn’t know what we’d said, except to say that it had three or fewer letters. We could equally have said “MAN” (using the key 8, 17, 8), “EAT” (using the key 0, 17, 14), or “EGG” (using the key 0, 23, 1). If we ever used the same key – 3, 18, 11 – again, our code would become vulnerable to frequency analysis, which is a technique for working out what the key might be based on the likelyhood of particular letters or words (especially common ones) being used in combination.

It’s pretty easy to see how to fix this: all you have to do is to choose a key that is at least as long as the message you want to encrypt, and never reuse the key.

This is how a one-time pad works. Suppose you and I agree a series of numbers, like this: 64191 25746 89891 93406 33604 89879. You keep a copy, and I keep a copy, and we never tell anybody else those numbers, or the order in which they appear.

When I want to send you a message, I first convert that message into a series of numbers, using a codebook or codetable. In the example codetable below – which has been optimised for the English language – the most-commonly used letters are represented by one digit each, while less-frequently used numbers are represented by two digits. So the message “STEAL THE PANTIES” becomes 82832 17890 83752 80148 33282. It’s important to remember that this still isn’t encrypted; it’s just encoded: turned into a format suitable for encryption.

If we often talk about “panties” in our messages (and who doesn’t?), we might add that word to our codebook to make it faster to write: for example, we might assign it the code “11” – in the table above, the prefix “99” means “look it up in the codebook”, so instead of writing “panties” as “80148 33282”, we’d write it as “9911” – cold war spies had whole dictionaries of most-common words assigned to numbers to make them shorter to write out! That makes our message: 82832 17890 83752 99110. In this particular implementation, we add a padding zero to make it up to a nice round block of five digits.

Next, we encrypt the message using our pre-arranged secret key, 64191 25746 89891 93406 33604 89879. To do this, we just take each digit in the message and add it to each digit in the key, ignoring any “tens” column. So 8 plus 6 is (1)4, 2 plus 4 is 6, 8 plus 1 is 9, and so on, to get our encrypted message.

All you have to do to decode it is run the whole thing backwards. From each digit in the message, deduct the corresponding value in the key – if you get any negative numbers, just add 10 to them so that they’re not negative any more. Then run the resulting encoded number through your codebook to get back the secret message.

In practice, using a codebook is optional, but very-highly recommended. In the basic codebook I’ve provided with my implementation, the word “condition” goes down from being “71547 23833 54” to just “99114 7”. A well-designed codebook will contain not only common words in your language, but anticipated words for the things that you expect to talk about in your messages (like “MISSION”, “CAPTURED”, and – of course – “PANTIES”).

Messages encrypted using one-time pads are so secure that it’s safe to send the message itself completely in the clear, which is exactly what we used to do. Especially during the cold war, but still today (and increasingly), governments have been able to communicate with spies in foreign countries simply by broadcasting strings of numbers over conventional radio, from what are called numbers stations by radio enthusiasts (and also by conspiracy theorists, of course). Of course, nowadays it’s perhaps more-feasible to send many kinds of messages by e-mail – and there are a number of one-time pad systems optimised for fully-computerised use, although there exists a greater risk of being traced online than by simply tuning in a radio.

Now: go have a play!

Click the link – One-Time Pad Encryption/Decryption Engine in Javascript – to try out my one-time pad engine and encrypt and decrypt a few messages of your own. It’s quite deliberately written in a way which does not communicate with my server at all, once the program has downloaded (unplug your computer from your Internet connection if you like, and you’ll find that it still works), so I’m not able to see what you’re encrypting. You can use your own codebook if you like, and the entire source code for the page should be reasonably easy to read, if you’re that way inclined. Have fun!

However, you certainly shouldn’t actually use it for passing secret messages around: read the caveats below if you can’t work out why for yourself!

Caveats

The first challenge with using one-time pads is finding a good secret key. People have used all kinds of things – patterns in music, entire text of books – that are all flawed and imperfect. The only secret key good enough for use in a one time pad is a cryptographically-random set of number. The random numbers generated by a conventional computer are not good enough: I suggest you get yourself five ten-sided dice and roll them all simultaneously, writing down the numbers which come up as they appear in front of you from left to right. Repeatedly. Yes, this is a boring process. For convenience, my implementation will generate random numbers for you, if you like, but they’re not good enough for actual use. The United States broke a German one-time pad in 1944 because the machine they used to generate the random numbers was not sufficiently random.
The second challenge is getting your secret key to the friend to whom you want to send secret messages. This must be done in person. If you transmit it by any other medium, it could already have been compromised. Even if you encrypt it, the system can only be considered to be as good as that encryption, which defeats the point entirely. During the cold war, KGB spies were issued with tiny keybooks like the one shown on the right. A book this small can be hidden in any number of places, as anybody who’s been geocaching knows! After receiving and decoding a message, the page used to provide the key could easily be burned, eaten, or otherwise destroyed.
A third challenge comes from the fact that no key must ever be re-used. As soon as a key is re-used, the code is no longer unbreakable. A combined U.S effort broke a 1945 Soviet one-time pad after the same key was used several times: once the U.S. knew something about the contents of some of the messages (they contained leaked British intelligence), they were able to partially break the key.
There must be no way for an unauthorised party to observe the plaintext before it has been encrypted or after it has been decrypted. Your desktop PC won’t do, because your enemy can read your screen through the wall, install a keylogger, or just peep through your window!
And, of course, as with all cryptography, your system is only as secure as the people involved. If your friend can be bribed, blackmailed, tricked or tortured into giving up information, the system fails. Obviously to maximise your ability to protect your system you should issue different keybooks to each of your trusted friends – this also helps to prevent them from talking to one another and organising a coup against you!

Further Reading

Wikipedia article on one-time pads.
A stronger Javascript key generator (still not strong enough for practical use, though)
A great explanation of one-time pads, also explains why books and music aren’t random enough to use as keys
Simple implementations of one-time pads in other programming languages
A good command-line one-time pad encrypter/decrypter written in Python
Shortwave Espionage / Secret Signals – a great (free, online) resource and e-book about numbers stations

ime P

Uncommon Occurances

I didn’t sleep well; I woke up several times throughout the night. On the upside, I have a strong recollection of three distinct yet inter-related dreams:

Dream I: Alex and the Accident

I came into work as normal and spoke to Alex, my co-worker. He’d been in some sort of car accident in which he’d hit and killed a man in an electric scooter. There was a lot of ambiguity about whose fault it was – the man had apparently accelerated his scooter right out into traffic… but Alex had been driving too fast at the time.

Significance:

My mum’s partner’s son, I recently learned, was in a car crash a week ago.
At work yesterday my boss was telling me about expensive repairs to his car.
I re-watched the shocking new don’t text and drive video yesterday.

Dream II – In The Red

I was a Western spy during the Cold War, attempting to infiltrate a Soviet University. With some difficulty, I was able to become enrolled at the University, but soon came under suspicion from the administrative management (all Party members, of course) after my luggage was found to contain a British newspaper. The newspaper contained details of Alex’s car crash, from Dream I, and this was later re-printed in the local newspapers, but with a suitably communist spin.

Later, after my cover was blown, I made plans to flee the country and return to the West.

Significance:

Second dream references the first dream.
The University campus was familiar; it was a little reminiscent of the University Of Worcester campus where I was at BiCon almost three weeks ago.

Dream III – Going To Work

I woke up, got dressed, and went to work. I discussed with co-workers Alex and Gareth a dream I’d had the previous night, in which Alex had crashed his car (as per Dream I) and about a film I’d seen the previous evening, about the infiltration of a Soviet University by a Western agent (as per Dream II). I explained that apparently the film was supposed to be about drugs, but maybe I’d failed to understand it because I didn’t see how it was supposed to be about drugs at all.

A client of ours paid a deposit on a reasonably-large job we’d quoted for, and I begun laying the foundations of the work as described in our technical specification.

Significance:

Third dream references the first two dreams, but as different media: one as a dream, the other as a film!
I’m expecting to get started on a new contract within the next couple of weeks, similar to the one referenced by the dream.

It was quite disappointing to be woken by my alarm and to discover that I still had to get up and go to work. While I’m usually quite aware that I’m dreaming when I’m dreaming, I somehow got suckered in by Dream III and had really got into the groove of going to work and getting on with my day, probably because I’d so readily assumed that Dream I was the dream and therefore that the same mundane things happening again must have been real life.

I was prompted to wonder, momentarily, if I might still be dreaming, when an unusual thing happened on the way to work. Just after I passed the site of the old post office sorting yard, about a third of the way to the office, I came across a woman crouched in a doorway, reaching out to a blue tit which was sat quite still in the middle of the pavement. Still half-asleep, I only barely noticed them in time to not walk right through them.

The bird must be injured, I thought, to not be flying away, as the woman managed to reach around it and pick it up. I stopped and waited to see if I could be of any use. Seconds later, the little creature wriggled free and flew off to perch on top of a nearby fence: it was perfectly fine!

The woman seemed as perplexed at this as I was: perhaps we both just found the world’s stupidest blue tit. I double-checked the clock on my phone (this is a reasonably-good “am I dreaming?” check for me, personally, as is re-reading text and using light switches) – but no, this was real. Just weird.

Edit: changed “Callbacks:” to “Significance:”. This is the format in which I’ll be blogging about the dreams I share with you now, I’ve decided.

Busy Days

[this post was damaged during a server failure on Sunday 11th July 2004, and it has not been possible to recover it]

[this post was partially recovered on 12 October 2018]

Yay! I won an eBay auction for a copy of Everyway. For £4! Yay! Winner! Now all I need are some friends, some paper, some pencils, and no dice.

In other good news, I solved a really nasty Project: Jukebox bug.

And finally: I’ve been spending way too long (when I should be revising) in Second Life. I’m currently working on trying to build the game world’s first Bluetooth-like short-range radio system, but while building prototypes I seem to have come up with a great espionage/surviellance device (i.e. a bug). It works really well. I’ve spent the afternoon listening in on people’s conversations. I intend to sell my bugging device for L$100 ($L = Linden Dollars, the currency of this virtual world), and then, when I’ve cornered the market, start selling a de-bugging device that can detect bug usage for L$500. I am one of those people, I have decided, whom; if I ran an anti-virus company, I would write viruses to ensure that people still needed my products.

I have one exam left. The …