Verifying the Substitution Cipher Folklore | Hacker News Reader

Verifying the Substitution Cipher Folklore

spinellis.gr

27 pointsnazri119 comments

You can break substitution ciphers pretty trivially, just using a simple hill climbing algorithm see http://practicalcryptography.com/cryptanalysis/stochastic-se...

If your cipher is at least 100 characters this will solve it very quickly.

Many misunderstand the classical lesson as "substitution ciphers are trivially broken by symbol frequency analysis", which isn't the point.

The point is to illustrate a property of a cipher that leaks information, in this case the symbol frequencies because the cipher preserves them. This is information that we don't normally consider valuable when working with plaintexts, but for crypto it's enormously valuable (i.e. it leaks a lot of information).

"I was expecting that this would yield an almost perfect result. In fact, the result still needs significant guesswork to decrypt."

I've never heard that substitution ciphers are simple to break using only letter frequencies. It does get you to a point where it makes the guessing a lot easier.

If you'd like to play with this yourself, it's #6 in the cryptopals challenges:

http://cryptopals.com/sets/1/challenges/6

I agree with the author: it's conceptually very simple, but a little tricky to code, even in the simplest case where you're relying on simple letter frequencies. You could probably do 10 good challenges on different ways to attack this problem, and towards the end you'd be getting into somewhat serious cryptanalysis: for instance, look at what Patterson and Al Fardan did with RC4.

The problems in set 1 are a little different, though. You get the important hint (which the author was missing) to use letter frequencies for a fitness function. But the cryptopals set 1 ciphers have tiny keyspaces that are easily searched exhaustively - a substitution cipher in general doesn't. To solve the author's problem you need to re-invent something like stochastic hill climbing.

He wrote like half the algorithm and then said it didn't work.

Seriously. With a simple genetic algorithm you can do significantly better. Considering 2-grams etc. It's nice that they decided to write up what they "learned" with this simple experiment, but they didn't try very hard. Or look at the literature.

Nobody is disputing that. If you think they are, you have misunderstood the article.

No, he implemented exactly the algorithm, and correctly noticed that it doesn't perfectly reveal the plain text because the letter distribution isn't fixed; it varies around some average.

A human would put in the top few letters and work out the rest with knowledge of english _words_, not with the rest of the letter distribution.

>"In fact, the result still needs significant guesswork to decrypt."

I have never heard anyone other than the author of this piece suggest otherwise. Ironically, this result is trivial. That said, I have a pretty serious classical crypto habit, so my conception of what constitutes 'crypto folklore' may be poorly calibrated.

I used simulated annealing, which is a non-obvious but fairly easy algorithm: https://github.com/Smaug123/ClassicalCiphers.jl/blob/master/...

I know plenty of CS undergrads who have broken the substitution cipher a part of a assignment. Saying it isn't trivial just because you couldn't do it foolish.

Did they break it using only single symbol frequency counts? Completely ignoring positional information? Because when a human breaks it by starting with frequency counts and then filling in blanks in words, that's a totally different ball game. Computers can definitely do it, but you need to put in more effort.

http://www-i6.informatik.rwth-aachen.de/unravel/

Does anyone know the history of where the word "trivial" started being used to mean "easy" instead of as "unimportant", like the author does here?

It drives me crazy - but perhaps I'm the one that's wrong. Is it correct to use "trivial" to mean "easy"?

I keep thinking it comes from people misunderstanding the meaning of "non-trivial", as in complex

When a math paper or textbook regards a proof as trivial, do they really mean "unimportant"?

Not being a native English speaker, that's where I got the impression that trivial meant easy/straightforward.

It literally means "of the trivium" (grammar, logic/dialectic and rhetoric) , or, more broadly, that which can be arrived at by straightforward argument, without further specialized knowledge (covered in the quadrivium). It can, but doesn't necessarily, mean either easy or unimportant. Is identity merely unimportant, or is it also easy? Is a long chain of logic either easy or unimportant merely because it's trivial?

In math, the word is used pretty much as a synonym for 'obvious'. But if you understand something well, it is obvious to you, which is why many results are called trivial by those who understand them.

A math professor I had once took a very, very long time to think about a question. After that, his first response was 'that is trivial', after which a quite long explanation followed.

Well, there are reasons why there are dictionaries and ethimology dictionaries: http://www.thefreedictionary.com/trivial http://www.etymonline.com/index.php?term=trivial it has usually two slightly different meanings, adopted more or less at the same time at the end of the 16th century in English. The actual meaning is not (in this context) "unimportant" and not exactly "easy", but rather - as I see it slightly different - "simple" in the sense of "commonplace" or rather "at the reach of the ordinary people". As well, non-trivial does not IMHO really mean "complex" but rather "beyond the reach of the ordinary people" or "needing some non-common reasoning or tools/methods to be reached", it is almost the same, but not exactly the same.

Reply on news.ycombinator.com