TP Cryptographie – César, Vigenère et attaque statistique en PowerShell

Un TP sur la cryptographie en PowerShell, on ne va pas attaquer les choses compliqué aujourd’hui. Seulement les bases de la crypto avec 2 algorithmes connus :

  1. César ; et
  2. Vigenère

Et une attaque qui fonctionne bien sur ce genre de protection : par statistique.

Chiffre de César

Le chiffre de césar est une méthode de chiffrement qui date des romains et du fameux empereur du même nom. Elle consiste à décaler d’un certain nombre dans l’alphabet les caractères de la phrase à chiffrer. Ce nombre est la clé de l’algorithme.

Exemple :

Si je prends la chaîne « abc » avec la clé ‘+1’ :

Ma chaîne chiffrée devient « bcd »

Implémentation :

Cet algorithme est implémenté dans le livre d’Arnaud PETITJEAN : Windows PowerShell – Guide de référence pour l’administration système (v3). Dans le chapitre 8, La Sécurité – p 431 dans la V3.

Comme pour sa fonction de génération de mot de passe, j’ai trouvé que son implémentation n’était pas la plus simple. Aussi, je vous en propose un autre :

<#
.SYNOPSIS
Effectue le chiffre de césar sur une chaîne de caractères
.DESCRIPTION
Chiffre une chaîne de caractère via le chiffre de César avec la clé indiqué
.INPUTS Message
Le message à chiffrer
.INPUTS clé
le décalage ou clé de l’algorithme
.OUTPUTS
La chaîne chiffrée
.EXAMPLE
C:\PS> $msg = 'CECI EST UN ESSAI DE PHRASE VRAIE'
C:\PS> Get-CesarCypher -Message $msg -cle 19
vxvb xlm ng xlltb wx iaktlx oktbx
.AUTHORS
TiTi
 
.LASTUPDATE
 2015-05-28
#>
Function Get-CesarCypher{
    param(
        [String] $Message,
        [int] $cle
    )
    
    $MessageTab = ($Message.ToLower()).ToCharArray()
    $alphabet = [int][char]'a'..[int][char]'z' | foreach{[char]$_}
    $i = 0.
    for($i=0 ; $i -lt $MessageTab.length ; $i++){
        if($MessageTab[$i] -ne ' '){
            $MessageTab[$i] = [char] $alphabet[(($alphabet.IndexOf($MessageTab[$i])+$cle)%$alphabet.length)]
        }
    }
    return [System.Text.Encoding]::ASCII.GetString($MessageTab)
}

Chiffre de Vigenère

Un autre algorithme de chiffrement historique assez connu est le chiffre de Vigenère, comme pour césar on va décaler les lettres dans l’alphabet, sauf qu’ici la clé n’est pas un nombre mais un autre mot, et on va décaler chaque lettre du message en additionnant le numéro dans l’alphabet de la lettre ayant la même position que celle du message dans la clé. On répète ensuite la clé autant de fois que nécessaire.

Note :

Si la clé à la même longueur que le message à chiffrer, alors on tombe alors dans le cas du chiffre de Vernam.

Exemple :

Si je prends la chaîne « abc » avec la clé ‘aab’ :

Ma chaîne chiffrée devient « bce »

Implémentation :

Pour la future v42 du livre d’Arnaud, en plus de remplacer son chiffre de César et d’ajouter la cmd-let de génération d’aléatoire que j’ai fait. Il pourra également ajoute, cette superbe fonction réalisé par ma petite chinoise mon apprentie :

<#
.SYNOPSIS
Chiffre par Vigenère une chaîne en entrée avec la clé fournie

.DESCRIPTION
Chiffre par Vigenère une chaîne en entrée avec la clé fournie

.INPUTS Message
Le message à chiffrer

.INPUTS clé
Le décalage ou clé de l’algorithme

.OUTPUTS
La chaine chiffrée

.EXAMPLE
C:\PS> $msg = 'CECI EST UN ESSAI DE PHRASE VRAIE'
C:\PS> Get-VigenereCypher -Message $msg -cle toto

.AUTHORS
Elsa, TiTi

.LASTUPDATE
 2015-05-28

#>
function Get-VigenereCypher {
    param (
        [Parameter(ValueFromPipeline=$True ,Mandatory=$True,HelpMessage="Message à chiffrer")] [String] $message,
        [Parameter(ValueFromPipeline=$False,Mandatory=$True,HelpMessage="Clé pour chiffrer")] [String] $cle
    )
    $message = $message.ToUpper()
    $cle = $cle.ToUpper()
    $chiffre = ''
    $j = 0
    for ($i = 0; $i -lt $message.length; $i++) {
        if($message[$i] -ne ' ') {
            $chiffre += [char](([int][char]$message[$i] -[int][char]'A' + [int][char]$cle[$j]-[int][char]'A'+1)%26 + [int][char]'A')
        } else {
            $chiffre += ' '
        }
        $j++ 
        if ($j -eq $cle.length) {
            $j = 0
        }
    }
    return $chiffre.toLower()
}

Attaque statistique sur ces algorithmes

Pour finir, je vais vous présenter une méthode d’attaque sur le chiffre de césar (et qui peut fonctionner dans une moindre mesure sur Vigenère). C’est l’attaque statistique, en fait dans la langue française on est capable de donner pour chaque lettre sa fréquence moyenne d’apparition dans un texte. C’est d’ailleurs très bien référencé sur Wikipédia : Fréquence d’apparition des lettres en français.

Du coup, je vais prendre l’exemple du chiffre de césar, à partir d’un exercice trouvé sur le net.

Si j’ai le chiffré suivant :

vxvb xlm ng xlltb wx iaktlx oktbx

Que l’on développe la petite fonction suivante qui nous renvoi les pourcentages d’apparition de chaque caractère dans un string :

 <#
.SYNOPSIS
Retourne les statistiques d'apparition de chaque lettre de l'alphabet dans une chaîne en entrée
.DESCRIPTION
Calcule le pourcentage d'apparition de chaque lettre de l'alphabet dans une chaîne donnée
.INPUTS Message
Le message à analyser
.OUTPUTS
La table de hash, caractère/fréquence
.EXAMPLE
PS H:\> Get-StringStats -Message 'vxvb xlm ng xlltb wx iaktlx oktbx'
Name Value
---- -----
x 0,181818181818182
[...]

.AUTHORS
TiTi
 
.LASTUPDATE
 2015-05-28
 
.TODO
#>

Function Get-StringCharStats{
    param(
        [String] $Message
    )
 
    $alphabet = ([int][char]'a'..[int][char]'z' | foreach{[char]$_})
    $hashtableFreq = @{}
    $i=0
    for($i=0 ; $i -lt $alphabet.length ; $i++){
        $hashtableFreq.Add([char]$alphabet[$i],0)
    }
    $i = 0
    for($i=0 ; $i -lt $Message.length ; $i++){
        if($Message[$i] -ne ' '){
            $hashtableFreq.([char]$Message[$i]) += (1/$Message.length)
        }
    }
    return $hashtableFreq.GetEnumerator() | Sort-Object -Property Value -Descending
}

Que l’on appelle sur notre chiffré :

PS H:\> Get-StringStats -Message 'vxvb xlm ng xlltb wx iaktlx oktbx'
Name Value
---- -----
x 0,181818181818182
l 0,121212121212121
t 0,0909090909090909
b 0,0909090909090909
v 0,0606060606060606
k 0,0606060606060606
a 0,0303030303030303
g 0,0303030303030303
i 0,0303030303030303
w 0,0303030303030303
o 0,0303030303030303
m 0,0303030303030303
n 0,0303030303030303
s 0
z 0
c 0
d 0
f 0
r 0
e 0
y 0
p 0
h 0
j 0
q 0
u 0

En comparant avec le tableau des fréquences sur Wikipédia,  on va pouvoir déterminer très facilement que le ‘x’ dans notre chiffré à de grande chance d’être le ‘e’ en clair.

Donc on peut déjà écrire (ici je remplace chiffré en minuscule par le clair en majuscule) :

'vEvb Elm ng Elltb wE iaktlE oktbE'

Idem pour le ‘l’ qui correspondrait au ‘s’ :

'vEvb ESm ng ESStb wE iaktSE oktbE'

Ensuite on commence à rencontrer des difficultés dans la mesure où les lettres suivantes ont le même nombre d’apparition dans mon String. On n’aurait pas (ou moins) ce problème sur un message chiffré plus long.

On va essayer de deviner pour b et t qui correspondrait à ‘a’ ou ‘i’

Si on remplace ‘b’ par ‘a’ et ‘t’ par ‘i’ le troisième mot deviendrai « ESSIA » alors que dans l’autre sens on obtient « ESSAI » qui paraît tout de même plus français. Donc on remplace ‘b’ par ‘i’ et ‘t’ par ‘a’, soit :

'vEvI ESm ng ESSAI wE iakASE okAIE'

A partir de là, on a assez d’information pour commencer à deviner des mots courant :

  • ‘ESm’ est probablement un ‘EST’
  • ‘ng’ deviendrait assez logiquement ‘UN’
  • ‘wE’ se transforme en ‘DE’
  • ‘vEvI’ pourrait être ‘CECI’

Ce qui nous donne déjà :

'CECI EST UN ESSAI DE iakASE okAIE'

En continuant le raisonnement logique et en s’appuyant sur les fréquences d’apparitions des lettres ou des digrammes (2 lettres).

On découvre rapidement la phrase chiffré :

'CECI EST UN ESSAI DE PHRASE VRAIE'

Conclusion

Voilà, j’espère vous avoir appris 2-3 trucs sur ces vieux algorithmes de crypto, et fait gagner du temps à ceux qui cherchait une implémentation toute faite. Et surtout que vous avez compris qu’il ne faut plus utiliser ces algorithmes dans la vraie vie, mais que pour un cours de Crypto c’est une très bonne introduction.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.