[tahoe-dev] [tahoe-lafs] #750: deterministic IV for writecaps for dir entries

[tahoe-lafs]

#750: deterministic IV for writecaps for dir entries
-----------------------------+----------------------------------------------
 Reporter:  zooko            |           Owner:       
     Type:  enhancement      |          Status:  new  
 Priority:  major            |       Milestone:  1.5.0
Component:  code-dirnodes    |         Version:  1.4.1
 Keywords:  confidentiality  |   Launchpad_bug:       
-----------------------------+----------------------------------------------
 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
 }}}

-- 
Ticket URL: <http://allmydata.org/trac/tahoe/ticket/750>
tahoe-lafs <http://allmydata.org>
secure decentralized file storage grid