# Authentication using a one-time pad

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 unforgability 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?

• 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! – John Deters Mar 24 '15 at 22:32
• 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. – thirtythreeforty Mar 24 '15 at 22:33
• 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}$? – poncho Mar 24 '15 at 23:16
• @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. – thirtythreeforty Mar 24 '15 at 23:23
• 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. – John Deters Mar 25 '15 at 1:13

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.