On Android, users can choose to install an application, or not, based on the permissions it requests. These permissions are later enforced on the application by the system, e.g., when accessing sensitive user data. In this work, we focus on the access to Wi-Fi related information, which is protected by the ACCESS_WIFI_STATE permission. We show that this apparently innocuous network related permission can leak Personally Identifiable Information (PII). Such information is otherwise only accessible by clearly identifiable permissions (such as READ_PHONE_STATE or ACCESS_FINE_LOCATION or ACCESS_COARSE_LOCATION). We analyzed permissions of 2700 applications from Google Play, and found that 41% of them use the ACCESS_WIFI_STATE permission. We then statically analyzed 998 such applications and, based on the results, selected 88 for dynamic analysis. Finally, we conducted an online survey to study the user perception of the privacy risks associated with this permission. Our results demonstrate that users largely underestimate the privacy implications of this permission, in particular because they often cannot realize what private information can be inferred from it. Our analysis further reveals that some companies have already started to abuse this permission to collect personal user information, for example, to get a unique device identifier for tracking across applications or to geolocalize the user without explicitly asking for the dedicated permissions. Because this permission is very common, most users are potentially at risk. There is therefore an urgent need for modification of the privileges granted by this permission as well as a more accurate description of the implications of accepting a permission.