В предыдущих статьях я рассказал про этапы выполнения запросов, про статистику, про два основных вида доступа к данным — последовательное сканирование и индексное сканирование, — и перешел к способам соединения.
Прошлая статья была посвящена вложенному циклу, а сегодня поговорим про соединение хешированием. Заодно затронем группировку и поиск уникальных значений.
Всем привет. На связи Владислав Родин. В настоящее время я являюсь руководителем курса «Архитектор высоких нагрузок» в OTUS, а также преподаю на курсах посвященных архитектуре ПО.
Помимо преподавания, как вы могли заметить, я занимаюсь написанием авторского материала для блога OTUS на хабре и сегодняшнюю статью хочу посвятить запуску нового потока курса «Алгоритмы для разработчиков».
Хеш-таблицы (HashMap) наравне с динамическими массивами являются самыми популярными структурами данных, применяемыми в production'е, поэтому очень часто можно услышать вопросы на собеседованиях касаемо их предназначения, особенностей их внутреннего устройства, связанных с ними алгоритмов. Данная структура данных является классической и встречается не только в Java, но и во многих других языках программирования.
Читать полностью »
Данный текст будет являться одной из переписанных глав для учебного пособия по защите информации кафедры радиотехники и систем управления, а также, с этого учебного кода, кафедры защиты информации МФТИ (ГУ). Полностью учебник доступен на github (см. также draft releases). На Хабре планирую выкладывать новые «большие» куски, во-первых, чтобы собрать полезные комментарии и замечания, во-вторых, дать сообществу больше обзорного материала по полезным и интересным темам.
Надёжная криптографическая хеш-функция обеспечивает преобразование открытого текста в текст заданной длины. При этом обеспечивается «стойкость»: сложность в восстановлении первого и второго прообразов. Или, говоря простым языком про первое свойство, сложность получения такого текста, значение хеш-функции для которого будет равно заданному.
Под сложностью восстановления понимается тот факт, что для нахождения первого прообраза [надёжной криптографической хеш-функции] требуется совершить в среднем не менее 
операций хеширования, где 
— количество бит в выходе криптографической хеш-функции. Взяв современную хеш-функцию с большим размером выхода (начиная от 256 бит) разработчик информационной системы уверен, что восстановить исходные данные по значению хеш-функции нельзя. Чаще всего он прав.
Но есть важный набор случаев, когда несмотря на надёжность хеш-функции восстановление прообраза или даже исходного текста не представляет проблемы. Это случай, когда использовать хеш-функцию бессмысленно. Это случай, когда количество вариантов исходного текста поддаётся перебору.
Читать полностью »
Бенчмарки сделаны в программе SMHasher на Core 2 Duo 3,0 ГГц
На Хабре неоднократно рассказывали про некриптографические хеш-функции, которые на порядок быстрее криптографических. Они применяются там, где важна скорость и нет смысла применять медленные MD5 или SHA1. Например, для построения хеш-таблиц с хранением пар ключ-значение или для быстрой проверки контрольной суммы при передаче больших файлов.
Одно из самых популярных — семейство хеш-функций xxHash, которое появилось около пяти лет назад. Хотя изначально эти хеши задумывались для проверки контрольной суммы при сжатии LZ4, но их стали применять на самых разных задачах. Оно и понятно: достаточно посмотреть на таблицу вверху со сравнением производительности xxHash и некоторых других хеш-функций. В этом тесте xxHash обходит ближайшего конкурента по производительности в два раза. Новая версия XXH3 поднимает планку ещё выше.
Читать полностью »
Привет! Меня зовут Ахмадеев Ринат, я Sr. PHP developer.
Представляю вашему вниманию конспект доклада "Make passwords great again! Как победить брутфорс и оставить хакеров ни с чем" с HighLoad++ 2018.
Докладчик: Алексей Ермишкин, Virgil Security, Inc., Chief Product Security Officer.
Тезисы: https://www.highload.ru/moscow/2018/abstracts/3865.
Слайдов в открытом доступе еще нет, поэтому приводится их текстовая расшифровка.
Когда я шел на доклад, то был настроен пессимистично, действительно, что еще можно нового тут придумать кроме хеша и соли? Но т.к. это Virgil Security, то я все же решил сходить.
В начале доклад казался действительно капитанским, и я даже начал терять интерес, но потом, как оказалось, даже узнал что-то новое.
Мне так понравился доклад, что я подготовил конспект. Всем рекомендую к ознакомлению.
Я расскажу о такой проблеме, как хеширование паролей в веб-сервисах. На первый взгляд кажется, что тут все «яснопонятно» и надо просто взять нормальный алгоритм, которых уже напридумывали много, написать чуть-чуть кода и выкатить все в продакшн. Но как обычно, когда начинаешь работать над проблемой, возникает куча подводных камней, которые надо обязательно учесть. Каких именно? Первый из них — это, пожалуй, выбор алгоритма: хоть их и много, но у каждого есть свои особенности. Второй — как выбирать параметры? Побольше и получше? Как быть с временем ответа пользователю? Сколько памяти, CPU, потоков? И третий — что делать с computational DoS? В этой статье я хочу поделиться некоторыми своими мыслями об этих трех проблемах, опытом внедрения нового алгоритма хеширования паролей в Яндексе и небольшим количеством кода.
Прежде чем переходить к алгоритмам и построению схемы хеширования, надо вообще понять, от чего же мы защищаемся и какую роль в безопасности веб-сервиса должно играть хеширование паролей. Обычно сценарий таков, что атакующий ломает веб-сервис (или несколько веб-сервисов) через цепочку уязвимостей, получает доступ к базе данных пользователей, видит там хеши паролей, дампит базу и идет развлекаться с GPU (и, в редких случаях, с FPGA и ASIС).
Читать полностью »
Коллизии существуют для большинства хеш-функций, но для самых хороших из них количество коллизий близко к теоретическому минимуму. Например, за десять лет с момента изобретения SHA-1 не было известно ни об одном практическом способе генерации коллизий. Теперь такой есть. Сегодня первый алгоритм генерации коллизий для SHA-1 представили сотрудники компании Google и Центра математики и информатики в Амстердаме.
Вот доказательство: два документа PDF с разным содержимым, но одинаковыми цифровыми подписями SHA-1.
Фарид Мансурович Аблаев — заведующий кафедрой теоретической кибернетики Казанского федерального университета. Приехав в московский офис Яндекса, Фарид Мансурович рассказал об алгоритмах, потенциально пригодных для запуска на квантовых компьютерах. Таких устройств пока очень мало, и они толком не освоены даже самыми передовыми компаниями. Но когда они начнут дешеветь, у специалистов уже будут наработки, позволяющие приступить к их использованию.
Одна из сфер, где с появлением квантовых систем могут произойти серьёзные изменения, — механизмы цифровой подписи. В докладе раскрывается алгоритм хеширования, радикально превосходящий аналоги для классических компьютеров. Под катом — подробная расшифровка и слайды.
Preview. Эта идея уже очень давно мучала мой воспаленный криптограффией мозг.
TL;DR идея хеш функции которая генерируется на основе входных данных
Читать полностью »
Привет! Недавно у меня возникла идея создать собственный алгоритм хеширования, на вход которого можно бы было подать информацию любой длины и получить хеш определенного размера. Особенность всех алгоритмов хеширование — в их необратимости. Но существует и другой, не менее важный момент — однозначность.
Читать полностью »
