Больше коллизий, хороших и разных! Или плохая хэш-функция — наше все!

Приветствую, читатели!

В последнее время на Хабре появляется много статей на тему информационной безопасности, так или иначе связанных с недавно вступившим в силу законом об этих ваших энторнетах №89417-6 и участившимися утечками с популярных ресурсов. Я тоже решил не отставать от моды и поделиться своими мыслями на эту тему.

Почему для хэширования паролей считается хорошим тоном использовать криптостойкие хэш-функции, защищенные от поиска коллизий типа ГОСТ 28147-89, md5, sha1, sha2 и т.д.? Ну хорошо, я еще понимаю использование их в хэшировании сообщений, данных для проверки подлинности, в электронных подписях, в алгоритмах поиска, в проверках наличия ошибок и т.п., для чего они собственно и создавались. Но пароли… Зачем здесь защита от коллизий, чтобы злоумышленник точно знал, что он нашел искомый пароль? Так может не так страшен черт, может коллизии это хорошо и чем больше, тем лучше, и лучше взять их на вооружение?

«Но как?», спросите вы. Представьте себе ситуацию: злоумышленник получил доступ к базе данных или даже просто хэши паролей. Вооружившись вычислительными мощностями он начинает ломать хэши. Не успел он начать и вот удача, первый улов, пароли к каким то хэшам подобраны. Потирая потные ладошки он решает проверить, что же он наловил. Пытается авторизоваться под логином ничего не подозревающего юзера (или, если база на руках, грызет ее) и… и это сработало! И что же он видит да шут его знает, а видит он что-то, что считает добычей. Вроде бы и все хорошо, но в то же время, его не покидает смутное сомнение, что как-то слишком все просто, может это мусор? Хотя… Вроде и номер банковской карты получен, и вроде номер телефона, вот же он, почта, какое-то содержимое закрытого контейнера данных бедного юзверя, непонятно что, но что-то точно интересное, может фоточки с котиками, может музыкальные треки или любовные записки. Пока непонятно, нужно разобраться, но уже что-то. В итоге все заканчивается тем, что он не понимает что оказывается у него на руках, не то мусор, не то реальные данные… А юзеров легион миллион, попробуй всех проанализировать.

Что оказывается в итоге, упоротый упорный злоумышленник начнет копать глубже и обнаруживает, что к конкретному хэшу подходит миллион, ну, или даже 10 миллионов паролей. Вот это я понимаю коллизии! Причем, для каждого из них получается различный набор данных пользователя. Вот и приехали.

Как это получается? А очень просто, как уже, наверное, догадались многие читатели, данные пользователя, хранящиеся в базе, шифруются ничем иным, как, собственно, паролем. Позвольте! Но как же! И тут возникает множество возражений, тухлые яйца уже заготовлены. Но постойте, давайте разбираться по порядку.

Да, я не говорил, что такой подход универсален и подойдет на все случаи жизни и да, я не говорил, что он одинаков в применении, даже в тех случаях, где подходит.

Для начала, давайте определимся с задачей и условиями. Итак, первое.

Задача

Главной задачей каждой системы защиты является усложнение жизни Злоумышленнику и максимальное затруднение доступа к закрытой информации.

Здесь задача делится на две подзадачи: доступ к Хранилищу (БД?), доступ к самой информации в Хранилище.

Доступ к Хранилищу

Не всегда бывает возможно ограничить доступ к Хранилищу закрытой информации, особенно, если Злоумышленник в погонах как показывает практика — shit happens утечки случаются. Невозможно уследить за всеми дырами во всех механизмах системы, особенно, если не ты их разрабатывал (механизмы, а не дыры). Тем более доступ к Хранилищу и так часто предоставляется в урезанном виде (авторизация/управление аккаунтом).

Доступ к информации в Хранилище

С Хранилищем вроде понятно. Остается только надеяться на себя и прикладывать максимум усилий именно к защите самой информации, а не доступа к ее Хранилищу. Представляя себе, что доступ к Хранилищу, а так же доступ к исходным кодам защиты подобны проходному двору. Поэтому нужно всегда готовиться к наихудшему варианту развития сценария, когда Злоумышленник получает физический доступ к Базе Данных и даже к коду. Должна стоять задача, что он получит мусор и удовлетворится, либо провазехается с ней годзиллион лет и таки плюнет на нее.

Условия

Предлагаю взять в качестве начальных условий типовую задачу и определиться с терминами.

Что мы имеем:

• Сервис, хранящий данные пользователей, как открытые, так и закрытые;
• Интерфейс Сервиса, через который проходит авторизация и управление аккаунтом;
• База Данных сервиса (Хранилище), в которой все и содержится;
• Код сервиса, открытый;
• Пользователи, пара-тройка миллионов, может больше;
• Злоумышленник, пытающийся либо удаленно, через Интерфейс Сервиса, либо напрямую, имея физический доступ к БД, заполучить данные Пользователей;
• Хранитель, то бишь Вы.

Что мы имеем с технической/алгоритмической точки зрения:

• Закрытый канал (а-ля SSL/TLS);
• «Долгая» авторизация (например, 3 сек.) с последующим отказом при превышении числа попыток;
• Плохая, очень Плохая Хэш-Функция (ПХФ) дающая множество коллизий;
• Что насчет Соли?

С закрытым каналом и «Долгой» авторизацией все понятно. Канал нам нужен для безопасной передачи открытого пароля на сторону сервиса и дальнейшей работы с ним, «Долгая» авторизация для предотвращения попыток лобовой атаки через Интерфейс Сервиса. Но использование Плохой Хэш-Функции вызывает сомнения. И что насчет Соли?

Давайте разберем эти два пункта по порядку и далее уже рассмотрим способы их применения и сам принцип защиты.

Плохая Хэш-Функция

Итак. Что это такое? Представим себе обычный хэш, допустим, разрядностью в 64 бита. Также наличие нескольких миллионов Пользователей.

Нетрудно подсчитать, что количество принимаемых значений хэшем составляет 18 446 744 073 709 551 616, т.е., порядка 18 квинтиллионов. Для нескольких миллионов Пользователей, да даже для всего населения Земли, это неисчерпаемый ресурс. Хорошей хэш-функцией принято называть такую, которая для все тех нескольких миллионов (разных) Паролей Пользователей нам даст уникальный хэш, т.е. повторения (коллизии) хэшей для разных паролей практически исключены (но теоретически возможны, что трудно проверяемо). Защита на таких функция строится на основании того, что очень сложно получить один хэш для разных Паролей, а даже если у разных Пользователей одинаковый Пароль, то тут спасает Соль.

Но защитники часто забывают, что главное это не защитить Сервис от проникновения Злоумышленника, а сохранить данные от раскрытия. По факту получается наоборот, после проникновения и утечки (так или иначе, но это происходит, даже у гигантов) данные оказываются практически, ну, или почти, в открытом виде. Ибо нефик как их защищать толком не ясно, то ли просто по принципу Security Through Obscurity, то ли шифрованием по хэшу, или логину или еще по чему-то, т.е. по тому, что и так содержится в БД и не поможет при наличии БД (и даже кода) у Злоумышленника. Уникальность хэшей только сыграет на руку Злоумышленнику и сузит диапазон поиска. Проблема заключается в том, что вся необходимая для взлома информация содержится в самой БД и коде. Вот и рождаются способы с хранением ключей шифрования у Пользователя в локальном хранилище и др. костыли.

Плохая же Хэш-Функция, наоборот, достаточно часто дает одинаковые хэши для множества Паролей. Как ее можно получить? Что ж, я не математик, но, думаю, даже непрофессионал первым же делом скажет, что нужно понизить разрядность хэша, допустим, до 32 бит. Что дает нам порядка 4 миллиардов значений. Что ж, уже неплохо! Дальнейшие усовершенствования, думаю, не представляют проблемы для специалистов.

Представим, что у нас используются Пароли длиной от 1 (sic!) до 10 (моветон) символов, содержащие цифры, латинские буквы разных регистров и пробел. Итого, мы получим Σ_i=1..10(59^i) = 519 929 111 116 169 700 значений Паролей, т.е. порядка полуквинтиллиона (что даже меньше количества значений 64-битного хэша аж в 36 раз!). Отсюда можно подсчитать примерное желаемое количество Паролей на один 32-битный хэш, это будет порядка 120 миллионов Паролей на хэш. Конечно, это зависит от построенной хэш-функции, задача состоит в том, чтобы в конкретном контексте Плохая Хэш-Функция равномерно «размазывалась» по множеству Паролей (т.е., имела примерно равное количество коллизий на значение), а еще лучше, по словарному множеству Паролей! :D Может и CRC32 хорошо подойдет, кто знает, нужно проводить исследования, может у вас будут другие требования к Паролю.

Написанное может показаться издевательством над здравым смыслом. Но это еще не все!

Итак, Плохой Хэш хранится точно так же в БД, как и классический, а что насчет Соли?

Соль

В использовании Соли нужно соблюдать одно правило — главное, не пересолить! Рассмотрим примеры:

Использование конструкций для получения Плохого Хэша вида

ПХ = ПХФ(Соль+Пароль)

не имеет особого смысла, т.к. сводится к решению ПХФ(Пароль);

В то же время использование конструкций вида

ПХ = ПХФ(Соль+ПХФ(Пароль))

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

Ну, и, конечно же, под Солью подразумевается Случайная Соль.

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

Для чего я писал весь этот бред сумасшедшего, что нам это дает и как это использовать?

Принцип работы

Наконец-то мы добрались до принципа работы защиты построенной на ПХФ.

Смоделируем ситуацию регистрации Пользователя на нашем Сервисе:

• Пользователь задает Логин, Пароль, Почтовый адрес, Номер телефона, Номер пластиковой карты и т.д.;
• Далее, после аутентификации, он заполняет контентом свой аккаунт, контент может быть двух типов:
  1. Открытый (Публичный),
  2. Закрытый (Доступный только Пользователю);
• Последующее использование аккаунта.

Что мы имеем? Начнем с контента. С открытым контентом все понятно, он доступен для чтения (а может и записи) любому желающему. Вся суть механизма защиты сводится к закрытому контенту. Выглядит это в виде зашифрованного контейнера. Ничего не забыли? Ах, да! Так же к закрытому контенту можно отнести поле Номера телефона, Почтовый адрес, Номер карты, по желанию. Но это уже разные типы закрытого контента, и к ним относятся разные способы защиты, об этом далее.

Как же защитить эту информацию от Злоумышленника?

Вся магия происходит в тот момент, когда Пользователь задает Пароль, который отправляется по зашифрованному каналу Сервису, но нигде не хранится (ну, разве что оперативно), а используется только во время сессии Пользователя (что логично и ничего нового тут нет). Но в обычных сервисах Пароль используется только в момент авторизации, а у нас на протяжении всей сессии. Когда Пользователь заполняет/меняет или читает содержимое закрытых полей или содержимое закрытого контейнера, в этот момент происходит, соответственно, шифрование или расшифровка по Паролю. Да-да, на лету.

Что нам это дает и как это происходит?

Механизм таков, что мы шифруем закрытый контент тем ключом (а точнее — Паролем), который точно не содержится в Хранилище Сервиса ни в каком виде (ни в закрытом, ни в открытом, ни даже в виде обфусцированного мегакода). От этого Пароля в БД мы имеем только Плохой Хэш (лишь жалкая тень Пароля), которому соответствует еще несколько миллионов Паролей и, соответственно, для каждого из этих Паролей результат расшифровки закрытых данных будет совершенно различным.

И тут я чувствую, что многие опять схватились за тухлые яйца. Да, возникает множество нюансов. Но обо всем по порядку. Очевидно, появляются следующие вопросы:

1. Да, но что мешает другому Пользователю зайти в чужой или даже в свой аккаунт под любым из этих миллионов Паролей? Ведь одному ПХ может соответствовать множество Паролей!
2. Шифрование Паролем не поможет, ведь по результату расшифровки все равно будет видно, насколько адекватные данные получены, да и та же высокая энтропия, отсутствие предполагаемых паттернов данных покажут, что Пароль подобран неверный!
3. Собственно, вытекающий из предыдущего пункта вопрос, как происходит шифрование разного типа данных? Ведь по расшифрованному Номеру телефона или Почтовому адресу сразу видно, является он валидным или нет, это даже можно автоматизировать!

Отвечаю.

По первому пункту. Да, ничто не мешает пользователю зайти под чужим логином и да, даже под своим логином с другим Паролем. Почти ничто. Но постойте! Разве я говорил, что данный способ защиты подходит абсолютно для всех случаев? К тому же, часто ли типичный Пользователь пытается заходить под левым Паролем в свой аккаунт или в чужой? Да, он может ошибиться, но вероятность совпадения случайной ошибки при наборе и реального Пароля по ПХ маловероятна. В итоге его отлупит упомянутая ранее «Долгая» авторизация. И даже, если он задастся целью, и случайно наткнется таки на подходящий под ПХ Пароль, то ничего интересного он не увидит в чужом аккаунте, как, впрочем, и в своем. Вы скажете, но ведь он сможет повредить чужие данные. Да, сможет, если у него получится сначала зайти. Но главная цель такой защиты как раз не целостность, а нераскрываемость данных. В итоге он ничего не получит, а повредив данные обратит на себя внимание (со стороны настоящего владельца, который тут же сообщит куда надо). Свои пусть вредит сколько влезет.

По остальным пунктам ответ дается в следующей части.

Подходы к шифрованию

Как, собственно, происходит шифрование данных, да причем таких различных, как Номера телефонов, Почтовые адреса, Номера карт, BLOB-контейнеры и тд. Подходов здесь есть несколько и основной принцип здесь состоит в перестановках и подменах значений в допустимых диапазонах.

Сами подходы шифрования:

1. Шифрование BLOB-контейнеров методом перестановок слов 32-64 битной разрядности, возможны вариации, по алгоритму шифрования, определяемому открытым Паролем. Что нам это дает? Известно, что шифрование приводит к повышению энтропии и отсутствию явных признаков исходных данных (известных паттернов), если это только не шум. И обычные методы шифрования (сдвиги, xor-ы, перестановки битов, модули и т.п.) хорошо приводят к такому результату. Но, если взломщик будет пытаться подобрать Пароль, то по высокой энтропии и отсутствию паттернов он определит неподходящий пароль, т.к. результат по сути будет мало отличаться от зашифрованного. При перестановке слов во время шифрования мы получаем не столь высокую энтропию, а так же, множество паттернов может сохраниться, так что даже зашифрованный контейнер будет казаться вполне обычными данными. Попытки расшифровки его так же будут приводить к похожим результатам. Может показаться, что это слабый механизм, но это зависит только от качества реализации алгоритма перестановок на основе Пароля. Вариантов искомых исходных данных может быть бесчисленное множество, учитывая количество подходящих под ПХ Паролей, и Злоумышленник не сможет однозначно быть уверен, это ли он искал, естественно, если он только точно не знает содержимое или его часть (но это уже другие нюансы, а если он знает все содержимое, какой смысл что-то ломать?). Так же никто не отменял вкрапления паттернов и псевдо-данных для снижения энтропии. И даже если рассматривать худший вариант, при котором высокая энтропия присутствует во всех случаях кроме случая расшифровки настоящим Паролем, то только представьте себе весь этот объем работы и анализа, который придется проделать Злоумышленнику.

   
   _{Энтропия низкая, а расшифровать до сих пор не могут.}

2. Далее идет шифрование, а точней, подмена значений id-полей в таблицах Пользователя в БД. Как работает этот подход, где используется и что он дает? Этот подход может использоваться в сокрытии таких данных Пользователя, как Номер телефона, Почтовый адрес, Номер карты и т.п. Работает он следующим образом, опять же, с помощью алгоритма основанного на оперировании значением Пароля, различные id-поля (одно, ведущее к Номеру телефона, другое, ведущее к Номеру карты, 3-е — к ее сроку действия и т.д.) вычисляются в момент доступа настоящего Пользователя, знающего свой Пароль. Злоумышленник же, пытаясь подобрать Пароль под ПХ, для каждого конкретного получаемого Пароля будет получать разные значения id-полей для конкретного Пользователя, которые будут вести его к разным значениям соответствующих полей Номера телефона, Адреса почты и т.д., никак не связанные с данным Пользователем. Да, это не совсем шифрование и не защищает сами данные как таковые, но, по крайней мере, не связывает их с конкретным Пользователем или, по-другому, не выдает реальных данных Пользователя, а вместо этого возвращает чьи-то чужие. Что это нам дает? Ну, например нельзя узнать реальную карту пользователя и ее срок действия, соответственно, нельзя по его реквизитам перевести все деньги и т.д. Чем плохо? Спамерам будет пофигу, они удовлетворятся и просто списком почтовых ящиков. Кстати, название почты и само имя домена почты можно тоже хранить в разных полях, что усложнит жизнь и спамерам. Подход не самый идеальный, но свое очарование в нем есть. Низкая энтропия на лицо :) А так же, его можно комбинировать со следующим подходом защиты, основанной на паранойе Пароле.
3. И, наконец, третий подход. Опять же, он относится к таким закрытым данным, как поле Почтового адреса, Номера телефона и т.д. Реализация его очень специфична и зависит от контекста и защищаемых данных. Суть его заключается в том, чтобы шифровать конкретные поля, например, Номер телефона или Почтовый адрес с помощью, опять же, перестановок (только теперь символьных), но не только, так же подходит подмена значений в пределах допустимых диапазонов, опять же, алгоритмом, основанном на значении Пароля. Начнем с перестановок, возьмем, к примеру, Номер телефона, допустим +7923XXXXXXX. Заметили кое-что важное? Да, это первая часть номера, она остается нетронутой, остальная часть XXXXXXX шифруется перестановками символов и/или заменой символов другими символами из допустимого диапазона (в данном случае — цифры 0-9), алгоритм шифрования должен это проделывать на основании исходного открытого Пароля, так же, результат должен быть обратим для расшифровки, как и в других случаях. В примере с Почтовым адресом, например таким XXXXX@gmail.com, тоже должна быть нетронутая часть, и эта часть — имя домена, думаю, тут понятно, имя домена можно легко проверить на валидность. В случае с Номером карты нужно учитывать его контрольную сумму и т.д. Что мы получаем в итоге? В итоге зашифрованные поля выглядят очень похоже на вполне себе незашифрованные. Сложно проверить на валидность. Низкая энтропия. Профит. Минусы — частный подход к конкретным типам данных.
4. Другие подходы… вполне возможны, идеи приветствуются.

Где это применимо

Допустим, у нас есть Dropbox. Ну ладно, не сам дропбокс, а аналог. В этом случае такая схема защиты может нам вполне подойти, у Пользователя есть как открытые, так и закрытые данные. Если произойдет утечка, или попытка удаленного прорыва, то смысла ломать открытые данные нет никакого, они и так открыты и не зашифрованы, а что касается закрытых данных, их расшифровка будет очень проблематичной, максимум, что сможет сделать Злоумышленник — повредить закрытые данные, но зная, что в такие сервисы обычно не кладут критичные данные и/или данные в единственном экземпляре, то большой проблемы такое проникновение для Пользователя не создаст, да, осадочек останется, но данные останутся нераскрыты. Конечно, теоретически всегда возможна случайная удача со стороны Злоумышленника, но она будет настолько маловероятна, что практически невозможна. Обычные способы защиты в этом плане ничем не лучше — везения со стороны Злоумышленника будет примерно столько же, а может и меньше.

Еще один вариант. Довольно-таки экзотичный. Представим, что у нас есть некий Сервис, предоставляющий в пользование личную искусственную нейронную сеть, не знаю что бы это могло быть, ну, например, для студентов или научных сотрудников, каждая сеть независимо обучается своим Пользователем. Тут немного сложней, шифрование/расшифровка по Паролю ее содержимого (коэффициентов, связей) должна будет происходить полностью, и, если она большая, то делать это будет накладно. Но в то же время, при получении Злоумышленником доступа к БД, он вряд ли сможет ее вскрыть. Ну, восстановит он какую-то GLaDOS непонятную кашу из непонятных связей, что она сможет делать, как проверить ее на валидность — нет ни малейшего представления.

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

Плюсы

Какие очевидные плюсы в данном подходе к защите информации?
Я вижу следующие:

• Можно использовать любой Пароль, (почти) любой длины и сложности. Нет необходимости придумывать закорючные пароли невероятной длины.
  
  Конечно, минимум тоже должен быть задан, например, 6 или 8 символов, что отбивает желание всем пользоваться исключительно короткими 2х-, 3х-символьными паролями;
• Большая сложность по подбору оригинального Пароля, учитывая выбор хорошей Плохой Хэш-Функции и хороших алгоритмов шифрования/расшифровки;
• Одним из основных плюсов, я считаю, является то, что ввиду большого числа коллизий есть возможность, в виде дополнительной услуги для Пользователя, помимо основного Пароля, сгенерировать несколько дополнительных Паролей для друзей ФСБ-шников;
  
• Это не Security Through Obscurity. Можно открыть исходный код и Хранилище и предложить попробовать достать из этого что-нибудь кроме «Из крыжовника, пыткам подвергнутого, немало вытянуть можно», особенно, учитывая, что у многих Пользователей с разными Паролям могут быть одинаковые плохиши Плохие Хэши.

Минусы

Минусы тоже достаточно очевидны:

• Частный подход к алгоритмам шифрования, выбору ПХФ;
• Ненулевая возможность входа в чужой аккаунт под левым Паролем и/или повреждение чужих данных;
• Отсутствие возможности использования полузакрытого контента, т.е. закрытого для всех, кроме, например, друзей;
• Проблематично использование большого закрытого контента, который требует расшифровки в полном объеме во время работы с ним. Зависит от типа контента и алгоритмов шифрования, не весь большой контент требует полной расшифровки;
• Еще один минус, дополняющий предыдущий, в том, что при смене Пароля придется перешифровывать весь закрытый контент, что может быть накладно;
• Если злоумышленник знает Номер телефона или Почтовый адрес жертвы, то тут могут возникнуть проблемы;

UPD. (спасибо TolTol и Loki3000)

• Отсутствие возможности авторизации через сторонние Сервисы, когда Пароль не передается в принципе;
• Восстановление Пароля для Пользователя будет большой головной болью.

Выводы

Выводы делать только Вам, уважаемое читатели.

Заключение

Да, в посте нет ни доказательств теорем, ни научного подхода, ни математических выкладок, ни практических опытов, ни строчки кода. Есть только длинная бессвязная портянка и многа букаф. Пост может показаться сумбурным и скомканным, да что там, так и есть, я лишь хотел поделиться мыслями в моей голове, которые еще не окончательно в ней упорядочились, но не дают покоя и, чтобы хоть как-то привести их в порядок и послушать мнения умных людей, решил излить их на бумагу в виде поста. Возможно, читатели приложит свою руку и наставит меня, глупца, на путь истинный. Спасибо за внимание и да хранит Б-г тех, кто дочитал до сель!

_{Замечу, так же, что я не являюсь экспертом в области криптографии и информационной безопасности, что очевидно, поэтому прошу, не пинайте меня строго и не забрасывайте сильно гнилыми помидорами. Рассчитываю на конструктивную критику и интересные обсуждения в комментариях.}

Автор: Indexator