A fundamental problem in security is authentication: namely, how to verify the identity of another party. Without this verification, the ideas of privacy and integrity are moot. Modern authentication techniques use cryptographic operations that secure the system against adversaries that do not have tremendous amounts of computation and memory. However, when the abilities of the adversary increase, such authentication paradigms become more susceptible to defeat. With the greater threat of defeat, the secret authentication keys must be replaced more often. Unfortunately, the popular key replacement algorithms typically rely on either third parties or on non-trivial computational ability. In this thesis we attack these two aspects of the authentication problem by presenting novel methods for authentication and key replacement in wireless environments.

We describe how to exploit the randomness of the physical layer to hide the authentication from adversaries. Typically, no effort is made to hide the authentication - it is sent in plain view of friend and foe alike. The proposed technique reveals significantly less key information than traditional authentication methods and can increase the data throughput of the system. We define metrics to quantify the performance of the proposed authentication system and use them to study the associated tradeoffs. A software radio implementation is then presented to demonstrate the feasibility of the proposed scheme.

Finally, we consider how secret keys can be replaced in an efficient manner. We describe a novel method of key replacement and generation that, unlike other methods, requires no additional message exhanges after initialization and yet generates highly random keys. As an added benefit, the method is shown to be extremely lightweight in terms of computation and memory requirements.