Parole*, paro*es, *aroles…
Частичные пароли: история о том, как задёшево вывести из себя пользователя и/или как вставить палки в колёса кейлоггерам.
Здравствуйте!
Что такое частичный пароль? Каковы достоинства и недостатки их использования в процессе аутентификации? В статье подробно рассматриваются математические основы, технические детали и практика применения частичных паролей. Предлагается порассуждать об их месте в современных цифровых системах.
Начнем, как принято, с определения: частичные пароли (от англ. partial passwords, pps) – это один из методов аутентификации, при котором у пользователя просят ввести некоторый случайный набор символов из пароля вместо полного пароля. Например, запрос может выглядеть следующим образом: «Пожалуйста, введите 2-й, 3-й и 6-й символ!». Я с удивлением обнаружил, что pps широко распространены на страницах многих зарубежных компаний, особенно в финансовом секторе. Однако, как пользователь, до недавнего времени я не был знаком с такой модификацией классической парольной защиты, но она показалась мне довольно занимательной. Источников на русском языке мне найти не удалось, поэтому я решил взять на себя ответственность рассказать читателям о pps, сопровождая материал пояснениями, формулами и картинками, помогающими понять суть вопроса. Приятного чтения!
Содержание:
Математический теорминимум
Контекст и мотивация к использованию pps
Детали реализации pps
Атаки на pps. Математические модели и некоторые численные результаты
Модельный пример реализации pps на языке python
Обсуждение и выводы
1. Математический теорминимум, иллюстрированный
Предполагая, что этот текст может быть интересен широкому кругу лиц, считаю необходимым привести некоторые элементарные факты из комбинаторики и теории вероятности, которые будут активно использоваться в статье.
(Если Вы без труда отличаете размещение без повторений от сочетаний с повторениями и помните, чем отличаются независимые события от несовместных, то можете пропустить этот раздел)
Много букв, еще больше картинок
Факториал натурального числа n
Число перестановок без повторений из n
Найдем количество всевозможных способов расставить n различных элементов по n упорядоченным позициям. Их
Число перестановок с повторениями из n для m типов,
Вновь имеем n упорядоченных позиций. В отличие от предыдущего случая, рассматриваются m различных типов элементов, в каждом из которых по
Число размещений из n по k без повторений
Найдем количество способов разместить
Число размещений из n по k с повторениями
Имеем
Число сочетаний из n по k без повторений
В случае сочетаний изменим постановку задачи. Рассмотрим некоторое множество из
Очевидно, что
Число сочетаний из n по k с повторениями
Что ж, пожалуй, это самая сложная часть в импровизированном теорминимуме. Эту задачу можно интерпретировать двумя эквивалентными способами. Один будет полезен в статье, а другой поможет вычислить количество сочетаний с повторениями.
Первый способ позволит нам легко найти значение величины
Второй способ, более нам интересный: пусть у нас есть
Вероятность (рекомендуется к ознакомлению, если читатель не помнит определения или не знаком с темой )
Теория вероятностей — раздел математики, изучающий случайные события, случайные величины, их свойства и операции над ними. Это один из самых молодых разделов математики, который получил свое строгое обоснование лишь в конце двадцатых годов прошлого века, в работах А.Н. Колмогорова. В наши дни теория вероятностей имеет одно из центральных мест во многих естественных и прикладных науках, начиная от социологии и лингвистики, заканчивая информатикой и квантовой механикой. «Нет почти ни одной естественной науки, в которой так или иначе не применялись бы вероятностные методы» (Вентцель Е. С.).
Теория вероятностей была известна еще в средние века, но не была оформлена как раздел математики, являясь более набором эмпирических фактов, которые часто формулировались в наглядных представлениях и задачах. В те стародавние времена двигателем прогресса в данном направлении были азартные игры.
В статье нам не понадобится ничего более, чем элементарные факты из теории вероятности, еще «доколмогоровской», скорее «средневеково-азартной», если позволите. Пусть какой-то «черный ящик» (рулетка) выдает случайное «нечто», только одно за раз . Назовем это экспериментом. Пусть число всевозможных «нечто», которые выдает рулетка, равно
Для экспериментов, где
Введем понятие независимости. Это центральное понятие в теории вероятностей, которое в первую очередь отделило ее от смежных разделов математики. Пусть у нас есть другое событие
Упражнение (со звездочкой): докажите, что число цепочек одновременных событий, необходимых для проверки независимости r событий (об этом написано выше), равно
Однако для нас интересен самый легкий случай: конечный набор элементарных исходов. Для таких экспериментов независимость можно проверить до безобразия простым образом: важно, чтобы один элементарный исход принадлежал не более, чем одному событию. Можно проверить, что в этом случае определение эквивалентно данному выше.
Назовем события несовместными, если они не могут происходить одновременно (не пересекаются по элементарным исходам).
Если события несовместны, то вероятность события
Если же события не являются несовместными (то есть совместны), то данная формула чуть усложняется - требуется вычесть вероятность одновременной реализации обоих событий, которую мы учли дважды (см. формулу включений-исключений):
Скажем также про условную вероятность. Условная вероятность события
В этой формуле есть небольшая проблема: если событие
Осталось вспомнить формулу полной вероятности. Представим, что всевозможные элементарные исходы разбиваются на непересекающиеся события
Для пояснения последней формулы стоит привести пример. Будем кидать игральный кубик (кубик честный, то есть выпадение каждой грани равновероятно и равно 1/6). Вероятность выпадения четного числа очков равна 1/2. Такая же вероятность и у нечетного числа очков на кубике. Два этих события — разбиение всех элементарных исходов 1-6. Вероятность выпадения числа, кратного 3, при условии выпадения четного числа очков — это 1/3 (только 6 из 2, 4, 6). Вероятность выпадения числа, кратного 3, при условии нечетного числа очков — это тоже 1/3 (только 3 из 1, 3, 5). Тогда вероятность выпадения кратного 3 числа очков на кубике равна: 1/2 * 1/3 + 1/2 * 1/3 = 1/3. Это так, ведь нам интересны числа 3 и 6 среди 1, 2, 3, 4, 5, 6.
Сделаю финальное замечание. Вероятность события — это вещественное число из отрезка от 0 до 1. В литературе, особенно математической, не принято записывать вероятность в процентах (можете назвать это снобизмом). Но для удобства изложения и краткости формулировок часто прибегают к использованию ‘%’, особенно в прикладных областях. Так что и здесь иногда будут использоваться проценты, за что перед особо впечатлительными я заранее извиняюсь.
На мой взгляд, это все, что было бы неплохо вспомнить из комбинаторики и теорвера перед основным текстом. Прошу прощения, если был излишне многословен.
2. Общие слова о pps
Вопрос обеспечения безопасности и эффективности процесса аутентификации пользователя на онлайн-ресурсе — крайне важная задача для компаний и организаций по всему миру, в эпоху бурного развития цифровых услуг, которая получила новый толчок к росту в последние полтора года, в период пандемии.
Существует множество различных методов аутентификации, такие как криптографические токены, биометрия и другие. Однако введение пароля остается наиболее общеупотребительной схемой аутентификации из-за своей простоты, эффективности и надежности (по крайней мере, теоретической). Однако же эта теоретическая, математическая надежность имеет множество «но», связанных с конкретными техническими реализациями процесса аутентификации, работой с реальным оборудованием, с реальным ПО и по реальным каналам связи, где могут возникнуть дополнительные уязвимости, снижающие безопасность системы. Конечно же, одной из центральных причин уязвимости схемы с паролями является человеческий фактор.
Теоретическая надежность паролей строится на его сложности, а точнее на его достаточной длине, достаточно большом алфавите и независимости, случайности символов в нем. Это делает пароль более защищенным перед различными атаками, связанными со статистическим анализом языка, подбором наиболее употребительных паролей или его частей из утекших баз данных и тому подобных. В идеальной ситуации, пользователю бы следовало выбирать пароль максимальной длины с независимым друг от друга выбором символов из всего доступного алфавита. Само собой, это идет в категорический разрез с человеческой натурой, поэтому, перебрав с десяток паролей-мемов (по типу password, qwerty и т.п.), дат и строк из песен можно взломать множество аккаунтов, что подтверждают многочисленные утечки, одна из которых будет использована в статье.
«We are humans. And sometimes, very humans»
Кроме того, возможны атаки с использованием вредоносных программ, различных кейлоггеров или же атаки с использованием социальной инженерии, как в офлайне (подсматривание пароля, кража имущества с данными об аккаунте), так и в онлайне (вымогательство, введение в заблуждение). Таким образом, злоумышленник может получить данные об аккаунте в один шаг. Также интересным применением может быть работа пользователя в системе, в безопасности которой он не может быть уверен наверняка (например, терминалы или кассы на улице, банкоматы с зловредными скиммерами).
В связи с этим изучаются специальные способы идентификации, с помощью которых можно было бы избежать компрометирования пароля пользователя за один раз. Одно из направлений — использование различных запросов при входе в аккаунт, не требующие ввода пароля целиком [1], [2]. В частности, могут использоваться частичные пароли (partial passwords, pps): сервер запрашивает ввести некоторый случайный набор символов из пароля, указанный при регистрации. Использование pps - простой и эффективный способ противостоять некоторым типам атак, которые могут получить информацию о полном пароле. Утверждается, что такая схема более безопасна, ведь число возможных запросов растет быстро при правильном выборе параметров (об этом более подробно будет написано ниже). Так, для пароля длины n при запросе m символов получаем
Кроме того, запрос частичного пароля в виде раздельных окошек с вынесенным отдельно запросом может стать непреодолимой преградой для простых, распространенных вредоносных программ, что делает идею взлома таких аккаунтов более технически сложной задачей.
Частичные пароли широко используются в банковском секторе, особенно в Великобритании (например: AIB, Standard Life, Barclays, HSBC, Bank of Ireland и др.), как часть двухэтапного (как минимум) процесса аутентификации [1]. Такое доверие к технологии, которая мало обсуждалась в научном сообществе и слабо изучена, может удивлять, как и ее широкое распространение лишь в нескольких странах в мире.
Поговорим об основных типах атак на pps. В большинстве своем, атаки на обычные и частичные пароли совпадают, за тем исключением, что злоумышленнику, как правило, требуется несколько перехватов информации о пароле, чтобы с большой вероятностью успешно ответить на очередной запрос сервера. Приведем основные типы атак:
Bruteforce: злоумышленник перебирает все возможные комбинации паролей в доступном алфавите. Далее он перебирает их по очереди, пока ответ на очередной запрос не будет успешным.
Атака с использованием словаря: при атаке используются статистические методы, основанные на частоте встречи букв в языке, на характерных сочетаниях букв и слов, распространенных видах паролей из скомпрометированных баз данных и т.п.
Кейлоггер (атаки с запоминанием): злоумышленник использует программу, чтобы отслеживать нажатия клавиш пользователем и использует накопленные данные для взлома всего пароля.
Разумеется, более эффективными являются комбинации описанных выше методов атак. Отдельно будет рассмотрена уязвимость pps, связанная с атакой не на конкретного пользователя, а на большую группу аккаунтов (trawling attack).
Вредные советы (перед прочтением сжечь)
Для желающих, в качестве теста, я ни при каких обстоятельствах не стал бы оставлять ссылку на сайт английского банка. На нем не советовал бы, введя случайные символы в качестве имени, увидеть пример интерфейса ввода частичного пароля (здесь – securecode, как дополнение к основному паролю). Now remember, I told you nothing, okay?
3. Детали реализации pps
Поговорим о том, как работают pps более подробно. Частичный пароль — это запрос ввода части символов из полного пароля. Протокол состоит из следующих этапов [2]:
Регистрация: пользователь выбирает пароль
длины , состоящий из символов некоторого алфавита (например, цифры для PIN, цифры и буквы для буквенного пароля). Выбор в некотором формате сохраняется на сервере (об этом будет рассказано в чуть ниже). Вход в систему: процесс аутентификации представляет собой последовательность вопрос-ответ:
Вопрос: сервер выбирает некоторое подмножество натуральных чисел
из и отправляет запрос ввода пользователю
Ответ: пользователь отвечает на запрос в форме
. Вход в систему производится только в случае для всех (то есть если предоставленные данные корректны).
Позиция | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Пароль | s | e | s | a | m | e | o | p | e | n |
Запрос (2,3,6) | e | s | e |
Остается простор для выбора оптимальных параметров: какой размер пароля
Интерес вызывает то, каким образом стоит хранить пароли пользователей на стороне сервера. Как правило, в классических реализациях аутентификации с помощью пароля на стороне сервера достаточно хранить только хэш от пароля (еще почитать можно тут). В этом случае нахождение пароля по данному значению хеша (или другого пароля с таким же значением хэша) является вычислительно сложной задачей, допускающей только полный перебор (впрочем, и тут есть некоторые уязвимости). Так что злоумышленник или нерадивый администратор, даже получив базу данных паролей с сервера, не сможет восстановить пароли по записанным там значениям хешей. В этом смысле такой подход значительно лучше, чем хранения пароля в виде текста. К примеру, широко распространены хеш функции семейства SHA (https://ru.wikipedia.org/wiki/SHA-2).
Однако в случае использования pps возникают некоторые сложности. Если вернуться к идее использования хешей, то нам придется хранить все возможные значения хеш-функции при выборе m из
Можно здесь сделать также интересное замечание: возможно, подбор параметров pps многими банками как раз был связан с использованием всего множества значений хешей. Как правило, у них
Что ж, не вернуться ли к идее хранения паролей в виде текста? На секунду может прийти такая мысль. От нее сразу же лучше отказаться: велика опасность компрометирования паролей пользователей. Это не вариант.
Другая возможная реализация заключается в следующем: пароль может храниться на сервере в зашифрованном виде с использованием какой-либо схемы симметричного шифрования, например AES. Тогда управление ключами может осуществляться с помощью оборудования, защищенного от несанкционированного доступа, например аппаратного модуля безопасности (Hardware security module, HSM) или отдельного сервера аутентификации с системами контроля доступа, чтобы избежать несанкционированного получения третьими лицами криптографического ключа. Так мы получаем черный ящик для шифрования и проверки подстрок символов в пароле, а именно: введенные символы пароля передаются в приложение, далее на HSM или сервер аутентификации вместе с паролем в зашифрованном виде. Далее HSM может расшифровать пароль и подтвердить или опровергнуть правильность предоставленных пользователем символов. Недостатком этого метода является использование специального оборудования и серверов, что увеличивает накладные расходы. Кроме того, в процессе аутентификации все же происходит полная расшифровка пароля, и при определенных обстоятельствах, может произойти утечка всего пароля.
Схема разделения секрета
Наиболее естественной реализацией является использование схем разделения секрета (например, схема Шамира). Схема Шамира позволяет реализовать
Обсудим идею схемы Шамира. Она довольно проста: для того, чтобы однозначно интерполировать многочлен степени
4. Виды атак на pps
Bruteforce
Обычная bruteforce-атака использует лишь информацию об алфавите (алфавит можно узнать при регистрации). Пусть размер алфавита равен
Скажем, что при регистрации пользователю предоставляется
Между делом, хочу еще раз напомнить, что pps часто используются в комплексе с другими средствами безопасности, такими как: запрос дополнительных данных о пользователе, двухфакторная аутентификация (почта, сообщения) и другими.
Само собой, атаки с полным перебором — это самый примитивный вариант для взлома. Однако если бы все пользователи выбирали пароли со случайным набором символов, то ничего лучше предложить злоумышленнику в этом случае и не получилось. Но люди используют некоторые устойчивые конструкции языка, слова, благозвучные комбинации букв, даты и тому подобное. Поэтому можно придумать что-то получше. Чуть более сложный вариант взлома паролей — использование данных о частоте встречи букв на определенных позициях. Так и назовем следующих подраздел.
Атака с использованием данных о частоте появления отдельных символов на определенных позициях
Теперь будем не просто случайно подбирать символы на каждую позицию, а использовать то, насколько часто тот или иной символ встречается в языке или, что еще лучше, в паролях, украденные базы с которыми были выложены в общий доступ. В статье рассматривается утечка базы RockYou, которая произошла в 2009 году. Это 32 миллиона паролей от сайта с приложениями, которые попали в сеть и теперь доступны всем желающим, в том числе и для научных изысканий. Приведем графики, на которых изображена зависимость частоты появления цифр в зависимости от позиции в шестизначных паролях из цифр (алфавит размера
Так, на графике видно, что буква ‘a’ встречается в среднем в 8% случаев в каждой позиции в 8-буквенных паролях, но на 2-ой позиции появляется в 18% случаев. То же и про цифры: так, в 6-значных PIN цифра ‘1’ встречается в 17% случаев в каждой позиции, но в 40% случаев на 1-ой позиции (вероятно, связано с датами и "123456").
Теперь попробуем провести эту атаку на саму же базу, работающую с pps, используя информацию о частоте появления букв в каждой из позиций (пароли будем выбирать случайно). Размеры PIN все те же 6 цифр, запрос
Заметим, что на левом графике 15 линий (ведь есть
Уже намного лучшие показатели, но язык не состоит из всевозможных сочетаний букв. Одни сочетания букв встречаются часто (например, «ing» или «con»), другие не встречаются вовсе (к примеру, «aaa» или «ww»). Поговорим далее об использовании сочетаний букв из английского языка для взлома pps.
Атака с использованием данных о частоте сочетаний символов на определенных позициях. Подбор пароля.
Теперь будем использовать данные о частоте встречи сочетаний букв в языке. Так, при запросе частичного пароля, будем принимать во внимание частоту появлений символов одновременно на требуемых позициях.
Было взято 11600 8-буквенных слов английского языка (из словаря ubuntu). Для запроса 2,3,6 позиций оказалось 2736 возможных ответа (16% от
Для запроса 6,7,8 получаем около 30%! Результат оказывается таким большим из-за распространенного окончания «ing». Построим графики зависимости доли взломанных pps для всех возможных запросов и среднее значение доли успехов от числа попыток ввода:
Видим, что для того, чтобы практически в 100% случаев взломать pps требуется порядка
Использовать сочетания букв из словаря — хорошая идея. Но что будет, если учиться на базах данных взломанных паролей?
Атака с использованием данных о частоте сочетаний символов на определенных позициях в реальных паролях
Можно проделать те же рассуждения, но основываясь на утечках из баз данных паролей. Вновь обратимся к базе RockYou. Так, 5 самых популярных 8-символьных паролей покрывают около 3% от всех паролей, что выглядит удручающе. Для PIN первые 6 охватывают 15.3% от общей доли, притом 12.8% (!) приходится на «123456». Хочется надеяться, что пользователи выбирают пароли для аккаунтов в финансовых и государственных учреждениях, соцсетях более осознанно, чем на сайтах игр, но все новые и новые сливы баз паролей, к сожалению, говорят об обратном.
Понятно, что такие проценты взлома пароля на 3-4 порядка превышают обычную bruteforce-атаку. Теперь перейдем к pps и найдем долю самых распространенных сочетаний букв для тех же запросов, что и в предыдущем разделе (см таблицу).
Теперь попытаемся взломать пароли из базы: снова будем брать случайный пароль и случайный запрос, выбирая для каждого типа запроса ответ с вероятностью, пропорциональной частоте встречи сочетаний во всей базе. Графики доли взломанных паролей для PIN (слева) и пароля из букв и цифр (справа) с теми же параметрами от числа попыток
Здесь мы получили наилучший результат атаки: от 22% до 50% со средним 30.6% для PIN с 6 попытками и от 4.2% до 10% со средним 5.5% для пароля из цифр и букв c 10 попытками.
Далее рассмотрим атаки, для противостояния которым и созданы pps: кейлоггинг или атаки с запоминанием.
Кейлоггинг (атаки с запоминанием)
Вот мы и пришли к атаке, с которой, как предполагается, эффективно справляются pps. Рассмотрим этот случай подробнее. Для теоретической оценки оптимальных параметров построим математическую модель частичных паролей.
Пусть пользователь создал пароль
Сценарий A (без повторений). Запрос вида
, где для , при этом для различных и . Сценарий B (с повторениями). Запрос вида
, где для (запрос может содержать повторяющиеся позиции).
Будем считать, что злоумышленнику удается перехватить вид запроса и ответ до того, как эти данные будут зашифрованы. Построим теоретические зависимости вероятности того, что пароль будет восстановлен полностью и вероятности того, что на запрос pps можно будет ответить с достаточно большой вероятностью от числа попыток ввода
Теорема
Пусть
Докажем этот факт. Действительно, если злоумышленник на момент предыдущего,
В сценарии A повторения не допускаются. Очередной,
На
шаге было известно символов ( ); выбор в запросе недостающих
символов из неизвестных (сочетания без повторений, ); выбор в запросе оставшихся
из уже известных символов (сочетания без повторений, ).
Рекуррентная последовательность начинается с
В сценарии B выбираются
Две основные формулы нами получены. Построим теперь зависимость вероятности
Как мы видим, в сценарии B вероятность полного раскрытия пароля ниже, чем для A при всех значениях числа попыток
Теперь рассмотрим, с какой вероятностью злоумышленник точно ответит на следующий запрос, имея информацию о
После
Приведем графики зависимости этих величин для некоторого набора параметров:
Видим, что хотя на первых нескольких попытках вероятность ответа чуть ниже у сценария A (так как в запросе не может быть повторов), но для всех остальных значений сценарий B имеет значительно более высокую стойкость к взлому. Однако, при выборе параметров, близких к используемым на практике, устойчивость к взлому все равно пугающе низкая (благо это только один из этапов аутентификации). Так, в случае
Сценарий B показывает лучшие результаты в сравнении со сценарием A (что довольно неожиданно). Но все же, запросы вида «Введите символы 1,1,3» или, тем более, «Ждем позиций 7,7,7» будут выглядеть несколько странно. Напомним, что такие выводы проделаны в сценариях, где злоумышленник пытается взломать пароль наверняка, не занимаясь подбором (крайне актуально в случае, когда он не хочет дать знать своей жертве о своих попытках входа).
Атака, когда позиции символов неизвестны
Вкратце поговорим о таком виде атак. Предположим, что по какой-то причине злоумышленнику удалось перехватить некоторое множество символов, но он не знает, на каких позициях они расположены (можно придумать случай, когда кейлоггер уж совсем неизобретательный и не может отследить текст запроса, а только нажатие клавиш). Рассмотрим, для простоты, случай, когда известен весь набор букв в слове (например, кейлоггер работал на компьютере пользователя месяцами и наверняка перехватил все возможные комбинации символов). Для сравнения, рассмотрим случай, когда известна длина пароля (например, на ресурсе, аккаунт на котором пытаются взломать, длина пароля фиксирована или по каким-то причинам не является секретом) и когда все же некоторые позиции символов известны. Возьмем пароль P=«password». Множество его символов S_P={‘p’,’a’,’s’,’w’,’o’,’r’,’d’}. Проведем эксперименты:
Эксперимент А: известно
и позиции 2 символов. Эксперимент B: известно
и длина пароля. Эксперимент C: известно
, длина пароля и позиции 2 символов.
Заранее можно сказать, что мораль будет в следующем: не надо давать никакой открытой информации о пароле пользователя при входе или выносить на дальний план ее защищенность. Также не надо давать подглядывать подозрительным незнакомцам (особенно в шляпе и черных очках, уж тем более в плаще и с именем Ева). Это мы и демонстрируем на данном примере (в столбцах A, B, C приводится количество подходящих под описание паролей из базы RockYou):
На этом месте в нашей статье мы остановимся со сравнением сценариев A и B. Далее будет рассматриваться только сценарий А. Желающие могут проделать аналогичные вычисления для сценария B. Это будет полезно для сравнения этих двух подходов в сценариях, где pps будет угадываться с некоторого момента, а не собираться достаточная информация для 100% преодоления запроса.
Атака кейлоггинг + bruteforce с несколькими попытками
Теперь соберем в кучу все, что мы знаем (синергируем, так сказать). Рассмотрим, для примера, сценарий A. Постановка задачи в основе своей остается той же, но дополняется следующим образом: мы допускаем на каждом этапе (вне зависимости от наших знаний о пароле) использование bruteforce-атаки, также имеем в запасе
Далее запишем выражение для доли запросов с
Если злоумышленник знает
Здесь
Теперь остается построить графики зависимости вероятности успешно ответить на запрос pps от числа перехваченных запросов для некоторых наборов параметров, употребительных в реально существующих системах (левый график для алфавита
Видим, что результаты значительно лучше предыдущих (для взломщика), основанных на отдельно запоминании или bruteforce (важно отметить, что здесь еще есть
Атака кейлоггинг + использование частоты встречи сочетаний символов на определенных позициях с несколькими попытками
Ведем огонь из всех орудий. Повторений символов в одном запросе вновь нет. Приведем грубую нижнюю оценку для вероятности взлома в этом случае. Используем данные из разделов выше для атаки с частотностью сочетаний символов и будем выбирать в своих попытках ввода самые распространенные из них. Приведем лишь численные значения для
Атака | Параметр | Вероятность взлома | |
PIN | пароль | ||
Кейлоггинг + bruteforce | 0.411 (0.838) | 0.096 (0.691) | |
Кейлоггинг + словарь | 0.602 (0.904) | 0.252 (0.812) |
Закономерно получаем, что выбор наиболее распространенных вариантов сочетаний значительно увеличивают вероятность взлома pps. Числа становятся довольно пугающими, что говорит о том, что в реально существующих системах подбор параметров pps нужно проводить более тщательно. Ожидаемо, что защищенность увеличивается при увеличении размера словаря
Об общих выводах напишем чуть ниже, а сейчас перейдем к модельному примеру реализации pps с использованием схемы разделения секрета Шамира на языке python.
5. Модельный пример реализации pps на python
Реализуем pps с схемой разделения Шамира на языке python:
pps.py
import base64
import bcrypt
import os
import shamir
import time
import random
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.backends import default_backend
def generate_partial_password(password, min_parts_required,
work_factor,
salt_length=16):
"""Создадим pps"""
plen = len(password)
salts = []
keys = []
ivs = []
for i in range(plen):
salts.append(os.urandom(salt_length))
keys.append(bcrypt.kdf(password=password[i].encode('utf-8'), salt=salts[i], desired_key_bytes=32, rounds=work_factor)) # Key Derivation Function
ivs.append(os.urandom(16))
secret, shares = shamir.make_random_shares(minimum=min_parts_required, shares=plen)
encrypted = []
for (x, y), key, iv in zip(shares, keys, ivs):
backend = default_backend()
cipher = Cipher(algorithms.AES(key), modes.CBC(iv), backend=backend) # алгоритм AES + Cipher Block Chaining (CBC)
encryptor = cipher.encryptor()
ct = encryptor.update(y.to_bytes(32, byteorder="little")) + encryptor.finalize()
encrypted.append(ct)
output = []
for salt, iv, ct in zip(salts, ivs, encrypted):
output.append({'salt': salt, 'iv': iv, 'ct': ct[:16]})
secret = base64.urlsafe_b64encode(secret.to_bytes(16, "little"))
print(secret)
hashed_secret = bcrypt.hashpw(secret, bcrypt.gensalt())
return output, hashed_secret
def test_partial_password(password, p, hashed_secret, work_factor):
"""Проверка правильности введенных символов"""
shares = []
for k,v in password.items():
key = bcrypt.kdf(password=v.encode('utf-8'),
salt=p[k]['salt'],
desired_key_bytes=32,
rounds=work_factor)
backend = default_backend()
cipher = Cipher(algorithms.AES(key), # алгоритм AES
modes.CBC(p[k]['iv']), # Cipher Block Chaining (CBC)
backend=backend)
decryptor = cipher.decryptor()
ct = p[k]['ct'] + (0).to_bytes(16, 'little')
y = decryptor.update(ct) + decryptor.finalize()
y = int.from_bytes(y[:16], byteorder='little')
shares.append((k+1, y))
secret = shamir.recover_secret(shares)
secret = base64.urlsafe_b64encode(secret.to_bytes(16, "little"))
if bcrypt.checkpw(secret, hashed_secret): # проверка соответствия хешированного и нехешированного пароля
return True
else:
return False
if __name__ == '__main__':
password = input('Введите пароль:')
f = False
while f == False:
print(f'Введите размер запроса от 1 до {len(password)}')
try:
min_parts_required = int(input())
if min_parts_required > 0 and min_parts_required <= len(password):
f = True
else:
print('Неверный диапазон')
except ValueError:
print('Введите корректное значение')
print('Генерация секрета из пароля и "точек" для каждой буквы')
output, hashed_secret = generate_partial_password(password,
min_parts_required=min_parts_required,
work_factor=50)
print("Вывод:", output)
print("Хешированный секрет:", hashed_secret)
print('Проверка введенных паролей')
challenge = sorted(random.sample(range(0, len(password)), min_parts_required)) # запрос без повторений
response = []
print(f"Введите символы {[challenge[i] for i in range(min_parts_required)]}!")
i = 0
while i < min_parts_required:
input_char = input(f"Символ {challenge[i]}:")
if len(input_char) == 1:
response += input_char
i += 1
else :
print('Введите единичный символ')
pps = dict(zip(challenge, response))
start = time.time()
result = test_partial_password(pps, output, hashed_secret, work_factor=50)
print("Выполнение:", time.time() - start, "сек")
reply = "верны" if result else "неверны"
print(f"Введенные символы {reply}")
shamir.py
from __future__ import division
import random
import functools
# 12-ое простое число Мерсенна
_PRIME = 2**127 - 1
_rint = functools.partial(random.SystemRandom().randint, 0)
def eval_at(poly, x, prime):
'''
Значение многочлена в точке x
'''
accum = 0
for coeff in reversed(poly):
accum *= x
accum += coeff
accum %= prime
return accum
def make_random_shares(minimum, shares, prime=_PRIME):
'''
Генерация случайных точек полинома
'''
if minimum > shares:
raise ValueError("восстановление секрета невозможно")
poly = [_rint(prime) for i in range(minimum)]
points = [(i, eval_at(poly, i, prime))
for i in range(1, shares + 1)]
return poly[0], points
def extended_gcd(a, b):
'''
Реализация расширенного алгоритма Евклида,
поиск x, y: ax+by=gcd(a,b)
'''
x = 0
last_x = 1
y = 1
last_y = 0
while b != 0:
quot = a // b
a, b = b, a % b
x, last_x = last_x - quot * x, x
y, last_y = last_y - quot * y, y
return last_x, last_y
def divmod(num, den, p):
'''
Вычисление num / den mod p = num * (den)^(-1) mod p
Возвращаемое значение: den * divmod(num, den, p) mod p == num
'''
inv, _ = extended_gcd(den, p)
return num * inv
def lagrange_interpolate(x, x_s, y_s, p):
'''
Нахождение y по данному x, зная n других точек (x, y)
k точек определяют многочлен степени k-1 или ниже
'''
k = len(x_s)
assert k == len(set(x_s)), "точки должны быть различны"
def MUL(vals): # MUL -- произведение аргументов
accum = 1
for v in vals:
accum *= v
return accum
nums = []
dens = []
for i in range(k):
others = list(x_s)
cur = others.pop(i)
nums.append(MUL(x - o for o in others))
dens.append(MUL(cur - o for o in others))
den = MUL(dens)
num = sum([divmod(nums[i] * den * y_s[i] % p, dens[i], p)
for i in range(k)])
return (divmod(num, den, p) + p) % p
def recover_secret(shares, prime=_PRIME):
'''
Восстановление cекрета по точкам
(x,y) - точки многочлена
'''
x_s, y_s = zip(*shares)
return lagrange_interpolate(0, x_s, y_s, prime)
(*) За основу благодарю Jonathan Street
Настала пора подвести некоторые итоги.
6. Обсуждение и некоторые выводы
Частичные пароли были созданы для противостояния компрометированию пароля за один шаг в случае использования злоумышленником кейлоггинга или элементарного оффлайн-подглядывания. Частичные пароли могут дать пользователю некоторое время для смены пароля или блокировки аккаунта перед тем, как взломщик получит достаточную для уверенного взлома информацию. Данная модификация классической парольной аутентификации широко распространена в ряде стран мира, особенно в финансовой сфере, крайне чувствительной к потере аккаунта. В статье мы рассмотрели устройство и методы реализации pps, базовые типы атак на них. Несмотря на то, что частичные пароли хорошо справляются с атаками полного перебора и атаками полного восстановления пароля, но с условием перехвата запросов даже элементарные улучшения алгоритмов взлома показывают высокую эффективность против pps с используемыми на практике (крупными финансовыми компаниями) параметрами. Поэтому следует с большим вниманием относится к подбору параметров pps, чтобы сделать защиту действительно стойкой.
Частичные пароли являются простой и дешевой надстройкой над обычными паролями, которые в купе с другими этапами многофакторной аутентификации (такими, как использование дополнительного, полного пароля, привязка к номеру телефона, к почте, к другим аккаунтам, запрос некоторых данных о пользователе, использование биометрии и другие) позволяют эффективно бороться с утечкой пароля, что делает защиту аккаунта еще более сильной, а взлом аккаунта — бесперспективным занятием. Отдельной сферой, на мой взгляд, может стать использование pps в различных уличных терминалах и банкоматах в качестве защиты от считывания с них данных (скиммеры, вредоносное ПО, любопытствующих взгляд из-за плеча).
Вспомним полученные нами промежуточные результаты анализа pps. Во-первых, довольно неожиданно оказалось, что запросы с, возможно, повторяющимися позициями являются более устойчивыми к взлому*(внимание на постановку вопроса) почти во всем диапазоне числа перехватов запросов, чем решение без повторений (*в смысле полного восстановления пароля и получения известной комбинации в следующем запросе). Но все равно, запросы типа «введите 5,5,5 символы» звучат странно и уязвимо (особенно с малым алфавитом). В таких сценариях лучше делать запрос побольше и блокировать выбросы с большим числом повторов. Очевидно, не стоит менять запрос при каждой перезагрузке, ведь злоумышленник может выжидать имеющихся у него позиций. Само собой, стоит информировать пользователя о попытках входа.
Той части коммьюнити, которая заинтересовалась темой, предлагается расширить анализ pps, провести дополнительные выкладки и расчеты для случая B (они похожи на А) и, возможно, дополнить анализ другими типами атак. Возможно, "поиграть" с распределениями выпадения символов, как-нибудь обыграть проблему с самыми "проблемными" или легко угадываемыми позициями. Возможно, изменить или придумать новые форматы запросов. Безусловно, нужно дальнейший поиск правильных вопросов и грамотных ответов на них.
Общие рекомендации по подбору параметров pps (в принципе, универсальные): самое очевидное — выбор длинного и стойкого пароля, минимум - не qwerty и alex123, максимум - сгенерированного случайно. Размер запроса не стоит делать большим - таким образом быстрее набираются данные о полном пароле, но и не слишком малым - тогда повышается вероятность подбора pps. Таким образом, можно найти некоторый оптимальный размер запроса частичного пароля.
Однако есть и очевидные минусы pps: не каждый человек захочет запоминать пароль так, чтобы у него от зубов отскакивали все символы в каждой позиции. Не все смогут его запомнить, а постоянное черчение таблички с паролем и подписанными номерами букв во многом убивает саму идею такого технического решения, как и бумажка с паролем в записной книжке. Кроме того, хоть решение дешевое и, в определенном смысле, эффективное, все же не стоит использовать его как единственное средство защиты, а позаботиться о комплексной безопасности аккаунта. Хорошая новость в том, что все большее число крупных компаний вводит принудительную многофакторную аутентификацию или хотя бы выпускают поучительные брошюры о цифровой гигиене. Будем надеяться, что новости о крупных утечках аккаунтов все реже будут нас беспокоить. Было бы хорошо сделать все, что зависит от нас, как от пользователей, для защиты наших данных, не жалея нескольких, может быть, десятков секунд при регистрации и входе на свою страничку. Остальное — остается на совести компании.
Спасибо всем, кто проявил интерес к данной статье. Надеюсь, что информация, изложенная мною, была полезной. До новых встреч!
Источники:
Mourouzis, Theodosis & Wojcik, Marcin & Komninos, Nikos. (2016). On The Security Evaluation of Partial Password Implementations.
Aspinall, David & Just, Mike. (2013). «Give Me Letters 2, 3 and 6!»: Partial Password Implementations and Attacks. 7859. 126-143. 10.1007/978-3-642-39884-1_11.
Adams, Anne & Sasse, Angela & Lunt, Peter. (1999). Making Passwords Secure and Usable. 10.1007/978-1-4471-3601-9_1.