Hash for use in embedded HMAC application

Question

I developed a GNSS logger (http://flysight.ca) which has become popular for scoring skydiving competitions. At the moment, there is little protection against competitors falsifying tracks, but I would like to change that.

The device uses an 8-bit AVR microcontroller. Memory and clock cycles are extremely limited. Because of the hardware design, the device has no warning when it is being turned off. This means it is not possible, e.g., to perform a computationally intensive signature only when the log file is closed.

The competition occurs over a few days. There is a central PC-based scoring system which is used to initialize and read data from the GNSS loggers.

Given these conditions, what I have in mind is the following:

1. The scoring system generates a unique random key at the start of the event.
2. Each GNSS logger is initialized with this key, which can be stored securely.
3. When a row is written to the log file, a cumulative signature is computed using an HMAC based on the key generated in (1).

Alas, even MD5 exceeds the resources I have available, so I am wondering if the modest security requirements (in particular, that signatures need only be secure for a few days) might allow me to use a faster hash function.

If you have a different idea, I'd love to hear that, too. Thanks so much for your help!

Answer 1

As cheaper alternatives to HMAC with modest security goals, consider:

1. SipHash—cheaper than MD5 because you don't have to pay for collision resistance; security is limited by the 64-bit output size
2. Maybe a Gimli-based PRF—Gimli is a new compact design
3. Derive a fresh key for each message, and use a one-time authenticator like a polynomial evaluation universal hash family such as Poly1305 or GHASH—extremely cheap to evaluate
4. Conceal a universal hash family output with a short-input, short-output PRF—faster than evaluating a generic long-input PRF

Of course, whether these actually provide security for your application depends on a lot more than the formal unforgeability properties of the cryptography. No cryptography can prevent physical interference with the GNSS signals, for example! With all of these systems, anyone who can verify log messages can also forge them—to separate the ability to verify from the ability to forge, you need public-key signatures, which are tremendously costlier.

To be clear: I don't suggest that you go out and invent new compositions of primitives right now along the lines I sketched above. Rather, I suggest you spend effort now articulating your security model, so that you can focus your effort on implementing a design that confidently provides the security you're hoping for, rather than spend weeks micro-optimizing Poly1305 and SipHash for your AVR microcontroller, only to find that you actually need signatures, not authenticators.