3
$\begingroup$

I am building a small embedded system of two nodes that communicate wirelessly. The microcontrollers I'm using are very limited: they only have 256 bytes of RAM. I would like to be able to authenticate messages sent and received between the nodes, but traditional methods such as HMAC aren't possible because of the constraints of the system (lack of RAM).

I do have a large (2 megabit) EEPROM that is largely unused. I would like to use this space to store a (relatively) large one-time pad that could be used to authenticate the messages, which are only a few bytes long. I do not care about the secrecy of the messages, only their unforgeability and integrity. If only, say, 4 bytes of pad are used per message, the pad should far outlast the system's expected usefulness. Finally, messages are not guaranteed to be received by the other node (for example, due to interference, malicious or not).

Are there any schemes that use a one-time pad for message authentication? Assume the one-time pad is truly random. Or is this an entirely hair-brained idea that is inherently insecure?

Improve this question
$\endgroup$
6
  • $\begingroup$ Not hare-brained, but you need enough bits in each of message to defend against corrupted or tampered messages, which takes a lot more than 4 bits. You also need to consider how these machines will securely re-sync if a message is lost. Restarting a one-time pad would make it be more than one-time! $\endgroup$
    – John Deters
    Commented Mar 24, 2015 at 22:32
  • $\begingroup$ Well, each machine could send its current offset as part of the message. And I said 4 bytes, not bits, of pad per message. Even more is acceptable really. But I still need to sign that message using the pad somehow. $\endgroup$
    – thirtythreeforty
    Commented Mar 24, 2015 at 22:33
  • $\begingroup$ What level of integrity protection are you looking for? That is, if someone modified a packet, what is an acceptable level of probability that the modification be undetected? $2^{-16}$? $2^{-64}$? $\endgroup$
    – poncho
    Commented Mar 24, 2015 at 23:16
  • $\begingroup$ @poncho, I suppose that depends on whether someone can forge a packet from scratch. If they can, then they can brute force finding a successful packet (although this could be mitigated with backoff). I could accept 2^-16 probability if they can only modify packets that I've legitimately created. If they can just try to forge something, 2^-32 would be better. $\endgroup$
    – thirtythreeforty
    Commented Mar 24, 2015 at 23:23
  • $\begingroup$ Have you modeled the value this system is protecting? $2^{32}$ sounds like it would be very simple to brute force attack it. All an attacker needs to do is forge a key offset of 0 for each message, and he has the winning hand. I like @poncho's suggestion of using a minimal-memory strong cypher as both the encryption and hash mechanisms, which gets further away from the roll-your-own nature of the OTP suggestion. $\endgroup$
    – John Deters
    Commented Mar 25, 2015 at 1:13

1 Answer 1

Reset to default
5
$\begingroup$

Actually, it's not a hare-brained idea at all; you certainly can do integrity checking using a one-time pad. However, I believe that you'll need to use the one-time pad bits a bit faster than you'd expect, to achieve a forgery probability of at most $2^{-32}$, I believe you'll need at least 64 pad bits per packet (assuming informational theoretical security - that is, we don't include any computational problems that are too difficult for the attacker to solve).

One way to do this would be do a polynomial hash over $GF(2^{32})$; that is, you use 32 bits of the pad as a value $H$, and compute the value $V = X_i H^i + X_{i-1} H^{i-1} + ... + X_1 H^1 + R$ (where the message is $(X_i, X_{i-1}, ..., X_1$, and $R$ is 32 other bits from your pad, and where the computation is done within $GF(2^{32})$; the value $V$ is your tag that you send with the packet. This provably has a forgery probability of a modified packet of at most $i 2^{-32}$ and a blind forgery probability of $2^{-32}$. You'd need to implement a $GF(2^{32})$ multiply routine; assuming you don't need extreme speed, that's not that difficult.

That being said, might I suggest a totally different approach: how about using Speck in a Davies-Meyer construction with a key? Speck is a block cipher that can be evaluated with minimal memory, and a Davies-Meyer construction would't require much memory. You'd start the construction with a secret state; assuming that you don't use the block size of 128, you'd also want to end the hash with hashing some other secret data). The advantages of this approach: you can reuse the same secret data (keying material) for every packet (and so there's no possibility of running out); you don't need to worry about packet drops (as this construction is stateless), and it should fit within your restrictions.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I like the Speck (or some other lightweight cipher) idea, but given the same starting state and the same payload, I would produce the same ciphertext, which could potentially be replayed by an attacker. I think I would merely need to have something like a Lamport clock in each message (a constantly increasing number), so that each message is never the same. Can you explain a little what the Davies-Meyer function does and why it's needed? I'm not familiar with it, and the Wikipedia page is a bit dense. $\endgroup$
    – thirtythreeforty
    Commented Mar 25, 2015 at 0:27
  • $\begingroup$ @thirtythreeforty: Davies-Meyer is intended to turn the cipher into a hash. Thinking about it more, perhaps CBC-MAC (you don't need to worry about the attacker extending the message, do you?) would work out better. If you need to worry about replays, putting in a counter (which would be included in the integrity check) is the obvious solution. $\endgroup$
    – poncho
    Commented Mar 25, 2015 at 2:25
  • $\begingroup$ I'm going to pursue the Speck idea using CBC-MAC or Davies-Meyer. Thanks! $\endgroup$
    – thirtythreeforty
    Commented Mar 26, 2015 at 6:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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