Cryptanalysis with Reasoning Systems

Today I would like to start the third article in a series on reasoning systems and declarative, executable specifications: GCHQ 2015 Crypto Puzzle Analysed. The material I prepared for this article on the 2015 GCHQ crypto puzzle was mothballed nearly a year ago now – and surely GCHQ will host a new puzzle this year. To date, I have not examined other people’s solution strategies as this would have spoiled the fun for me. I set out to solve this problem differently. I wanted to build a general solver, one that would not rely on the hints GCHQ so generously provided in the form of pre-filled parts of the puzzle, one that would work for other puzzles and which would demonstrate how problems with significant analytical complexity can be solved using functional programming techniques.

This is part 3 of a 3 part series GCHQ 2015 Crypto Puzzle Analyzed. Part 1 is The Anatomy of a Puzzle. Part 2 is The Reasoned Lisper.

Advertisements

6 Comments

Filed under Uncategorized

6 responses to “Cryptanalysis with Reasoning Systems

  1. tom_mellior

    The forward propagation technique you implemented for the GCHQ puzzle in the derive-known-plaintext function is very interesting, but I was wondering how long it ran and how much it discovered. These details are missing in the post, so I implemented my own version in Prolog: http://pastebin.com/fLXKRKQ6

    I found that this “preprocessing” fixpoint search finds a complete solution, so no call to your break-puzzle would even be needed. Can you confirm?

    I also found that my solution is both shorter and faster than yours, but I just might be more used to logic programming in Prolog than you are used to logic programming in Lisp 🙂

    I posted some more remarks in the discussion on Hacker News: https://news.ycombinator.com/item?id=13349068

    (Also, did I miss anything or are no comments allowed on the post in https://chriskohlhepp.wordpress.com/reasoning-systems/gchq-2015-crypto-puzzle-full-analysis/ itself?)

    • Hello Tim, and thank you for taking the time to comment. I have not timed the derive-known-plaintext function but the number of solutions it provides depends on the amount on initial plaintext provided. Fixed point with the plain text furnished by GCHQ was 1 so you are right that the solution is total. Of course that would make the solution specific to that data set, something I was specifically trying to avoid. Leaving out the GCHQ furnished plaintext, yields multiple solutions. As for the Prologue solution being shorter, it may well be. My Prologue heralds back to uni, so forgive me if I won’t go there. Question would be, is it generic? Can the design pattern be applied to other algorithmic problems? That is rather what I was ultimately trying to pursue. See also https://chriskohlhepp.wordpress.com/reasoning-systems/specification-driven-programming-a-design-pattern/

      Comments are allowed.

      • tom_mellior

        Hi Chris,
        thanks for your answer. Yes, the usual way of writing Prolog program is generic in the sense that it follows (or, rather, *can* follow) a generate-and-test approach as you describe in your post on specification driven design. And thanks for confirming that your derive-known-plaintext function can solve the original puzzle completely. That’s a very nice and powerful technique that you use there!

      • Hello Tom, thanks also for taking the time to respond. I’d be interested to know if it is possible to represent imperative logic in Prolog. What I was striving for here was a deliberate layering of declarative logic (the specification) and imperative algorithm – much like Haskell separates side effecting from non side effecting abstractions through monads. The idea being that we can do both, declarative specification AND imperative logic (what I call the generator), but control how and where – hence ultimately deriving the design pattern for it.

  2. tom_mellior

    [This reply may be at the wrong nesting level, I think WordPress doesn’t want these threads to become arbitrarily deeply nested.]

    Yes and to to the question about imperative logic in Prolog. “No”, because Prolog doesn’t have loops and destructive variable assignments in the sense of most other programming languages; “yes”, because you can usually write down a very efficient tail-recursive formulation of the looping computation that will be executed as if it had been an imperative loop.

    Here’s the Fibonacci-up-to-N example:

    fibonacci_sequence(N, FibonacciSequence) :-
    fibonacci_sequence(0, 1, N, [], FibonacciSequence).

    fibonacci_sequence(A, _B, N, Sequence, Sequence) :-
    A > N,
    !.
    fibonacci_sequence(A, B, N, Sequence0, [A|Sequence1]) :-
    A =< N,
    C is A + B,
    fibonacci_sequence(B, C, N, Sequence0, Sequence1).

    This is somewhat similar to how it would be structured in Haskell or other functional languages: The "loop" is put into an auxiliary definition with extra arguments that are initialized to 0 and 1; inside the loop, you compare, compute, and recurse.

    And here is how you can use this in the Prolog REPL to find a solution to the sum-of-even-Fibonacci-numbers example:

    ?- fibonacci_sequence(4000000, Seq), findall(E, (member(E, Seq), E mod 2 =:= 0), Evens), sumlist(Evens, Sum).
    Seq = [0, 1, 1, 2, 3, 5, 8, 13, 21|…],
    Evens = [0, 2, 8, 34, 144, 610, 2584, 10946, 46368|…],
    Sum = 4613732.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s