Хеш-функция, которая производит короткие хеши?

99

Есть ли способ шифрования, который может взять строку любой длины и создать хэш размером менее 10 символов? Я хочу создать достаточно уникальный идентификатор, но на основе содержимого сообщения, а не случайным образом.

Я могу жить с ограничением сообщений целыми значениями, если строки произвольной длины невозможны. Однако в этом случае хеш не должен быть одинаковым для двух последовательных целых чисел.

rath3r
источник
Это называется хешем. Это не будет уникальным.
SLaks
1
Это также проблема с усечением хэша , поэтому см. Также stackoverflow.com/q/4784335
Питер Краусс,
2
К вашему сведению, см. Список хэш-функций в Википедии.
Basil Bourque

Ответы:

79

Вы можете использовать любой общедоступный алгоритм хеширования (например, SHA-1), который даст вам немного более длительный результат, чем тот, который вам нужен. Просто обрежьте результат до желаемой длины, что может быть достаточно хорошо.

Например, в Python:

>>> import hashlib
>>> hash = hashlib.sha1("my message".encode("UTF-8")).hexdigest()
>>> hash
'104ab42f1193c336aa2cf08a2c946d5c6fd0fcdb'
>>> hash[:10]
'104ab42f11'
Грег Хьюгилл
источник
3
Любая разумная хеш-функция может быть усечена.
Президент Джеймс К. Полк
90
Разве это не повысит риск столкновения в гораздо большей степени?
Габриэль Санмартин
143
@erasmospunk: кодирование с помощью base64 ничего не делает для устойчивости к столкновениям, поскольку если hash(a)сталкивается с, hash(b)то base64(hash(a))также сталкивается с base64(hash(b)).
Грег Хьюгилл
56
@GregHewgill, вы правы, но мы не говорим о коллизиях исходного хеш-алгоритма (да, sha1коллизии, но это уже другая история). Если у вас есть хэш из 10 символов, вы получите более высокую энтропию, если он закодирован с помощью base64vs base16(или hex). Насколько выше? С base16вы получаете 4 бита информации на символ, с base64этой цифрой 6 бит / символ. Всего "шестнадцатеричный" хэш из 10 символов будет иметь 40 бит энтропии, а base64 - 60 бит. Так что он немного более устойчивый, извините, если я не был супер ясен.
Джон Л. Джегутанис
20
@erasmospunk: О, я понимаю, что вы имеете в виду, да, если у вас есть ограниченный фиксированный размер для вашего результата, вы можете упаковать более значимые биты с кодировкой base64 по сравнению с шестнадцатеричным кодированием.
Грег Хьюгилл
46

Если вам не нужен алгоритм, устойчивый к преднамеренной модификации, я нашел алгоритм под названием adler32, который дает довольно короткие (~ 8 символов) результаты. Выберите его из раскрывающегося списка, чтобы попробовать:

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

BT
источник
2
он очень старый, не очень надежный.
Mascarpone
1
@Mascarpone "не очень надежный" - источник? У него есть ограничения, если вы их знаете, неважно, сколько ему лет.
BT
8
@Mascarpone "меньше слабостей" - опять же, какие слабости? Как вы думаете, почему этот алгоритм не на 100% идеален для использования OP?
BT
3
@Mascarpone ОП не говорит, что им нужен хеш криптографического уровня. OTOH, Adler32 - это контрольная сумма, а не хеш, поэтому он может не подходить, в зависимости от того, что OP на самом деле делает с ним.
PM 2Ring
2
Есть одно предостережение для Adler32, цитируя Википедию : Adler-32 имеет слабость к коротким сообщениям длиной в несколько сотен байтов, потому что контрольные суммы для этих сообщений плохо покрывают 32 доступных бита.
Basil Bourque
13

Вам нужно хешировать содержимое, чтобы получить дайджест. Доступно много хешей, но 10 символов - это довольно мало для набора результатов. Раньше люди использовали CRC-32, который выдает 33-битный хеш (в основном 4 символа плюс один бит). Также существует CRC-64, который производит 65-битный хэш. MD5, который производит 128-битный хэш (16 байтов / символов), считается сломанным для криптографических целей, потому что могут быть найдены два сообщения с одинаковым хешем. Само собой разумеется, что всякий раз, когда вы создаете 16-байтовый дайджест из сообщения произвольной длины, у вас будут дубликаты. Чем короче дайджест, тем выше риск столкновений.

Однако ваше беспокойство о том, что хэш не будет одинаковым для двух последовательных сообщений (будь то целые числа или нет), должно быть истинным для всех хешей. Даже одно изменение бита в исходном сообщении должно привести к совершенно иному итоговому дайджесту.

Итак, использование чего-то вроде CRC-64 (и базового 64 для результата) должно привести вас к тому району, который вы ищете.

Джон
источник
1
Делает ли CRC хеш-код SHA-1 и затем основание 64 для результата более устойчивым к коллизиям?
5
«Однако ваше беспокойство о том, что хеш-коды не будут одинаковыми для двух последовательных сообщений [...], должно быть истинным для всех хеш-кодов». - Это не обязательно правда. Например, для хеш-функций, которые используются для кластеризации или обнаружения клонов, на самом деле верно прямо противоположное: вы хотите, чтобы похожие документы давали похожие (или даже одинаковые) хеш-значения. Хорошо известным примером алгоритма хеширования, который специально разработан для получения идентичных значений для аналогичных входных данных, является Soundex.
Jörg W Mittag
Я использую хэши для аутентификации подписи сообщения. Таким образом, для известного сообщения и указанной подписи хэш должен быть правильным. Хотя меня не волнует, будет ли небольшой процент ложных срабатываний. Это вполне приемлемо. В настоящее время я использую усеченный хэш SHA-512, сжатый с помощью base62 (что я быстро придумал) для удобства.
@ JörgWMittag Отличный отзыв о SoundEx. Я исправился. Не все хэши имеют одинаковые характеристики.
Джон
12

Просто резюмируя ответ, который был мне полезен (отмечая комментарий @ erasmospunk об использовании кодировки base-64). Моей целью было получить короткую строку, которая была бы в основном уникальной ...

Я не эксперт, поэтому, пожалуйста, исправьте это, если есть какие-либо явные ошибки (в Python снова, как принятый ответ):

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='

resultЗдесь используется больше , чем просто шестнадцатеричных символов (то , что вы получите , если вы использовали hash.hexdigest()) , так что это менее вероятно столкновение (то есть, должны быть более безопасными , чем укоротить гекс переваривать).

Примечание. Использование UUID4 (случайное). См. Http://en.wikipedia.org/wiki/Universally_unique_identifier для других типов.

Джей Джей Гивакс
источник
7

Вы можете использовать существующий алгоритм хеширования, который производит что-то короткое, например MD5 (128 бит) или SHA1 (160). Затем вы можете сократить это еще больше, объединяя разделы дайджеста с другими разделами. Это увеличит вероятность коллизий, но не так плохо, как простое усечение дайджеста.

Кроме того, вы можете включить длину исходных данных как часть результата, чтобы сделать его более уникальным. Например, операция XOR первой половины дайджеста MD5 со второй половиной приведет к получению 64 бита. Добавьте 32 бита для длины данных (или меньше, если вы знаете, что длина всегда умещается в меньшее количество бит). Это приведет к 96-битному (12-байтовому) результату, который затем можно преобразовать в 24-символьную шестнадцатеричную строку. В качестве альтернативы вы можете использовать кодировку base 64, чтобы сделать ее еще короче.

Dynamichael
источник
2
FWIW, это известно как сворачивание XOR.
PM 2Ring
7

Если вам нужно, "sub-10-character hash" вы можете использовать алгоритм Fletcher-32 , который производит 8-символьный хеш (32 бита), CRC-32 или Adler-32 .

CRC-32 медленнее Adler32 в 20% - 100%.

Флетчер-32 чуть надежнее Адлера-32. У него более низкие вычислительные затраты, чем у контрольной суммы Адлера: сравнение Флетчера и Адлера .

Ниже приводится пример программы с несколькими реализациями Флетчера:

    #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;
    }

Вывод:

4031760169 F04FC729                                                                                                                                                                                                                              
4031760169 F04FC729                                                                                                                                                                                                                              

1448095018 56502D2A                                                                                                                                                                                                                              
1448095018 56502D2A                                                                                                                                                                                                                              

Соответствует тестовым векторам :

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

Adler-32 имеет слабость к коротким сообщениям с несколькими сотнями байтов, потому что контрольные суммы для этих сообщений плохо покрывают 32 доступных бита. Проверь это:

Алгоритм Adler32 недостаточно сложен, чтобы конкурировать с сопоставимыми контрольными суммами .

sg7
источник
6

Просто запустите это в терминале (в MacOS или Linux):

crc32 <(echo "some string")

Длина 8 символов.

sgon00
источник
4

Вы можете использовать библиотеку hashlib для Python. В shake_128 и shake_256 алгоритмы обеспечивают переменные хешей длины. Вот рабочий код (Python3):

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

Обратите внимание, что с параметром длины x (в примере 5) функция возвращает хеш-значение длины 2x .

Feran
источник
1

Сейчас 2019 год, и есть варианты получше. А именно xxhash .

~ echo test | xxhsum                                                           
2d7f1808da1fa63c  stdin
сорбет
источник
Эта ссылка не работает. лучше дать более полный ответ.
eri0o
0

Недавно мне понадобилось что-то вроде простой функции сокращения строк. По сути, код выглядел примерно так (впереди код C / C ++):

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);
}

Вероятно, у него больше коллизий, чем можно было бы ожидать, но он не предназначен для использования в качестве криптографической хеш-функции. Вы можете попробовать различные множители (например, изменить 37 на другое простое число), если у вас слишком много коллизий. Одна из интересных особенностей этого фрагмента заключается в том, что, когда Src короче, чем Dest, Dest заканчивается входной строкой как есть (0 * 37 + value = value). Если вы хотите что-то «читаемое» в конце процесса, Normalize скорректирует преобразованные байты за счет увеличения коллизий.

Источник:

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

CubicleSoft
источник
std :: hash не решает некоторые варианты использования (например, избегая перетаскивания в раздутых std :: templates, когда будет достаточно всего нескольких дополнительных строк кода). Здесь нет ничего глупого. Он был тщательно продуман, чтобы иметь дело с основными ограничениями в Mac OSX. Мне не нужно целое число. Для этого я мог бы использовать djb2 и по-прежнему избегать использования std :: templates.
CubicleSoft
Это все еще звучит глупо. Зачем вообще использовать значение DestSizeбольше 4 (32 бита), если сам хеш такой дерьмовый? Если вам нужна стойкость к столкновениям, обеспечиваемая выходом, превышающим int, вы должны использовать SHA.
Navin
Послушайте, это не совсем традиционный хеш. Он имеет полезные свойства, в которых пользователь может объявлять размер строки в местах с чрезвычайно ограниченным буферным пространством в определенных ОС (например, Mac OSX), И результат должен соответствовать ограниченному домену реальных имен файлов, И они не хотят просто усекать имя, потому что это БУДЕТ вызывать коллизии (но более короткие строки не трогают). Криптографический хеш - не всегда правильный ответ, и std :: hash также не всегда правильный ответ.
CubicleSoft