XPKeygen

Генератор VLK-ключей для Windows XP / Windows Server 2003. Этот инструмент позволяет генерировать валидные ключи Windows XP на основе исходного ключа продукта, который может быть случайным. Исходный ключ продукта (Raw Product Key, RPK) задаётся в виде 9 цифр XXX-YYYYYY и необходим только для генерации ключа Windows XP.

Загрузка

Перейдите на вкладку Releases и загрузите оттуда последнюю версию.

Планы

Этот проект не мёртв — я сделаю всё возможное, чтобы довести его до ума.

Проблема

В общем, единственное, что отделяет нас от генерации валидных ключей Windows XP для КАЖДОЙ ВЕРСИИ и КАЖДОЙ СБОРКИ, — это отсутствие соответствующих закрытых ключей, полученных из их открытых аналогов внутри pidgen.dll. В интернете нет широко доступного кода для функции дискретного логарифмирования на эллиптической кривой, есть только расплывчатая информация о том, как это сделать.

Со временем проблема была частично решена.

Ресурс BINK не был никак закодирован, данные просто последовательно записывались в ресурс. sk00ter также полностью объяснил формат BINK на форумах MDL. Используя предыдущие знания сообщества по этой теме, я написал BINK Reader на Python 3. Файл находится в открытом доступе в этом репозитории, нажмите здесь, чтобы посмотреть исходный код.

Решение задачи дискретного логарифма — самая неизученная область исследований по состоянию на 28 мая 2023 года. Однако мой друг nephacks всё же нашёл тот неуловимый инструмент для решения этой сложной проблемы в самых тёмных уголках интернета. Он называется ECDLP (Elliptic Curve Discrete Logarithm Problem) Solver от Mr. HAANDI. Поскольку найти его в сети было крайне сложно, я перезалил его на свой сайт. Вы можете скачать инструмент здесь.

Файл ReadMe, который идёт с версией 0.2a солвера, сам по себе достаточно хорош, так что любой, у кого есть мозги, сможет настроить этот инструмент. Однако он не является открытым исходным кодом, поэтому интегрировать его в мой keygen оказалось невозможным.

Принцип работы

Нам нужно использовать случайный исходный ключ продукта как основу для генерации идентификатора продукта вида AAAAA-BBB-CCCCCCS-DDEEE.

Идентификатор продукта

Константа семейства ОС AAAAA отличается для каждой серии Windows XP. Например, для SP3 она равна 76487.

Разделы BBB и CCCCCC по сути кодируют исходный ключ продукта. Например, если первый раздел равен XXX, а второй — YYYYYY, исходный ключ продукта будет закодирован как XXX-YYYYYY.

Контрольная цифра S выбирается так, чтобы сумма всех цифр C с добавлением этой цифры была числом, кратным 7.

Индекс открытого ключа DD позволяет узнать, какой открытый ключ был использован для успешной проверки подлинности нашего ключа продукта. Например, для ключей Professional это 22, а для ключей VLK — 23.

Случайное число EEE используется для генерации другого идентификатора установки каждый раз.

Ключ продукта

Сам ключ продукта (не путать с RPK) имеет вид FFFFF-GGGGG-HHHHH-JJJJJ-KKKKK и кодируется в Base-24 с алфавитом BCDFGHJKMPQRTVWXY2346789, чтобы исключить любые легко путаемые символы, такие как I и 1 или O и 0.

Согласно формуле ёмкости алфавита, ключ может содержать максимум 114 бит информации. $$N = \log_2(24^{25}) \approx 114$$

Исходя из этого расчёта, мы разворачиваем 114-битный ключ продукта в 4 упорядоченных сегмента:

Для простоты мы объединим сегменты Upgrade и Serial в один сегмент под названием Data. По такой логике мы сможем извлечь RPK, сдвигая Data вправо, и упаковать его обратно, сдвигая биты влево, потому что у большинства априори валидных ключей продукта, которые я проверял, бит Upgrade был установлен в 1.

Microsoft переделала формат ключа продукта в Windows Server 2003, добавив серверный ключ аутентификации бэкенда, что было действительно безопасным подходом к проверке лицензий, поскольку никто не мог даже предположить, какой алгоритм проверки они использовали на своём частном сервере. Помимо добавления онлайн-механизма проверки, они также увеличили общую арифметику с 384 до 512 бит, а скаляр подписи — до 62 бит информации.

Однако, если бы мы генерировали ключ без учёта онлайн-активации, мы всё равно могли бы создавать валидные ключи, которые позволили бы пройти установку операционной системы. И именно это делает код — он генерирует случайный 10-битный ключ аутентификации. Сегодня это вообще не имеет значения, так как серверы активации отключены, а Server 2003 считается abandonware, точно так же, как весь этот проект не следует считать пиратством.

Эллиптические кривые

Эллиптическая криптография (ECC) — это тип систем с открытым ключом. Этот класс систем опирается на сложные "односторонние" математические задачи — легко вычислить в одну сторону и практически невозможно решить в "другую". Иногда их называют "лазейками" (trapdoor) — легко попасть, сложно выбраться.^[5]

ECC основана на решении уравнений вида $$y^2 = x^3 + ax + b$$

В общем случае в криптографии используются два особых случая эллиптических кривых — F_2m и F_p. Они отличаются лишь незначительно. Обе кривые определены над конечным полем: F_p использует простое число больше 3, F_2m предполагает $p = 2m$. Microsoft использовала последний вариант в своём алгоритме.

Эллиптическая кривая над конечным полем F_p состоит из:

• набора целочисленных координат ${x, y}$, таких что $0 \le x, y < p$;
• набора точек $y^2 = x^3 + ax + b \mod p$.

Эллиптическая кривая над F₁₇ выглядела бы так:

Кривая состоит из синих точек на изображении выше. На практике "эллиптические кривые", используемые в криптографии, — это "наборы точек в квадратной матрице".

Приведённая выше кривая — "учебная". Она обеспечивает очень малую длину ключа (4–5 бит). В реальных ситуациях разработчики обычно используют кривые размером 256 бит и более.

Ресурс BINK

Поскольку это криптографическая система с открытым ключом, Microsoft должна была поделиться открытым ключом с релизом Windows XP для проверки вводимых ключей продукта. Он хранится внутри pidgen.dll в виде ресурса BINK. Первый набор данных BINK предназначен для проверки розничных ключей, второй — для OEM-ключей соответственно.

Структура ресурса BINK для Windows 98 и Windows XP выглядит следующим образом:

Каждый сегмент отмечен разным цветом, значения заголовка BINK одинаковы.

Windows Server 2003 и Windows XP x64 реализуют это иначе:

А вот мои прототипы структур для BINK Reader на C:```c typedef struct _EC_BYTE_POINT { CHAR x[256]; // x-coordinate of the point on the elliptic curve. CHAR y[256]; // y-coordinate of the point on the elliptic curve. } EC_BYTE_POINT;

typedef struct _BINKHDR { // BINK version - not stored in the resource. ULONG32 dwVersion;

// Original BINK header.
ULONG32 dwID;
ULONG32 dwSize;
ULONG32 dwHeaderLength;
ULONG32 dwChecksum;
ULONG32 dwDate;
ULONG32 dwKeySizeInDWORDs;
ULONG32 dwHashLength;
ULONG32 dwSignatureLength;

// Extended BINK header. (Windows Server 2003+)
ULONG32 dwAuthCodeLength;
ULONG32 dwProductIDLength;

} BINKHDR;

typedef struct _BINKDATA { CHAR p[256]; // Finite Field order p. CHAR a[256]; // Elliptic Curve parameter a. CHAR b[256]; // Elliptic Curve parameter b.

EC_BYTE_POINT G;    // Base point (Generator) G.
EC_BYTE_POINT K;    // Public key K.

} BINKDATA;

typedef struct _BINKEY { BINKHDR header; BINKDATA data; } BINKEY;

Если вы хотите копнуть глубже, исходный код `pidgen.dll` и все его функции доступны в этом репозитории, в папке «pidgen».

### Восстановление закрытого ключа

Если мы хотим генерировать валидные ключи продуктов для Windows XP, нам нужно вычислить соответствующий закрытый ключ, используя открытый ключ из `pidgen.dll`, а это значит, что нам придётся решить обратную задачу односторонней ECC.

Судя по ключу из BINK, порядок кривой составляет **384 бита** в Windows XP и **512 бит** в Server 2003 / XP x64 соответственно.
Вычислительная сложность при использовании самого эффективного Rho-алгоритма Полларда с асимптотической сложностью $O(\sqrt{n})$ составляла бы как минимум $O(2^{168})$ для Windows XP и $O(2^{256})$ для Windows Server 2003, но, к счастью для нас,
Microsoft ограничила значение подписи до 55 бит в Windows XP и 62 бит в Windows Server 2003, чтобы уменьшить количество совпадающих ключей продуктов, снизив сложность до гораздо более приемлемых $O(2^{28})$ / $O(2^{31})$.

Как уже упоминалось, существует только один публичный инструмент, который удовлетворяет нашим текущим потребностям, — ECDLP-солвер от господина HAANDI.<br>

Для вычисления закрытого ключа нам нужно передать инструменту открытые значения ECC из ресурса BINK, а также порядок `genOrder` базовой точки `G(Gx; Gy)`. Порядок базовой точки можно вычислить с помощью SageMath.

**Вот основной алгоритм, который я использовал для восстановления закрытого ключа Windows 98:**

1. Вычислите порядок базовой точки с помощью **SageMath**. В SageMath выполните следующие команды:
    1) `E = EllipticCurve(GF(p), [0, 0, 0, a, b])`, где `p`, `a` и `b` — десятичные параметры эллиптической кривой из ресурса BINK.
    2) `G = E(Gx, Gy)`, где `Gx` и `Gy` — десятичные координаты базовой точки из ресурса BINK.
    3) `K = E(Kx, Ky)`, где `Kx` и `Ky` — десятичные координаты открытого ключа из ресурса BINK.
    4) `n = G.order()` — `n` будет вычисленным порядком базовой точки. **На его вычисление может потребоваться время, даже на самых новых сборках.**
    5) Разложите порядок на множители с помощью `factor(n)`. Microsoft использовала простые числа для порядков точек, поэтому если возвращается само число, это совершенно нормально.
    6) Сохраните полученные множители порядка куда-нибудь.
    7) `-K` даст вам инверсию открытого ключа в проективной плоскости с координатами `(x : y : z)`. Сохраните координату `y` куда-нибудь — она требуется для генерации корректного закрытого ключа.
2. Вычислите закрытый ключ с помощью **ECDLP Solver v0.2a**.
    1) Инструмент поставляется с шаблоном задания `job_template.txt` и файлом ReadMe. Чтобы использовать его, необходимо понимать, как он работает.
    2) Вставьте все открытые значения эллиптической кривой из ресурса BINK, **кроме координаты `Ky`**. Чтобы сгенерировать корректный закрытый ключ, **вы должны использовать инверсную координату `-Ky`, которую вы вычислили ранее в SageMath.**
    3) Вставьте множители порядка базовой точки `n` и укажите количество множителей. Скорее всего, это будет `1`, поскольку Microsoft в основном использует простые числа для порядков генераторов.
    4) Запустите инструмент `<arch> ECDLP Solver.exe <job_name>.txt` и подождите, пока он вычислит для вас закрытый ключ `k = %d`.

**Вот пример задания `job_xp.txt` для Windows XP, которое даёт правильный закрытый ключ для ECDLP Solver.**```pascal
GF := GF(22604814143135632990679956684344311209819952803216271952472204855524756275151440456421260165232069708317717961315241);
E := EllipticCurve([GF|1,0]);
G := E![10910744922206512781156913169071750153028386884676208947062808346072531411270489432930252839559606812441712224597826,19170993669917204517491618000619818679152109690172641868349612889930480365274675096509477191800826190959228181870174];
K := E![14399230353963643339712940015954061581064239835926823517419716769613937039346822269422480779920783799484349086780408,17120082747148185997450361756610881166187863099877353630300913555824935802439591336620545428308962346299700128114607];
/*
FactorCount:=1;
61760995553426173
*/

And the ECDLP Solver output for it:

Важное примечание:

Имейте в виду, что мне не удалось сгенерировать корректный ключ Windows XP x64 с помощью восстановленного мной приватного ключа, даже используя координату Ky вместо обычной -Ky. По какой-то причине мне также не удалось вычислить порядок базовой точки Windows Server 2003 с помощью SageMath. Я дал ему 12 часов на вычисления на моём i7-12700K, но он всё ещё был занят вычислениями.

Проверка / генерация ключей продукта

Остальная часть работы выполняется в коде этого keygen.

Известные проблемы

• Некоторые ключи недействительны, но в целом это довольно редкое явление. Примерно 2 из 3 ключей должны работать.
  Исправлено в v1.2. Предыдущие версии генерировали действительный ключ с точной вероятностью 0x40000/0x62A32, что давало ровно 0.64884, или около 65%. Моя оценка «2 из 3» была невероятно точной.
• Протестировано на нескольких конфигурациях Windows XP. Работает на Professional x86, всех пакетах обновления. Другие выпуски Windows могут не работать. x64 НЕ РАБОТАЕТ.
• Генерация ключей Server 2003 пока не включена.
  Исправлено в v2.2.
• Некоторые ключи Windows XP VLK, как правило, «хуже» других. Некоторые из них могут вызвать повреждённый WPA с пустым Installation ID после установки. Наилучшие шансы сгенерировать «лучшие» ключи — когда раздел BBB установлен в 640, а раздел CCCCCC не равен нулю.
• Генерация ключей Windows Server 2003 сломана. Я даже не знаю, с чего начать. Ключи, похоже, недействительны нигде, но алгоритм хорошо документирован. В моей реализации получается примерно 1 из 3 «действительных» ключей.
  Исправлено в v2.3*.

Литература

В следующих релизах я добавлю в библиографию ещё несколько достойных материалов.

Основы активации Windows XP:

• [1] Inside Windows Product Activation - Fully Licensed | archive.org
• [2] MSKey 4-in-1 ReadMe | archive.org
• [3] Windows序列号产生原理(椭圆曲线法) | archive.org

Понимание криптографии на эллиптических кривых:

• [4] Elliptic Curve Cryptography for Beginners - Matt Rickard | archive.org
• [5] Elliptic Curve Cryptography (ECC) - Practical Cryptography for Developers | archive.org
• [6] A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography - Cloudflare | archive.org

Публичные обсуждения:

• [7] Windows 98 Equivalent // Server 2003 Algorithm | archive.org
• [8] Cracking Windows XP | archive.org

Участие / Использование

Если вы собираетесь демонстрировать или форкать это ПО, пожалуйста, отдайте должное Endermanch, z22 и MSKey.
Не стесняйтесь модифицировать его по своему усмотрению, при условии, что оно останется открытым. Лицензировано под GNU General Public License v3.0.

Любые вклады и вопросы приветствуются.