Merge lp:~jderose/dmedia/tie-size-to-id into lp:dmedia

[Jason Gerard DeRose]

Cryptographically ties doc['bytes'] to doc['_id'].

This allows us to insure that for a given doc['_id'] (the top-hash), the doc['bytes'] and doc['_attachments']['leaves']['data'] are actually correct.

Validating doc['bytes'] is important because we want to be fairly confident about preallocating that much space before starting a file download. Otherwise a malicious peer need do nothing more than start circulating a bogus doc with the wrong doc['bytes'] to wreak all kinds of havoc.

Even though we're still using sha1, I'm doing this is a way that makes sense for when we migrate to Skein. The top-hash of a file whose size is 31415 bytes gets "personalized" like this:

tophash = sha1(b'dmedia/tophash 31415' + leaves).digest()

With Skein it would work like this:

tophash = skein512(leaves, pers=b'dmedia/tophash 31415').digest()

[Jason Gerard DeRose (jderose)]

Ah, also note that leafhash_personalization() and leafhash() aren't currently being used... just some daydreaming about how I'll do this when we switch to Skein.

[lp:~jderose/dmedia/tie-size-to-id]

170. By Jason Gerard DeRose on 2011-02-22

Replaced somewhat silly HASH alias with sha1 so code is easier to read

[David Jordan (dmj726)]

Without signing this as a crypto expert, I'd say this code looks fine.

review: Approve

[Jason Gerard DeRose (jderose)]

review: Approve

=== modified file 'dmedia/downloader.py'
--- dmedia/downloader.py	2011-02-13 07:24:32 +0000
+++ dmedia/downloader.py	2011-02-22 15:22:38 +0000
@@ -24,6 +24,7 @@
 """
 
 from os import path
+from hashlib import sha1
 from base64 import b32encode
 from urlparse import urlparse
 from httplib import HTTPConnection, HTTPSConnection
@@ -38,7 +39,7 @@
 from . import __version__
 from .constants import CHUNK_SIZE, TYPE_ERROR
 from .errors import DownloadFailure
-from .filestore import FileStore, HashList, HASH
+from .filestore import FileStore, HashList
 
 
 USER_AGENT = 'dmedia %s' % __version__
@@ -154,7 +155,7 @@
     def process_leaf(self, i, expected):
         for r in xrange(3):
             chunk = self.download_leaf(i)
-            got = b32encode(HASH(chunk).digest())
+            got = b32encode(sha1(chunk).digest())
             if got == expected:
                 self.dst_fp.write(chunk)
                 return chunk

=== modified file 'dmedia/filestore.py'
--- dmedia/filestore.py	2011-02-19 02:37:59 +0000
+++ dmedia/filestore.py	2011-02-22 15:22:38 +0000
@@ -155,7 +155,7 @@
 from os import path
 import stat
 import tempfile
-from hashlib import sha1 as HASH
+from hashlib import sha1
 from base64 import b32encode, b32decode
 import json
 import re
@@ -291,6 +291,80 @@
     return b32
 
 
+def tophash_personalization(file_size):
+    """
+    Personalize the top-hash with *file_size*.
+
+    For example:
+
+    >>> tophash_personalization(3141)
+    'dmedia/tophash 3141'
+
+    This is used to cryptographically tie ``doc['bytes']`` to ``doc['_id']``.
+    You can't change the leaves or the file size without affecting the top-hash.
+
+    The personalization is designed to be easy to implement in JavaScript.  For
+    example, this is the equivalent JavaScript function:
+
+        ::
+
+            function tophash_personalization(file_size) {
+                return ['dmedia/tophash', file_size].join(' ');
+            }
+
+    When hashing with Skein, this value would be used for the Skein
+    personalization parameter.  See PySkein and the Skein specification for
+    details:
+
+        http://packages.python.org/pyskein/
+
+        http://www.skein-hash.info/
+
+    When hashing with sha1, the top-hash is calculated like this:
+
+    >>> from hashlib import sha1
+    >>> from base64 import b32encode
+    >>> pers = tophash_personalization(3141)
+    >>> leaves = b'pretend this is the concatenated leaves'
+    >>> b32encode(sha1(pers + leaves).digest())  # The top-hash
+    'M55ORBTYICEDQ2WUREDYIYYO6VUJ3R6S'
+
+    :param file_size: the file size in bytes (an ``int``)
+    """
+    return ' '.join(['dmedia/tophash', str(file_size)]).encode('utf-8')
+
+
+def tophash(file_size):
+    """
+    Initialize hash for a file that is *file_size* bytes.
+    """
+    return sha1(tophash_personalization(file_size))
+
+
+def leafhash_personalization(file_size, leaf_index):
+    """
+    Personalize the leaf-hash with *file_size* and *leaf_index*.
+
+    For example:
+
+    >>> leafhash_personalization(3141, 0)
+    'dmedia/leafhash 3141 0'
+
+    :param file_size: the file size in bytes (an ``int``)
+    :param leaf_index: the index of this leaf (an ``int``, starting at zero)
+    """
+    return ' '.join(
+        ['dmedia/leafhash', str(file_size), str(leaf_index)]
+    ).encode('utf-8')
+
+
+def leafhash(file_size, leaf_index):
+    """
+    Initialize hash for the *leaf_index* leaf in a file of *file_size* bytes.
+    """
+    return sha1(leafhash_personalization(file_size, leaf_index))
+
+
 class HashList(object):
     """
     Simple hash-list (a 1-deep tree-hash).
@@ -347,7 +421,7 @@
         self.dst_fp = dst_fp
         self.leaf_size = leaf_size
         self.file_size = os.fstat(src_fp.fileno()).st_size
-        self.h = HASH()
+        self.h = tophash(self.file_size)
         self.leaves = []
         self.q = Queue(4)
         self.thread = Thread(target=self.hashing_thread)
@@ -368,7 +442,7 @@
         queue.  This functionality is in its own method simply to make testing
         easier.
         """
-        digest = HASH(chunk).digest()
+        digest = sha1(chunk).digest()
         self.h.update(digest)
         self.leaves.append(digest)
         if self.dst_fp is not None:
@@ -443,7 +517,7 @@
     if fp.mode != 'rb':
         raise ValueError("fp: must be opened in mode 'rb'; got %r" % fp.mode)
     fp.seek(0)  # Make sure we are at beginning of file
-    h = HASH()
+    h = sha1()
     size = os.fstat(fp.fileno()).st_size
     h.update(str(size).encode('utf-8'))
     h.update(fp.read(QUICK_ID_CHUNK))
@@ -499,7 +573,7 @@
     >>> from dmedia.tests import sample_mov  # Sample .MOV file
     >>> src_fp = open(sample_mov, 'rb')
     >>> fs.import_file(src_fp, 'mov')  #doctest: +ELLIPSIS
-    ('ZR765XWSF6S7JQHLUI4GCG5BHGPE252O', [...])
+    ('TGX33XXWU3EVHEEY5J7NBOJGKBFXLEBK', [...])
 
     And when you have the content-hash and extension, you can retrieve the full
     path of the file using `FileStore.path()`:
@@ -970,9 +1044,9 @@
         temporary file name, like this:
 
         >>> fs = FileStore()
-        >>> tmp = fs.tmp('ZR765XWSF6S7JQHLUI4GCG5BHGPE252O', 'mov', create=True)
+        >>> tmp = fs.tmp('TGX33XXWU3EVHEEY5J7NBOJGKBFXLEBK', 'mov', create=True)
         >>> tmp  #doctest: +ELLIPSIS
-        '/tmp/store.../transfers/ZR765XWSF6S7JQHLUI4GCG5BHGPE252O.mov'
+        '/tmp/store.../transfers/TGX33XXWU3EVHEEY5J7NBOJGKBFXLEBK.mov'
 
         Then the downloader will write to the temporary file as it's being
         downloaded:
@@ -991,9 +1065,9 @@
         Finally, the downloader will move the temporary file into its canonical
         location:
 
-        >>> dst = fs.tmp_verify_move('ZR765XWSF6S7JQHLUI4GCG5BHGPE252O', 'mov')
+        >>> dst = fs.tmp_verify_move('TGX33XXWU3EVHEEY5J7NBOJGKBFXLEBK', 'mov')
         >>> dst  #doctest: +ELLIPSIS
-        '/tmp/store.../ZR/765XWSF6S7JQHLUI4GCG5BHGPE252O.mov'
+        '/tmp/store.../TG/X33XXWU3EVHEEY5J7NBOJGKBFXLEBK.mov'
 
         The return value is the absolute path of the canonical file.
 

=== modified file 'dmedia/schema.py'
--- dmedia/schema.py	2011-02-15 07:53:55 +0000
+++ dmedia/schema.py	2011-02-22 15:22:38 +0000
@@ -110,7 +110,7 @@
 >>> src_fp = open(sample_mov, 'rb')
 >>> hashlist = HashList(src_fp)
 >>> hashlist.run()
-'ZR765XWSF6S7JQHLUI4GCG5BHGPE252O'
+'TGX33XXWU3EVHEEY5J7NBOJGKBFXLEBK'
 
 
 After calling `HashList.run()`, the binary digests of the leaf content-hashes

=== modified file 'dmedia/tests/helpers.py'
--- dmedia/tests/helpers.py	2011-02-20 13:01:32 +0000
+++ dmedia/tests/helpers.py	2011-02-22 15:22:38 +0000
@@ -33,7 +33,7 @@
 
 from . import sample_mov, sample_thm
 
-mov_hash = 'ZR765XWSF6S7JQHLUI4GCG5BHGPE252O'
+mov_hash = 'TGX33XXWU3EVHEEY5J7NBOJGKBFXLEBK'
 mov_leaves = [
     b32decode('IXJTSUCYYFECGSG6JIB2R77CAJVJK4W3'),
     b32decode('MA3IAHUOKXR4TRG7CWAPOO7U4WCV5WJ4'),
@@ -46,7 +46,7 @@
 
 mov_qid = 'GJ4AQP3BK3DMTXYOLKDK6CW4QIJJGVMN'
 
-thm_hash = 'TA3676LFHP2SHNUHAVRYXP7YWGLMUQ4U'
+thm_hash = 'GKZMOPVZILR43MZCXLVYP7T62XGBT7BQ'
 thm_leaves = [b32decode('F6ATTKI6YVWVRBQQESAZ4DSUXQ4G457A')]
 thm_qid = 'EYCDXXCNDB6OIIX5DN74J7KEXLNCQD5M'
 

=== modified file 'dmedia/tests/test_downloader.py'
--- dmedia/tests/test_downloader.py	2011-02-13 04:34:33 +0000
+++ dmedia/tests/test_downloader.py	2011-02-22 15:22:38 +0000
@@ -245,7 +245,7 @@
         self.assertEqual(path.getsize(sample_mov), path.getsize(src))
 
         e = raises(IntegrityError, inst.finalize)
-        self.assertEqual(e.got, 'UECTT7A7EIHZ2SGGBMMO5WTTSVU4SUWM')
+        self.assertEqual(e.got, 'AYDIKK2IYAYTP7H5QCDK5FQ55F7QH4EN')
         self.assertEqual(e.expected, mov_hash)
         self.assertEqual(e.filename, src)
         self.assertFalse(path.exists(dst_d))

=== modified file 'dmedia/tests/test_filestore.py'
--- dmedia/tests/test_filestore.py	2011-02-18 13:19:08 +0000
+++ dmedia/tests/test_filestore.py	2011-02-22 15:22:38 +0000
@@ -153,6 +153,46 @@
         good = 'NWBNVXVK5DQGIOW7MYR4K3KA5K22W7NW'
         assert f(good) is good
 
+    def test_tophash(self):
+        f = filestore.tophash
+        h = f(31415)
+        self.assertEqual(
+            h.digest(),
+            sha1(b'dmedia/tophash 31415').digest()
+        )
+        l = ''.join(mov_leaves)
+        h.update(l)
+        self.assertEqual(
+            h.digest(),
+            sha1(b'dmedia/tophash 31415' + l).digest()
+        )
+
+    def test_leafhash(self):
+        f = filestore.leafhash
+        l = ''.join(mov_leaves)
+
+        h = f(1079991, 0)
+        self.assertEqual(
+            h.digest(),
+            sha1(b'dmedia/leafhash 1079991 0').digest()
+        )
+        h.update(l)
+        self.assertEqual(
+            h.digest(),
+            sha1(b'dmedia/leafhash 1079991 0' + l).digest()
+        )
+
+        h = f(1079991, 1)
+        self.assertEqual(
+            h.digest(),
+            sha1(b'dmedia/leafhash 1079991 1').digest()
+        )
+        h.update(l)
+        self.assertEqual(
+            h.digest(),
+            sha1(b'dmedia/leafhash 1079991 1' + l).digest()
+        )
+
     def test_pack_leaves(self):
         f = filestore.pack_leaves
 
@@ -412,7 +452,7 @@
         src_fp.read(1024)  # Make sure seek(0) is called
         dst_fp = open(tmp.join('dst1.mov'), 'wb')
         inst = self.klass(src_fp, dst_fp, 32 * 2**20)
-        self.assertEqual(inst.run(), 'R3QI4WFID6VDVK2NBB6WXE5ALMNLZAHQ')
+        self.assertEqual(inst.run(), '6PTK7CX54TFB6HMHI62FJZL7XAEWT72J')
         self.assertFalse(src_fp.closed)  # Should not close file
         self.assertFalse(dst_fp.closed)  # Should not close file
         dst_fp.close()
@@ -430,7 +470,7 @@
         src_fp.read(1024)  # Make sure seek(0) is called
         dst_fp = open(tmp.join('dst2.mov'), 'wb')
         inst = self.klass(src_fp, dst_fp, 16 * 2**20)
-        self.assertEqual(inst.run(), 'B4IBNJ674EPXZZKNJYXFBDQQTFXIBSSC')
+        self.assertEqual(inst.run(), 'HNNTABOJXN4ZBJMD665IA7QAZRJKDA3B')
         self.assertFalse(src_fp.closed)  # Should not close file
         self.assertFalse(dst_fp.closed)  # Should not close file
         dst_fp.close()
@@ -1133,7 +1173,7 @@
         self.assertEqual(path.getsize(sample_mov), path.getsize(src))
 
         e = raises(IntegrityError, inst.tmp_verify_move, mov_hash, 'mov')
-        self.assertEqual(e.got, 'UECTT7A7EIHZ2SGGBMMO5WTTSVU4SUWM')
+        self.assertEqual(e.got, 'AYDIKK2IYAYTP7H5QCDK5FQ55F7QH4EN')
         self.assertEqual(e.expected, mov_hash)
         self.assertEqual(e.filename, src)
         self.assertFalse(path.exists(dst_d))