A random number you already have: The stack address

June 5, 2022 software python rust stack

Summary

Linux, macOS, and other operating systems use Address Space Layout Randomization (ASLR) for security, slightly randomizing the stack and heap addresses of programs. This allows us to leverage a local stack variable's address to generate a pseudo-random number, but we need to truncate the value to ignore irrelevant bits. In Rust, we can obtain a random number by converting a stack variable's address to a u32, while in Python, we adapt the method to account for specific bits. However, this technique doesn’t work in Go due to the managed nature of Go routines, which store stack memory on the heap. I discovered this method while analyzing Rust's hashmap implementation, which uses stack addresses to enhance hash randomness and resist denial of service attacks. You can verify ASLR's effect on randomness by toggling it off in your system settings, causing the output to become constant.

For security reasons Linux, macOS and others will slightly randomize the address at which your program’s stack and heap start. This is called Address Space Layout Randomization (ASLR).

Hence in many languages we can use the address of a local (stack) variable as a budget random number.

Stack addresses on 64-Linux always start with 0x00_00_7f so we need to ignore at least the top three bytes. Truncating to a u32 will do. Here it is in Rust:

fn main() {
    let i = 0;
    let r = &i as *const _ as u32;
    println!("{r}");
}

It seems to work fairly well in Python (CPython) too. The main difference is that the bottom 14 bits of a stack address are always 00000011010000 (0x0d0). I don’t know why this is, but it’s an interpreted language, it makes no promises. We drop the top three bytes and bottom 14 bits, giving us 26 bits (0x3ffffff) of randomness.

Here it is in Python (CPython, because it relies on the implementation of id):

def rand():
    i = 0
    return (id(i) >> 14) & 0x3_ff_ff_ff

print(rand())

This does not work in Go because we are always in a managed go-routine. The memory we use as our stack appears to be actually on the heap.

I learnt this from looking at Rust’s hashmap. It’s default hasher uses the stack address as a number to randomize the mapping of keys to backing array indexes. This helps aHash resist denial of service attacks and avoid a pathological performance case (see Design).

You can confirm that the randomness is caused by ASLR by disabling it:

echo 0 | sudo tee /proc/sys/kernel/randomize_va_space
# Enable: echo 2 | sudo tee /proc/sys/kernel/randomize_va_space

Now you should get the same value every time.

Graham King