4 ms·
Galileo's Proposed Authentication Algorithm: Part 1
- eximius 6y agoVery interesting, but what stops an adversary from spoofing a key 6' that was derived from 5 in the same way the network might? The same verification would derive 5 from 6', then 4, down to 0. What secret does the network have that allows for the next keygen to be done only by them? EDIT: Does the network generate all X keys in advance in reverse or something?
- vii 6y agoYes, the network works back from the signed key, which is published last. The TESLA scheme uses a one-way pseudo-random hash function to generate keys, see this paper https://www.esat.kuleuven.be/cosic/publications/article-2749.pdf https://www.esat.kuleuven.be/cosic/publications/article-2749... so if you know the signed key you can generate the others. That means you can't easily fork a new chain with a K_6' as the receiver can easily check f(K_6') = K_5 where f is a hash function that is hard to reverse. Once the key has been published, an adversary can use it to generate messages. A requirement in TESLA is that there is close time-synchronisation between the sender and receiver. This is enforced by the safe-packet test as defined in https://tools.ietf.org/html/rfc4082 https://tools.ietf.org/html/rfc4082 which checks that the message packet was received within the time window expected from key signing. As the satellite positioning systems depend heavily on highly synchronised clocks this is pretty reasonable.
- espadrine 6y agoYou might notice that one of the author of this document is casually the creator of the most widely used cipher in the world.
- RcouF1uZ4gsC 6y agoThat would be Vincent Rijmen of AES and SHA-3 fame.
- ris 6y agoThe article makes a good description of the problem, explains how the solution works, but doesn't really explain why the solution solves the problem. How can it protect against a delayed identical signal being re-transmitted at a higher power by a relay station? All its cryptography will check out. How does the key being transmitted afterwards actually help it? If we need a chain of message keys to be able to decode a block of messages, and messages frequently go missing, doesn't this mean missing a message in the chain makes authenticating any later (er... previous?) messages of the block impossible?
- oritsnile 6y agoThere a certain time windows where a key is valid, so you can delay a few days for example (keys are disclosed either after 30s or 5min). You can really protect against real time replay of the signal, at least not in the authentication protocol. But there are other Methods of detecting relays. The delayed publication of the key give the algorithm the needed asymmetricity. Since a key only authenticates message in a specific time window, attackers can't reuse the key once it's out there. Regarding your last point, you can reconstruct "used" key with new keys. The keys are basically generated with K_{n-1} = F(K_n), where F is a hash function. So with the current key you can authenticated all previous messages.
- petertodd 6y agoThat's an excellent point. But IIUC it can be solved with a local clock of sufficient accuracy by making sure you got the message for the right time, at the right moment. This is now even feasible for handheld equipment, as "chip scale" atomic clocks are now commercially available, with dimensions on the order of a few cm on each side. This one is based on Rubidium: https://www.microsemi.com/product-directory/embedded-clocks-frequency-references/5207-space-csac https://www.microsemi.com/product-directory/embedded-clocks-..., and here's another based on cesium: http://www.jackson-labs.com/index.php/products/csac http://www.jackson-labs.com/index.php/products/csac At one point Digikey was even stocking them as an off-the-shelf item! Relatively cheap too, "just" thousands of dollars per unit.
- cryptonector 6y ago
- petertodd 6y agoNote that this is an example of the broader timestamped HMAC signature scheme concept. My Google-fu isn't up to the task today. But I'm sure I've seen proposed before, eg with something like Bitcoin as the timestamp provider. My OpenTimestamps project is a curious example where I actually made an effort to avoid implementing this by accident. tl;dr: It's a service that does Bitcoin timestamping. In the process, centralized servers generate "calendars" - the database of digests they've timestamped. Now, for disaster recovery the calendar servers have a HMAC with secret key to authenticate digests they've promised to timestamp. The idea being that the HMAC lets us get timestamps back from the community to re-add to the calendar in case the data somehow gets lost. For technical reasons, that HMAC "signs" the current time, and the output of that HMAC gets timestamped securely with Bitcoin. But since OTS servers are not supposed to be trusted, that HMAC digest is deliberately truncated to 64 bits to make it feasible to brute force with significant effort, thus making them not useful as an actual timestamp: https://github.com/opentimestamps/opentimestamps-server/blob/1b191439f66d603d3d5d32a60b691ce8c92746ad/otsserver/calendar.py#L30 https://github.com/opentimestamps/opentimestamps-server/blob... This is ok for their intended purpose, because if you're willing to brute force 64-bits, I'm ok letting you add some junk to the OTS calendars in the event of a disaster. I'm actually considering using that scheme as a trusted timestamping mechanism for OTS, by simply revealing the HMAC keys after they've been timestamped by Bitcoin. They're already derived with a merkle tree from a single seed - each second gets a different HMAC key. To turn that into a verifiable signature you just need to derive all the keys in advance, construct a tweaked version of that merkle tree, and then publish the root. A full signature is then the HMAC output, and a path up the tree to the public root. The advantage for OTS is the amortized size of the signatures would be smaller than a ECC signature, plus being hash based it's a quantum resistant scheme.
- londons_explore 6y agoYour comment here would make a lot more sense to someone outside the project if you have a one-sentence summary about what opentimestamps tries to offer.
- petertodd 6y ago