Not all homophonic substitutions can be auto-solved

[daikon]

... we have software that can solve the 408 in a matter of seconds. People have hammered the 340 with all this great software for years and never cracked it. This would suggest it is not homophonic substitution.

I wanted to address this common misconception. It's seems there is a general assumption that any homophonic substitution can be automatically solved by currently available programs that implement hill-climb algorithms like ZKDecrypto and AZDecrypt. And I'm not talking about carefully crafted plaintext that doesn't have certain common letters (like passages from the novel "Gadsby"), or that has an abundance of rare letters, or a very high, or very low IoC. That's actually not the problem. Or plaintexts in languages other than English, as that's solvable too, obviously. But there is still a way to fool hill-climb algorithm quite easily. Here is an example cipher I've constructed to illustrate this problem. It is a straight homophonic substitution, without any tricks of any kind. Each ciphertext symbol translates to only one plaintext letter, and there are no additional transformations to the plaintext that need to be done to read it:

Code: Select all

9V[J%:;*S#K&_/$T'_A(
]#4$B)$%a0M$+USP<$`#
W,Q5L1a#Y-$&E2$$F#G3
9$.X:*N/#$_+VW#6J#=;
^C,T0ZD$^#HI`#R7K#>Y
?-P8L^A.^*QEJ4#a#@`#
U1<9#K^B+^,RFL5#a#=`
#S2:;#J$C#>#3<$D#[#9
$PG#6$Q'H7RO#8M#:^A-
^B?/$#X.@(P$*Z=)]C;%
IE[#+]F#^D,A&a#VG'``
_B(4K<)5L0>?1$%$26YH
&QZC9'IEND3FJ@#7^A-(
=#R[/8K)$#:%4L0T]G.>
#_*P^1$B2U[H&$$'IE]#
+[F#^C,(?#;D)b#35YA%
6J<9B&b#C'7K:G/b#$D(
$)8L%HI


It has a fairly normal plaintext too. In fact, it's a passage from one of the Zodiac letters I picked at random. The cipher has the exact number of unique symbols as Z340, and it's slightly longer at 347 letters, so it should be actually easier to solve. Yet, neither ZKDecrypto nor AZDecrypt can crack it at default settings. I've used the highest setting of "keys per cipher" for AZDecrypt and I let ZKDecrypto run for nearly an hour. I can see that it gets close at times, and I can even find a few correct words in the jumble of letters, but I can only see them because I know the plaintext. It is still generally unreadable otherwise (without knowing the plaintext).

It is by no means a clever way of constructing a cipher, and it should actually be fairly clear how I did it after manual analysis, but it does appear to fool automated cracking attempts. I'll post a hint tomorrow, if nobody solves it before then.

EDIT: It appears I misunderstood some of the options of ZKDecrypto, and how to use it in general. So I stand corrected, the cipher above *can* be auto-solved. But definitely not in seconds.

EDIT#2: See this cipher which proved to be truly unsolvable without manual analysis and careful merging of cycles.

[glurk]

daikon-

Is 10 minutes fast enough? I had to download it and run the program in that time, ofc.

Code: Select all

SFTDASSOMEDAYITMA
YHAPENTHATAVICTOM
MUSTBEFOUNDIVETOT
ALITTLEIISTOFSOCI
ETYOFFENDERSWHOMI
GHTWELLBEUNDERGRO
UNDWHOWOULDNEVERB
EMISSEDWHOWOULDNE
VERBEMISSEDTHEREI
STHEPESTULENTUAIN
UTENCESWHOWHRITEF
ORAUTOTRATHSALLPE
OPLEWHOHAVEFLABBY
HANDSANDIRRITATIN
GLAUGHSAILCHILDRE
NWHOAREUTINDATESA
NDIMPLOREYOUWITHI
MPLATTALITEOPLEWH
OARESHAKEINTHANDS
SHATEHANDSLIKETHA
TANDALL

I didn't do all corrections and etc., but that is pretty readable... The idea of ZKD was NEVER that it solve every single letter perfectly - no program can do that - but just get close enough to be readable and correctable. It does do that. Which was the point.

-glurk

[Mr lowe]

coolbananas

[daikon]

Is that from ZKDecrypto? Which version? Are you using it at default settings? I've tried both v1.0 and v1.2 and neither get to the clarity of your result. Am I not doing something correctly? After loading the ciphertext I go to "Key" -> "Init Key" then hit "Ok" without changing anything and then hit "Start". That is all, right?

[glurk]

Yes, from ZKD. And, well, I wrote the program. So I know how to use it better than most. I used 1.0 here too, but 1.2 is also available, but it is arguable which is best.

-glurk

EDIT: ZKD is not, and was NEVER meant to be a "press-it-and-forget-it" program, although it tends to work well in that respect. It's more of a workbench, but being totally honest, I didn't really DO any work here. I loaded the cipher you posted, ran the program, and saw a readable result in mere minutes. You saw the short time it just took me...

[daikon]

Yes, I'm aware you wrote ZKDecrypto. In fact, I was hoping this post would catch your attention. :) But you still haven't answered my question. Did you alter any of the default settings? Because as best as I can tell, this cipher can't be solved at default settings. Mostly because of the default homophone distribution that assumes that more frequent letters will get more homophones in the ciphertext and vice versa. And, as you probably already guessed, I've tried to get away from that assumed distribution as much as possible in the cipher above. Which seems to be the case for Z340 as well, because we have a big frequency spike for "+", and I don't think anyone was able to come up with a good explanation for it.

[glurk]

I changed no defaults here. But with that said, the ZKD program saves its defaults, if changed, in a file ZODIAC.INI

You can delete that file, ZODIAC.INI in the program folder, and it will restart with the built-in settings. I may have changed mine at some point. I'm certain that I have mine set as:

Code: Select all

plain = C:\Users\USER\Desktop\zkdecrypto\
fail = 30000
swap = 5
revert = 400
use = 15
line = 17
lang = 0
minword = 4
maxword = 20
extra = ABCDEFGHIJKLMNOPQRSTUVWXYZ

-glurk

EDIT: I think you are NOT using the "extra letters" option, which is very important.

EDIT 2: In fact, the importance of the "extra letters" was quite understated in the documentation, but no one wanted to write instructions or docs. It's lucky that they exist at all, LOL.

[daikon]

I've compared my INI file with yours, and the only 2 differences are: your fail count is set way higher than the default (30,000 vs the default 2,000), but I suppose that's ok, we do want it to run as long as possible. However, the more important difference is that your "extra" line is set to all letters. Mine (and the default setting) is no letters at all. And that's what makes the difference in solving my constructed cipher above. When I manually change it to full alphabet, ZDK gets to the correct plaintext fairly quickly. Can you please explain what it is for and why it is not set to full alphabet by default? I suppose I can always check the source code, but it'll probably be quicker to ask the author of the program. :)

[glurk]

I'm happy to answer, but let me get some stuff off my chest, this is directed at no-one in particular.

I am the original author of the ZKD "solve-engine" - the part that solves the ciphers. And I'm still around.

Two other programmers did most of the work on the Windows GUI. I don't really do GUI / Windows works, I am more of a command-line Unix based programmer.

NONE of us wanted to write documentation. Hell, no one does. And the program, over 5 years, kept changing! Everyone was adding their own stuff. In truth, it was lucky to come together as well as it did.

BUT it's a free program, as in no monetary charge, and also free as in that the entire program is open source, and freely available.

So, I'd say first to read the source code, if you can. But think of this - if a homophonic cipher has 26 total letters at most in the plaintext, but 63 symbols, how many alphabet letters would you want to be able to cover the homophones? At LEAST the number of symbols in the cipher - 63. Plus at least one more alphabet - 63 + 26. It is possible to add more, of course.

-glurk

EDIT: The honest fact is that the program COULD have ended up better than it did. But hell, man, three of us spent 5 years on it for no pay, no real recognition, or anything else. It is what it is. And if you USE it well, it works well. It is a tool. And it's even a changeable, malleable tool. I don't know what else to say. I never got one penny for the years of work, but never asked for one either. It was just meant to be useful. I'm glad that the man who invented the wheel wasn't on a MB having to answer questions on how to use it.

[daikon]

glurk,
Don't get me wrong, I'm not saying anything bad about ZKDecrypto! It's an awesome and very useful tool and your contribution to solving this puzzle is immense. Especially considering it is a free program. The point I was trying to make (quite unsuccessfully at that though) is that the hill-climb algorithm isn't guaranteed to solve every homophonic substitution cipher. The issue, I suspect, is in the way it works. Basically, if there is no hill to climb, it won't be able to arrive at the solution. For example, if the solution field looks more like a very steep spike surrounded by a deep crevasse, if you will, the hill-climb algorithm will likely miss it. That's why it can't be used to solve modern encryption schemes -- the solution field for those looks like random white noise with a very narrow spike right at the correct plaintext. So I tried to construct a similarly behaving cipher using a straight homophonic substitution, but it seems it's not as easy as I thought.

The reason I'm doing this is not to poke holes in ZKDecrypto! Not at all. That was furthest from my mind. I'm just trying to think like Zodiac. To see if I can come up with a cipher that's as hard to crack as Z340 and maybe in the process I'll learn something about how Z340 was constructed in the first place. Not that he had any way of predicting how computers will be used to try to crack his ciphers, but who knows, maybe he simply got lucky and found a way to construct very hard to crack cipher, even for modern computers.