Cryptanalysis with Reasoning Systems
chriskohlhepp.wordpress.com
chriskohlhepp.wordpress.com
___
(1) Download the single image for the puzzle: https://www.gchq.gov.uk/sites/default/files/grid-shading-puz...
(2) Read: In this type of grid-shading puzzle, each square is either black or white. Some of the black squares have already been filled in for you. Each row or column is labelled with a string of numbers. The numbers indicate the length of all consecutive runs of black squares, and are displayed in the order that the runs appear in that line. For example, a label "2 1 6" indicates sets of two, one and six black squares, each of which will have at least one white square separating them.
___
Source: "A Christmas card with a cryptographic twist for charity" (2015)
https://www.gchq.gov.uk/news-article/christmas-card-cryptogr...
___
SPOILER-1: The above puzzle links to other puzzles, which maybe found here:
SPOILER-2: GCHQ's solutions to all of the puzzles is here: https://www.gchq.gov.uk/directors-christmas-puzzle-answers
The pre-analysis in the derive-known-plaintext is particularly interesting because it's the key to making this tractable. But pieces are missing... Does anyone understand this well enough to explain what known-plaintext and matrix-match would be? I can't even work out their types with confidence.
Some findings:
- I was wondering why the linked blog post didn't show the results of derive-known-plaintext (what I call "preprocessing"). It turns out, this may be because this forward propagation solves the puzzle completely. There is no need for backtracking search, so there is no need for the whole fancy Screamer framework.
- Since preprocessing solves the problem completely, applying the constraints to its result to "finalize" the solution is instantaneous in Prolog. With Screamer this takes 3 seconds. Screamer doesn't seem to be all that impressive... At least not for this particular problem.
- In the case where there are no initial marks on the board, after preprocessing having marked almost everything, Prolog finds the four possible solutions in 0.037 seconds on my 2015 laptop. Preprocessing takes a second.
Let me know if you have questions!
https://github.com/chriskmanx/demystifycpp/blob/master/READM...
In the end I now left a comment at the overview post for this series of blog posts at https://chriskohlhepp.wordpress.com/2016/12/06/cryptanalysis... because comments seem to be disabled on the featured post itself.
https://chriskohlhepp.wordpress.com/reasoning-systems/specif...
Sure, though this particular example doesn't show its strengths very well. Your pre-analysis is so powerful that even in the case where you start with the empty board, any hand-written primitive brute force enumeration technique should be blazingly fast.
> I work in low latency trading, so I am happy to take any challenge from Prolog in C++.
I'm not saying Prolog is always faster than C++ or Common Lisp :-) I guess I'm saying that every embedding of a Prolog-like system in some other language I have seen so far was less powerful, less elegant, and much less performant than Prolog. This is only partly gloating from a Prolog fan. Another part of me would very much like to have better such systems integrated with other languages.
One drawback of Prolog, of course, is that Prolog can be a bit painful to interface with the rest of your application. Unless, of course, you write everything in Prolog...
One nit to pick with the terminology though: solving a cryptogram puzzle is _not the same thing_ as doing cryptanalysis, eg to determine what constitutes a weak DES key. Not even the same ballpark. ;)