Vinegar – refined Vigenère – can you break my cipher?

I’m idly interested in cryptography, the art of scrambling a message so that it can be transmitted securely, and only someone with the magic key can understand the message.

When I was young, I designed a cryptographic algorithm. I thought I was so clever, but just because *I* couldn’t break it, that doesn’t make it secure.

In this article, I present my naive cryptographic algorithm. It’s very flawed, so please don’t use it for anything important. Can you find the flaw?

This article will start with some background on substitution ciphers and the Vigenère cipher, which my method was based upon. Then, we’ll look at my big idea itself, Vinegar. To keep it interesting, there’s a little code breaking challenge as well. Enjoy!

How Etaoin Shrdlu defeated substitution ciphers.

Like most children, my first encounter with cryptography was a substitution cipher. A friend gave me a sheet of paper with each of the 26 letters and wacky squiggle next to each one. This would be our secret code. Replace each letter with it’s squiggle and it would just look like a bunch of squiggles.

We thought it was unbreakable, but it wasn’t. This sort of code can be cracked by knowing that E is the most common letter in English, so the most common squiggle in the hidden message is probably an E. The next most common squiggle is probably a T. Once you’ve covered the twelve most common letters in English; E, T, A, O, I, N, S, H, R, D, L and U;
♦ou ♦an easil♦ ♦or♦ out ♦hat the other ♦issin♦ letters ♦ould ♦e.

What we need is a cipher the produces a coded message with an equal mixture of symbols. Enter Vigenère.

The Vigenère cipher

Centuries ago, the choice of people who wanted to communicate in private was Vigenère. Here’s how it works.

          A 0
Z 25 B 1
Y 24 C 2
X 23 D 3
W 22 E 4
V 21 F 5
U 20 G 6
T 19 H 7
S 18 I 8
R 17 J 9
Q 16 K 10
P 15 L 11
O 14 M 12
N 13

(This was meant to be circular.)

The key to understanding a lot of cryptography is that the 26 letters of the English language can be used as numbers. On this chart, each letter has been given a number. Now, it’s possible to do simple calculations with letters. What’s C+C? The answer is E, because 2+2=4.

Don’t get excited, but you can do subtraction as well. K-H is D, because 10-7=3.

You may be wondering what should happen if you add past ‘Z’ or subtract past ‘A’. For our purposes, imagine the 26 letters on a clock face in a circle. On a normal clock, when a hand ticks past the 12, it moves onto 1, not 13. Its the same with the Vigenère clock of letters. After the letter ‘Z’, is the letter ‘A’.

Finally, because we’ve constrained our system to these 26 values, adding ‘B’ (1) turns out to be the same as subtracting ‘Z’ (25). Regardless of where you start, performing either +B or -Z will end at the same letter. In fact, all of the 26 possible additions will have an equivalent subtraction. You can find each letter’s pair on the chart by looking for the letter across from the other. ‘A’ and ‘N’ are self pairing; +A is the same as -A, and +N is the same as -N.

Working within this system, we can use this to encrypt secret messages. Imagine Bob and Carol wish to communicate in private, but the bad guys can read their messages. To stop the bad guys, Bob and Carol meet up in advance and agreed the code they will use future.

Later, Bob wants to send the message “But now you will die by chainsaw” to Carol. (He’s a fan of Internet cartoons.) Now we have the system of adding letters together, Bob can perform a simple calculation on each letter of the secret plain text message. He takes the previously agreed keyword, “WILHELM”, and adds each letter of the keyword to each letter of the plain text, repeating the keyword as often as needed;


When Carol receives the encoded message, she can get back the plain-text by subtracting the keyword.


Vigenère fixes the flaw with substitution ciphers because all the letter Es in the original message will all (mostly) come out as different letters.

Vigenère eventually fell out of use once a new flaw was discovered. Frequency analysis was still hiding there. If you know that the length of the keyword is 7, then you know that every 7th letter was encoded with the same letter from the keyword. So if you circle the 1st, 8th, 15th, etc letter of a long enough hidden message, the most frequent letter of those circled letters is probably an ‘E’, etc. Repeat for each group of letters 7 spaces apart and you can work out what the plain-text message was.

(How did we know the keyword was 7 letters long? There are ways. Wikipedia have an in-depth description but you don’t need to know how for this puzzle.) If you want to experiment, “Sharky” has a rather splendid web-app to perform the encoding and decoding.

Vinegar – Refined Vigenère

This is my improvement to the Vigenère cipher, which I called Vinegar. (Because that’s close to how I kept mispronouncing it.)

The problem with Vigenère is that the keyword is repeated, and that repetition exposed the vulnerability. What we need is a keyword that’s long without repeating, but small enough to be remembered.

Vinegar takes a 17 letter keyword and expands it to 210 letters. With that long 210 letter keyword, you can use Vigenère without having to repeat the keyword, and it’s the repetition in Vigenère that exposes it’s vulnerability.

Why 17? Because it’s the sum of the first four prime numbers. 2+3+5+7=17. We’ll use the keyword “WILHELMVONHACKENS” for this example.

Split the keyword up into groups of 2, 3, 5 and 7 letters. WI, LHE, LMVON and HACKENS.

Repeat each sub-key to make up 210 letters:


Because each group has a prime number length, the four groups will effectively expand into a 210 letter Vigenère keyword for the price of a 17 letter keyword. (210 is 2x3x5x7.) Add each column together to get the long key…


To avoid the Vigenère vulnerability, we can only use a 17 letter keyword once per 210 letters. So if you are encoding a longer message, use the last 17 letters of each 210 block for a new keyword to use for the next block of 210 characters.

So there’s my cipher. It has a flaw. Can you work it out? To try your hand, I came up with a random 17 letter codeword and expanded it to 210 letters. I then used that long key to encrypt my secret message. (My message is a little shorter than 210 letters, so I left some at the end un-used.) The plain-text is perfectly normal English. Spaces and punctuation are retained from the plain text.

Iwy seix zfvdzykjxm moebj dkaavmin vjkehleozp atir sdvwkvm cf hhbd vw gauj ty qzintte av mjbo xr xxnb whuieift, zaed jmioidh xv ts xtt elmv fg zok xgwnlpn vbues mp irmc twpb, yebhaoz rdlnrpbj jgg kzmlkyah vo dvta hn jzfxggaxcq.

Can you decode my message without the key? Post me a comment. Enjoy.

Picture Credits:
I’m lying by Taylor Dawn Fortune
Local Praire Dog Gossip by Art G
With grateful thanks to Richard Heathfield.

Google snooping WiFi? Don’t panic! Don’t panic!

Google have got into a bit of hot water when it emerged that while their cars drove around taking pictures for their Street View service, they collected and stored people’s private WiFi traffic. People have understandably got angry with Google for doing this, but I think some demystification is in order.

Did they collect my private data?

If your WiFi access point uses WPA with a good pass-key, don’t worry. Your network traffic is encrypted and is just noise without that pass-key.

If your WiFi is “open”, then anyone within range can collect and look at your network traffic. I would be more worried about that creepy guy in the van parked around the corner, maliciously snooping on you, spamming and browsing dodgy websites. Worrying about Google would be way down my list. Take this opportunity to switch on WPA on your access point. This article will still be here afterwards.

How come their camera cars collect WiFi data at all?

It can be used to supplement or replace GPS. Google are in the mapping and navigation business, and knowing where you are is essential to helping you get where you are going.

If you go out to some random spot in a built-up area and switch on your laptop’s WiFi gizmo, you’ll find several access points, both public and private, all with a variety of weird names. Make a list of those access points and their signal strength, compare it against a list of known access-points and their previously monitored location, do a few calculations and you’ll have your location.

No need for GPS electronics, just use the same WiFi electronics your laptop will have anyway.

That’s very nice, but even my WiFi address is private. They shouldn’t have collected even that.

Is it? By necessity, your WiFi access point has to broadcast it’s identity to the public in the clear. Your neighbours might be using WiFi too, possibly within range of your own laptop. When it hears something broadcast, it loads the packet and looks to see if its from an access point it knows about. It’ll be receiving lots of noise from your neighbours and silently throwing away anything it’s not interested in.

Now apply the principle that no-one else should even look at a packet’s identity. You’ll have no way of knowing which packets are yours and which are someone else’s unless you do look at the access points identity. It’s part of the protocol.

But they collected private traffic as well as just the access point’s identity. How could that be accidental?

Even when you are only interested in the identity of an access point, you need to collect a whole packet before it’s useful. The trouble is that radio on it’s own is subject to noise and interference. To fix this, the clever people that designed the WiFi protocols added a noise check. Before a packet is broadcast, some simple calculations are done on the content of the packet and the result is added on the end. The recipient takes the packet and performs the same calculation on the content. If the result the recipient ends up with is the same as the number on the end of the packet received, it can be reasonably sure the packet arrived without errors.

For this to work, the recipient needs the whole packet. If they only listened to first bit where the sender’s identity is stored, there is a risk of noise creeping in, masquerading as correct data.

But why did they store the whole packet after the error check has passed?

Very little of a software developer’s work is making things from scratch. Instead, we reuse and build upon work done in the past. We make reusable components that can be reused for different things.

I can only speculate here, but I imagine that when Google put this project together, they would have taken a generic WiFi receiver component which has been well tested and trusted rather than build an entirely new one. The packet is the natural unit of a WiFi receiver, so it would be expected that generic components designed to deal with WiFi traffic would store whole packets as a matter of routine.

Wouldn’t they have noticed a huge data file if they were only planning to store a fraction of what they did collect?

They would have been taking pictures and collecting many image files at the same time, so the space taken up by captured WiFi traffic would be a small proportion. Even if they were only collecting WiFi locations, the amount of storage that would be required in the field isn’t quite so predictable. Databases aren’t simple files where one item is stored one after the other, but are complex structures with indexing and redundant copies.

I imagine that if I were an engineer at Google and I wanted an estimate of how many hard disks to buy, I would send the car out on a short test journey and see how big the database is when it came back. Multiply that figure by however far the car will be going and that’s how much storage I’ll need. Hard disks are not that expensive these days, so spending engineer’s time working on reducing the amount of storage needed might not be a good economy.

Even so, collecting private network traffic is illegal. If I were caught eavesdropping, I probably wouldn’t get away with it.

(I’m not a lawyer, and this is not legal advice. If you take legal advice from a software engineer, you’re insane.)

If Google were taken to a criminal court over this, they could show that there was no intention to eavesdrop as I’ve outlined. If they take steps to securely destroy the additional collected data, no-one has been harmed here. Prosecuting this “crime” would be a petty reaction to a simple oversight.

But I don’t trust Google to not look at and abuse the collected private data.

If you’re not using WPA, your private data has been broadcast to all and sundry in range since you started using it, and you’re only worried now?

Picture credit: ‘Shot of Daventry area while cycling’ by… me!