Fernus
@Fernus
Техник - Механик :)

Preimage — атака нахождения прообраза. Теория + практика. Пофантазируем?

Вообщем нечаянно наткнулся вот на эту тему:
https://qna.habr.com/q/929645

Суть задачи (чтобы не нырять по ссылке) цитирую:
сколько будет подбираться md5 хэш по этой маске:
?????????.??.??????????????????
где:
? - любое число от 0 до 9
. - неизменяемый символ
И сколько ресурсов для этого понадобиться?)


Ради интереса упростил немного( точнее много:) ) её до:
XXXXXXXXX.XX.??????????????????
где:
X - известное число

MD5 заранее известен - нужно подобрать текст к этому хэшу по заданной маске.

На своём ноуте с картой NVIDIA GTX 1050 Ti мне бы понадобилось около 150 лет... :)

Вопросы:
1. Сколько понадобится компов объединённых вместе, чтобы решить эту задачу (мою и автора вопроса по ссылке)?
2. Какими технологиями можно их объединить, чтобы задействовать ресурсы других компов через сеть(интернет)?
Если взять во внимание то, что другие эти компы будут согласны участвовать в таком эксперименте, но у них разные ОС и они обычные юзеры(аля сижу смотрю ютуб и тыкаю инсту).

UPD:
Все ответы имеют место быть - отметил решением.
Думаю, можно расходиться :)
Чисто был мозговой штурм перед сном))
Данную задачу нельзя решить за 5 минут...в разумных пределах исчисляемых ресурсами...
  • Вопрос задан
  • 223 просмотра
Решения вопроса 4
hint000
@hint000
у админа три руки
2. Какими технологиями можно их объединить, чтобы задействовать ресурсы других компов через сеть(интернет)?

https://ru.wikipedia.org/wiki/BOINC
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Подсчитайте, сколько различных текстов подходят под ваш паттерн (каждый ? дает 10 вариантов - всего 10^k, где k - количество ? в шаблоне).

Посмотрите, сколько ваша видео карточка выдает хэшей. Беглый гуглеж дает что-то порядка 3Ghash/s Поделите 10^k на 3*10^9 - получите максимальное время в секундах. Можно ожидать, что в среднем понадобится половина этого времени.

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

Если я не сбился в расчетах, то вам понадобится 5-6 лет на одной карточке, чтобы подобрать текст. Если вы готовы ждать месяц, то вам понадобится 600 компов в кластере.
Ответ написан
jcmvbkbc
@jcmvbkbc
"I'm here to consult you" © Dogbert
Сколько понадобится компов объединённых вместе, чтобы решить эту задачу (мою и автора вопроса по ссылке)?

Решение этой задачи перебором идеально распараллеливается, даже в уме. Поэтому если взять N компов, решение найдётся в N раз быстрее.

На своём ноуте с картой NVIDIA GTX 1050 Ti мне бы понадобилось около 150 лет... :)

Соответственно, 150 таких компов справятся за год, а 1314000 таких компов -- за час.
Ответ написан
Fernus
@Fernus Автор вопроса
Техник - Механик :)
Как бы банально не звучало: wikipedia всё чётко объясняет :)

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

Атака нахождения первого прообраза: по данному значению хеша h найти такое сообщение m, что hash(m) = h.[1]
Атака нахождения второго прообраза: по данному сообщению m1 найти отличное от него сообщение m2 такое, что hash(m2) = hash(m1).[1]
Для идеальной n-битовой хеш-функции сложность нахождения первого прообраза составляет 2n, что считается высоким показателем, учитывая среднюю длину хеш-значений (порядка 160 бит). Если злоумышленник не может провести атаку с меньшими затратами, то такая хеш-функция считается устойчивой к атаке нахождения прообраза.

Разработанные на сегодняшний момент атаки на прообраз не являются практически пригодными. Если такую атаку возможно будет применить на практике, то это сильно повлияет на многие протоколы сети Интернет. В данном ключе, слово «практический» означает, что атака может быть проведена за разумное время при разумных затратах. Атака по нахождению прообраза, которая стоит миллиарды и занимает десятилетия вычислений, совсем не практична; в то же время атака, на которую уйдёт всего несколько тысяч долларов и несколько недель вычислений, применима на практике.

Все известные на сегодняшний момент применимые или почти применимые на практике атаки[2][3][4] на MD5 и SHA-1 — это коллизионные атаки, которые легче для проведения[5]. Устойчивость к нахождению прообраза можно свести к устойчивости к коллизиям.



Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Changellenge >> Москва
от 255 000 до 490 000 ₽
Changellenge >> Москва
от 255 000 до 490 000 ₽
07 окт. 2024, в 08:54
15000 руб./за проект
07 окт. 2024, в 07:12
15000 руб./за проект