04 - Algorithme pour l'authentification et l'intégrité - 1ere Partie (SHA256)

Algorithmes pour l’authentification et l’intégrité - 1ere Partie (SHA256)

Une fonction de hachage génère une valeur condensée d'un ensemble de données pouvant être relativement volumineux.

C'est aussi une empreinte qui peut  vérifier la signature concernant l'intégrité des données transmise.
Exemple, la vérification de la signature d'un fichier après téléchargement afin d'assurer qu'il n a pas été corrompu.

Cela permet également de conserver la confidentialité  tel que les données personnelles d'un utilisateur qui doit conserver son anonymat dans le cadre des lois informatique et s'assurer de leur authenticité, (ex: téléphone mobile).

Les données générées par une fonction de hachage ne permettent pas de retrouver la donnée initiale.

Je ne vais pas prendre tous les algo de hachage, mais ceux que j'utilise, c'est à dire le SHA-256
et le HMAC,  peut être du MD5 (à voir), avec un exemple que j'aurai écrit.

      SHA-2 Secure Hash Algorithm

          Les familles SHA sont écrits par la NSA (National Security Agency), La fonction de
          hachage SHA-2 dérive des fonctions SHA-1, SHA-0,MD5, MD4

         La famille SHA-2 fait référence aux  algorithmes SHA224, SHA256, SHA384 et SHA512.

         Pour les SHA-256 et SHA-512: Ces fonctions de hachage sont calculées avec
         32-bits et 64-bits mots respectivement. Malgré l'utilisation de différentes quantités
         de décalage et les constantes addictives, et leur structures, les deux sont presque
         identiques. La seule différence réside dans le nombre de tours dans leurs structures.

        Les attaques identifiées sur le SHA-1 n'ont pas pu être reproduite dans le cadre du SHA-2

                                            SHA-1   SHA-256   SHA-384    SHA-512 

      Message digest size         160         256            384              512

      Message size                    2^64       2^64          2^128          2^128 

      Block size                         512        512            1024            1024      

      Word size                          32          32              64                64

      Number of steps                80          80             80                80

${\displaystyle Maj(x,y,z)=(x\wedge y)\oplus (x\wedge z)\oplus (y\wedge z)}$      Security                               80          128           192              256

     lien sur les spécificaitons de hachage


     FIPS 180 - SECURE HASH STANDARD -


       Le traitement se fait en deux étapes  :

                   1) Pré Traitement,  le message est complété avec des caractères de remplissage
                        pour être découper par bloc de 512 bits ou 64 bytes.

                   2) Le condensat s'obtient par un mécanisme de compression exécuté à chaque
                        itération dans la boucle de traitement des blocs du message qui aura été
                        préalablement découpé lors de la phase de pré-traitement.

           6 fonctions logique sont utilisés :

           

${\displaystyle Maj(x,y,z)=(x\wedge y)\oplus (x\wedge z)\oplus (y\wedge z)}$           

${\displaystyle \Sigma _{0}^{\{256\}}(x)=ROTR^{2}(x)\oplus ROTR^{13}(x)\oplus ROTR^{22}(x)}$          

${\displaystyle \Sigma _{1}^{\{256\}}(x)=ROTR^{6}(x)\oplus ROTR^{11}(x)\oplus ROTR^{25}(x)}$          

${\displaystyle \sigma _{0}^{\{256\}}(x)=ROTR^{7}(x)\oplus ROTR^{18}(x)\oplus SHR^{3}(x)}$        

${\displaystyle \sigma _{1}^{\{256\}}(x)=ROTR^{17}(x)\oplus ROTR^{19}(x)\oplus SHR^{10}(x)}$         

          Expression des formules en C 

     CH(x,y,z) (((x) & (y)) ^ (~(x) & (z)))    

     MAJ(x,y,z) (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)))

     EP0(x) (ROTRIGHT(x,2) ^ ROTRIGHT(x,13) ^ ROTRIGHT(x,22))

     EP1(x) (ROTRIGHT(x,6) ^ ROTRIGHT(x,11) ^ ROTRIGHT(x,25))

     SIG0(x)(ROTRIGHT(x,7) ^ ROTRIGHT(x,18) ^ ((x) >> 3))

     SIG1(x)(ROTRIGHT(x,17)^ ROTRIGHT(x,19) ^ ((x) >> 10))         

     ROTRIGHT(a,b) (((a) >> (b)) | ((a) << (32-(b))))

     ROTLEFT(a,b) (((a) << (b)) | ((a) >> (32-(b))))  

          Extrait de la fonction de hachage démontrant l'utilisation de ces formules.
          La variable data contient le message.

int a, b, c, d, e, f, g, h, i, j, t1, t2; int[] m = new int[64];
int[] m = new int[64];

for (i = 0, j = 0; i < 16; ++i, j += 4) m[i] = (data[j] << 24) | (data[j + 1] << 16) | (data[j + 2] << 8) | (data[j + 3]);

for (; i < 64; ++i) m[i] = SIG1(m[i - 2]) + m[i - 7] + SIG0(m[i - 15]) + m[i - 16];

for (i = 0; i < 64; ++i) {

t1 = h + EP1(e) + CH(e, f, g) + k[i] + m[i];

t1 = h + EP1(e) + CH(e, f, g) + k[i] + m[i];

t2 = EP0(a) + MAJ(a, b, c);

t2 = EP0(a) + MAJ(a, b, c);

h = g;

h = g;

g = f;

g = f;

e = d + t1;

e = d + t1;

f = e;

f = e; d = c; a = t1 + t2; c = b; b = a;

}

          Note: voir un exemple de traitement en java à la fin de cet article.

          extrait du main :

byte[] data="hello world!".getBytes();
int strLen = data.length; SHA256_CTX ctx = new SHA256_CTX(); int[] hash = new int[32]; StringBuilder hashStr = new StringBuilder();

#Initialization Vector (en dur) SHA256Init(ctx);

#Pré traitement SHA256Update(ctx, data, strLen);

#hachage SHA256Final(ctx, hash);

# résultat du condensat sous forme texte for (int i = 0; i < 32; i++) hashStr.append(String.format("%02X", hash[i]));

return hashStr.toString();

       

      Voici des schéma graphiques,  Algo sha 256 (wiki), pour plus de détails :    Traitement

Liens utiles
Fonction_de_hachage
SHA-2
sha256-hash-calculator
onewayhash

Voir exemple ci-dessous:

Check sample C program 

C sample program SHA256

J'ai adapté un exemple écrit en C en java.

Note : il y a encore un petit bug, je n'obtient pas la même valeur 

de hachage entre le calculator SHA256 et le programme,je pense que 

c'est à cause des unsigned int en C qui n'existe pas en java, je

n'obtiens pas les même valeurs de décalage, le int java peut avoir 

des valeurs négative et cela à un impact sur le résultat du condensat, 

faut que je trouve une solution à ce problème. cela a aussi un impact

sur le HMAC qui utilise le SHA-256 en sous appel.

Test main 

package test;

public class TestSHA256 {
    public static void main(String[] args) {

        String data = "Hello World!";
        String hashData = SHA256.hash(data.getBytes());
        System.out.println(hashData);
    }
}

Java program sha256

package test;

public class SHA256 {

    private static int[] k = {0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
            0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
            0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
            0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
            0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
            0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
            0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
            0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2};

    public SHA256() {

    }

    //#define ROTLEFT(a,b) (((a) << (b)) | ((a) >> (32-(b))))    
private static int ROTLEFT(int a, int b) {
        return (((a) << (b)) | ((a) >> (32-(b))));
    }

    //#define ROTRIGHT(a,b) (((a) >> (b)) | ((a) << (32-(b))))    
private static int ROTRIGHT(int a, int b) {
        return (((a) >> (b)) | ((a) << (32-(b))));
    }

    //#define CH(x,y,z) (((x) & (y)) ^ (~(x) & (z)))    
private static int CH(int x, int y, int z) {
        return (((x) & (y)) ^ (~(x) & (z)));
    }

    //#define MAJ(x,y,z) (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)))    
private static int MAJ(int x, int y, int z) {
        return (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)));
    }

    //#define DBL_INT_ADD(a,b,c) if (a > 0xffffffff - (c)) ++b; a += c;    
private static void DBL_INT_ADD(int a, int b, int c) {
        if (a > 0xffffffff - (c)) ++b; a += c;
    }

    //#define SIG0(x) (ROTRIGHT(x,7) ^ ROTRIGHT(x,18) ^ ((x) >> 3))    
private static int SIG0(int x) {
        return (ROTRIGHT(x,7) ^ ROTRIGHT(x,18) ^ ((x) >> 3));
    }

    //#define SIG1(x) (ROTRIGHT(x,17) ^ ROTRIGHT(x,19) ^ ((x) >> 10))    
private static int SIG1(int x) {
        return (ROTRIGHT(x,17) ^ ROTRIGHT(x,19) ^ ((x) >> 10));
    }

    //#define EP0(x) (ROTRIGHT(x,2) ^ ROTRIGHT(x,13) ^ ROTRIGHT(x,22))    
private static int EP0(int x) {
        return (ROTRIGHT(x,2) ^ ROTRIGHT(x,13) ^ ROTRIGHT(x,22));
    }

    //#define EP1(x) (ROTRIGHT(x,6) ^ ROTRIGHT(x,11) ^ ROTRIGHT(x,25))    
private static int EP1(int x) {
        return (ROTRIGHT(x,6) ^ ROTRIGHT(x,11) ^ ROTRIGHT(x,25));
    }

 private static void memset(byte[] ia, int initValue) {
        for (int i = 0; i < ia.length; i++) {
            ia[i] = (byte)initValue;
        }
    }

public static String hash(byte[] data) {
        int strLen = data.length;
        SHA256_CTX ctx = new SHA256_CTX();
        int[] hash = new int[32];
        StringBuilder hashStr = new StringBuilder();
        SHA256Init(ctx);
        SHA256Update(ctx, data, strLen);
        SHA256Final(ctx, hash);

        for (int i = 0; i < 32; i++)
            hashStr.append(String.format("%02X", hash[i]));

        return hashStr.toString();
    }

private static void SHA256Transform(SHA256_CTX ctx, byte[] data) {
        int a, b, c, d, e, f, g, h, i, j, t1, t2;
        int[]  m = new int[64];


        for (i = 0, j = 0; i < 16; ++i, j += 4)
            m[i] = (data[j] << 24) | (data[j + 1] << 16) | (data[j + 2] << 8) | (data[j + 3]);
        for (; i < 64; ++i)
            m[i] = SIG1(m[i - 2]) + m[i - 7] + SIG0(m[i - 15]) + m[i - 16];

        a = ctx.state[0];
        b = ctx.state[1];
        c = ctx.state[2];
        d = ctx.state[3];
        e = ctx.state[4];
        f = ctx.state[5];
        g = ctx.state[6];
        h = ctx.state[7];

        for (i = 0; i < 64; ++i) {
            t1 = h + EP1(e) + CH(e, f, g) + k[i] + m[i];
            t2 = EP0(a) + MAJ(a, b, c);
            h = g;
            g = f;
            f = e;
            e = d + t1;
            d = c;
            c = b;
            b = a;
            a = t1 + t2;
        }

        ctx.state[0] += a;
        ctx.state[1] += b;
        ctx.state[2] += c;
        ctx.state[3] += d;
        ctx.state[4] += e;
        ctx.state[5] += f;
        ctx.state[6] += g;
        ctx.state[7] += h;
    }


    private static void SHA256Init(SHA256_CTX ctx) {
        ctx.datalen = 0;
        ctx.bitlen[0] = 0;
        ctx.bitlen[1] = 0;
        ctx.state[0] = 0x6a09e667;
        ctx.state[1] = 0xbb67ae85;
        ctx.state[2] = 0x3c6ef372;
        ctx.state[3] = 0xa54ff53a;
        ctx.state[4] = 0x510e527f;
        ctx.state[5] = 0x9b05688c;
        ctx.state[6] = 0x1f83d9ab;
        ctx.state[7] = 0x5be0cd19;
    }

    private static void SHA256Update(SHA256_CTX ctx, byte[] data, int len) {
        int t, i;
        for (i = 0; i < len; ++i) {
            ctx.data[i] = data[i];
            ctx.datalen++;
            if (ctx.datalen == 64) {
                SHA256Transform(ctx, ctx.data);
                DBL_INT_ADD(ctx.bitlen[0], ctx.bitlen[1], 512);
                ctx.datalen = 0;
            }
        }
    }

    private static void SHA256Final(SHA256_CTX ctx, int[] hash) {

        int i;
        i = ctx.datalen;

        // Pad whatever data is left in the buffer.        if (ctx.datalen < 56) {
            ctx.data[i++] = (byte) 0x80;
            while (i < 56)
                ctx.data[i++] = (int) 0x00;
        } else {
            ctx.data[i++] = (byte) 0x80;
            while (i < 64)
                ctx.data[i++] = 0x00;
            SHA256Transform(ctx, ctx.data);
            memset(ctx.data, (byte) 0x00);
        }

        // Append to the padding the total message's length in bits and transform.        DBL_INT_ADD(ctx.bitlen[0], ctx.bitlen[1], ctx.datalen * 8);
        ctx.data[63] =(byte) ctx.bitlen[0];
        ctx.data[62] = (byte) (ctx.bitlen[0] >> 8);
        ctx.data[61] = (byte) (ctx.bitlen[0] >> 16);
        ctx.data[60] = (byte) (ctx.bitlen[0] >> 24);
        ctx.data[59] = (byte)  ctx.bitlen[1];
        ctx.data[58] = (byte) (ctx.bitlen[1] >> 8);
        ctx.data[57] = (byte) (ctx.bitlen[1] >> 16);
        ctx.data[56] = (byte) (ctx.bitlen[1] >> 24);
        SHA256Transform(ctx, ctx.data);

        // Since this implementation uses little endian int ordering and SHA uses big endian,        // reverse all the ints when copying the final state to the output hash.
        for (i = 0; i < 4; ++i) {
            hash[i] =(ctx.state[0] >> (24 - i * 8) & 0x000000ff);
            hash[i + 4] = (ctx.state[1] >> (24 - i * 8) & 0x000000ff);
            hash[i + 8] = (ctx.state[2] >> (24 - i * 8) & 0x000000ff);
            hash[i + 12] =(ctx.state[3] >> (24 - i * 8) & 0x000000ff);
            hash[i + 16] =(ctx.state[4] >> (24 - i * 8) & 0x000000ff);
            hash[i + 20] = (ctx.state[5] >> (24 - i * 8) & 0x000000ff);
            hash[i + 24] =(ctx.state[6] >> (24 - i * 8) & 0x000000ff);
            hash[i + 28] = (ctx.state[7] >> (24 - i * 8) & 0x000000ff);
        }
    }

    private static class SHA256_CTX {

        byte[] data = new byte[64];
        int datalen = 0;
        int[] bitlen = new int[2];
        int[] state = new int[8];
    }

}