Good hash algorithm for Moteino for verifying data payload integrity?

[WhiteHare]

Prior to switching to Moteino I ran quite a few packets through some NRF24L01+'s (with its implementation of CRC) through a loopback to compare what was sent and what was received so that I could note differences.  The short-of-it: a non-trivial number of data payloads got corrupted but passed CRC anyway.

I'll do the same with Moteino, but, jumping ahead, I expect I'll probably get similar results at the margins.  So, as a guard against that, is there an especially good hash algorithm for Moteino whose results could be added to the data payload so that the receiving Moteino can rehash the data and compare against the received hashcode to see if they match?  It wouldn't do error correction (though that's another avenue), but at least it would prevent acting on corrupted data payloads.

Any thoughts on this or libraries to recommend?  These days it shouldn't be necessary to find a textbook and code it from scratch, as more than likely there are at least some folks here already doing it.

[TomWS]

Prior to switching to Moteino I ran quite a few packets through some NRF24L01+'s (with its implementation of CRC) through a loopback to compare what was sent and what was received so that I could note differences.  The short-of-it: a non-trivial number of data payloads got corrupted but passed CRC anyway.

I'll do the same with Moteino, but, jumping ahead, I expect I'll probably get similar results at the margins.  So, as a guard against that, is there an especially good hash algorithm for Moteino whose results could be added to the data payload so that the receiving Moteino can rehash the data and compare against the received hashcode to see if they match?  It wouldn't do error correction (though that's another avenue), but at least it would prevent acting on corrupted data payloads.

Any thoughts on this or libraries to recommend?  These days it shouldn't be necessary to find a textbook and code it from scratch, as more than likely there are at least some folks here already doing it.

Uh, what's wrong with using encryption?  If the packet makes it through that with identifiable content it has to be correct, doesn't it?

Tom

[WhiteHare]

Prior to switching to Moteino I ran quite a few packets through some NRF24L01+'s (with its implementation of CRC) through a loopback to compare what was sent and what was received so that I could note differences.  The short-of-it: a non-trivial number of data payloads got corrupted but passed CRC anyway.

I'll do the same with Moteino, but, jumping ahead, I expect I'll probably get similar results at the margins.  So, as a guard against that, is there an especially good hash algorithm for Moteino whose results could be added to the data payload so that the receiving Moteino can rehash the data and compare against the received hashcode to see if they match?  It wouldn't do error correction (though that's another avenue), but at least it would prevent acting on corrupted data payloads.

Any thoughts on this or libraries to recommend?  These days it shouldn't be necessary to find a textbook and code it from scratch, as more than likely there are at least some folks here already doing it.

Uh, what's wrong with using encryption?  If the packet makes it through that with identifiable content it has to be correct, doesn't it?

Tom

Sounds like a promising idea, and from the way you're asking, it sounds like you've already vetted it.  If so, then roughly speaking, how many bytes of identifiable content would I need to pad into an otherwise very short data payload in order to be extremely confident that none of the bytes in the payload are corrupted?  Likewise, how long of a key?

I gather you're thinking of this approach because the RFM69x has built-in hardware encrypt/decrypt, and so perhaps it's more power efficient to leverage that than have the ATMEGA328p crunch something else?

[WhiteHare]

It appears not, unless the hardware crypto also incorporates a cryptographic hash:  http://stackoverflow.com/questions/3655516/does-encryption-guarantee-integrity
Do you happen to know if it does?

[TomWS]

It appears not, unless the hardware crypto also incorporates a cryptographic hash:  http://stackoverflow.com/questions/3655516/does-encryption-guarantee-integrity
Do you happen to know if it does?

I 'think' you're over thinking this problem.  If all you want to do is ensure that the data being received is the data being sent, then encryption (AES-128) with a known expected value will do it.  For example, on every packet I send, the leading byte is the length of the packet (redundant to be sure, but fits my scheme well).  If I wanted to be ABSOLUTELY sure that the data is 100% correct, I could send one more byte using the same length byte at the end of the packet.  If the two match AND I use encryption, I'm gonna be pretty sure the data is good...
Tom

Updated to clarify when the second length packet would be sent.

[WhiteHare]

You may well be exactly right.  Is there a name for that approach?  I don't doubt that it would be an improvement over relying only on the built-in CRC, but the issue would seem to be its unknown collision rate, especially on really short inputs. 

I'll toss a couple other possible contenders into the ring:  SipHash is designed to be fast and seems to be commonly used for short inputs (https://131002.net/siphash). xxHash looks like it might be very fast (https://131002.net/siphash/).  It appears that both SipHash and xxHash have have performed well on a basic benchmark collision test.  It would be interesting to know if either of them were actually faster than the RFM69x's hardware encryption approach you outlined or likewise if either required less total  energy to run on a battery powered Moteino node.  If it it turned out that one or the other was  faster or used less energy, then would you still prefer the approach you outlined, or would it change your preference?

[TomWS]

You may well be exactly right.  Is there a name for that approach?  I don't doubt that it would be an improvement over relying only on the built-in CRC, but the issue would seem to be its unknown collision rate, especially on really short inputs. 

I'll toss a couple other possible contenders into the ring:  SipHash is designed to be fast and seems to be commonly used for short inputs (https://131002.net/siphash). xxHash looks like it might be very fast (https://131002.net/siphash/).  It appears that both SipHash and xxHash have have performed well on a basic benchmark collision test.  It would be interesting to know if either of them were actually faster than the RFM69x's hardware encryption approach you outlined or likewise if either required less total  energy to run on a battery powered Moteino node.  If it it turned out that one or the other was  faster or used less energy, then would you still prefer the approach you outlined, or would it change your preference?

Well, it can't be faster, the encryption engine is built in to the RFM69 and takes place 'on the fly' and while it seems there should be some power cost, I haven't seen anything in the datasheet that indicates that it does.  And you, yourself, pointed out that the AVR processors are not exactly state of the art in uA/MHZ so I can't imagine an AVR based algorithm will win out in this regard. I'll admit that I haven't run the experiment of transmit/receive the same set of packets comparing power with and without encryption.  I'll leave that experiment for you youngsters 

I will say that I've lost packets but I've never noticed corrupted ones.  However, I can't say I've run that experiment either 

I'd be happy to give this method a 'name', but it just seems intuitive to me that you can't accidentally change any set of bits in an AES-128 encrypted message and still get a decipherable result in which data at end of the message meets an expected value, especially packets as short as ours.

Tom

[kobuki]

Hashing data to have some confidence in the message transmission mechanism is and old and interesting problem. Radio packets can and will be corrupted. Even I've seen it many times (including ones that passed the simple 16-bit CRC, even). Encryption has nothing to do with the authencity or integrity of the message. Thinking so can lead to serious mistakes. All modern ciphers employ a kind of MAC to verify the integrity and authencity of the encrypted messages.

@Tom: what you're suggesting is replacing a mathematically sound algorithm on data integrity with heuristics, using knowledge on the payload in your own software. That surely works to an extent, but well, it's a trade-off. You can avoid the additional memory footprint of the hashing algo, but then you can't really be sure about the integrity of your data. And of course additional integrity checks don't come for free on small memory devices, albeit the impact is small in comparison.

@WhiteHare: I'm curious which hashing algo you'll find appropriate for your needs. Adding 4..8 bytes to a short message similar in lenght also has its own implications, but sometimes it's unavoidable...

[TomWS]

Encryption has nothing to do with the authencity or integrity of the message.

I'm glad to hear that the authorities believe this as it might mean that this method can still be patented (although I doubt it).  Just to be sure, however, maybe I should, at least, name it.

If you take the suggestion out of context then I agree, encryption has nothing to do with integrity of the message.  However, taken in the context of this discussion, I believe it does provide a solid (and virtually free*) mechanism for verifying that the data has been received error free.

I think you will agree that any 'n' bit (n=1..pkt len) data corruption occurring within an encrypted packet with affect ALL subsequent bits in the decrypted stream, including the last byte that I'll call a 'check' byte.  As with CRC, the check byte will be an accumulation of all data preceding it. However, it is only a byte so has a 1:256 chance of being corrupted to its original value. 

If this is ALL there was, then, you're right, this is pretty useless.  But let's not forget the CRC byte which was OP's original concern due to it's sensitivity to false positives.   

By adding the check byte, at a minimum, we've multiplied the probability of CRC error by the 1:256 probability of a false positive of the check byte - an improvement to be sure. 

Now if we examine the probability that the SAME n bit error that produced a false positive on one check byte ALSO produces a false positive on the other byte (which is arrived via a totally different algorithm than the first byte), I think we have a link that's reliable enough to carry weather data or even garage door open commands with confidence.  Certainly we won't use this on the Mote that we're using to do a fly-by of Pluto, but I believe it's good enough in the context of this discussion.

*Note: In an earlier post I said that the encryption occurs 'on the fly'.  This is not true, the calculation takes place only after the FIFO is filled and consumes an additional 7uS per 16 bytes of packet data.  I apologize for the error.

Tom

[WhiteHare]

Hashing data to have some confidence in the message transmission mechanism is and old and interesting problem. Radio packets can and will be corrupted. Even I've seen it many times (including ones that passed the simple 16-bit CRC, even). Encryption has nothing to do with the authencity or integrity of the message. Thinking so can lead to serious mistakes. All modern ciphers employ a kind of MAC to verify the integrity and authencity of the encrypted messages.

@Tom: what you're suggesting is replacing a mathematically sound algorithm on data integrity with heuristics, using knowledge on the payload in your own software. That surely works to an extent, but well, it's a trade-off. You can avoid the additional memory footprint of the hashing algo, but then you can't really be sure about the integrity of your data. And of course additional integrity checks don't come for free on small memory devices, albeit the impact is small in comparison.

@WhiteHare: I'm curious which hashing algo you'll find appropriate for your needs. Adding 4..8 bytes to a short message similar in lenght also has its own implications, but sometimes it's unavoidable...

@kobuki What makes me hesitant about sipHash is that it's a 64-bit hash value.  If the data payload is small enough, then I've got to believe I could send a damn good ecc instead and get much better value out of a 64 bit overhead. 

Unfortunately, this isn't a topic I'm versed in, so at the moment I'm trying to feel my way through the dark.

[kobuki]

@Tom:

I'd rather not comment on what an encryption algorithm and a hash is for and what authorities think of which. Encryption is encryption, hashes are hashes... Animals living in a nearby but different zoo. BTW, a single bit flip in an AES block will cause the whole block to change, not just subsequent bits (RFM69 is employing AES encryption).

OTOH, you said the magic words: "I think we have a link that's reliable enough to carry weather data or even garage door open commands with confidence" - that is, the current solution is reliable enough for specific purposes, and with that I completely agree. You can easily employ a few safety checks, and that's probably how most off-the-shelf remotes work. Most of the time we just need something that fits our purposes and "just works". But you also mention CRC which can be considered a weak hash, and you probably still use it in addition to your heuristics checks. But we can't comment on OP's requirements on what's a "robust enough" check or hash for him. That's why I said I'm curious what he ends up with.

[kobuki]

@WhiteHare: ECC algorithms don't come for cheap, unfortunately, at least on these small MCUs. But there's at least choice, for instance:

https://github.com/kmackay/micro-ecc
https://github.com/iSECPartners/nano-ecc

I'm wondering when pico-ecc will see the daylight

[TomWS]

a single bit flip in an AES block will cause the whole block to change, not just subsequent bits

Better yet!  In my case BOTH the leading and ending bytes would be affected and unlikely to match each other AND the packet length.  Perfect!  Thanks!

Tom

[kobuki]

Better yet!  In my case BOTH the leading and ending bytes would be affected and unlikely to match each other AND the packet length.  Perfect!  Thanks!

But the resulting block is undefined So it can be either a perfect fit for your checks or complete garbage (mostly the latter, though).

[WhiteHare]

@WhiteHare: ECC algorithms don't come for cheap, unfortunately, at least on these small MCUs. But there's at least choice, for instance:

https://github.com/kmackay/micro-ecc
https://github.com/iSECPartners/nano-ecc

I'm wondering when pico-ecc will see the daylight

@kobuki Thanks for the links!  I'll look into those.

I think the garage door vs. weather data distinction is a good one.  If it's weather data, the standards can be more relaxed, as it's slowly changing and there will be another update in a matter of minutes, so you can comparison check against a moving average, etc.

Plus, there will be a lot more weather updates than garage door commands, so it makes sense to be cheap about weather updates,  if anywhere.

So, then, that leaves what to do about the high value, important stuff, like garage door commands.

@kobuki What approach would you take when it comes to garage door commands?