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

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

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

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

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

Спасибо

ОБНОВИТЬ

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

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

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

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

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

1

Решение

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

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

2

Другие решения

Извините, неправильно прочитал ваш вопрос. 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];
}

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

1

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

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

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

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

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

1

Это может быть ориентировано на детей, но старый АНБ Детский раздел есть некоторые действительно хорошие идеи.

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


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

сетка букв

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

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

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

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

0

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

В качестве быстрого отступления о том, почему эти алгоритмы ведут себя так: по необходимости, они предназначены для того, чтобы скрыть статистические отношения между входом и выходом, чтобы сделать их более трудными для взлома. Например, в английском языке буква «е» является наиболее часто используемой буквой; в некоторых очень слабых классических шифрах вы можете просто найти наиболее распространенную букву и цифру, которые соответствуют «е» (например, — если 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_similarity

0

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

0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector