jueves, 18 de septiembre de 2014

Diffie-Hellman key agreement

Diffie-Hellman protocol.

Chinese remainder theorem

Exponenciación modular

Algoritmo de Euclides y algoritmo extendido de Euclides

Factorización de un número

Test de primalidad

viernes, 12 de septiembre de 2014

The importance of randomness in security

Randomness is an important topic for a great number of persons, from scientists to philosophers, because of many questions around it. Although it's not obvious to many people, randomness is present in many aspects of our lives, like in videogames, simulations and even in security [1]. The latter is to main focus in this essay, because randomness is very important in various techniques related to safe activity in computer based information systems, such as in Internet browsing or in the use of cash machines.

What makes a number to be a random number?

For many mathematician and scientists, random numbers must be unknowable and unpredictable. This numbers also should pass many statistical test of uniformity [2], such as the chi-squared test or the Kolmogorov-Smirnov test.

The security in a cryptographic system (hereafter the cryptosystem) is strongly related to techniques that require random sequences for many different purposes [3]. One of the most important elements in cryptography are the cryptographic keys which determine the transformation of the plaintext into ciphertext and vice versa. Considering many of this algorithms are publicly known, the security in a cryptosystem is dependent on how the keys are managed, generated, transmitted, stored and destroyed.

Pseudo-Random Number Generators

In this point one can assume that random numbers are very important for many different reasons, but another question arises, how to generate good random numbers? In practice Pseudo-Random Number Generators (hereafter PRNG) are used, which are algorithm that generate pseudo-random numbers [4]. A PRNG works when an initial value is given to the algorithm as a seed, which ideally must be truly random [3], for generate a new number.

The core components of a PRNG are [4]: an internal state which consists of all the parameters, variables and other stored values that the PRNG uses for its operations, and the entropy source which is the source of randomness (seed) to update said internal state.

Usually the entropy sources come from changes in the physical environment of the device [7], such changes in the temperature, changes in the voltage or frequency of the power supply, exposure to radiation, etc. Many modern operating system, like Linux [6], have a PRNG implementation, where their entropy source comes from to the aforementioned sources and other sources, such as keystroke, mouse clicks, disk I/O.

If it is very difficult to access to a hardware entropy source, it is recommend to obtain random input from a large of uncorrelated sources and to mix them with a strong mixing function [5]. This function should preserve the randomness present in any of the sources even if other quantities are easily guessable.

Security notions in a PRNG

In security there is a notion about adversaries [4]: there are those who have access to the output of the generator, those who can control (partially or totally) the source of the generator and those who can control (partially or totally) the internal state of the generator, or any combination of them. Various standards define several desirable security properties of a PRNG [4] involving this notion of the adversary:
  • Resilience: an adversary must not to be able to predict future PRNG outputs even if he can influence the entropy source.
  • Forward security: an adversary must not to be able to predict future PRNG outputs even if he can compromise the internal state of the PRNG.
  • Backward security: an adversary must not to be able to predict past PRNG outputs even if he can compromise the internal state of the PRNG.
  • Entropy preservation [6]: the generator must preserves the entropy of the internal state after the output and refresh operations, in other words, the entropy must not to decrease.
In the Barak and Halevi PRNG model they define a new security property called robustness [4] that implies the aforementioned properties. This property actually assesses the behavior of a PRNG after compromise of its internal state [8], implying that even an observer with knowledge and control of the components of the PRNG can not distinguish the output of the generator from an endless string of random bits.

So, randomness is very important, right?

I think that because the today massive exchange of information, it is good have a bit of paranoia regarding about our security. For this very reason the security in the communication channels is so important to many people, because their personal, private information can be compromised if it is accessible to malicious people.

Maybe it is funny when a friend play a joke to us, but I don't think that it would be funny if someone “plays” with confidential information which it must be secret to almost everyone. Specially if it is regarding money or something very personal, of course.


[1] Jon Callas, "Using and Creating Cryptographic-Quality Random Numbers", 1996. https://www.merrymeet.com/jon/usingrandom.html
[2] Banks, Carson, et al, "Discrete-event System Simulation". https://cs.wmich.edu/~alfuqaha/Spring09/cs6910/lectures/Chapter7.pdf
[3] Márton, Suciu, et al, "Generation and Testing of Random Numbers for Cryptographic Applications", 2012.. http://www.acad.ro/sectii2002/proceedings/doc2012-4/11-Suciu.pdf
[4] Dodis, Pointcheval, et al, "Security Analysis of Pseudo-Random Number Generators with Input: /dev/random is not Robust". https://eprint.iacr.org/2013/338.pdf
[5] Eastlake, Crocker, Schiller, "Randomness Recommendations for Security", 1994.. http://www.hjp.at/doc/rfc/rfc1750.html
[6] Ruhault, "Barak-Halevi pseudo-random number generator model extended with applications to /dev/random". http://webmath.univ-rennes1.fr/c2/Soumissions_C2/c2_Ruhault.pdf
[7] Barak, Shaltiel,Tromer, "True Random Number Generators Secure in a Changing Environment". http://www.math.ias.edu/~boaz/Papers/trng.pdf
[8] Barak, Halevi, "A model and architecture for pseudo-random generation with applications to /dev/random", 2005. https://eprint.iacr.org/2005/029.pdf