deterministic IV for writecaps for dir entries

[zooko]

Okay, here is a patch which replaces os.urandom(16) with a (tagged) secure hash of the write cap. This protects the directory entries against the "VM rollback problem", which otherwise might expose the writecaps of entries to someone who has only the readcap to the dir in the case that the writer of the dir suffered a vm rollback.

In addition, this makes packing deterministic, so that pack(unpack(packeddir)) == packeddir. (Kevan's original unit tests for this ticket assumed that would be the case.)

Is there any cryptographic problem that making this change would raise? It means that encryption of the writecaps doesn't have "semantic security" (which I think corresponds to IND-CPA?), but they actually didn't anyway since each one is accompanied by its readcap.

Perhaps surprisingly, this patch appears to reduce the CPU usage a little bit for packing directories (at least on Mac OS X).

Please examine this patch, all cryptographers and security experts!

Before this patch:

benchmarking <function unpack at 0x3282370>
N:      64, time: best:    0.07,   2th-best:    0.07, ave:    0.08,   2th-worst:    0.07, worst:    0.09 (of      5), reps/s:     13, ave rate:      837
N:     256, time: best:    0.29,   2th-best:    0.29, ave:    0.30,   2th-worst:    0.30, worst:    0.32 (of      5), reps/s:      3, ave rate:      851
N:    1024, time: best:    1.15,   2th-best:    1.15, ave:    1.18,   2th-worst:    1.15, worst:    1.31 (of      5), reps/s:      0, ave rate:      866
N:    4096, time: best:    4.37,   2th-best:    4.37, ave:    4.49,   2th-worst:    4.41, worst:    4.93 (of      5), reps/s:      0, ave rate:      912
benchmarking <function pack at 0x3282330>
N:      64, time: best:    0.07,   2th-best:    0.07, ave:    0.07,   2th-worst:    0.07, worst:    0.08 (of      5), reps/s:     13, ave rate:      862
N:     256, time: best:    0.29,   2th-best:    0.29, ave:    0.29,   2th-worst:    0.29, worst:    0.29 (of      5), reps/s:      3, ave rate:      872
N:    1024, time: best:    1.15,   2th-best:    1.15, ave:    1.15,   2th-worst:    1.15, worst:    1.15 (of      5), reps/s:      0, ave rate:      889
N:    4096, time: best:    4.36,   2th-best:    4.38, ave:    4.39,   2th-worst:    4.38, worst:    4.45 (of      5), reps/s:      0, ave rate:      933
benchmarking <function unpack_and_repack at 0x32823b0>
N:      64, time: best:    0.07,   2th-best:    0.07, ave:    0.07,   2th-worst:    0.07, worst:    0.08 (of      5), reps/s:     13, ave rate:      857
N:     256, time: best:    0.29,   2th-best:    0.29, ave:    0.29,   2th-worst:    0.29, worst:    0.30 (of      5), reps/s:      3, ave rate:      870
N:    1024, time: best:    1.15,   2th-best:    1.15, ave:    1.15,   2th-worst:    1.15, worst:    1.15 (of      5), reps/s:      0, ave rate:      888
N:    4096, time: best:    4.37,   2th-best:    4.38, ave:    4.38,   2th-worst:    4.38, worst:    4.39 (of      5), reps/s:      0, ave rate:      935

after this patch:

benchmarking <function unpack at 0x32823f0>
N:      64, time: best:    0.07,   2th-best:    0.07, ave:    0.08,   2th-worst:    0.07, worst:    0.08 (of      5), reps/s:     13, ave rate:      844
N:     256, time: best:    0.29,   2th-best:    0.29, ave:    0.30,   2th-worst:    0.29, worst:    0.32 (of      5), reps/s:      3, ave rate:      858
N:    1024, time: best:    1.11,   2th-best:    1.11, ave:    1.15,   2th-worst:    1.11, worst:    1.27 (of      5), reps/s:      0, ave rate:      894
N:    4096, time: best:    4.25,   2th-best:    4.26, ave:    4.37,   2th-worst:    4.27, worst:    4.79 (of      5), reps/s:      0, ave rate:      938
benchmarking <function pack at 0x32823b0>
N:      64, time: best:    0.07,   2th-best:    0.07, ave:    0.07,   2th-worst:    0.07, worst:    0.08 (of      5), reps/s:     13, ave rate:      859
N:     256, time: best:    0.29,   2th-best:    0.29, ave:    0.29,   2th-worst:    0.29, worst:    0.29 (of      5), reps/s:      3, ave rate:      874
N:    1024, time: best:    1.11,   2th-best:    1.12, ave:    1.12,   2th-worst:    1.12, worst:    1.12 (of      5), reps/s:      0, ave rate:      917
N:    4096, time: best:    4.26,   2th-best:    4.26, ave:    4.27,   2th-worst:    4.28, worst:    4.28 (of      5), reps/s:      0, ave rate:      959
benchmarking <function unpack_and_repack at 0x3282430>
N:      64, time: best:    0.07,   2th-best:    0.07, ave:    0.07,   2th-worst:    0.07, worst:    0.08 (of      5), reps/s:     13, ave rate:      856
N:     256, time: best:    0.29,   2th-best:    0.29, ave:    0.29,   2th-worst:    0.29, worst:    0.29 (of      5), reps/s:      3, ave rate:      871
N:    1024, time: best:    1.11,   2th-best:    1.11, ave:    1.13,   2th-worst:    1.12, worst:    1.18 (of      5), reps/s:      0, ave rate:      908
N:    4096, time: best:    4.25,   2th-best:    4.25, ave:    4.25,   2th-worst:    4.26, worst:    4.26 (of      5), reps/s:      0, ave rate:      963

[zooko]

Okay, I went ahead and committed this in 786ed012b3510135. Brian: I hope you sneak away from your vacation and log into the internet on your cell phone and review this patch before I release v1.5...

[warner]

I think this is ok.. we're always using the same data with the same key, so no worries there.. we'd be enabling readers to mount a dictionary attack if we weren't already doing so by putting the readcap in the dirnode contents, so there's no increase in exposure there either.

I think it would be more accurate to call this a "salt" instead of an "IV" though, since 1) we're using CTR mode, and 2) we're hashing this value to generate and AES key, not an IV. I don't know what I was thinking when I named that value "IV" in the original code.

Also, looking at the code, we're using two hashes and not using the intermediate value anywhere. So how about using just one hash? Instead of:

IV = hashutil.mutable_rwcap_iv_hash(self._node.get_writekey())
key = hashutil.mutable_rwcap_key_hash(IV, self._node.get_writekey())
cryptor = AES(key)

we could use something like:

wk = self._node.get_writekey()
key = hashutil.mutable_rwcap_key_hash2(wk)
cryptor = AES(key)

where mutable_rwcap_key_hash2 is a one-argument function that hashes a fixed prefix with the writekey.

I too am surprised by the apparent speedup. Maybe the kernel context-switching time needed to read from /dev/urandom (or the refill-/dev/urandom code that gets invoked when you drain few kb from the entropy pool) is larger than the SHA256 code that gets invoked by the extra hash. In any case, using just one hash ought to be faster than either the original code or the attached patch.

[zooko]

Whoops, I had forgotten that the name "IV" was wrong, and was misled by it into thinking it ought to be separate from the key. Your suggested patch sounds better to me.

[warner]

oh, I'm being stupid and the new code is bad. What we're doing is encrypting a list of child writecaps in such a way that the containing dirnode's writecap is required to retrieve them. Obviously each child writecap must be encrypted with a different key. It is reasonable to use the hash of the child writecap as a salt (since there's no requirement that the constant child writecap be encrypted differently each time), but it is not ok to use the hash of the parent dirnode writecap as a salt (because that's the same for all children).

My suggested change is wrong too.

The code needs to be more like:

salt = hashutil.mutable_rwcap_iv_hash(rwcap)
key = hashutil.mutable_rwcap_key_hash(salt, self._node.get_writekey())
crypto = AES(key)

I'll make this change soon.

[zooko]

Whoops. Ouch. I'm sure glad you caught that! I was thinking when I wrote the patch that I was using the writecap of the entry as the input, but obviously I was using the key of the directory!

[zooko]

By the way, a more traditional way to do something like this would be to use the same key (the one for the dir) to encrypt each entry and use a unique IV for each entry. We are in the habit of instead generating a unique key for each thing we want to encrypt and typically just leaving the IV at 0, which seems fine to me, too.

Your proposed fix is in the latter tradition. Please hurry up and commit it so that nobody uses trunk to write directories insecurely!

[warner]

Huh, I wasn't even aware of pycryptopp offering IV!=0.

I'll test the patch tomorrow, but I'm not sure I'll be able to to commit it until about 24h from now.

[warner]

pushed, in c1d5717cf0ecd68f.