Techniques are provided that rotate a device address used to identify a wireless client device on a wireless network. The wireless client device and at least one network infrastructure component identify a plurality of device addresses associated with the wireless client device. In some embodiments, the plurality of device addresses are generated via a corresponding plurality of invocations of a stateful random number generator, such as a cryptographically secure pseudorandom number generator.