Algoritmo hash per i dati di crescita/streaming dinamici?

Question

Ci sono algoritmi che puoi Continua hashing da un digest hash noto? Ad esempio, il client carica un pezzo di file su servera, posso ottenere un md5 Somma del contenuto caricato, quindi il client carica il resto del file file su serverb, posso trasferire lo stato di md5 interni a ServerB e finire l'hash?

C'era un Cool Black Magic Hack Basato su MD5 ho trovato anni fa su comp.lang.python, ma sta usando ctypes per una versione specifica di md5.so o _md5.dll, quindi non è un codice abbastanza portatile per diverse versioni di interprete di Python o altri linguaggi di programmazione. Oltre al md5 Il modulo è deprecato nella libreria standard Python poiché 2.5, quindi devo trovare una soluzione più generale.

Inoltre, può il stato dell'hashing essere archiviato nel digest esagonale stesso? (Quindi posso continuare a hashing di un flusso di dati con un digest hash esistente, non un sporco hack interno.)

Answer 1

Non dal digest noto, ma dallo stato noto. È possibile utilizzare un'implementazione Python MD5 pura e salvare il suo stato. Ecco un esempio che usa _md5.py da da 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()

Come notato da E.Dan, puoi anche utilizzare quasi tutti gli algoritmo di checksuming (CRC, Adler, Fletcher), ma non ti proteggono bene dalla modifica intenzionale dei dati, solo dagli errori casuali.

EDIT: ovviamente, puoi anche reimplementare il metodo di serializzazione utilizzando i ctypes dal thread a cui si fa riferimento in modo più portatile (senza costanti magiche). Credo che questo dovrebbe essere una versione/architettura indipendente (testato su Python 2.4-2.7, sia i386 che 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()

Non è compatibile con Python 3, poiché non ha un modulo _MD5/MD5.

Sfortunatamente l'implementazione OpenSSL_MD5 di Hashlib non è adatta a tali hack, poiché l'API EVP OpenSSL non fornisce chiamate/metodi per serializzare in modo affidabile gli oggetti EVP_MD_CTX.

Answer 2

Questo è teoricamente possibile (l'MD5 finora dovrebbe contenere tutto il stato Devi continuare) ma sembra che le API normali non forniscano ciò di cui hai bisogno. Se puoi invece bastare con un CRC, questo sarà probabilmente molto più semplice, poiché quelli sono più comunemente usati per i casi di "streaming" come hai bisogno. Vedere qui:

binascii.crc32 (dati [, CRC])

crc32() accetta un opzionale crc Input che è il checksum da cui continuare.

Spero possa aiutare.

Answer 3

Anch'io stavo affrontando questo problema e non ho trovato una soluzione esistente, quindi ho scritto una biblioteca che utilizza Ctypes per decostruire la struttura dei dati OpenSSL che tiene lo stato di hasher: https://github.com/kislyuk/rehash. Esempio:

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()