A method of authenticating a mobile device over Bluetooth advertisements according to one embodiment includes broadcasting, by an access control device, a first Bluetooth advertisement including a challenge message generated by the access control device, receiving, by the mobile device, the first Bluetooth advertisement including the challenge message, broadcasting, by the mobile device, a second Bluetooth advertisement including a challenge response message generated by the mobile device based on the challenge message, receiving, by the access control device, the second Bluetooth advertisement including the challenge response message, and determining, by the access control device, whether the mobile device is authorized to perform an action with respect to the access control device by verifying the challenge response message.