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

Question

[N]

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

Суть задачи (чтобы не нырять по ссылке) цитирую:

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

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

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

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

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

UPD:
Все ответы имеют место быть - отметил решением.
Думаю, можно расходиться :)
Чисто был мозговой штурм перед сном))
Данную задачу нельзя решить за 5 минут...в разумных пределах исчисляемых ресурсами...

Comments

[Wataru]

Непонятен вопрос. Вам надо подобрать текст соответствующий заданной маске, чтобы он имел известный md5 хеш? Или вам надо подобрать текст, чтобы его хэш удовлетворял заданной маске?

[N]

Wataru, Да, MD5 заранее известен.
P.S.: Подправил вопрос, чтобы понятнее было.

[Антон Шаманов]

эта тема в большинстве случаев не имеет смысла т.к. срок жизни токена обычно не более суток.

[N]

Антон Шаманов, Скажу больше...в "голове" я себе ставил задачу минут в 3-5 :)
У меня нет столько "друзей" для эксперимента, чтобы замутёхать такой кластер :)

Answer 1

[hint000]

2. Какими технологиями можно их объединить, чтобы задействовать ресурсы других компов через сеть(интернет)?

https://ru.wikipedia.org/wiki/BOINC

Comments

[N]

Спасибо за ответ. Поизучаю)

Answer 2

[Wataru]

Подсчитайте, сколько различных текстов подходят под ваш паттерн (каждый ? дает 10 вариантов - всего 10^k, где k - количество ? в шаблоне).

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

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

Если я не сбился в расчетах, то вам понадобится 5-6 лет на одной карточке, чтобы подобрать текст. Если вы готовы ждать месяц, то вам понадобится 600 компов в кластере.

Comments

[N]

Я готов ждать не больше 3 минут максимум :)
Но траектория логики понятна))

Answer 3

[jcmvbkbc]

Сколько понадобится компов объединённых вместе, чтобы решить эту задачу (мою и автора вопроса по ссылке)?

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

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

Соответственно, 150 таких компов справятся за год, а 1314000 таких компов -- за час.

Comments

[N]

Такую математику я крутил в голове тоже)
Получается для полноценного эксперимента мне нужно около 1/10 населения РФ :)
Жёстко :)

Просто вдруг есть ещё какие способы)) Но уже вижу, что - вряд ли))

[Василий Банников]

N, ну майнеры такую задачу решают при помощи всяких FPGA)

[N]

Василий Банников, Здесь в контексте обычных компов и "смертных" юзеров была задача :)

Answer 4

[N]

Как бы банально не звучало: wikipedia всё чётко объясняет :)

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

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

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

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

Источник

https://ru.wikipedia.org/wiki/%D0%90%D1%82%D0%B0%D...