Взлом банковских PIN-кодов с помощью игры «Мастермайнд»

файлы с подробными стратегиями взлома Mastermind и PIN-кодов можно скачать по адресу dsi.unive.it

Риккардо Фокарди (Riccardo Focardi), Фламиния Л. Луччио (Flaminia L. Luccio), Венецианский университет Ка Фоскари, "Взлом банковских PIN-кодов с помощью игры «Мастермайнд»", Конференция: Веселье с алгоритмами, 5-я Международная конференция FUN 2010, Искья, Италия, 2-4 июня 2010.

Директор банка был очень расстроен, заметив, как Джо, системный администратор, проводит свободное время за игрой в «Мастермайнд», старую, бесполезную игру 70-х годов. Он боролся с желанием сказать ему, как лучше провести свою жизнь, ограничившись лишь презрительным взглядом, которого точно не заметил. Неудивительно, что на следующий день директор, ошеломленный, упал на стул, прочитав в газете о крупном цифровом мошенничестве с банкоматами его банка, в результате которого команда хакеров со всего мира украла миллионы евро. В статье говорилось, что хакеры «играли с банковскими компьютерами, как в «Мастермайнд», и смогли раскрыть тысячи PIN-кодов пользователей во время часового обеденного перерыва. В тот самый момент, за секунду до того, как потерять сознание, он понял едва заметную улыбку на лице Джо накануне, когда тот тренировался в своей любимой игре — «Мастермайнд».

Введение
Игра «Мастермайнд» была изобретена в 1970 году Мордекаем Мейровицем, израильским почтальоном. В игру играют как в настольную игру между двумя игроками или как в игру для одного игрока между одним игроком и компьютером (в обоих случаях называемым, соответственно, взломщиком кода и создателем кода). Создатель кода выбирает линейную последовательность цветных фишек и прячет их за экраном. Допускаются дубликаты. Взломщик кода должен в разных попытках угадать как цвет, так и положение фишек. В ходе каждого испытания он чему-то учится и на основе этого принимает решение о следующей попытке: в частности, ответ, состоящий из черного колышка (который мы будем называть черным маркером), представляет собой правильную догадку о цвете и положении колышка (но маркер не указывает, какой из них правильный), ответ, состоящий из белого колышка (называемого белым маркером), представляет собой только правильную догадку о цвете, но в неправильном положении.

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

Хотя эта настройка кажется безопасной, за последние годы обнаружено несколько атак на уровне API на эти HSM. Атаки работают, исходя из предположения, что злоумышленник является инсайдером, получившим доступ к HSM на каком-либо банковском коммутаторе и выполняющим сложные последовательности вызовов API, из которых он может определить значение PIN-кода. Существует множество примеров таких атак, один из которых, который мы рассматриваем в этой статье, — это так называемая атака dectab. Интуитивно, при проверке PIN-кода API принимает на вход различные параметры, некоторые из которых являются общедоступными. Одним из этих параметров является таблица десятичной классификации, которая отображает промежуточное шестнадцатеричное представление PIN-кода пользователя в десятичное число. Манипулируя некоторой информацией, например, изменяя способ десятичной обработки чисел и наблюдая, влияет ли это на результат проверки, злоумышленник может определить, какие цифры PIN-кода являются фактическими. Положение угадываемых цифр PIN-кода восстанавливается путем манипулирования другим общедоступным параметром, т. е. значением PIN-кода. Объединив всю эту информацию, злоумышленник может восстановить весь PIN-код.

Наш вклад
В этой статье мы показываем, что атаки с использованием десятичной обработки чисел можно рассматривать как расширенную игру «Мастер разума». Каждый вызов API представляет собой испытание для взломщика кода, а возвращаемое значение API — это соответствующий ответ создателя кода. Одновременное манипулирование таблицей Dectab и набором символов аналогично запросу у создателя кода раскрыть цвет и положение одной цифры PIN-кода, если его предположение верно, подобно тому, что происходит с черным маркером в игре Mastermind. Модификация только таблицы Dectab, напротив, соответствует запросу наличия определенных цифр в PIN-коде, аналогично белому маркеру в игре. Мы формализуем вышеизложенную интуицию, показав, как взлом PIN-кода и Mastermind можно рассматривать как примеры более общей проблемы или игры.

Эта расширенная проблема предлагает новый способ улучшения атаки с использованием таблицы Dectab. Идея состоит в том, чтобы позволить игроку (т. е., злоумышленнику) запрашивать наборы цветов (т. е., цифр), а не только отдельные цвета, для каждой позиции. Это, по сути, может быть реализовано в контексте взлома PIN-кода путем модификации нескольких записей таблицы Dectab. С этой целью мы разрабатываем компьютерную программу, которая оптимизирует хорошо известную методику, представленную Кнутом (Knuth) в для стандартной игры Mastermind, и расширяем ее на нашу задачу. Мы проводим эксперименты, показывающие, что программа почти так же точна, как современные решатели Mastermind, но быстрее, поскольку она способна вычислять стратегии для случаев, которые еще не были рассмотрены. Что еще более интересно, та же самая стратегия решения адаптирована к задаче взлома PIN-кода, доказывая вышеупомянутую новую границу среднего числа вызовов API, необходимых в декта-атаках.

Результаты экспериментов
Мы разработали программу, которая является оптимизированным расширением оригинальной программы для Mastermind, представленной Кнутом. Она работает следующим образом:
1. Перебирает все возможные варианты предположений. Для каждого предположения вычисляет количество «выживших» решений, связанных с каждым возможным исходом предположения.
2. Выбирает предположение из предыдущего шага, которое минимизирует максимальное количество выживших решений среди всех возможных исходов, и выполняет предположение:
(а) Для каждого возможного исхода сохраняет соответствующие выжившие решения и рекурсивно вызывает этот алгоритм;
(б) останавливается, когда количество выживших решений равно 0 (невозможный исход) или 1 (угадана правильная последовательность).

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

Большинство вычислений заняло несколько секунд, другие — несколько минут, и мы также смогли найти новые верхние границы минимального числа ходов для неизвестных значений. Идея Кнута не определяет оптимальную стратегию, однако она очень близка к оптимальной. Мы смогли эффективно определить границы для 2 цветов и 9 и 10 фишек, а также для 3 цветов и 8 фишек, и перечислить точную последовательность ходов, которые необходимо выполнить.

Затем применили тот же самый алгоритм к задаче взлома PIN-кода. В этом случае использование множеств с более чем 2 элементами в предположениях не улучшило решения. С множествами размером не более 2х алгоритм работает довольно хорошо, мы смогли нашли стратегию со средним числом вызовов 14,484 вместо 16,145. Это улучшение основано на идее расширенных предположений, в которых наборы значений могут быть запрошены путем одновременного изменения их отображения в таблице определения одной и той же величины.

Эта идея нова и расширяет стратегию атаки. В специальных вызовах API «только для декодирования», где смещение остается неизменным, чтобы немедленно обнаруживать, когда цифра появляется в качестве одной из промежуточных цифр PIN-кода, эти вызовы обобщаются на множества путем выполнения предположений (после вычитания смещения) вида (S, . . . , S ), где S содержит цифры, наличие которых необходимо проверить. Также нашли новую границу для PIN-кодов длиной 5, дающую в среднем 20,88 вызовов. Стоит отметить, что наши результаты близки к оптимальному разбиению решений на почти сбалансированное бинарное дерево. Фактически, легко вычислить, что это даст среднее количество вызовов 13,362 и 16,689 для PIN-кодов длиной 4 и 5 соответственно.

Все файлы с подробными стратегиями взлома Mastermind и PIN-кодов можно скачать по адресу dsi.unive.it/focardi/MM PIN

Заключение
В данной работе рассмотрены две довольно разные задачи: Mastermind и взлом PIN-кода. Их можно рассматривать как примеры расширенной игры Mastermind, в которой предположения могут содержать наборы фишек. Реализовали оптимизированную версию классического решателя для Mastermind и применили ее к взлому PIN-кода, улучшив известную оценку количества вызовов API. Идея использования наборов в предположениях фактически подсказала новую стратегию атаки, которая уменьшает количество необходимых вызовов. Объединив «стандартные» атаки с этой новой стратегией, смогли уменьшить среднее количество вызовов с 16,145 до 14,484. Также нашли новую оценку для PIN-кодов длиной 5, дающую в среднем 20,88 вызовов. Оба средних случая близки к оптимуму. В качестве будущей работы мы намерены изучить расширение более сложных методов на условия взлома PIN-кода.

В заключение отметим, что мы хотели бы попросить директора банка, опубликовавшего наш реферат, и других серьезных людей быть более открытыми и никогда не считать что-либо бесполезным только потому, что это смешно: «Рано или поздно общество поймет, что определенные виды тяжелой работы на самом деле достойны восхищения, даже если они доставляют больше удовольствия, чем почти все остальное».

Эшли Шил (Ashley Sheil), Технологический университет Мюнстера, Германия, Дэвид Мэлоун (David Malone), Национальный университет Ирландии, "Угадывание PIN-кодов, по одному частичному PIN-коду за раз", Entropy, 24(9), сентябрь 2022.

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

11.12.2025

Комментарий:

Шнобелевская премия - 1998 - литература

За смелость, настойчивость изучения защитного пукания подростка, изящное литературное изложение своего опыта, Мара Сидоли удостоена Шнобелевской премии в области литературы за 1998 год и стала президентом Национальной ассоциации за прогресс в психоанализе
подробнее

Шнобелевская премия - 1996 - химия

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

Источник - пресса

Шнобель Процедура Пресса Анналы Архив Статьи Шнобелист