mayton2019

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

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

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

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

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

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

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

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

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

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

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

Хеши бывают разной длины. От 8 бит до 512 бит. И в зависимости от сложности самой функции
и от разрядности возможны такие ситуации что для разных файлов вдруг хеш совпадает.

В криптографии отдельно изучают парадокс дней рождений (когда группа случайных людей порядка
20 человек вдруг имеет 50% вероятность нахождения пары людей с одинаковой датой рождения
вида MM/DD). Вобщем этот парадокс для криптунов - шибко важный и они носятся с ним везде
и любят обсуждать применительно к атакам на шифры и ЭЦП.

Кажется Брюс Шнайер предлагал свою метрику для ожидания коллизий в зависимости от длины
ключа.

В Java существовала атака на хеш-мап основанная на том что хеш-функция несовершеннаа
и может давать коллизии.

Для латиницы

public static int hashCode(byte[] value) {
        int h = 0;
        byte[] var2 = value;
        int var3 = value.length;
        for(int var4 = 0; var4 < var3; ++var4) {
            byte v = var2[var4];
            h = 31 * h + (v & 255);
        }
        return h;
    }

Насколько я понимаю ни к чему страшному атака не приводила. Просто хеш-мапа вырождалась
в список и некоторые тайм-критичные системы (Tomcat/Jetty) могли тормозить на отдаче хедеров.
Фиксилось это просто заменой бакетов хеш-табли на деревья при определенном условии. ТАм
было что-то вроде - если длина цепочки в бакете больше чем константа - то генерировать дерево.

Вобщем некоторые кибер-задроты не поленились и нашли такие строки которые дают одинаковые хеши.

Некоторые хеш-функции (CRC-32) обладают интересными свойствами. На диапазоне целых до 4 млрд
эта функция вообще дает 0 коллизий и точно отображает ключ в бакет. Кажется это свойства
тех полиномов на базе которых CRC вообще строятся. (Насчет CRC я точно не уверен. Мой приятель
этот факт проверял на С++).

Я честно говоря считал что в хешах уже все известно но периодически их придумывают новые с разными
свойствами. Вот для нужд биг-даты в 2008 был придуман Mur-mur https://en.wikipedia.org/wiki/MurmurHash

И еще примерно 9 лет назад один чел создал хеш-функцию xxhash которая якобы супер-быстрая
https://github.com/Cyan4973/xxHash но я не мерял. Такая себе функция-шустрик.

Вобщем из свойств раздличают криптографические (SHA) (трудно создать коллизию) и вот эти вот шустрики
которые летают как CPU и годятся для хешей но при этом ЭЦП на них строить не рекомендуется.

В 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 достаточно хорошо описывает ХТ и можно начать читать с нее и далее по ссылкам.