Криптографическая головоломка: импорт ключа WebMoney в Crypto Service Provider

Приватные ключи в системе 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:

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.
От автора.

Возможно кому-то сложно будет понять, почему я не выбрал «легкий путь». Поясняю: люблю криптографические головоломки. Кто-то сканворды решает, а мне больше нравятся головоломки вот в таком виде.