If the AP and client possess a shared secret (as in WPA2), then there's no reason for a third party to be able to deduce any identifying information.
Okay. How would you design a system to permit associated or unassociated stations to passively determine whether or not they were in range of a given AP? Remember that human-friendly names for a given AP are almost certain to collide.
Simple protocol: The AP and client have shared secret K (similar to the present WPA2 key). We define the identity of a network as this secret key. The AP can change "BSSID" every hour, while broadcasting [BSSID, Hash(BSSID, K)]. An interested client runs through their database of known private networks, checking if the broadcaster is any they know.
This obviously has a number of shortcomings (eg our attacker is also known to groom people into uploading K to their silos), but it should illustrate the concept.
That solves the problem for clients that have connected to that AP before. [0]
How do you propose to solve the problem for clients that have never interacted with that AP before?
[0] It probably actually doesn't, but I won't distract you with why at the moment. :)
Okay, I'm a little confused, please bear with me.
Are you designing two half systems, one of which periodically changes BSSID but provides no other anonymity protection, and the other which hashes the BSSID with the WPA2 PSK?
Or are you designing one system with a rotating BSSID that transmits -in cleartext- the BSSID and the hashed BSSID?
It's obviously impossible to have a publicly-available network that hides its existence to the public (while a private network can obviously hide its existence to the public completely), so each problem will obviously have different ideal solutions.
It's the merging and the details of the same that's the complicated bit, and the only thing worth talking about in this sub-thread.
You made the assertion that the "the committees designing [wireless communications] protocols don't think [that things screamed on the street corner are public data]". [0] This is simply not true. The folks who designed 802.11 had to make several key-management-complexity/computational-power/ease-of-use tradeoffs.
> ...while a private network can obviously hide its existence to the public completely...
Not if it's a relatively-high-performance radio network operating in a relatively tiny slice of spectrum, [1] it can't.
[0] https://news.ycombinator.com/item?id=10950276
[1] As 802.11b/g/n does
A high-bandwith radio transmitter obviously gives its presence up, but that doesn't mean it needs to identify itself. Of course the FCC likes transmitters to do this, but that too is an anti-feature with respect to public-use spectrum.
There were obviously tradeoffs involved for 802.11, which is how we got WEP. I'd just be surprised if having a (semi-)fixed MAC address was ever questioned, given that it's the basis for 802.3 and leaking some associated identity is basically a forgone conclusion in today's world of license plates, etc. But with the obvious effects of mechanized tracking and aggregation, it really shouldn't be. So I stand by my assertion that the designers would have benefited from a perspective where being pushed to do the equivalent of continually shouting/showing one's identity is a very bad thing.
So. How would you design a system to permit associated or unassociated stations to passively determine whether or not they were in range of a given AP? Remember that unassociated stations may never have ever interacted with the AP in question before this moment.