Cracking the Adventure Time cipher | Hacker News Reader

Cracking the Adventure Time cipher

aaronrandall.com

241 pointsaaronrandall24 comments

This seems like as good a time as any to bring up a question I've been wondering. I've seen enough examples like this to know that, for monoalphabetic substitution ciphers, frequency analysis is the way to go with attacking them. But what about ciphers that are just slightly more complicated than that, but nowhere near the strength of "real" crypto. How does one go about attacking these?

Like, imagine a cipher where you shift each letter once (modulo 'Z') for each character of the text thus far (e.g. "HELLO WORLD" becomes "HFNOS BUYTM"). I'm sure someone has a name for this that I don't know. This seems immune to frequency analysis (unless you have such a large ciphertext that you begin to notice recurring strings with 1/26th the probability of a monoalphabetic cipher), but still trivial enough that an experienced cryptanalyist should crack it immediately. My question is, how would they do it? What's the "next step" if frequency analysis fails?

The cypher you describe sounds like a weaker version of a Vignère cypher, which resisted cryptanalysis until 1863, after nearly three hundred years of use. The Wikipedia page has a decent description of how to cryptanalyse that sort of polyalphabetic cypher.

You're right, it looks like my scheme is equivalent to a Vignère cypher with "ABCDEFGHIJKLMNOPQRSTUVWXYZ" as the key, with the weaknesses thereof. Thanks!

You might be interested to read "Cryptanalysis: A Study of Ciphers and Their Solution", a 1939 (!) book by Helen Fouché Gaines. It covers a lot of these kinds of variants.

Great question :) Frequency analysis is actually still pretty useful for ciphers more complicated than a monoalphabetic substitution cipher. Take a polyalphabetic substitution cipher (similar to the one you described), where a key is used to determine the offset for each character. In this example the key is ABC:

Key: ABCABCABCABCA... Plaintext: MYNAMEISAARON... Ciphertext: MZPANGITCASQN...

At first glance, frequency analysis would be useless against this ciphertext. But if you can work out the key length (in this case, 3), you can group every 3rd character together and then perform frequency analysis on each group, as we know each group as been encrypted with the same key, making frequency analysis relevant again.

There's a fun (toy) crypto challenge I do every year for undergrad students, you can see the past problems here: http://www.cwu.edu/math/previous-challenges (I wasn't a big fan of the 2016 problems)

Don't sell yourself short. If you can write the Python code to work out the Pigpen key "VAMPIRE", you can break poorly-implemented AES, RSA, and ECC.

http://cryptopals.com/

Set #1 starts out with a simpler problem than Pigpen, and then a problem that's just barely harder than Pigpen, but that requires actual code and whose solution will also help you break repeated-nonce AES-CTR.

I started going through those somewhat recently and have really enjoyed it. Thanks for putting that together.

For anyone else looking for another one along the same lines, this is a good one too: http://overthewire.org/wargames/natas/natas0.html

OverTheWire is phenomenal. I've been recommending it since before it was OverTheWire. I believe it used to be called "PullThePlug". Great suggestion, anyway.

frequency analysis on a simple substitution type cypher should never fail.

it was close. but the trick is the frequencies on short messages only give you probabilities that a certain mapping is true.

but those probabilities are enough to shorten the potential mappings significantly (i.e. e is probably e or t, g is probably e or t). Combine that with a word match (does the result contain stop words such as - it not the etc)

and bam, game over.

This is just "yet another substitution cipher".

There's an automated program that does quite well: http://quipqiup.com/

Pasting in his first two strings (the "standard pigpen" letters) finds the solution in 5 seconds.

Very cool! Although it doesn't solve either of them perfectly for me (e.g. "HEY BUYS" instead of "HEY GUYS").

Would love to read more about how that tool works :)

http://quipqiup.com/howwork.php

That's very cool, but it doesn't correctly find the solution with the first string alone, it gives a wildly wrong answer (BEACH ASIONY MISE I WILLS BY WHO MY NEVER KISS HE-M UNDELIVE)

So don't trust that a system doesn't have a simple solution because an automated solver like doesn't provide a correct answer.

If you put them both in at once, the second output is 100% correct:

    VGYURYPEDFNCEPGEWELLPVNWRDCNFGMGXQEPPRGCBFIGLEMG. EQPMEIGQNVBAGBTFEGMSYNRKMNWEPBLWBYPSNWMQNFBDWEQVYNRCBFIGLEMG
    
    =>
    
    HEY GUYS I PROMISE I WILL SHOW UP MORE NEXT ISSUE MARCELINE. ITS NICE TO HAVE AFRIEND YOU KNOW IS ALWAYS DOWN TO RAP WITH YOU MARCELINE

Seems to be non-deterministic. Sometimes I get 'Hey Buys', sometimes I get 'Hey Guys', and sometimes I get:

   WEHXLHT I PROMITE IS IYYTWOSLP MORE FEUNITTLEMARVEYIFE. IN T FIVE NO WAKE AGRIEF CHOLD FOSITAY SAHT COSF NO RAPS IN WHOLMARVEY I FE

Yeah. It's not the best algorithm.

I looked for a while and http://www-i6.informatik.rwth-aachen.de/unravel/ seems to be state-of-the-art.

I just did something similar last week with the first puzzle from The Maze of Games, which I found through the sample for it in the current Humble Book Bundle (Puzzle Book Bundle)[2]. Although, I don't have any experience with cryptography, so I probably stumbled a bit more. It was fun though!

1: https://www.humblebundle.com/books/puzzle-book-bundle

In a similar vein, I liked this post (breaking the code from Kevin Mitnik's book "Ghost in the Wire"):

http://www.fabiensanglard.net/Ghost_in_the_Wires/index.php

By the way, the book is excellent!

Very cool - I recognised the Pigpen cipher immediately, as we used to use it all the time in my boy scout days back in the 70's. The process of figuring out the substitutions was very cool, and I might use this article as the basis for teaching my kids about cryptoanalysis...

The Pigpen symbols certainly are distinctive, recognising them helped me get started.

That's great to hear, hope your kids enjoy. Thanks!

Cryptanalyzing a small text with a weak cipher is pretty hard, but not impossible.

Of course, assuming you're not using a really super duper weak cipher like ROT13. Just moderately weak.

Does anyone know an open source tool for monoalphabetic (or polyalphabetic) substitution that can handle arbitrary dictionaries?

<ᄃᄀ⨆⩀ コ🝕רּ⩀!

Reply on news.ycombinator.com