From: Yarrow Charnot [ycharnot@IDENTIKEY.COM] Sent: Thursday, August 10, 2000 6:06 PM To: BUGTRAQ@SECURITYFOCUS.COM Subject: Re: machine independent protection from stack-smashing attack ----- Original Message ----- From: John Viega To: Sent: Thursday, August 10, 2000 8:05 PM Subject: Re: machine independent protection from stack-smashing attack > Our understanding is that the biggest reason why StackGuard hasn't > been ported to more architectures is that there's not really a > portable source of randomness available, such as a /dev/random. 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 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. 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. --------chrand.c-------- /* Yarrow Random Number Generator (True Randomness Achieved in Software) */ /* Copyright (c) 1998-2000 by Yarrow Charnot, Identikey */ /* All Lefts, Rights, Ups, Downs, Forwards, Backwards, Pasts and Futures Reserved */ /* To compile on Sun: gcc -m32 -msupersparc -mcpu=v8 -g -O3 -finline-functions -Wa,-xarch=v8plusc -Winline -lrt */ /* To compile on Intel, MSVC with /G6 /Gr /O2 and with either /MT or /MD is recommended */ /* If you want to export any of the following functions, you know what to do */ #include #include #include #if defined (WIN32) || defined (_WIN32) || defined (WIN32_WINNT) || defined (_WIN32_WINNT) || defined (__WIN32__) || defined (WINDOWS) || defined (_WINDOWS) #include #define thread_yield() Sleep(0) #else #include #define thread_yield() sched_yield() #define _rmtmp() #endif #ifdef _MSC_VER #include #pragma intrinsic (_lrotr, _lrotl) #define ASM __asm #if defined(_M_IX86) || defined(__i386__) static __forceinline unsigned __int64 __fastcall clock_counter (void) { __asm {_emit 0x0F} __asm {_emit 0x31} } #pragma warning (push) #pragma warning (disable:4035) static __forceinline unsigned __int32 __fastcall bswap32 (unsigned __int32 x) {__asm mov eax,x __asm bswap eax} #pragma warning (pop) #else extern unsigned __int64 clock_counter (void); /* Alpha or Motorola clock counter compiled separately */ #define bswap32(x) (rotl32 ((unsigned __int32)(x), 8) & 0x00ff00ff | rotr32 ((unsigned __int32)(x), 8) & 0xff00ff00) #endif #else /* GCC or CC then */ #define __int8 char #define __int16 short #define __int32 long #define __int64 long long #define __cdecl #define __fastcall #define __forceinline __inline__ #define ASM __asm__ #define _lrotr(x, n) ((((unsigned __int32)(x)) >> ((int) ((n) & 31))) | (((unsigned __int32)(x)) << ((int) ((32 - ((n) & 31)))))) #define _lrotl(x, n) ((((unsigned __int32)(x)) << ((int) ((n) & 31))) | (((unsigned __int32)(x)) >> ((int) ((32 - ((n) & 31)))))) #if defined (_M_IX86) || defined (__i386__) && defined (__GNUC__) static __inline__ unsigned long long clock_counter (void) { __asm__ (".byte 0x0F, 0x31" :"=a", "=d"); } #elif defined (sparc) || defined (__sparc) || defined (sun) || defined (__sun) && defined (__GNUC__) static __inline unsigned long long clock_counter (void) { register unsigned long x, y; __asm__ __volatile__ ("rd %%tick, %0; clruw %0, %1; srlx %0, 32, %0" : "=r" (x), "=r" (y) : "0" (x), "1" (y)); return ((unsigned long long) x << 32) | y; } #else extern unsigned __int64 clock_counter (void); /* one of the above or any other clock counter function compiled separately */ #endif #define bswap32(x) (rotl32 ((unsigned __int32)(x), 8) & 0x00ff00ff | rotr32 ((unsigned __int32)(x), 8) & 0xff00ff00) #endif #define rotr32(x, n) _lrotr (x, n) #define rotl32(x, n) _lrotl (x, n) #ifndef _OCTET_ #define _OCTET_ typedef union _OCTET { unsigned __int64 Q[1]; unsigned __int32 D[2]; unsigned __int16 W[4]; unsigned __int8 B[8]; } OCTET; #endif #define NK 257 /* internal state size */ #define NI 120 /* seed in increment */ #define NA 70 /* rand out increment A */ #define NB 139 /* rand out increment B */ typedef struct _ch_randgen { OCTET ira[NK]; /* numbers live here */ OCTET *seedptr; /* next seed pointer */ OCTET *rndptrA; /* randomizing pointer #1 */ OCTET *rndptrB; /* randomizing pointer #2 */ OCTET *rndptrX; /* main randout pointer */ OCTET rndLeft; /* left rand accumulator */ OCTET rndRite; /* rite rand accumulator */ } ch_randgen; /* extern void hash_block (const unsigned __int8 *block, const unsigned __int32 block_byte_size, unsigned __int8 *hash); */ #define HASH_BITS 192 /* I use Tiger. Modify it to match your HASH */ #define HASH_BLOCK_BITS 512 /* I use Tiger. Modify it to match your HASH */ #define HASH_BYTES (HASH_BITS / 8) #define HASH_BLOCK_BYTES (HASH_BLOCK_BITS / 8) #define HASH_OCTETS (HASH_BITS / 64) #define HASH_BLOCK_OCTETS (HASH_BLOCK_BITS / 64) /* attach by Yarrow Charnot. attaches x to y. can be seen as about 2-3 rounds of RC6 encryption */ __forceinline void __fastcall attach (OCTET *y, const OCTET *x, const unsigned __int32 anyA, const unsigned __int32 anyB, const unsigned __int32 oddC, const unsigned __int32 oddD) { register OCTET _x; register OCTET _y; _x.D[0] = x->D[0]; _x.D[1] = x->D[1]; _y.D[0] = y->D[0]; _y.D[1] = y->D[1]; _x.D[0] = rotl32 ((bswap32 (_x.D[0]) | 1) * x->D[1], 5); _x.D[1] = rotl32 ((bswap32 (_x.D[1]) | 1) * x->D[0], 5); _y.D[0] = (bswap32 (rotl32 (_y.D[0] ^ _x.D[0], _x.D[1])) + anyA) * oddC; _y.D[1] = (bswap32 (rotl32 (_y.D[1] ^ _x.D[1], _x.D[0])) + anyB) * oddD; y->D[1] = _y.D[0]; y->D[0] = _y.D[1]; } /* detach by Yarrow Charnot. detaches x from y. can be seen as about 2-3 rounds of RC6 decryption */ __forceinline void __fastcall detach (OCTET *y, const OCTET *x, const unsigned __int32 sameA, const unsigned __int32 sameB, const unsigned __int32 invoddC, const unsigned __int32 invoddD) { register OCTET _x; register OCTET _y; _x.D[0] = x->D[0]; _x.D[1] = x->D[1]; _y.D[0] = y->D[1]; _y.D[1] = y->D[0]; _x.D[0] = rotl32 ((bswap32 (_x.D[0]) | 1) * x->D[1], 5); _x.D[1] = rotl32 ((bswap32 (_x.D[1]) | 1) * x->D[0], 5); _y.D[0] = rotr32 (bswap32 (_y.D[0] * invoddC - sameA), _x.D[1]) ^ _x.D[0]; _y.D[1] = rotr32 (bswap32 (_y.D[1] * invoddD - sameB), _x.D[0]) ^ _x.D[1]; y->D[0] = _y.D[0]; y->D[1] = _y.D[1]; } /* QUICKLY seeds in a 64 bit number, modified so that a subsequent call really "stirs" in another seed value (no bullshit XOR here!) */ __inline void chseed (ch_randgen *prandgen, const unsigned __int64 seed) { prandgen->seedptr += NI; if (prandgen->seedptr >= (prandgen->ira + NK)) prandgen->seedptr -= NK; attach (prandgen->seedptr, (OCTET *) &seed, 0x213D42F6U, 0x6552DAF9U, 0x2E496B7BU, 0x1749A255U); } /* The heart of Yarrow 2000 Chuma Random Number Generator: fast and reliable randomness collection. */ /* thread yielding function is the most OPTIMAL source of randomness combined with a clock counter. */ /* it doesn't have to switch to another thread, the call itself is random enough. test it yourself. */ /* this FASTEST way to collect minimal randomness on each step couldn't use the processor any LESS. */ /* even functions based on just creation of threads and their destruction can not compare by speed. */ /* temporary file creation is just a little extra thwart to bewilder the processor cache and pipes. */ /* if you make clock_counter return all 0's, still produces a stream indistinguishable from random. */ void reseed (ch_randgen *prandgen, const unsigned int inittimes) { unsigned int i, j; OCTET x, y; for (j = inittimes; j; j--) { fclose (tmpfile ()); for (i = NK * inittimes; i; i--) { thread_yield (); y.Q[0] += clock_counter (); attach (&x, &y, 0x52437EFFU, 0x026A4CEBU, 0xD9E66AC9U, 0x56E5A975U); attach (&y, &x, 0xC70B8B41U, 0x9126B036U, 0x36CC6FDBU, 0x31D477F7U); chseed (prandgen, y.Q[0]); } } _rmtmp (); } /* returns a 64 bit of Yarrow 2000 Chuma RNG random number */ __inline unsigned __int64 chrand (ch_randgen *prandgen) { prandgen->rndptrX ++; prandgen->rndptrA += NA; prandgen->rndptrB += NB; if (prandgen->rndptrX >= (prandgen->ira + NK)) { prandgen->rndptrX -= NK; reseed (prandgen, 1); } if (prandgen->rndptrA >= (prandgen->ira + NK)) prandgen->rndptrA -= NK; if (prandgen->rndptrB >= (prandgen->ira + NK)) prandgen->rndptrB -= NK; attach (&prandgen->rndLeft, prandgen->rndptrX, prandgen->rndptrA->D[0], prandgen->rndptrA->D[1], 0x49A3BC71UL, 0x60E285FDUL); attach (&prandgen->rndRite, &prandgen->rndLeft, prandgen->rndptrB->D[0], prandgen->rndptrB->D[1], 0xC366A5FDUL, 0x20C763EFUL); chseed (prandgen, prandgen->rndRite.Q[0]); return prandgen->rndRite.Q[0] ^ prandgen->rndLeft.Q[0]; } /* returns a 32 bit random number */ __inline unsigned __int32 chrand32 (ch_randgen *prandgen) { OCTET r = {chrand (prandgen)}; return r.D[0] ^ r.D[1]; } /* generates a cryptographically secure random big number 0 <= x < 32^n */ /* automatically reseeds if necessary or if requested 1/16 of the internal state or more */ /* __inline void bigrand (ch_randgen *prandgen, unsigned __int32 *x, unsigned __int32 n) { unsigned int i; OCTET block[HASH_BLOCK_OCTETS]; OCTET hash[HASH_OCTETS]; OCTET *j; if (n >= NK/8) reseed (prandgen, 1); for (*x++ = n; (signed) n > 0; ) { for (i = 0; i < HASH_BLOCK_OCTETS; i++) block->Q[i] += chrand (prandgen) + hash->Q[i % HASH_OCTETS]; hash_block (block->B, HASH_BLOCK_BYTES, hash->B); for (i = HASH_OCTETS, j = hash; i && ((signed) n > 0); i--, j++, x += 2, n -= 2) { attach ((OCTET *) &x, j, 0x0AEF7ED2U, 0x3F85C5C1U, 0xD3EFB373U, 0x13ECF0B9U); } } } */ /* Initializes Yarrow 2000 Chuma Random Number Generator */ /* reseeding about 8 times prior to the first use is recommended. */ /* more than 16 will probably be a bit too much as time increases by n^2 */ __inline ch_randgen *new_chrand (const unsigned int inittimes) { ch_randgen *prandgen; prandgen = (ch_randgen *) malloc (sizeof (ch_randgen)); prandgen->seedptr = prandgen->ira; prandgen->rndptrX = prandgen->ira; prandgen->rndptrA = prandgen->ira; prandgen->rndptrB = prandgen->ira; prandgen->rndLeft.Q[0] = 0x1A4B385C72D69E0FUL; prandgen->rndRite.Q[0] = 0x9C805FE7361A42DBUL; reseed (prandgen, inittimes); prandgen->seedptr = prandgen->ira + chrand (prandgen) % NK; prandgen->rndptrX = prandgen->ira + chrand (prandgen) % NK; prandgen->rndptrA = prandgen->ira + chrand (prandgen) % NK; prandgen->rndptrB = prandgen->ira + chrand (prandgen) % NK; return prandgen; } /* Clean up after chuma */ __inline void kill_chrand (ch_randgen *randgen) { memset (randgen, 0, sizeof (ch_randgen)); free (randgen); } int __cdecl main (void) { ch_randgen *rng; rng = new_chrand (8); /* ....... use the generator ....... good luck breaking it! ....... any critic is welcome ....... send it to /dev/null ....... */ kill_chrand (rng); } --------chrand.c-------- ------------------------------------------------------------- Identikey - The Key To Internet Security ------------------------------------------------------------- - Yarrow Charnot Chief Security Advisor Identikey (Australia) Pty Ltd https://www.identikey.com ------------------------------------------------------------- The views expressed in this message are those of the individual sender, except where the sender specifically states them to be the views of Identikey (Australia) Pty Ltd. -------------------------------------------------------------