deterministic IV for writecaps for dir entries #750

New Issue

zooko · 2009-07-07T15:01:13Z

zooko commented

2009-07-07 15:01:13 +00:00

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

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 added the

labels 2009-07-07 15:01:13 +00:00

zooko added this to the 1.5.0 milestone 2009-07-07 15:01:13 +00:00

zooko commented

2009-07-07 15:04:11 +00:00

Attachment deterministic_IV.darcspatch.txt (22828 bytes) added

**Attachment** deterministic_IV.darcspatch.txt (22828 bytes) added

deterministic_IV.darcspatch.txt

22 KiB

zooko commented

2009-07-09 04:43:11 +00:00

Okay, I went ahead and committed this in changeset: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...

zooko added the

fixed

label 2009-07-09 04:43:11 +00:00

zooko closed this issue

2009-07-09 04:43:11 +00:00

warner commented

2009-07-09 16:40:40 +00:00

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.

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 commented

2009-07-09 18:08:41 +00:00

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 commented

2009-07-12 10:35:45 +00:00

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.

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.

warner removed the

fixed

label 2009-07-12 10:35:51 +00:00

warner reopened this issue

2009-07-12 10:35:51 +00:00

zooko commented

2009-07-12 14:21:53 +00:00

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 commented

2009-07-12 14:24:09 +00:00

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!

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 commented

2009-07-12 23:09:54 +00:00

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.

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 commented

2009-07-12 23:52:08 +00:00

pushed, in changeset:c1d5717cf0ecd68f.

warner added the

fixed

label 2009-07-12 23:52:08 +00:00

warner closed this issue

2009-07-12 23:52:08 +00:00

Sign in to join this conversation.