Приватные ключи в системе Windows, как правило, сохраняются в специальном хранилище ключей. Работа с этими ключами происходит путем вызова функций криптографического провайдера (далее CSP). При использовании стандартного CSP (Microsoft Base Cryptographic Provider) ключи пользователя хранятся в папке C:\Users\[Vasia]\AppData\Roaming\Microsoft\Crypto. При использовании специальных устройств, ключи хранятся в памяти самого устройства.
Для повышения безопасности, было принято решение импортировать ключ WebMoney (тот самый .kwm, которым подписывают запросы к интерфейсам) в CSP. Обычно те, кто использует ключ для подписи запросов к WM-интерфейсам, хранят его либо в виде файла .kwm в файловой системе, либо в виде xml-представления – оба варианта не очень-то безопасны.
Это оказалось не так уж просто.
Детально о проблемах, с которыми вы столкнетесь, при повышении безопасности своего платежного сервиса, читайте под катом.
Итак. Начнем с формата файла kwm. Файл имеет не замысловатый формат (мелочи упущены):
1. Хеш для проверки целостности.
2. Зашифрованная приватная RSA-экспонента (D).
З. Зашифрованный RSA-модуль (Modulus).
Проблема № 1: после расшифровки файла ключа, получаем только 2 из нужных нам 8 параметров.
У нас есть: D и Modulus, нам нужны: Exponent, Modulus, P, Q, DP, DQ, InverseQ, D (детально структуру, к которой нужно привести ключ для импорта в CSP смотрите в MSDN msdn.microsoft.com/en-us/library/Aa387401).
Если бы знать E (открытая экспонента), не сложно было бы найти все эти параметры. Обычно E принимают одно из чисел Ферма: 17, 257, 65537 или 4294967297. Проверить очень просто:
1. Зашифровываем произвольное сообщение message нашими параметрами D и Modulus:
2. Пытаемся расшифровать с помощью Exponent (предполагаемого) и Modulus:
Если полученное после расшифровки сообщение совпало с оригинальным, значит Exponent подобрали правильно.
Примечание: здесь и далее, оператор "^" – возведение в степень, а оператор "%" нахождение остатка от деления.
Проблема №2: открытая экспонента нам не известна, и она достаточно большая.
К сожалению, ни одно из них чисел Ферма не подошло в качестве открытой экспоненты. Это немного расстроило. Далее, надеясь, что это число все-таки не слишком большое – были испробованы (брутфорсом) все числа, менее 4-х байт. Ни одно из них не подошло. Вроде бы тупик и можно было бы про эту идею забыть…
На этом могло бы все и закончиться. Добыть открытую экспоненту не представлялось возможным: брутфорсить ее несколько десятков (а то и сотен) лет.
Однако история имеет продолжение. Жил на свете такой человек как Michael J. Wiener, который придумал способ взлома системы RSA, в случае малого значения d. У нас немного наоборот: малое значение открытой экспоненты, которую мы не знаем.
И действительно, применив атаку Винера на RSA, можно практически мгновенно найти открытую экспоненту любого ключа (если она не очень длинная).
Вот что получилось:
Оригинальные значения D и Modulus (полученные из файла kwm):
Открытая экспонента, которую удалось мгновенно восстановить с помощью атаки Винера на RSA:
Казалось, дело за малым: привести полученные параметры к структуре Private Key BLOBs и импортировать в любой крипто-провайдер. Но не так все просто…
Проблема №3: публичная экспонента длиннее 4-х байт, а формат Private Key BLOBs разрешает экспоненты только до 4-х байт длиной (4 байта включительно).
Вот беда! Казалось бы, задача не имеет решения и можно про нее забыть (уже во второй раз).
Хотя… Ведь мы имеем параметры криптосистемы (в частности простые числа p и q). Поэтому можно сделать так:
1. Берем оригинальные параметры P и Q.
2. Выбираем подходящую нам публичную экспоненту Exponent2 (не более 4-х байт). Возьмем число Ферма 65537.
3. Вычисляем закрытую экспоненту D2 (мультипликативно обратное к числу e по модулю (P-1)*
(Q-1)). D2 будет отличаться от оригинального D из файла kwm.
4. Вычисляем параметры: DP2, DQ2, InverseQ2. Они нужны для быстрого получения подписи, с применением китайской теоремы об остатках.
5. Самое важное! Вычисляем разницу между оригинальным D (которое в оригинальном ключе kwm) и D2 нашей модифицированной криптосистемы (т.е. D2 — D).
Теперь модифицированный ключ можно сохранить в хранилище CSP (к примеру, eToken PRO) как закрытый RSA-ключ, а deviation сохранить как PKCS#11 объект. При использовании Microsoft CSP, deviation можно сохранить в хранилище пользователя.
В принципе, значение deviation не является секретным, секретным теперь является наш модифицированный ключ (который храним в CSP).
Вот пример на C#, который отвечает за импорт модифицированного ключа в CSP:
Как же теперь получить подпись сообщения message?
Оригинальная подпись получается так:
У нас теперь нет D, но есть D2 и deviation, причем D2 + deviation = D. Прямой доступ к D2 отсутствует, т.к. оно в ведении CSP: можно только получить подпись этим D2, путем вызова стандартных функций. Вспоминаем алгебру:
Этот закон действует и в модульной алгебре. Итак, наша оригинальная подпись (без знания D) находится так:
Профит! Теперь наш ключ в ведении CSP (в случае с аппаратным устройством, это довольно надежно). Небольшая неприятность – весь «не вместился», остался еще «кусочек» в виде deviation. Но этот deviation не является секретом, без знания D2 он практически не привносит никакой подсказки об оригинальном D.
Но не спешите расслабляться.
Проблема № 4: структура подписываемых данных отличается от общепринятой.
Если расшифровать подпись, полученную средствами Win CAPI (расшифровать можно публичной экспонентой и модулем), то увидим примерно такую структуру:
в начале стандартный заголовок, а в конце 32 байта хеша подписываемого сообщения (привел для SHA-256).
Подпись WebMoney Signer'ом отличается: первые байты заполнены случайными числами, далее 16 байт хеша MD4, затем заголовок из 2-х байт.
Проблема в том, что CSP не поддерживает прямой функции модульного возведения в степень закрытым ключом (если бы так можно было — все бы получилось). Разрешается лишь:
1. Подписать сообщение. В явном виде нам никак не подходит, т.к. WebMoney не будут признавать нашу подпись — ведь структура отличается.
2. Зашифровать сообщение. Опять же — шифрование своеобразное (оригинальное сообщение видоизменяется, дополняется случаными числами) — оно никак не согласуется с нашим форматом.
Опять тупиковая ситуация. Хотя… А что если подсунуть нашему CSP не настоящий хеш, а псевдо-хеш, в который мы вместим данные в нужном нам формате? Хеш-функция не обратима, по этому нет ни единого способа проверить является ли хеш настоящим.
Для этого нам нужно выбрать алгоритм, имеющий достаточно длинный хеш: чтобы и наш 16 байнытный MD4 вместился, и 2-х байтный заголовок, да еще и, неплохо было бы, для безопасности, дополнить данные случайными числами.
SHA-512 оказался великоват, а вот SHA-256 в самый раз.
Вот такой получилась функция для формирования подписи:
Теперь все работает как часы: ключ совместим с любым криптографическим устройством, работающим в Windows-системе (ака eToken, ruToken — что угодно), подпись получается валидной.
P.S.
От автора.
Возможно кому-то сложно будет понять, почему я не выбрал «легкий путь». Поясняю: люблю криптографические головоломки. Кто-то сканворды решает, а мне больше нравятся головоломки вот в таком виде.
Для повышения безопасности, было принято решение импортировать ключ WebMoney (тот самый .kwm, которым подписывают запросы к интерфейсам) в CSP. Обычно те, кто использует ключ для подписи запросов к WM-интерфейсам, хранят его либо в виде файла .kwm в файловой системе, либо в виде xml-представления – оба варианта не очень-то безопасны.
Это оказалось не так уж просто.
Детально о проблемах, с которыми вы столкнетесь, при повышении безопасности своего платежного сервиса, читайте под катом.
Итак. Начнем с формата файла kwm. Файл имеет не замысловатый формат (мелочи упущены):
1. Хеш для проверки целостности.
2. Зашифрованная приватная RSA-экспонента (D).
З. Зашифрованный RSA-модуль (Modulus).
Проблема № 1: после расшифровки файла ключа, получаем только 2 из нужных нам 8 параметров.
У нас есть: D и Modulus, нам нужны: Exponent, Modulus, P, Q, DP, DQ, InverseQ, D (детально структуру, к которой нужно привести ключ для импорта в CSP смотрите в MSDN msdn.microsoft.com/en-us/library/Aa387401).
Если бы знать E (открытая экспонента), не сложно было бы найти все эти параметры. Обычно E принимают одно из чисел Ферма: 17, 257, 65537 или 4294967297. Проверить очень просто:
1. Зашифровываем произвольное сообщение message нашими параметрами D и Modulus:
encrypted = message^D % Modulus
2. Пытаемся расшифровать с помощью Exponent (предполагаемого) и Modulus:
message = encrypted^Exponent % Modulus
Если полученное после расшифровки сообщение совпало с оригинальным, значит Exponent подобрали правильно.
Примечание: здесь и далее, оператор "^" – возведение в степень, а оператор "%" нахождение остатка от деления.
Проблема №2: открытая экспонента нам не известна, и она достаточно большая.
К сожалению, ни одно из них чисел Ферма не подошло в качестве открытой экспоненты. Это немного расстроило. Далее, надеясь, что это число все-таки не слишком большое – были испробованы (брутфорсом) все числа, менее 4-х байт. Ни одно из них не подошло. Вроде бы тупик и можно было бы про эту идею забыть…
На этом могло бы все и закончиться. Добыть открытую экспоненту не представлялось возможным: брутфорсить ее несколько десятков (а то и сотен) лет.
Однако история имеет продолжение. Жил на свете такой человек как Michael J. Wiener, который придумал способ взлома системы RSA, в случае малого значения d. У нас немного наоборот: малое значение открытой экспоненты, которую мы не знаем.
И действительно, применив атаку Винера на RSA, можно практически мгновенно найти открытую экспоненту любого ключа (если она не очень длинная).
Вот что получилось:
Оригинальные значения D и Modulus (полученные из файла kwm):
D: 19715AB67A97257C5C80C8CD8F97448199F6F3FF8A3724DEA911C32CB5E64395D3175D6112A51DC14911FBA4E8FD107C1C65BE062A3491B1131168DF423408E2593
Modulus: 789BE5F2D0C90430EAEFC640B752FE707D75EB12C9C76F776C981014C1825C48989F15F5F53AFBF9B9C11D5C9AF184CC4F3938A48045414F814636C1275321F3AB9
Открытая экспонента, которую удалось мгновенно восстановить с помощью атаки Винера на RSA:
Exponent: 21EA463DEB0B
Казалось, дело за малым: привести полученные параметры к структуре Private Key BLOBs и импортировать в любой крипто-провайдер. Но не так все просто…
Проблема №3: публичная экспонента длиннее 4-х байт, а формат Private Key BLOBs разрешает экспоненты только до 4-х байт длиной (4 байта включительно).
Вот беда! Казалось бы, задача не имеет решения и можно про нее забыть (уже во второй раз).
Хотя… Ведь мы имеем параметры криптосистемы (в частности простые числа p и q). Поэтому можно сделать так:
1. Берем оригинальные параметры P и Q.
2. Выбираем подходящую нам публичную экспоненту Exponent2 (не более 4-х байт). Возьмем число Ферма 65537.
3. Вычисляем закрытую экспоненту D2 (мультипликативно обратное к числу e по модулю (P-1)*
(Q-1)). D2 будет отличаться от оригинального D из файла kwm.
4. Вычисляем параметры: DP2, DQ2, InverseQ2. Они нужны для быстрого получения подписи, с применением китайской теоремы об остатках.
5. Самое важное! Вычисляем разницу между оригинальным D (которое в оригинальном ключе kwm) и D2 нашей модифицированной криптосистемы (т.е. D2 — D).
Теперь модифицированный ключ можно сохранить в хранилище CSP (к примеру, eToken PRO) как закрытый RSA-ключ, а deviation сохранить как PKCS#11 объект. При использовании Microsoft CSP, deviation можно сохранить в хранилище пользователя.
В принципе, значение deviation не является секретным, секретным теперь является наш модифицированный ключ (который храним в CSP).
Вот пример на C#, который отвечает за импорт модифицированного ключа в CSP:
public void ImportPrivateKey(byte[] modulusBytes, byte[] privateExponentBytes)
{
// пропускаем проверку аргументов
var modulus = new BigInteger(modulusBytes);
var d = new BigInteger(privateExponentBytes);
var p = Wiener.Calculate(d, modulus); // применяем атаку Винера на RSA и находим P (по закрытой экспоненте и модулю)
var q = modulus/p;
var f = (p - 1)*(q - 1); // функция Эйлера
var e = new BigInteger(new byte[] {1, 0, 1}); // 65537
var d2 = e.modInverse(f); // d2 -- модифицированная секретная экспонента
var dp2 = d2%(p - 1);
var dq2 = d2%(q - 1);
var iq = q.modInverse(p);
var rsaParameters = new RSAParameters
{
D = toByteArray(d2),
DP = toByteArray(dp2),
DQ = toByteArray(dq2),
Exponent = toByteArray(e),
InverseQ = toByteArray(iq),
Modulus = toByteArray(modulus),
P = toByteArray(p),
Q = toByteArray(q)
};
BigInteger deviation;
byte flag; // если d > d2, то флаг установлен
if (d > d2)
{
deviation = d - d2;
flag = 0;
}
else
{
deviation = d2 - d;
flag = 1;
}
// Импортируем наш ключ в CSP (для сохранения в eToken, следует указать имя CSP "eToken Base Cryptographic Provider")
var cspParameters = new CspParameters
{
Flags =
CspProviderFlags.UseNonExportableKey | CspProviderFlags.UseUserProtectedKey,
KeyNumber = (int)KeyNumber.Exchange,
KeyContainerName = _containerName
};
// Используем хранилище пользователя
RSACryptoServiceProvider.UseMachineKeyStore = false;
using (var cryptoServiceProvider = new RSACryptoServiceProvider(cspParameters))
{
// импорт модифицированного ключа
cryptoServiceProvider.ImportParameters(rsaParameters);
}
// Сохраняем deviation в хранилище пользователя (не является секретом)
Storage.SaveDataInStorage(_containerName, toByteArray(deviation));
Storage.SaveDataInStorage(_containerName + "_flag", new[] {flag});
}
* This source code was highlighted with Source Code Highlighter.
Как же теперь получить подпись сообщения message?
Оригинальная подпись получается так:
signature = hash ^ D % Modulus
У нас теперь нет D, но есть D2 и deviation, причем D2 + deviation = D. Прямой доступ к D2 отсутствует, т.к. оно в ведении CSP: можно только получить подпись этим D2, путем вызова стандартных функций. Вспоминаем алгебру:
a^(b+c) = a^b * a^c
Этот закон действует и в модульной алгебре. Итак, наша оригинальная подпись (без знания D) находится так:
part1 = hash ^ D2 % Modulus
part2 = hash ^ deviation % Modulus
signature = part1 * part2 % Modulus
Профит! Теперь наш ключ в ведении CSP (в случае с аппаратным устройством, это довольно надежно). Небольшая неприятность – весь «не вместился», остался еще «кусочек» в виде deviation. Но этот deviation не является секретом, без знания D2 он практически не привносит никакой подсказки об оригинальном D.
Но не спешите расслабляться.
Проблема № 4: структура подписываемых данных отличается от общепринятой.
Если расшифровать подпись, полученную средствами Win CAPI (расшифровать можно публичной экспонентой и модулем), то увидим примерно такую структуру:
1FFFFFFFFFFFFFFFFFFFFFFFF003031300D0609608648016503040201050004209F64A747E1B97F131FABB6B447296C9B6F0201E79FB3C5356E6C77E89B6A806
в начале стандартный заголовок, а в конце 32 байта хеша подписываемого сообщения (привел для SHA-256).
Подпись WebMoney Signer'ом отличается: первые байты заполнены случайными числами, далее 16 байт хеша MD4, затем заголовок из 2-х байт.
Проблема в том, что CSP не поддерживает прямой функции модульного возведения в степень закрытым ключом (если бы так можно было — все бы получилось). Разрешается лишь:
1. Подписать сообщение. В явном виде нам никак не подходит, т.к. WebMoney не будут признавать нашу подпись — ведь структура отличается.
2. Зашифровать сообщение. Опять же — шифрование своеобразное (оригинальное сообщение видоизменяется, дополняется случаными числами) — оно никак не согласуется с нашим форматом.
Опять тупиковая ситуация. Хотя… А что если подсунуть нашему CSP не настоящий хеш, а псевдо-хеш, в который мы вместим данные в нужном нам формате? Хеш-функция не обратима, по этому нет ни единого способа проверить является ли хеш настоящим.
Для этого нам нужно выбрать алгоритм, имеющий достаточно длинный хеш: чтобы и наш 16 байнытный MD4 вместился, и 2-х байтный заголовок, да еще и, неплохо было бы, для безопасности, дополнить данные случайными числами.
SHA-512 оказался великоват, а вот SHA-256 в самый раз.
Вот такой получилась функция для формирования подписи:
public string Sign(string value)
{
if (string.IsNullOrEmpty(value))
throw new ArgumentNullException("value");
var toSign = new byte[32]; // Псевдо-хеш SHA256
var random = new byte[14]; // случайные числа
var hash = getHash(value); // наш хеш сообщения MD4
var prefix = new byte[] {0, 56}; // заголовок WebMoney
var rngCryptoServiceProvider = new RNGCryptoServiceProvider();
rngCryptoServiceProvider.GetBytes(random);
Buffer.BlockCopy(random, 0, toSign, 0, random.Length);
Buffer.BlockCopy(hash, 0, toSign, random.Length, hash.Length);
Buffer.BlockCopy(prefix, 0, toSign, random.Length + hash.Length, prefix.Length);
var cspParameters = new CspParameters
{
Flags =
CspProviderFlags.UseNonExportableKey | CspProviderFlags.UseUserProtectedKey,
KeyNumber = (int) KeyNumber.Exchange,
KeyContainerName = _containerName
};
byte[] signature1;
BigInteger modulus;
using (var rsaCryptoServiceProvider = new RSACryptoServiceProvider(528, cspParameters))
{
signature1 = rsaCryptoServiceProvider.SignHash(toSign, CryptoConfig.MapNameToOID("SHA256"));
modulus = new BigInteger(rsaCryptoServiceProvider.ExportParameters(false).Modulus);
}
var deviation = new BigInteger(Storage.LoadDataFromStorage(_containerName));
// стандартный заголовок SHA-256
var header = new byte[]
{
0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x00,
0x30,
0x31, 0x30, 0x0D, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01,
0x05,
0x00, 0x04, 0x20
};
var toEncrypt = new byte[65];
Buffer.BlockCopy(header, 0, toEncrypt, 0, header.Length);
Buffer.BlockCopy(random, 0, toEncrypt, header.Length, random.Length);
Buffer.BlockCopy(hash, 0, toEncrypt, header.Length + random.Length, hash.Length);
Buffer.BlockCopy(prefix, 0, toEncrypt, header.Length + random.Length + hash.Length, prefix.Length);
byte flag = Storage.LoadDataFromStorage(_containerName + "_flag")[0];
var part1 = new BigInteger(signature1);
BigInteger part2;
if (1 == flag)
{
// Инверсия -- в проекции на школьную алгебру -- это деление
part2 = new BigInteger(toEncrypt).modInverse(modulus).modPow(deviation, modulus);
}
else
part2 = new BigInteger(toEncrypt).modPow(deviation, modulus);
var signature = toByteArray((part1*part2)%modulus);
// Переводим в little-endian
Array.Reverse(signature);
// Приводим к строковому виду
var uResult = new ushort[KeyBytesLength/2];
Buffer.BlockCopy(signature, 0, uResult, 0, signature.Length);
var stringBuilder = new StringBuilder();
for (int pos = 0; pos < uResult.Length; pos++)
stringBuilder.Append(string.Format(CultureInfo.InvariantCulture, "{0:x4}", uResult[pos]));
return stringBuilder.ToString();
}
* This source code was highlighted with Source Code Highlighter.
Теперь все работает как часы: ключ совместим с любым криптографическим устройством, работающим в Windows-системе (ака eToken, ruToken — что угодно), подпись получается валидной.
P.S.
От автора.
Возможно кому-то сложно будет понять, почему я не выбрал «легкий путь». Поясняю: люблю криптографические головоломки. Кто-то сканворды решает, а мне больше нравятся головоломки вот в таком виде.