Fonction de hachage qui produit des hachages courts?

98

Existe-t-il un moyen de chiffrement qui peut prendre une chaîne de n'importe quelle longueur et produire un hachage de moins de 10 caractères? Je souhaite produire des identifiants raisonnablement uniques mais basés sur le contenu du message, plutôt que de manière aléatoire.

Je peux vivre en limitant les messages à des valeurs entières, si les chaînes de longueur arbitraire sont impossibles. Cependant, le hachage ne doit pas être similaire pour deux entiers consécutifs, dans ce cas.

rath3r
la source
Cela s'appelle un hachage. Ce ne sera pas unique.
SLaks
1
C'est aussi un problème de troncature de hachage , alors voir aussi stackoverflow.com/q/4784335
Peter Krauss
2
Pour info, consultez la liste des fonctions de hachage sur Wikipedia.
Basil Bourque

Réponses:

77

Vous pouvez utiliser n'importe quel algorithme de hachage couramment disponible (par exemple SHA-1), ce qui vous donnera un résultat légèrement plus long que ce dont vous avez besoin. Tronquez simplement le résultat à la longueur souhaitée, ce qui peut être suffisant.

Par exemple, en Python:

>>> import hashlib
>>> hash = hashlib.sha1("my message".encode("UTF-8")).hexdigest()
>>> hash
'104ab42f1193c336aa2cf08a2c946d5c6fd0fcdb'
>>> hash[:10]
'104ab42f11'
Greg Hewgill
la source
2
Toute fonction de hachage raisonnable peut être tronquée.
President James K.Polk
88
cela n'augmenterait-il pas le risque de collision dans une bien plus grande mesure?
Gabriel Sanmartin
143
@erasmospunk: l'encodage avec base64 ne fait rien pour la résistance aux collisions, car si il hash(a)entre en collision avec, hash(b)il base64(hash(a))entre également en collision avec base64(hash(b)).
Greg Hewgill
56
@GregHewgill vous avez raison, mais nous ne parlons pas de la collision de l'algorithme de hachage original (oui, des sha1collisions mais c'est une autre histoire). Si vous avez un hachage de 10 caractères, vous obtenez une entropie plus élevée s'il est encodé avec base64vs base16(ou hex). Combien plus haut? Avec base16vous obtenez 4 bits d'informations par caractère, avec base64ce chiffre est de 6 bits / caractère. Au total, un hachage "hexadécimal" de 10 caractères aura 40 bits d'entropie tandis qu'un base64 60 bits. C'est donc un peu plus résistant, désolé si je n'étais pas super clair.
John L. Jegutanis
20
@erasmospunk: Oh, je vois ce que vous voulez dire, oui si vous avez une taille fixe limitée pour votre résultat, vous pouvez intégrer des bits plus significatifs avec le codage base64 par rapport au codage hexadécimal.
Greg Hewgill
46

Si vous n'avez pas besoin d'un algorithme résistant aux modifications intentionnelles, j'ai trouvé un algorithme appelé adler32 qui produit des résultats assez courts (~ 8 caractères). Choisissez-le dans le menu déroulant ici pour l'essayer:

http://www.sha1-online.com/

BT
la source
2
c'est très ancien, pas très fiable.
Mascarpone
1
@Mascarpone "pas très fiable" - source? Il a des limites, si vous les connaissez, peu importe son âge.
BT
8
@Mascarpone "moins de faiblesses" - encore une fois, quelles faiblesses? Pourquoi pensez-vous que cet algorithme n'est pas parfait à 100% pour l'utilisation de l'OP?
BT
3
@Mascarpone L'OP ne dit pas qu'ils veulent un hachage de qualité crypto. OTOH, Adler32 est une somme de contrôle, pas un hachage, donc il peut ne pas convenir, en fonction de ce que l'OP en fait réellement.
PM 2Ring
2
Il y a une mise en garde à Adler32, citant Wikipedia : Adler-32 a un faible pour les messages courts de quelques centaines d'octets, car les sommes de contrôle de ces messages ont une mauvaise couverture des 32 bits disponibles.
Basil Bourque
13

Vous devez hacher le contenu pour créer un condensé. Il existe de nombreux hachages disponibles, mais 10 caractères sont assez petits pour le jeu de résultats. Il y a longtemps, les gens utilisaient CRC-32, qui produit un hachage de 33 bits (essentiellement 4 caractères plus un bit). Il existe également CRC-64 qui produit un hachage de 65 bits. MD5, qui produit un hachage de 128 bits (16 octets / caractères) est considéré comme cassé à des fins cryptographiques car deux messages peuvent être trouvés qui ont le même hachage. Il va sans dire que chaque fois que vous créez un condensé de 16 octets à partir d'un message de longueur arbitraire, vous allez vous retrouver avec des doublons. Plus le résumé est court, plus le risque de collision est grand.

Cependant, votre souci que le hachage ne soit pas similaire pour deux messages consécutifs (entiers ou non) devrait être vrai avec tous les hachages. Même un simple changement dans le message d'origine devrait produire un résumé résultant très différent.

Donc, utiliser quelque chose comme CRC-64 (et base-64 pour le résultat) devrait vous amener dans le quartier que vous recherchez.

John
la source
1
Est-ce que CRC utilise un hachage SHA-1 puis base 64 le résultat rend l'ID résultant plus résistant aux collisions?
5
"Cependant, votre inquiétude que le hachage ne soit pas similaire pour deux messages consécutifs [...] devrait être vraie avec tous les hachages." - Ce n'est pas forcément vrai. Par exemple, pour les fonctions de hachage utilisées pour le clustering ou la détection de clonage, c'est exactement le contraire qui est vrai: vous voulez que des documents similaires donnent des valeurs de hachage similaires (voire identiques). Soundex est un exemple bien connu d'algorithme de hachage spécialement conçu pour produire des valeurs identiques pour une entrée similaire.
Jörg W Mittag
J'utilise les hachages pour authentifier la signature du message. Donc, fondamentalement, pour un message connu et une signature spécifiée, le hachage doit être correct. Je m'en fiche s'il y aurait un petit pourcentage de faux positifs, cependant. C'est tout à fait acceptable. J'utilise actuellement le hachage SHA-512 tronqué compressé avec base62 (quelque chose que j'ai fouetté rapidement) pour plus de commodité.
@ JörgWMittag Excellent point sur SoundEx. Je me suis trompé. Tous les hachages n'ont pas les mêmes caractéristiques.
John
12

Je résume juste une réponse qui m'a été utile (en notant le commentaire de @ erasmospunk sur l'utilisation de l'encodage en base 64). Mon objectif était d'avoir une corde courte qui était surtout unique ...

Je ne suis pas un expert, veuillez donc corriger cela s'il y a des erreurs flagrantes (en Python encore une fois comme la réponse acceptée):

import base64
import hashlib
import uuid

unique_id = uuid.uuid4()
# unique_id = UUID('8da617a7-0bd6-4cce-ae49-5d31f2a5a35f')

hash = hashlib.sha1(str(unique_id).encode("UTF-8"))
# hash.hexdigest() = '882efb0f24a03938e5898aa6b69df2038a2c3f0e'

result = base64.b64encode(hash.digest())
# result = b'iC77DySgOTjliYqmtp3yA4osPw4='

Le resultici utilise plus que de simples caractères hexadécimaux (ce que vous obtiendriez si vous les utilisiez hash.hexdigest()), il est donc moins susceptible d'avoir une collision (c'est-à-dire qu'il devrait être plus sûr de tronquer qu'un condensé hexadécimal).

Remarque: Utilisation de UUID4 (aléatoire). Voir http://en.wikipedia.org/wiki/Universally_unique_identifier pour les autres types.

JJ Geewax
la source
7

Vous pouvez utiliser un algorithme de hachage existant qui produit quelque chose de court, comme MD5 (128 bits) ou SHA1 (160). Ensuite, vous pouvez raccourcir cela davantage en XORing des sections du résumé avec d'autres sections. Cela augmentera le risque de collision, mais pas aussi grave que de simplement tronquer le résumé.

En outre, vous pouvez inclure la longueur des données d'origine dans le cadre du résultat pour le rendre plus unique. Par exemple, XORing de la première moitié d'un condensé MD5 avec la seconde moitié donnerait 64 bits. Ajoutez 32 bits pour la longueur des données (ou moins si vous savez que la longueur tiendra toujours dans moins de bits). Cela entraînerait un résultat de 96 bits (12 octets) que vous pourriez ensuite transformer en une chaîne hexadécimale de 24 caractères. Vous pouvez également utiliser le codage base 64 pour le rendre encore plus court.

dynamichael
la source
2
FWIW, c'est ce qu'on appelle le pliage XOR.
PM 2Ring
7

Si vous avez besoin, "sub-10-character hash" vous pouvez utiliser l' algorithme Fletcher-32 qui produit un hachage de 8 caractères (32 bits), CRC-32 ou Adler-32 .

CRC-32 est plus lent que Adler32 d'un facteur de 20% à 100%.

Fletcher-32 est légèrement plus fiable que Adler-32. Il a un coût de calcul inférieur à celui de la somme de contrôle Adler: comparaison Fletcher vs Adler .

Un exemple de programme avec quelques implémentations Fletcher est donné ci-dessous:

    #include <stdio.h>
    #include <string.h>
    #include <stdint.h> // for uint32_t

    uint32_t fletcher32_1(const uint16_t *data, size_t len)
    {
            uint32_t c0, c1;
            unsigned int i;

            for (c0 = c1 = 0; len >= 360; len -= 360) {
                    for (i = 0; i < 360; ++i) {
                            c0 = c0 + *data++;
                            c1 = c1 + c0;
                    }
                    c0 = c0 % 65535;
                    c1 = c1 % 65535;
            }
            for (i = 0; i < len; ++i) {
                    c0 = c0 + *data++;
                    c1 = c1 + c0;
            }
            c0 = c0 % 65535;
            c1 = c1 % 65535;
            return (c1 << 16 | c0);
    }

    uint32_t fletcher32_2(const uint16_t *data, size_t l)
    {
        uint32_t sum1 = 0xffff, sum2 = 0xffff;

        while (l) {
            unsigned tlen = l > 359 ? 359 : l;
            l -= tlen;
            do {
                sum2 += sum1 += *data++;
            } while (--tlen);
            sum1 = (sum1 & 0xffff) + (sum1 >> 16);
            sum2 = (sum2 & 0xffff) + (sum2 >> 16);
        }
        /* Second reduction step to reduce sums to 16 bits */
        sum1 = (sum1 & 0xffff) + (sum1 >> 16);
        sum2 = (sum2 & 0xffff) + (sum2 >> 16);
        return (sum2 << 16) | sum1;
    }

    int main()
    {
        char *str1 = "abcde";  
        char *str2 = "abcdef";

        size_t len1 = (strlen(str1)+1) / 2; //  '\0' will be used for padding 
        size_t len2 = (strlen(str2)+1) / 2; // 

        uint32_t f1 = fletcher32_1(str1,  len1);
        uint32_t f2 = fletcher32_2(str1,  len1);

        printf("%u %X \n",    f1,f1);
        printf("%u %X \n\n",  f2,f2);

        f1 = fletcher32_1(str2,  len2);
        f2 = fletcher32_2(str2,  len2);

        printf("%u %X \n",f1,f1);
        printf("%u %X \n",f2,f2);

        return 0;
    }

Production:

4031760169 F04FC729                                                                                                                                                                                                                              
4031760169 F04FC729                                                                                                                                                                                                                              

1448095018 56502D2A                                                                                                                                                                                                                              
1448095018 56502D2A                                                                                                                                                                                                                              

D'accord avec les vecteurs de test :

"abcde"  -> 4031760169 (0xF04FC729)
"abcdef" -> 1448095018 (0x56502D2A)

Adler-32 a un faible pour les messages courts de quelques centaines d'octets, car les sommes de contrôle de ces messages ont une mauvaise couverture des 32 bits disponibles. Vérifie ça:

L'algorithme Adler32 n'est pas assez complexe pour rivaliser avec des sommes de contrôle comparables .

sg7
la source
6

Exécutez simplement ceci dans un terminal (sur MacOS ou Linux):

crc32 <(echo "some string")

8 caractères de long.

sgon00
la source
4

Vous pouvez utiliser la bibliothèque hashlib pour Python. Les algorithmes shake_128 et shake_256 fournissent des hachages de longueur variable. Voici un code de travail (Python3):

import hashlib
>>> my_string = 'hello shake'
>>> hashlib.shake_256(my_string.encode()).hexdigest(5)
'34177f6a0a'

Notez qu'avec un paramètre de longueur x (5 dans l'exemple), la fonction renvoie une valeur de hachage de longueur 2x .

feran
la source
1

Nous sommes maintenant en 2019 et il existe de meilleures options. À savoir, xxhash .

~ echo test | xxhsum                                                           
2d7f1808da1fa63c  stdin
sorbet
la source
Ce lien est rompu. il vaut mieux donner une réponse plus complète.
eri0o le
0

J'avais récemment besoin de quelque chose du genre d'une simple fonction de réduction de chaîne. Fondamentalement, le code ressemblait à ceci (code C / C ++ à venir):

size_t ReduceString(char *Dest, size_t DestSize, const char *Src, size_t SrcSize, bool Normalize)
{
    size_t x, x2 = 0, z = 0;

    memset(Dest, 0, DestSize);

    for (x = 0; x < SrcSize; x++)
    {
        Dest[x2] = (char)(((unsigned int)(unsigned char)Dest[x2]) * 37 + ((unsigned int)(unsigned char)Src[x]));
        x2++;

        if (x2 == DestSize - 1)
        {
            x2 = 0;
            z++;
        }
    }

    // Normalize the alphabet if it looped.
    if (z && Normalize)
    {
        unsigned char TempChr;
        y = (z > 1 ? DestSize - 1 : x2);
        for (x = 1; x < y; x++)
        {
            TempChr = ((unsigned char)Dest[x]) & 0x3F;

            if (TempChr < 10)  TempChr += '0';
            else if (TempChr < 36)  TempChr = TempChr - 10 + 'A';
            else if (TempChr < 62)  TempChr = TempChr - 36 + 'a';
            else if (TempChr == 62)  TempChr = '_';
            else  TempChr = '-';

            Dest[x] = (char)TempChr;
        }
    }

    return (SrcSize < DestSize ? SrcSize : DestSize);
}

Il a probablement plus de collisions qu'on ne le souhaiterait, mais il n'est pas destiné à être utilisé comme fonction de hachage cryptographique. Vous pouvez essayer différents multiplicateurs (c'est-à-dire changer le 37 en un autre nombre premier) si vous obtenez trop de collisions. L'une des caractéristiques intéressantes de cet extrait de code est que lorsque Src est plus court que Dest, Dest se retrouve avec la chaîne d'entrée telle quelle (0 * 37 + valeur = valeur). Si vous voulez quelque chose de "lisible" à la fin du processus, Normaliser ajustera les octets transformés au prix d'une augmentation des collisions.

La source:

https://github.com/cubiclesoft/cross-platform-cpp/blob/master/sync/sync_util.cpp

CabineSoft
la source
std :: hash ne résout pas certains cas d'utilisation (par exemple, en évitant de faire glisser le std :: templates bloaty alors que quelques lignes de code supplémentaires suffiront). Il n'y a rien de stupide ici. Il a été soigneusement pensé pour faire face aux principales limitations de Mac OSX. Je ne voulais pas d'entier. Pour cela, j'aurais pu utiliser djb2 tout en évitant d'utiliser std :: templates.
CubicleSoft
Cela semble encore idiot. Pourquoi voudriez - vous jamais utiliser un DestSizeplus de 4 (32 bits) lorsque le hachage lui - même est si merdique? Si vous vouliez la résistance aux collisions fournie par une sortie plus grande qu'un int, vous utiliseriez SHA.
Navin
Regardez, ce n'est pas vraiment un hachage traditionnel. Il a des propriétés utiles où l'utilisateur peut déclarer la taille de la chaîne dans des endroits où l'espace tampon est extrêmement limité sur certains systèmes d'exploitation (par exemple Mac OSX) ET le résultat doit tenir dans le domaine limité des noms de fichiers réels ET ils ne veulent pas simplement tronquer le nom parce que cela causera des collisions (mais les chaînes plus courtes sont laissées seules). Un hachage cryptographique n'est pas toujours la bonne réponse et std :: hash n'est pas toujours la bonne réponse.
CubicleSoft