Я здесь немного порассуждаю на тему деревьев оптимального хранения и всего прочего (ПТ - не считается!).

Мощность функции SHA1 (160 bit) составляет приблизительно 2^160 элементов. Каждый элемент занимает 20 байт или в BINHEX кодировании 40 символов как я привёл ниже для наглядности. Атака грубой силой на SHA1(password) выползет в большой облом т.к. медленно и гиморрно. Исходя из табличной оптимизации, представим гипотетическую базу, которая содержит отображения SHA1 на на искомый пароль (в скобках замечу, что паролей может быть несколько (цепочка) но для простоты пока будем считать что один).



База получается нехилая. Приблизительны размер:



Где AvgPwdLen - средняя длина пароля в символах.
WastedSpace - некая служебная информация (1-2 символа).

Если учитывать хранение в B+Tree (Organization index table) то надо еще добавить накладных 25% расходов на частично заполенные блоки. Вобщем база неподъемная. Но netwind мне подкинул мысль. Собсно если хеши сортированны то ключевой информации в них мало и хранить можно изменения. В таблице я отметил звёздочкой символы-повторы по отношению к предыдущей позиции.

Далее.

Гипотеза1. С линейным ростом количества ключей в RadixTree, физический рост БД должен замедляться прибл. по логарифму от размера, а с учётом колиизий и того медленнее

Гипотеза2. Для успешной атаки на SHA1(pwd) необязательно находить искомый пароль. Достаточно найти пароль-близнец

Гипотеза3. RadixTree хорошо индексируется для поиска по ключу

Эти гипотезы мне предстоит прверить.

Какие нерешённые вопросы.

1. Как оценить возможный рост подобного дерева с учётом RadixTree? Крайний вариант несжатого дерева по формулам неподъёмен и неукладывается ни в одну мыслимую БД ? Самый сжатый вариант, когда цепочки из 4 битов укладываются в один символ и этот символ является узлом виртуального RadixTree технически сложен. Я не представляю какой информации в нём будет больше. Служебной? Или полезной?

2. Как оптимизировать хранение цепочек символов в RadixTree? Есть ли стандартные методологии создания сжатого Read/only RadixTree?

2. Как наполнять? В данном конкретном примере я использовал "Top 500 worst passwords" (просто для наглядности).

4. Когда остановить наполнение? Когда пойдут колиизии хешей (о-о- неужели?) ? Когда весь мыслимый набор словарей общеупотребимых слов на [:alpha:] на всех языках земли будет исчерпан? Когда будут исчерпаны числовые суффиксы. Служебные символы? Когда будет исчерпан алфавит Unicode?

Вобщем поискал я имплементации RadixTree. Ничего толком не нашёл. Почти все работают в оперативной памяти а мне это не подходит.

Буду делать дерево на диске. Макет софта уже написал на Java. Работает медленновато и с глючками но дерево из каталогов уже строит.

В продакшене перенесу на Linux. Основной смысл - поиграться с разными файловыми системами (ext4, XFS, Reiser) и их настройками размера блоков чтобы выбрать ту, которая наиболее компактно хранить множество мелких файлов. Оценивать буду просто. По факту переполнения partition.

Я думал об этом. База (в классической rdbms) не приспособлена для хранения дереьвев. Реализация в лоб - инверсные списки мне не нравится. Много накладных расходов на ссылочные ключики и поиск от корня к листу идёт не очень быстро. Неплохой вариант - использовать иерархическую СУБД но у меня к сожалению опыта работы с такой нету. И изучать её только ради этого эксперимента както неохота. А вариант с файловой системой привлекает своей простотой. В некоторых случаях даже ПО не надо. Можно искать значения pwd ключика просто блуждая по директориям.

Забавно что файловая структура уже не транспортабельна. Я влил в неё около 80 тыс. ключей и попытался сархивировтаь zip-ом и получил ошибку превышения количества узлов на архив. Похоже что распространять её я смогу только как образ диска.

netwindдумаю, соседние отсортированные sha1 при небольшом словаре будут слишком отличаться, чтобы упаковка дала хоть какую-то выгоду. а большой словарь вы уже не потянете просто из-за размеров.
тут вон пасаны никак не могут md5 досчитать http://www.freerainbowtables.com/en/tableprogress/, а вы один на sha1 замахнулись.
Спасибо за информацию по поводу MySQL. Я этого не знал. В принципе мысль сжимать индексы меня беспокоила в контексте Oracle. Если взять к примеру следующий набор пар key:pwd из набора тек которые я уже наформировал

keypwd00FFC7F...................8Daemod00FFC91...................B5afjst

И разбить ключ на композитный следующим образом.

key1key2pwd00FFC7F...................8Daemod00FFC91...................B5afjst

То можно получить некоторое преимущество при использовании опции compressed во время создания индекса. Я пока не планирую использовать Oracle пока до конца не исследую возможности применения ФС.

По поводу RainbowTables. Я не слишком вникал в идею проекта. Но сходу хотел-бы покритиковать их за недостатки.

1) Одна БД в RT расчитывается стого для фиксированного SALT или его отсутствия и известного набора символов [alpha+num].

2) Неизвестна возможность слияния двух баз. Возможно ли это технически?

3) Неизвестно достаточное колиечтво данных для расшифровки. Неизвестно сколько щас хранится частичных (редуцированных) хешей с паролями в БД. ИЛи по крайней мере я не уяснил эту формулу.

Мой проект RainbowTree имеет следущие преимущества.

1) Набор символов паролей одной БД никак не ограничен.

2) Возможно слияние. И очень быстро. При использовании какой нибудь GFS возможно параллельное наполнение БД с нескольких рабочих станций одновременно. Если слегка подправить формат текстового файла паролей в узле , то в одну БД можно бросать хеши и MD5 и Lan Man и SHA1. И это практически не повлияет на производительность и объем.

3) Есть быстрая обратная операция выгрузки бд в плоский. Можно посчитать сколько физически хешей+паролей хранится в данный момент.

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

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

Я не буду спорить по поводу энтропии. Но при достаточно большом количестве ключей моя Гипотеза1 должна работать. Сейчас в моём дереве 7 уровней вложенности (это за 10-15 минут работы генератора паролей из 5 символов). Семь первых символов удалось отобразить в сжатое представление. Дальше нужен расчёт по формулам геометрической прогресси. Каждый новый уровень в 16 раз крупнее предыдущего по количеству ключей. Но каждый дочерний узел содержит ключи на 1 символ меньше родительского.

iv_an_ru,

У пароля не может быть незначащих бит. Все его биты равномерно участвуют в формирования хеша SHA1.

Возможно вы не то хотели сказать?

Это потребует от пользователя помнить дату и вводить её вместе с паролем. В противном случае он не пройдёт форму идентификации. Я таких систем чесно говоря не встречал. Это напоминает SALT если-бы дата была единой для всех пользователей системы, и тогда секретность будет действительно повышена.

iv_an_ru
Скажем, если во всём корпусе паролей используются только символы от 0 до 0x7F, то неважно, что говорит алгоритм про восьмой бит каждого символа --- он заранее известен, может браться не из пароля, а из головы. Значит число значащих бит = 7*макс. длина пароля.
В более общем случае, берите log2 от числа допустимых символов и множьте на максимальную длину пароля, округляйте до целого вверх.
Я понял вашу мысль. На самом деле всё гораздо печальнее. В некоторых системах (Oracle до девятки-десятки) пароли шли в uppercase что еще сильнее сужало область допустимых значений хеша. И символы с кодами number+alpha+control даже могут и не захватывать всю таблицу ASCII до 127 кода. Но основное преимущество моего метода в том, что база бесконечно улучшаема и доступна для изменений. У неё нет критерия "табличности" или 100% заполненности.

P.S. Я еще побарахтаюсь пару дней, и когда мне наскучит возиться с хешами, забью и скажу что был неправ. А свою базу выложу на публичное скачивание. Просто щас изучаю возможности Reiser и надо найти какой-то материальный и весомый тест.

P.P.S. Конечно-же ребята с rainbow tables достигли бОльших успехов (хотя-бы по мегафлопам). Мне их не догнать. Но идея как всегда будоражит ум.

Ладно всем пока. Пошёл отдыхать.

junior idiotДалее: если речь идёт о подборе обычного SHA1(pwd), то в таблицах/деревьях смысла очень немного, так как современная видеокарта позволяет осуществлять переборы со скоростью до 100 миллионов паролей в секунду. Даже если пренебречь расходами памяти на "служебные" нужды, и даже на хеши, это соответствует 60+ терабайтам в сутки (при оптимистичном допущении, что средняя длина пароля 8 символов). То есть, если вы отведёте под свои неведомым образом организованные таблички 60+ терабайт (реально в 3-5 раз больше), то выиграете сутки работы видеокарты. Неужели оно того стоит?
Диск+Процессор(ы) это ресурсы которые следует использовать совместно. Я нисколько не умаляю достоинств современных GPU но даже им для расчета SHA2 512/384 бит потребуется больше времени. И поэтому любое техничное решение должно базироваться не на маргинальных а на усреднённых режимах использования всего оборудования. Т.е процессора+диска. Разумеется построить дерево, охватывающее ВСЕ 2^160 ключей нереально. Мне даже выше подсказали, что при полном использовнии алфавита ANSI я оставляю 8-й бит неиспользованым и следовательно конечный автомат SHA1 имеет (теоретически) недостижимые или слабо-достижимые состояния в которые его трудно вогнать таким узким распределением сингалов на входе.

Сегодня я уже отказался от ReiserFS и от декомпозиции ключ->файл.

Я буду использовать обычную файловую систему со стандартным размером блока, но ключи буду группировать по перфиксам.

Например

Файл с префиксами 00/634 ключа:

/sha1/database/00/634

Будет хранить значения суффикса.

И некоторое значение расчитанных паролей.

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

Вопрос хранения данных в БД по прежнему открытый. Но пока у меня еще нет ВРЕМЕННЫХ данных. Я не могу оценить, сколько мне надо места и не знаю среднюю скорость своего алгоритма. Как только она появиться я тут-же поделюсь цифрами.

По поводу коллизий SHA и ваших формул расчета скорости я не готов ответить. Надо подумать.