logoalt Hacker News

notpachetyesterday at 11:49 PM2 repliesview on HN

Cipher noob question: is there any check that can be done to ensure a cipher is actually decodable? What if the author made a flaw when encoding it, so that it's not actually solvable?


Replies

schoentoday at 2:39 AM

My intuition is no, the family of cipher methods (even those that could be implemented by hand) is too open-ended, so there's no particular statistic that you could expect to see for all solvable ciphers and no unsolvable ciphers.

The definition of solving a cipher must be something like getting a highly meaningful result (like intelligible natural language text) by applying a process with relatively low Kolmogorov complexity relative to the length of the output. If you don't have a constraint like that, it could literally be meaningless what should count as a solution. For example, a cipher that was encrypted under a one-time pad can be successfully decoded to any plaintext just by choosing the appropriate key; there's no reason to prefer any plaintext over any other unless you have external knowledge that constrains the plaintext and/or the key. (That's what it means for the one-time pad to be information-theoretically secure, which is the lack of a constraint that helps distinguish a "good" solution from a "bad" solution.)

Basically you could say that every cipher is a transformation of a plaintext with some kind of computer program. (The human who invented the cipher may not have thought of it as a computer program, perhaps because computers hadn't even been invented yet, but there should be an equivalent program to the encipherment and decipherment process.) A good solution in that Kolmogorov complexity sense is like "a short program produced a meaningful decryption". There are statistical methods to recognize some kinds of plaintext, and there are statistical methods to recognize properties of specific ciphers (for example, to guess the most likely length of a Vigenère key), but it doesn't seem that this can inherently generalize across "all possible programs".

But if you want to limit the family of ciphers to specific things like Vigenère or Playfair or something, then yes, there are good statistical tests. It's just that it creates a higher-order question of how much flexibility the cipher creator could have had to choose a cipher method, conceivably including one that isn't attested anywhere, or one that has more good security properties of some kind than other classical ciphers did.

It seems like this will intersect with historical research, like "well, I don't think that so-and-so was actually sophisticated enough to literally create an interesting new kind of cipher from scratch, so therefore if this is a real message, it's probably one of these methods that would have been known in that cultural environment at that time and place", which maybe is enough of a constraint to have decent statistical tests. But we still have some idiosyncratic things like the Voynich Manuscript where experts have been fighting for decades over the baseline question of whether it's actually an enciphered human language plaintext!

The worst case problem is not even an error in encipherment but the idea that the apparent ciphertext could literally be random (chosen by throwing dice or spinning a wheel or drawing letter tiles or something), so there's no form of meaningful decipherment possible by any means, even with the original creator's knowledge.

elahiehyesterday at 11:56 PM

Without a third-party check, nope. Case in point, Chaocipher ... https://www.chaocipher.com/ e.g. see "Progress Report #23" the PDF there. Transcription errors galore!

This cipher context "rhymes" well with Kryptos K4 in many ways.

show 1 reply