RFC: Future-proofed cryptographic hash values.

[jbenet]

Problem

As time passes, software that uses a particular hash function will often need to upgrade to a better, faster, stronger, ... one. This introduces large costs: systems may assume a particular hash size, or call sha1 all over the place.

It's already common to see hashes prefixed with a function id:

sha1-a651ec3c4cc479977777f916fcedb221f38aaba1
sha256-aec71a4d4a8f44bc0c3e1133d5544d724b857cf20fe5aaeb1bc4d6e7c1ee68f1

Is this the best way? Maybe it is. But there are some problems:

1. Hashes tend to be transferred/printed encoded in hex, base32, base64, base54, etc. The name of the hash function may not be compatible with your encoding. (e.g. the hashes above are hex values, but 's' is not a valid hex char) This introduces annoying complexity when merely encoding/decoding hashes for storing / transferring / printing out to uses. (Ugh!) This gets worse when "things expecting a hex hash" that you don' control cannot be used with this scheme.
2. When storing millions of hashes, the extra byte costs of something like blake2b- may matter. So we might want to use a much narrower prefix. Particularly given that "widely used and accepted secure cryptographic hash functions" tend to change very little over time (by 2014 there's less than 256 that you might seriously consider).

Is there an RFC for this? I haven't found a "Hash Function Suite" like the "Cypher Suite" in TLS (RFC 5246/A.5).

Potential solutions

Use a short prefix mapping to some "crytographic hash function" suite. This already has to be done: the sha1- prefix is more human readable, but probably not a good idea to blindly dispatch a function based on the string sha1. Whitelisting specific strings (a blessed table) already happens.

So what would this look like? For example, suppose sha1 is 0x01

# name prefixed
sha1-0beec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33 # hex
sha1-bpxmpnpkh4h5xsk5bxkh6pc3yj25vcrt # base32
sha1-aef1qioaay9wkladm4f7a6nubty # base58
sha1-c+7hteo/d9vjxq3ufzxbwnxaijm # base64

sha256-2c26b46b68ffc68ff99b453c1d30413413422d706483bfa0f98a5e886266e7ae # hex
sha256-fqtli23i77di76m3iu6b2mcbgqjuellqmsb37ihzrjpiqytg46xa # base32
sha256-3ymapqcucjxdwprbjfr5mjcpthqfg8pux1txqrem35jj # base58
sha256-lca0a2j/xo/5m0u8htbbnbnclxbkg7+g+ypeigjm564 # base64

# id prefixed (`0x01 for sha1, and `0x02` for sha256)
010beec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33 # sha1 in hex
aef65r5v5i7q7w6jlug5i7z4lpbhlwukgm # sha1 in base32
4jvyy9wgauheuckrj7szdd2e1vqs # sha1 in base58
aqvux7xqpw/byv0n1h88w8j12ooz # sha1 in base64

022c26b46b68ffc68ff99b453c1d30413413422d706483bfa0f98a5e886266e7ae # sha256 in hex
aiwcnndlnd74nd7ztnctyhjqie2bgqrnobsihp5a7gff5cdcm3t24 # sha256 in base32
eryupqi6npzkezrsc1mgaaorxh7tkyy6v7nc8h5t4zeh # sha256 in base58
aiwmtgto/8ap+ztfpb0wqtqtqi1wzio/opmkxohizueu # sha256 in base64

Pros:

• hash values are consistent with the encoding :)
• shorter

Cons:

• numbers are hard to human-read. This is a less strong point, as some ids would be quickly recognizable. e.g. 0x01 is sha1, 0x02 is sha256, etc.
• prefixing bytes makes encoded values change altogether. :(

---

on varints

Ideally, for proper future proofing, we want a varint. Though it is to be noted that varints are annoying to parse + slower than fixed-width ints. There are so few "widely used...hash functions" that it may be okay to get away with one byte. Luckily, can wait until we reach 127 functions before we have to decide which one :)

May be able to repurpose utf-8 implementations for this.

** Random UTF-8 question: ** why are the subsequent bytes wasting two bits each?? '10' prefix below.

U+0000    U+007F     1 0xxxxxxx
U+0080    U+07FF     2 110xxxxx  10xxxxxx
U+0800    U+FFFF     3 1110xxxx  10xxxxxx  10xxxxxx
U+10000   U+1FFFFF   4 11110xxx  10xxxxxx  10xxxxxx  10xxxxxx
U+200000  U+3FFFFFF  5 111110xx  10xxxxxx  10xxxxxx  10xxxxxx  10xxxxxx
U+4000000 U+7FFFFFFF 6 1111110x  10xxxxxx  10xxxxxx  10xxxxxx  10xxxxxx  10xxxxxx

From http://en.wikipedia.org/wiki/UTF-8#Description

Is it to keep the code point ranges nice and rounded-ish?

[jbenet]

@dominictarr @substack @maxogden @davidad @ali01 @msparks @sqs @feross @dcposch

[dominictarr]

what are the scenarios this will get used in?
I'm guessing it's something like this:

There is a widely used hash function X. later, people will develop better hash functions, but there will still be plenty of people using X. Later, weaknesses are discovered in X,
everyone is suggested to update to Y.

This is far far fewer hash functions than if you just always use the best hash function around. You probably shouldn't just update your app to the current flavor of the month... this would really be something you might do once in a decade or two.

If you have hash trees, which I'm guessing you would... then you well have to rebuild all your data anyway. maybe all you need to pass the current hash function in the handshake or config file, and have tests where you inject a different hash function or allow building with a new hash function.

[davidad]

Re. the UTF-8 question, I think it is so that "continuation" bytes are unambiguous vs. "starting" bytes. This means that e.g. if is a stream is chopped off in the middle of a multibyte glyph, the remote will know that it does not have a complete glyph at the start of the stream.

[davidad]

Anyway, @jbenet, when I was thinking about the wire protocol for my "new OSI model", I came to roughly the same conclusion, that we need a prefix field to specify ciphersuite/protocol version. The way I figured it, the cost of a varint is not worth it, since if push comes to shove, a "protocol version" could be standardized that has an additional ciphersuite field with a bigger size. However, I decided on two bytes rather than one (same size as the TLS ciphersuite field, and with IANA's "port numbers" in mind).

BTW, a bonus of ciphersuite prefix field is that an appropriate lookup table can be used to determine the length of the hash, so other content can follow it on the wire with no delimiters.

I would like to put in a word for making it a true ciphersuite field, rather than a "hash function suite" field. A ciphersuite specifies a hash function, anyway; why invent an entirely new, incompatible numbering scheme for a smaller concept? If you want to use shiny new hashes like BLAKE2b that aren't part of a TLS ciphersuite yet, just use an existing unassigned block like {0xdc, *} and define your own set of ciphersuites there, copying some existing ciphersuite but modifying the hash function. (I recommend copying the ECDHE-ECDSA-ChaCha20-Poly1305 ciphersuite if it's all the same to you.)

[jbenet]

@dominictarr

You probably shouldn't just update your app to the current flavor of the month... this would really be something you might do once in a decade or two.

Yeah definitely.

If you have hash trees, which I'm guessing you would... then you well have to rebuild all your data anyway.

Maybe, not always. For example, you might be switching from sha256 to blake2b for the speed improvement, but don't necessarily need to change all the stored data. (And even if you do, in a live p2p system, you'll be upgrading over time). So as I see it, hash functions will need to coexist in systems aiming to have data in use ~10 years. So git + bittorrent definitely qualify :)

---

@davidad

I think it is so that "continuation" bytes are unambiguous vs. "starting" bytes. This means that e.g. if is a stream is chopped off in the middle of a multibyte glyph, the remote will know that it does not have a complete glyph at the start of the stream.

Ahh, makes sense. But seems brittle. Reliability (and message/item atomicity) will still have to be the responsibility of the stream's client. So this probably doesn't need it.

Anyway, @jbenet, when I was thinking about the wire protocol for my "new OSI model", I came to roughly the same conclusion

Yeah, figured you ran into this too :)

the cost of a varint is not worth it, since if push comes to shove, a "protocol version" could be standardized that has an additional ciphersuite field with a bigger size. However, I decided on two bytes rather than one (same size as the TLS ciphersuite field, and with IANA's "port numbers" in mind).

Seems like UTF-16 where the varint cost is enormous. :/

BTW, a bonus of ciphersuite prefix field is that an appropriate lookup table can be used to determine the length of the hash, so other content can follow it on the wire with no delimiters.

Oh yeah! That's great.

I would like to put in a word for making it a true ciphersuite field, rather than a "hash function suite" field. A ciphersuite specifies a hash function, anyway; why invent an entirely new, incompatible numbering scheme for a smaller concept?

Yeah, sgtm.

If you want to use shiny new hashes like BLAKE2b that aren't part of a TLS ciphersuite yet, just use an existing unassigned block like {0xdc, *} and define your own set of ciphersuites there, copying some existing ciphersuite but modifying the hash function.

It's kind of silly that the combinations need to be enumerated. Saves space in the end, due to valid combinations sparsity? Or just good old standard IANA protocol? For many use cases though, one only needs a hash function (say hashes in git). Would be nice to just use standardized values for each of the components, and allocates a byte per component wanted in the application.

https://www.iana.org/assignments/tls-parameters/tls-parameters.xhtml#tls-parameters-4

Hey look! It's a really slow package manager. Guess the size of the id namespace calls for a really slow publish process. :)

Aaaaaand, here's what we're looking for:

https://www.iana.org/assignments/tls-parameters/tls-parameters.xhtml#tls-parameters-18

Boom. Maybe just use those.

(I recommend copying the ECDHE/ChaCha/Poly1305 ciphersuite if it's all the same to you.)

ECDHE-{ECDSA,RSA}-CHACHA20-POLY1305-BLAKE2 ?

---

Btw, @davidad's new OSI (an awesome proposal) is here: http://davidad.github.io/blog/2014/04/24/an-osi-layer-model-for-the-21st-century/

[davidad]

@jbenet Re. UTF-8 vs UTF-16, saving a byte is one thing, but the CPU cost of processing or filtering packets is another, and I think the UTF-8 style varint imposes a heavy penalty on the latter that is not really justified, since there's only going to be one of these objects per packet. (UTF-8 makes sense because text files are entirely full of packed glyphs, among other reasons like ASCII compatibility.) And they really ought to be able to fit in two bytes for pretty much ever (but unlike Y2K, if that assumption turns out to be wrong, it is at least possible to back out of it).

[jbenet]

the CPU cost of processing or filtering packets is another

Yeah, that's fair.

since there's only going to be one of these objects per packet.

I plan to use this per-hash. So, say, an ipfs tree object would have many.

And they really ought to be able to fit in two bytes for pretty much ever

Yep. Unless there's a proliferation of hash functions made possible by the emergence of a more open + interoperable way of specifying hash function. (i can imagine variants/wrappers of others)

[jbenet]

First pass:

• https://github.com/jbenet/multihash
• https://github.com/jbenet/node-multihash

[feross]

Very neat!

[msparks]

crypt(3) is a similar idea, but password-focused.

[jbenet]

• https://github.com/jbenet/go-multihash too

@msparks said

crypt(3) is a similar idea, but password-focused.

You mean the way crypt stores things ($id$salt$encrypted) ? If so, this way of storing is like the sha256- str prefix discussed above.

[msparks]

crypt(3) is similar in that it uses ID prefixes, e.g., a $1$ prefix is MD5 and a $5$ prefix is SHA-256. It's dissimilar in that it adds the ID to the ASCII-readable digest. If I read your proposal correctly, you're prepending the ID to the hash output bytes.

(Note: I'm not saying anything novel; just mentioning prior work.)

[jbenet]

If I read your proposal correctly, you're prepending the ID to the hash output bytes.

@msparks yep. You can see https://github.com/jbenet/go-multihash/blob/master/multihash.go -- this makes it en/decodable between binary <--> string. (prepending $5$ to a hex digest is bad because $ is not hex, so converting becomes problematic).

[jbenet]

You can see this technique being used in https://github.com/jbenet/node-ipfs