A method of authenticating an agent to a secure environment of a device, in a challenge-response authentication sys tem comprising the device, a remote authentication server and a connection path between the device and the remote authentication server, the method comprising: while the connection path is not established:—obtaining a predictable challenge based on at least a current value of a counter;—obtaining a response for the challenge; and,—authenticating the agent to the secure environment based on at least the response; and, wherein, upon successful authentication, the value of the counter is incremented. A challenge-response authentication system and an apparatus are also claimed.