# 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
`n`

of 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
`n`

pixels contains`n`

positions 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