A method and a wireless device for exchanging messages with an access point (AP) while the wireless device is in a pre-associated state during which the wireless device is unauthenticated and is not associated with a network. The wireless device receives a beacon from the AP indicating that the AP will protect messages communicated with the wireless device. The wireless device then sends to the AP a message including a request for information from the AP. The wireless device obtains a public key of the AP, and receives an encrypted response to the request and an encrypted symmetric key. The wireless device decrypts the encrypted symmetric key using the public key of the AP to recover a symmetric key that is not encrypted, and decrypts the encrypted response to the request using the decrypted symmetric key to recover a response to the request that is not encrypted.