Опрокидывающиеся VISA PIN

Среда, 2 июля, 2008 @ 12:38 AM | Банковские и EFTPoS

Ниже приводится статья, я обнаружил недавно. Это одно из наиболее полных описаний PIN Контрольная стоимость (PVV) взлома.

Я думал, я хотел бы повторить это здесь, на моем местного ведения.

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

http://69.46.26.132/ ~ biggold1/fastget2you/tutorial. PHP

--- Подлинный текст ----

Предисловие
Вы когда-нибудь интересно, что произойдет, если вы потеряете вашей кредитной или дебетовой карты, а кто-то находит. Если это лицо может получать наличные деньги из банкоматов гадать, каким-то образом, ваш пин-код? Кроме того, если вы были, кто считает, кто-то карточку бы вы попробуйте угадать, PIN и шанс получить легкие деньги? Конечно, ответ на оба вопроса будет "нет". Эта работа не касается второго вопроса, это вопрос личной этики. При этом я постараюсь ответить на первый вопрос.

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

Данная работа анализирует один из самых распространенных PIN алгоритмов, VISA PVV, используется во многих банкоматах карт (кредитных и дебетовых карт), и пытается выяснить, насколько устойчивы является PIN угадать нападений. Под "угадать" Я не имею в виду, выбирая случайные PIN и пытается ее в банкомате. Хорошо известно, что в целом мы с учетом трех последовательных попыток ввода право PIN, если мы не банкомат держит карты. Как VISA PIN четыре цифры долго можно легко сделать вывод, что вероятность случайного PIN угадали 3 / 10000 = 0.0003, кажется низким, чтобы он был безопасным, оно означает, что вам надо потерять карту более чем в три тысячи раз ( или потерять больше, чем три тысячи карт одновременно:) до тех пор, пока существует разумная вероятность потерять деньги.

То, что я действительно подразумевается под "угадать" был разорвать PIN алгоритм так что при любой картой Вы можете сразу узнать, связанные PIN. Поэтому данный документ исследования, возможности, анализ алгоритмов и предлагается метод для нападения. В заключение мы даем инструмент, который реализует атаку и представить результаты, о предполагаемом шанс выйти из системы. Заметим, что до тех пор, пока другой банковской безопасности, связанных с алгоритмами (другие PIN форматов, таких как IBM PIN или карточки проверка подписей, такие, как CVV или CVC) аналогичны VISA PIN, тот же анализ может быть сделано приносит почти те же результаты и выводы.

VISA PVV алгоритм

Одна из наиболее распространенных PIN алгоритмов VISA PIN Контрольная стоимость (PVV). Клиент получает ПИН и магнитной полосы карты. Закодированные в магнитной полосы состоит из четырех цифр, называемых PVV. Это число является криптографической подписи PIN и другие данные, связанные с картой. Когда пользователь вводит свой PIN банкомат считывает с магнитной полосой, шифрует и направляет всю эту информацию на центральный компьютер. Там суда PVV вычисляется с использованием клиент вступил PIN и карты с криптографических алгоритмов. Судебное разбирательство PVV сравнивается с PVV, хранящихся в карте, если они соответствуют центральный компьютер возвращается в банкомате для авторизации транзакции. См. более подробно.

Описание PVV алгоритма можно найти в двух документах, связанных в предыдущей странице. В целом он состоит в шифрование 8 байт (64 бит) строку данных, называется Преобразованные безопасности Параметр (TSP), с DES алгоритм (DEA) в электронных книг кодекса режима (ЕЦБ) с помощью тайного ключа 64 бит. PVV вытекает из результатов шифрования процесса, который представляет собой 8 байт строки. Четыре цифры PVV (слева направо) соответствует первых четырех десятичных цифр (слева направо) от выхода из DES, если его рассматривать в качестве 16 шестнадцатеричных символов (16 х 4 = битные 64-битные) строку. Если нет Есть четыре десятичных цифр из 16 шестнадцатеричных символов затем PVV завершена приняты (слева направо), не десятичное символов и decimalizing них с помощью преобразования-> 0, B-> 1, C-> 2, D -> 3, E-> 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. Метод заключается в том, что делать грубую силу поисках ключа пространстве. Заметим, что это не единственный метод, можно попытаться найти недостатки в ДЭА, многие пытались, но это старый стандарт по-прежнему в широком использовании (в настоящее время заменен AES и RSA, однако). Это свидетельствует о его достаточно, чтобы грубая сила является единственным реальным способом (Есть несколько атак, но лучше не практично в нашем случае, в резюме см. LASEC памятки и грязные подробности см. Biham И Шамире 1990, Biham И Шамире 1991 году, Мацуи 1993, Biham И Бирюков 1994 и Heys 2001).

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

Подготовка к нападению

Грубая сила атаки состоит в шифровании ОВЧ с известными 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, то можно ярлык первых четырех десятичных цифр любой номер первой категории, как Си, 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-й, который равен 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 пара нужно иметь успешный грубой силы нападения. Теперь мы можем вычислить ожидаемое количество ложных срабатываний на первом поиска: оно будет рядом судебных разбирательств раза вероятности для одной случайной ложноположительный, т.е. T * P, где Т = 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) / LOG (P) ~ 4.2. Поскольку мы не можем сделать поиск дробно это удобно раунд этого числа. Поэтому то, что ожидаемое количество ложных срабатываний, если мы проводим пять обысков? Это T * P ^ 5 ~ 0.0007, или примерно 1 из 1400. Таким образом, используя пять ОВЧ-PVV пара безопасно получить истинное секретный ключ, не ложных срабатываний.

The attack

После того, как мы знаем, что нам нужно пять ОВЧ-PVV пара, как мы получаем их? Конечно, нам нужно по крайней мере, одну карту с известным PIN, и в силу характера PVV алгоритм, это единственное, что нам нужно. С другой PIN систем, таких как IBM, нам потребуется пять карт, однако это не является необходимым с VISA PVV алгоритма. Нам просто нужно идти с магнитной полосой, а затем изменить PIN четыре раза, но чтение карты после каждого изменения.

Нужно читать магнитной полосе карты, чтобы получить PVV и ключа шифрования Selector. Вы можете купить коммерческий магнитной полосой читателя или сделать самостоятельно, выполнив инструкции вы найдете в предыдущей страницы и ссылки в нем. После того, как вы читателю увидеть это описание стандартных магнитных дорожек, чтобы узнать, как получить 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 функции первых четырех, основаны на тех же код Эрик Янг, и тот, который наиболее эффективны (включает оптимизированный C и ассемблере код x86). Таким образом, я выбрал libdes которая была оригинальной и осуществления всех соответствующих конденсированная код в файлы encrypt.c (C версия) и x86encrypt.s (x86 ассемблер версия). Код слегка изменен для достижения каких-либо улучшений в атаку "грубой силой: первоначальный перестановка является фиксированной общей крутые в каждом ОВЧ шифрования, и поэтому можно сделать только один раз в начале. Еще одно улучшение в том, что я написал совершенно новую функцию setkey (я назвал его nextkey), которая является оптимальной для грубой силы петли.

Чтобы получить рабочую программу вы должны набрать в соответствующем месте пять TSPs и их PVVs, а затем собрать его. Я тестировал только в UNIX платформ, с помощью Makefile Makegetpvvkey обобщить (используйте команду "Make-F Makegetpvvkey"). Он может составить от других систем, но вы, возможно, потребуется установить некоторые вещи. Будьте уверены, что определение типа long64 соответствует 64-битное целое. В принципе, нет зависимости от endianness от процессора. Я успешно обобщены и запустить его на 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 ложноположительный в среднем.

Это очень интересный результат, это означает, что, в среднем, каждая карта имеет два действительных коды: клиент PIN и ожидалось ложноположительный. Я назвал это "ложной", но отмечают, что до тех пор, как он создает истинную 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 млн. ключей в секунду. Интересно оно получает лучшие результаты, чем Intel Pentium IV 1800 МГц и 2000 МГц (см. диаграммы ниже, нажмите на них, чтобы увеличить). Я считаю, это связано с некоторыми I / O насыщения, то кэш-памяти или доступа, что процессор AMD (которая вдвое кэш Pentium) или материнская плата, в которой она работает, удается избежать. В первом рисунке вы можете увидеть, что DES нарушение скорости процессоров все более или менее линейной взаимосвязи с процессором скорости, за исключением двух Intel Pentium я упоминал ранее. Это логично, это означает, что за двойной процессор скорости вы получите двойной разрыв скорости, но следить за насыщение эффектов, в данном случае это лучше, AMD Athlon 1600 МГц, которые будут даже дешевле, чем Intel Pentium 1800 МГц или 2000 МГц.

На второй диаграмме можно видеть более подробно то, что мы бы назвали собственного DES-брейк мощность процессора. Я получаю это значение простого деления перерыва скорости на скорости процессора, то есть, мы получаем число DES ключами попытались в секунду и на МГц. Это показатель эффективности работы процессора типа, независимо от его скорости. Полученные результаты свидетельствуют о том, что лучший процессор для выполнения этой задачи является AMD Athlon, а затем приходит Alpha и очень близки после того, как его Intel Pentium (за исключением высокой скорости те, которые выполняют очень плохо из-за эффекта насыщения). Далее идет Mips процессор, и в последнем месте Sparc. Некоторые Alpha и Mips процессоры расположены в нижней части шкалы, поскольку они являются ранние релизы не включая увеличение конце версий. Имейте в виду, что я включала выполнение x86 процессоры для C и ассемблере код как есть большая разница. Кажется, что GCC является не очень хорошая генератора оптимизированный машинный код, но мы, разумеется, не знают ли ручной оптимизации кода ассемблера для других процессоров (Alpha, MIPS, Sparc) будет увеличить свои результаты по сравнению с родной компилятор C (я не использую GCC для этих других платформ), как это происходит с процессором x86.