Salut à tous, dans ce post on va s’attaquer à la solution du AZTEC CHALLENGE de la GreHack 2017. Pour les rageux, petit rappel concernant les spoils dans l’article sur le premier exercice du challenge. Du coup, sans transitions

AZTEC CHALLENGE GreHack 2017

Je vous rappelle le sujet du challenge, on nous donne un GIF animé et un indice avec :

Divide and conquer

Vu l’indice on part à la recherche du fameux « good frame« . Et comme ça bouge et qu’on n’y voit rien. On va donc commencer par séparer notre GIF en images statiques. Quelques options :

• en ligne avec : ezgif.com ;
• ou bien sous linux avec la commande convert :

convert animation.gif astec.png

Qui va vous créer, dans le dossier courant, une image astec-<n°>.png par frame du GIF.

Ensuite, on passe par une étape un peu reloue, il faut se péter les yeux sur chaque image voir si quelque-chose sort de l’ordinaire. Si vous avez de bons yeux (et que vous aimez bien quand tout est bien carré/bien parallèle), vous devriez voir un tout petit QR code dans la n°114.

Il suffit alors d’utiliser n’importe quel paint, gimp ou autre pour extraire enfin ce tout petit carré de 19×19. L’art de cacher quelques octets dans 5Mo de données. CE qui vous donne l’image suivante.

Après quelques recherches web, on finit par comprendre qu’il s’agit d’un QR de type AZTEC CODE (en tombant là par exemple). Et ça tombe bien comme l’exercice s’appelle AZTEC CHALLENGE ! Je vous laisse vous casser les ratiches à essayer de le décoder avec un lecteur mobile (si vous êtes assez suicidaire pour scanner des trucs pareil avec votre smartphone) ou sur les Z’internet comme chez zxing.org. Il semble que les concepteurs de ce QR code aient bien pourris le truc pour s’assurer qu’on le fasse à la main.

Du coup, on cherche à décoder à la main et direct Google, hein. Voici les liens qui m’ont bien aidé pour le challenge.

• Cette vidéo YouTube :

• Ce « blog »? en russe (et traduit en Anglais par Chrome)
  http://recog.ru/blog/standarts/6.html
• Et comme toujours Wikipédia est votre meilleur ami dans ce genre de situation :
  https://en.wikipedia.org/wiki/Aztec_Code

Je vous incite vivement à en prendre connaissance, sinon vous allez rien capter à la suite.

Close, but not enougth.

Avec les 3 liens ci-dessus, vous devriez rapidement comprendre comment on doit lire un AztecCode à deux niveaux.

Et avec la table des correspondances sur 5 bits sur Wikipédia. Il est relativement simple de faire une lecture « à l’arrache » 5 bits par 5 bits de l’image (avec paint et un bête convertisseur binaire/décimal). Et sans s’emmerder à comprendre en détail comment on décode un l’Aztec Code.

Notez le mode d’écriture 5 bits par 5 bits en colimaçon qui fait que ça ressemble à n’importe quoi à la lecture pour un humain. Par exemple les 5 premiers bits se lisent 11010 soit 26 en décimal et qui correspond bien à Y dans notre table. Remarquez aussi l’encodage où on change régulièrement de « mode ». Ça fonctionne un peu comme un Clavier où l’on commence en CAPSLOCK et puis un code L/L (Latch to Lower) nous fait retourner en mode « minuscule » et ou P/S correspond enfin à un appui sur Shift pour accéder aux touches de ponctuation.

Bref, du coup on obtient le message :

You're close<etdelamerderrière>

Bon on se dit qu’on tient le bon bout mais qu’on n’y est pas encore. Si tout va bien dans votre tête à ce moment-là, vous devriez vous souvenir de l’indice qui dit « Once you found the good frame, don’t be colourblind!« .

Colorblind

Là, j’ai sortie Paint.NET et il y a deux façons de faire.

Good Cop

Vous ouvrez votre image et vous passez le « sélecteur de couleurs » sur chaque pixel à la recherche des anomalies RGB. Comme ici un pixel blanc à R-255 G-255 et B-254.

Bad Cop

Ou alors vous ouvrez le menu « Ajustement->Niveaux », et vous « secouez le curseur comme un âne et jusqu’à ce que ça bouge« . Ce n’est pas délicat, mais personne n’a dit qu’on devait être délicat…

Braquage à la Daltonienne

Résultat, on se rend rapidement compte que notre QR contient 4 type de pixels :

1. Des blancs à 255-255-255 ;
2. Des blancs à 255-255-254 ;
3. Des noirs à 0-0-0 ; et
4. Des noirs à 1-1-1.

En connectant deux neurones, j’ai pondu un mini-script Python3 sur un coin de table qui remplace les pixels 1-1-1 par du rouge et les pixels 255-255-254 par du bleu, pour mieux visualiser les modifications que ça implique dans l’image.

from PIL import Image
import numpy as np
im = Image.open('QRCcode.png')
data = np.array(im)
for i in range(0,19,1):
  for j in range(0,19,1):
    print(str(i)+'/'+str(j)+': '+str(data[i,j]))
    if(np.all(data[i,j] == [ 1, 1, 1, 255])):
      data[i,j] = [255, 0, 0, 255]
    if(np.all(data[i,j] == [255, 255, 254, 255])):
      data[i,j] = [0, 0, 255, 255]
im2=Image.fromarray(data)
im2.save('QRCcode_revealed.png')

Je vous laisse le faire tourner pour obtenir ça.

Après quelques secondes de réflexion, il n’y a qu’une façon correcte d’interpréter ça. Il faut transformer les pixels blancs à 255-255-254 en noir et les pixels noirs à 1-1-1 en blancs, et garder les autres tels-quels.

A titre d’exercice, je vous laisse générer le QR-Code final en noir et blanc en éditant le script ci-dessus (et il doit y avoir plein d’autres façons de le faire).

Human Barcode Scanner

Bon on se doute qu’on a le bon QR code, du coup, on va lire les données (comme ça fonctionne toujours pas avec les zxing.org). Donc vous prenez votre QR final et vous faite votre lecture bit par bit.

La lecture donne le tableau suivant.

Et si vous concaténez le tout :

0001011100110111010100110001001110000100010010001001101011010011001111010000011101110011000000101010011100001111011001111111000101001111101110110111011101001110111010010111111100111100111111011101111100110111011100010110110011100001101010111101110111110011011101110001011011001110000110101011

Si vous n’avez pas bien suivi (comme moi), tous les liens que je vous ai donné au début de l’article, vous allez décoder directement en séparant des blocs de 5 bits dans la masse ci-dessus. Par exemple en python :

aztec = "000101110011011101010011000100[...]" 
x = 5
tab = [aztec [i: i + x] for i in range(0, len(aztec ), x)]
print(*tab, sep='\n')
00010
11100
[...]

Et rapidement tomber sur le message suivant en convertissant les valeurs en décimale :

AztecChallengfmk imbzf[etc.]

Et si vous n’êtes pas trop con, vous devriez vous dire que vous êtes pas loin mais que vous avez encore loupé un truc. Sauf que là, on a plus d’indice, retour à la doc donc, on a manqué une astuce.

BIT(E?) Stuffing

Dans la vidéo que je vous ai mis plus haut, à 10min50 il explique qu’après avoir décodé vos codeword de 6 bits dans le QR, si vous en avez qui n’ont que des 0, il faut retirer le dernier bit (et qu’il ne comprend pas pourquoi aussi, mais que c’est horrible d’ailleurs). En fait c’est pas horrible, c’est même sur Wikipédia, ça s’appelle le bit stuffing (ou bourrage de bits en français. Et non, pas de blague salace toi au fond ! je te vois…). Et l’article sur l’AZTEC-Code de Wikipédia explique assez bien comment c’est utilisé :

code words of all-zero and all-ones are avoided by bit stuffing: if the first b−1 bits of a code word have the same value, an extra bit with the complementary value is inserted into the data stream. This insertion takes place whether or not the last bit of the code word would have had the same value or not.

Also note that this only applies to strings of b−1 bits at the beginning of a code word. Longer strings of identical bits are permitted as long as they straddle a code word boundary.

When decoding, a code word of all zero or all one may be assumed to be an erasure, and corrected more efficiently than a general error.

La méthode de lecture 5bits par 5 bits ne fonctionne donc pas, on va être obliger de suivre (un peu) le manuel. On doit donc :

1. dégager dans les codewords de 6 bits, et
2. virer le dernier bit de ceux qui sont égal à 11111x ou 00000x ;
3. Reconcaténer le tout et séparer en bloc en 5 bits avant de commencer à lire

aztec = "0001011100110111010100110001001110000100010010001001101011010011001111010000011101110011000000101010011100001111011001111111000101001111101110110111011101001110111010010111111100111100111111011101111100110111011100010110110011100001101010111101110111110011011101110001011011001110000110101011"
x = 6
tab = [aztec [i: i + x] for i in range(0, len(aztec ), x)]
print(*tab, sep='\n')
000101
110011
011101
010011
000100
111000
010001
001000
100110
101101
001100
111101
000001 <= bit stuffing ici
110111
001100
000010
101001
110000
111101
100111
111100
010100
111110 <= et bit stuffing là
111011
[...]

On a donc viré deux bits en trop. On reprend notre message en blocs de 5 bit et on le décode comme avant pour obtenir :

AztecChallengeWasFunIn[D/L]

4 bits et 1 Digit

Il reste un dernier point, le mode Digit se lit sur quatre bits et non cinq, donc il faut diviser la suite en morceaux de 4 bits et non pas 5.

It’s up to you, don’t disapoint me.

Je vous laisse faire à partir de là, il n’y a plus de piège, vous devriez trouvez les quelques caractères restants sans trop de difficultés. Vous pouvez continuer à jouer avec du Python, du PowerShell, ou du une feuille de calcul Excel, tout fait l’affaire. Je vous mets une capture de ce que ça peut donner en Excel ci-dessous.

Mais, je ne vais pas vous la donner pour vous forcer à bosser un peu, y’a pas de raisons qu’il n’y ai que moi qui me crève le c.. ! :p

Conclusion AZTEC CHALLENGE de la GreHack 2017

Bein moi je l’ai trouvé bien fun ce petit exercice AZTEC CHALLENGE du GreHack 2017, j’ai appris 2-3 trucs et on s’est bien marré au labo. Par contre, je suis pas enthousiaste sur ma capacité à faire la suite vu que je ne peux pas faire ça à plein temps non plus… Bref, n’attendez pas trop la solution à Interlude par ici, je n’aurais probablement pas le temps de m’en occuper avant la conférence, mais si vous avez des idées ou que vous avez aimez ma solution, un petit message en commentaire ça fait toujours plaisir (et si ça me permet de résoudre le problème…)

N’hésitez pas si vous avez des questions aussi.

A bientôt mes lapins.