Преодолевая VISA PIN
Jul 02, 2008 в банковской сфере и EFTPoS
Ниже приводится статья я обнаружил недавно. Это один из наиболее полных описаний PIN Контрольная стоимость (PVV) взлома.
I thought I would replicate it here for my local reference.
В комментарии были сделаны в отношении грамматики использовались в первоначальном тексте, я уже исправлены некоторые очевидные ошибки, в то время как поддержание связи с исходного материала.
http://69.46.26.132/ ~ biggold1/fastget2you/tutorial.php
--- Исходный текст ----
Предисловие
Вы когда-нибудь чудо, что произойдет, если вы потеряете вашей кредитной или дебетовой карты, и кто-то находит его. Будет ли этот человек иметь возможность снимать наличные деньги из банкоматов гадать, каким-то образом, ваш PIN? Кроме того, если вы были, кто считает кого-то карты бы вы попробуйте угадать PIN и принимать шанс получить легких денег? Конечно, ответ на оба вопроса должны быть "нет". Эта работа не касается второго вопроса, это вопрос личной этики. При этом я пытаюсь ответить на первый вопрос.
Все информация используемый для этой работы государственных и можно свободно найти в Интернете. Остальное идет математики и программирования, таким образом, мы можем узнать что-нибудь и улыбнемся. Я выявить никаких секретов. Кроме того, цель (и окончательное завершение) этой работы заключается в том, чтобы продемонстрировать, что PIN алгоритмов все еще достаточно сильны, чтобы обеспечить достаточную безопасность. Мы все знаем, технология не является слабым звеном.
Эта работа анализирует один из самых распространенных PIN алгоритмы, VISA PVV, используемый многими банкомат карт (кредитных и дебетовых карточек) и пытается выяснить, каким является стойкой к PIN угадать нападений. Под "угадать" Я не имею в виду выбора случайных PIN и пытается ее в банкомате. Хорошо известно, что в целом мы с учетом трех последовательных судебных процессов ввести право PIN, если мы не банкомат держит карты. Как VISA PIN четыре цифры долго это легко сделать вывод, что вероятность случайных PIN угадать 3 / 10000 = 0.0003, кажется низкой, чтобы они были безопасными; это означает, что вы должны терять вашу карту более чем в три тысячи раз ( или потерять более трех тысяч карточек в то же время:) до тех пор, пока есть реальный шанс потерять деньги.
То, что я действительно подразумевается под "угадать" был разорвать PIN алгоритм так, что, учитывая любые карты вы можете сразу узнать, связанные PIN. Поэтому этот документ исследования, возможности, анализ алгоритмов и предлагается метод для нападения. Наконец мы даем инструмент, который осуществляет нападения и представить результаты, о предполагаемом шанс выйти из системы. Заметим, что до тех пор, пока другие банковские безопасности, связанных с алгоритмами (другие PIN форматов, таких, как IBM PIN или карточку подтверждения подписи, таких, как CVV и CVC) аналогичным VISA PIN, тот же анализ можно сделать приносит почти те же результаты и выводы.
Одна из наиболее распространенных PIN алгоритмов VISA PIN Контрольная стоимость (PVV). Клиент получает ПИН и магнитной полосы карты. Кодировка магнитной полосой состоит из четырех цифр, называемых PVV. Это число является криптографической подписи PIN и другие данные, связанные с картой. Когда пользователь вводит свой PIN банкомат считывает с магнитной полосой, шифрует и направляет всю эту информацию на центральный компьютер. Там суда PVV вычисляется с помощью клиента вступил PIN и карты с информацией криптографические алгоритмы. Судебное разбирательство PVV сравнивается с PVV хранится в карты, если они совпадают с центральным компьютером возвращается в банкомат для авторизации транзакции. См. более подробно.
Описание PVV алгоритма можно найти в двух документах, связанных в предыдущей странице. В целом она состоит в шифрования по 8 байт (64 бит), строка данных, называемый преобразовало Параметр безопасности (ОВЧ), с DES алгоритм (DEA), в Электронные Код книги режиме (ЕЦБ) с помощью тайного 64-битный ключ. PVV вытекает из результатов шифрования процесса, который представляет собой 8 байт строки. Эти четыре цифры PVV (слева направо) соответствуют первых четырех десятичных цифр (слева направо) на выходе из ДЕЗ, когда считается 16 шестнадцатеричных символов (16 х 4 бита = 64 бит) строку. Если нет Есть четыре десятичных цифр среди 16 шестнадцатеричных символов, а затем PVV завершен принято (слева направо), не десятичных знаков и decimalizing их с помощью преобразования-> 0, B-> 1, C-> 2, D -> 3, Е-> 4, F-> 5. Вот пример:
Результат от DES: 0FAB9CDEFFE7DCBA
PVV: 0975
Стратегия избежания decimalization на пропуск символов, до тех пор, пока четыре десятичных цифр можно найти (что произойдет, будет практически все время, как мы увидим ниже) очень умен, поскольку он позволяет избежать предвзятости важно в распределении цифр, которая была доказана быть смертельным для других систем, хотя влияние этой системы было бы гораздо меньше. См. также связанная с этим проблема не применяют для VISA PVV.
ОВЧ, видели, как 16 шестнадцатеричных символов (64 бит) строка, формируется (слева направо) с 11-правый цифры PAN (номер карточки), за исключением последней цифре (контрольная цифра), одна цифра от 1 до 6 , который выбирает тайным ключом шифрования и, наконец, четырех цифр PIN. Вот пример:
PAN: 1234 5678 9012 3445
Ключевые селектор: 1
PIN: 2468
ОВЧ: 5678901234412468
Очевидно, что проблема разрушения VISA PIN состоит в поисках тайного ключа для шифрования DES. Метод заключается в том, что делать грубую силу поисках ключа пространстве. Заметим, что это не единственный метод, можно попытаться найти недостатки в DEA, многие пытались, но это старый стандарт по-прежнему находится в широкое использование (в настоящее время заменен AES и RSA, однако). Это свидетельствует о его достаточно, чтобы грубая сила является единственным реальным способом (Есть некоторые лучше нападения, но не практическим, в нашем случае, для резюме см. LASEC памятки и грязные подробности см. Biham И Шамир 1990 году, Biham И Шамир 1991 году, Мацуи 1993 году Biham И Бирюков 1994 года и Heys 2001).
Ключевым селектор цифра была весьма вероятно, представляет для покрытия возможности одного из ключевых компромисс. В этом случае они просто выпустить новые карточки, используя еще один ключевой селектор. Пожилых карточками могут быть заменены новыми или просто банкомата может прозрачно писать новые PVV (в соответствии с новым ключом и сохранение того же ПИН-код) в следующий раз клиент использует его / ее карты. Для поколебать безопасность всех пользователей должно быть предложено изменить свой ПИН, однако было бы стыдно за банковские объяснить причину, так что весьма вероятно, они бы не сделать такой запрос.
Подготовка к нападению
Грубая сила атаки состоит в шифровании ОВЧ с известными PVV с использованием всех возможных ключей шифрования, и сравнить полученные каждым PVV с известными PVV. После матча находится у нас есть кандидат ключ. Но сколько ключей мы попробовать? Как мы уже говорили выше, ключевым является 64-битный долго, то это означает, что мы должны попытаться 2 ^ 64 ключей. Однако это не так. На самом деле только 56 бит являются эффективными в DES ключами, поскольку один бит (младший) из каждого октета была исторически защищены, как контрольная для других; на практике эти 8 бит (по одному для каждой из 8 октетов), игнорируются.
Поэтому DES ключом пространство состоит из 2 ^ 56 ключей. Если мы пытаемся все эти ключи, мы сможем найти один и только один матч, соответствующий банковский секретный ключ? Конечно, нет. Мы будем получать много, соответствующие клавиши. Это происходит потому, что PVV это лишь небольшая часть (одна четвертая) от DES производства. Кроме того PVV это перерос потому, что некоторые из цифр (между 0 и 5 после последнего, видели слева направо, между цифрой 6 и 9) может исходить от десятичных цифр или от decimalized шестнадцатеричных цифр DES производства. Таким образом, многие ключи будут производить DES вывод, который уступает тому же сопоставление PVV.
Тогда то, что мы можем сделать, чтобы найти реальные ключевым среди тех других позитивный ложные ключи? Просто мы для шифрования второго различных ОВЧ, а также с известными PVV, но используя только клавиши кандидатом, который дал позитивные соответствие с первого ОВЧ-PVV пара. Однако нет никакой гарантии, мы не будем получать снова много ложных срабатываний вместе с истинным ключом. Если это так, нам потребуется третий ОВЧ-PVV пара, повторите этот процесс и так далее.
Прежде чем мы начнем нашу атаку мы должны знать, сколько ОВЧ-PVV пар нам потребуется. Для этого нам надо вычислить вероятность случайного DES производства, в результате сопоставления PVV только случайно. Есть несколько способов вычислить это число, и здесь я буду использовать простой подход легко понять, но которая требует определенного фона в математике вероятности.
Вероятность всегда можно рассматривать как соотношение благоприятных случаев к возможным случаям. В нашей проблемой количество возможных случаев дается подстановки из 16 элементов (от 0 до F шестнадцатеричных цифр), в группе из 16 из них (16 шестнадцатеричных цифр DES выходных). Это определяется по 16 ^ 16 ~ 1,8 * 10 ^ 19, которая, разумеется совпадала с 2 ^ 64 (разных номеров из 64 бит). Этот набор номера могут быть разделены на пять категорий:
Те, по крайней мере четырех десятичных цифр (от 0 до 9) среди 16 шестнадцатеричных цифр (от 0 до F) от DES производства.
Те, кто именно только трех десятичных цифр.
Те, кто точно только двух десятичных цифр.
Те, кто точно только одно десятичных цифр.
Те, кто не десятичных цифр (все между А и F).
Давайте подсчитать, сколько номеров осени в каждой категории. Если мы этикетка 16 шестнадцатеричных цифр DES производства, как X1 на X16 тогда мы можем ярлык первых четырех десятичных цифр или иной номер первой категории, как Xi, XJ, XK и XL. Число различных комбинаций с этого профиля зависит от продукта 6 I-1 * 10 * 6j-I-1 * 10 * 6K-J-1 * 10 * 6 LK-1 * 10 * 1616-L, где 6 ' S поступает из числа возможностей для F цифры, в 10 из возможностей от 0 до 9 цифр, и 16 из возможностей от 0 до F цифры. Теперь общее число в первой категории просто уделять путем суммирования этого продукта за I, J, K, L от 1 до 16, но с I <J <K <Л. Если вы делаете некоторые математические работы вы увидите этот равна произведению 104 / 6 с суммированием за I от 4 до 16 (I-1) * (I-2) * (I-3) * 6i-4 * 16 16-я ~ 1,8 * 1019.
Аналогично число случаев, во второй категории предоставляется путем суммирования над I, J, K от 1 до 16 с I <J <К данному продукту 6i-1 * 10 * 6j-I-1 * 10 * 6K-J -1 * 10 * 616-K, которые вы можете работать это будет 16! / (3! * (16-13)!) * 103 * 6 13 = 16 * 15 * 14 / (3 * 2) * 103 * 613 = 56 * 104 * 613 ~ 7.3 * 1015. Аналогично для третьей категории мы суммирования над I, J от 1 до 16 с I <J 6 I-1 * 10 * 6j-I-1 * 10 * 616-J, который равен 16! / (2! * (16-14)!) * 102 * 614 = 2 * 103 * 615 ~ 9.4 * 1014. Опять же, для четвертой категории мы суммирования за I от 1 до 16 6i-1 * 10 * 616-I = 160 * 615 ~ 7,5 * 1013. И, наконец, сумма случаев, в пятой категории дается подстановки из шести элементов (М цифр с) в группу 16, то есть, 616 ~ 2.8 * 1012.
Я надеюсь, что вы выполнили расчеты до этого момента, трудно частью это делается. Теперь в качестве доказательства того, что все правильно вы можете сумма ряде случаев в 5 категориях и посмотреть, равно общее число возможных случаев мы рассчитаны прежде. У операций с использованием 64-битных чисел или округления (для поплавков), или переполнения (для чисел) ошибки не позволит вам получить точный результат.
До сих пор мы подсчитали число возможных случаев, в каждой из пяти категорий, но мы заинтересованы в получении ряда благоприятных случаях вместо. Это очень легко получить последний из бывших, как это только фиксация комбинация из четырех десятичных цифр (или требуется шестнадцатеричных цифр, если нет Есть четыре десятичных цифр) от PVV вместо давая им бесплатно. На практике это означает превращение в 10 в формуле выше на 1 и требуемую сумму в 6 в 1 в том случае, если нет Есть четыре десятичных цифр. Это означает, что мы должны делать первый результат на 104, второй 103 * 6, третий 102 * 62, четвертый на 10 * 63 и пятый 64. Тогда число благоприятных случаев в пяти категориях примерно 1,8 * 1015, 1.2 * 1012, 2.6 * 1011, 3.5 * 1010, 2.2 * 109, соответственно.
Теперь мы можем получить то, что вероятность для DES вывода на матч PVV случайно. Нам просто нужно добавить пять номеров благоприятных случаях и разделите его на общее число возможных случаев. При этом мы получаем, что вероятность очень приблизительно 0,0001 или один из десяти тысяч. Разве странно, это хорошо округлены результат? Вовсе нет, просто посмотрите на номера мы рассчитанных выше. К первой категории доминирует на несколько порядков число благоприятных и возможные случаи. Это скорее интуитивное, как представляется очевидным, что очень маловероятно, не имея четыре десятичных цифр (10 шансов из 16 цифр процентов) среди 16 шестнадцатеричных цифр. Мы видели ранее, что взаимосвязь между количеством возможных и выгодные дела в первой категории было разделение на 10 ^ 4, вот где наши результате P = 0.0001 приходит с.
Наша цель для всех этих расчетов состоит в том, чтобы выяснить, сколько ОВЧ-PVV парами нам необходимо для выполнения успешной атаку "грубой силой". Теперь мы можем вычислить ожидаемое число ложных срабатываний в первую поиска: он будет рядом судебных разбирательств раза вероятности для одной случайной ошибки, то есть Т * С, где Т = 2 ^ 56, размер ключа пространстве. Это составляет примерно 7.2 * 10 ^ 12, довольно большое количество. Ожидаемое число ложных срабатываний во второй поиска (только для позитивных ключей ознакомиться в первом поиска) будут (T * P) * P, на третий поиска будет ((T * P) * P) * P и так далее. Таким образом, для N поиски ожидаемого количества ложных срабатываний будет T * P ^ Н.
Мы можем получить ряд обысков необходимо ожидать лишь один ложноположительный выразить уравнением T * P ^ N = 1 и решения для Н. Так N равен логарифму в базе P 1 / T, которая по свойствам логарифмов он дает N = LOG (1 / T) / вход (С) ~ 4.2. Поскольку мы не можем сделать поиск дробно это удобно круглые этот номер. Поэтому то, что ожидаемое количество ложных срабатываний, если мы проводим пять обысков? Он T * P ^ 5 ~ 0,0007, или примерно 1 из 1400. Таким образом, используя пять ОВЧ-PVV пар является безопасным для получения истинного секретный ключ без каких-либо ложных срабатываний.
После того, как мы знаем, что нам нужно пять ОВЧ-PVV пар, как нам получить их? Конечно, нам нужно по крайней мере одну карточку с известными PIN, и в силу характера PVV алгоритм, это единственное, что нам нужно. С другой PIN систем, таких как IBM, нам потребуется пять карт, однако это не является необходимым с VISA PVV алгоритм. Нам надо просто читать магнитной полосой, а затем изменить PIN четыре раза, но чтение карты после каждого изменения.
Это необходимо для чтения магнитной полосы на карте, чтобы получить PVV и ключом шифрования селектор. Вы можете купить коммерческие магнитной полосой читателя или сделать одну себя следующие инструкции вы можете найти в предыдущей страницы и ссылки в них. Если у вас есть читатель рассматриваем это описание стандартных магнитных дорожек, чтобы узнать, как получить PVV с данными следующим образом. В этом документе PVV области в направлениях 1 и 2, считается пять символов давно, но на самом деле истинный PVV состоит из четырех последних цифр. Первый из пяти цифр является ключевым селектор. Я только видел карты со значением 1 в этой цифре, которая соответствует стандарту и с секретным ключом и не в компьютере (и, следовательно, они не должны перейти к другой ключевой изменения Selector).
Я сделал простую программу на С, getpvvkey.c, выполнять атаки. Она состоит из петель попробовать все возможные ключи для шифрования первого ОВЧ, если полученные PVV матчей верно PVV новых ОВЧ судом, и так далее до тех пор, пока существует несоответствие, и в этом случае ключ отбрасываются, а новое судом, или пяти, полученных PVVs матч соответствующие PVVs верно, и в этом случае мы можем предположить, мы получили банковские секретный ключ, однако цикл продолжается до тех пор, пока она истощает ключевым пространством. Это делается для обеспечения мы находим действительно ключевой, поскольку существует вероятность (хотя и очень низкий) первый ключевой обнаружили является ложным положительным.
Ожидается, программа займет очень много времени, чтобы закончить и свести к минимуму риск отключения электроэнергии, компьютерные вывешивать и т.д. это контрольно-пропускные пункты в файл getpvvkey.dat время от времени (точное время зависит от скорости на компьютере, это около одного часа для самых быстрых компьютеров в настоящее время использования). По той же причине, если позитивный ключ было написано в файле getpvvkey.key. Программа отображает только одно сообщение в начале, начальная позиция взята из контрольно-пропускной пункт файл, если таковые имеются, после этого больше ничего не отображается.
DES алгоритм является ключевым моментом в программе, поэтому очень важно оптимизировать его скорость. Я тестировал несколько реализаций: libdes, SSLeay, OpenSSL, cryptlib, NSS, libgcrypt, катакомбах, libtomcrypt, cryptopp, UFC-склепе. DES функции первые четыре основаны на тот же код, Eric Young, и то, которое осуществляется наилучшим (включает оптимизированный C и x86 код сборщика). Поэтому я выбрал libdes которая была оригинальной и осуществления всех соответствующих конденсированных код в файлы encrypt.c (C версия) и x86encrypt.s (x86 Версия ассемблера). Код немного изменен для достижения некоторых усовершенствований в атаку "грубой силой": первоначальный подстановки является фиксированной общей крутых в каждом ОВЧ шифрования, и поэтому можно сделать только один раз в начале. Еще одним усовершенствованием является то, что я написал совершенно новую функцию SetKey (я назвал его nextkey), которая является оптимальной для грубой силы петля.
Чтобы получить рабочую программу вы просто введите в соответствующем месте пять TSPs и их PVVs, а затем обобщить его. Я тестировал только на UNIX платформах, с использованием Makegetpvvkey Makefile для компиляции (используйте команду "Make-F Makegetpvvkey"). Он может составить от других систем, но вы, возможно, потребуется исправить некоторые вещи. Будьте уверены, что определение типа long64 соответствует 64-битное целое. В принципе нет никакой зависимости от порядка байтов в процессор. Я успешно собран и запустить его на Pentium-Linux, Альфа-Tru64, архитектуры Mips-Irix и Sparc-Solaris. Если у вас нет и не хотите, чтобы установить Linux (вы не знаете, что вам не хватает ;-) вас еще есть выбор для запуска Linux на CD и использовать мою программу, см. мою страницу Linux, не устанавливая ее.
После того как вы нашли секретные банковские ключа, если вы хотите найти PIN от произвольного карточка вам просто нужно написать аналогичную программу (жаль я не написан он, я слишком ленив:), что бы попытаться все 10 ^ 4-коды путем создания соответствующей ОВЧ, зашифровать его с (не более) секретный ключ, вытекающих PVV и сравнив его с PVV на магнитной полосе карты. Вы получите один матч за истинную PIN. Лишь один матч? Помните, что мы видели выше, у нас есть шанс на 0,0001, что случайное шифрование матчах PVV. Мы стараемся 10000-Пен (и, следовательно, TSPs), таким образом, мы ожидаем, 10000 * 0,0001 = 1 ложноположительный в среднем.
Это очень интересный результат, это означает, что в среднем каждая карточка имеет два действительных коды: код клиента, и ожидается, ложноположительный. Слово это "ложные", но отмечают, что до тех пор, как он создает справедливо PVV это PIN столь же актуальными, как один клиент. Кроме того, нет возможности узнать, которая, которые, даже для банкомата, только клиент знает. Даже если ложноположительный были не действительны, как PIN, вы еще три судебных процесса в банкомате в любом случае, достаточно в среднем. Поэтому вероятность мы рассчитывается в начале этого документа о случайном догадываться о PIN должна быть исправлена. На самом деле оно в два раза превышает стоимость, то есть, это 0,0006 или один из более чем 1600 год, по-прежнему безопасно низким.
Результаты
Важно, чтобы оптимизировать компиляцию программы и запустить ее в возможном быстрый процессор из-за долгого времени ожидается запуск. Я обнаружил, что компилятор оптимизации флаг-O получает лучшую производительность, мысли некоторое улучшение достигается добавлением-fomit-кадр-указатель флаг на Pentium-Linux, то-флаг на пика Альфа-Tru64, флаг-МПА от архитектуры Mips-Irix и скорость флаг на Sparc-Solaris. Специальные флаги (-DDES_PTR-DDES_RISC1-DDES_RISC2-DDES_UNROLL-DASM) для DES код, как преимущества, как хорошо. Все эти флаги уже были опробованы и я выбрал наилучшее сочетание для каждого процессора (см. Makefile), но вы можете попробовать для тонкой настройки других флагов.
По моим испытаниям лучшей производительности достигается с AMD Athlon 1600 МГц процессор, превышающей 3.4 million ключей в секунду. Интересно оно получает лучшие результаты, чем Intel Pentium IV 1800 МГц и 2000 МГц (см. диаграммы ниже, нажмите на них, чтобы увеличить). Я считаю, это объясняется некоторыми I / O насыщения, несомненно, кэш-память или доступа, что процессор AMD (которая в два раза кэш Pentium) или материнская плата, в которой она работает, удается избежать. На первом рисунке вы можете видеть, что DES нарушение скорости процессоров все более или менее линейную связь с процессором скорости, за исключением двух Intel Pentium я упоминал ранее. Это логично, это означает, что для двойной процессор скорости вы будете получать двойное нарушение скорости, но и следить за насыщения последствия, в этом случае лучше AMD Athlon 1600 МГц, который будет еще дешевле, чем Intel Pentium 1800 МГц или 2000 МГц.
Во второй диаграмме мы можем увидеть более подробно, что мы хотели бы призвать собственного DES перерыв мощности процессора. Я получаю этот параметр просто разделить перерыва скорости на скорость процессора, то есть, мы получим число DES ключами пытались секунду, и процентам МГц. Это показатель эффективности работы процессора типа, независимо от его скорости. Полученные результаты показывают, что наилучший процессор для выполнения этой задачи является AMD Athlon, а затем приходит "Альфа" и очень близки после того, как он это Intel Pentium (за исключением высокой скорости те, которые выполняют очень плохо из-за насыщения эффект). Далее идет архитектуры Mips процессор, и в последнее место Sparc. Некоторые альфа-и архитектуры Mips процессор находится в нижней части шкалы, поскольку они являются ранние релизы не включая усовершенствований поздней версии. Имейте в виду, что я включала выполнение x86 процессоры для C и ассемблер код, так как существует большая разница. Похоже, что GCC является не очень хорошая генератор оптимизированный машинный код, но мы, разумеется, не знают ли ручная оптимизация кода ассемблера для других процессоров (Alpha, MIPS, Sparc) позволит повысить свои результаты по сравнению с родной компилятор C (Я не использую GCC для других платформ), как это происходит с процессором x86.
Обновление
Вот статья, где эти методы могут быть использованы.