4 ms·
> The issue we run into here is ambiguous encoding. What I have done in the past for this is to encode the messages as UTF-8 and separate them by 0xFF, since t
by layer8 2y ago
> The issue we run into here is ambiguous encoding.
What I have done in the past for this is to encode the messages as UTF-8 and separate them by 0xFF, since that byte value never occurs in UTF-8 encoding [0]. If the messages to be hashed are character strings, you have to decide on some encoding anyway in order to hash them.
[0] UTF-8 bytes always contain at least one zero bit: https://en.wikipedia.org/wiki/UTF-8#Encoding https://en.wikipedia.org/wiki/UTF-8#Encoding. Incidentally, if one wanted to create the UTF-8 equivalent of zero-terminated strings without reserving a character value (like NUL) as the sentinel value, one could use 0xFF for that.
- dfox 2y agoThat actually makes more sense than the usual opposite approach of using over-long encoding for NULs in the data.
- oconnor663 2y agoI usually recommend an 8-byte length suffix for each piece instead of a separator.* That way you don't need to make any assumptions about what bytes are legal. Putting the length in suffix position means you can still stream input into your hash state without knowing how long it's going to be in advance, and 2^64 bytes is enough for any practical application. (The maximum input size of SHA-256 is less than this.) I'm less sanguine than the authors about using Protobuf or CBOR for "canonical" serialization like this. I think it tends to "work until it doesn't". It's not what these formats were designed for, and you have to ask awkward questions like "is the order of struct fields guaranteed?" and "do integers always use the smallest possible representation?". This is more obvious for JSON, as the post points out, but every common serialization format I'm aware of has problems like this. I think we need a dedicated standard to do a good job of this, but I'm not aware of anything widespread. It's a surprisingly hard problem. * Technically you only need the suffix for each variable-length piece, and you can omit the first one. But it's more complicated if the number of pieces is variable. (If you have two adjacent fixed-length pieces, and then you combine them, does the hash change?) This sort of penny-pinching is interesting to think about in a design that's going to come with a giant set of test vectors, but it's asking for trouble in an application doing something custom. This is another reason I'd like to have a standard here.
- hamandcheese 2y agoDoes that mean the random suffix is effectively a secret? Otherwise an attacker could construct inputs with the separator, achieving the same thing as a simple separator, right?
- oconnor663 2y agoIt's not a random suffix, but a length suffix. So for example putting "hello" and "world!" together looks like "hello" | 5 | "world!" | 6. Concretely, you probably represent 5 and 6 as eight little-endian bytes, i.e. `n.to_bytes(8, 'little')` in Python. If you want to stop attackers from guessing/constructing hashes, you need to get a secret key involved, which is what the "YoloMAC" section of the post is about.
- layer8 2y agoIt depends on the use case. If, for example, you want to hash a username–password pair, I find write(toUtf8(username)); write((byte) 0xFF); // never occurs in UTF-8, hence unambiguous separator write(toUtf8(password)); to be most straightforward and parsimonious, and the assumption is maximally local.
- oconnor663 2y agoI agree that this approach works in the use case you're describing, but there are a couple reasons I wouldn't want to teach it broadly. Mainly, a caveat like "remember to only use this with UTF-8 strings and not with arbitrary bytes" is exactly the sort of thing applications routinely get wrong in the wild. Also, focusing on wacky edge cases, do we really know that our UTF-8 strings are valid UTF-8? Maybe we're comfortable staking our security on that in a language like Rust, where invalid strings are literally undefined behavior anyway. But what about in Go for example, where this snippet writes 0xff to stdout with no warnings whatsoever? func main() { s := string([]byte{0xff}) fmt.Println(s) }
- layer8 2y ago
- akira2501 2y agoIf your data can't contain a NUL byte then you could just XOR all the bytes of the message by the separator character byte itself.
- layer8 2y agoIf your data can't contain a NUL byte you can just use NUL as the separator.