Hey @de0u, thanks for the detailed answer!
de0u The baseline Android protocol doesn't support MAC randomization, so using Bluetooth will often leak a largely-permanent device identifier to nearby observers. This is all independent of any particular app's interest in Bluetooth information.
Yeah, that makes sense. I've set it to automatically turn off after 5 minutes of inactivity and I normally turn it off manually once I'm done with it anyway. Honestly if someone wanted to track me, Bluetooth would probably be the least reliable way of doing so, so it's not really a part of my threat model.
de0u With respect to the particular app (not named so far), it's not clear why it should demand the Nearby Devices permission. Perhaps it's just sloppy coding (see "Hanlon's Razor").
It seemed unusual to me as well, that's why I decided to ask here. At least it's only required for using my bluetooth headset and not for all functionality. I guess I'll be walking around with wired headphones more often.
de0u Personally I don't think I'd leave Nearby Devices on for that app permanently, and I might try to avoid using the app at all.
Sounds like a good idea. I wish I didn't need to use the app but I have no other choice in my country, almost everyone uses it (or a couple other much worse apps).