Re: machine independent protection from stack-smashing attack

[Ariel Waissbein <core.lists.bugtraq () CORE-SDI COM>]

There are a few remarks I want to make about previous posts on this subject. I find
people talking about randomness and while not making explicit a precise definition.
The approach followed is ingenious implementation-wise, but evades the theoretical
issue of randomness and gives no statement towards this end.

What would be the ``correct" definition of randomness for cryptographic purposes?
Who knows? Pseudorandom generator are more easily defined. And however at
least three different definitions could be used for this purpose, they are Shannon's,
Kolmogorov's, and the one which Blum, Goldwasser, Micali and Yao gave in the
papers [GoMi82], [BlMi84] and [Yao85]. This one is highly regarded by the computer
scientist community this days. And is also --in today's knowledge-- the most security-
and efficiency-aimed for cryptographic purposes. Oded Goldreich explains it ``is rooted
in complexity theory", and then ``Lloosely speaking, a random generator is an efficient
program (or algorithm) that stretches short random strings into long pseudorandom
sequences" ([Goldreich00]). There is also the different distributions followed by certain
properties of certain particles such as fotons, which is the cornerstone of the quantum
key exchange protocol of [BennettBrassard84] and [Wiesner83].

In the preceding posts, it seems,  random pools and random generators are treated as
they were the same object. When they are not. In particular I want to point out that a
bit array of, say, n bits, passing a statistical test such as Kolmogorov-Smirnov, or the
like (see [Knuth2]), need not be secure for cryptographic purposes. Namely, the source
of that array needs to be studied. For example, the array defined by the 2-adic (binary)
representation of pi is RANDOM, however it is not CRYPTOGRAPHICALY SECURE
RANDOM. (Because an efficient  program writing this array is existent.) To this end, the
Kolmogorov or the Blum-Micali-Goldwasser-Yao definition are far more complexity-
aimed.


Yarrow Charnot wrote:

> Not true! There sure are and have always been sources of randomness on all the platforms. It just always comes down 
> to proper implementation. Sure you would need to add processor-dependent code for each platform, but there sure is a 
> portable source of randomness available. It's called RDTSC on Intel, %tick on SPARC, etc. and it's a base for 
> /dev/random anyway. However, the

This is not exactly accurate, meaning that any output from a specific microchip
used by a specific person follows a probability distribution, which is with high
probability different from random. Hence, my previous comment on randomness.
Furthermore, in certain cases this distributions can be calculated, and predictions
made (as in the case of pi). See for example works on Power Analysis, SPA and
DPA (linear or differential power analysis) such as [KoJaJu99] and [Kocher96].
There have also been, and continue to be, attacks such as the well known
TEMPEST ([Tempest]), in which technology plays an important role (see [AnKu]
and the bibliography therein). There are also well funded organizations ``making
in-depth analysis of the system, designing sophisticated attacks, and the most
advanced analysis tools" ([AndersonKuhn96], see also [Gutmann96]).


> authors of /dev/random didn't conduct any research on its behaviour, missing out on its true power.
>
> In any case a portable source of randomness is not the reason why StackGuard hasn't been ported to more 
> architectures. Microsoft purposedly doesn't allow pages to be non-executable, leaving an easily exploitable hole to 
> allow NSA hack into any Windows server or workstation exploiting buffer overflows. Products like StackGuard are the 
> only hope for many software developers.
>
> And if a reliable source of randomness is really such a problem, I'm ready to share with you my (you can call it more 
> random than /dev/random) random number generator based on the real power of the clock counter.

It is towards this discussion that I direct you to the power analysis research papers quoted above, and the
product of www.Musicrypt.com for Biometric User Verification using the keystroke profile of individuals.
Specifically, you can not rely the security of your random number generator in the alleged noise on the
peripherals of a terminal and, thus, have to make additional computations. It is in this additional computations
that your security should rely. There have been research activity in the vein of the proposed PRNGs (see
[DavisIhakaFenstermacher94], [EastlakeCrockerSchiller94], [Gutmann96] and [KelseySchneierFerguson98]).
Sources of randomness and random generation are studied. However this works lack a comprehensive
cryptanalytic analysis, and only the latter focuses on some possible attacks.

> Although strong on its own, I'd recommend adding a hash function of your choice and uncommenting bigrand to have a 
> cryptographically strong RNG. Otherwise returns truly random 64-bit numbers any time.

---------
BIBs

[AndersonKuhn96] Ross Anderson and Markus Kuhn, ``Tamper Resistance - a Cautionary Note" ,
second USENIX Workshop on Electronic Commerce Proceedings, Oakland, California,
November 18-21, 1996, pp 1-11. Best paper at conference award.

[BennettBrassard84] C.~H. Bennett and G.~Brassard.``Quantum cryptography: public key
distribution and coin tosing", In Proc. Internat. Conf. Computer Systems and Signal
Processing, pp 175-179. Bangalore, 1984.

[BlMi84] M. Blum and S. Micali ``how to generate cryptographically strong sequences
of pseudo-random bits", SIAM Journal of Computing, vol. 13, pp 850-864, 1984.

[DavisIhakaFenstermacher94] D. Davis, R. Ihaka, and P. Fenstermacher,  ``Cryptographic
Randomness from Air Turbulence in Disk Drives", Advances in Cryptology - CRYPTO '94
Proceedings, Springer-Verlag, 1994, pp. 114-120.

[EastlakeCrockerSchiller94] D. Eastlake, S.D. Crocker, and J.I. Schiller, ``Randomness
Requirements for Security", RFC 1750, Internet Engineering Task Force, 1994.

[Goldreich00] O. Goldreich, ``Pseudorandomness". Download from
http://www.wisdom.weizmann.ac.il/~oded/PS/prg99.ps

[GoMi82] S. Goldwasser and S. Micali ``Probabilistic encryption", Journal of computer
and system science, vol.28(2), pp 270-299.

[Gutmann96] Peter Gutmann, ``Secure Deletion of Data from Magnetic and Solid-State
Memory", second USENIX Workshop on Electronic Commerce Proceedings, Oakland,
California, November 18-21, 1996.

[Gutmann98] P. Gutmann, ``Software Generation of Random Numbers for Cryptographic
Purposes", Proceedings of the 1998 Usenix Security Symposium, USENIX
Association, 1998, pp. 243-257.

[KelseySchneierFerguson98] J. Kelsey, B. Schneier and N. Ferguson, ``Yarrow 160:
notes and analysis of the yarrow cryptographic pseudorandom number generator",
Sixth Annual Workshop on Selected Areas in Cryptography, Springer Verlag,
August 1999, to appear.

[Kocher96] P. Kocher ``Timing attacks on Implementations of Diffie-Hellman, RSA, DSS
and Other Systems, Advances in Cryptology - CRYPTO 96, pp 104-113, 1996.

[KoJaJu99] P. Kocher, J. Jaffe and B. Jun ``Differential power analysis", Advances in
Cryptology - CRYPTO 99, ed. M. Wiener, pp.388-397, 1999.

[Knuth2] Donald E. Knuth, ``The art of computer programming (vol. 2)", Addison
Wesley.

[Tempest] The complete unofficial TEMPEST web page. Available at
http://www.eskimo.com/~joelm/tempest

[Wiesner83] S.~Wiesner. ``Conjugate coding", Sigact News, 15(1):77-88, 1983.

[Yao85] A.C. Yao ``Theory and applications of trap door functions", In 23rd IEEE
Symposium on foundations of computer science, pp 1-10, 1985.


------

Finally, I remark that -as far as I know- there has not been any breakthru in the random number
generation following the approach suggested in the previous posts. And no sound proofs of these
PRNG's security are available. The subject of seeding, and entropy measurement remain obscure.
And only random number generators in the sense of BMGY have been broadly studied. However
this subject of study is still open and, as I briefly exposed above, many questions remain to be
answered. I hope that this post contributes to the implementation of random-number/random-pool
generators. Bye.


    Ariel Waissbein.




--
==================[ CORE Seguridad de la Informacion S.A. ]=========
Ariel Waissbein
Researcher - Corelabs

email :  ariel_waissbein () core-sdi com             http://www.core-sdi.com
=========================================================

I was scared. Petrified. Because (x) hearing voices isn't like catching a cold,
you can't get rid of it with lemmon tea (y) it's inside, it is not some naevus,
an epidermal blemish you can cover up or cauterise (z) I had no control over it.
It was there of its own volition, just stopped in and (zz) I was going bananas.
-Tibor Fischer ``TheThought Gang"




--- For a personal reply use wata () core-sdi com