  Medium Access Control (MAC) address randomization is a key component for
privacy protection in Wi-Fi networks. Current proposals periodically change the
mobile device MAC addresses when it disconnects from the Access Point (AP).
This way frames cannot be linked across changes, but the mobile device presence
is exposed as long as it remains connected: all its communication is trivially
linkable by observing the randomized yet same MAC address throughout the
connection. Our runtime MAC re-randomization scheme addresses this issue,
reducing or eliminating Wi-Fi frames linkability without awaiting for or
requiring a disconnection. Our MAC re-randomization is practically
'over-the-air': MAC addresses are re-randomized just before transmission, while
the protocol stacks (at the mobile and the AP) maintain locally the original
connection MAC addresses - making our MAC layer scheme transparent to upper
layers. With an implementation and a set of small-scale experiments with
off-the-shelf devices, we show the feasibility of our scheme and the potential
towards future deployment.
