Айтишники хелп

Ку всем

Челы-информатики, объясните почему чел в видосе 

говорит, что чтобы отгадать что было инпутом в хеш алгоритм SHA256, нужно в среднем 2 в 256 степени попыток?

Ведь это просто неправда. Да, ты можешь найти такой инпут, который даст ТАКОЙ ЖЕ аутпут, как ИСКОМЫЙ инпут, но найти искомый инпут как таковой невозможно из-за потери информации при хешировании.

Или я не прав?

 

 

Перебираемые значения хешируешь и проверяешь со своим хешем.

Ничего там не теряется, чел выше прав

Это называется Коллизия.

 

Это ОДИН ИЗ способов разрешения коллизий. Если очень коротко. 

 

Коллизии необходимо максимально уменьшать.

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

чтоб найти оригинальный Закрытый ключ, необходимо сравнивать по времени вычислений в таком случае худшее время поиска будет O(n). И сравнивать его с таймингом работы от оригинального Закрытого ключа.

http://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BA%D0%BE%D0%BB%D0%BB%D0%B8%D0%B7%D0%B8%D0%B9

Ferum сказал(а):↑

Это называется Коллизия.

 

Это ОДИН ИЗ способов разрешения коллизий. Если очень коротко. 

 

Коллизии необходимо максимально уменьшать.

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

чтоб найти оригинальный Закрытый ключ, необходимо сравнивать по времени вычислений в таком случае худшее время поиска будет O(n). И сравнивать его с таймингом работы от оригинального Закрытого ключа.

http://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BA%D0%BE%D0%BB%D0%BB%D0%B8%D0%B7%D0%B8%D0%B9

Нажмите, чтобы раскрыть...

А теперь ещё раз только своими словами

 

 

sad_summer сказал(а):↑

Ничего там не теряется, чел выше прав

Нажмите, чтобы раскрыть...

Откуда инфа что ничего не теряется?

При хешировании используется оператор мод. Так что как минимум он теряет информацию об инпуте

aQuere сказал(а):↑

А теперь ещё раз только своими словами

 

Нажмите, чтобы раскрыть...

Блин а куда ещё проще Брат?) Ты "Закрытый ключ" не понял что такое это как раз твой "Импут".

aQuere сказал(а):↑

А теперь ещё раз только своими словами

 

 

Откуда инфа что ничего не теряется?

Нажмите, чтобы раскрыть...

Одно из требований для хэш функций - это детерминированность, т.е. одни и те же данные дают одно и то же значение хэша. 

sad_summer сказал(а):↑

Одно из требований для хэш функций - это детерминированность, т.е. одни и те же данные дают одно и то же значение хэша. 

Нажмите, чтобы раскрыть...

sad_summer сказал(а):↑

Ничего там не теряется, чел выше прав

Нажмите, чтобы раскрыть...

И как эти две вещи вообще связаны?

aQuere сказал(а):↑

И как эти две вещи вообще связаны?

Нажмите, чтобы раскрыть...

А всё я понял тебя, сорян не правильно прочитал. Виноват

 

aQuere сказал(а):↑

как ИСКОМЫЙ инпут, но найти искомый инпут как таковой невозможно из-за потери информации при хешировании.

Нажмите, чтобы раскрыть...

Почему невозможно то? Один из найденных инпутов искомый, а это множество уже перебрать не составит труда

sad_summer сказал(а):↑

А всё я понял тебя, сорян не правильно прочитал. Виноват

 

Нажмите, чтобы раскрыть...

Да все ок.

Я вот ещё о чем подумал: раз разные инпуты могут давать один аутпут (коллизия), то я могу войти в свой акк с д2ру вообще с другим паролем, потому что наши пароли прежде чем попасть в базу данных хешируются и при логине хеш введённого пароля сравнивается с хешем пароля при регистрации

 

Cloud In Pants сказал(а):↑

Почему невозможно то? Один из найденных инпутов искомый, а это множество уже перебрать не составит труда

Нажмите, чтобы раскрыть...

Но ты ведь понимаешь что это множество, которое для тебя перебрать нет труда (лол) - оно бесконечно?!

Каким образом бесконечность перебирать будем?

aQuere сказал(а):↑

А теперь ещё раз только своими словами

Нажмите, чтобы раскрыть...

Касательно приведённого способа. Если у тебя есть возможность оследить время работы хэшФункции на машине жертвы, то Хеш от разных импутов будет считаться за разное время, при взломе SHA256 у тебя получится допустим 10 импутов с одинаковым хэшем. Только один из этих импутов и Есть оригинальный Пароль жертвы. Тогда тебе необходимо оследить время работы, т.к. от разного импута оно будет отличаться. И тогда ты сможешь определить оригинальный пароль жертвы по совпадению времени работы ХэшФункции. Это один из способов решения колизиий.

По факту ты лишь немного сузишь и узнаешь что некоторые пароли не подходят, т.к. от некоторых импутов время расчёта будет одинаковое.т.е ты половину неверных ипутов таким способов отсечёшь. Поэтому и есть термин "Сужать коллизию" и соответственно ещё есть способы... крч ты понял я думаю.

 

Ferum сказал(а):↑

Касательно приведённого способа. Если у тебя есть возможность оследить время работы хэшФункции на машине жертвы, то Хеш от разных импутов будет считаться за разное время, при взломе SHA256 у тебя получится допустим 10 импутов с одинаковым хэшем. Только один из этих импутов и Есть оригинальный Пароль жертвы. Тогда тебе необходимо оследить время работы, т.к. от разного импута оно будет отличаться. И тогда ты сможешь определить оригинальный пароль жертвы по совпадению времени работы ХэшФункции. Это один из способов решения колизиий. 

 

Нажмите, чтобы раскрыть...

Но согласись, что мы работаем в рамках человеческих паттернов поведения в выборе пароля. То есть он обычно определённой небольшой длины, определённые символы итд -  под это можно оптимизировать алгоритм поиска инпута и шансы твоего успеха будут далеко не 0.

НО если говорить без привязки к контексту, то узнать инпут невозможно, потому что такой аутпут хеш функция выдаёт для бесконечного числа инпутов

 

aQuere сказал(а):↑

Да все ок.

Я вот ещё о чем подумал: раз разные инпуты могут давать один аутпут (коллизия), то я могу войти в свой акк с д2ру вообще с другим паролем, потому что наши пароли прежде чем попасть в базу данных хешируются и при логине хеш введённого пароля сравнивается с хешем пароля при регистрации

 

Но ты ведь понимаешь что это множество, которое для тебя перебрать нет труда (лол) - оно бесконечно?!

Каким образом бесконечность перебирать будем?

Нажмите, чтобы раскрыть...

Ничего в жизни не видал бесконечного. То же количество паролей ограниченно их паттерном.

Cloud In Pants сказал(а):↑

Ничего в жизни не видал бесконечного. То же количество паролей ограниченно их паттерном.

Нажмите, чтобы раскрыть...

А, ну раз ты не видел, то и нет этого

Понял, отстал

aQuere сказал(а):↑

Но согласись ты мы работаем в рамках человеческих паттернов поведения в выборе пароля. То есть он обычно определённой небольшой длины, определённые символы итд -  под это можно оптимизировать алгоритм поиска хеша и шансы твоего успеха будут далеко не 0.

НО если говорить без привязки к контексту, то узнать инпут невозможно, потому что такой аутпут хеш функция выдаёт для бесконечного числа инпутов

Нажмите, чтобы раскрыть...

Знание числа символов и тд безусловно снизит временную сложность взлома.

Есть ситуации когда можно узнать импут, есть ситуации когда невозможно. На эту тему можно часами дискутировать)

А вот если есть доступ к пк жертве, а вот если мы знаем что человек небрежный и вводит короткий пароль, а вот если у нас есть троян который отслеживает такты процессора и тд...

Ferum сказал(а):↑

Знание числа символов и тд безусловно снизит временную сложность взлома.

Есть ситуации когда можно узнать импут, есть ситуации когда невозможно. На эту тему можно часами дискутировать)

А вот если есть доступ к пк жертве, а вот если мы знаем что человек небрежный и вводит короткий пароль, а вот если у нас есть троян который отслеживает такты процессора и тд...

Нажмите, чтобы раскрыть...

А поч у тебя инпут импут?

 

Ferum сказал(а):↑

Знание числа символов и тд безусловно снизит временную сложность взлома.

Есть ситуации когда можно узнать импут, есть ситуации когда невозможно. На эту тему можно часами дискутировать)

А вот если есть доступ к пк жертве, а вот если мы знаем что человек небрежный и вводит короткий пароль, а вот если у нас есть троян который отслеживает такты процессора и тд...

Нажмите, чтобы раскрыть...

Охренеть интересная фигня во втором абзаце

Звучит круто, по хакерски

 Вчера в 21:38

Ferum сказал(а):↑

 Вчера в 21:38

Нажмите, чтобы раскрыть...

Этошо

aQuere сказал(а):↑

Этошо

Нажмите, чтобы раскрыть...

Невозможность делМеседжей, крч забей Бро)

Ferum сказал(а):↑

Невозможность делМеседжей, крч забей Бро)

Нажмите, чтобы раскрыть...

Ты тут всех бро и братьями называешь почему-то, ещё и с большой буквы

Чисто на позитиве чел

aQuere сказал(а):↑

Ты тут всех бро и братьями называешь почему-то, ещё и с большой буквы

Чисто на позитиве чел

Нажмите, чтобы раскрыть...

Я могу быть не прав, но алгоритм шифрования работает следующим образом: ты берёшь исходное сообщение, потом генерируешь ключ и после всё это засовываешь в алгоритм шифрования. На выходе получаешь зашифрованное сообщение.

Злоумышленник перехватывает зашифрованное сообщение. Для дешифровки ему нужен ключ, знание алгоритма шифрования и после этого реверсировать его. Ключ в SHA256 - строка из 0 и 1 длинной в 256 символов. Состояний клетки 2, клеток 256 = 2 ^256 вариантов.

ARXUMAG сказал(а):↑

Я могу быть не прав, но алгоритм шифрования работает следующим образом: ты берёшь исходное сообщение, потом генерируешь ключ и после всё это засовываешь в алгоритм шифрования. На выходе получаешь зашифрованное сообщение.

Злоумышленник перехватывает зашифрованное сообщение. Для дешифровки ему нужен ключ, знание алгоритма шифрования и после этого реверсировать его. Ключ в SHA256 - строка из 0 и 1 длинной в 256 символов. Состояний клетки 2, клеток 256 = 2 ^256 вариантов.

Нажмите, чтобы раскрыть...

Хеширование и шифрование это разные вещи, в шифровании есть понятие дешифровки - возвращения к изначальному значению. В хешировании - нет. С помощью sha256 ты можешь захешировать 4 тома войны и мира в 64-символьный HEX, каким образом можно подобное дешифровать? Там даже малой части этой информации физически быть не может.

Ramdesu сказал(а):↑

Хеширование и шифрование это разные вещи, в шифровании есть понятие дешифровки - возвращения к изначальному значению. В хешировании - нет. С помощью sha256 ты можешь захешировать 4 тома войны и мира в 64-символьный HEX, каким образом можно подобное дешифровать? Там даже малой части этой информации физически быть не может.

Нажмите, чтобы раскрыть...

Честно говоря, как я понял видео ТСа, это ответ на какую-то фразу из другого видео т.е. не совсем понятно для чего конкретно используется алгоритм в том случае. Как я понимаю возможно 2 варианта:

1) исходное сообщение довольно малой длины и там нет коллизий - например в случае, если исходный месседж меньше ключа.

2) ТС не правильно понял видео и речь идёт не об нахождении исходного сообщения, а об его изменении т.е. у меня есть сообщение "Вася должен Пете 100 руб" и хеш "123", я нахожу ключ, при котором сообщение даёт нужный хеш и тогда я могу отправить дальше "Вася должен Пете 1000 бачей" + новый хеш и это пройдёт проверку у верификатора.

ARXUMAG сказал(а):↑

2) ТС не правильно понял видео и речь идёт не об нахождении исходного сообщения, а об его изменении т.е. у меня есть сообщение "Вася должен Пете 100 руб" и хеш "123", я нахожу ключ, при котором сообщение даёт нужный хеш и тогда я могу отправить дальше "Вася должен Пете 1000 бачей" + новый хеш и это пройдёт проверку у верификатора.

Нажмите, чтобы раскрыть...

Я почему-то не посмотрел видео, из-за которого начался разговор изначально. Посмотрел, теперь я понял, о чем вообще речь, и вот, что я думаю:

1. Да, сообщения автора о коллизиях не имеют смысл. Тебе подойдет ЛЮБОЙ ключ, который может генерировать тот же самый хеш при хешировании его + сообщения, этого достаточно для подделки сообщения. Вообще без разницы является ли этот ключ изначальным или нет, задача по взлому будет выполнена. Само изначальное значение, конечно же, найти не представляется возможным, из-за того, что входных данных, как указал автор, намного больше (бесконечно), чем хешей (в случае с SHA256 их размер ограничен 256 битами = 64 символами HEX), а значит у любого значения будет большое количество коллизий.

 

2. Речь в видео про хеширование, НЕ шифрование. Дешифровать хеш НЕЛЬЗЯ. Ключ, о котором идет речь, - это по сути не секретный ключ, который используется при шифровании и с помощью которого можно дешифровать сообщение, а статическая соль для хеширования. Смысл в том, что при хешировании вместе с хешируемым сообщением мы кладем в функцию хеширования "секретный ключ" - соль, т.е. видоизменяем реальный аргумент, который мы хешируем, чтобы получить на выходе другой хеш. Это нужно для того, чтобы другой человек не мог хешировать свои поддельные сообщения с помощью того же алгоритма хеширования - соль кардинально меняет получаемый хеш. К примеру, таким образом работает HMAC, он позволяет обеспечить устойчивость сообщений от их модификации сторонними пользователями. Такое используется, например, в JWT. С помощью сикрета хешируется пейлоад + хедер. 

 

Вот как это подробно работает:  

 

Описание принципа работы JWT

При логине сервер генерирует JWT. Чтобы его можно было проверить, он использует HMAC (подход, похожий на тот, о котором рассказывается в видео. Первом, которое про крипту и из-за которого появился этот видеоответ) - он берет пейлоад и хедер (мейл юзера, алго хеширования и прочее) и хеширует его с добавлением в аргумент хеш функции статической соли ("секретного ключа"). JWT передается юзеру и далее с помощью него он авторизует свои действия.  

 

JWT состоит из ТРЕХ частей. Первая - header (алгоритм хеширования + какие-то другие мета данные), вторая - payload (данные о токене - login юзера (чтобы его можно было найти), время генерации токена (чтобы можно было проверять его валидность по времени) и другие, третья - HMAC, полученный хешированием header + payload + secret. Заметь, и header, и payload ПУБЛИЧНЫЕ, они шифруются с помощью base64. Их можно просмотреть даже не зная secret. Secret нужен только для сверки HMAC (при получении сервером JWT он проводит такое же хеширование header + payload + secret и сравнивает хеши). Сервер НЕ может получить изначальные данные и НЕ получает их из хеша. Повторюсь, это невозможно, и именно по этой причине в JWT есть два публичных блока с инфой, которые не нуждаются в дешифрации с помощью сикрета.

 

Для чего я это объяснял сверху? Для того, чтобы показать, что подход с HMAC, подобие которого используется в видео автора, никак не связан с обратной дешифровкой хеша в изначальные данные. Изначальные данные в этих случаях НЕ скрыты от юзера. Просто для гарантии сохранности их целостности и неизменности используется специальный ключ (подпись), полученный хешированием мессаджа + секретного ключа. Подобную подпись, логично, может сгенерировать только тот, кто имеет доступ к секретному ключу.  

 

При чем способ, который был в видео автора о крипте, является чем-то вроде улучшенной версии HMAC, потому что в HMAC обе стороны (валидирующая и отправляющая) должны знать секретный ключ. В случае с тем способом, который был в видео, валидирующая сторона должна знать только публичный ключ. Отправляющая - секретный  

 

Если подвести итог, то вычислительно получить из хеша любое из изначальных значений, которое при хешировании выдаст такой хеш, НЕВОЗМОЖНО. Это критерий того, является ли хеш функция криптографической (пригодной для использования в криптографии). Функция хеширования - это односторонняя функция, не обратимая, какого бы размера ни был инпут (ты указывал, что мол если он будет меньше аутпута, то это сработает). Какой бы ты информацией ни обладал, тебе нужно будет делать подбор - к примеру, с помощью вышеупомянутых радужных таблиц.

 

ARXUMAG сказал(а):↑

это ответ на какую-то фразу из другого видео

Нажмите, чтобы раскрыть...

Изначальное видео тут - https://www.youtube.com/watch?v=bBC-nXj3Ng4

 

Где-то с 4 минуты рассказывается про подписи

 

ARXUMAG сказал(а):↑

2) ТС не правильно понял видео и речь идёт не об нахождении исходного сообщения, а об его изменении т.е. у меня есть сообщение "Вася должен Пете 100 руб" и хеш "123", я нахожу ключ, при котором сообщение даёт нужный хеш и тогда я могу отправить дальше "Вася должен Пете 1000 бачей" + новый хеш и это пройдёт проверку у верификатора.

Нажмите, чтобы раскрыть...

На самом деле я вчитался и в этом сообщении ты уже указал по сути то же самое, что и я. Хеш используется для верификации. Удалять пост выше не буду, потому что в прошлом сообщении ты указывал, что "для дешифровки ему нужен ключ", что не является правдой, дешифровать сообщение не получится, но подобрать подпись для верификации - получится. Похоже, у нас произошло недопонимание, и ты по сути это и имел ввиду, а я триггернулся на термин "дешифрации". Все равно оставлю, может сообщение принесет ценность для кого-то даже если для тебя это предельно ясно было изначально

 

И да, ты прав, и правильно ответил на вопрос автора. Для того, чтобы подобрать 256 бита нужно максимум 2^256 попыток просто потому, что существует всего 2^256 возможных комбинаций. И тут речь вообще не об угадывании инпута, который дает такой хеш, а об угадывании самого хеша. Т.е. ты не сикрет находишь, а потом генеришь сколько угодно поддельных сообщений, а формируешь поддельное сообщение и потом пытаешься подобрать ИМЕННО к нему 256-битный хеш. Тогда да, попыток будет 2^256. Если речь про угадывание самого сикрета, то сложность его угадывания будет зависеть уже от его длины и используемого пула символов