Zeecka zeecka

Sudo ku

Aperi'CTF 2019 - Steganography (250 pts)

13 septembre 2019 · Steganography

Aperi’CTF 2019 - Sudo ku

Détails du challenge

EventChallengeCategoryPointsSolves
Aperi’CTF 2019Sudo kuStéganographie2501

Tu veux jouer à un game ? Alors suis les règles.

Challenge :

Ressources :

  • [Steganography using Sudoku Puzzle.pdf](/files/aperictf_2019/sudo_ku/Steganography using Sudoku Puzzle.pdf) - md5sum: d9422e48a7931bc073ac1a35703176ea

TL;DR

Utiliser un sudoku solver pour obtenir chaque solution du sudoku de YouLoose.jpg. Lire le paper et implémenter le schéma d’extraction. Tester le schéma d’extraction sur chaque solution.

Méthodologie

Whirlpinch

Nous avons plusieurs fichiers et une aide (ressources). L’un des fichiers est un sudoku auquel un effet de tourbillon a été appliqué. Pour le retirer, ouvrir le fichier YouLoose.jpg avec gimp ou photoshop et appliquer l’effet inverse. Dans gimp : Filters > Distorsion > Whirlpinch. Puis régler la valeur de rotation à -720,00.

![YouLoose.jpg](/files/aperictf_2019/sudo_ku/YouLoose.jpg)

![distortion.png](/files/aperictf_2019/sudo_ku/distortion.png)

Puis exporter/sauvegarder le fichier.

![YouLoose_nodistortion.png](/files/aperictf_2019/sudo_ku/YouLoose_nodistortion.png)

Résoudre le sudoku

Si vous tentez de résoudre le sudoku, vous remarquerez probablement qu’il possède plusieurs solutions. Pour obtenir chaque solution, nous allons utiliser un sudoku solver. J’ai trouvé ce sudoku solver que j’ai porté en python3 (parce que je voulais une solution en python3).

J’ai décidé d’écrire le script suivant pour obtenir chaque solution :

#!/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)

Sortie :

[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]]

Il y a 5 solutions possibles pour ce sudoku.

À noter que https://www.dcode.fr propose également un sudoku solver :

![dcode1.png](/files/aperictf_2019/sudo_ku/dcode1.png)

![dcode2.png](/files/aperictf_2019/sudo_ku/dcode2.png)

Le paper PDF

Puisque le challenge nous demande de suivre les règles, nous allons essayer de suivre le paper « Steganography using Sudoku Puzzle » fourni dans les ressources. Ce paper décrit une méthode de stéganographie utilisant un sudoku résolu et une image.

Nous allons prendre l’image TheGame.png comme payload à cacher :

![TheGame.png](/files/aperictf_2019/sudo_ku/TheGame.png)

Dans le processus, l’utilisateur doit calculer une matrice nommée « reference matrix » qui correspond au sudoku résolu, dupliqué pour remplir la taille de l’image cachée.

Ici, notre image a la taille suivante : 420*696. Nous devons dupliquer notre matrice sudoku en x et y pour obtenir une reference matrix de taille 420*696.

Voici un exemple : si notre sudoku résolu avait une taille de 3*3 et ne contenait que des lettres (habituellement 9*9 contenant des chiffres) :

abc
def
ghi

Ensuite, avec une image de taille 11*11, nous aurions calculé la reference matrix suivante :

abcabcabcab
defdefdefde
ghighighigh
abcabcabcab
defdefdefde
ghighighigh
abcabcabcab
defdefdefde
ghighighigh
abcabcabcab
defdefdefde
#!/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

Nous n’affichons pas chaque matrice mais elles sont correctes. Voici maintenant le processus d’extraction :

  • Les 9 premiers pixels contiennent la taille n des données cachées. En regardant l’image, les 8 premiers pixels sont noirs (valeur 0) et le dernier est bleu. La taille est codée en binaire (big endian) sur les 9 premiers pixels.
  • Les n pixels suivants contiennent n positions dans la reference matrix (l’abscisse x est codée sur le canal vert et y sur le canal rouge). Pour une position donnée dans la reference matrix, on obtient un chiffre entre 1 et 9.

Note : le paper contient une erreur car ils supposent M(gi,gi+1) = M(R,G). Cependant, gi est censé être l’abscisse Y et gi+1 l’abscisse X d’après leur Fig. 3 et wikipedia. Cela est en contradiction avec l’une de leurs phrases : “Then R and G are chosen as X-axis and Y-axis”. Autrement dit, une partie du texte peut être mal comprise à cause d’une erreur. On peut résoudre cela en inversant R et G.

Une fois les n chiffres entre 1 et 9 extraits, il faut convertir de base9 en int (base10) puis en ascii. Si vous ne comprenez pas le processus d’extraction, consultez [Steganography using Sudoku Puzzle.pdf](/files/aperictf_2019/sudo_ku/Steganography using Sudoku Puzzle.pdf)

Voici le script final qui tente d’extraire les données pour chaque reference matrix avec les coordonnées définies par les valeurs des pixels :

#!/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

Sortie :

[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*}

Vous pouvez trouver des scripts génériques pour cacher / extraire des données :

  • Cacher des données avec un sudoku : sudoku.py - md5sum : 83e3a26ee072575a10fcfc7c6c80b737
  • Extraire des données avec un sudoku : sudoku_solve.py - md5sum : fcce0c40ec4e5e4bfc6f5690f08a83ca
  • Sudoku solver : sudosolver.py - md5sum : f9d6e578a69b29cdec483086df89478f

Zeecka