As we’ve seen in the cryptarithm solver, a lot of auto-solver attacks are very time-consuming. And, if we’re using a tkinter GUI interface, after 5 seconds we’re going to get “program not responding” messages. This means that Transpo Solver is going to need a very similar approach to what I used in Crypta Solver, which was a timer in the center of the solver function, and a call to after() in the top-level gui.py file. Then, to pass data back and forth between these two levels, I want a class object acting like a data record.
In fact, the above structure can be used for auto-solvers for any cipher type, not just transpositions, but there will effectively be two groups of differences that we have to deal with. The first group addresses transpositions versus substitutions. The second is the differences within the solver functions themselves across cipher types.
If we look at substitution cipher types, we might have up to three or four methods of attack (with associated settings), while with transpositions there may be only one or two (generally speaking). I might increment through the full key space (1234 to 4321), or I could use a hillclimber to semi-randomly approach the correct numeric key by measuring the “fitness” of the results for transpositions. Or, with substitutions, I might try using every word in the wordlist as my key, and only print out the results that come closest to looking like my target language (e.g. – English), or I could randomize the alphabet and use an alphabetic hillclimber approach. Conversely, with the Vigenere family, I could use the Kasiski method to get the period of the cipher and take a semi-manual approach to finding the keyphrase interactively with the program.
What this all comes down to is the kind of data that needs to be passed between levels. Obviously, I need the message itself, and a solver method indicator (1 = bruteforce incrementer; 2 = wordlist; 3 = hillclimber; etc.) But, I also need to send start and stop widths for transpositions; plus return where I left off at timeout, and return the top 10 or so suggestions for the solved plaintext plus associated keys. Then, there may be cipher-specific data that only applies in one case.
One example of “cipher-specific” is Route Transposition. A brute-force attack would run through all of the routes (on-by rows, columns, diagonals, etc.; off-by rows, columns, diagonals, etc.; plus rotations, horizontal and vertical flips; and normal and reversed directions of the text). My non-GUI approach was:
For every string direction (normal and reversed):
.. For every on-by route:
.... For every flip type:
...... For every off-by route:
........ Decrypt the CON
........ Test for "fitness"
........ Display the most "fit" results
I’ve been using enums, in the form of:
for onby in enum_onby:
But that’s going to be awkward to modify if I have a one-second timer, and I have to interrupt and restart the for-loops in the middle all the time. Either I use straight numbers to identify the individual on-by and off-by routes, or I have to see if something like the following would work:
for onby in enum_onby[OnByDiags:]:
Regardless, storing the enum values in the record class object for Route transposition is a unique issue.
Looking at railfence, we’ve got two options – the text was written into the fence by zigzag and taken off by rows; or it was written in by rows and taken off by zigzag. This is similar to AMSCO, where the cipher starts by writing a single letter, then a pair, then single again; or by writing in a pair, a single then another pair. In comparison, we only need to worry about one option for Columnar (since complete and incomplete are the same thing to an auto-solver). However, with Myszkowski, as with most attacks on the keyword for substitutions, we need to remember where we left off in a wordlist. We can’t simply use:
for word in wordlist:
.. decrypt text with word
.. test result for "fitness"
.. quit function on timeout
Instead, we need something more like:
load start_point (start with 0)for ptr in range(start_point, len(wordlist)):
.. word = wordlist[ptr]
.. decrypt text with word
.. test result for "fitness"
.. if timeout, store ptr as next start_point
.... quit function
From a toplevel viewpoint, we have the following commonalities:
The user clicks the "Solve" button
Initialize the record object for the current cipher type
Call the decryptor method for the current cipher type
Wait until the decryptor solves the CON, times out or fails out
Check the return status in the record object
If the CON is solved, display the solution and the key, and mark the CON "done"
If no solution is found, mark the CON as "failed" somehow (or "skip")
If the decryptor timed out, use after(1 ms) to call the decryptor again, picking up where it left off based on the contents of the record object
The data record object can be common across most transposition types, excluding Grille and Swagman, which don’t have solvers yet. The other types can be shoehorned into one record structure:
Record[
cipher,
start_width,
stop_width,
key,
variant, # 0 or 1
status, # 0=Keep going, 1=solved, 2=failed
message, # Feedback to the user
high_cnt, # For tracking numbers of n-grams
solve_list # 10-20 solutions with large numbers of n-grams
]
For railfence, start_width and stop_width are the range points for the number of rails. Offset will start at 0 for each new rail value. Ignore key. Railfence ciphers may solve in under 10 seconds, so we might not need to interrupt processing in the middle. There’s no hillclimber for railfence.
For Route, use start_width to set the width of the complete rectangle. Use key for storing the enum value for on-by, if necessary. However, Route transposition ciphers may solve in under 10 seconds, so we might not need to interrupt processing in the middle. There’s no hillclimber for Route.
message allows the decryptor to communicate back to the user, such as by stating that the incrementer reached the end of the key without finding a solution, or showing progress by displaying intermediary key values.
Once all of this other stuff is in place, we need to address the decryptors. Generally, we could just take the make_template() functions from the encryption/decryption sections, and run the key incrementer against the template and match the output with unravel() and the gram_counter(). This would reduce the number of lines in the files since we’d be recycling code. The problem is that we may be running loops of 1 million or 10 million iterations, and constantly making function calls inside those loops will add perceptibly to the solver execution times.
There’s an argument that can be made that simplification and reuse of code shouldn’t get in the way of speed. This is doubly true of the hillclimbers, which can have bigger loop counts with averages of 10-20 minute execution times.
Anyway.
I’m right on the verge of writing the first transposition solver, which I think is going to be for Railfence, to be followed by Route, both because I expect them to run fast enough to NOT need timeouts. Before I start that though, I want to tweak the tkinter entry screen code to allow for the little customizations needed for things like Railfence, AMSCO and Route, and to activate or deactivate the Solve button for the types that don’t have solvers, such as Grille and Swagman.
It’s always something.
Next up: No idea
The Black Chamber 