Table des matières

Write Up: StegCryptoDIY - RNG

Script de la solution ici

Description

Il s’agit de la seconde partie du challenge StegCryptoDIY. L’objectif est de retrouver une clé secrete cachée dans le fichier leHACK19_chall.png

À notre disposition

Deux fichers PNG :

leHACK19_ref.png
leHACK19_chall.png

Et le texte découvert dans la première partie StegCryptoDIY - PNG :

N = 11755068944142969498743245984761181325605304625286958721391766091283132398437645038349775898923465331260308064611167926187399384723360941883732174901666803
g1 = 3808819505564999545252623631192503212186598088555343738111165382623421720119837544658173822461834076347795159366593177669058705087266898444818926668584519
g2 = 8721787400327783748014849037626039397807612372804016643653047575976009827003447778861262036752326827613078346225192581708240820325867658742078694445677877

# I use this functons for enciphering our skey :
encipher(int.from_bytes(skey,'big'),g1,g2,N) with
def encipher(m,g1,g2,N):
    s1=random.randrange(2**127,2**128)
    s2=random.randrange(2**127,2**128)
    return (m*pow(g1,s1,N))%N, (m*pow(g2,s2,N))%N
        
# and here is a flag: lehack2019{REDACTED}

Analyse des fichiers

Comme vu lors de la première partie, les deux fichiers paraissent identiques mais sont différents.

Avec l’outil identify, on remarque que l’image challenge contient une couche de transparence en plus identify-diff-ref-chall

Regardons d’un peu plus pres avec Python.

import numpy as np
import imageio.v3 as iio

im_ref = iio.imread('leHACK19_ref.png')
im_chall = iio.imread('leHACK19_chall.png')
print(im_ref.shape)
print(im_chall.shape)

# Verification de la taille des images
assert im_chall.shape[:2] == im_ref.shape[:2]

# On observe les differente valeurs d'opacité de l'image challenge
opacity_vals = []
for row in im_chall:
    for key_pix in row:
        opacity_vals.append(key_pix[3])
print("Décompte des valeurs uniques d'opacité")
print(np.asarray(np.unique(opacity_vals, return_counts=True)).T)

>>> Décompte des valeurs uniques d'opacité
>>> [[   254   7616][   255 681234]]

On voit que :

Les deux images sont bien de la même taille, et on trouve une couche de transparence en plus.
Il y a seulement 2 valeurs de transparence différentes (254 et 255).

On crée une image pour visualiser cette différence :

im_hidden = np.zeros(im_ref.shape,dtype='uint8')
for i,row in enumerate(im_chall):
    for j,key_pix in enumerate(row):
        opacity = key_pix[3]
        if opacity == 254:
            im_hidden[i][j] = np.array([255,255,255])
        else:
            im_hidden[i][j] = np.array([0,0,0])
iio.imwrite("./hidden_image.jpg", im_hidden)

hidden_image

TADAAA!

La clé secrete a été encodée dans les coordonnées des pixels, et ces coordonnées ont été générées à l’aide de LCGs

Linear Congruential Generator
Générateur Congruentiel Linéaire (En Francais)

Décodage de la clé

Récuperation des pixels de la clé

Dans un premier temps on recupere les pixels formant la clé :

Il s’agit de ceux ayant une opacité de 254, et avec une coordonnées y de 75 ou plus (ceux ne faisant pas partie du message).

pix_key_vals = []
for key_pix in key_pixs:
    y = key_pix[0]
    x = key_pix[1]
    pix = key_pix[2]
    # Recherche du parametres RGB différent
    for rgb_ind in range(3):
        if pix[rgb_ind]!=im_ref[y][x][rgb_ind]:
            pix_key_vals.append((x,y,chr(pix[rgb_ind])))

# On observe les differentes valeurs composants la clé secrete
key_vals = [pix[2] for pix in pix_key_vals]
print("\nValeurs uniques composants la clé secrete: ",''.join(np.unique(key_vals)))

>>> Valeurs uniques composants la clé secrete:   (),0123456789GLORTacehiklnru{}

Récuperation de l’ordre de la clé

Les LCGs permettent de générer des nombres pseudos aléatoires facilement et economiquement

class LCG:
    def __init__(self, seed, a, c, m):
        self.seed = seed
        self.a = a
        self.c = c
        self.m = m
        print(f"\nLCG: Valeur Initial={self.seed}, Multiplicateur={self.a}, Incrementeur={self.c}, Modulo={self.m}")

    def next(self):
        self.seed = (self.a * self.seed + self.c) % self.m
        return self.seed

Ici on en a deux: (LCGx, LCGy) = ((a*X[n-1] + b) % n, (c*(Y[n-1] - 75) + d) % n + 75).

Heureusement pour nous, les LCGs sont de mauvais PRNG dans le cas d’applications cryptographiques, car il est très facile de retrouver leurs parametres en connaissant assez d’états précédents

multiplier = (x[i-2] - [i-1]) * inverse(x[i-1] - x[i], mod) % mod
increment = (x[i-1] - x[i] * multiplier) % modulus
Pour récupérer le module (ici déja connu il faudra plus d’états et un peu d’arithmétique modulaire)

Ainsi même sans connaitre l’anniversaire de notre vilain et celui de sa mère, il est aisé de retrouver le LCG ayant crée les coordonnés x (nul besoin de récupérer le LCG des coordonnées Y)

Avec les valeurs composants notre clé, on devine que le flag est dedans.

On peut donc retrouver des états précedents en cherchant les pixels correspondant au début du flag lehack.

for c in 'lehack ':
    for key_val in pix_key_vals:
        if key_val[2]==c:
            print(key_val)
>>>  (53, 386, 'l')
(6, 175, 'e')
(387, 196, 'e')
(375, 512, 'h')
(136, 197, 'a')
(284, 337, 'a')
(313, 142, 'c')
(394, 555, 'k')

On essaye les différentes combinaisons possibles (leh = [53,387,375] ou [53,6,375]).

modulus_x = 2**9
# Deux possibilités s'offrent a nous, on teste les deux
possible_known_x_states = [[53,387,375],[53,6,375]]

for known_x_states in possible_known_x_states:
    try:
        multiplier_x =  (known_x_states[2] - known_x_states[1]) * inverse(known_x_states[1] - known_x_states[0], modulus_x) % modulus_x
        increment_x = (known_x_states[1] - known_x_states[0] * multiplier_x) % modulus_x
        print(f"success for x_states: {known_x_states}, multiplier = {multiplier_x}, increment = {increment_x})
    except ValueError as e:
        print(e)
        print(f"failed for x_states: {known_x_states}")

>>> base is not invertible for the given modulus
>>> failed: [53, 387, 375]
>>> success: [53, 6, 375] 417 433

Une seule de nos combinaisons est valide.

On peut donc créér notre LCG et générer les coordonnées x pour reconstruire la clé secrete.

lcgx = LCG(53,multiplier_x,increment_x,modulus_x)
flag = ['l'] # valeur initiale
for i in range(len(pix_key_vals)-1):
    nx = lcgx.next()
    for key_val in pix_key_vals:
        if(key_val[0]==nx):
            #print(nx,val[2])
            flag.append(key_val[2])
print(''.join(flag))
print(len(flag))

>>> LCG: Valeur Initial=53, Multiplicateur=417, Incrementeur=433, Modulo=512
>>> lehack2019{REDACTED}(REDACTED
>>> 168

Pour finir en testant on finit par trouver que le premier élément de la clé correnspond à la parenthèse (, x0=253.

lcgx = LCG(253,multiplier_x,increment_x,modulus_x)
flag = ['('] # valeur initiale
for i in range(len(pix_key_vals)-1):
    nx = lcgx.next()
    for key_val in pix_key_vals:
        if(key_val[0]==nx):
            #print(nx,val[2])
            flag.append(key_val[2])
print(''.join(flag))
print(len(flag))

>>> LCG: Valeur Initial=253, Multiplicateur=417, Incrementeur=433, Modulo=512
>>> (REDACTED,REDACTED) lehack2019{REDACTED}
>>> 340

VOILA clé récupérée!

Solution de MiKhai37 pour StegCryptoDIY - RNG