Cryptographic pseudo-random generation of address subsets

Question

Suppose I have devices which broadcast, on an insecure channel, 32-bit addresses. I want to make these devices untraceable - one way to do so is to allocate for each device a distinct subset of address, for example $X=256$ addresses for each device with no repetitions, and make each device change its address from time to time (to a different number in its subset). A secure receiver, who knows how the addresses-subsets are separated, could trace the origin device of the address.

However, this would require to store $X$ addresses on each device.

Another way is finding some injective function $f:Z_{2^{32}} \to Z_{2^{32}}$, where the first device will calculate on-the-fly the addresses $f(0), ..., f(X-1)$, the second device will calculate $f(X), ..., f(2X-1)$, etc... However, if the code of this function falls to the wrong hands, the whole mechanism becomes worthless (I'm talking about physically breaking and reading the code secrets of one of the devices, not only reading its addresses from outside).

A third way is to have a different salt in each device and a CSPRNG executed $X$ times per device - leaving out salts that generate addresses that are "already taken" by previous devices. In this case, after some time (around $2^{32}/X$ addresses, $2^{32}/{X^2}$ devices), it will become hard to find salts that do not generate "already taken" addresses.

Is there a mechanism that is both memory efficient and secure, i.e. breaking one device won't give too much information about the addresses of other devices (except that they are different from those of the broken device), without loosing too much of the address space (keep generating "devices" easily)?

Thanks

--- EDIT ---

Fourth way: Similar to the third way, I can create create pairs of $(s_1, l_1), (s_2, l_2), ...$ where $s_i$ are randomly chosen salts and $0 < l_i \leq L$ is the number of times I can execute the CSPRNG on $s_i$ before getting a collision with an address generated by a previous $s_j$ (for $j < i$).

Then all I have to do is to give some $(s_i, l_i)$ pairs to each device so it could generate the amount of addresses I want. For example, if every $l$ is a powers of 2, I could make devices that have pairs like: $(s_{i_1}, 128), (s_{i_2}, 64), (s_{i_3}, 32), (s_{i_3}, 16), (s_{i_4}, 8), ...$, and when I run out of $(s, 128)$ pairs, have devices that have: $(s_{i_1}, 64), (s_{i_2}, 64), (s_{i_3}, 64), (s_{i_4}, 32), (s_{i_5}, 16), (s_{i_6}, 8), ...$

I am not sure about the average amount of memory I need on each device, but I know that the generated addresses can use much more than $1/256$ of the address space (suggested in the "third way"). Obviously, when it comes to pairs like $(s, 1)$ it would be more efficient to simply store the generated number...

I think there is a fundamental problem with what I'm trying to do. Informally, I am trying to allocate random numbers to each device and "compress" them. The only way to do that is to generate the numbers pseudo-randomly based on a secret, but then other devices must "know" that secret to prevent collisions - i.e. if a device is compromised then the secrets of other devices are lost too. An asymmetric mechanism is needed - knowing that an address is taken by a different device without knowing the other device's secret. I don't believe it's possible with 32-bit numbers.

Answer 1

It is possible to build a hybrid between your first two solutions, to trade off between their advantages and disadvantages.

Let $E_K : \{0,1\}^{32} \to \{0,1\}^{32}$ be a block cipher with a 32-bit block. You will select a single global key $K$, that will be stored on every device. Also, for each device, select a few starting points $s_1,\dots,s_m$, say $m=8$ of them. These are specific to each device. The idea is that the device has a pool of $nm$ addresses, namely, the values $E_K(s_1), E_K(s_1+1), \ldots, E_K(s_1+n-1)$, $E_K(s_2),E_K(s_2+1),\dots,E_K(s_2+n-1)$, $\ldots,E_K(s_m+n-1)$. Each time the device changes its address, it selects a new address from its pool -- either randomly, or cycling through the addresses in the pool, whichever you prefer. Here you should select $n,m$ so that $nm=X$, so that each device has $X$ different addresses in its pool.

Now you select different start points $s_1,\dots,s_m$ for each device, and select the starting points so the devices' address pools don't overlap. One approach is to choose each $s_i$ to be a random multiple of $n$, uniformly and independently at random, sampling without replacement (i.e., you discard a starting point if it has been previously selected). In this way, you can arrange to have up to about $2^{32}/(nm)=2^{32}/X$ devices.

This scheme requires each device to store $m+1$ values, the starting points $s_1,\dots,s_m$ and the global key $K$. The security you get is pretty decent. If no device is compromised, this scheme is as good as your first solution (and as good as you can get, assuming 32-bit addresses): it'll take $nm$ or $\approx \sqrt{nm}$ address-changes before a device ever repeats its address (depending upon how the device selects from its pool, either cycling or random selection). If a device is compromised, not all is lost: you still have some security remaining; in particular, you get security equivalent to a pool of $m$ addresses.

This now lets you tune the parameters to trade off between storage cost vs level of security. My suggestion would be to pick $m$ as large as you can reasonably afford, given the amount of storage available for this security mechanism.

As fgrieu points out, in this scheme the block cipher must have a 32-bit block size, which is not as common as 64-bit or 128-bit block, but still well studied as part of Format Preserving Encryption, including by Granboulan and Pornin (in proceedings of Fast Software Encryption 2007); Bellare, Ristenpart, Rogaway and Stegers (in proceedings of Selected Areas in Cryptography 2009); Morris, Rogaway, and Stegers (in proceedings of Crypto 2009). (Paragraph and links copied from fgrieu's comment; my thanks to fgrieu.)