You don't need to compute the challenge in N nanoseconds. Instead, the car could send a challenge, the key can compute it in however much time it likes. Then the car sends a one time pad, the key receives it and xors the otp with the challenge's response. Then it sends that.

The cryptographic challenge makes it secure, the XORed one-time-pad allows for fast measurement of the round trip time.