Patterson's Cipher for Jefferson – Challenge Solved After 200 Years (2009) | Hacker News Reader

Patterson's Cipher for Jefferson – Challenge Solved After 200 Years (2009)

cryptiana.web.fc2.com

43 pointsPetiver9 comments

> a specimen of such writing, which I may safely defy the united ingenuity of the whole human race to decypher, to the end of time

Turns out to have been rather optimistic. But I'd say that holding up for 200 years before yielding to a combination of modern mathematics and brute computational force that would have been utterly unimaginable to Patterson is still quite impressive.

Anything with probability and randomness tends to break my brain but I find it fascinating.

If I interpret the 200-years-late solution correctly, it relied to a large part on trial and error (like one "trick" is to focus on adjacent rows, which seems to be more of a "hunch" than a deep, mathematical strategy). Things like this make me wonder why so many modern encryption standards rely on "simple" mathematical concepts that are easily testable (even if testing might take a million years). Even if that's your base, why not throw some random algorithms on top, like swapping every 7th symbol, reversing the whole thing and then adding a random one in the middle. Wouldn't that immediately make it more tedious to decipher at not much of an additional cost? Is this done anywhere?

Is keeping the algorithm open but the keys secret not the premise of modern cryptography? The idea is that an open algorithm can be tested for venerabilities, while secret algorithms may actually be broken, but you may never know, making them dangerous.

It is done by amateurs who design "super secret encryption algorithms" that nearly always turn out to be trivially breakable.

I'll assume you don't mean this "random algorithm" you "throw in" to be secret, (otherwise see the other response) and instead you hope that complicating the algorithm to make cryptanalysis more difficult.

The thing is - You don't want cryptanalysis to be difficult! You want the world's cryptographic experts to look at your algorithm, immediately see the potential ways to crack it, and quickly find that none of them actually work.

A complex encryption algorithm is bad because there could be vulnerabilities hiding in the complexity. That "swapping every 7 symbol" could make it easier to crack by creating subtle patterns in the output.

Well, it depends on your needs. I imagine a one time encryption algorithm (ie not intended for reuse) could make good use of security through obfuscation or obscurity. This kind of strategy is essentially meaningless in the context of computers, the internet, and effort-free encryption that is mostly good enough.

Those types of strategies, tricks, don't work in practice. A foundational principle in security and cryptography is to assume an attacker possesses the entire design of your system except for the secret keys. So, just assume that an attacker knows your funny business every 7 characters. All they would do is strip it out.

All they would need to do is download your trial program, decompile it, and look at the decryption code. That takes seasoned people minutes to do.

I believe that small changes like this can make ciphers more secure in practice but are usually best avoided. The are several factors involved.

* Modern ciphers are carefully designed and random changes to the algorithm may weaken the cipher, by say shrinking the effective key space or leaking internal state information due to timing attacks. Without careful cryptographic analysis by experts, motivated to study the new changes over a period of months or years, it may be hard to anticipate the overall effect of the changes. This in an argument in favor of adopting the existing studied systems and implementations.

* Some types of changes can be safely made and may be worthwhile. For example, superencipherment by encrypting the output of one cipher with a different independent system and an independent second key is almost certainly going to make breaking the system harder. This, however, reduces the performance of the encryption and requires careful implementation for perhaps no gain over simply choosing stronger parameters (for example, rounds and key length) with a single system. Examples of superencipherment that have been successful include the system used by soviet agents known as the VIC cipher. Apparently, this cipher resisted attempts at decryption. (The VIC cipher combined two simpler ciphers a franctionated substitution followed by an interrupted columnar transposition. There was a nice explanation of this cipher in Scientific American that I read in the mid 1960's, but I can't find that reference. See [1].)

* Widely used encryption systems, say AES, have an inherent advantage because they are widely used. Multiple, widely vetted, implementations and use patterns have been studied and any breaks in the systems are likewise reported widely.

* Superencryption, when done correctly, does mitigate the risk of an unexpected development in cryptanalysis of one of the underlying systems. One of the involved ciphers could be broken, as we've seen over and over again in the history of cryptanalysis, in which case the second cipher would continue to provide protection.

* A random secret change to a cipher, say modifying a magic constant like Salsa20's nothing up my sleeve constant (search for "nothing up my sleeve" in [2]), is likely to make any script-kiddie hacker code used by random bad guys fail to break your personalized cipher. The problem then becomes, keeping your random change private. Once the cipher is used to communicate with others, the secret is no longer secret and is likely to get out. This is the basis for simply assuming that your adversary already knows your encryption algorithm.

* Finally, if your adversary is a state actor and the stakes are high enough, your random secret changes to some cipher probably won't stop them. See Schneier's blog [3].

[1] http://www.quadibloc.com/crypto/pp1324.htm

[2] https://en.wikipedia.org/wiki/Salsa20

[3] https://www.schneier.com/blog/archives/2015/08/mickens_on_se...

My understanding of the solution is a little different. The virtue of the cryptography scheme was that by adding pending characters carefully, it became useless to use frequency analysis of single letters. However, what the solution does is look for digraphs - pairs of letters like "th" or "qu" that are common in english. (And, placing low scores to unlikely digraphs like "dx".) Doing two rows at a time is just part of this strategy.

This type of transposition cipher has been easily cracked for decades.

Reply on news.ycombinator.com