Efficient Authentication Mechanisms for Navigation Systems – a Radio-Navigation Case Study

Georg T. Becker, Sherman C. Lo, David S. De Lorenzo, Di Qiu, Chris­tof Paar, Per Enge

Proceedings of the 22nd International Technical Meeting of the Satellite Division of the Institute of Navigation (ION GNSS 2009) pp. 901 - 912, September 22-25 2009, Savannah, GA.


In this paper we introduce an efficient authentication mechanism especially designed for navigation systems that is based upon the Timed Efficient Stream Loss-Tolerant Authentication (TESLA) algorithm. We analyze the different attack scenarios on navigation systems and show that it is only necessary to authenticate the source and time of the signals to enable a secure position determination. Traditional message authentication is only needed to prevent counterfeit correction message attacks. With this knowledge and a detailed security analysis of the needed key size, we developed adjusted TESLA, an authentication mechanisms that can authenticate the source and time-messages using only 80 bits. One of the reasons why we can use such a small authentication message is due to the insertion of a timestamp into the generation of the one-way chains. This significantly increases the security of adjusted TESLA compared to the original TESLA and enables us to use a smaller key size. Adjusted TESLA has a about a 75% smaller size than traditional digital signatures that have signature sizes of at least 320 bits. To prevent counterfeit correction message attacks additional 32 or 40 bits are needed for the transmission of a MAC. But this is still an improvement of at least 62.5% compared to digital signatures or the first proof-of-concept implementation of TESLA in eLORAN. This enables us to significantly improve the security of navigation systems by using only a very small data rate. We propose the use of adjusted TESLA in eLORAN. With this security improvement and LORAN’s strength against over-the-air attacks, eLORAN will not only be a backup for current GNSS systems, but will be a real alternative for current civil GNSS systems in application that require the highest possible security level against attacks.