Syndrome-Fortuna: A viable approach for Linux random number generation

  • Sérgio Vale Aguiar Campos UFMG
  • Jeroen van de Graaf UFMG
  • Daniel Rezende Silveira UFMG


This work presents a random number generator based on the intractability of an NP-Complete problem from the area of error-correcting codes. It uses a non-heuristic approach for entropy collection, taken from the Fortuna design philosophy. We implemented the new generator inside the Linux kernel, providing an alternative system interface for secure random number generation.


Augot, D., Finiasz, M., and Sendrier, N. (2005). A family of fast syndrome based cryptographic hash functions. In Dawson, E. and Vaudenay, S., editors, Mycrypt 2005, volume 3715, pages 64–83. Springer.

Berlekamp, E., McEliece, R., and Van Tilborg, H. (1978). On the inherent intractability of certain coding problems (corresp.). IEEE Transactions on Information Theory, 24(3):384–386.

Chabaud, F. (1994). On the security of some cryptosystems based on error-correcting codes. In EUROCRYPT, pages 131–139.

Ferguson, N. and Schneier, B. (2003). Practical Cryptography. Wiley & Sons.

Fischer, J.-B. and Stern, J. (1996). An efficient pseudo-random generator provably as secure as syndrome decoding. In EUROCRYPT, pages 245–255.

Goldberg, I. and Wagner, D. (1996). Randomness and the Netscape browser. Dr. Dobb’s Journal of Software Tools, 21(1):66, 68–70.

Goldreich, O. (2001). Foundations of Cryptography. Volume I: Basic Tools. Cambridge University Press, Cambridge, England.

Goldreich, O., Krawczyk, H., and Michael, L. (1993). On the existence of pseudorandom generators. SIAM J. Computing, 22(6):1163–1175.

Impagliazzo, R., Levin, L., and Luby, M. (1989). Pseudorandom generation from one-way functions. In Proc. 21st Ann. ACM Symp. on Theory of Computing, pages 12–24.

L’Ecuyer, P. and Simard, R. (2007). Testu01: A c library for empirical testing of random number generators. ACM Transactions on Mathematical Software, 33(4).
Como Citar

Selecione um Formato
CAMPOS, Sérgio Vale Aguiar; VAN DE GRAAF, Jeroen; SILVEIRA, Daniel Rezende. Syndrome-Fortuna: A viable approach for Linux random number generation. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 11. , 2011, Brasília. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2011 . p. 122-135. DOI:

Artigos mais lidos do(s) mesmo(s) autor(es)