Криптографічна головоломка імпорт ключа 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):
Відкрита експонента, яку вдалося миттєво відновити за допомогою атаки Вінера на 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, Inverse Q2. Вони потрібні для швидкого отримання підпису із застосуванням китайської теореми про залишки.
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 = новий BigInteger(modulusBytes); var d = новий 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 []); // 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 & 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 CspProviderFlag KeyNumber = ( int )KeyNumber.Exchange, KeyContainerName = _containerName >;
// Використовуємо сховище користувача RSACryptoServiceProv >false;
using ( var cryptoServiceProv >new RSACryptoServiceProvider(cspParameters)) // імпорт модифікованого ключа cryptoServiceProvider.ImportParameters(rsaParameters); >
// Зберігаємо deviation в сховище користувача (не секрет) Storage.SaveDataInStorage(_containerName, toByteArray(deviation)); Storage.SaveDataInStorage(_containerName + "_flag", new []); >
* Цей source code був highlighted with Source Code Highlighter.
Як же отримати підпис повідомлення message?
Оригінальний підпис виходить так:
signature = hash ^D % Modulus
У нас тепер немає D, але є D2 та deviation, причому D2 + deviation = D. Прямий доступ до D2відсутня, т.к. воно у веденні CSP: можна лише отримати підпис цим D2, шляхом виклику стандартних функцій. Згадуємо алгебру:
Цей закон діє й у модульній алгебрі. Отже, наш оригінальний підпис (без знання D) знаходиться так:
part1 = hash ^ D2 % Modulus
part2 = hash ^ deviation % Modulus
signature = part1 * part2 % Modulus
Профіт! Тепер наш ключ у веденні 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 якраз.
Ось такою вийшла функція для формування підпису:
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 [] ; // заголовок WebMoney
var rngCryptoServiceProv >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 = _container
byte [] signature1; BigInteger modulus;
using ( var rsaCryptoServiceProv >new RSACryptoServiceProvider(528, cspParameters)) signature1 = rsaCryptoServiceProv >"SHA256" )); modulus = new BigInteger (rsaCryptoServiceProv & false ).Modulus); >
var deviation = новий BigInteger(Storage.LoadDataFromStorage(_containerName));
// стандартный заголовок SHA-256 заголовок вар. = новий байт [] 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 = новий байт [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);
байтовий прапор = 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(підпис, 0, uResult, 0, підпис.Довжина);
var stringBuilder = новий StringBuilder ();
for ( int pos = 0; pos string .Format(CultureInfo.InvariantCulture, "" , uResult[pos]));
* Цей вихідний код було виділено за допомогою підсвічування вихідного коду.
Тепер все працює як годинник: ключ сумісний з будь-яким криптографічним пристроєм, що працює в Windows-системі (він же eToken, ruToken — що угодно), підписка отримується дійсною.
Можливо кому-то складно буде понять, чому яне вибрав "легкий шлях". Пояснюю: кохаю криптографічні головоломки. Хтось сканворди вирішує, а мені більше подобаються головоломки у такому вигляді.
А у нас тут можна отримати грант на тестовий період Яндекс.Хмари. Варто лише у полі «секретний пароль» запровадити «Хабр»