Aperi’CTF 2019 - Sudo ku
Challenge details
| Event | Challenge | Category | Points | Solves |
|---|---|---|---|---|
| Aperi’CTF 2019 | Sudo ku | Steganography | 250 | 1 |
You wanna play a game ? Then follow the rules.
Challenge:
- TheGame.png - md5sum: 5e2ad60deaf4bca8359030a0ba8a0b50
- YouLoose.jpg - md5sum: 5d4ccd32191d7dd6bb5823bab4e3b528
Resources:
- [Steganography using Sudoku Puzzle.pdf](/files/aperictf_2019/sudo_ku/Steganography using Sudoku Puzzle.pdf) - md5sum: d9422e48a7931bc073ac1a35703176ea
TL;DR
Use sudoku solver to get each sudoku solutions of YouLoose.jpg. Read the paper and implement the extract scheme. Test extract scheme on each solutions.
Methodology
Whirlpinch
We got multiple files and an help (resources). One of the file is a sudoku which had a swirl effect. To remove it, open the file YouLoose.jpg with gimp or photoshop and apply the reversed effect. In gimp: Filters > Distorsion > Whirlpinch. Then set the rotation value to -720,00.
Then export/save the file.
Solve sudoku
If you attempt to solve the sudoku you’ll propably notice that there is multiple solutions for it. To get each solutions, we’ll use a sudoku solver. I found this sudoku solver which I ported to python3 (because I wanted a python3 solution).
I decided to write the following script to get each solutions:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# http://infohost.nmt.edu/tcc/help/lang/python/examples/sudoku/
# (Ported to python3)
from sudosolver import *
s = "..4...3.." \
".8...2..9" \
"7..9...6." \
"..879...." \
"2..4.6..3" \
"....319.." \
".3..69.18" \
"1..8...3." \
"..6...2.."
SOLUTIONS = []
def addToSolutions(x):
"""
SudokuSolver solutionObserver handler
Add each matrice solution to SOLUTIONS
"""
global SOLUTIONS
M = []
for rowx in range(9):
l = []
for colx in range(9):
cell = x.get(rowx, colx)
l.append(cell)
M.append(l)
SOLUTIONS.append(M)
slv = SudokuSolver(s, solutionObserver=addToSolutions)
slv.solve()
for num, sol in enumerate(SOLUTIONS):
print("[Solution n° "+str(num+1)+"]")
print(sol)
Output:
[Solution n° 1]
[[9, 1, 4, 6, 5, 8, 3, 2, 7],[6, 8, 3, 1, 7, 2, 4, 5, 9], [7, 2, 5, 9, 4, 3, 8, 6, 1], [3, 6, 8, 7, 9, 5, 1, 4, 2], [2, 9, 1, 4, 8, 6, 5, 7, 3], [5, 4, 7, 2, 3, 1, 9, 8, 6], [4, 3, 2, 5, 6, 9, 7, 1, 8], [1, 5, 9, 8, 2, 7, 6, 3, 4], [8, 7, 6, 3, 1, 4, 2, 9, 5]]
[Solution n° 2]
[[9, 1, 4, 6, 5, 8, 3, 2, 7], [6, 8, 3, 1, 7, 2, 4, 5, 9], [7, 2, 5, 9, 4, 3, 8, 6, 1], [3, 6, 8, 7, 9, 5, 1, 4, 2], [2, 9, 1, 4, 8, 6, 5, 7, 3], [5, 4, 7, 2, 3, 1, 9, 8, 6], [4, 3, 2, 5, 6, 9, 7, 1, 8], [1, 7, 9, 8, 2, 4, 6, 3, 5], [8, 5, 6, 3, 1, 7, 2, 9, 4]]
[Solution n° 3]
[[9, 2, 4, 6, 1, 8, 3, 5, 7], [6, 8, 5, 3, 7, 2, 1, 4, 9], [7, 1, 3, 9, 5, 4, 8, 6, 2], [3, 4, 8, 7, 9, 5, 6, 2, 1], [2, 9, 1, 4, 8, 6, 5, 7, 3], [5, 6, 7, 2, 3, 1, 9, 8, 4], [4, 3, 2, 5, 6, 9, 7, 1, 8], [1, 5, 9, 8, 2, 7, 4, 3, 6], [8, 7, 6, 1, 4, 3, 2, 9, 5]]
[Solution n° 4]
[[9, 2, 4, 6, 1, 8, 3, 5, 7], [6, 8, 5, 3, 7, 2, 1, 4, 9], [7, 1, 3, 9, 5, 4, 8, 6, 2], [3, 6, 8, 7, 9, 5, 4, 2, 1], [2, 9, 1, 4, 8, 6, 5, 7, 3], [5, 4, 7, 2, 3, 1, 9, 8, 6], [4, 3, 2, 5, 6, 9, 7, 1, 8], [1, 5, 9, 8, 2, 7, 6, 3, 4], [8, 7, 6, 1, 4, 3, 2, 9, 5]]
[Solution n° 5]
[[9, 5, 4, 6, 1, 8, 3, 2, 7], [6, 8, 1, 3, 7, 2, 4, 5, 9], [7, 2, 3, 9, 5, 4, 8, 6, 1], [3, 6, 8, 7, 9, 5, 1, 4, 2], [2, 1, 9, 4, 8, 6, 5, 7, 3], [5, 4, 7, 2, 3, 1, 9, 8, 6], [4, 3, 2, 5, 6, 9, 7, 1, 8], [1, 9, 5, 8, 2, 7, 6, 3, 4], [8, 7, 6, 1, 4, 3, 2, 9, 5]]
There is 5 possible solutions for this sudoku.
Note that https://www.dcode.fr also have a sudoku solver:
PDF Paper
Since the challenge ask us to follow the rules, we’ll try to follow the paper “Steganography using Sudoku Puzzle” given in resources. This paper is about a steganography methode using solved sudoku and image.
We’ll take TheGame.png image as our payload to hide:
In the process, the user has to compute a matrix named “reference matrix” which is the sudoku solved, duplicated to fill the size of the hidden image.
Here our image has the following size: 420*696. We have to duplicate our sudoku matrix in x and y to have a reference matrix with the size of 420*696.
Here is an example: if our solved sudoku had the size of 3*3 and contain only letters (usually 9*9 containing digits):
| a | b | c |
|---|---|---|
| d | e | f |
| g | h | i |
Then, with an image with the size of 11*11, we would have computed the following reference matrix:
| a | b | c | a | b | c | a | b | c | a | b |
|---|---|---|---|---|---|---|---|---|---|---|
| d | e | f | d | e | f | d | e | f | d | e |
| g | h | i | g | h | i | g | h | i | g | h |
| a | b | c | a | b | c | a | b | c | a | b |
| d | e | f | d | e | f | d | e | f | d | e |
| g | h | i | g | h | i | g | h | i | g | h |
| a | b | c | a | b | c | a | b | c | a | b |
| d | e | f | d | e | f | d | e | f | d | e |
| g | h | i | g | h | i | g | h | i | g | h |
| a | b | c | a | b | c | a | b | c | a | b |
| d | e | f | d | e | f | d | e | f | d | e |
#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# http://infohost.nmt.edu/tcc/help/lang/python/examples/sudoku/
# (Ported to python3)
from PIL import Image
from sudosolver import *
s = "..4...3.." \
".8...2..9" \
"7..9...6." \
"..879...." \
"2..4.6..3" \
"....319.." \
".3..69.18" \
"1..8...3." \
"..6...2.."
SOLUTIONS = []
def addToSolutions(x):
"""
SudokuSolver solutionObserver handler
Add each matrice solution to SOLUTIONS
"""
global SOLUTIONS
M = []
for rowx in range(9):
l = []
for colx in range(9):
cell = x.get(rowx, colx)
l.append(cell)
M.append(l)
SOLUTIONS.append(M)
def sudokuToRefMatrix(s, w, h):
"""
Convert sudoku "s" to a reference matrix with
size of "size"
"""
M = []
for i in range(h):
M.append((s[i % len(s)] * ((w//9)+1))[:w])
return M
slv = SudokuSolver(s, solutionObserver=addToSolutions)
slv.solve()
imgSrcName = "TheGame.png"
imgSrc = Image.open(imgSrcName)
w, h = imgSrc.size
for num, sol in enumerate(SOLUTIONS):
print("[Solution n° "+str(num+1)+"]")
refMatrix = sudokuToRefMatrix(sol,w,h)
print(len(refMatrix))
print(len(refMatrix[0]))
[Solution n° 1]
696
420
[Solution n° 2]
696
420
[Solution n° 3]
696
420
[Solution n° 4]
696
420
[Solution n° 5]
696
420
We do not display each matrix but they are correct. Now here is the extract process:
- The 9 first pixels contains the size
nof the hidden data. Looking at the image, the 8 first pixels are black (0 value) and last is blue. Size is coded in binary mode (big endian) on 9 first pixels. - The next
npixels containsnpositions in the reference matrix (x abscisse is coded on green channel and y on red channel). For a given position in the reference matrix we got a digit between 1 and 9.
Note: the paper had a mistake in it because they assume M(gi,gi+1) = M(R,G). However, gi is supposed to be Y abscisse and gi+1 X abscisse according to their Fig. 3 and wikipedia. This is in contradiction with one of their sentence: “Then R and G are chosen as X-axis and Y-axis”. In other word, a part of the text could be missunderstood due to a mistake. This can be solved by swapping R and G.
Once the n digits between 1 and 9 are extracted, we need to convert from base9 to int (base10) and then to ascii. If you do not understand the extract process, see [Steganography using Sudoku Puzzle.pdf](/files/aperictf_2019/sudo_ku/Steganography using Sudoku Puzzle.pdf)
Here is the final script which try to extract data for each reference matrix with coordinates defined by pixels values:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-
import codecs
from PIL import Image
# http://infohost.nmt.edu/tcc/help/lang/python/examples/sudoku/
# (Ported to python3)
from sudosolver import *
def longToTxt(l):
hexa = hex(l)[2:].strip('L').encode("utf-8")
return codecs.decode(hexa, "hex_codec").decode("utf-8")
def base9ToInt(i):
""" Integer (base9) to Integer (base10) """
return int(i, 9)
def addToSolutions(x):
"""
SudokuSolver solutionObserver handler
Add each matrice solution to SOLUTIONS
"""
global SOLUTIONS
M = []
for rowx in range(9):
l = []
for colx in range(9):
cell = x.get(rowx, colx)
l.append(cell)
M.append(l)
SOLUTIONS.append(M)
def subMatrix(M, n=1):
"""
Substract n to each elt in an 2D array
(substract 1 by default)
"""
return [[x-n for x in l] for l in M]
def sudokuToRefMatrix(s, w, h):
"""
Convert sudoku "s" to a reference matrix with
size of "size"
"""
M = []
for i in range(h):
M.append((s[i % len(s)] * ((w//9)+1))[:w])
return M
def tuplesToSize(t):
"""
Compute size from 9 firsts tuples of list t
"""
i = 0
nb = 0
for l in t[:9][::-1]:
for elt in l[::-1]:
nb += elt*(256**i)
i += 1
return nb
###############################################################################
s = "..4...3.." \
".8...2..9" \
"7..9...6." \
"..879...." \
"2..4.6..3" \
"....319.." \
".3..69.18" \
"1..8...3." \
"..6...2.."
imgSrcName = "TheGame.png"
c1 = 0 # Channel 1 is Red ==> 0
c2 = 1 # Channel 2 is Green ==> 1
SOLUTIONS = [] # List of solutions for the sudoku "s"
if __name__ == "__main__":
slv = SudokuSolver(s, solutionObserver=addToSolutions)
slv.solve()
imgSrc = Image.open(imgSrcName)
w, h = imgSrc.size
imgdata = list(imgSrc.getdata()) # List of (r,g,b)
# Size (9 px) Fig 6. General format of embedding data
sizeTuples = tuplesToSize(imgdata)
for num, sol in enumerate(SOLUTIONS):
print("[Solution n° "+str(num+1)+"]")
expected = subMatrix(sol) # Fig 2. Sudoku solution after subtracting 1
refMatrix = sudokuToRefMatrix(expected, w, h) # Fig 4. Ref. matrix
data = "" # tmp flag
for i in range(sizeTuples):
px = imgdata[i+9] # +9 due to size hidding
data += str(refMatrix[px[c1]][px[c2]]) # extract data
try: # If data extracted from refMatrix is printable then print it
print(longToTxt(base9ToInt(data)))
except:
continue
Output:
[Solution n° 1]
[Solution n° 2]
Bravo ! Vous pouvez valider le challenge avec le flag suivant: APRK{*5UD0KU_M4ST3R*}.
Congratz ! You can validate the challenge with the following flag: APRK{*5UD0KU_M4ST3R*}.
[Solution n° 3]
[Solution n° 4]
[Solution n° 5]
Flag
APRK{*5UD0KU_M4ST3R*}
You can find generic scripts to hide / extract data:
- Hide data using sudoku : sudoku.py - md5sum : 83e3a26ee072575a10fcfc7c6c80b737
- Extract data using sudoku : sudoku_solve.py - md5sum : fcce0c40ec4e5e4bfc6f5690f08a83ca
- Sudoku solver : sudosolver.py - md5sum : f9d6e578a69b29cdec483086df89478f