hashed-potatoes-with-salt - Tumblr blog

hashed-potatoes-with-salt · 21 days

Text

An Overview of The Nihilist Cipher

Hello! If you're someone interested in ciphers, read ahead to learn a little about one of my long time favorite ciphers, the Nihilist Cipher.

The Nihilist cipher is a polyalphabetic substitution cipher, which basically means it relies on multiple shift ciphers applied to different letters in the text being encoded. If you're familiar with the Vigenère Cipher, Nihilist is pretty similar in a lot of ways.

I'll go through some history of the cipher, how to encode/decode using it, and how to conduct a known plaintext attack on it. I'll also go over how you might approach attacking it without a known plaintext (mainly because I think it's cool), but it won't be the main focus.

History

The Nihilist Cipher was first used by Russian nihilists against Russia's tsarist regime in the late 19th century. It's since been used as a basis for several ciphers with improved security used in WWII, notably the VIC cipher which is essentially an extremely complex hand-encoded cipher that's part of the Nihilist family.

"If [the VIC] cipher were to be given a technical name, it would be known as a 'straddling bipartite monoalphabetic substitution superenciphered by modified double transposition.'" David Kahn, Number One From Moscow

Usage

Encoding a message requires two things: A key and a Polybius square, known by you and the person you're communicating with. A Polybius square is one of these guys:

To use the cipher, you must first convert the plaintext into a numeric representation by mapping each letter to a number using the square. The mapping follows a (row, column) scheme, so the letter 'T' in the above square would become '45'. You'll notice that the square is 5x5, meaning there is 1 less square than there are letters in the English alphabet! This is typically solved by either choosing a square to represent 2 letters, differentiated using context by the receiver, or by simply leaving off an unused/infrequently used letter (often Q). It's also common to place a word at the start of the Polybius square, in this case "EXAMPLE" to offset the alphabet and avoid the mappings becoming trivial and obvious to attackers.

After we convert the plaintext to it's numeric representation, that's when the key becomes important. We first encode the key we picked using the Polybius square (i.e. the key MATH would become 14 13 45 32). Then, we repeat the key along the plaintext, and add each plaintext value to the key value to get the ciphertext!

To decode, the receiver must simply repeat the encryption process in reverse: repeating the key across the ciphertext, subtracting the key values, and translating the numeric plaintext back into English text. Because the encryption and decryption processes use the same key, the Nihilist Cipher is considered symmetric.

Known Plaintext Attack

Now we get into the fun part: How can we decode Nihilist encoded text without knowing the key? We will assume we know some ciphertext and the plaintext associated with it. Therefore, our goal is to use what we know to reveal the key, and use the key to decrypt the rest of the cipher. For example, assume we know that the first line of the Bee Movie script, "According to all known laws of aviation", results in the ciphertext "37 66 67 64 35 68 48 53 75 66 57 66 56 84 84 32 57 95 25 84 66 73 36 86 45 65 94 55 37 88 48 85 54".

Since the ciphertext is simply the result of adding the key to the plaintext, to find the key we only need to do the reverse and subtract the plaintext from the ciphertext!

Even with only this short segment, we can see the repeating key is "14 42 43 21 14 43". Now we can repeat this key across the whole message and decrypt the Bee Movie script into numeric encoded plaintext.

At this point, you might be realizing where the next challenge lies. Unless you happen to be in a situation where you don't know the key yet somehow do know the Polybius square, this alone doesn't tell us very much! Since we've essentially converted our original problem into a simple substitution cipher, this is where we employ frequency analysis to figure out which number maps to which letter in the Polybius square. If you're up for a challenge you can do this manually, or use an online tool to analyze the frequency of each number and compare it to how often each letter of the English alphabet appears in typical text. Eventually, you'll be able to decode the Polybius square as the square below.

Ironically, the first snippet of The Bee Movie which we knew the plaintext of includes no 'E's, which are the most frequent letter in the English language, but letter frequencies of the full text would end up being much closer to the expected letter proportions.

Congratulations! You've now completed a plaintext attack on the Nihilist cipher and can sit down with a cup of tea for a bit of light reading .

Ciphertext-Only Attack

Now maybe that was too easy for you. Maybe you're a pro cipher-cracker, and you want to decode the Nihilist cipher without some "plaintext crutch". Here's how you can try to approach it! This method will need a large amount of ciphertext available, and relies on statistical analysis, plus some exploitation of the cipher's design to crack it.

The majority of this attack follows the same approach as a statistical attack on the Vigenère cipher. First you determine the key length by testing various key lengths, splitting the text up into groups that would be encoded with the same key, and computing the index of coincidence, which will be high (close to 0.068, the index of coincidence of English text) when the guessed key length is correct.

At this point, if this were the Vigenère cipher, we would have to go on to analyze the mutual index of coincidence between groups of ciphertext characters with the same key shifted by various amounts, but flaws in the Nihilist encoding system mean there's a good chance we can identify the key without this step!

Because of the way the Polybius square is set up, and the lack of modular arithmetic in the encoding method, every key letter value has exactly 25 possible ciphertext numbers that can result from that key. By comparing the ciphertext values encoded with the same shift, we can quickly identify or at least significantly narrow down the shift used to obtain those values! There are even a few cipher text values that immediately reveal what key was used to generate that cipher text (For example, a cipher text value of 30 can only be obtained using key=15). For a full list of possible ciphertext values generated by each key, check out this document I put together.

And that's it!

You are now a certified expert in all things Nihilist cipher. Go forth and use your new skill responsibly, leaving behind cryptic messages everywhere you go.

Happy decoding!

Sources:

https://www.cia.gov/resources/csi/static/Number-One-From-Moscow.pdf https://en.wikipedia.org/wiki/VIC_cipher

https://cyberw1ng.medium.com/nihilist-cipher-an-in-depth-look-at-the-cryptographic-technique-2023-b05b83551957

https://courses.cs.washington.edu/courses/cse163/20wi/files/lectures/L04/bee-movie.txt

#cryptology #number theory #ciphers #math #mathblr #people from my cryptology class haiiiiii

5 notes · View notes