Seven Languages in Seven Weeks - Prolog Day 3 Self Study

Time to catch up with Seven Languages in Seven Weeks! This is the last chapter on Prolog and here are the tasks:

• Modify the Sudoku solver to work on six-by-six puzzles (square are 3x2) and 9x9 puzzles
• Make the Sudoku solver print prettier solutions

Note: since I am using SWI Prolog instead of gprolog as used in the book, there are a few differences:

• :- use_module(library(clpfd)). this statement is used at the beginning to import the all_different/1 predicate.
• This predicate is used instead of fd_all_different/1 to check if all list elements are different.
• +Vars ins +Domain is used instead of fd_domain/2 to validate the domain of list elements.

Here's the solution for six-by-six puzzles:

:- use_module(library(clpfd)).
valid([]).
valid([H|T]) :- all_different(H), valid(T).

sudoku(Puzzle, Solution) :-
 Solution = Puzzle,
 Puzzle = [
  S11, S12, S13, S14, S15, S16,
  S21, S22, S23, S24, S25, S26,
  S31, S32, S33, S34, S35, S36,
  S41, S42, S43, S44, S45, S46,
  S51, S52, S53, S54, S55, S56,
  S61, S62, S63, S64, S65, S66
 ],
 Puzzle ins 1..6,
 Row1 = [S11, S12, S13, S14, S15, S16],
 Row2 = [S21, S22, S23, S24, S25, S26],
 Row3 = [S31, S32, S33, S34, S35, S36],
 Row4 = [S41, S42, S43, S44, S45, S46],
 Row5 = [S51, S52, S53, S54, S55, S56],
 Row6 = [S61, S62, S63, S64, S65, S66],
 Col1 = [S11, S21, S31, S41, S51, S61],
 Col2 = [S12, S22, S32, S42, S52, S62],
 Col3 = [S13, S23, S33, S43, S53, S63],
 Col4 = [S14, S24, S34, S44, S54, S64],
 Col5 = [S15, S25, S35, S45, S55, S65],
 Col6 = [S16, S26, S36, S46, S56, S66],
 Rect1 = [S11, S12, S13, S21, S22, S23],
 Rect2 = [S14, S15, S16, S24, S25, S26],
 Rect3 = [S31, S32, S33, S41, S42, S43],
 Rect4 = [S34, S35, S36, S44, S45, S46],
 Rect5 = [S51, S52, S53, S61, S62, S63],
 Rect6 = [S54, S55, S56, S64, S65, S66],
 valid([Row1, Row2, Row3, Row4, Row5, Row6,
  Col1, Col2, Col3, Col4, Col5, Col6,
  Rect1, Rect2, Rect3, Rect4, Rect5, Rect6]).

pretty_print(Puzzle) :-
 writef("\
 +-----+ +-----+\n\
 |%d %d %d| |%d %d %d|\n\
 |%d %d %d| |%d %d %d|\n\
 +-----+ +-----+\n\n\
 +-----+ +-----+\n\
 |%d %d %d| |%d %d %d|\n\
 |%d %d %d| |%d %d %d|\n\
 +-----+ +-----+\n\n\
 +-----+ +-----+\n\
 |%d %d %d| |%d %d %d|\n\
 |%d %d %d| |%d %d %d|\n\
 +-----+ +-----+", Puzzle).

How to enable IP Forwarding in Mac OS X

Another note to self: how to enable IP forwarding in Mac OS X:

sudo sysctl -w net.inet.ip.forwarding=1

(credit: Stack Exchange)

vortex3 (reloaded)

In the original vortex3 post, I wasn't able to reproduce the exploit since the vortex levels were recompiled with a newer version of gcc. Thanks to some hints from the vortex admins, I managed to solve the level using another approach. Here are my notes from github:

Obviously, the objective of this level is to overflow buf which will allow to overwrite lpp. In turn, buf's address will be written to wherever *lpp points to. By selecting an appropriate memory location for lpp, it will be possible to inject &buf as a function pointer into some data structure that will later execute it. I tried two approaches:

• Overwriting an entry of the .dtors section, which contains a list of destructors, each called subsequently before program termination.
• Overwriting an entry of the .plt/.got sections, the dynamic linking structure which resolves the position of shared library functions such as exit().

I guess the original intent to solve this level was to use the first approach, induced by the suggested reading material. In the mean time, the vortex wargames have been recompiled with a newer version of gcc and unfortunetaly, the .ctors/.dtors sections are no longer writable, as mentioned by the vortex admins. In a second notice, they suggest to brute force the 2^16 possible values and draw own conclusions. This resulted in 3 address values which led to a successful exploit: 0x0804928c, 0x080492cc and 0x08049306. Interestingly enough, these memory locations originate from a read/write memory location, where the program text is loaded. But the program text is actually executed from the 4k memory region starting at 0x08048000. Comparing the dumps of both regions 0x08048000-0x08049000 (read/execute) and 0x08049000-0x0804a000 (read/write), I realized that they almost match, the only differences several are unitialized memory addresses in the latter. From there on, I started reading about the loading process and dynamic linking in order to understand the meaning of this memory layout. I concluded that the raw program text is loaded in the higher memory region. During initialization, the loader copies its contents and completes missing references to several dynamic process structures such as the .got and the .plt starting at 0x08048000.

Following the pointers from 0x0804928c, we see that it leads to the .plt at 0x0804962c (exit@got.plt) and eventually to the exit() function from the dynamically linked libc at 0x0804830a (). Following the double indirection (**lpp), the .plt entry for exit() is therefore overwritten and program execution will jump to &buf instead of exit() when called at the end of the main function.

Neue Zürcher Zeitung Binary Issue

Last Friday, I was surprised to notice that the front page of the Neue Zürcher Zeitung's daily edition was scattered with nothing but zeros and ones. At first, I thought this had to be some kind of a printing defect, similar to the illegible raw output of a PDF. But then I realized that the gothic letters in the title were also affected by the anomaly; this couldn't be a mistake.

Sure enough, this was just a bogus cover page in front of the real title page to advertise the newspaper's new online archive. After manually decoding the first value 01001110 (N) together with the following 01011010 (Z) occuring twice, I knew the rest of the page couldn't be random, so I decided to unveil the hidden text...

First step was to get a digitized version of that newspaper issue. Scanning it wasn't necessary since it's available online. I then used tesseract, an OCR engine to retrieve the strings from the image file (note: this isn't even necessary since one can just copy-paste the contents from the PDF, but it's just more fun). Finally, I hacked the following ruby script to convert the binary data into characters:

#!/usr/bin/ruby

puts "converting file #{ARGV[0]}"
str = IO.read(ARGV[0]).gsub(/[^01]/, '')
puts str
for i in 0..str.length/8
 print str[i*8, 8].to_i(2).chr
end
puts

The result: the encoded texts correspond to the articles of the real front page. Of course, they had to be shortened to fit. I was a bit disappointed though not to find any easter eggs :( Still, it was a good distraction :)

LinkedIn Password Data Leaked

As reported by several security related online portals, a file with approx. 6.5 mio SHA-1 password hashes from LinkedIn users is currently circulating the web. I could easily get ahold of a copy of that 250 Mb file through bittorrent and realized that my password matched an entry :(.

Here's how you can check:

$ echo -n "password" | shasum
$ grep 5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8 SHA1.txt
$ grep 000001e4c9b93f3f0682250b6cf8331b7ee68fd8 SHA1.txt 
000001e4c9b93f3f0682250b6cf8331b7ee68fd8

As mentioned here, a subset of the hashes are marked with 00000, presumably to identify already cracked passwords. You should therefore check both variants as shown above.

If your password matches, you should change your LinkedIn Password asap and then change your passwords everywhere where you reused it (especially for popular platforms like Facebook, Google or Amazon).

Vortex Solutions on Github

I checked in my vortex solutions on github, check it out: github.com/antoinet/vortex.