Security notes / Message signing notes
| Security related stuff.
Hash as verifier; message integrity
You do a hash on the source side, and make the receiving side do the same hash, and compare them.
This is generally a good indicator of both success on success, and of failure on failure, needs only a tiny amount of further transfer.
- speed: as fast as possible
- robustness: hash should have avalanche effect
Doesn't care much about:
- keyspace size
- being a secure hash (but it's sometimes a nice bonus)
Checks against obvious garbled data
Detecting unintentional corruption of transmitted data is useful to avoid some very basic misbehaviour, and doesn't have to be complex at all to significantly lower the chances of that happening.
There are some things so simple they are barely hashes, but serve the same function. Examples:
- serial port parity bit
- four different methods, but all necessarily simple. Odd is arguably the best, but not by much.
- not actually used a lot - they give so little protection, and no no automatic fix, that you're better off adding your own checking (and possible correction) in your protocol
- GPS, specifically the NMEA 0183 text protocol
- per line, all characters are XORed together. The resulting byte is appended as hex, e.g. the 06 in
- which is weak protection, but enough to ignore most garbled lines
- Barcodes tend to have a check digit. That digit does not carry any useful data, it just lets you check that some math involving all digits checks out. This avoids a lot of incorrect scans
- For example, ISBNs (used on books) have their last digit as a check digit
More serious but still relatively simple hashes include:
- IPv4 uses a 16-bit checksum (of the header only) that is basically just addition
- TCP over IPv4 uses a 16-bit checksum (of header and payload) that is basically just addition
- TCP over IPv6 uses a 16-bit checksum (of header and payload) that is basically just addition
- MODBUS uses CRC16
- XMODEM used a sum of bytes, a later variant used 16-bit CRC instead
- YMODEM used a 16-bit CRC
- ZMODEM used 16-bit or 32-bit CRC
Most of these are mainly meant to make fairly likely that a garbled transmission is detected as bad, but...
- not focusing on the best probability of that detection (CRC is decent, the rest is not)
- not error correction (without retransmission)
- not strong against ill intent
Slightly more robust variants
On keyspace size
Keyspace size matters in that in that how likely you are likely to get the right hash with wrong data is a probability that lowers with larger spaces.
Luckily, said probabilities lower very quickly. While 16 bits probably isn't enough, and 32-bit is meh, there are simple and fast hashes like MD5 (128 bit) or SHA-1 (160 bit) that are arguably already overkill for this use, even if you're verifying gigabytes of data at a time.
- That serial port check bit has a roughly 1 in 2 chance. Which is why we rarely use it.
- that GPS byte, no matter how much smarter you could calculate it, when garbled still has a roughly 1 in 256 chance in matching.
On avalance effect
The avalance effect roughly means that the calculation has some reason that a small, local change leads to larger changes throughout the hash.
This protects against errors that happen locally any might check out for the wrong reasons.
For example, one of the simplest hash functions is a simple bytewise XOR, which is usually blindingly fast to execute, But if, say, data was transmitted over a 7-bit serial line (that chopped off the highest bit in bytes), XOR would check out perfectly, because the XOR would also have that bit missing. 0 XOR 0 = 0.
Sure, that's a pathological example, but hashes with at least some avalance effect are simple to make, and solve this particular issue.
It's also why throwing a cryptographic hashes at a problem can rarely hurt, even if you otherwise don't need it.
Hash as identifier
Supporting data structures
|This article/section is a stub — probably a pile of half-sorted notes, is not well-checked so may have incorrect bits. (Feel free to ignore, or tell me)|
Authenticity via hashes