Ищем алгоритм хеширования, где небольшое изменение во входных данных приведет к небольшому изменению хеша

c++ algorithm hash cryptography antivirus

497 просмотра

6 ответа

5428 Репутация автора

Текущие хеш-функции предназначены для больших изменений хеш-функции, даже если изменяется только очень малая часть входных данных. Что мне нужно, так это алгоритм хеширования, выходная мутация которого будет прямо пропорциональна входной мутации. Например, мне нужно что-то похожее на это:

Hash("STR1") => 1000
Hash("STR2") => 1001
Hash("STR3") => 1002

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

Мое текущее требование - иметь большой битрейт (может быть 512 бит?), Чтобы избежать коллизий.

Спасибо

ОБНОВИТЬ

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

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

Еще один аспект заключается в том, чтобы избежать столкновения. Позвольте мне объяснить, что я имею в виду под этим. Это не противоречивая цель. Я хочу, чтобы Hash ("STR1") производил 1000, а Hash ("STR2") - 1001 или 1010, возможно, не имеет значения, если значение близко к предыдущему хешу. Но Hash («Это очень большая строка или, возможно, даже двоичные данные» + 100 случайных символов) не должен выдавать значение, близкое к 1000. Я понимаю, что это не будет работать всегда, и будут некоторые коллизии хеш-диапазона, но Я думаю, что могу ввести другой алгоритм хеширования и проверить оба, чтобы минимизировать коллизии.

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

Еще раз спасибо за ваше время и усилия

Автор: Davita Источник Размещён: 19.07.2016 01:57

Ответы (6)


1 плюс

77 Репутация автора

Извините, неправильно прочитал ваш вопрос. MD5 или SHA-x это не то, что вы хотите.

Согласно википедии, например, https://en.wikipedia.org/wiki/Substitution_cipher не имеет лавинного эффекта (это слово, которое вы имеете в виду).

С точки зрения хеширования вы можете использовать какую-то цифру .

Например:

char* hashme = "hallo123";
int result=0;
for(int i = 0; i<8; ++i) {
   result += hashme[i];
}

Надеюсь, это помогает больше сейчас.

Автор: Cadoiz Размещён: 19.07.2016 02:17

2 плюса

98176 Репутация автора

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

Тем не менее, я думаю, что «минимальные коллизии» и «пропорциональное изменение объема производства» являются противоречивыми целями.

Автор: Jonathon Reinhart Размещён: 19.07.2016 02:22

0 плюса

4912 Репутация автора

Это может быть ориентировано на детей, но у старого раздела NSA Kid есть несколько действительно хороших идей.

Конечно, эти алгоритмы действительно небезопасны, поэтому вы не можете использовать их вместо РЕАЛЬНОГО шифрования. (Но вы не можете использовать настоящий алгоритм шифрования, когда хотите просто повеселиться.)


Номер сетка включает в себя создание сетки, затем используя координаты каждой буквы:

сетка букв

Дальнейшие идеи:

  • Смешайте букву
  • Преобразовать числа в двоичные файлы, чтобы запутать

Извилистый путь также использует сетку. По сути, буквы упакованы в сетку слева направо, рядами вниз. Вывод получается путем разрезания по вертикали через сетку:

Пароль загадка

Автор: Laurel Размещён: 19.07.2016 02:49

1 плюс

593 Репутация автора

В других областях это называется перцептивным хэшированием.

Один из подходов к этому заключается в следующем:

  1. Получите обучающий мультимножество n-грамм. (Например, если n = 2, и ваши тренировочные данные были «Это тест», ваш тренировочный набор будет «Th», «hi», «is», «s» и т. Д.)
  2. Сортируйте и вычисляйте частоты указанных н-грамм по убыванию.

Тогда хэш слова - это первые биты слова «для каждого n-грамма в базе данных, является ли частота этого слова, называемая n-граммой, выше средней частоты?»

Обратите внимание, что это может привести к множеству столкновений с похожими словами, к сожалению, если длина хеша не будет слишком длинной.

Автор: TLW Размещён: 19.07.2016 03:19

0 плюса

8040 Репутация автора

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

В качестве быстрого отступления о том, почему эти алгоритмы ведут себя так: по необходимости, они предназначены для того, чтобы скрыть статистические отношения между входом и выходом, чтобы сделать их более трудными для взлома. Например, в английском языке буква «е» является наиболее часто используемой буквой; в некоторых очень слабых классических шифрах вы можете просто найти наиболее распространенную букву и цифру, которая соответствует «е» (например, - если n - самая распространенная буква, то шансы равны n = e). На самом деле, статистическая схема, подобная описанной вами, вероятно, сделает алгоритм значительно более уязвимым для атак с выбранным открытым текстом, известным открытым текстом, человеком посередине и повторным воспроизведением.

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

Если вы знаете, что

7/19/2016 1:35 transfer $10 from account x to account y

(где отметка даты используется для защиты от повторной атаки) кодирует в

12345678910

в то время как

7/19/2016 1:40 transfer $10 from account x to account y

кодирует в

12445678910

это довольно безопасное предположение, что

12545678910

будет означать что-то вроде

7/19/2016 1:45 transfer $10 from account x to account y

Не имея доступа к исходному ключу, вы можете регулярно воспроизводить этот пакет, чтобы продолжать воровать деньги с чьего-либо счета, просто выполняя тривиальное редактирование. Конечно, это довольно надуманный пример, но он все же иллюстрирует основную проблему.

Мое понимание того, что вы ищете, - это статистическое сходство между файлами. Это может помочь некоторым: https://en.wikipedia.org/wiki/Semantic_s Similarity

Автор: EJoshuaS - Reinstate Monica Размещён: 19.07.2016 06:57

0 плюса

109 Репутация автора

Это действительно существует. Термин хеширование с учетом локальных особенностей. Конкретную реализацию можно найти здесь: https://github.com/trendmicro/tlsh . В зависимости от исходного документа вы можете обратиться к цифровой экспертизе или VisualRank (от Google) для поиска похожих изображений и видео. Для текстовых данных это обычно используется в антиспаме (подробнее здесь: http://spdp.di.unimi.it/papers/pdcs04.pdf ). Для двоичных файлов вы можете сначала запустить дизассемблер, а затем запустить алгоритм для текстовой версии - но это только мое чувство, у меня нет исследования, чтобы поддержать это утверждение, но это была бы интересная гипотеза для проверки.

Автор: Ace.Di Размещён: 21.02.2018 08:24
Вопросы из категории :
32x32