Криптографическая головоломка: импорт ключа 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.
    От автора.

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

    Похожие публикации

    Комментарии 19

    • НЛО прилетело и опубликовало эту надпись здесь
        +2
        Поэтому во всем мире, кроме СНГ, не знают таких слов WM, а даже если и знают, то в большинстве случаев платежи по ним не принимают.
          0
          а не страшно ли нам, что не страшно им? )

          а вообще — молодцы, что не свернули с пути со словами «корявый MS, отсутствие документации и пр»
          +1
          Интересное решение, прочитал с большим удовольствием
            0
            Профит от хранения ключа на криптографическом устройстве в полной силе существует тогда, когда он это само устройство не покидает. Обычно он вообще там внутри генерируется. А так, можно просто ключ и в rar файлике шифрованном на флешке хранить, примерно с тем же успехом.

            Статья симпатичная :)
              +1
              eToken PRO сам генерит подпись. Ключ никогда не покидает устройство. Собственно, для него и делалось.
                0
                Я наверное тогда не совсем верно понимаю значение слова «импорт»?
                  0
                  Импорт — здесь сохранение ключа в CSP. После того, как сохранили, извлечь уже не возможно — можно только использовать (у случае с eToken, а то некоторые устройства сами не реализуют подпись).
              0
              Вот дела: чтобы защитить ключ, надо сперва его взломать о_О
                0
                Я правильно понял:
                для создания подписи разными ключами, в отличии от остальных ключей, при использовании ключа WM придется делать лишние не стандартные телодвижения?
                  0
                  Webmoney поддерживает pkcs12 и windows CSP. Никаких телодвижений не нужно. Топику место в «ненормальном программировании» )
                    0
                    Поясните что вы имеете в виду? Ключ Keeper Light?

                    Дело в том, что не все интерфейсы работают с авторизацией Keeper Light — некоторые только с авторизацией Classic.
                    0
                    Просто ключ в нестандартном формате и привести его к стандартному оказалось совсем не просто.
                    +3
                    Да весьма симпатично. Оригинальное применение известной атаки Винера весьма доставило. Помнится в универе заставляли реализовывать. В самом деле позволяет с полиномиальной скоростью восстановить секретную экспоненту, только если не ошибаюсь при условии что d<n1/4.
                    Кстати, как там ваш проект реализации ДСТУ поживает?

                      +1
                      >>только если не ошибаюсь при условии что d<n1/4.

                      Если точнее, то d < 1/3 * n ^ (1/4) Если бы можно было d любой длины находить — то смысла в RSA бы не было. Может когда и придумают…

                      >>Кстати, как там ваш проект реализации ДСТУ поживает?

                      web.cryptography.org.ua/index.html — там все написано. В общем то, после того как научились генерить ключи и подпись для обоих базисов — дело немножко подвисло. Теперь задача — сделать быструю версию подписи для ОНБ. Надеюсь появится время и займусь. Напишу вам.

                      Кстати, есть у вас идеи, как (и в каких случаях) можно использовать deviation для ослабления безопасности? У меня парочка есть, но не всегда можно использовать.
                        0
                        [оффтоп href=«web.cryptography.org.ua/tasks.html» ]
                        > На данный момент умножение точки кривой на число занимает 7-10 секунд

                        Как вы этого добились? Даже если взять самый простой (интерфейсом) NTL, в лоб на нём нарисовать умножение справа самым простым способом, даже с перегруженными операторами, всё равно получается около 150 подписей в секунду в GF(P)
                        [/оффтоп]
                          0
                          >>Как вы этого добились?

                          Добились — хорошее слово. Будете смеяться, но первая реализация вычисляла произведение точки на число 15 минут.

                          Там умножение в ОНБ. В принципе, оно длительно выполняется. Скорее всего нужно перевести в полиномиальный базис, тогда будет быстрее. В общем, если вы разбираетесь в вопросе — можете посмотреть исходники.
                      0
                      А можно более детальное описание структуры kwm привести? Я помню, что у классика kwm-файл может быть разного размера, соответственно интересно было бы почитать как в случае с изменяющимся размером получить D и Modulus.

                      Теперь модифицированный ключ можно сохранить в хранилище CSP (к примеру, eToken PRO) как закрытый RSA-ключ, а deviation сохранить как PKCS#11 объект

                      Закрытый RSA-ключ, который будет помечен как неэкспортируемый и поэтому его нельзя будет извлечь? Если да, то в случае с хранилищем win* все можно извлечь, правда нестандартным, но довольно простым способом.
                        0
                        >>А можно более детальное описание структуры kwm привести?

                        Вот здесь исходный код на C# для расшифровки ключа: wm-api.svn.sourceforge.net/svnroot/wm-api/trunk/WebMoney.Cryptography/DecryptedKey.cs В самом верху файла — константы. Они повторяют структуру файла kwm.

                        >>Я помню, что у классика kwm-файл может быть разного размера, соответственно интересно было бы почитать как в случае с изменяющимся размером получить D и Modulus

                        Это раньше было, теперь размер все время одинаковый. Раньше его раздували простейшим алгоритмом «для безопасности». Смысл, возможно, был, когда у всех было подключение 32 Кбод. Сейчас убрали.

                        >>Закрытый RSA-ключ, который будет помечен как неэкспортируемый и поэтому его нельзя будет извлечь? Если да, то в случае с хранилищем win* все можно извлечь, правда нестандартным, но довольно простым способом.

                        С win-хранилища можно (если на ключ не установлен пароль). А вот с eToken — такой возможности нет в принципе — только вместе с устройством.

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.