Geekly Articles each Day
📜 ⬆️ ⬇️

Python random number security

This article is the second in a series of publications devoted to the vulnerabilities of pseudo-random number generators (PRNG).

Recently, a number of publications have appeared that describe the PRNG vulnerabilities, starting from the very foundations ([1]) and ending directly with vulnerabilities in various programming languages ​​and CMS and other software implemented on their basis ([2], [3], [4] ).

These publications are popular because PRNG is the basis of many aspects of web application security. Pseudo-random numbers / character strings are used to secure the web applications in:
')

In the last article , based on the research of George Argyros and Aggelos Kiayias ([3]), we learned how to predict random numbers in PHP based on PHPSESSID and reduce the entropy of pseudorandom numbers in various ways.

We will now look at PRNG in web applications developed in Python.

Python PRNG Features


In Python, there are three modules designed to generate random / pseudo-random numbers: random , urandom, and _random :


Random ()

The first uses the MT algorithm (the _random module), but first of all it tries to initialize it with the help of SEED taken from urandom , which turns PRNG into RNG (random number generator). If you cannot call urandom (for example, / dev / urandom is missing or you cannot call the desired function from advapi32.dll ), then int (time.time () * 256) is used as SEED (which, as you already know, provides insufficient entropy).

SYSTEMRANDOM ()

SystemRandom () calls the urandom module, which uses external sources to generate random data.

The change in the implementation of the MT algorithm is that instead of a single number based on one of the 624 numbers from the current PRNG state ( state ), two numbers are used:

random_random() { unsigned long a=genrand_int32(self)>>5, b=genrand_int32(self)>>6; return PyFloat_FromDouble((a*67108864.0+b)*(1.0/9007199254740992.0)); }

Also, unlike PHP, the generator can be initialized not only with a long variable, but also with any sequence of bytes ( init_by_array () is called ) , which happens when the random module is imported using an external entropy source (32 bytes are taken from urandom ), and in case this fails, time () is used :

 if a is None: try: a = int.from_bytes(_urandom(32), 'big') except NotImplementedError: import time a = int(time.time() * 256)

Protection


It would seem that these changes, in contrast to PHP, provide sufficient generator entropy even when calling random.random () . But it is not all that bad".

A special feature of Python frameworks is that, unlike PHP, Python is run once with the web server, which means that the initialization of the default state occurs once when you execute the import random command or when you force a random.seed () call (this is extremely a rare case for web applications), which allows for an attack on the MT state according to the following algorithm:


The accuracy of determining the states depends on the index of the state element ( i ): for i mod 2 = 0, the entropy is 2 ^ 6 , for i, mod 2 = 1 - 2 ^ 5 .

Further, using queries 1,2,199,200, you can define the states state_1 [1] , state_1 [2] , state_1 [3] , state_1 [397] , state_1 [398] , on the basis of which the states state_2 [1] and state_2 [2] are generated, from which the random number of inquiry No. 313 also turns out. However, the entropy of this number is 2 ^ 24 (16M) . Entropy is reduced by queries 511 and 625 . These queries help calculate state_2 [397] , state_3 [1] . This reduces the number of variants of states to 2 ^ 8 , i.e. There are a total of 256 variants of the “random” number used in query No. 313 .

A necessary condition for the execution of an attack is that no one gets stuck in the query process, thereby having no effect on the change of the PRNG status (in other words, the state indexes will be determined correctly). It is also necessary that query No. 1 uses elements of the PRNG status with indexes not exceeding 224 , otherwise query No. 200 will use a different state of the generator, which will not allow the execution of the angiorithm. The probability of this event is 36% .

Therefore, the additional task of query # 625 is to determine that all previous requests were actually made in the required states and no one has entered the query process.

In addition, we bring to your attention a script that receives random numbers of 6 queries at the input. At the output, all possible random numbers of query # 313 are formed .

Practical use


We analyzed several frameworks and web applications in the Python language (among them Plone and Django). Unfortunately, (and perhaps fortunately) it was not possible to find the vulnerable among them.

The most likely challenger is Plone, since it has the output of a random number ( SiteErrorLog.py ), but the problem of attacking it is as follows. Plone works under Python 2.7. * , Which, when outputting float to str (), truncates the last 5 digits, which expands the number of enumerated variants (both for local iteration and external requests to the server) to very large numbers.

Python of the third branch does not cut float in the st () r function, which makes applications on it the main contenders for carrying out attacks.

We bring to your attention a script that receives 6 random numbers at the input (initialized with a state with the necessary indices, for example, from the vuln.py test script), and at the output generates possible variants of the random number being matched. The running time of this scenario on an average computer is about an hour.

Note: this scenario does not take into account the possible error in determining the state element for (i mod 2 = 1), therefore, the efficiency decreases from 36% to 18%.

Conclusion


Features of executing Python framework code (on the web server side) allow an attacker to conduct attacks that are impossible or very difficult to implement in PHP. To protect the PRNG you need to follow simple rules:


Links


[1] http://habrahabr.ru/post/151187/
[2] http://jazzy.id.au/default/2010/09/20/cracking_random_number_generators_part_1.html
[3] http://crypto.di.uoa.gr/CRYPTO.SEC/Randomness_Attacks_files/paper.pdf
[4] http://www.slideshare.net/d0znpp/dcg7812-cryptographyinwebapps-14052863
[5] http://media.blackhat.com/bh-us-10/presentations/Kamkar/BlackHat-USA-2010-Kamkar-How-I-Met-Your-Girlfriend-slides.pdf
[6] http://en.wikipedia.org/wiki/Mersenne_twister
[7] http://jazzy.id.au/default/2010/09/22/cracking_random_number_generators_part_3.html

Author: Yunusov Timur.

Source: https://habr.com/ru/post/156133/

More articles:


All Articles