Здравствуйте, FDSC, Вы писали:
FDS>Странно, я не нашёл (я нашёл только этоАвтор: Relayer
Дата: 14.05.06
. Или это оно и есть?)
угу. эт меня склероз замучал. насчет битовых массивов я пару лет назад писал в другую конфу
вот порылся на диске и нашел:
============================================================================
1. Прелюдия
Задача: есть множество (предварительно сгенерированных) серийных
номеров, необходимо построить хеш-таблицу, которая будет вычислять
принадлежность произвольной строки этому множеству.
Решение 1:
хеш функция H()
битовый массив B
if B[H(sn)] == 1 then sn is valid
недостаток — высокий уровень ложного срабатывания
Решение 2 (Probabilistic Spell Checker):
хеш функции H1()..Hn()
битовый массив B
if B[Hj(sn)] == 1 для всех 1<=j<=n then sn is valid
весь остальной материал относится к вариации на 2е решение.
2. Практика
на практике вполне легко добиться вероятности ложной идентификации
порядка 10^-8 (при мощности множества серийных номеров порядка 10^4).
такое решение позволяет нам получить ответ на вопрос валиден серийный
номер или нет. но оно имеет и отрицательную сторону — взломщик легко
может вычислить значения хешфункций для некотрого серийника и
установить соответствующие биты в "1" (т.е. пропачить хештаблицу).
усложним ему работу
рассмотрим битовую строку:
HB = ( B[H1(sn)], B[H2(sn)], B[H3(sn)], ... B[Hn(sn)] )
мы требовали чтобы в случае валидного сериника все ее элементы были
равны "1". откажемся от этого
при генерации хеш таблицы выберем
некоторую константу KEY (размереностью n бит). потребуем чтобы
валидный серийник выдавал HB == KEY (это приведет к некоторому
усложнению формирования хештаблицы B). что мы имеем в данном случае ?
взломщику не известна константа KEY (программа в дальнейшем может этой
константой расшифровывать блоки кода).
тестовый прогон дал такие результаты:
размер B = 2^18 бит (32 Кб)
кол-во хеш функций n = 32 (использовался SHA1)
SizeOf(HB) == SizeOf(KEY) == n == 32 бита
кол-во используемых бит в хештаблице B = 41% (остальные биты заполнены
мусором)
кол-во серийных номеров = 3868
общее кол-во перебраных кандидатов в серийные номера ~= 10^6
время ~= 5 мин (P3 1Gz)
3. блек лист
при дискредитации серийного номера его не такто просто вычекнуть из
хеш-таблицы, т.к. одни и теже биты могут использоваться несколькими
серийниками из списка. для возможности "вычеркивания" введем следующее
условие: некоторая (nfix <= n) часть битов в HB из таблицы B должна
принадлежать только этому серийнику и никаким другим. для вычеркивания
серийника из таблицы достаточно установить в другое состояние его
"уникальные" биты. это никоим образом не отразится на верификации других
серийниках.
был проведен тестовый прогон с nfix = 8. результаты практически те же
что и без "уникальных" битов.
4. детали
4.1 ничто не запрещает нам наложить более сложное условие чем
HB == KEY
например:
HB xor HH(sn) == KEY
здесь HH() — некотрая хешфункция
4.2 при формировании хештаблицы достаточно легко достичь ее коэф.
заполнения порядка 50%. дальше начинаются существенные пробуксовки
4.3 заполнение неиспользуемых элементов в таблице B "мусором"
существенно усложняет реверсирование схемы
4.4 нет особых ограничений на вид серийника. при тестировании я
использовал серийники из 9ти символов (буквы+цифры). мощность
множества серийников 2^(9*5) = 2^45
4.5 ложка дегтя
при дискредитации ключа KEY, очень сложно
сформировать хештаблицу для тех же серийников и другого ключа.
5. финита ля комедия
утверждение 4.5 портит всю картину. но если мы выберем nfix == n (т.е.
потребуем чтобы все биты в строке HB были "уникальными") то смена
ключа будет полностью безболезненной.
тестовый прогон:
размер B = 2^18 бит (32 Кб)
кол-во хеш функций n = 32 (использовался SHA1)
nfix == n == 32
SizeOf(HB) == SizeOf(KEY) == n == 32 бита
кол-во используемых бит в хештаблице B = 25% (остальные биты заполнены
мусором)
кол-во серийных номеров = 2503
общее кол-во перебраных кандидатов в серийные номера ~= 2*10^7
время ~= 2 часа (P3 1Gz)
отмечу что увеличивая размер B можно практически во столько же раз
увеличить кол-во серийников которые можно "втиснуть" в хеш.
т.е. при 64 кб ~= 5*10^4 серийников
128 кб ~= 10^5 серийников
============================================================================
(c) на все это — мой. вобщем юзайте на здоровье
Здравствуйте, sergey2b, Вы писали:
R>>в направлении регистрации на форуме и заполнения профиля.
S>я зарегистрировался.
одним анонимом стало меньше
ну и то хорошо
S>Могли бы вы рассказать каким образом можно вставить в программу пароль для расшифровки зашифрованного кода что бы его не могли найти или как можно использовать несколько паролей для расшифровки одного и того же участка кода. Конечная цель если пароль принадлежит ключу из блек листа его не возможно было использовать для расшифровки участка кода.
вообще в идеале ключ(пароль) для расшифровки кода должен получаться в процессе верификации ключа. и естественно его нет ни в каком виде в серийнике. некоторые ассиметричные криптоалгоритмы позволяют это сделать. т.е. результат верификации серийника должен быть не ответ да/нет, а некоторый инвариант, который одинаков для всех серийников. как это сделать — очень сильно зависит от выбранного алгоритма.
