Хеширование – что это и зачем
Криптографические хеш-функции — незаменимый и повсеместно распространенный инструмент, используемый для выполнения целого ряда задач, включая аутентификацию, проверку целостности данных, защиту файлов и даже обнаружение зловредного ПО.
Существует масса алгоритмов хеширования, отличающихся криптостойкостью, сложностью, разрядностью и другими свойствами. Считается, что идея хеширования принадлежит сотруднику IBM, появилась около 50 лет назад и с тех пор не претерпела принципиальных изменений.
Зато в наши дни хеширование обрело массу новых свойств и используется в очень многих областях информационных технологий.
Что такое хеш?
Если коротко, то криптографическая хеш-функция, чаще называемая просто хешем, — это математический алгоритм, преобразовывающий произвольный массив данных в состоящую из букв и цифр строку фиксированной длины.
Причем при условии использования того же типа хеша длина эта будет оставаться неизменной, вне зависимости от объема вводных данных.
Криптостойкой хеш-функция может быть только в том случае, если выполняются главные требования: стойкость к восстановлению хешируемых данных и стойкость к коллизиям, то есть образованию из двух разных массивов данных двух одинаковых значений хеша.
Интересно, что под данные требования формально не подпадает ни один из существующих алгоритмов, поскольку нахождение обратного хешу значения — вопрос лишь вычислительных мощностей. По факту же в случае с некоторыми особо продвинутыми алгоритмами этот процесс может занимать чудовищно много времени.
Как работает хеш?
Например, мое имя — Brian — после преобразования хеш-функцией SHA-1 (одной из самых распространенных наряду с MD5 и SHA-2) при помощи онлайн-генератора будет выглядеть так: 75c450c3f963befb912ee79f0b63e563652780f0. Как вам скажет, наверное, любой другой Брайан, данное имя нередко пишут с ошибкой, что в итоге превращает его в слово brain (мозг).
Это настолько частая опечатка, что однажды я даже получил настоящие водительские права, на которых вместо моего имени красовалось Brain Donohue. Впрочем, это уже другая история. Так вот, если снова воспользоваться алгоритмом SHA-1, то слово Brain трансформируется в строку 97fb724268c2de1e6432d3816239463a6aaf8450.
Как видите, результаты значительно отличаются друг от друга, даже несмотря на то, что разница между моим именем и названием органа центральной нервной системы заключается лишь в последовательности написания двух гласных.
Более того, если я преобразую тем же алгоритмом собственное имя, но написанное уже со строчной буквы, то результат все равно не будет иметь ничего общего с двумя предыдущими: 760e7dab2836853c63805033e514668301fa9c47.
Впрочем, кое-что общее у них все же есть: каждая строка имеет длину ровно 40 символов. Казалось бы, ничего удивительного, ведь все введенные мною слова также имели одинаковую длину — 5 букв.
Однако если вы захешируете весь предыдущий абзац целиком, то все равно получите последовательность, состоящую ровно из 40 символов: c5e7346089419bb4ab47aaa61ef3755d122826e2. То есть 1128 символов, включая пробелы, были ужаты до строки той же длины, что и пятибуквенное слово.
То же самое произойдет даже с полным собранием сочинений Уильяма Шекспира: на выходе вы получите строку из 40 букв и цифр. При всем этом не может существовать двух разных массивов данных, которые преобразовывались бы в одинаковый хеш.
Вот как это выглядит, если изобразить все вышесказанное в виде схемы:
Для чего используется хеш?
Отличный вопрос. Однако ответ не так прост, поскольку криптохеши используются для огромного количества вещей.
Для нас с вами, простых пользователей, наиболее распространенная область применения хеширования — хранение паролей. К примеру, если вы забыли пароль к какому-либо онлайн-сервису, скорее всего, придется воспользоваться функцией восстановления пароля.
В этом случае вы, впрочем, не получите свой старый пароль, поскольку онлайн-сервис на самом деле не хранит пользовательские пароли в виде обычного текста. Вместо этого он хранит их в виде хеш-значений. То есть даже сам сервис не может знать, как в действительности выглядит ваш пароль.
Исключение составляют только те случаи, когда пароль очень прост и его хеш-значение широко известно в кругах взломщиков.
Таким образом, если вы, воспользовавшись функцией восстановления, вдруг получили старый пароль в открытом виде, то можете быть уверены: используемый вами сервис не хеширует пользовательские пароли, что очень плохо.
Вы даже можете провести простой эксперимент: попробуйте при помощи специального сайта произвести преобразование какого-нибудь простого пароля вроде «123456» или «password» из их хеш-значений (созданных алгоритмом MD5) обратно в текст.
Вероятность того, что в базе хешей найдутся данные о введенных вами простых паролях, очень высока. В моем случае хеши слов «brain» (8b373710bcf876edd91f281e50ed58ab) и «Brian» (4d236810821e8e83a025f2a83ea31820) успешно распознались, а вот хеш предыдущего абзаца — нет.
Отличный пример, как раз для тех, кто все еще использует простые пароли.
Еще один пример, покруче. Не так давно по тематическим сайтам прокатилась новость о том, что популярный облачный сервис Dropbox заблокировал одного из своих пользователей за распространение контента, защищенного авторскими правами.
Герой истории тут же написал об этом в твиттере, запустив волну негодования среди пользователей сервиса, ринувшихся обвинять Dropbox в том, что он якобы позволяет себе просматривать содержимое клиентских аккаунтов, хотя не имеет права этого делать.
Впрочем, необходимости в этом все равно не было.
Дело в том, что владелец защищенного копирайтом контента имел на руках хеш-коды определенных аудио- и видеофайлов, запрещенных к распространению, и занес их в черный список хешей.
Когда пользователь предпринял попытку незаконно распространить некий контент, автоматические сканеры Dropbox засекли файлы, чьи хеши оказались в пресловутом списке, и заблокировали возможность их распространения.
Где еще можно использовать хеш-функции помимо систем хранения паролей и защиты медиафайлов? На самом деле задач, где используется хеширование, гораздо больше, чем я знаю и тем более могу описать в одной статье.
Однако есть одна особенная область применения хешей, особо близкая нам как сотрудникам «Лаборатории Касперского»: хеширование широко используется для детектирования зловредных программ защитным ПО, в том числе и тем, что выпускается нашей компанией.
Как при помощи хеша ловить вирусы?
Примерно так же, как звукозаписывающие лейблы и кинопрокатные компании защищают свой контент, сообщество создает черные списки зловредов (многие из них доступны публично), а точнее, списки их хешей. Причем это может быть хеш не всего зловреда целиком, а лишь какого-либо его специфического и хорошо узнаваемого компонента.
С одной стороны, это позволяет пользователю, обнаружившему подозрительный файл, тут же внести его хеш-код в одну из подобных открытых баз данных и проверить, не является ли файл вредоносным.
С другой — то же самое может сделать и антивирусная программа, чей «движок» использует данный метод детектирования наряду с другими, более сложными.
Криптографические хеш-функции также могут использоваться для защиты от фальсификации передаваемой информации. Иными словами, вы можете удостовериться в том, что файл по пути куда-либо не претерпел никаких изменений, сравнив его хеши, снятые непосредственно до отправки и сразу после получения.
Если данные были изменены даже всего на 1 байт, хеш-коды будут отличаться, как мы уже убедились в самом начале статьи. Недостаток такого подхода лишь в том, что криптографическое хеширование требует больше вычислительных мощностей или времени на вычисление, чем алгоритмы с отсутствием криптостойкости.
Зато они в разы надежнее.
Кстати, в повседневной жизни мы, сами того не подозревая, иногда пользуемся простейшими хешами. Например, представьте, что вы совершаете переезд и упаковали все вещи по коробкам и ящикам.
Погрузив их в грузовик, вы фиксируете количество багажных мест (то есть, по сути, количество коробок) и запоминаете это значение.
По окончании выгрузки на новом месте, вместо того чтобы проверять наличие каждой коробки по списку, достаточно будет просто пересчитать их и сравнить получившееся значение с тем, что вы запомнили раньше. Если значения совпали, значит, ни одна коробка не потерялась.
Источник: https://www.kaspersky.ru/blog/the-wonders-of-hashing/3633/
Хэширование: Просто и наглядно
Хэширование, или хэш-функция — одна из основных составляющих современной криптографии и алгоритма блокчейна.
Но, что это такое? Как наглядно представить это понятие?
Начнем с того, что хэширование — особое преобразование любого объема информации, в результате которого получается некое отображение, образ, называемый хэшем (hash) — уникальная короткая символьная строка, которая присуща только этому массиву входящей информации.
Из этого следует, что для любого объема информации, будь-то одна буква или роман Льва Толстого «Война и мир» (или даже всеё Полное собрание сочинений этого атвора) существует уникальный и неповторимый хэш — короткая символьная строка. Причем, если в той же «Войне и мире» изменить хотя бы один символ, добавить один лишь знак, — хэш изменится кардинально.
Как такое может быть? Целый многотомный роман и коротокая строчка, которая отражает его!
В этом смысле хэш подобен отпечатку пальца человека.
Как известно, отпечаток пальца уникален и в природе не существует людей с одинаковыми отпечатками. Даже у близнецов отпечатки пальцев разные.
То же касается и структуры ДНК человека. Она уникальна! Нет людей с одинаковым набором ДНК.
Но, ведь, ДНК, а тем более отпечаток пальцев — относительно короткий набор информации. И, тем не менее, они являются неким кодом, присущим конкретному человеку. Можно считать, что это и есть «хэши» этого человека. С тем лишь отличием, что они («хэши») не меняются с возрастом.
Итак, первое свойство хэша — его уникальность:
- Каждому набору (массиву) информации присущ строго определенный, уникальный хэш.
Тем не менее, иногда встречаются т.н. коллизии — случаи, когда хеш-функция для разных входных блоков информации вычисляет одинаковые хэш-коды.
Математики-криптографы стараются создать такие хэш-функции, вероятность коллизий в которых стремилась бы к нолю.
Следует отметить, что функций, которые вычисляют хэш, существует множество. Но, наиболее распространена (в частности, используется в протоколе блокчейна биткоина) хэш-функция под названием SHA-256 (от Secure Hash Algorithm — безопасный алгоритм хеширования). Эта хэш-функция формирует хэш в виде строки из 64 символов (длина — 256 бит или 32 байта).
Попробуем при помощи SHA-256 hash калькулятора получить хэш для заголовка этой статьи («Хэширование: Просто и наглядно»).
Это будет: ef3c82303f3896044125616982c715e7757d4cd1f84c34c6b2e64167d2fde766
А теперь изменим заголовок всего лишь на один символ — добавим знак восклицания в конце («Хэширование: Просто и наглядно!»).
Получилось: a6123e137d1d7f0aad800cdbc0918a65bb7a778a607cb993043d99718ec5a9e1
Как видите, изменение всего лишь на один знак исходного массива информации привело к кардинальному изменению его хэша!
И это второе важное свойство хэша:
- При самом незначительном изменении входной информации её хэш меняется кардинально.
Это свойство важно при использовании хэширования в цифровой подписи, т.к. позволяет удостовериться, что подписанная информация не была изменена во время её передачи по каналам связи. Но, подробнее об этом в следующей моей статье.
Третье важное свойство хэша, вытекает из того, что хэш-функция необратима. Другими словами:
- Не существует обратной функции, которая из хэша может восстановить исходный массив информации.
Из этого следует, что восстановить по хэшу соответствующий ему массив информации возможно только перебором всех возможных вариантов. Что практически невозможно, поскольку количество информации бесконечно!
Это свойство важно, поскольку делает взлом хэша (восстановление исходной информации по её хэшу) или невозможным или весьма дорогостоящим занятием.
Еще одно важное свойство хэш-функций — это высокая скорость работы.
- Хэширование позволяет достаточно быстро вычислить искомый хэш для весьма большого массива входной информации.
Этим хэширование существенно отличается от кодирования (шифрования) и декодирования (дешифрования).
Хэширование или хэш-функция используется во многих алгоритмах и протоколах. В частности, в электронной подписи и блокчейне.
Просто и наглядно, как это делается, я расскажу в следующих статьях.
А пока прочитайте мою предыдущую статью из цикла «Просто и наглядно» о Шифровании с открытым ключом.
Источник: https://golos.io/ru–kriptografiya/%40uanix/kheshirovanie-prosto-i-naglyadno
Что такое Хэширование? Под капотом блокчейна
Очень многие из вас, наверное, уже слышали о технологии блокчейн, однако важно знать о принципе работы хэширования в этой системе. Технология Блокчейн является одним из самых инновационных открытий прошлого века.
Мы можем так заявить без преувеличения, так как наблюдаем за влиянием, которое оно оказало на протяжении последних нескольких лет, и влиянием, которое оно будет иметь в будущем. Для того чтобы понять устройство и предназначение самой технологии блокчейн, сначала мы должны понять один из основных принципов создания блокчейна.
Простыми словами, хэширование означает ввод информации любой длины и размера в исходной строке и выдачу результата фиксированной длины заданной алгоритмом функции хэширования.
В контексте криптовалют, таких как Биткоин, транзакции после хэширования на выходе выглядят как набор символов определённой алгоритмом длины (Биткоин использует SHA-256).
Input- вводимые данные, hash- хэш Посмотрим, как работает процесс хэширования. Мы собираемся внести определенные данные.
Для этого, мы будем использовать SHA-256 (безопасный алгоритм хэширования из семейства SHA-2, размером 256 бит). Как видите, в случае SHA-256, независимо от того, насколько объёмные ваши вводимые данные (input), вывод всегда будет иметь фиксированную 256-битную длину.
Это крайне необходимо, когда вы имеете дело с огромным количеством данных и транзакций. Таким образом, вместо того, чтобы помнить вводимые данные, которые могут быть огромными, вы можете просто запомнить хэш и отслеживать его. Прежде чем продолжать, необходимо познакомиться с различными свойствами функций хэширования и тем, как они реализуются в блокчейн.
Криптографические хэш-функции
Криптографическая хэш-функция — это специальный класс хэш-функций, который имеет различные свойства, необходимые для криптографии. Существуют определенные свойства, которые должна иметь криптографическая хэш-функция, чтобы считаться безопасной. Давайте разберемся с ними по очереди.
Свойство 1: Детерминированние
Это означает, что независимо от того, сколько раз вы анализируете определенный вход через хэш-функцию, вы всегда получите тот же результат. Это важно, потому что если вы будете получать разные хэши каждый раз, будет невозможно отслеживать ввод.
Свойство 2: Быстрое вычисление
Хэш-функция должна быть способна быстро возвращать хэш-вход. Если процесс не достаточно быстрый, система просто не будет эффективна.
Свойство 3: Сложность обратного вычисления
Сложность обратного вычисления означает, что с учетом H (A) невозможно определить A, где A – вводимые данные и H(А) – хэш. Обратите внимание на использование слова “невозможно” вместо слова “неосуществимо”. Мы уже знаем, что определить исходные данные по их хэш-значению можно. Возьмем пример.
Предположим, вы играете в кости, а итоговое число — это хэш числа, которое появляется из кости. Как вы сможете определить, что такое исходный номер? Просто все, что вам нужно сделать, — это найти хэши всех чисел от 1 до 6 и сравнить.
Поскольку хэш-функции детерминированы, хэш конкретного номера всегда будет одним и тем же, поэтому вы можете просто сравнить хэши и узнать исходный номер. Но это работает только тогда, когда данный объем данных очень мал.
Что происходит, когда у вас есть огромный объем данных? Предположим, вы имеете дело с 128-битным хэшем. Единственный метод, с помощью которого вы должны найти исходные данные, — это метод «грубой силы».
Метод «грубой силы» означает, что вам нужно выбрать случайный ввод, хэшировать его, а затем сравнить результат с исследуемым хэшем и повторить, пока не найдете совпадение.
Итак, что произойдет, если вы используете этот метод?
- Лучший сценарий: вы получаете свой ответ при первой же попытке. Вы действительно должны быть самым счастливым человеком в мире, чтобы это произошло. Вероятность такого события ничтожна.
- Худший сценарий: вы получаете ответ после 2 ^ 128 — 1 раз. Это означает, что вы найдете свой ответ в конце всех вычислений данных (один шанс из 340282366920938463463374607431768211456)
- Средний сценарий: вы найдете его где-то посередине, поэтому в основном после 2 ^ 128/2 = 2 ^ 127 попыток. Иными словами, это огромное количество.
Таким образом, можно пробить функцию обратного вычисления с помощью метода «грубой силы», но потребуется очень много времени и вычислительных ресурсов, поэтому это бесполезно.
Свойство 4: Небольшие изменения в вводимых данных изменяют хэш
Даже если вы внесете небольшие изменения в исходные данные, изменения, которые будут отражены в хэше, будут огромными.
Давайте проверим с помощью SHA-256:Видите? Даже если вы только что изменили регистр первой буквы, обратите внимание, насколько это повлияло на выходной хэш.
Это необходимая функция, так как свойство хэширования приводит к одному из основных качеств блокчейна – его неизменности (подробнее об этом позже).
Свойство 5: Коллизионная устойчивость
Учитывая два разных типа исходных данных A и B, где H (A) и H (B) являются их соответствующими хэшами, для H (A) не может быть равен H (B).
Это означает, что, по большей части, каждый вход будет иметь свой собственный уникальный хэш.
Почему мы сказали «по большей части»? Давайте поговорим об интересной концепции под названием «Парадокс дня рождения».
Что такое парадокс дня рождения?
Если вы случайно встречаете незнакомца на улице, шанс, что у вас совпадут даты дней рождений, очень мал. Фактически, если предположить, что все дни года имеют такую же вероятность дня рождения, шансы другого человека, разделяющего ваш день рождения, составляют 1/365 или 0,27%.
Другими словами, он действительно низкий. Однако, к примеру, если собрать 20-30 человек в одной комнате, шансы двух людей, разделяющих тот же день, резко вырастает. На самом деле, шанс для 2 человек 50-50, разделяющих тот же день рождения при таком раскладе.
Как это применяется в хэшировании?
Предположим, у вас есть 128-битный хэш, который имеет 2 ^ 128 различных вероятностей. Используя парадокс дня рождения, у вас есть 50% шанс разбить коллизионную устойчивость sqrt (2 ^ 128) = 2 ^ 64.
Как вы заметили, намного легче разрушить коллизионную устойчивость, нежели найти обратное вычисление хэша. Для этого обычно требуется много времени.
Итак, если вы используете такую функцию, как SHA-256, можно с уверенностью предположить, что если H (A) = H (B), то A = B.
Свойство 6: Головоломка
Свойства Головоломки имеет сильнейшее воздействие на темы касающиеся криптовалют (об этом позже, когда мы углубимся в крипто схемы). Сначала давайте определим свойство, после чего мы подробно рассмотрим каждый термин.
Для каждого выхода «Y», если k выбран из распределения с высокой мин-энтропией, невозможно найти вводные данные x такие, что H (k | x) = Y. Вероятно, это, выше вашего понимания! Но все в порядке, давайте теперь разберемся с этим определением.
В чем смысл «высокой мин-энтропии»?
Это означает, что распределение, из которого выбрано значение, рассредоточено так, что мы выбираем случайное значение, имеющее незначительную вероятность. В принципе, если вам сказали выбрать число от 1 до 5, это низкое распределение мин-энтропии. Однако, если бы вы выбрали число от 1 до бесконечности, это — высокое распределение мин-энтропии.
Что значит «к|х»?
«|» обозначает конкатенацию. Конкатенация означает объединение двух строк. Например. Если бы я объединила «голубое» и «небо», то результатом было бы «голубоенебо». Итак, давайте вернемся к определению. Предположим, у вас есть выходное значение «Y». Если вы выбираете случайное значение «К», невозможно найти значение X, такое, что хэш конкатенации из K и X, выдаст в результате Y. Еще раз обратите внимание на слово «невозможно», но не исключено, потому что люди занимаются этим постоянно. На самом деле весь процесс майнинга работает на этом (подробнее позже).
Примеры криптографических хэш-функций:
- MD 5: Он производит 128-битный хэш. Коллизионная устойчивость была взломана после ~2^21 хэша.
- SHA 1: создает 160-битный хэш. Коллизионная устойчивость была взломана после ~2^61 хэша.
- SHA 256: создает 256-битный хэш. В настоящее время используется в Биткоине.
- Keccak-256: Создает 256-битный хэш и в настоящее время используется Эфириуме.
Хэширование и структуры данных. Структура данных — это специализированный способ хранения данных. Если вы хотите понять, как работает система «блокчейн», то есть два основных свойства структуры данных, которые могут помочь вам в этом: 1. Указатели 2. Связанные списки
Указатели
В программировании указатели — это переменные, в которых хранится адрес другой переменной, независимо от используемого языка программирования. Например, запись int a = 10 означает, что существует некая переменная «a», хранящая в себе целочисленное значение равное 10.
Так выглядит стандартная переменная. Однако, вместо сохранения значений, указатели хранят в себе адреса других переменных. Именно поэтому они и получили свое название, потому как буквально указывают на расположение других переменных.
Связанные списки
Связанный список является одним из наиболее важных элементов в структурах данных. Структура связанного списка выглядит следующим образом:
*Head – заголовок; Data – данные; Pointer – указатель; Record – запись; Null – ноль Это последовательность блоков, каждый из которых содержит данные, связанные со следующим с помощью указателя.
Переменная указателя в данном случае содержит адрес следующего узла, благодаря чему выполняется соединение. Как показано на схеме, последний узел отмечен нулевым указателем, что означает, что он не имеет значения. Важно отметить, что указатель внутри каждого блока содержит адрес предыдущего. Так формируется цепочка.
Возникает вопрос, что это значит для первого блока в списке и где находится его указатель? Первый блок называется «блоком генезиса», а его указатель находится в самой системе.
Выглядит это следующим образом:
*H ( ) – Хэшированные указатели изображаются таким образом Если вам интересно, что означает «хэш-указатель», то мы с радостью поясним. Как вы уже поняли, именно на этом основана структура блокчейна. Цепочка блоков представляет собой связанный список.
Рассмотрим, как устроена структура блокчейна:
* Hash of previous block header – хэш предыдущего заголовка блока; Merkle Root – Корень Меркла; Transactions – транзакции; Simplified Bitcoin Blockchain – Упрощенный блокчейн Биткоина.
Блокчейн представляет собой связанный список, содержащий данные, а так же указатель хэширования, указывающий на предыдущий блок, создавая таким образов связную цепочку.
Что такое хэш-указатель? Он похож на обычный указатель, но вместо того, чтобы просто содержать адрес предыдущего блока, он также содержит хэш данных, находящихся внутри предыдущего блока. Именно эта небольшая настройка делает блокчейн настолько надежным. Представим на секунду, что хакер атакует блок 3 и пытается изменить данные.
Из-за свойств хэш-функций даже небольшое изменение в данных сильно изменит хэш. Это означает, что любые незначительные изменения, произведенные в блоке 3, изменят хэш, хранящийся в блоке 2, что, в свою очередь, изменит данные и хэш блока 2, а это приведет к изменениям в блоке 1 и так далее. Цепочка будет полностью изменена, а это невозможно. Но как же выглядит заголовок блока?
* Prev_Hash – предыдущий хэш; Tx – транзакция; Tx_Root – корень транзакции; Timestamp – временная отметка; Nonce – уникальный символ.
Заголовок блока состоит из следующих компонентов:
· Версия: номер версии блока · Время: текущая временная метка · Текущая сложная цель (См. ниже) · Хэш предыдущего блока · Уникальный символ (См. ниже) · Хэш корня Меркла Прямо сейчас, давайте сосредоточимся на том, что из себя представляет хэш корня Меркла. Но до этого нам необходимо разобраться с понятием Дерева Меркла.
Что такое Дерево Меркла?
Источник: Wikipedia На приведенной выше диаграмме показано, как выглядит дерево Меркла. В дереве Меркла каждый нелистовой узел является хэшем значений их дочерних узлов.
Листовой узел: Листовые узлы являются узлами в самом нижнем ярусе дерева. Поэтому, следуя приведенной выше схеме, листовыми будут считаться узлы L1, L2, L3 и L4.
Дочерние узлы: Для узла все узлы, находящиеся ниже его уровня и которые входят в него, являются его дочерними узлами. На диаграмме узлы с надписью «Hash 0-0» и «Hash 0-1» являются дочерними узлами узла с надписью «Hash 0».
Корневой узел: единственный узел, находящийся на самом высоком уровне, с надписью «Top Hash» является корневым.
Так какое же отношение Дерево Меркла имеет к блокчейну?
Каждый блок содержит большое количество транзакций. Будет очень неэффективно хранить все данные внутри каждого блока в виде серии. Это сделает поиск какой-либо конкретной операции крайне громоздким и займет много времени. Но время, необходимое для выяснения, на принадлежность конкретной транзакции к этому блоку или нет, значительно сокращается, если Вы используете дерево Меркла.
Давайте посмотрим на пример на следующем Хэш-дереве:
Изображение предоставлено проектом: Coursera Теперь предположим, я хочу узнать, принадлежат ли эти данные блоку или нет:Вместо того, чтобы проходить через сложный процесс просматривания каждого отдельного процесса хэша, а также видеть принадлежит ли он данным или нет, я просто могу отследить след хэша, ведущий к данным:
Это значительно сокращает время. Хэширование в майнинге: крипто-головоломки. Когда мы говорим «майнинг», в основном, это означает поиск нового блока, который будет добавлен в блокчейн. Майнеры всего мира постоянно работают над тем, чтобы убедиться, что цепочка продолжает расти. Раньше людям было проще работать, используя для майнинга лишь свои ноутбуки, но со временем они начали формировать «пулы», объединяя при этом мощность компьютеров и майнеров, что может стать проблемой. Существуют ограничения для каждой криптовалюты, например, для биткоина они составляют 21 миллион. Между созданием каждого блока должен быть определенный временной интервал заданный протоколом. Для биткоина время между созданием блока занимает всего 10 минут. Если бы блокам было разрешено создаваться быстрее, это привело бы к:
- Большому количеству коллизий: будет создано больше хэш-функций, которые неизбежно вызовут больше коллизий.
- Большому количеству брошенных блоков: Если много майнеров пойдут впереди протокола, они будут одновременно хаотично создавать новые блоки без сохранения целостности основной цепочки, что приведет к «осиротевшим» блокам.
Таким образом, чтобы ограничить создание блоков, устанавливается определенный уровень сложности. Майнинг чем-то напоминает игру: решаешь задачу – получаешь награду. Усиление сложности делает решение задачи намного сложнее и, следовательно, на нее затрачивается большее количество времени.WRT, которая начинается с множества нулей. При увеличении уровня сложности, увеличивается количество нулей. Уровень сложности изменяется после каждого 2016-го блока.
Процесс Майнинга
Примечание: в этом разделе мы будем говорить о выработке биткоинов. Когда протокол Биткоина хочет добавить новый блок в цепочку, майнинг – это процедура, которой он следует. Всякий раз, когда появляется новый блок, все их содержимое сначала хэшируется.
Если подобранный хэш больше или равен, установленному протоколом уровню сложности, он добавляется в блокчейн, а все в сообществе признают новый блок. Однако, это не так просто. Вам должно очень повезти, чтобы получить новый блок таким образом. Так как, именно здесь присваивается уникальный символ.
Уникальный символ (nonce) — это одноразовый код, который объединен с хэшем блока. Затем эта строка вновь меняется и сравнивается с уровнем сложности. Если она соответствует уровню сложности, то случайный код изменяется. Это повторяется миллион раз до тех пор, пока требования не будут наконец выполнены.
Когда же это происходит, то блок добавляется в цепочку блоков.
Подводя итоги:
• Выполняется хэш содержимого нового блока. • К хэшу добавляется nonce (специальный символ). • Новая строка снова хэшируется. • Конечный хэш сравнивается с уровнем сложности, чтобы проверить меньше он его или нет • Если нет, то nonce изменяется, и процесс повторяется снова. • Если да, то блок добавляется в цепочку, а общедоступная книга (блокчейн) обновляется и сообщает нодам о присоединении нового блока. • Майнеры, ответственные за данный процесс, награждаются биткоинами.
Помните номер свойства 6 хэш-функций? Удобство использования задачи?
Для каждого выхода «Y», если k выбран из распределения с высокой мин-энтропией, невозможно найти вход x таким образом, H (k | x) = Y.
Так что, когда дело доходит до майнинга биткоинов: • К = Уникальный символ • x = хэш блока • Y = цель проблемы Весь процесс абсолютно случайный, основанный на генерации случайных чисел, следующий протоколу Proof Of Work и означающий:
- Решение задач должно быть сложным.
- Однако проверка ответа должна быть простой для всех. Это делается для того, чтобы убедиться, что для решения проблемы не использовались недозволенные методы.
Что такое скорость хэширования? Скорость хэширования в основном означает, насколько быстро эти операции хэширования происходят во время майнинга.
Высокий уровень хэширования означает, что в процессе майнинга участвуют всё большее количество людей и майнеров, и в результате система функционирует нормально. Если скорость хэширования слишком высокая, уровень сложности пропорционально увеличивается. Если скорость хэша слишком медленная, то соответственно, уровень сложности уменьшается.
Вывод
Источник: https://habr.com/post/345740/
Как надо хешировать пароли и как не надо
В очередной раз заканчивая проводить аудит информационной безопасности веб-проекта, моя личная бочка с гневом переполнилась негодованием так, что оно перелилось через край в этот пост.
Постараюсь очень лаконично и быстро обрисовать ситуацию с хэшами.
Сразу определю какую задачу применения хешей буду рассматривать — аутентификация пользователей. Не токены восстановления паролей, не аутентификация запросов, не что-то еще. Это также не статья про защиту канала передачи данных, так что комментарии по challenge-response и SSL неуместны!
Матчасть (короткая)
Hash = хеш функция — (свертка) функция однозначного отображения строки (любой длины) на конечное множество (строку заданной длины). Само число (строка) хеш — результат вычисления хеш-функции над данными.
Существуют криптографические и некриптографические (классифицируются отдельно, к ним относятся, например, контрольные суммы) хеш-функции.
Для криптографических хэшей есть три дополнительных условия, которые отличают их от всех остальных:
- Необратимость: для заданного значения хеш-функции m должно быть вычислительно неосуществимо найти блок данных X, для которого H(X)=m.
- Стойкость к коллизиям первого рода: для заданного сообщения M должно быть вычислительно неосуществимо подобрать другое сообщение N, для которого H(N)=H(M).
- Стойкость к коллизиям второго рода: должно быть вычислительно неосуществимо подобрать пару сообщений ~(M, M'), имеющих одинаковый хеш
Подробнее — ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5
Вникать в тонкости криптографии прикладному разработчику не обязательно, достаточно запомнить какие хэш-функции (алгоритмы по названию) можно сейчас использовать, а какие уже нет. MD5 — уже нельзя, коллеги, — используйте bcrypt/scrypt.
В веб-приложениях, в числе прочего, хеш-функции используются для безопасного хранения секретов (паролей) в базе данных.
Именно хэш-функция становится вашим последним оплотом, если злоумышленник смог свести нападение к локальной атаке на систему аутентификации. Про онлайн атаки (перебор паролей НТТР запросами), может быть, кто-то еще напишет позже.
Ниже перечислены требования, которым ваш хеш в базе должен удовлетворять:
- стойкость к атакам перебора (прямой перебор и перебор по словарю)
- невозможность поиска одинаковых паролей разных пользователей по хешам
Для выполнения первого требования нужно использовать стойкие в настоящее время (а не в 90х годах!) хеш-функции.
Для выполнения второго — к паролю перед хешированием добавляется случайная строка (соль). Таким образом, у двух пользователей с паролем «123456» будут разные соли «соль1» и «соль2», а соответственно и хеш-функции от «123456соль1» и «123456соль2» в базе тоже будут разные.
Теперь немного про систему хранения — и соль и сам хеш хранятся в базе данных.
То есть получив доступ к СУБД, злоумышленник получает и значения хешей и соли.
Используйте локальный параметр!
Чтобы усложнить жизнь при атаке перебора следует дописать соль к паролю, а не наоборот (для людей, которые пишут слева направо, конечно). Так как хеш-функция, как правило, вычисляется последовательно по строке (требования поточности алгоритма), то злоумышленнику при переборе «соленых» хешей, будет проще, когда подхешовое выражение начинается с соли.
Проще потому, что он (злоумышленник) может предвычислить заранее хеш(соль) и далее считать хеш(соль)+хеш(пароль) уже куда быстрее (практически с той же скоростью, что и просто хеш(пароль)). Для всех паролей, что он будет перебирать.
Для того чтобы еще усложнить жизнь атакующему, Solar Designer www.openwall.com/presentations/YaC2012-Password-Hashing-At-Scale/mgp00005.html предлагает ввести еще одну штуку, под названием локальный параметр.
Это по сути «вторая соль» дописывается ко всем (паролям+соль) конструкциям, и является одинаковой для всех хешей в базе. В чем же трюк? В том, что локального параметра в базе нет. Это константа системы, которая храниться в памяти приложения, куда она попадает из конфига (любым способом, только не из базы).
Очень простая и действенная мера, которая позволяет практически полностью исключить атаку перебора по данным только одного хранилища хешей (без знания локального параметра).
Единственный раз мы (ONsec) ломали хеши с локальным параметром, выработав при этом тактику атаки на сам локальный параметр (регистрируемся в приложении, затем ищем в базе свой хеш, соль (свой пароль мы и так знаем) и перебираем ЛП). И тщетно. На длинах 16+ байт для современных функций хеширования — это очень дорого по железу. В итоге проще оказалось скомпрометировать систему аутентификации (проставить себе role=admin в базе через UPDATE 😉 )
Очень рекомендую ознакомиться с презентацией: www.openwall.com/presentations/YaC2012-Password-Hashing-At-Scale/mgp00001.html
Защищайте свои хранилища надежно и грамотно!
Заключение
Буду реалистом — естественно, никто не станет переписывать свои проекты ради «каких-то» хешей. Но новые проекты можно писать на scrypt/bcrypt. А также — внедряйте локальный параметр даже на слабых MD5 — он правда помогает, проверено 🙂
При переходе на другой тип хеширования, помимо трудозатрат, часто встает вопрос производительности. Действительно, более стойкие алгоритмы потребляют больше ресурсов.
Тестируйтесь перед внедрением для своих нагрузок по скорости аутентификации пользователей в секунду (для большинства крупных проектов переход на scrypt оказался безболезненным). Выбор конкретного идеального типа хеша в конкретной ситуации может сильно разнится.
Так, например, ДБО все чаще выбирают железные решения для генерации хешей с заданной скоростью.
В заключении, привожу скорости перебора хешей (единицы измерения — мегахэши в секунду, то есть количество ), полученных на карточке AMD Radeon 7990 стоимостью менее $1000 (даже по старому курсу):
- MD5: 16000 M/s
- SHA-1: 5900 M/s
- SHA256: 2050 M/s
- SHA512: 220 M/s
- NTLM: 28400 M/s
- bcrypt: 8,5 k/s
А по поводу эффективности перебора bcrypt рекомендую также ознакомиться с www.openwall.com/presentations/Passwords13-Energy-Efficient-Cracking/Passwords13-Energy-Efficient-Cracking.pdf
Источник: http://www.pvsm.ru/informatsionnaya-bezopasnost/53864
Хэш-функция
smLogic.
ru > Шифрование и цифровые подписи > Хэш-функция
Хеширование широко применяется в информационных технологиях – для построения достаточно уникальных идентификаторов наборов данных, контрольного суммирования с целью обнаружения случайных или намеренных ошибок при хранении или передаче, для хранения паролей в системах защиты (в этом случае доступ к области памяти, где находятся пароли, не позволяет восстановить сам пароль) и т.п.
Хэш-функция предназначена для сжатия входного массива данных произвольной длины в битовую строку заранее заданного размера (нескольких десятков или сотен бит).
Хэш-функция h принимает в качестве аргумента входной массив данных (документ) X произвольной длины и возвращает хэш-значение h(X)=Н фиксированной длины.
Обычно хэшированная информация является сжатым двоичным представлением основного сообщения произвольной длины называемым дайджестом сообщения (message digest).
Следует отметить, что значение хэш-функции h(X) сложным образом зависит от документа X и не позволяет восстановить сам документ из хэш-значения Н (однонаправленная хэш-функция).
Вообще под однонаправленностью понимают не невозможность, а высокую сложность восстановления сообщения по его хэшу, так как на данный момент нет используемых хэш-функций с доказанной однонаправленностью.
Теоретически существует массив данных Y, для которого h(X) = h(Y). Эти пары X,Y называют коллизиями. Основное требование, предъявляемое криптографическими приложениями к хэш-функциям, состоит в отсутствии эффективных алгоритмов поиска коллизий.
Схемы электронной подписи – одна из сфер применения хэш-функций.
При формировании электронной подписи на практике часто подписывается не само сообщение, а его хеш-образ.
В процессе цифрового подписания система ЭЦП обрабатывает исходное сообщение (прообраз) криптографически стойким односторонним хэш-алгоритмом. Эта операция приводит к генерации дайджеста сообщения.
Затем система зашифровывает полученный дайджест закрытым ключом отправителя, создавая «электронную подпись», и прикрепляет её к прообразу.
По получении сообщения, адресат при помощи системы ЭЦП заново вычисляет дайджест подписанных данных, расшифровывает ЭЦП открытым ключом отправителя, тем самым сверяя, соответственно, целостность данных и их источник; если вычисленный адресатом и полученный с сообщением дайджесты совпадают, значит информация после подписания не была изменена.
В системах ЭЦП могут использоваться различные хэш-функции, но они должны удовлетворять ряду условий:
- хэш-функция должна быть чувствительна к всевозможным изменениям в тексте, таким как вставки, выбросы, перестановки и т.п.;
- хэш-функция должна обладать свойством необратимости, то есть задача подбора документа, который обладал бы требуемым значением хэш-функции, должна быть вычислительно неразрешима;
- вероятность коллизий, то-есть того, что значения хэш-функций двух различных документов (вне зависимости от их длин) совпадут, должна быть ничтожно мала.
Источник: https://www.smlogic.ru/shifrovanie-i-tsifrovye-podpisi/hesh-funktsiya/
Чтобы понять блокчейн, нужно понять, что такое хеш
Для меня ключ к познанию блокчейна – это понимание криптографических хешей. Мне кажется, многие из нас, обычных людей, делают ошибку, представляя себе блокчейн как, в первую очередь, списки анонимных транзакций, распределённых по децентрализованным сетям.
Хотя отдельный блокчейн действительно таков, иногда упускается из виду, что основой блокчейновой технологии является не децентрализация, анонимность или даже распредёленные реестры, а собственно криптография.
Хотя это, наверное, очевидно для человека с базовым пониманием компьютерных наук, для большинства из нас это нечто совершенно новое.
Очень краткая история цифровых денег
Биткойн – новый подход к предыдущим экспериментам с цифровыми деньгами. В 1990-х это была горячая, но спекулятивная тема. Даже Алан Гринспен в своей речи в 1996 г. сказал:
Таким образом, использование цифровой валюты истеблишментом было на повестке дня задолго до Биткойна. Для того чтобы освободить цифровую валюту от истеблишмента, требовалось ещё одно новшество. Этим новшеством стала криптография.
Когда Гринспен произносил свою речь, шифропанки уже экспериментировали с цифровыми валютами с явным намерением дестабилизировать банки.
В числе их экспериментов, существовавших до Биткойна, были Hashcash Адама Бэка, BitGold Ника Сабо, B-Money Вэй Дая и RPOW Хэла Финни.
Все они использовали возможности криптографических хеш-функций, и вместе они образуют гигантские плечи, на которых сегодня стоит Биткойн.
Что такое криптографические хеш-функции?
Криптографическая хеш-функция берёт данные и, по сути, переводит их в строку букв и цифр. Вы когда-нибудь пользовались URL-сокращалками типа Bitly или TinyURL? Это нечто похожее.
Вы вводите что-то длинное, а на выходе получается что-то короткое, олицетворяющее то длинное. Только в случае криптографических хеш-функций ввод не обязательно должен быть длинным.
Это может быть что-то очень короткое (например, слово «пёс») или почти бесконечно длинное (например, весь текст «Повести о двух городах»), и на выходе вы получите уникальную строку установленной длины.
Кроме того, в отличие от сокращателей ссылок, хеш-функции, применяемые в Биткойне, действуют только в одном направлении. Хотя одни и те же данные всегда дадут один и тот же хеш, воспроизвести изначальные данные по полученному из них хешу невозможно.
Итак, данные вводятся в хеш-функцию, функция выполняется и получается строка букв и цифр (можете попробовать самостоятельно здесь). Эта строка называется хешем. В блокчейне Биткойна хеши состоят из 256 бит или 64 символов.
Может показаться невозможным, чтобы почти бесконечное количество данных могло последовательно переводиться в уникальную строку всего из 64 символов, но именно таким чудесным образом действуют криптографические функции.
С помощью этой невероятной технологии целые книги, заполненные текстом, могут быть переведены в одну строку из 64 цифр и букв.
И каждый раз, когда вы вводите одни и те же данные, вы получите не только один и тот же хеш, но уникальный и отличный от любого другого хеша.
Пример
Хеш фразы:
df0a199c7fef0a53d9a4144bc9122441b94510c13faf424ca26b65aa5035048f
Тогда как хеш слова «пёс»:
cd6357efdd966de8c0cb2f876cc89ec74ce35f0968e11743987084bd42fb8944
Как работают криптографические хеш-функции
Существуют разные виды криптографических хеш-функций, и каждая из них работает по-разному.
Использовавшаяся выше хеш-функция – SHA-256, хеш-функция, применяемая в Биткойне, – работает на основе безумно сложной формулы, связанной с отражением света от эллипсов. Вам не стоит слишком из-за этого переживать.
Суть в том, что криптографические хеш-функции – это чертова магия, и вы никогда их до конца не поймете, если только вы не математик.
Как хеш-функции применяются в блокчейне
Чтобы блокчейн работал, он должен обновляться. Подобно банку, он должен вести актуальные записи всех транзакций и активов (например, биткойнов), имеющихся у каждого участника сети. Именно при обновлении транзакционной информации любая аутентифицирующая система уязвима для атаки.
Банк сглаживает этот риск благодаря наличию строгой централизованной иерархии, гарантирующей подлинность на свой собственный риск.
Так как блокчейну удаётся обновляться, оставаясь децентрализованным? Он использует криптографическую вероятностную хеш-игру, называемую «доказательство выполнения работы» (Proof of Work).
Криптография обеспечивает консенсус
Чтобы продолжать функционировать, блокчейн должен создавать новые блоки. Так как блокчейны – это децентрализованные системы, новые блоки должны создаваться не единственным аутентифицирующим субъектом, а сетью в целом. Чтобы решить, каким будет новый блок, сеть должна достичь консенсуса.
Чтобы достичь консенсуса, майнеры предлагают определённые блоки, блоки верифицируются, и, наконец, сеть выбирает единственный блок, который будет следующей частью реестра. Однако очень много майнеров предлагают идентичные блоки, проходящие верификацию.
Так каким образом конкретный блок выбирается, чтобы стать следующим в цепи?
Компьютеры соревнуются в хеш-игре. Всё очень просто. По сути, чтобы выиграть игру, майнящий компьютер должен угадать число, называемое «нонс» (nonce), которое в комбинации со всеми предыдущими данными блокчейна даёт при вводе в хеш-функцию SHA-256 определённый хеш.
Помните хакеров из фильмов, использующих программу, угадывающую миллион паролей в минуту, чтобы взломать компьютер? Это что-то вроде этого.
Все майнеры мира одновременно используют похожую программу-угадайку, ищущую правильный нонс, который при добавлении к данным блокчейна и вводе в хеш-функцию SHA-256 даст рандомный хеш, который сам блокчейн «определил» как «решение» задачи.
Компьютеры, в каком-то смысле, работают совместно, так как каждый предложенный хеш не может быть предложен снова. Компьютер, первым отгадавший правильное число, выигрывает право на создание следующего блока и получает 12,5 биткойна, что сейчас равно примерно $50 000.
Так обеспечивается консенсус, а также предотвращаются атаки, нацеленные на манипулирование системой.
Так как результатом каждого ввода является совершенно уникальный хеш, только определенный нонс в комбинации с верными ранее верифицированными блокчейновыми данными даст хеш, решающий уравнение.
При вводе неточных или мошеннических предшествующих записей не может быть угадан верный хеш. Таким образом, криптография делает блокчейны более безопасными, чем любой банк с человеческой верификацией.
Тем не менее, поскольку постепенно всё больше людей выделяли всё больше компьютерной мощности на майнинг биткойнов, возникла новая проблема.
Новаторы разработали мощные компьютеры, предназначенные исключительно для майнинга биткойнов.
Эти компьютеры способны предлагать хеши намного чаще, чем средний компьютер, что позволяет им прийти к верной догадке намного быстрее и, как следствие, намайнить больше биткойнов.
Проблема заключается в том, что когда всё меньше людей могут позволить себе майнинговые технологии, риск централизации возрастает. Блоки создаются и биткойны майнятся, как только находится решение следующего блока.
Таким образом, имеющий ресурсы может просто собрать более мощную майнинговую машину, чем у всех других, и майнить огромный процент остающихся биткойнов быстрее всех других, просто предлагая больше догадок в более короткий срок.
10-минутное решение
Сатоши предусмотрел механизм, сглаживающий эту проблему, и он также полагается на возможности хеш-функций. Вот как я предпочитаю смотреть на его решение:
Представьте, что ваша хеш-функция на выходе вместо цифр и букв даёт животных. Существует равная вероятность, что при вводе рандомных данных хеш-функция выдаст слона или обезьяну. Ваши случайно выбираемые данные могут быть переведены либо в одно, либо в другое животное с одинаковой вероятностью.
Но теперь представьте, что вы задаёте определённые критерии того, в какое животное должна перевести ваши данные хеш-функция, чтобы работать. Это влияет на вероятность хеширования тех или иных данных в животное, удовлетворяющее вашим критериям.
Например, данные «abc123» с большей вероятностью выдадут любое животное (на самом деле в данном примере вероятность 100%), чем любое двуногое, потому что существует намного больше потенциальных догадок, подходящих под любое животное, чем под любое двуногое.
Ещё меньше вероятность получить любую обезьяну.
Блокчейн Биткойна работает так, что игра на отгадывание самокорректируется, чтобы всегда быть достаточно сложной, чтобы все компьютеры сети могли угадывать только каждые 10 минут, независимо от мощности отгадывающих компьютеров.
Это значит, что угадывание хеша и майнинг блока сегодня теоретически намного сложнее, чем при запуске Биткойна в 2009 г., потому что в сети очень много сверхмощных компьютеров.
И в самом деле, сегодня невозможно майнить биткойны с помощью обычного ноутбука, тогда как в ранние дни Биткойна все участники сети использовали стандартные компьютеры.
Так как же протокол Биткойна гарантирует, что игра на отгадывание будет становиться достаточно сложной, чтобы даже чрезвычайно мощным майнинговым компьютерам на отгадывание требовалось примерно 10 минут? Вспомните пример с обезьяной.
Чем более конкретные критерии заданы для выхода хеш-функции, тем больше догадок нужно сделать, чтобы получить этот более конкретный выход. Вместо того чтобы «правильным» ответом было животное (легко), двуногое (сложно) или обезьяна (сложнее), для «правильной» строки хеша, выигрывающей игру, задаются всё более конкретные критерии.
В частности, игра усложняется посредством требования наличия у правильного хеша в начале определённого количества нулей.
Представьте себе это следующим образом. Если я попрошу вас отгадать рандомное трёхзначное число, чтобы получить шоколадку, у вас больше шансов угадать, если правильное число – любое трёхзначное число, чем если это любое трёхзначное число, начинающееся с 0.
Это сложно понять, но в основе лежит математический закон, говорящий, что достаточно квадратного корня N рандомных событий, чтобы вероятность их совпадения составляла 50%.
Та же самая математика поддерживает парадокс дней рождения – если в комнате всего 23 человека, существует 50% вероятность, что у двух из них день рождения в один и тот же день.
К сожалению, делая угадывание числа всё сложнее и сложнее, блокчейн Биткойна неизбежно пришел к исключению из майнинга обычных людей. Но это справедливая цена децентрализации. Без этого одна богатая компания могла бы теоретически создать чрезвычайно мощный компьютер, способный мгновенно добыть все оставшиеся биткойны.
Должен заметить, что я лишь (с трудом) понимаю, как работает блокчейн Биткойна.
Другие блокчейны могут использовать криптографию совершенно иначе, чем я здесь описал. Например, я не знаю, использует ли ту же систему доказательство доли владения (proof of stake) – как утверждается, более эффективное усовершенствование доказательства выполнения работы.
Но так как блокчейн Биткойна является моделью для всех других блокчейнов, его понимание – это важнейший шаг к постижению мира криптовалют. Хотя существенно также понимание многих других аспектов блокчейна, осмысление того, как он использует криптографию, – наверное, важнейшая часть пазла.
Источник
Источник: https://bitnovosti.com/2017/10/16/chtoby-ponyat-blokchejn-nuzhno-ponyat-chto-takoe-hesh/
Загрузка...
