I have built a GPS based on the AVR microcontroller. The GPS is used to log flight data for competitions. The log file is updated 10 times per second. What I'd like to do is to associate a signature with this file so that anyone can confirm that the file was written by the GPS.

This suggests that the GPS should have a private key of some sort internally, and that verification should occur through a public key. However, there are a couple of significant hardware limitations:

  1. The AVR is an 8-bit processor running at 8 MHz. I can keep a running MD5 hash of the file, but there is not enough time between samples to calculate, e.g., an ECDSA signature.
  2. The hardware does not know when it will shut down. When the user turns off the switch, it just shuts down. This means it is not possible to perform the hash/signature once just before shutdown. The signature would have to be updated every time a new row is added to the log file, i.e., 10 times per second.

Something like an HMAC would fit the processor limitations, but not the necessity of public verification. Is there some variant of an HMAC which can be computed using a private key and then verified using a public counterpart?

Thanks for your help!

| improve this question | | | | |
  • 2
    $\begingroup$ If there was such a variant, don't you think everybody would be using it? ;) $\endgroup$ – SEJPM Jan 21 '17 at 19:44
  • $\begingroup$ Would you have bandwidth to trade signature size for speed? Could you use the bandwith for doing pre-computations? $\endgroup$ – SEJPM Jan 21 '17 at 19:47
  • 1
    $\begingroup$ I'm sure if there were such a variant it would be quite popular, but sometimes searching for something becomes a lot easier once you know what it's called. I was hoping someone might comment to say, "Oh, yes, that's called xxx and it's quite common." $\endgroup$ – Michael Cooper Jan 21 '17 at 20:08
  • $\begingroup$ What kind of pre-computations do you have in mind? I have about 50 ms of unused time between samples, so about 400,000 clock cycles. This doesn't go very far on an 8-bit microcontroller. $\endgroup$ – Michael Cooper Jan 21 '17 at 20:14
  • 2
    $\begingroup$ You could sign several samples at a time. If you sign blocks of 20 samples then you have 8,000,000 clock cycles between signatures. (Your signing code will have to be able to be interrupted in the middle to take samples) $\endgroup$ – user253751 Jan 22 '17 at 0:30

Signature algorithms of the ECDSA family are amenable to precomputations. Indeed, when you want to sign message m with ECDSA, the process goes thus:

  • We work in a curve (or a subgroup of a curve) of order $n$ (a prime integer). A conventional generator $G$ is given (a fixed point of order $n$). Private key is $x$ (a non-zero integer modulo $n$) and public key is point $Q = xG$.

  • Generate (for each signature) a new random non-zero integer $k$ modulo $n$. The integer MUST be selected uniformly in the whole range (this is important).

  • Compute the point $kG$, extract its $X$ coordinate, and reduce it modulo $n$; this yields the first half of the signature, $r$.

  • Hash message $m$ and truncate/reduce the hash value into an integer modulo $n$ (let's call it $h$).

  • Compute the second half of the signature: $s = (h+xr)/k \pmod n$

The point here is that the most expensive part, which is the computation of $kG$, does not actually depend on the message that is to be signed. It can thus be done in advance, before the message $m$ is obtained. A precomputing setup would pre-generate a bunch of values $k$, with corresponding values $r$ and $1/k \pmod n$, thereby reducing the online part of the signature to a couple of modular multiplications and a modular addition. This, however, calls for the following comments:

  • The process above requires a random $k$, produced with a random generator of cryptographic quality. This is a tough thing to get in practice, especially on embedded systems. Since a failure to use good randomness may expose the private key itself (and such blunders have happened in practice), another mechanism for generating the $k$ value has been defined, called derandomization. In the case of ECDSA, this is described in RFC 6979. However, while this removes the need for a random source, it makes $k$ depend on the input message $m$. As such, it prevents precomputations.

  • ECDSA, as defined by the relevant standards, operate on "classic" curves, which are not necessarily the fastest curves around. You might want to investigate EdDSA, and especially Ed25519 (application of EdDSA to a specific 255-bit curve). This can be done, but may run into some extra issues:

    • EdDSA is specified as derandomized, so no precomputations. It so happens that the signature verifier cannot actually know whether the signer was derandomized or not, so you could "re-randomize" the algorithm, which is totally heretic from a cryptographic point of view, and thus possible but fraught with peril.

    • The actual signature computation uses a hash function invocation, which is defined to be SHA-512. SHA-512 is reasonably efficient... on big desktop and servers, where 64-bit registers are available. Your 8-bit AVR won't like it.

  • Precomputations can help you only if you have time to precompute. The typical use case for precomputations is paying a toll on a highway or bridge: the signing device on a car has very little time to compute the actual signature (transaction should be completed while the wireless device is in range of the detection apparatus, and that does not last because the car does not slow down), but minutes if not hours to prepare the next signature. In your case, you have a long and potentially unbounded stream of signatures to compute, so it is not obvious whether you have enough time to do all precomputations.

To give some figures, the current record for elliptic curve computations on 8-bit AVR processors is described in this paper; they compute a point multiplication in Curve25519 in about 14 millions of clock cycles. This is substantially higher than your budget (at 0.400 millions of cycles per signature).

Here are some ideas that may help (or not):

  • "Modern" curves such as Curve25519 are designed under the essential premiss that multiplications are fast. This is true for the CPU in desktop and server systems, and also smartphones. But not on 8-bit AVR. Therefore, they are not necessarily a good choice in your specific case.

  • I suppose that the value of your signatures is not that high. I mean, you worry about fakes, but a fake log will not yield billions of dollars to attackers. As such, you could probably tolerate a slightly lower level of security. A 160-bit or so curve will provide a security level of about $2^{80}$, which is beyond the current public records in curve breaking. This is technologically attainable, but at a tremendous expense (we are talking billions of dollars here), so it is unlikely to be done merely in order to make fake GPS log (I assume you are talking about drone racing or something similar).

  • Under these conditions, I would say that among known curves, the fastest one will probably K-163, described in FIPS 186-4. This curve has a special structure that allows faster computations, provided that you apply some weird maths (the Frobenius endomorphism). However, even with the full power of the Frobenius, I fear that it would still not fit the per-signature cost in 400k clock cycles.

  • The human user is human; he is not that fast. By that, I mean that while you cannot predict when the user will pull the switch, you can still instruct the said user that pulling the switch may lose, say, the last two seconds of GPS logs. Therefore, you could compute one signature every 2 seconds, on twenty lines of logs in one go, instead of doing ten signatures per second. I have just multiplied your CPU budget by 20! And now, ECDSA with K-163 may become a realistic solution.

  • You might want to consider plugging in a better CPU. In a GPS receiver, chances are that the radio part uses way more power than the CPU, so you could use a more beefy CPU. The ARM Cortex-M0+, clocked at 48 MHz, would draw at most a few milliwatts (including the power for some RAM), and can compute an Ed25519 signature in less than 200ms.

Another, completely different idea, would be to use Lamport's signature scheme. It uses only hash functions and can be very fast. Its main issue is that it is a one-time signature scheme: if you sign two distinct messages with the same private key, then you reveal the private key, and forgeries become easy. However, in your specific case, you could apply it in the following way:

  • Before a flight, the GPS system generates a new public/private key pair, and exports the public key.
  • During the flight, the system regularly computes a new signature over the entirety of the log file, and replaces the previous signature. Thus, it only keeps a single signature in its storage system. This uses the fact that the private key is revealed only through showing two signatures; signature values that are never shown are thus not a problem.
  • The private key is held in RAM only, so it disappears when the system shuts down.

To ease usage, you could envision an hybrid system:

  • The system has a "permanent" key pair, to use in ECDSA or Ed25519 or a similar system.
  • When it boots up, it generates a new Lamport public/private key pair.
  • The public key is signed with the ECDSA/Ed25519/whatever key; the Lamport public key and the signature are then stored along in the log file header.
  • The running Lamport signature is computed every second or so, as described above.
  • The Lamport private key disappears upon shutdown.

Combining all of the ideas above makes me think that what you are looking for is possible, but certainly not commonplace. You are in for a big delve in arcane cryptography, and we know, out of experience, that such things are hard, in particular because there is no test for security (you can test for functionality, but you cannot easily know whether what you produced is secure).

So, a fun project, but don't build a business on it.

| improve this answer | | | | |
  • 1
    $\begingroup$ Depending on what the OP is using to store the log data, reliably overwriting old Lamport signatures could be tricky, especially if they also want to minimize wear on the storage device. But your suggestion of only signing the log at intervals of, say, a few seconds seem sound. $\endgroup$ – Ilmari Karonen Jan 22 '17 at 10:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.