Previous Abstract Return to Session A5

Session A5: Integrity and Assurance

Bitwise Asymmetric Proof-of-Life Over Low Bandwidth Channels
Peter Hokanson and Johnathan York, ARL, University of Texas at Austin
Location: Ballroom E
Date/Time: Wednesday, Aug. 25, 5:05 p.m.

As essential civilian uses of GNSS have grown in scope, the need for robust civilian anti-spoof capability has become increasingly apparent. Two main proposals have appeared to offer civilian authentication: Chimera for GPS and OS-NMA for Galileo. These use some cryptographic combination of watermarks in ranging codes and digital signatures for the navigation message. A digital signature provides proof of not only the contents of the message, but also indirectly that the transmission time is not ahead of the signed time contained within.
Existing digital signature algorithms impose limits on key performance metrics: large signatures limit time between authentications, message structures limit the rate of unpredictable symbols, and the trailing bits in signatures are predictable with sufficient effort. Current proposals require nontrivial measures to improve these metrics, including the use of multi-satellite signatures, sideband data, or minute-level authentication times.
We propose a novel cryptographic technique using established primitives that creates iterated timed bit commitments that can be evaluated with asymmetric difficulty. Knowledge of the relevant private key allows a transmitter to generate these commitments at a symbol rate that is intractable with only the public key: an adversary without the private key is unable to commit to better-than-pseudorandom data. Receivers can validate bits are authentic after linear delay, and express confidence in signal authenticity as a function of number of bits validated. Such a stream of symbols provides a proof-of-life of a transmitter across even a very low bandwidth channel, such as that used for GNSS navigation messages.
This structure consists of a time lock puzzle [1] with the chosen key encoding a function of public data including the time and some number of previous commitment bits. A one-bit hash of the locked data is used to determine the next transmitted symbol. This establishes a cryptographic channel through which signal and parity information can be passed with well-characterized error rate. The symbol rate of this channel and difficulty of each hash can be easily adjusted such that only the private keyholder can tractably generate valid signals: the ability to send known data functions as a proof of knowledge of the private key (or of an implausible amount of work).
With knowledge of the public key, validation of individual bits within the sequence is possible and parallelizable with only modest effort. Receivers may, depending on message parity data, choose to validate varying fractions of bits and express confidence in a more-continuous range.
This method potentially allows for improvement in several of the key performance metrics including a more consistent level of confidence in bit verification. We believe this is a useful building block in providing better authentication without needing secrets in receivers. While this presentation focuses on the subproblem of navigation message authentication, the full benefits of this technique are expected to be realized when this technique is incorporated into the generation of pseudorandom ranging sequences, which is currently under study. We submit this presentation to consider the navigation-related applications of this technique and expect future submissions to cryptography publications for review of its cryptographic strength.
[1] Rivest, R. L., Shamir, A. & Wagner, D. A. (1996) Time-lock puzzles and timed-release crypto.



Previous Abstract Return to Session A5