Предисловие
Вы когда-нибудь задумывались, что произойдет, если вы потеряете свою кредитную или дебетовую карту, и кто-то ее найдет. Сможет ли этот человек снять наличные в банкомате, каким-то образом угадав ваш PIN-код? Более того, если бы вы были тем, кто находит чью-то карту, попытались бы вы угадать PIN-код и рискнули получить легкие деньги? Конечно, ответ на оба вопроса должен быть «нет». Эта работа не касается второго вопроса, это вопрос личной этики. При этом я пытаюсь ответить на первый вопрос.
Вся информация, использованная для этой работы, является общедоступной и может быть свободно найдена в Интернете. Остальное - это математика и программирование, поэтому мы можем чему-то научиться и повеселиться. Я не раскрываю секретов. Более того, цель (и окончательный вывод) этой работы - продемонстрировать, что алгоритмы ПИН-кода по- прежнему достаточно сильны, чтобы обеспечить достаточную безопасность. Все мы знаем, что технологии - не слабое место.
В этой работе анализируется один из наиболее распространенных алгоритмов PIN, VISA PVV, используемый многими банкоматными картами (кредитными и дебетовыми картами), и делается попытка выяснить, насколько устойчив к атакам с подборами PIN. Под «угадыванием» я не имею в виду выбор случайного ПИН-кода и попытку его использования в банкомате. Хорошо известно, что, как правило, нам дается три последовательных попытки ввести правильный PIN-код, если мы не будем использовать банкомат для сохранения карты. Поскольку ПИН-код VISA состоит из четырех цифр, легко сделать вывод, что вероятность случайного угадывания ПИН-кода составляет 3/10000 = 0,0003, что кажется достаточно низким, чтобы быть в безопасности; это означает, что вам нужно потерять свою карту более трех тысяч раз (или потерять более трех тысяч карт одновременно
до тех пор, пока не появится разумный шанс потерять деньги.
Под «угадыванием» я на самом деле имел в виду нарушение алгоритма ПИН-кода, чтобы с учетом любой карты вы могли сразу узнать соответствующий ПИН-код. Поэтому в этом документе изучается такая возможность, анализируется алгоритм и предлагается метод атаки. Наконец, мы даем инструмент, который реализует атаку, и представляем результаты о предполагаемой вероятности взлома системы. Обратите внимание, что до тех пор, пока другие алгоритмы, связанные с банковской безопасностью (другие форматы PIN-кодов, такие как IBM PIN или подписи проверки карты, такие как CVV или CVC), аналогичны VISA PIN, такой же анализ может быть проведен с почти такими же результатами и выводами.
Алгоритм VISA PVV
Одним из наиболее распространенных алгоритмов PIN-кода является значение проверки PIN-кода VISA (PVV). Клиенту выдается ПИН-код и карта с магнитной полосой. На магнитной полосе закодировано четырехзначное число, называемое PVV. Этот номер является криптографической подписью ПИН-кода и других данных, связанных с картой. Когда пользователь вводит свой PIN-код, банкомат считывает магнитную полосу, шифрует и отправляет всю эту информацию на центральный компьютер. Там пробный PVV вычисляется с использованием введенного клиентом ПИН-кода и информации о карте с помощью криптографического алгоритма. Пробный PVV сравнивается с PVV, хранящимся на карте, если они совпадают, центральный компьютер возвращает банкомат авторизации для транзакции. См. Подробнее.
Описание алгоритма PVV можно найти в двух документах, ссылки на которые приведены на предыдущей странице. Таким образом, он заключается в шифровании 8-байтовой (64-битной) строки данных, называемой преобразованным параметром безопасности (TSP), с помощью алгоритма DES (DEA) в режиме электронной кодовой книги (ECB) с использованием секретного 64-битного ключа. PVV получается из вывода процесса шифрования, который представляет собой 8-байтовую строку. Четыре цифры PVV (слева направо) соответствуют первым четырем десятичным цифрам (слева направо) выходных данных DES, если рассматривать их как строку из 16 шестнадцатеричных символов (16 x 4 бит = 64 бита). Если среди 16 шестнадцатеричных символов нет четырех десятичных цифр, то PVV завершается, беря (слева направо) недесятичные символы и переводя их в десятичную форму с помощью преобразования A-> 0, B-> 1, C-> 2, D -> 3, E-> 4, F-> 5. Вот пример:
Выход из DES: 0FAB9CDEFFE7DCBA
PVV: 0975
Стратегия предотвращения десятичной дроби путем пропуска символов до тех пор, пока не будут найдены четыре десятичных цифры (что случается почти всегда, как мы увидим ниже), очень умна, поскольку позволяет избежать важной систематической ошибки в распределении цифр, которая, как было доказано, является фатальной. для других систем, хотя влияние на эту систему будет намного меньше. См. Также связанную проблему, не относящуюся к VISA PVV.
TSP, рассматриваемый как строка из 16 шестнадцатеричных (64-битных) символов, формируется (слева направо) из 11 крайних правых цифр PAN (номера карты), исключая последнюю цифру (контрольную цифру), одну цифру от 1 до 6. который выбирает секретный ключ шифрования и, наконец, четыре цифры ПИН-кода. Вот пример:
PAN: 1234 5678 9012 3445
Ключевой селектор: 1
PIN-код: 2468
TSP: 5678901234412468
Очевидно, проблема взлома VISA PIN состоит в том, чтобы найти секретный ключ шифрования для DES. Для этого используется метод перебора ключевого пространства. Обратите внимание, что это не единственный метод, можно попытаться найти слабое место в DEA, многие пытались, но этот старый стандарт все еще широко используется (теперь он заменен на AES и RSA). Это демонстрирует, что он достаточно надежен, так что грубая сила является единственным жизнеспособным методом (есть несколько более эффективных атак, но в нашем случае они непрактичны, краткое содержание см. В меморандуме LASEC, а подробные сведения см. В Biham & Shamir 1990, Biham & Shamir 1991, Мацуи 1993, Бихам и Бирюков 1994 и Хейс 2001 ).
Цифра переключателя ключа, скорее всего, была введена, чтобы скрыть возможность компрометации ключа. В этом случае им просто нужно выпустить новые карты, используя другой ключевой селектор. Старые карты можно заменить новыми или просто банкомат может прозрачно записать новый PVV (соответствующий новому ключу и сохраняющий тот же PIN-код) в следующий раз, когда клиент будет использовать свою карту. В целях повышения безопасности всех пользователей следует попросить изменить свои ПИН-коды, однако банку будет неудобно объяснять причину, поэтому очень вероятно, что они не будут делать такой запрос.
Готовимся к атаке
Атака методом грубой силы заключается в шифровании TSP с известным PVV с использованием всех возможных ключей шифрования и сравнении каждого полученного PVV с известным PVV. Когда совпадение найдено, у нас есть ключ-кандидат. Но сколько ключей нам нужно попробовать? Как мы уже говорили выше, длина ключа составляет 64 бита, это означает, что нам нужно попробовать 2 ^ 64 ключа. Однако это не так. Фактически только 56 битов эффективны в ключах DES, потому что один бит (наименее значимый) каждого октета исторически зарезервирован в качестве контрольной суммы для других; на практике эти 8 бит (по одному на каждый из 8 октетов) игнорируются.
Следовательно, пространство ключей DES состоит из 2 ^ 56 ключей. Если мы попробуем все эти ключи, найдем ли мы одно и только одно совпадение, соответствующее секретному ключу банка? Конечно нет. Мы получим много совпадающих ключей. Это связано с тем, что PVV составляет лишь небольшую часть (четверть) вывода DES. Кроме того, PVV вырождается, потому что некоторые цифры (между 0 и 5 после последней, если смотреть слева направо, цифра между 6 и 9) могут происходить из десятичной цифры или из десятичной шестнадцатеричной цифры вывода DES. Таким образом, многие ключи будут давать вывод DES, который дает такое же соответствие PVV.
Тогда что мы можем сделать, чтобы найти настоящий ключ среди этих других ложноположительных ключей? Просто нам нужно зашифровать второй другой TSP, также с известным PVV, но используя только ключи-кандидаты, которые дали положительное совпадение с первой парой TSP-PVV. Однако нет никакой гарантии, что мы больше не получим много ложных срабатываний вместе с истинным ключом. Если это так, нам понадобится третья пара TSP-PVV, повторите процесс и так далее.
Прежде чем начать атаку, мы должны знать, сколько пар TSP-PVV нам понадобится. Для этого мы должны вычислить вероятность того, что случайный вывод DES случайно даст совпадающий PVV. Есть несколько способов вычислить это число, и здесь я воспользуюсь простым для понимания подходом, который требует некоторого опыта в математике вероятностей.
Вероятность всегда можно рассматривать как отношение благоприятных случаев к возможным случаям. В нашей задаче количество возможных случаев определяется перестановкой 16 элементов (шестнадцатеричных цифр от 0 до F) в группу из 16 из них (16 шестнадцатеричных цифр вывода DES). Это равно 16 ^ 16 ~ 1,8 * 10 ^ 19, что, конечно, совпадает с 2 ^ 64 (разные числа из 64 бит). Этот набор чисел можно разделить на пять категорий:
Давайте посчитаем, сколько номеров попадает в каждую категорию. Если мы пометим 16 шестнадцатеричных цифр вывода DES как от X 1 до X 16, то мы можем пометить первые четыре десятичных цифры любого заданного числа первой категории как X i , X j , X k и X l . Количество различных комбинаций с этим профилем определяется произведением 6 i-1 * 10 * 6 j-i-1 * 10 * 6 k-j-1 * 10 * 6 lk-1 * 10 * 16 16-lгде 6 - это количество возможных цифр от A до F, 10 - это варианты цифр от 0 до 9, а 16 - варианты цифр от 0 до F. Теперь общее количество в первой категории просто дается суммированием этого продукта по i, j, k, l от 1 до 16, но с i <j <k <l. Если вы делаете некоторые математические работы вы увидите на жилу продукта 10 4 /6 с суммированием по г от 4 до 16 (я-1) * (I-2) * (I-3) * 6 i- 4 * 16 16-я ~ 1,8 * 10 19 .
Аналогично количество случаев во второй категории определяется суммированием по i, j, k от 1 до 16 с i <j <k продукта 6 i-1 * 10 * 6 j-i-1 * 10 * 6 kj- 1 * 10 * 6 16-k, которое можно вычислить как 16! / (3! * (16-13)!) * 10 3 * 6 13 = 16 * 15 * 14 / (3 * 2) * 10 3 * 6 13 = 56 * 10 4 * 6 13 ~ 7,3 * 10 15 . Аналогично для третьей категории у нас есть суммирование по i, j от 1 до 16 с i <j от 6 i-1 * 10 * 6 j-i-1 * 10 * 6 16-j, что равно 16! / (2! * (16-14)!) * 102 * 6 14 = 2 * 10 3 * 6 15 ~ 9,4 * 10 14 . Опять же, для четвертой категории у нас есть суммирование по i от 1 до 16 из 6 i-1 * 10 * 6 16-i = 160 * 6 15 ~ 7,5 * 10 13 . И, наконец, количество случаев в пятой категории определяется перестановкой шести элементов (цифры от A до F) в группе из 16, то есть 6 16 ~ 2,8 * 10 12 .
Надеюсь, вы следовали расчетам до этого момента, самая сложная часть сделана. Теперь в качестве доказательства того, что все правильно, вы можете просуммировать количество случаев в 5 категориях и увидеть, что оно равно общему количеству возможных случаев, которое мы вычислили ранее. Выполняйте операции с 64-битными числами или ошибки округления (для чисел с плавающей запятой) или переполнения (для целых чисел) не позволят получить точный результат.
До сих пор мы подсчитали количество возможных случаев в каждой из пяти категорий, но вместо этого мы заинтересованы в получении количества благоприятных случаев. Последнее очень легко вывести из первого, поскольку это просто фиксирует комбинацию четырех десятичных цифр (или требуемых шестнадцатеричных цифр, если нет четырех десятичных цифр) PVV вместо того, чтобы позволить им освободиться. На практике это означает превращение 10 в приведенной выше формуле в 1 и необходимое количество 6 в 1, если нет четырех десятичных цифр. То есть мы должны разделить первый результат на 10 4 , второй на 10 3 * 6, третий на 10 2 * 6 2 , четвертый на 10 * 6 3 и пятый на 6 4 . Тогда количество благоприятных случаев в пяти категориях составляет примерно 1,8 * 10 15 , 1,2 * 10 12 , 2,6 * 10 11 , 3,5 * 10 10 , 2,2 * 10 9 соответственно.
Теперь мы можем узнать, какова вероятность того, что результат DES случайно совпадет с PVV. Нам просто нужно сложить пять чисел благоприятных случаев и разделить их на общее количество возможных случаев. Делая это, мы получаем, что вероятность очень приблизительно равна 0,0001 или одна из десяти тысяч. Странно ли такой округлый результат? Вовсе нет, просто взгляните на числа, которые мы вычислили выше. Первая категория на несколько порядков доминирует по количеству благоприятных и возможных случаев. Это довольно интуитивно понятно, так как кажется очевидным, что очень маловероятно, чтобы не было четырех десятичных цифр (10 шансов из 16 на цифру) среди 16 шестнадцатеричных цифр. Ранее мы видели, что соотношение между количеством возможных и благоприятных случаев в первой категории было делением на 10 ^ 4, отсюда и наш результат p = 0,0001.
Нашей целью для всех этих вычислений было выяснить, сколько пар TSP-PVV нам нужно для успешной атаки методом грубой силы. Теперь мы можем вычислить ожидаемое количество ложных срабатываний при первом поиске: это будет количество попыток, умноженное на вероятность одного случайного ложного срабатывания, то есть t * p, где t = 2 ^ 56, размер ключа пространство. Это составляет примерно 7,2 * 10 ^ 12, довольно большое число. Ожидаемое количество ложных срабатываний во втором поиске (ограниченном положительными ключами, найденными в первом поиске) будет (t * p) * p, для третьего поиска будет ((t * p) * p) * p и скоро. Таким образом, для n поисков ожидаемое количество ложных срабатываний будет t * p ^ n.
Мы можем получить количество поисков, необходимое для ожидания только одного ложного срабатывания, выражая уравнение t * p ^ n = 1 и решая для n. Таким образом, n равно логарифму 1 / t по основанию p, что по свойствам логарифмов дает n = log (1 / t) / log (p) ~ 4,2. Поскольку мы не можем выполнить дробный поиск, удобно округлить это число. Следовательно, каково ожидаемое количество ложных срабатываний, если мы выполним пять поисков? Это t * p ^ 5 ~ 0,0007 или примерно 1 из 1400. Таким образом, использование пяти пар TSP-PVV безопасно для получения истинного секретного ключа без ложных срабатываний.
Атака
Когда мы узнаем, что нам нужно пять пар TSP-PVV, как их получить? Конечно, нам нужна хотя бы одна карта с известным PIN-кодом, и из-за характера алгоритма PVV это единственное, что нам нужно. Для других систем PIN, таких как IBM, нам потребуется пять карт, однако это не обязательно с алгоритмом VISA PVV. Нам просто нужно прочитать магнитную полосу, а затем четыре раза изменить PIN-код, но считывать карту после каждого изменения.
Чтобы получить PVV и селектор ключа шифрования, необходимо прочитать магнитную полосу карты. Вы можете купить коммерческий считыватель магнитных полос или сделать его самостоятельно, следуя инструкциям, приведенным на предыдущей странице, и ссылкам на них. Когда у вас есть читатель, посмотрите это описание стандартных магнитных дорожек, чтобы узнать, как получить PVV из считанных данных. В этом документе говорится, что поле PVV на дорожках 1 и 2 состоит из пяти символов, но на самом деле истинное значение PVV состоит из последних четырех цифр. Первая из пяти цифр - это ключ выбора. Я видел только карты со значением 1 в этой цифре, что соответствует стандарту, и секретный ключ никогда не скомпрометирован (и поэтому им не нужно было переходить на другой ключ, изменяя селектор).
Я сделал простую программу на языке C, getpvvkey.c , для выполнения атаки. Он состоит из цикла, в котором проверяются все возможные ключи для шифрования первого TSP, если полученный PVV совпадает с истинным PVV, выполняется попытка нового TSP и так далее, пока не будет обнаружено несоответствие, в этом случае ключ отбрасывается и создается новый. выполняется попытка, или пять производных PVV совпадают с соответствующими истинными PVV, и в этом случае мы можем предположить, что получили секретный ключ банка, однако цикл продолжается до тех пор, пока он не исчерпает пространство ключей. Это делается для того, чтобы убедиться, что мы находим истинный ключ, потому что есть вероятность (хотя и очень низкая), что первый найденный ключ является ложным срабатыванием.
Ожидается, что программа будет завершена очень долго и минимизировать риски отключения электроэнергии, зависания компьютера и т. д., Время от времени она создает контрольные точки в файле getpvvkey.dat (точное время зависит от скорости компьютера, для самых быстрых компьютеров, которые сейчас используются, это около часа). По той же причине, если найден положительный ключ, он записывается в файл getpvvkey.key. Программа отображает только одно сообщение в начале, начальная позиция взята из файла контрольной точки, если таковой имеется, после этого больше ничего не отображается.
Алгоритм DES является ключевым моментом в программе, поэтому очень важно оптимизировать его скорость. Я проверил несколько реализаций: libdes, SSLeay, OpenSSL, cryptlib, NSS, libgcrypt, катакомбы, libtomcrypt, cryptopp, UFC-склеп. Функции DES первых четырех основаны на том же коде Эрика Янга и являются наиболее эффективными (включая оптимизированный код ассемблера C и x86). Поэтому я выбрал libdes, которая была исходной реализацией, и сжал весь соответствующий код в файлах encrypt.c (версия C) и x86encrypt.s. (версия для ассемблера x86). Код немного изменен для достижения некоторых улучшений в атаке методом грубой силы: начальная перестановка является фиксированной общей крутизной в каждом шифровании TSP и, следовательно, может быть сделана только один раз в начале. Еще одно улучшение заключается в том, что я написал совершенно новую функцию setkey (я назвал ее nextkey), которая оптимальна для цикла грубой силы.
Чтобы программа заработала, вам просто нужно ввести в соответствующем месте пять TSP и их PVV, а затем скомпилировать ее. Я тестировал его только на платформах UNIX, используя для компиляции make-файл Makegetpvvkey (используйте команду «make -f Makegetpvvkey»). Он может компилироваться в других системах, но вам может потребоваться исправить некоторые вещи. Убедитесь, что определение типа long64 соответствует 64-битному целому числу. Принципиально нет зависимости от порядка байтов процессора. Я успешно скомпилировал и запустил его на Pentium-Linux, Alpha-Tru64, Mips-Irix и Sparc-Solaris. Если у вас нет и вы не хотите устанавливать Linux (вы не знаете, что вам не хватает ;-), у вас все еще есть выбор: запустить Linux на компакт-диске и использовать мою программу, см. Мою страницу с Linux без его установки. На самом деле у меня есть подготовленный ISO-образ Knoppix размером 700 МБ, который имеет исходный код, но не скомпилированный двоичный файл, потому что он бесполезен без действительных данных TSP / PVV. Тем не менее, он хорошо компилируется в этой среде. См. Инструкции на указанной странице.
После того, как вы нашли секретный ключ банка, если вы хотите найти PIN-код произвольной карты, вам просто нужно написать аналогичную программу (извините, я ее не написал, я слишком ленив, которая попробует все 10 ^ 4 PIN-кода путем создания соответствующего TSP, шифрования его (уже не) секретного ключа, получения PVV и сравнения его с PVV на магнитной полосе карты. Вы получите одно совпадение для настоящего ПИН-кода. Только один матч? Помните, что мы видели выше, у нас есть шанс 0,0001, что случайное шифрование соответствует PVV. Мы пробуем 10000 PIN-кодов (и, следовательно, TSP), поэтому в среднем мы ожидаем 10000 * 0,0001 = 1 ложное срабатывание.
Это очень интересный результат, он означает, что в среднем каждая карта имеет два действительных PIN-кода: PIN-код клиента и ожидаемое ложное срабатывание. Я называю это «ложным», но учтите, что до тех пор, пока он генерирует истинный PVV, это PIN-код, такой же действительный, как и пользовательский. Более того, невозможно узнать, что есть что, даже для банкомата; знает только покупатель. Даже если ложное срабатывание не было действительным в качестве ПИН-кода, у вас все равно есть три попытки в банкомате, в среднем достаточно. Поэтому вероятность, которую мы вычислили в начале этого документа о случайном угадывании PIN-кода, должна быть скорректирована. На самом деле это вдвое больше, т. Е. 0,0006 или один из более чем 1600, все еще безопасный низкий.
Результаты
Важно оптимизировать компиляцию программы и запускать ее на максимально быстром процессоре из-за длительного ожидаемого времени выполнения. Я обнаружил, что флаг оптимизации компилятора -O обеспечивает лучшую производительность, хотя некоторые улучшения были достигнуты добавлением флага -fomit-frame-pointer на Pentium-Linux, флага -spike на Alpha-Tru64, флаг -IPA на Mips-Irix и флаг -fast на Sparc-Solaris. Специальные флаги (-DDES_PTR -DDES_RISC1 -DDES_RISC2 -DDES_UNROLL -DASM) для кода DES также имеют общие преимущества. Все эти флаги уже были протестированы, и я выбрал лучшую комбинацию для каждого процессора (см. Make-файл), но вы можете попробовать настроить другие флаги.
Согласно моим тестам, лучшая производительность достигается с процессором AMD Athlon 1600 МГц, превышающим 3,4 миллиона ключей в секунду. Интересно, что он дает лучшие результаты, чем Intel Pentium IV 1800 МГц и 2000 МГц (см. Рисунки ниже, щелкните по ним, чтобы увеличить). Я считаю, что это происходит из-за некоторого насыщения ввода-вывода, безусловно, кеш-памяти или доступа к памяти, которых удается избежать процессору AMD (у которого половина кеш-памяти Pentium) или материнской плате, на которой он работает. На первом рисунке ниже вы можете видеть, что скорость прерывания DES всех процессоров имеет более или менее линейную зависимость от скорости процессора, за исключением двух Intel Pentium, о которых я упоминал ранее. Это логично, это означает, что при удвоении частоты процессора вы получите двукратное превышение скорости, но следите за эффектами насыщения, в данном случае лучше AMD Athlon 1600 МГц,
На втором рисунке мы можем более подробно увидеть то, что мы назвали бы внутренней мощностью прерывания DES процессора. Я получаю это значение, просто разделив скорость прерывания на скорость процессора, то есть мы получаем количество ключей DES, используемых в секунду и на МГц. Это показатель производительности процессора независимо от его скорости. Результаты показывают, что лучшим процессором для этой задачи является AMD Athlon, затем идет Alpha и очень близко идет Intel Pentium (за исключением высокоскоростных процессоров, которые работают очень плохо из-за эффекта насыщения). Далее идет процессор Mips и на последнем месте Sparc. Некоторые процессоры Alpha и Mips расположены в нижней части шкалы, потому что они являются ранними выпусками, не включая усовершенствования поздних версий. Обратите внимание, что я включил производительность процессоров x86 для кода C и ассемблера, поскольку есть большая разница. Кажется, что gcc не является хорошим генератором оптимизированного машинного кода, но, конечно, мы не знаем, улучшит ли ручная оптимизация кода ассемблера для других процессоров (Alpha, Mips, Sparc) их результаты по сравнению с собственными компиляторами C. (Я не использовал gcc для этих других платформ), как это происходит с процессором x86.
Наивысшая оценка, которую я получил при запуске моей программы, составляла приблизительно 3 423 922 ключа в секунду с использованием процессора AMD. Итак, сколько времени потребуется AMD, чтобы взломать VISA PIN? Это будет просто соотношение между размером ключевого пространства и скоростью попытки ключа, то есть 2 ^ 56 ключей / 3 423 922 ключа в секунду ~ 2,1 * 10 ^ 10 секунд ~ 244 тысячи дней ~ 667 лет. Это время завершения программы, но в среднем истинный секретный ключ будет найден вдвое быстрее. Использование коммерческих криптографических карт (таких как IBM PCI Cryptographic Coprocessor или XL-Crypt Encryption Accelerator) не очень помогает, они максимум в 2 раза быстрее моей топовой отметки, т.е. на поиск ключа в лучшем случае уйдет больше ста лет. Некоторое увеличение скорости может быть достигнуто (максимум вдвое) при использовании выделенного гигабитного VPN-бокса или подобного оборудования, что явно не предусмотрено производителем ;-)
Даже если вам удастся заставить сотню новейших процессоров AMD или Pentium работать параллельно, поиск ключа все равно займет более 3 лет (если они оснащены криптокартами, время может быть сокращено до менее двух лет или менее. более одного года в случае сотен гигабитных VPN-боксов). Ясно, что только дорогостоящее специализированное оборудование (доступное только для крупных организаций) или массовая совместная интернет-атака будет успешной в разумные сроки (обе вещи уже были сделаны). Это хорошие новости. Плохая новость заключается в том, что я намеренно немного солгал (вы, наверное, уже заметили): алгоритм VISA PVV позволяет использовать тройное шифрование DES (3-DES) с использованием 128-битного (всего 112 эффективного) ключа шифрования. Если 3-DES действительно используется системой PVV, вы все равно можете использовать ту же атаку, но вам потребуются четыре дополнительных пары TSP-PVV (с этим проблем нет), и для поиска потребуется больше, чем в 3 * 2 ^ 56 раз. ключ двойной длины. Забудь это.
Алгоритм PVV с тройным DES заключается в шифровании TSP с помощью левой половины ключа шифрования, затем он расшифровывает результат с помощью правой половины ключа и снова зашифровывает результат с помощью левой половины ключа. Обратите внимание, что если вы используете симметричный 128-битный ключ, то есть левая половина равна правой половине, вы получаете одно шифрование DES с одним 64-битным ключом. В этом случае алгоритм вырождается в тот, который я объяснил выше. Вот почему я проделал эту работу, потому что система PVV старая и, возможно, когда она была имплантирована, 3-DES был нежизнеспособен (из-за аппаратных ограничений) или казался чрезмерным (к тому времени) людям, ответственным за реализацию, так что возможно, некоторые банки используют алгоритм PVV с одним шифрованием DES.
Наконец, мы можем заключить, что алгоритм VISA PVV в его общей форме с использованием 3-DES довольно безопасен. Он может быть взломан только с использованием специально разработанного оборудования (что подразумевает огромную инверсию и, следовательно, не имеет смысла, см. Уэйнер и Винер.), что на много порядков превышает скорость шифрования новейших процессоров. Однако очевидный бесконечный экспоненциальный рост мощностей компьютеров, а также Интернет-сообщества заставляет думать, что система PVV может оказаться в реальной опасности в течение нескольких лет. Конечно, банки, использующие PVV с одним DES (если таковые имеются), уже подвергаются действительному риску совместной атаки через Интернет. Вы можете подумать, что это очень сложно координировать, я имею в виду убеждать людей, но подумайте о троянских и вирусных программах, и вы увидите, что продолжать это не так уж и сложно.
Вы когда-нибудь задумывались, что произойдет, если вы потеряете свою кредитную или дебетовую карту, и кто-то ее найдет. Сможет ли этот человек снять наличные в банкомате, каким-то образом угадав ваш PIN-код? Более того, если бы вы были тем, кто находит чью-то карту, попытались бы вы угадать PIN-код и рискнули получить легкие деньги? Конечно, ответ на оба вопроса должен быть «нет». Эта работа не касается второго вопроса, это вопрос личной этики. При этом я пытаюсь ответить на первый вопрос.
Вся информация, использованная для этой работы, является общедоступной и может быть свободно найдена в Интернете. Остальное - это математика и программирование, поэтому мы можем чему-то научиться и повеселиться. Я не раскрываю секретов. Более того, цель (и окончательный вывод) этой работы - продемонстрировать, что алгоритмы ПИН-кода по- прежнему достаточно сильны, чтобы обеспечить достаточную безопасность. Все мы знаем, что технологии - не слабое место.
В этой работе анализируется один из наиболее распространенных алгоритмов PIN, VISA PVV, используемый многими банкоматными картами (кредитными и дебетовыми картами), и делается попытка выяснить, насколько устойчив к атакам с подборами PIN. Под «угадыванием» я не имею в виду выбор случайного ПИН-кода и попытку его использования в банкомате. Хорошо известно, что, как правило, нам дается три последовательных попытки ввести правильный PIN-код, если мы не будем использовать банкомат для сохранения карты. Поскольку ПИН-код VISA состоит из четырех цифр, легко сделать вывод, что вероятность случайного угадывания ПИН-кода составляет 3/10000 = 0,0003, что кажется достаточно низким, чтобы быть в безопасности; это означает, что вам нужно потерять свою карту более трех тысяч раз (или потерять более трех тысяч карт одновременно
до тех пор, пока не появится разумный шанс потерять деньги.Под «угадыванием» я на самом деле имел в виду нарушение алгоритма ПИН-кода, чтобы с учетом любой карты вы могли сразу узнать соответствующий ПИН-код. Поэтому в этом документе изучается такая возможность, анализируется алгоритм и предлагается метод атаки. Наконец, мы даем инструмент, который реализует атаку, и представляем результаты о предполагаемой вероятности взлома системы. Обратите внимание, что до тех пор, пока другие алгоритмы, связанные с банковской безопасностью (другие форматы PIN-кодов, такие как IBM PIN или подписи проверки карты, такие как CVV или CVC), аналогичны VISA PIN, такой же анализ может быть проведен с почти такими же результатами и выводами.
Алгоритм VISA PVV
Одним из наиболее распространенных алгоритмов PIN-кода является значение проверки PIN-кода VISA (PVV). Клиенту выдается ПИН-код и карта с магнитной полосой. На магнитной полосе закодировано четырехзначное число, называемое PVV. Этот номер является криптографической подписью ПИН-кода и других данных, связанных с картой. Когда пользователь вводит свой PIN-код, банкомат считывает магнитную полосу, шифрует и отправляет всю эту информацию на центральный компьютер. Там пробный PVV вычисляется с использованием введенного клиентом ПИН-кода и информации о карте с помощью криптографического алгоритма. Пробный PVV сравнивается с PVV, хранящимся на карте, если они совпадают, центральный компьютер возвращает банкомат авторизации для транзакции. См. Подробнее.
Описание алгоритма PVV можно найти в двух документах, ссылки на которые приведены на предыдущей странице. Таким образом, он заключается в шифровании 8-байтовой (64-битной) строки данных, называемой преобразованным параметром безопасности (TSP), с помощью алгоритма DES (DEA) в режиме электронной кодовой книги (ECB) с использованием секретного 64-битного ключа. PVV получается из вывода процесса шифрования, который представляет собой 8-байтовую строку. Четыре цифры PVV (слева направо) соответствуют первым четырем десятичным цифрам (слева направо) выходных данных DES, если рассматривать их как строку из 16 шестнадцатеричных символов (16 x 4 бит = 64 бита). Если среди 16 шестнадцатеричных символов нет четырех десятичных цифр, то PVV завершается, беря (слева направо) недесятичные символы и переводя их в десятичную форму с помощью преобразования A-> 0, B-> 1, C-> 2, D -> 3, E-> 4, F-> 5. Вот пример:
Выход из DES: 0FAB9CDEFFE7DCBA
PVV: 0975
Стратегия предотвращения десятичной дроби путем пропуска символов до тех пор, пока не будут найдены четыре десятичных цифры (что случается почти всегда, как мы увидим ниже), очень умна, поскольку позволяет избежать важной систематической ошибки в распределении цифр, которая, как было доказано, является фатальной. для других систем, хотя влияние на эту систему будет намного меньше. См. Также связанную проблему, не относящуюся к VISA PVV.
TSP, рассматриваемый как строка из 16 шестнадцатеричных (64-битных) символов, формируется (слева направо) из 11 крайних правых цифр PAN (номера карты), исключая последнюю цифру (контрольную цифру), одну цифру от 1 до 6. который выбирает секретный ключ шифрования и, наконец, четыре цифры ПИН-кода. Вот пример:
PAN: 1234 5678 9012 3445
Ключевой селектор: 1
PIN-код: 2468
TSP: 5678901234412468
Очевидно, проблема взлома VISA PIN состоит в том, чтобы найти секретный ключ шифрования для DES. Для этого используется метод перебора ключевого пространства. Обратите внимание, что это не единственный метод, можно попытаться найти слабое место в DEA, многие пытались, но этот старый стандарт все еще широко используется (теперь он заменен на AES и RSA). Это демонстрирует, что он достаточно надежен, так что грубая сила является единственным жизнеспособным методом (есть несколько более эффективных атак, но в нашем случае они непрактичны, краткое содержание см. В меморандуме LASEC, а подробные сведения см. В Biham & Shamir 1990, Biham & Shamir 1991, Мацуи 1993, Бихам и Бирюков 1994 и Хейс 2001 ).
Цифра переключателя ключа, скорее всего, была введена, чтобы скрыть возможность компрометации ключа. В этом случае им просто нужно выпустить новые карты, используя другой ключевой селектор. Старые карты можно заменить новыми или просто банкомат может прозрачно записать новый PVV (соответствующий новому ключу и сохраняющий тот же PIN-код) в следующий раз, когда клиент будет использовать свою карту. В целях повышения безопасности всех пользователей следует попросить изменить свои ПИН-коды, однако банку будет неудобно объяснять причину, поэтому очень вероятно, что они не будут делать такой запрос.
Готовимся к атаке
Атака методом грубой силы заключается в шифровании TSP с известным PVV с использованием всех возможных ключей шифрования и сравнении каждого полученного PVV с известным PVV. Когда совпадение найдено, у нас есть ключ-кандидат. Но сколько ключей нам нужно попробовать? Как мы уже говорили выше, длина ключа составляет 64 бита, это означает, что нам нужно попробовать 2 ^ 64 ключа. Однако это не так. Фактически только 56 битов эффективны в ключах DES, потому что один бит (наименее значимый) каждого октета исторически зарезервирован в качестве контрольной суммы для других; на практике эти 8 бит (по одному на каждый из 8 октетов) игнорируются.
Следовательно, пространство ключей DES состоит из 2 ^ 56 ключей. Если мы попробуем все эти ключи, найдем ли мы одно и только одно совпадение, соответствующее секретному ключу банка? Конечно нет. Мы получим много совпадающих ключей. Это связано с тем, что PVV составляет лишь небольшую часть (четверть) вывода DES. Кроме того, PVV вырождается, потому что некоторые цифры (между 0 и 5 после последней, если смотреть слева направо, цифра между 6 и 9) могут происходить из десятичной цифры или из десятичной шестнадцатеричной цифры вывода DES. Таким образом, многие ключи будут давать вывод DES, который дает такое же соответствие PVV.
Тогда что мы можем сделать, чтобы найти настоящий ключ среди этих других ложноположительных ключей? Просто нам нужно зашифровать второй другой TSP, также с известным PVV, но используя только ключи-кандидаты, которые дали положительное совпадение с первой парой TSP-PVV. Однако нет никакой гарантии, что мы больше не получим много ложных срабатываний вместе с истинным ключом. Если это так, нам понадобится третья пара TSP-PVV, повторите процесс и так далее.
Прежде чем начать атаку, мы должны знать, сколько пар TSP-PVV нам понадобится. Для этого мы должны вычислить вероятность того, что случайный вывод DES случайно даст совпадающий PVV. Есть несколько способов вычислить это число, и здесь я воспользуюсь простым для понимания подходом, который требует некоторого опыта в математике вероятностей.
Вероятность всегда можно рассматривать как отношение благоприятных случаев к возможным случаям. В нашей задаче количество возможных случаев определяется перестановкой 16 элементов (шестнадцатеричных цифр от 0 до F) в группу из 16 из них (16 шестнадцатеричных цифр вывода DES). Это равно 16 ^ 16 ~ 1,8 * 10 ^ 19, что, конечно, совпадает с 2 ^ 64 (разные числа из 64 бит). Этот набор чисел можно разделить на пять категорий:
- Те, у которых не менее четырех десятичных цифр (от 0 до 9) среди 16 шестнадцатеричных цифр (от 0 до F) вывода DES.
- Те, у которых ровно три десятичных знака.
- Те, у которых ровно две десятичные цифры.
- Те, у которых только одна десятичная цифра.
- Те, у кого нет десятичных цифр (все от A до F).
Давайте посчитаем, сколько номеров попадает в каждую категорию. Если мы пометим 16 шестнадцатеричных цифр вывода DES как от X 1 до X 16, то мы можем пометить первые четыре десятичных цифры любого заданного числа первой категории как X i , X j , X k и X l . Количество различных комбинаций с этим профилем определяется произведением 6 i-1 * 10 * 6 j-i-1 * 10 * 6 k-j-1 * 10 * 6 lk-1 * 10 * 16 16-lгде 6 - это количество возможных цифр от A до F, 10 - это варианты цифр от 0 до 9, а 16 - варианты цифр от 0 до F. Теперь общее количество в первой категории просто дается суммированием этого продукта по i, j, k, l от 1 до 16, но с i <j <k <l. Если вы делаете некоторые математические работы вы увидите на жилу продукта 10 4 /6 с суммированием по г от 4 до 16 (я-1) * (I-2) * (I-3) * 6 i- 4 * 16 16-я ~ 1,8 * 10 19 .
Аналогично количество случаев во второй категории определяется суммированием по i, j, k от 1 до 16 с i <j <k продукта 6 i-1 * 10 * 6 j-i-1 * 10 * 6 kj- 1 * 10 * 6 16-k, которое можно вычислить как 16! / (3! * (16-13)!) * 10 3 * 6 13 = 16 * 15 * 14 / (3 * 2) * 10 3 * 6 13 = 56 * 10 4 * 6 13 ~ 7,3 * 10 15 . Аналогично для третьей категории у нас есть суммирование по i, j от 1 до 16 с i <j от 6 i-1 * 10 * 6 j-i-1 * 10 * 6 16-j, что равно 16! / (2! * (16-14)!) * 102 * 6 14 = 2 * 10 3 * 6 15 ~ 9,4 * 10 14 . Опять же, для четвертой категории у нас есть суммирование по i от 1 до 16 из 6 i-1 * 10 * 6 16-i = 160 * 6 15 ~ 7,5 * 10 13 . И, наконец, количество случаев в пятой категории определяется перестановкой шести элементов (цифры от A до F) в группе из 16, то есть 6 16 ~ 2,8 * 10 12 .
Надеюсь, вы следовали расчетам до этого момента, самая сложная часть сделана. Теперь в качестве доказательства того, что все правильно, вы можете просуммировать количество случаев в 5 категориях и увидеть, что оно равно общему количеству возможных случаев, которое мы вычислили ранее. Выполняйте операции с 64-битными числами или ошибки округления (для чисел с плавающей запятой) или переполнения (для целых чисел) не позволят получить точный результат.
До сих пор мы подсчитали количество возможных случаев в каждой из пяти категорий, но вместо этого мы заинтересованы в получении количества благоприятных случаев. Последнее очень легко вывести из первого, поскольку это просто фиксирует комбинацию четырех десятичных цифр (или требуемых шестнадцатеричных цифр, если нет четырех десятичных цифр) PVV вместо того, чтобы позволить им освободиться. На практике это означает превращение 10 в приведенной выше формуле в 1 и необходимое количество 6 в 1, если нет четырех десятичных цифр. То есть мы должны разделить первый результат на 10 4 , второй на 10 3 * 6, третий на 10 2 * 6 2 , четвертый на 10 * 6 3 и пятый на 6 4 . Тогда количество благоприятных случаев в пяти категориях составляет примерно 1,8 * 10 15 , 1,2 * 10 12 , 2,6 * 10 11 , 3,5 * 10 10 , 2,2 * 10 9 соответственно.
Теперь мы можем узнать, какова вероятность того, что результат DES случайно совпадет с PVV. Нам просто нужно сложить пять чисел благоприятных случаев и разделить их на общее количество возможных случаев. Делая это, мы получаем, что вероятность очень приблизительно равна 0,0001 или одна из десяти тысяч. Странно ли такой округлый результат? Вовсе нет, просто взгляните на числа, которые мы вычислили выше. Первая категория на несколько порядков доминирует по количеству благоприятных и возможных случаев. Это довольно интуитивно понятно, так как кажется очевидным, что очень маловероятно, чтобы не было четырех десятичных цифр (10 шансов из 16 на цифру) среди 16 шестнадцатеричных цифр. Ранее мы видели, что соотношение между количеством возможных и благоприятных случаев в первой категории было делением на 10 ^ 4, отсюда и наш результат p = 0,0001.
Нашей целью для всех этих вычислений было выяснить, сколько пар TSP-PVV нам нужно для успешной атаки методом грубой силы. Теперь мы можем вычислить ожидаемое количество ложных срабатываний при первом поиске: это будет количество попыток, умноженное на вероятность одного случайного ложного срабатывания, то есть t * p, где t = 2 ^ 56, размер ключа пространство. Это составляет примерно 7,2 * 10 ^ 12, довольно большое число. Ожидаемое количество ложных срабатываний во втором поиске (ограниченном положительными ключами, найденными в первом поиске) будет (t * p) * p, для третьего поиска будет ((t * p) * p) * p и скоро. Таким образом, для n поисков ожидаемое количество ложных срабатываний будет t * p ^ n.
Мы можем получить количество поисков, необходимое для ожидания только одного ложного срабатывания, выражая уравнение t * p ^ n = 1 и решая для n. Таким образом, n равно логарифму 1 / t по основанию p, что по свойствам логарифмов дает n = log (1 / t) / log (p) ~ 4,2. Поскольку мы не можем выполнить дробный поиск, удобно округлить это число. Следовательно, каково ожидаемое количество ложных срабатываний, если мы выполним пять поисков? Это t * p ^ 5 ~ 0,0007 или примерно 1 из 1400. Таким образом, использование пяти пар TSP-PVV безопасно для получения истинного секретного ключа без ложных срабатываний.
Атака
Когда мы узнаем, что нам нужно пять пар TSP-PVV, как их получить? Конечно, нам нужна хотя бы одна карта с известным PIN-кодом, и из-за характера алгоритма PVV это единственное, что нам нужно. Для других систем PIN, таких как IBM, нам потребуется пять карт, однако это не обязательно с алгоритмом VISA PVV. Нам просто нужно прочитать магнитную полосу, а затем четыре раза изменить PIN-код, но считывать карту после каждого изменения.
Чтобы получить PVV и селектор ключа шифрования, необходимо прочитать магнитную полосу карты. Вы можете купить коммерческий считыватель магнитных полос или сделать его самостоятельно, следуя инструкциям, приведенным на предыдущей странице, и ссылкам на них. Когда у вас есть читатель, посмотрите это описание стандартных магнитных дорожек, чтобы узнать, как получить PVV из считанных данных. В этом документе говорится, что поле PVV на дорожках 1 и 2 состоит из пяти символов, но на самом деле истинное значение PVV состоит из последних четырех цифр. Первая из пяти цифр - это ключ выбора. Я видел только карты со значением 1 в этой цифре, что соответствует стандарту, и секретный ключ никогда не скомпрометирован (и поэтому им не нужно было переходить на другой ключ, изменяя селектор).
Я сделал простую программу на языке C, getpvvkey.c , для выполнения атаки. Он состоит из цикла, в котором проверяются все возможные ключи для шифрования первого TSP, если полученный PVV совпадает с истинным PVV, выполняется попытка нового TSP и так далее, пока не будет обнаружено несоответствие, в этом случае ключ отбрасывается и создается новый. выполняется попытка, или пять производных PVV совпадают с соответствующими истинными PVV, и в этом случае мы можем предположить, что получили секретный ключ банка, однако цикл продолжается до тех пор, пока он не исчерпает пространство ключей. Это делается для того, чтобы убедиться, что мы находим истинный ключ, потому что есть вероятность (хотя и очень низкая), что первый найденный ключ является ложным срабатыванием.
Ожидается, что программа будет завершена очень долго и минимизировать риски отключения электроэнергии, зависания компьютера и т. д., Время от времени она создает контрольные точки в файле getpvvkey.dat (точное время зависит от скорости компьютера, для самых быстрых компьютеров, которые сейчас используются, это около часа). По той же причине, если найден положительный ключ, он записывается в файл getpvvkey.key. Программа отображает только одно сообщение в начале, начальная позиция взята из файла контрольной точки, если таковой имеется, после этого больше ничего не отображается.
Алгоритм DES является ключевым моментом в программе, поэтому очень важно оптимизировать его скорость. Я проверил несколько реализаций: libdes, SSLeay, OpenSSL, cryptlib, NSS, libgcrypt, катакомбы, libtomcrypt, cryptopp, UFC-склеп. Функции DES первых четырех основаны на том же коде Эрика Янга и являются наиболее эффективными (включая оптимизированный код ассемблера C и x86). Поэтому я выбрал libdes, которая была исходной реализацией, и сжал весь соответствующий код в файлах encrypt.c (версия C) и x86encrypt.s. (версия для ассемблера x86). Код немного изменен для достижения некоторых улучшений в атаке методом грубой силы: начальная перестановка является фиксированной общей крутизной в каждом шифровании TSP и, следовательно, может быть сделана только один раз в начале. Еще одно улучшение заключается в том, что я написал совершенно новую функцию setkey (я назвал ее nextkey), которая оптимальна для цикла грубой силы.
Чтобы программа заработала, вам просто нужно ввести в соответствующем месте пять TSP и их PVV, а затем скомпилировать ее. Я тестировал его только на платформах UNIX, используя для компиляции make-файл Makegetpvvkey (используйте команду «make -f Makegetpvvkey»). Он может компилироваться в других системах, но вам может потребоваться исправить некоторые вещи. Убедитесь, что определение типа long64 соответствует 64-битному целому числу. Принципиально нет зависимости от порядка байтов процессора. Я успешно скомпилировал и запустил его на Pentium-Linux, Alpha-Tru64, Mips-Irix и Sparc-Solaris. Если у вас нет и вы не хотите устанавливать Linux (вы не знаете, что вам не хватает ;-), у вас все еще есть выбор: запустить Linux на компакт-диске и использовать мою программу, см. Мою страницу с Linux без его установки. На самом деле у меня есть подготовленный ISO-образ Knoppix размером 700 МБ, который имеет исходный код, но не скомпилированный двоичный файл, потому что он бесполезен без действительных данных TSP / PVV. Тем не менее, он хорошо компилируется в этой среде. См. Инструкции на указанной странице.
После того, как вы нашли секретный ключ банка, если вы хотите найти PIN-код произвольной карты, вам просто нужно написать аналогичную программу (извините, я ее не написал, я слишком ленив
, которая попробует все 10 ^ 4 PIN-кода путем создания соответствующего TSP, шифрования его (уже не) секретного ключа, получения PVV и сравнения его с PVV на магнитной полосе карты. Вы получите одно совпадение для настоящего ПИН-кода. Только один матч? Помните, что мы видели выше, у нас есть шанс 0,0001, что случайное шифрование соответствует PVV. Мы пробуем 10000 PIN-кодов (и, следовательно, TSP), поэтому в среднем мы ожидаем 10000 * 0,0001 = 1 ложное срабатывание.Это очень интересный результат, он означает, что в среднем каждая карта имеет два действительных PIN-кода: PIN-код клиента и ожидаемое ложное срабатывание. Я называю это «ложным», но учтите, что до тех пор, пока он генерирует истинный PVV, это PIN-код, такой же действительный, как и пользовательский. Более того, невозможно узнать, что есть что, даже для банкомата; знает только покупатель. Даже если ложное срабатывание не было действительным в качестве ПИН-кода, у вас все равно есть три попытки в банкомате, в среднем достаточно. Поэтому вероятность, которую мы вычислили в начале этого документа о случайном угадывании PIN-кода, должна быть скорректирована. На самом деле это вдвое больше, т. Е. 0,0006 или один из более чем 1600, все еще безопасный низкий.
Результаты
Важно оптимизировать компиляцию программы и запускать ее на максимально быстром процессоре из-за длительного ожидаемого времени выполнения. Я обнаружил, что флаг оптимизации компилятора -O обеспечивает лучшую производительность, хотя некоторые улучшения были достигнуты добавлением флага -fomit-frame-pointer на Pentium-Linux, флага -spike на Alpha-Tru64, флаг -IPA на Mips-Irix и флаг -fast на Sparc-Solaris. Специальные флаги (-DDES_PTR -DDES_RISC1 -DDES_RISC2 -DDES_UNROLL -DASM) для кода DES также имеют общие преимущества. Все эти флаги уже были протестированы, и я выбрал лучшую комбинацию для каждого процессора (см. Make-файл), но вы можете попробовать настроить другие флаги.
Согласно моим тестам, лучшая производительность достигается с процессором AMD Athlon 1600 МГц, превышающим 3,4 миллиона ключей в секунду. Интересно, что он дает лучшие результаты, чем Intel Pentium IV 1800 МГц и 2000 МГц (см. Рисунки ниже, щелкните по ним, чтобы увеличить). Я считаю, что это происходит из-за некоторого насыщения ввода-вывода, безусловно, кеш-памяти или доступа к памяти, которых удается избежать процессору AMD (у которого половина кеш-памяти Pentium) или материнской плате, на которой он работает. На первом рисунке ниже вы можете видеть, что скорость прерывания DES всех процессоров имеет более или менее линейную зависимость от скорости процессора, за исключением двух Intel Pentium, о которых я упоминал ранее. Это логично, это означает, что при удвоении частоты процессора вы получите двукратное превышение скорости, но следите за эффектами насыщения, в данном случае лучше AMD Athlon 1600 МГц,
На втором рисунке мы можем более подробно увидеть то, что мы назвали бы внутренней мощностью прерывания DES процессора. Я получаю это значение, просто разделив скорость прерывания на скорость процессора, то есть мы получаем количество ключей DES, используемых в секунду и на МГц. Это показатель производительности процессора независимо от его скорости. Результаты показывают, что лучшим процессором для этой задачи является AMD Athlon, затем идет Alpha и очень близко идет Intel Pentium (за исключением высокоскоростных процессоров, которые работают очень плохо из-за эффекта насыщения). Далее идет процессор Mips и на последнем месте Sparc. Некоторые процессоры Alpha и Mips расположены в нижней части шкалы, потому что они являются ранними выпусками, не включая усовершенствования поздних версий. Обратите внимание, что я включил производительность процессоров x86 для кода C и ассемблера, поскольку есть большая разница. Кажется, что gcc не является хорошим генератором оптимизированного машинного кода, но, конечно, мы не знаем, улучшит ли ручная оптимизация кода ассемблера для других процессоров (Alpha, Mips, Sparc) их результаты по сравнению с собственными компиляторами C. (Я не использовал gcc для этих других платформ), как это происходит с процессором x86.
Наивысшая оценка, которую я получил при запуске моей программы, составляла приблизительно 3 423 922 ключа в секунду с использованием процессора AMD. Итак, сколько времени потребуется AMD, чтобы взломать VISA PIN? Это будет просто соотношение между размером ключевого пространства и скоростью попытки ключа, то есть 2 ^ 56 ключей / 3 423 922 ключа в секунду ~ 2,1 * 10 ^ 10 секунд ~ 244 тысячи дней ~ 667 лет. Это время завершения программы, но в среднем истинный секретный ключ будет найден вдвое быстрее. Использование коммерческих криптографических карт (таких как IBM PCI Cryptographic Coprocessor или XL-Crypt Encryption Accelerator) не очень помогает, они максимум в 2 раза быстрее моей топовой отметки, т.е. на поиск ключа в лучшем случае уйдет больше ста лет. Некоторое увеличение скорости может быть достигнуто (максимум вдвое) при использовании выделенного гигабитного VPN-бокса или подобного оборудования, что явно не предусмотрено производителем ;-)
Даже если вам удастся заставить сотню новейших процессоров AMD или Pentium работать параллельно, поиск ключа все равно займет более 3 лет (если они оснащены криптокартами, время может быть сокращено до менее двух лет или менее. более одного года в случае сотен гигабитных VPN-боксов). Ясно, что только дорогостоящее специализированное оборудование (доступное только для крупных организаций) или массовая совместная интернет-атака будет успешной в разумные сроки (обе вещи уже были сделаны). Это хорошие новости. Плохая новость заключается в том, что я намеренно немного солгал (вы, наверное, уже заметили): алгоритм VISA PVV позволяет использовать тройное шифрование DES (3-DES) с использованием 128-битного (всего 112 эффективного) ключа шифрования. Если 3-DES действительно используется системой PVV, вы все равно можете использовать ту же атаку, но вам потребуются четыре дополнительных пары TSP-PVV (с этим проблем нет), и для поиска потребуется больше, чем в 3 * 2 ^ 56 раз. ключ двойной длины. Забудь это.
Алгоритм PVV с тройным DES заключается в шифровании TSP с помощью левой половины ключа шифрования, затем он расшифровывает результат с помощью правой половины ключа и снова зашифровывает результат с помощью левой половины ключа. Обратите внимание, что если вы используете симметричный 128-битный ключ, то есть левая половина равна правой половине, вы получаете одно шифрование DES с одним 64-битным ключом. В этом случае алгоритм вырождается в тот, который я объяснил выше. Вот почему я проделал эту работу, потому что система PVV старая и, возможно, когда она была имплантирована, 3-DES был нежизнеспособен (из-за аппаратных ограничений) или казался чрезмерным (к тому времени) людям, ответственным за реализацию, так что возможно, некоторые банки используют алгоритм PVV с одним шифрованием DES.
Наконец, мы можем заключить, что алгоритм VISA PVV в его общей форме с использованием 3-DES довольно безопасен. Он может быть взломан только с использованием специально разработанного оборудования (что подразумевает огромную инверсию и, следовательно, не имеет смысла, см. Уэйнер и Винер.), что на много порядков превышает скорость шифрования новейших процессоров. Однако очевидный бесконечный экспоненциальный рост мощностей компьютеров, а также Интернет-сообщества заставляет думать, что система PVV может оказаться в реальной опасности в течение нескольких лет. Конечно, банки, использующие PVV с одним DES (если таковые имеются), уже подвергаются действительному риску совместной атаки через Интернет. Вы можете подумать, что это очень сложно координировать, я имею в виду убеждать людей, но подумайте о троянских и вирусных программах, и вы увидите, что продолжать это не так уж и сложно.
