Hacker News Reader

Comment by Analemma_ | Hacker News Reader

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?

View on HN

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.

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)

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.

Reply on news.ycombinator.com