Security protocols operating over wireless channels can incur significant communication costs (e.g., energy, delay), especially under adversarial attacks unique to the wireless environment such as signal jamming, fake signal transmission, etc. Since wireless devices are resource constrained, it is important to optimize security protocols for wireless environments by taking into account their communication costs. Towards this goal, we first present a novel application of a signal-flow-based approach to analyze the communication costs of security protocols in the presence of adversaries. Our approach models a protocol run as a dynamic probabilistic system and then utilizes Linear System theory to evaluate the moment generating function of the end-to-end cost. Applying this technique to the problem of secret key exchange over a wireless channel, we quantify the efficiency of existing families of key exchange cryptographic protocols, showing, for example, that an ID-based approach can offer an almost 10-fold improvement in energy consumption when compared to a traditional PKI-based protocol. We then present a new key exchange protocol that combines traditional cryptographic methods with physical-layer techniques, including the use of “ephemeral” spreading codes, cooperative jamming, and role-switching. Utilizing signal flow analysis, we demonstrate that this new protocol offers performance advantages over traditional designs.