Hash algorithm for dynamic growing/streaming data?

问题:

Are there any algorithm that you can continue hashing from a known hash digest? For example, the client upload a chunk of file to ServerA, I can get a md5 sum of the uploaded content, then the client upload the rest of the file chunk to ServerB, can I transfer the state of md5 internals to ServerB and finish the hashing?

There was a cool black magic hack based on md5 I found years ago at comp.lang.python, but it's using ctypes for a specific version of md5.so or _md5.dll, so it's not quite portable code for different python interpreter versions or other programming languages, besides the md5 module is deprecated in python standard library since 2.5 so I need to find a more general solution.

What's more, can the state of the hashing be stored in the hex digest itself? (So I can continue hashing a stream of data with an existing hash digest, not a dirty internal hack.

Any idea is appreciated. Thanks in advance :)

回答1:

Not from the known digest, but from the known state. You can use a pure python MD5 implementation and save its state. Here is an example using _md5.py from from PyPy:

import _md5

def md5_getstate(md):
    return (md.A, md.B, md.C, md.D, md.count + [], md.input + [], md.length)

def md5_continue(state):
    md = _md5.new()
    (md.A, md.B, md.C, md.D, md.count, md.input, md.length) = state
    return md

m1 = _md5.new()
m1.update("hello, ")
state = md5_getstate(m1)
m2 = md5_continue(state)
m2.update("world!")
print m2.hexdigest()

m = _md5.new()
m.update("hello, world!")
print m.hexdigest()

As e.dan noted, you can also use almost any checksuming algorithm (CRC, Adler, Fletcher), but they do not protect you well from the intentional data modification, only from the random errors.

EDIT: of course, you can also re-implement the serialization method using ctypes from the thread you referenced in a more portable way (without magic constants). I believe this should be version/architecture independent (tested on python 2.4-2.7, both i386 and x86_64):

# based on idea from http://groups.google.com/group/comp.lang.python/msg/b1c5bb87a3ff5e34

try:
    import _md5 as md5
except ImportError:
    # python 2.4
    import md5
import ctypes

def md5_getstate(md):
    if type(md) is not md5.MD5Type:
        raise TypeError, 'not an MD5Type instance'
    return ctypes.string_at(id(md) + object.__basicsize__,
                            md5.MD5Type.__basicsize__ - object.__basicsize__)

def md5_continue(state):
    md = md5.new()
    assert len(state) == md5.MD5Type.__basicsize__ - object.__basicsize__, \
           'invalid state'    
    ctypes.memmove(id(md) + object.__basicsize__,
                   ctypes.c_char_p(state),
                   len(state))
    return md

m1 = md5.new()
m1.update("hello, ")
state = md5_getstate(m1)
m2 = md5_continue(state)
m2.update("world!")
print m2.hexdigest()

m = md5.new()
m.update("hello, world!")
print m.hexdigest()

It is not Python 3 compatible, since it does not have an _md5/md5 module.

Unfortunately hashlib's openssl_md5 implementation is not suitable for such hacks, since OpenSSL EVP API does not provide any calls/methods to reliably serialize EVP_MD_CTX objects.

回答2:

This is theoretically possible (the md5 so far should contain all the state you need to continue) but it looks like the normal APIs don't provide what you need. If you can suffice with a CRC instead, this will probably be a lot easier, since those are more commonly used for the "streaming" cases like you need. See here:

binascii.crc32(data[, crc])

crc32() accepts an optional crc input which is the checksum to continue from.

Hope that helps.

回答3:

I was facing this problem too, and found no existing solution, so I wrote a library that uses ctypes to deconstruct the OpenSSL data structure holding the hasher state: https://github.com/kislyuk/rehash. Example:

import pickle, rehash
hasher = rehash.sha256(b"foo")
state = pickle.dumps(hasher)

hasher2 = pickle.loads(state)
hasher2.update(b"bar")

assert hasher2.hexdigest() == rehash.sha256(b"foobar").hexdigest()