Checksum 8 bit reversing

[Kiwazaru]

Yop tout le monde !
Bon alors il y a quelques temps j'ai vu un post parlant de calcul CRC, et j'ai vu qu'il y avait un calcul de Checksum 8 bit dans le code.
J'ai été pris par ce petit algorithme pendant une petite heure avant d'imaginer qu'on pourrait peut être au final en déduire certaines choses.
Pour ceux qui ne savent pas, un checksum (autrement dit somme de contrôle en français) est un calcul qui permet de verifier l'intégrité d'un message face aux modifications accidentelles..
Par exemple, X envoi "LOL" à Y, le checksum de "LOL" vaut 0xAB (je dis ça au pif hein :p) et Y va calculer le checksum du message reçu. Si les deux checksum (celui fourni avec le paquet et celui calculé en local) sont identiques, alors le message est considéré comme authentique, autrement le message est en quelque sorte foutu en "Bad checksum" (que l'on peu observer parfois si vous faites joujou avec Wireshark :p).

Je ne vous donne pas plus de détails. Il y a une partie "jeu" et en fin de post l'explication complète du procédé (autrement dit sûrement ce pour quoi vous êtes ici :p mais essayez de jouer le jeu quand même )
Je vais vous donner l'algorithme (en C) du calcul du checksum 8 bit et je vais vous demander une information

Algorithme:

Code C :

unsigned char checksum(char *data){
    int i;
    unsigned char t = 0;
    for (i=0; i < strlen(data); i++){
        t += data[i];
    }
    return (t & 0xFF);
}

Travail demandé: Trouvez une faille permettant d'évaluer les collisions dans cet algorithme.
Le checksum d'un mot de passe transféré et contrôlé via un checksum 8 bit a été retrouvé. Le serveur distant utilise les checksums pour vérifier la correspondance des deux mots de passe. Contournez ce système.
Informations: Checksum => 0xCA

Arrêtez vous à cet endroit et ne regardez pas en dessous si vous voulez jouer

Je vais maintenant expliquer le principe.
Comme tout le monde le sais ici, 8 bit c'est l'équivalent d'un octet.
Si vous avez compris l'algorithme, vous avez donc dû comprendre que le checksum au final n'est qu'une vulgaire addition du genre:
"ABCDEF" = A + B + C soit 65 + 66 + 67 + 68 + 69 + 70 = 405
405 = 0001 1001 0101 (3 octets)
Ensuite on effectue un AND par 0xFF (soit 1111 1111) sur le résultat pour ne garder que les 8 premiers bits (soit un octet).
Nous comprenons donc que le checksum est simplement les 8 premiers bit du résultat de l'addition.
On obtient donc:
0001 1001 0101
0000 1111 1111
0000 1001 0101 = 195 soit 0x95
Le checksum final sera donc de 0x95 (en hexadecimal).
A partir de là vient un raisonnement logique.
On sait que quelque soit la valeur, on s'en fou des octets suivants, on ne garde que le premier octet. Il nous suffit donc de faire un calcul pour rajouter ou enlever une valeur à nos 8 bits du message qu'on veut coder pour obtenir le même checksum qu'un message totalement différent !
Je m'explique: Prenons deux messages "Bonjour" et "Au revoir".

Checksum Bonjour: 223 : 0xDF
Checksum Au revoir: 109 : 0x6D

Nous obtenons bien deux checksum différent, prenons les maintenant en binaire.

223 = 0xDF = 1101 1111
109 = 0x6D = 0110 1101
Le deuxième checksum est donc plus petit que celui du message original. Il va donc falloir lui rajouter un octet qui compensera cette différence.

On soustrait donc 223 par 109 on obtient: 114
114 = 0111 0010
0111 0010 + 0110 1101 = 223
Il va donc falloir ajouter à notre chaîne la valeur de l'octet 114 en ascii soit "r", la chaîne devient donc "Au revoirr".

On refait le checksum de ces deux chaînes plus en détails:

Bonjour = 66 + 111 + 110 + 106 + 111 + 117 + 114 = 735 = 0010 1101 1111
AND 0xFF = 1101 1111
Au revoir = 65 + 117 + 32 + 114 + 101 + 118 + 111 + 105 + 114 + 114 = 991 = 0011 1101 1111
AND 0xFF = 1101 1111

On obtient bien les checksum 0xDF et 0xDF !

Code d'exploitation:

Code C :

#include <stdio.h>
#include <stdlib.h>

/* Reversing de l'algorithme checksum 8 bit. Modification d'un caractère pour compléter
les 8 premiers bits comme sur le message original. */

unsigned char checksum(char *data);
unsigned char reverse(unsigned char *oData, unsigned char *fData);

int main(){
    char *plaintext = "Bonjour", ciphertext[512] = "Au revoir";
    unsigned char cso = checksum(plaintext), csm = checksum(ciphertext);
    unsigned char diff = reverse(plaintext , ciphertext);
    printf("Checksum Original: %d : 0x%x\n", cso, cso);
    printf("Checksum Modifie: %d : 0x%x\n", csm, csm);
    if(cso > csm) {
        printf("Calcul: %d + %d\n", csm, diff);
        ciphertext[strlen(ciphertext)] += diff;
        csm = checksum(ciphertext);
    }
    else {
        printf("Calcul: %d - %d\n", csm, diff);
        ciphertext[strlen(ciphertext)] -= diff;
        csm = checksum(ciphertext);    
    }
    printf("Checksum Original: %d : 0x%x\n", cso, cso);
    printf("Checksum Final: %d : 0x%x\n", csm, csm);
    printf("Nouveau message: %s", ciphertext);
    return 0;
}

unsigned char checksum(char *data){
    int i;
    unsigned char t = 0;
    for (i=0; i < strlen(data); i++){
        t += data[i];
    }
    return (t & 0xFF);
}

unsigned char reverse(unsigned char *oData, unsigned char *fData){
    unsigned char csoData = checksum(oData), csfData = checksum(fData);
    if (csoData > csfData) { return ((csoData & 0xFF) - (csfData & 0xFF)); }
    else { return ((csfData & 0xFF) - (csoData & 0xFF)); }
}

Output:

Checksum Original: 223 : 0xdf
Checksum Modifie: 109 : 0x6d
Calcul: 109 + 114
Checksum Original: 223 : 0xdf
Checksum Final: 223 : 0xdf
Nouveau message: Au revoirr

Je sais que la notion est très simple en soi mais j'ai jugé intéressant de la partager

Have fun

EDIT: Certains termes sont FAUX, je corrigerais ça demain ! Le principe du post est toujours le même mais les explications ne sont pas toutes vraies !

[b0fh]

Pour ceux qui ne savent pas, un checksum (autrement dit somme de contrôle en français) est un calcul qui permet de verifier l'authenticité d'un message.

FAUX.

Un checksum vérifie l'intégrité d'un message face aux modifications accidentelles. Et de fait, il est extrêmement facile, a partir d'un message existant, de créer un autre message avec le même CRC.

Un Hash vérifie l'intégrité d'un message face à des modifications volontaires. Mais ni l'un ni l'autre n'apportent d'information sur l'authenticité d'un message, puisque n'importe qui peut calculer ce hash.

Un MAC (message authentication code) vérifie l'authenticité d'un message, parce que l'algorithme nécessite une clef secrete sans laquelle on ne peut calculer de MAC valide.

Une signature électronique sur un hash est l'équivalent asymétrique d'un MAC, et fournit aussi l'authenticité.

[Kiwazaru]

Ah bon bah mon post tombe à l'eau alors :p
Merci pour ces précisions b0fh

La somme de contrôle (le terme anglais checksum est également employé), parfois appelée « empreinte », est un nombre qu'on ajoute à un message à transmettre pour permettre au récepteur de vérifier que le message reçu est bien celui qui a été envoyé. L'ajout d'une somme de contrôle à un message est une forme de contrôle par redondance.

J'ai dû donc mal comprendre cette phrase :p

[gruik]

La somme de contrôle (...) permet au récepteur de vérifier que le message reçu est bien celui qui a été envoyé.

J'ai dû donc mal comprendre cette phrase :p

yep, le sens n'est même pas ambigu, la tournure est peut-être mal choisie
la "somme de contrôle" sert à contrôler que ce que l'on a reçu ne comportait pas d'erreur, l'intégrité du message donc, tandis que s'assurer de l'identité de l'expéditeur relève de l'authenticité du message, pas mieux, b0fh a bien résumé la chose

[Kiwazaru]

Comme me l'a fait remarquer octarin (je crois que c'est lui), il est inutile de rajouter le AND à :

Code C :

return (t & 0xFF);

puisque nous traitons déjà la donnée en unsigned char (codé donc sur un octet et allant de 0 à 255).