08.11.2004

Снова о Случайных Числах или Старый взгляд на новые вещи II.

Эта статья является продолжением увлекательного разговора о случайных и псевдослучайных числах, начатого статьёй "Старый взгляд на новые вещи". О возможностях, скрытой опасности и силе, которая скрыта в ГСЧ. В статье рассматривается основы математической теории для работы с СЧ, приводятся новые примеры использования ГПСЧ, ...

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

- Хорошо, хорошо. Что случилось?
- Ты славный парень. Но ты лишен информации. А что сказал Винер? Винер сказал: "Чем более вероятно сообщение, тем меньше оно содержит информации". Такие плакаты ты увидишь в любом зале ожидания...
Аркадий Стругацкий "Дни кракена"

Введение/Introduction
Продолжим наше путешествие по таинственной дороге RN (Random Numbers - Случайные Числа, далее СЧ).
Автор скромно предполагает, что вы читали первую статью - "Старый взгляд на новые вещи" (на [1]), если же нет, то ... "сложно продолжить путь, так и не начав его" :).
В самом начале вы натолкнётесь на несколько простеньких формул. Есть конечно опасения, что "каждая формула вдвое сокращает круг читателей", но я надеюсь, что Вас это не касается, в противном случае вы можете их просто пропустить (так же могут поступить те, кто сдал курс Теории Вероятностей ;)).

Начало/Beginning
Давайте зададимся простым вопросом: чем одна последовательность СЧ отличается от другой?
Например: чем последовательность СЧ, выдаваемая /dev/random отличается от последовательности СЧ выдаваемой /dev/urandom ?
Ответ, что: "/dev/random создаёт только случайные байты" нужно понять немного глубже.
Статистическая теория даёт нам ряд количественных критериев, по которым проводят проверку качества ГСЧ(Генераторов Случайных Чисел (Random Number Generator) (RNG)) или Генераторов Псевдослучайных Чисел(Pseudorandom Number Generator (PRNG))?
вместо Pseudorandom очень хочется поставить Poor random :-)

Такую проверку проводят по ряду количественных критериев, которые нам даёт статистическая теория.
Ниже приводятся некоторые наиболее распространённые тесты:
1. Критерий "хи-квадрат" (пишется греческая буква хи, возведённая в квадрат)
2. Проверка по моментам распределения.
3. Проверка на равномерность.
4. Проверка независимости элементов последовательности.
5. etc.

Ниже рассмотрена сущность второго и третьего тестов:

Проверка по моментам распределения.

	МОМЕНТ -
	(от лат. momentum - движущая сила, толчок), понятие теории вероятностей;
	характеристика распределения значений случайной величины Х. 
	В простейшем случае, когда Х может принимать лишь конечное число значений
	x1, x2,..., xn
	с вероятностями
	p1, p2,..., pn,
	моментом порядка k величины Х называется выражение:
	
	
	  k     k           k
	x1 p1+x2 p2+ ... +xn pn
	
	Момент 1-го порядка а - математическое ожидание, 
	момент 2-го порядка - дисперсия (если а = 0).
	
	Я конечно рассчитываю, что вам знакомы такие понятия из теории вероятностей, 
	как математическое ожидание и дисперсия, но до кучи :) приведу формулы и для них.
	
	Математическое ожидание:
	Если X принимает значения xi с вероятностями pi
	Тогда математическое ожидание запишется:
	
	
	     n
	    --
	MX= \ (xipi)
	    /
	    --
	     i
	
	Математическое ожидание имеет смысл среднего значения случайной величины.
	Для непрерывной величины сумма заменяется на интеграл.
	Дисперсия:
	
	          2
	DX=M(X-MX)
	
	Дисперсия даёт разброс случайной величины вокруг среднего значения.
	Именно смысл дисперсии имеют величины в принципе неопределённости Гейзенберга.
	

Т.о. проверка по моментам распределения последовательности случайных чисел x1,x2, ... ,xN заключается в подсчёте математического ожидания (сиречь среднего) и дисперсии. Если числа близки к равномерной случайной последовательности [0,1], то при достаточно больших N(число выборок)
Mx~0,5
Dx~1/12
Эти числа получаются, если в интегральные формулы для мат. ожидания и дисперсии подставить функцию плотности распределения, описывающую равномерное распределение в интервале [0,1].

Проверка на равномерность.
Для проверки на равномерность нужно интервал распределения случайной величины (например отрезок [0,1]) разбить на n равных частей. Тогда каждое из чисел xi попадёт в один из интервалов.
Пусть M1 - число чисел, попавших в первый интервал M2 - во второй и т.д. При этом
M1+M2+ ... +Mn=N
Тогда относительные частоты попадания случайных чисел в каждый из n интервалов:
p1=M1/N ,p2=M2/N , ... ,pn=Mn/N ,
Далее строится гистограмма(pi от xi).
Если числа равномерные, то при большом N гистограмма должна приближаться к теоретической прямой 1/n.
Число разбиений обычно берётся 10-20.

Таким образом - не составляет труда написать простенькую программку для тестирования функций ГСЧ.
Исходничек, приведённый ниже предназначен для "тестирования" функции, выдающей случайные числа(rnd(), пример которой приведён в первой статье); вычисляет среднее значение, дисперсию, а так же распределение случайных чисел по пяти интервалам.

	  // for test rnd() function
	
	#ifndef _TESTRND_CPP_
	#define _TESTRND_CPP_
	
	#include <stdio.h>
	#include <math.h>
	#include "utils.h" //for rnd()
	
	// number of intervals
	#define _N_ 5
	#define DEFAULT_MAX_RND 10
	
	const char prog_name[]="testrnd";
	
	int main(int argc,char *argv[])
	{
		float *RndData; // store random numbers
		int NumberOfIterations;
		uint MaxRnd;
		int i; // counter
		float x;
		float average;
		int r1=0,r2=0,r3=0,r4=0,r5=0; 
			// for calculate number of random numbers in various intervals
	
		if(argc<2)
		{
	printf("Usage:\n%s <number of iterations> <random max(divisible on 5)>\n",prog_name);
	return -1;
		}
		NumberOfIterations=atoi(argv[1]);
		if(argc<3)
			MaxRnd=DEFAULT_MAX_RND;
		else
			MaxRnd=atoi(argv[2]);
	
		if(NumberOfIterations==0 || MaxRnd==0)
		{
	printf("Number of iterations and random max must be more than zero!\n");
			return 2;
		}
		// print parameters
	printf("parameters:\nNumber of iterations: %d\nrandom max: %d\n",NumberOfIterations,MaxRnd);
		average=0;
		RndData=new float[NumberOfIterations];
		if(RndData==NULL)
		{
			printf("Cant allocate memory for RndData !\n");
			return 3;
		}
		for(i=0;i<NumberOfIterations;i++)
		{
			//\/\/\/\/\/\/\/\/\//
			x=rnd(MaxRnd+1);
			//\/\/\/\/\/\/\/\/\//
			RndData[i]=x;
			average+=x;
			// calculate number of random numbers in various intervals
			if(x<MaxRnd/5)
				r1++;
			else
			{
				if(x<2*MaxRnd/5)
					r2++;
				else
				{
					if(x<3*MaxRnd/5)
						r3++;
					else
					{
						if(x<4*MaxRnd/5)
							r4++;
						else
						{
							if(x<=MaxRnd)
								r5++;
						}
					}
				}
			}
		}
		average/=NumberOfIterations;
	
		//---------- calculate dispersion  ---------------
		float Dispersion=0,fx=0;
		for(i=0;i<NumberOfIterations;i++)
		{
			fx+=(RndData[i]-average)*(RndData[i]-average);
	//		printf("%1.3f\n",RndData[i]);
		}
		Dispersion=fx/(NumberOfIterations-1);
		Dispersion=sqrt(Dispersion);
		//---------- calculate dispersion end ------------
	
		printf("-------------------\n");
		printf("Average:\t %1.3f\n",average);
		printf("Dispersion:\t %1.3f\n",Dispersion);
		printf("<%d:\t\t %d\n",MaxRnd/5,r1);
		printf("<%d:\t\t %d\n",2*MaxRnd/5,r2);
		printf("<%d:\t\t %d\n",3*MaxRnd/5,r3);
		printf("<%d:\t\t %d\n",4*MaxRnd/5,r4);
		printf("<%d:\t\t %d\n",MaxRnd,r4);
		printf("-------------------\n");
		printf("Number of intervals (n): %d\n",_N_);
		printf("1/n:\t\t %1.3f\n",(float)1/_N_);
		printf("p1:\t\t %1.3f\n",(float)r1/NumberOfIterations);
		printf("p2:\t\t %1.3f\n",(float)r2/NumberOfIterations);
		printf("p3:\t\t %1.3f\n",(float)r3/NumberOfIterations);
		printf("p4:\t\t %1.3f\n",(float)r4/NumberOfIterations);
		printf("p5:\t\t %1.3f\n",(float)r5/NumberOfIterations);
		printf("-------------------\n");
	
		delete []RndData;
		RndData=NULL;
		return 0;
	}
	#endif //#ifndef _TESTRND_CPP_
	  

Этот исходничек - только скромный пример проверки ГСЧ. Для более серьёзной работы рекомендую использовать замечательную утилиту ENT (см. [6])

ГПСЧ в сети и не только ...
Открываю газету, вижу рекламу firewall-а и что же я там читаю...

... техника "захвата сеанса" IP известна с середины 80-х годов. По сути, для фальсификации IP-адреса требуется "угадать" порядковый номер TCP-пакета. В большинстве реализаций TCP/IP используется простой аддитивный алгоритм приращения порядковых номеров, поэтому для нарушителя не составляет труда угадать следующий номер пакета в рамках соединения (даже имея всего один перехваченный пакет), чтобы с этого момента захватить связь. Брандмауэры Cisco серии PIX Firewall если не исключают, то сильно затрудняют возможность угадывания порядковых номеров TCP, генерируя их с помощью специального алгоритма псевдослучайных чисел;


Конечно это не самая популярная уязвимость - если просмотреть архив уязвимостей, то уязвимость ГСЧ пренебрежимо(?!) мала, по сравнению с Buffer Overflow и Format String Vulnerability =).
Но, как говорится, на безрыбье и рак - рыба :-)
Тем более эту уязвимость порой достаточно просто эксплуатировать; например, существует такая проблема, как ­конкуренция доступа к каталогу /tmp:
эта проблема возникает, когда программа с правами другого пользователя(например root ;) создаёт в каталоге /tmp временный файл, если файл с таким именем уже есть, то функция open() завершится и вернёт его дескриптор программе. Т.о. злоумышленник может создать символическую ссылку на любой файл в системе и с нужным именем поместить её в каталоге /tmp, что позволяет ему уничтожить системные файлы. Тут главное - кто первым успеет создать временный файл(в этом и состоит конкуренция). Казалось бы, есть простой выход - создавать временные файлы со случайными именами... ,но это решение тоже уязвимо - можно создать много ссылок с "верными" именами и любая верная ссылка сделает свою работу!

А для многих программ надёжность ГСЧ не только один из критериев успеха, но и условие хм... выживания...:
Вот,например, что говорится в статье "История одной уязвимости" (почитать можно на [2]).

Code Red, очевидно, не мог достичь всех возможных целей, ввиду ограничения интервала псевдослучайно генерируемых ip-адресов. Сразу после публикации анализа червя появляется его второе поколение. Новый червь стал незначительной модификацией первоначального варианта. Отличие заключалось в исправленном алгоритме генерации ip-адресов...
...
Обратимся к коду размножения. Этот код базируется на генераторе псевдослучайных ip-адресов, который можно описать следующим фрагментом на Си:

 
	     DWORD GetRandomIp(DWORD ThreadCounter)
	{
	 DWORD ResultIP;
	 SYSTEMTIME systime;
	 DWORD temp1, temp2, temp3;
	 DWORD SecMilisec;
	 ResultIP = ThreadCounter*0x50F0668D;
	 GetSystemTime(&systime);
	 memcpy(&SecMilisec, &systime.wSecond, sizeof temp);
	 temp1 = SecMilisec*SecMilisec*0xCD59E3;
	 temp2 = SecMilisec*0x1E1B9;
	 temp3 = ResultIP + temp1;
	#ifdef  CRv1
	 temp2 = temp2 + temp3;
	#else
	 ResultIP = temp2 + temp3;
	#endif
	 ResultIP = ResultIP*0xCF3383 + 0x76BFE53;
	 temp2 = ResultIP & 0xff;
	 if ((temp2 == 127) || (temp2 == 224)) {
	  ResultIP = ResultIP + 0x20DA9;
	 }
	 return ResultIP;
	}
	
Из листинга видно, что алгоритм сменился во втором поколении червя. Вероятно, была просто поправлена ошибка.

Генерируемый ip-адрес является функцией 3х параметров:

номер потока (1-100),
текущая секунда (0-59),
текущая миллисекунда (0-999).

Отсюда максимально возможный неповторяющийся набор получаемых адресов равен:

100*60*1000 = 6000000 = 6 млн. ip-адресов.

Понятно, что все заявления по поводу инфицирования практически всех возможных целей не имеют под собой основания. 6 млн. ip-адресов это только 0,1 % всех теоретически возможных ip-адресов.

Эту же проблему не обошёл своим вниманием и знаменитый Крис Касперски в статье [7].

При условии, что выбор IP-адреса заражаемой жертвы происходит по более или менее случайному закону (а большинство червей распространяются именно так), по мере насыщения сети червем скорость его распространения будет неуклонно снижается и вовсе не потому, что магистральные каналы окажутся перегруженными! Попробуйте сгенерировать последовательность случайных байт и подсчитайте количество шагов, требующихся для полного покрытия всей области от 00h до FFh. Очевидно, что за 100h шагов осуществить задуманное нам ни за что не удастся. Если только вы не будете жульничать, одни и те же байты будут выпадать многократно, в то время как другие останутся не выпавшими ни разу! И чем больше байт будет покрыто, тем чаще станут встречаться повторные выпадения! Аналогичным образом дело обстоит и с размножением вируса. На финальной стадии размножения полчища червей все чаще будут стучаться в уже захваченные компьютеры, и гигабайты сгенерированного ими трафика окажутся сгенерированными впустую.

Как видите - у вирусов и червей ГСЧ вообще является одним из важных органов =).

Чаще всего (можно сказать - почти всегда) - инициализация ГПСЧ происходит вызовом различных вариаций функции time() , а далее работает рекурентная последовательность.

В качестве примера приведён код ГПСЧ нашумевшего вируса mydoom.

	    static DWORD xrand16_seed;
	
	void xrand_init(void)
	{
		xrand16_seed = GetTickCount();
	}
	
	WORD xrand16(void)
	{
		xrand16_seed = 0x015a4e35L * xrand16_seed + 1L;
		return ((WORD)(xrand16_seed >> 16L) & (WORD)0xffff);
	}
	
	DWORD xrand32(void)
	{
		return xrand16() | (xrand16() << 16);
	}
	    

"Чем меньше мы знаем, тем больше можем сказать - любопытный парадокс всех наук, связанных со статистикой и с теорией вероятностей."
Аркадий Стругацкий "Дни кракена"

В качестве заключения
Наступает новое время - всё меняется; и вот уже появляются процессоры со встроенными ГСЧ.
Примером является камень от VIA Technologies(www.via.com.tw) с ядром 'Nehemiah'(the First x86 Processor to Market with Embedded Security Features).
А вот, что говорится об этом ядре:

At its heart is an advanced Random Number Generator (RNG) that uses random electrical noise on the chip to securely produce random number values, and features a direct application level interface through a new x86 instruction. Developers can obtain random numbers directly from the hardware without having to use separate software drivers, thereby providing an inherently more secure and efficient solution than combined hardware/software RNG architectures. The RNG includes several operating modes, offering performance from 750K bits per second to as high as 6 million bits per second.

"VIA's incorporation of a hardware random number source on the processor die is exciting for developers, since it provides a simple and effective way of obtaining high quality randomness. This is particularly important for security and cryptography applications, since it is notoriously difficult to generate random numbers of adequate quality without a hardware random number generator," said Paul Kocher, President of Cryptography Research, Inc. and co-inventor of SSL 3.0. "I am enthusiastic about the benefit to applications such as secure web browsing, cryptographic key generation, and protocols where randomness is required."

После этого можно было бы начать говорить о "скорой" кончине ГПСЧ, но этот разговор я предоставлю другим (потому что сам так не считаю ;).

СЧ по-прежнему нужны; не только криптографам - даже астрономам требуется их использовать (см. статью "Фотографии кошек помогут изучать галактики" от 15 сентября 2004 на [10]), но стоит понять, что отчасти именно ГПСЧ виновники тех "смертей интернета", которые раз в 5-6 месяцев прогнозируют антивирусные компании.

Продолжение следует...

Дополнительная информация
1. www.bugtraq.ru
2. www.security.nnov.ru
3. www.securitylab.ru
4. www.random.org
5. RFC 1750
6. www.fourmilab.ch/random/
Программу ENT можно скачать по адресу www.fourmilab.ch/random/random.zip
7. Крис Касперски Жизненный цикл червей
статью можно почитать на wasm.ru
8. Брюс Шнайер Прикладная криптография
В in-et-е можно найти электронный вариант книги (к сожалению я не помню :( где скачал эту книгу(в формате .pdf))
9. http://www.cs.berkeley.edu/~daw/rnd/
- большое количество ссылок на ресурсы(eng), посвящённые RN.
10. www.membrana.ru

P.S.
Эта статья является некоторым итогом серии выпусков, рассылки Моделирование Виртуальной Вычислительной Системы. В этой статье автор выражает некоторые суждения, которые могут быть весьма спорными, не претендуя на истину в последней инстанции и глубину своих познаний в данной области автор с благодарностью готов выслушать замечания и дополнения.

P.P.S.
В статье использованы вырезки из различных источников. Авторский текст оставлен без редактирования с моей стороны (т.е. даётся AS IS).

Удачи!

noonv [AT] narod [.] ru

XIII

или введите имя

CAPTCHA