Bon le GreHack challenge est terminé, la conférence était sympa. Y’avait du très bon et du beaucoup moins bien pendant la journée. Les workshops étaientt impeccables par contre. Et visiblement le CTF s’est bien passé. Je vais tacher de digérer les présentations avant de vous faire un retour sur celles qui valaient la peine. J’ai un peu de temps de vous faire un débriefe de l’étape n°3 : Interlude challenge de la GreHack 2017, que n’avait pas eu le temps traiter avant l’événement. J’ai moins de scrupules à vous donner les solutions maintenant que la conférence est passée en plus, donc allons-y,
Interlude challenge de la GreHack 2017
Comme un $crIpT kIddI3
Donc on a un texte incompréhensible et une image svg en indice. De mon côté j’avais un peu gratter la source du svg pour voir s’il n’y avait pas du texte ou un indice caché dans le XML source du fichier. Ce qu’il fallait voir c’est surtout qu’il s’agit de la représentation d’une fonction affine en mathématique. Les plus cultivés d’entre vous auront alors fait le lien avec le chiffrement par fonction affine.
L’article Wikipédia nous indique qu’il est assez simple de casser ce type de fonction par brute-force dans la mesure où ce chiffrement est quasi-équivalent à un chiffre de césar.
D’ailleurs comme souvent pour les fonction cryptographique simple, il y a des sites qui permettent de faire ça très bien à votre place :
https://www.dcode.fr/affine-cipher
Placez le texte et demander lui d’essayer tous les coefficients, Il devrait vous donner la solution du challenge rapidement.
No code needed, no brain needed.
Voilà pour les flemmards.
Comme un vrai n’hacker
Pour ceux que ça intéresse, ré-implémenter un brute-force en PowerShell ou en python, ce n’est pas vraiment compliqué non plus. A partir du moment où vous avez compris le comportement de la fonction de chiffrement Affine.
Les fonction affines sont des fonctions mathématiques du format :
y = a.x + b
Et dont on peut donc calculer l’inverse avec la fonction :
x = (y - b) / a
Si vous avez lu mon article sur le chiffrement de césar, le chiffrement par fonction affine est une généralisation du cas particulier pour césar où a = 1. La subtilité du chiffrement pas fonction affine est que celui-ci fonctionne modulo la taille de l’alphabet d’entrée (disons m dans la suite) soit 26 dans notre cas.
On a donc une fonction de chiffrement de la forme :
y = (a.x + b) mod 26
Et de déchiffrement de la forme
x = (y - b / a) mod 26
Enfin, un des prérequis pour ce chiffrement fonctionne est que les variables a et m soit « co-premier« . C’est à dire qu’ils n’ont aucuns diviseurs autre que 1 et –1 en commun. Cette propriété permet d’éviter que 2 lettres différente en entrée se retrouvent chiffrée par la même en sortie (Cf. Congruence sur les entiers), et donc notre fonction de déchiffrement ai un unique résultat possible.
On peut facilement construire une liste des valeurs de a possibles pour un alphabet de 26 caractères :
1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25
On n’a pas de contraintes sur b en dehors de la taille de l’alphabet comme maximum. Soit au final 12 × 26 = 312 clés de chiffrement (combinaisons de a et b) possibles.
On écrit donc un petit script PowerShell pour tester toutes ces possibilités. Il n’y a rien de particulier dans ce code si ce n’est que la notion d’inverse et celle de l’inverse modulaire (et non l’inverse classique que l’on apprend au collège). Notion plutôt bien expliqué : ici. Version courte, on trouve le code source de cette fonction d’inverse particulière sur rosettacode.
PowerShell Get-AffineDecipher
Ce qui permet de coder à l’arrache un brute-force du déchiffrement ci -dessous. (note : qualité du code pas top, j’ai fait ça à l’arrache dans le train je suis pas fier de moi sur celle-ci).
$Encryptedtext="UBBAHKXYQUHCK"
function get-invmod($a,$n){
if ([int]$n -lt 0) {$n = -$n}
if ([int]$a -lt 0) {$a = $n - ((-$a) % $n)}
$t = 0
$nt = 1
$r = $n
$nr = $a % $n
while ($nr -ne 0) {
$q = [Math]::truncate($r/$nr)
$tmp = $nt
$nt = $t - $q*$nt
$t = $tmp
$tmp = $nr
$nr = $r - $q*$nr
$r = $tmp
}
if ($r -gt 1) {return -1}
if ($t -lt 0) {$t += $n}
return $t
}
function Get-AffineDecipher($Encryptedtext){
$Ciphertab = $Encryptedtext.ToCharArray()
foreach ($a in @(1,3,5,7,9,11,15,17,19,21,23,25)){
foreach ($b in 0..25){
$Deciphertab = @()
foreach ($letter in $Ciphertab){
$y = [int]$letter - 65 # [int][char]'A'=65
$invmoda = get-invmod $a 26
$decipherletter = [int](((($y - $b) *$invmoda) % 26))
if ([int]$decipherletter -lt 0) {
$decipherletter = 26 - ((-$decipherletter) % 26)}
$decipherletter +=65
$Deciphertab += [char]$decipherletter
}
$cleartext = (-join $Deciphertab)
echo "$a-$b : $cleartext"
}
}
}
Get-AffineDecipher $Encryptedtext
#17 - 20 : #AFFINEROMANCEEn relisant les 312 résultats possibles vous devriez rapidement voir la solution est en fait le flag à présenter pour valider le Interlude challenge de la GreHack 2017.
Fin
Voilà j’espère que cette solution pour le Interlude challenge de la GreHack 2017 vous aura intéressé. Pour ma part j’avais oublié le chiffrement par fonction affine quelque part dans les cartons de mes cours d’école d’ingé au fond d’un placard…
Geeker bien!
