18 ms·
Cryptanalysis with Reasoning Systems
- kodfodrasz 10y agoMost interesting read I had on HN this week. I suggest reading it end to end!
- tastythrowaway2 10y agothat's a great IDEA
- saycheese 10y agoIf you want to try solving the puzzle on your own, here's how to get started. ___ (1) Download the single image for the puzzle: https://www.gchq.gov.uk/sites/default/files/grid-shading-puzzle.jpg 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-cryptographic-twist-charity https://www.gchq.gov.uk/news-article/christmas-card-cryptogr... ___ SPOILER-1: The above puzzle links to other puzzles, which maybe found here: https://www.gchq.gov.uk/puzz https://www.gchq.gov.uk/puzz SPOILER-2: GCHQ's solutions to all of the puzzles is here: https://www.gchq.gov.uk/directors-christmas-puzzle-answers https://www.gchq.gov.uk/directors-christmas-puzzle-answers
- _e 10y agoDoes anyone know what the name of the color scheme the author is using in their terminal?
- mahmud 10y agoThat's the default emacs color scheme. The terminal is just SLIME. https://common-lisp.net/project/slime/ https://common-lisp.net/project/slime/
- _e 10y agothank you!
- deleted 10y ago[deleted]
- chriskohlhepp 10y agoAuthor here: Colour theme is "solarized dark" using Emacs.
- chriskohlhepp 10y agoCorrection, for that article I disabled the theme. The other poster is correct in that syntax highlighting is from SLIME.
- tom_mellior 10y agoThis is somewhat interesting, but some of the terminology is idiosyncratic ("lambda closures") to the point of being downright confusing ("attack vector"). 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.
- tom_mellior 10y agoOK, I took what I understood the idea of this preprocessing to be and implemented it in Prolog (257 lines including data and comments, maybe 100 lines of "real" code): http://pastebin.com/fLXKRKQ6 http://pastebin.com/fLXKRKQ6 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!
- saycheese 10y agoMy suggestion would just be to email the author; his email in the text of the link below and right above "Licensed under the GNU General Public License", but after the word email: https://github.com/chriskmanx/demystifycpp/blob/master/README.md https://github.com/chriskmanx/demystifycpp/blob/master/READM...
- tom_mellior 10y agoI was poking around for a GitHub page, a mail address, or a comment feature, but gave up more quickly than you did :-) 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-with-lisp/ https://chriskohlhepp.wordpress.com/2016/12/06/cryptanalysis... because comments seem to be disabled on the featured post itself.
- 60654 10y agoThat's a great example of using a problem solver system to solve a constraint satisfaction problem! It was a fun read. 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. ;)
- chriskohlhepp 10y agoAuthor here: Hello 60654, I fully understand the difference between cracking a run length encoding problem and finding weaknesses in DES. There are many tools at the disposal of a security analyst. Another would be CSP and FDR: https://www.google.com.au/url?sa=t&source=web&rct=j&url=http://www.cs.utexas.edu/~shmat/courses/cs6431/lowe.pdf&ved=0ahUKEwjSq9Xhu7TRAhWGmZQKHUWjDt8QFggZMAA&usg=AFQjCNGxf3ifVB-gnMR0CieJkcesGsyOow&sig2=05lPggciu8183tXLldnLqA https://www.google.com.au/url?sa=t&source=web&rct=j&url=http.... However, that article, like mine, goes to show how logic programming can very well be used to mount cryptanalytic attacks. It differs from quantitative statistical methods as these exploit different weaknesses. Qualitative vs quantitative. Most of the people with skills in the latter work in quantitative trading and hedge funds - including yours truly.
- 60654 10y agoThat's a great example of using a problem solver system to solve a constraint satisfaction problem! It was a fun read. 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. ;)