mayton2019

1) Можешь смело брать sha256/512. Они уже имеют аппаратную поддержку в процессорах и должны быть быстрее чем MD5. Проверь этот факт для твоего API.

2) По поводу борьбы с коллизиями. Нужно посчитать цену коллизии. Тоесть если она все таки
возникает - как это повлияет на ваш бизнес. И как вы будете выходить из ситуации.

Вообще я думаю что все будет в порядке. 350 млрд. Номерная емкость SHA256 - это 1.157920892373162E77
и доля ключей составляет 3.0226589942830556E-66.

Это буквально 0 процентов. Ноль целых и потом 60 нулей после запятой.

Можно использовать фильтр Блума. Тогда для твоего числа ключей (4 320 000 000) надо
будет держать структуру размером 4.8 Гб https://hur.st/bloomfilter/?n=4320000000&p=0.01&m=&k=

Но фильтр отбивает не 100% ответов а просто некую большую часть (99% в данной формуле). И поэтому надо чтобы
в базе всегда стоял unique constraint. Да и вообще констрейнт - это часть культуры проектирования
баз. Поэтому это даже не должно обсуждаться. База без гарантий уникальности - это сильно
подпорченная информация. Информация низкого качества.

Фильтры Блума используются в Cassandra, Hadoop, Databricks, Redis. Обычно не как основные а как
вспомогательные структуры. Поэтому такие решения - вполне себе production-ready.

У папки нет хеш-сумм. По крайней мере пока мы не договорились о порядке обхода файлов.
Дело в том что

hash(file1, file) <> hash(file2, file1)

поэтому порядок важен.

Мы не можем доверять естественному порядку файлов. Потому что для NTFS - он (допустим) лексикографический.
А для флешки (FAT32) файлы могут лежать в рандомном порядке и поэтому хеш такого фолдера может
быть разным.

Есть ли вероятность что если два одинаковых файла имеют отличия то контрольные хеш суммы будут одинаковые или иметь отличие в 1 символ ?

Все современные криптографические хеши обладают свойством типа "эффект лавины" когда
случайное изменение 1 бита входного текста вызывает изменение 50% битов хеша (или крипто-блока).

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

Обычные контрольные суммы не тестируются на эффект лавины и не обязаны этому следовать.

Может ли вирус во время вычисления хеш сумм подменять значения хеша ?

Наука криптография изучает софистическую модель взаимодействия Алисы и Боба которые
ведут переписку по незащищенному каналу который контролируется злоумышленником Кларком.
И на этом пожалуй все. Никакие вирусы при этом не рассматриваются. Криптография предполагает
что комьютер Алисы и Боба абсолютно полностью защищен и никаких снифферов или кейлоггеров
или перехватчиков файлов там быть не может.

Вирусы изучает инфо-безопасность и форензика уже с позиции анализа посмерного снимка.
Тоесть когда уже событие случилось. И при этом у них и методы изучения и выводы и инструменты
совсем другие. Криптография к этому моменту уже никому не интересна. Работа вируса отменяет
сразу все аксиомы криптогарфии одним махом.

В 2000х годах хакеры, используя метод радужных таблиц (rainbow tables) научились находить пароль по известному хешу
за вполне короткое время если обладали заранее расчитанной базой этих таблиц. И если они знали
какая хеш-функция работала. Особенно для Windows NTLM у них ловко выходило. И при условии
что пароль был корткий. До 8 символов например. Для большего пароля база росла экспоненциально.

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

Теперь стандартные наборы таблиц не работали. Им нужно для вашего софта персонально генерить свой сет
таблиц. Даже на видеокартах этот процесс очень долгий и сами таблички занимают много гигабайт. Короче
никому это было не нужно и salt является надежным убийцей радуги.

В криптографии есть аналогия с вектором инициализации IV для симметричных шифров.

Дружище тебе не надо портить дерево. Оно и так хорошо.
Просто заведи отдельную хеш-таблицу и трекай две структуры
одновременно.

LRU например так и делает. Цепной список + Hashtable.

Утилита transmission-show показывает содержимое torrent-файла.

Меня интересует насколько быстро будет "взломан" пароль "My_sUper passw0rd", хешированный с помощью одного из алгоритмов доступных в PHP (sha512, ripemd320, whirlpool, tiger192,4 и haval256,5)

Можно консультроваться с популярными базами Rainbow Tables просто на предмет того поддерживается
ли нужный тип хеша и какова максимальная длинна ключа. Вот для 9-символьного ключа SHA1 нужно качать
690 Gb базу alpha-numeric хешей а для вашего 17 символьного скорее всего таких таблиц не существует.

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

Тоесть хорошая рекомендация в наше время - делать волшебное слово длинее чем 12 символов. И построение
фразы должно быть таким чтобы поиск по справочникам был тоже бесполезен. Ваш ключ также содержит
пробел и это делает применение алфавита alpha-numeric тоже бесполезным. Нужно альфа-нумерик + space.
А таких таблиц я не видел.

Там похоже дата создания файла сохраняется.

$ unzip -l -v opengl.zip  | head
Archive:  opengl.zip
 Length   Method    Size  Cmpr    Date    Time   CRC-32   Name
--------  ------  ------- ---- ---------- ----- --------  ----
13049256  Stored 13049256   0% 2005-05-18 17:19 a814c96e  OpenGL/AdbeRdr602_rus.exe
      42  Stored       42   0% 2004-05-04 03:00 9dd0d91b  OpenGL/Autorun.inf
       0  Stored        0   0% 2006-02-03 18:02 00000000  OpenGL/Catalog/
       0  Stored        0   0% 2006-02-03 18:04 00000000  OpenGL/Catalog/1070801/
    4242  Stored     4242   0% 2005-12-07 16:05 c1c0e4a3  OpenGL/Catalog/1070801/index.htm
  162399  Stored   162399   0% 2005-12-07 16:09 fcb2cedb  OpenGL/Catalog/search.html

Проверь какие у тебя даты.

Что указать в параметре -m - на это отвечает хелп.

$ hashcat --help
hashcat - advanced password recovery

Usage: hashcat [options]... hash|hashfile|hccapxfile [dictionary|mask|directory]...

- [ Options ] -

 Options Short / Long           | Type | Description                                          | Example
================================+======+======================================================+=======================
 -m, --hash-type                | Num  | Hash-type, see references below                      | -m 1000

Очень много. Практически все современные NoSQL-in-memory-dbms используют хеш-таблицы в каком-то варианте.

Хеш-таблицы являются частью механизма буферного кеша (страничного кеша) в дисковых БД. В Oracle, Postgres e.t.c.

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

Дисковые файловые системы могут использовать хеш-таблицы (в зависимости от настроек). Как хранить списки файлов в директориях. Там кажется выбор есть. Дерево или хеш-табличка.

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

int hashCodeRange(int from, int to) {
        final Object[] es = elementData;
        if (to > es.length) {
            throw new ConcurrentModificationException();
        }
        int hashCode = 1;
        for (int i = from; i < to; i++) {
            Object e = es[i];
            hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
        }
        return hashCode;
    }

Используй метод equals. Это будет правильный ответ на собеседовании.

Или какой-то вариант потеряется?

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

По поводу вопроса. Да. Скорее всего какой-то вариант потеряется в силу свойства хеш-функций. Это свойство сюрьекции. Что существует какие-то 2 аргумента что функция даст одно значение для них двоих. Для тройного "ША" будет скорее всего ситуация еще хуже. Тоесть еще больше коллизий. Но мы эти коллизии чорта с два найдем просто в силу того что числа слишком большие и переборные методы здесь нам не друзья.

А зачем здесь две звездочки?

typedef struct hash_table {
  int count;
  int size;
  INFO** array;
}HTAB;

Мне кажется что 1 уровня вложенности достаточно (массив).

Хеш-таблица - это не массив. Хотя она может опираться на массив как на базовую структуру хранения (в случае метода открытой адресации). В классическом варианте хеш таблица - это совокупность структур данных в памяти. Массив массивов. Или массив списков (как будет угодно).

Про количество элементов - это сложный вопрос. Хеш таблица (ХТ) обычно резервирует памяти чуть больше чем надо. И экстендится когда памяти не хватает. Там для экстенда есть отдельный алгоритм. Можно считать что оверхед такой хеш-таблицы больше чем у массива. А количество элементов фактически - хранится отдельным счетчиков.

Вообще русская wiki достаточно хорошо описывает ХТ и можно начать читать с нее и далее по ссылкам.