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.
Quote from: WhiteHare on August 28, 2015, 05:24:29 PM
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
Quote from: TomWS on August 28, 2015, 05:33:28 PM
Quote from: WhiteHare on August 28, 2015, 05:24:29 PM
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?
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?
Quote from: WhiteHare on August 28, 2015, 06:37:35 PM
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.
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?
Quote from: WhiteHare on August 29, 2015, 12:03:07 AM
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
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...
Quote from: kobuki on August 29, 2015, 06:57:20 PM
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
Quote from: kobuki on August 29, 2015, 06:57:20 PM
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.
@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.
@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 ;)
Quote from: kobuki on August 30, 2015, 08:53:01 AM
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
Quote from: TomWS on August 30, 2015, 09:42:40 AM
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).
Quote from: kobuki on August 30, 2015, 09:00:29 AM
@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?
Quote from: WhiteHare on August 30, 2015, 09:57:03 AM
@kobuki What approach would you take when it comes to garage door commands?
Well, there are several approaches I'd consider. A good hash that fits the Atmel is a good candidate. Repeating messages a few times and comparing the important parts of the payload in subsequent ones is also a possibility. For controlling home or garage doors some added security might be important, like code hopping sequences against message repeating attacks. There is a good thread about it here, look for "jump codes" or "code hopping" or similar, I don't have the topic link handy, sorry. And, of course, using the built-in encryption is probably always a good idea, using a strong random key. For a simple door opener probably all of these can be implemented. Most of these already has proven, free code on the net for these chips, so there's no need to re-invent the wheel in each case.
If using listen-mode, I think it may make sense to keep the initial packet to a listening node short so that, in theory, the time its RFM69x spends cyclically doing 16ma Rx can be minimized. However, follow that short packet by immediately sending to the same node a longer packet that can be 72+ bits long or however long it needs to be to have confidence in the integrity of the packet. The idea is this: the node decodes the first small packet, sticks it in the FIFO for the ATMEGA328P, and then issues an interrupt to the sleeping ATMEGA328P, which then starts to wake up from deep power down sleep (which I've measured taking about 2.1ms on an 8Mhz Pro Mini, and so I'm assuming it would take the the same amount of time on a Moteino). Now, while the ATMEGA is waking up, the RFM69 stays in receive mode, burning 16ma regardless, so it's already primed to receive the next, longer packet, which it can then decode and shove into the FIFO also. Therefore, if by the time the ATMEGA328P wakes up from the first interrupt the ATMEGA finds only the first short packet in the FIFO queue for it to read and not also a longer, properly hashed packet behind it, then it may quickly conclude that the first packet was corrupt and it may command itself (the ATMEGA) and the RFM69x to go immediately back to sleep, forgetting all about the entire episode.
Make sense? I haven't yet tested that, but that's my current mental model of how it could work and still be energy frugal.
You could if you wished send the longer packet as the first packet, and the energy penalty would be meaningful but not knock-dead terrible, simply because the RFM69x already wastes 16ma for about 1.3ms just waking up on each cycle while in listen-mode, so the percentage difference of energy wasted by having to listen for longer packets all the time isn't enormous--maybe roughly just a 25% difference or thereabouts, depending on further assumptions.