Предлагаю читателям «Хабрахабра» перевод статьи «How To Decrypt Magnetic Card Data With DUKPT».
Недавно мне было нужно расшифровать карточные данные из считывателя магнитных дорожек. Казалось бы, это просто. Беру ключ и выполняю определенный алгоритм расшифровки. Но не тут-то было.
Оказалось, мои считыватели используют схему известную как DUKPT (Derived Unique Key Per Transaction — Определение Уникального Ключа На Транзакцию). Идея этой схемы состоит в том, что для каждой транзакции (или в нашем случае для каждого проката карты) данные шифруются с использованием ключа вычисленного для отдельного проката карты.
Таким образом, чтобы расшифровать данные, которые были зашифрованы с использованием этой схемы, вы должны уметь вычислять ключ для отдельного проката карты. Процесс вычисления такого ключа (сессионного ключа) далеко не простой.
Процесс описан в документе ANSI X9.24 part 1. Однако документ стоит примерно $140. Бесплатную, легко-доступную документацию, описывающую этот процесс, трудно найти. Лучший ресурс, который мне удалось найти, тут; там довольно хорошее объяснение как вычисляется IPEK (Initial Pin Encryption Key — начальный ключ для вычисления ключей). К сожалению, это только часть полной схемы. В этом посте я попытаюсь всесторонне объяснить схему DUKPT.
BDK: Это сокращение от Base Derivation Key (базовый ключ алгоритма). Этот ключ известен только производителю и разработчику софта, взаимодействующего со сканером магнитных дорожек.
IPEK: Это сокращение от Initial Pin Encryption Key (начальный ключ для вычисления ключей). Этот ключ определяется из BDK. Этот ключ загружается на устройство производителем и используется для генерации будущих ключей. Компрометация IPEK не компрометирует BDK.
KSN: Это сокращение от Key Serial Number (Серийный номер ключа). KSN это комбинация серийного номера сканера магнитных дорожек и счетчика количества прокатов карты, которое было выполнена на устройстве.
BDK используется производителем для генерации IPEK, который загружается на устройство во время разработки. Устройство использует IPEK и KSN для вычисления сессионного ключа, которым шифруются данные читаемые с карты.
BDK требуется разработчикам софта для вычисления IPEK. Получив IPEK, они могут запросить KSN у устройства. IPEK и KSN используются для получения ключа на отдельную транзакцию/прокат карты. Имея эти ключи, разработчики могут расшифровать карточные данные.
Чтобы получить начальный ключ для вычисления ключей (IPEK), нам нужен базовый ключ алгоритма (BDK) и серийный номер ключа (KSN). IPEK определяется с помощью алгоритма TripleDES. TripleDES это простой алгоритм DES выполняемый в три прохода.
Алгоритм использует ключ длиной 24 байта. Используется алгоритм DES три раза сначала с ключом с 1-8 байт, затем 9-16 байт и, наконец, 17-24 байт отдельно за каждый проход.
TripleDES может использовать ключ длиной 16 байт, такой метод называется EDE3. Будут использоваться сначала байты 1-8, затем 9-16 и, снова, 1-8 эмитируя 24-х байтовый ключ.
Некоторые реализации TripleDES не могут автоматически использовать короткий ключ. Перед тем как это понять я потратил много времени пытаясь разобраться в чем проблема. Предположив что это особая реализация TripleDES я использовал эмитированный 24 байтовый ключ из 16 байтов.
После долгих мучений на меня снизошло попробовать взять первые 8 байт и добавить их в конец ключа перед тем, как передать его в TripleDES алгоритм. Это решило проблему.
IPEK состоит из двух 8-ми байтовых частей, которые получаются в результате двух отдельных проходов алгоритма TripleDES. Оба получаются с помощью шифрования старших 8 байт KSN с обнуленным счетчиком. Разница между левой и правой частями в том, что правая часть получается шифрованием KSN с помощью немного измененной версии BDK. Я опишу этот процесс ниже.
Предположим, имеется 16 байтовый BDK представленный шестнадцатеричной строкой «0123456789ABCDEFFEDCBA9876543210». Также имеем 10 байтовый KSN со счетчиком равным 8, представленный шестнадцатеричной строкой «FFFF9876543210E00008».
Получим BDK для шифрования левой части IPEK добавлением первых 8 байт в конец BDK, это будет следующий 24 байтовый ключ.
Если длина KSN не равна 10 байтам, то дополняем его до 10 байт шестнадцатеричной «F» (1111). Важно отметить, что IPEK является самым первым ключом на устройстве. Это значит, что мы вычисляем его со счетчиком в KSN равным 0. Чтобы получить KSN со счетчиком 0, мы накладываем на него маску шестнадцатеричным представлением которой является строка «FFFFFFFFFFFFFFE00000».
Замечательно. Теперь у нас есть нулевой KSN. Однако нам нужны старшие 8 байт KSN. Мы получаем их, сдвигая KSN вправо на 16 бит.
Отлично. Следующий шаг — TripleDES шифрование строки «FFFF9876543210E0» с помощью ключа BDK в 24 байт «0123456789ABCDEFFEDCBA98765432100123456789ABCDEF». Результатом этого шифрования будет левая часть IPEK.
Если вы помните, я упоминал что для получения правой часть будет использоваться немного измененная версия BDK. Таким образом, чтобы сделать это, нам нужно взять оригинальный 16 байтовый BDK «0123456789ABCDEFFEDCBA9876543210» и выполнить XOR по следующей маске «C0C0C0C000000000C0C0C0C000000000». Похоже это полностью произвольная маска, но увы, она необходима для получения верного IPEK.
Мы сделаем тоже самое, что делали с ключом для левой части, возьмем старшие 8 байт и добавим их в конец, получится следующий 24 байтовый ключ.
Далее возьмем старшие 8 байт KSN с нулевым счетчиком (который мы вычисляли ранее) и зашифруем его с помощью TripleDES ключом который только что вычислили. Это даст нам правый регистр IPEK, получаем следующий 16 байтовый IPEK (я разделил левую и правую части для ясности).
У нас есть IPEK. Далее нам нужно получить из IPEK уникальный ключ для отдельного проката карты (сессионный ключ). Чтобы получить его, используется некая подпрограмма, назовем ее черный ящик, целью которой является возврат отдельного сессионного ключа. Происходящее в черном ящике — пока не наша забота. Прямо сейчас мы посмотрим на вход этой подпрограммы.
Наш черный ящик имеет два входа. Один это ключ и второй — строка для шифрования. Строка представляет собой измененный KSN.
Если помните, младшие 21 бит KSN содержат счетчик количества прокатов карты на устройстве. Мы передадим модифицированный KSN в подпрограмму столько раз, сколько единиц в бинарном представлении счетчика. Ключ который передается с измененным KSN это IPEK на первой итерации, а на следующих итерациях это будет ключ полученный из черного ящика на предыдущей итерации.
Начнем с изменения KSN. Для начала мы возьмем младшие 8 байт KSN и обнулим значение счетчика в KSN. Это можно сделать с помощью маскирования KSN с использованием следующей маски.
Полученное значение мы будем использовать для вычисления каждого сообщения передаваемого в черный ящик. В нашем примере со счетчиком равным 8 мы должны передать в черный ящик двоичное представление числа 8 (1000). Для демонстрации предположим, что счетчик имеет более сложное значение 10 (1010).
Мы будем извлекать набор двоичных чисел из счетчика. В нашем случае для числа 10 (1010) будет два двоичных числа: 1000 и 0010. Вы уловили схему? Мы получаем набор чисел, представляющих каждую бинарную единицу числа 10.
Далее берем первое число и применяем операцию OR с KSN, у которого обнулен счетчик, как было показано ранее (заметим что шестнадцатеричное представление первого числа будет 0008).
Теперь передаем IPEK как ключ и только что модифицированный KSN в черный ящик. Черный ящик вернет новый ключ. Это первый сессионный ключ (представленный в шестнадцатеричном виде): «27f66d5244ff62e1aa6f6120edeb4280».
Далее повторим процесс со следующим двоичным числом, вычисленным ранее, 2 (0010). На этот раз, мы будем использовать первый сессионный ключ, который мы только что получили и вычислим новую модификацию KSN.
Для вычисления новой модификации KSN мы будем выполнять операцию OR с последней полученной модификацией: 9876543210E00008.
Теперь передадим наш новый ключ «27f66d5244ff62e1aa6f6120edeb4280» и новую модификацию KSN «9876543210E0000A» в черный ящик и получим другой будущий ключ, «6cf2500a22507c7cc776ceadc1e33014». Это сессионный ключ для нашего устройства со счетчиком 10.
Однако, наш настоящий счетчик был равен 8, а настоящий сессионный ключ «27F66D5244FF62E1AA6F6120EDEB4280» мы вычислили на первом этапе.
Последняя операция, которую мы должны проделать с полученным значением, конечное преобразование ключа, которым мы будем расшифровывать данные. Мы должны выполнить XOR ключа с маской «00000000000000FF00000000000000FF».
Это ключ, который требуется для расшифрования данных.
Чёрным ящиком я назвал алгоритм, который вычисляет сессионные ключи. Чёрный ящик принимает текущий сессионный ключ, который я обозначу current_sk, и модификацию KSN, обозначим ksn_mod.
Если в начале предположение что IPEK полученный выше был передан как current_sk, а ksn_mod был равен значению «9876543210E00008», которое мы вычислили выше.
Для начала нам нужно взять current_sk, получить старшие 8 байт и сдвинуть их на 64 бита вправо, получим «6AC292FAA1315B4D». Это можно получить с помощью битовой маски.
Здесь нам нужно сдвинуть это значение на 64 бита вправо, чтобы получить «6AC292FAA1315B4D». Назовем его left_key (выглядит как левая часть current_sk).
Далее получим 8 младших байт current_sk, с помощью маски.
Давайте назовем это значение (вы догадались) right_key. Далее возьмем right_key и выполним XOR с ksn_mod «9876543210E00008».
Это значение назовем message. Далее берем message и шифруем его с помощью DES (простой DES). Будем передавать в DES алгоритм message как данные, которые надо закриптовать, и left_key, как ключ которым надо зашифровать. Получится значение «2FE5D2833A3ED1BA». Теперь нужно выполнить XOR этого значения и right_key.
Это значение младшие 8 байт нашего сессионного ключа! Теперь нам надо повторить только что описанные операции с другими входными данными. На этот раз мы берем current_sk и выполняем XOR его с «C0C0C0C000000000C0C0C0C000000000». Насколько я могу судить это значение произвольно, но оно часть стандарта ANSI, так что вы просто должны поверить моим словам.
Если мы возьмем значение «AA02523AA1315B4D454A7363D7D5933A» и подставим его вместо current_sk в операцию, которая описана выше, мы получим «27F66D5244FF62E1». Это старшие 8 байт нашего сессионного ключа. Комбинируя их получим «27F66D5244FF62E1AA6F6120EDEB4280».
Надеюсь, я объяснил схему DUKPT и как она относится к эффективности сканеров магнитных дорожек. Жду исправления и вопросы в секции комментариев.
Недавно мне было нужно расшифровать карточные данные из считывателя магнитных дорожек. Казалось бы, это просто. Беру ключ и выполняю определенный алгоритм расшифровки. Но не тут-то было.
Оказалось, мои считыватели используют схему известную как DUKPT (Derived Unique Key Per Transaction — Определение Уникального Ключа На Транзакцию). Идея этой схемы состоит в том, что для каждой транзакции (или в нашем случае для каждого проката карты) данные шифруются с использованием ключа вычисленного для отдельного проката карты.
Таким образом, чтобы расшифровать данные, которые были зашифрованы с использованием этой схемы, вы должны уметь вычислять ключ для отдельного проката карты. Процесс вычисления такого ключа (сессионного ключа) далеко не простой.
Процесс описан в документе ANSI X9.24 part 1. Однако документ стоит примерно $140. Бесплатную, легко-доступную документацию, описывающую этот процесс, трудно найти. Лучший ресурс, который мне удалось найти, тут; там довольно хорошее объяснение как вычисляется IPEK (Initial Pin Encryption Key — начальный ключ для вычисления ключей). К сожалению, это только часть полной схемы. В этом посте я попытаюсь всесторонне объяснить схему DUKPT.
Определения
BDK: Это сокращение от Base Derivation Key (базовый ключ алгоритма). Этот ключ известен только производителю и разработчику софта, взаимодействующего со сканером магнитных дорожек.
IPEK: Это сокращение от Initial Pin Encryption Key (начальный ключ для вычисления ключей). Этот ключ определяется из BDK. Этот ключ загружается на устройство производителем и используется для генерации будущих ключей. Компрометация IPEK не компрометирует BDK.
KSN: Это сокращение от Key Serial Number (Серийный номер ключа). KSN это комбинация серийного номера сканера магнитных дорожек и счетчика количества прокатов карты, которое было выполнена на устройстве.
Как оно работает
BDK используется производителем для генерации IPEK, который загружается на устройство во время разработки. Устройство использует IPEK и KSN для вычисления сессионного ключа, которым шифруются данные читаемые с карты.
BDK требуется разработчикам софта для вычисления IPEK. Получив IPEK, они могут запросить KSN у устройства. IPEK и KSN используются для получения ключа на отдельную транзакцию/прокат карты. Имея эти ключи, разработчики могут расшифровать карточные данные.
Вычисление IPEK
Чтобы получить начальный ключ для вычисления ключей (IPEK), нам нужен базовый ключ алгоритма (BDK) и серийный номер ключа (KSN). IPEK определяется с помощью алгоритма TripleDES. TripleDES это простой алгоритм DES выполняемый в три прохода.
Алгоритм использует ключ длиной 24 байта. Используется алгоритм DES три раза сначала с ключом с 1-8 байт, затем 9-16 байт и, наконец, 17-24 байт отдельно за каждый проход.
TripleDES может использовать ключ длиной 16 байт, такой метод называется EDE3. Будут использоваться сначала байты 1-8, затем 9-16 и, снова, 1-8 эмитируя 24-х байтовый ключ.
Некоторые реализации TripleDES не могут автоматически использовать короткий ключ. Перед тем как это понять я потратил много времени пытаясь разобраться в чем проблема. Предположив что это особая реализация TripleDES я использовал эмитированный 24 байтовый ключ из 16 байтов.
После долгих мучений на меня снизошло попробовать взять первые 8 байт и добавить их в конец ключа перед тем, как передать его в TripleDES алгоритм. Это решило проблему.
Подробности
IPEK состоит из двух 8-ми байтовых частей, которые получаются в результате двух отдельных проходов алгоритма TripleDES. Оба получаются с помощью шифрования старших 8 байт KSN с обнуленным счетчиком. Разница между левой и правой частями в том, что правая часть получается шифрованием KSN с помощью немного измененной версии BDK. Я опишу этот процесс ниже.
Предположим, имеется 16 байтовый BDK представленный шестнадцатеричной строкой «0123456789ABCDEFFEDCBA9876543210». Также имеем 10 байтовый KSN со счетчиком равным 8, представленный шестнадцатеричной строкой «FFFF9876543210E00008».
Получим BDK для шифрования левой части IPEK добавлением первых 8 байт в конец BDK, это будет следующий 24 байтовый ключ.
0123456789ABCDEFFEDCBA98765432100123456789ABCDEFЕсли длина KSN не равна 10 байтам, то дополняем его до 10 байт шестнадцатеричной «F» (1111). Важно отметить, что IPEK является самым первым ключом на устройстве. Это значит, что мы вычисляем его со счетчиком в KSN равным 0. Чтобы получить KSN со счетчиком 0, мы накладываем на него маску шестнадцатеричным представлением которой является строка «FFFFFFFFFFFFFFE00000».
FFFF9876543210E00008
and FFFFFFFFFFFFFFE00000
= FFFF9876543210E00000
Замечательно. Теперь у нас есть нулевой KSN. Однако нам нужны старшие 8 байт KSN. Мы получаем их, сдвигая KSN вправо на 16 бит.
FFFF9876543210E00000 >> 16 = FFFF9876543210E0
Отлично. Следующий шаг — TripleDES шифрование строки «FFFF9876543210E0» с помощью ключа BDK в 24 байт «0123456789ABCDEFFEDCBA98765432100123456789ABCDEF». Результатом этого шифрования будет левая часть IPEK.
6AC292FAA1315B4D
Если вы помните, я упоминал что для получения правой часть будет использоваться немного измененная версия BDK. Таким образом, чтобы сделать это, нам нужно взять оригинальный 16 байтовый BDK «0123456789ABCDEFFEDCBA9876543210» и выполнить XOR по следующей маске «C0C0C0C000000000C0C0C0C000000000». Похоже это полностью произвольная маска, но увы, она необходима для получения верного IPEK.
0123456789ABCDEFFEDCBA9876543210
xor C0C0C0C000000000C0C0C0C000000000
= C1E385A789ABCDEF3E1C7A5876543210
Мы сделаем тоже самое, что делали с ключом для левой части, возьмем старшие 8 байт и добавим их в конец, получится следующий 24 байтовый ключ.
C1E385A789ABCDEF3E1C7A5876543210C1E385A789ABCDEF
Далее возьмем старшие 8 байт KSN с нулевым счетчиком (который мы вычисляли ранее) и зашифруем его с помощью TripleDES ключом который только что вычислили. Это даст нам правый регистр IPEK, получаем следующий 16 байтовый IPEK (я разделил левую и правую части для ясности).
6AC292FAA1315B4D 858AB3A3D7D5933A
Вычисление сессионных ключей
У нас есть IPEK. Далее нам нужно получить из IPEK уникальный ключ для отдельного проката карты (сессионный ключ). Чтобы получить его, используется некая подпрограмма, назовем ее черный ящик, целью которой является возврат отдельного сессионного ключа. Происходящее в черном ящике — пока не наша забота. Прямо сейчас мы посмотрим на вход этой подпрограммы.
Наш черный ящик имеет два входа. Один это ключ и второй — строка для шифрования. Строка представляет собой измененный KSN.
Если помните, младшие 21 бит KSN содержат счетчик количества прокатов карты на устройстве. Мы передадим модифицированный KSN в подпрограмму столько раз, сколько единиц в бинарном представлении счетчика. Ключ который передается с измененным KSN это IPEK на первой итерации, а на следующих итерациях это будет ключ полученный из черного ящика на предыдущей итерации.
Начнем с изменения KSN. Для начала мы возьмем младшие 8 байт KSN и обнулим значение счетчика в KSN. Это можно сделать с помощью маскирования KSN с использованием следующей маски.
FFFF9876543210E00008
and 0000FFFFFFFFFFE00000
= 00009876543210E00000
Полученное значение мы будем использовать для вычисления каждого сообщения передаваемого в черный ящик. В нашем примере со счетчиком равным 8 мы должны передать в черный ящик двоичное представление числа 8 (1000). Для демонстрации предположим, что счетчик имеет более сложное значение 10 (1010).
Мы будем извлекать набор двоичных чисел из счетчика. В нашем случае для числа 10 (1010) будет два двоичных числа: 1000 и 0010. Вы уловили схему? Мы получаем набор чисел, представляющих каждую бинарную единицу числа 10.
Далее берем первое число и применяем операцию OR с KSN, у которого обнулен счетчик, как было показано ранее (заметим что шестнадцатеричное представление первого числа будет 0008).
9876543210E00000
OR 0000000000000008
= 9876543210E00008
Теперь передаем IPEK как ключ и только что модифицированный KSN в черный ящик. Черный ящик вернет новый ключ. Это первый сессионный ключ (представленный в шестнадцатеричном виде): «27f66d5244ff62e1aa6f6120edeb4280».
Далее повторим процесс со следующим двоичным числом, вычисленным ранее, 2 (0010). На этот раз, мы будем использовать первый сессионный ключ, который мы только что получили и вычислим новую модификацию KSN.
Для вычисления новой модификации KSN мы будем выполнять операцию OR с последней полученной модификацией: 9876543210E00008.
9876543210E00008
OR 0000000000000002
= 9876543210E0000A
Теперь передадим наш новый ключ «27f66d5244ff62e1aa6f6120edeb4280» и новую модификацию KSN «9876543210E0000A» в черный ящик и получим другой будущий ключ, «6cf2500a22507c7cc776ceadc1e33014». Это сессионный ключ для нашего устройства со счетчиком 10.
Однако, наш настоящий счетчик был равен 8, а настоящий сессионный ключ «27F66D5244FF62E1AA6F6120EDEB4280» мы вычислили на первом этапе.
Последняя операция, которую мы должны проделать с полученным значением, конечное преобразование ключа, которым мы будем расшифровывать данные. Мы должны выполнить XOR ключа с маской «00000000000000FF00000000000000FF».
27F66D5244FF62E1AA6F6120EDEB4280
XOR 00000000000000FF00000000000000FF
= 27F66D5244FF621EAA6F6120EDEB427F
Это ключ, который требуется для расшифрования данных.
Чёрный ящик
Чёрным ящиком я назвал алгоритм, который вычисляет сессионные ключи. Чёрный ящик принимает текущий сессионный ключ, который я обозначу current_sk, и модификацию KSN, обозначим ksn_mod.
Если в начале предположение что IPEK полученный выше был передан как current_sk, а ksn_mod был равен значению «9876543210E00008», которое мы вычислили выше.
Для начала нам нужно взять current_sk, получить старшие 8 байт и сдвинуть их на 64 бита вправо, получим «6AC292FAA1315B4D». Это можно получить с помощью битовой маски.
6AC292FAA1315B4D858AB3A3D7D5933A
AND FFFFFFFFFFFFFFFF0000000000000000
= 6AC292FAA1315B4D0000000000000000
Здесь нам нужно сдвинуть это значение на 64 бита вправо, чтобы получить «6AC292FAA1315B4D». Назовем его left_key (выглядит как левая часть current_sk).
Далее получим 8 младших байт current_sk, с помощью маски.
6AC292FAA1315B4D858AB3A3D7D5933A
AND 0000000000000000FFFFFFFFFFFFFFFF
= 0000000000000000858AB3A3D7D5933A
Давайте назовем это значение (вы догадались) right_key. Далее возьмем right_key и выполним XOR с ksn_mod «9876543210E00008».
858AB3A3D7D5933A
AND 9876543210E00008
= 1DFCE791C7359332
Это значение назовем message. Далее берем message и шифруем его с помощью DES (простой DES). Будем передавать в DES алгоритм message как данные, которые надо закриптовать, и left_key, как ключ которым надо зашифровать. Получится значение «2FE5D2833A3ED1BA». Теперь нужно выполнить XOR этого значения и right_key.
2FE5D2833A3ED1BA
XOR 858AB3A3D7D5933A
= AA6F6120EDEB4280
Это значение младшие 8 байт нашего сессионного ключа! Теперь нам надо повторить только что описанные операции с другими входными данными. На этот раз мы берем current_sk и выполняем XOR его с «C0C0C0C000000000C0C0C0C000000000». Насколько я могу судить это значение произвольно, но оно часть стандарта ANSI, так что вы просто должны поверить моим словам.
6AC292FAA1315B4D858AB3A3D7D5933A
XOR C0C0C0C000000000C0C0C0C000000000
= AA02523AA1315B4D454A7363D7D5933A
Если мы возьмем значение «AA02523AA1315B4D454A7363D7D5933A» и подставим его вместо current_sk в операцию, которая описана выше, мы получим «27F66D5244FF62E1». Это старшие 8 байт нашего сессионного ключа. Комбинируя их получим «27F66D5244FF62E1AA6F6120EDEB4280».
Заключение
Надеюсь, я объяснил схему DUKPT и как она относится к эффективности сканеров магнитных дорожек. Жду исправления и вопросы в секции комментариев.