Plaintext vergelijken met encrypted data

[Hmail]

Het vraagstuk waar ik mee zit is: Hoe vergelijk ik of een bestand gewijzigd is aan de hand van encrypted data op een server? Als metadata knip ik een bestand op in blokken waarvan ik de checksum naar de server stuur. Dus zegmaar dit in pseudocode:

code:

while( fread( buffer, BLOCK_LENGTH, file ) > 0 )
{
    checksum = get_block_checksum( buffer );
    if( !server_has_checksum( checksum ) )
        upload_block( encrypt_data( buffer ), checksum );
}

Het probleem ontstaat hier wanneer er data in het bestand wijzigt van ongelijke lengte. De resterende data schuift dan op en daardoor zijn alle checksum ongelijk. Dit betekent dat dat bij een bit meer of minder aan het begin van het bestand alle data opnieuw verstuurd moet worden. Bij grote bestanden gaat dat een probleem worden.
Een idee wat ik heb is gaan zoeken in het bestand naar het punt waarop de checksums weer overeenkomen met de server. Dus dan zou je zoiets in pseudocode krijgen:

code:

while( fread( buffer, BLOCK_LENGTH, file ) > 0 )
{
    checksum = get_block_checksum( buffer );
    if( !server_has_checksum( checksum ) )
    {
        changed_data[pointer] = buffer[0];
        fseek( file, pointer_where_data_was_unchanged + (++pointer), SEEK_SET );
    }
    else
    {
        // upload changed_data 
    }
}

Dit is een manier om het op te lossen, alleen past deze het encryptie algoritme aan, zodat een kleine wijziging in het bestand ook een kleine wijziging in de encrypted data betekent. Dat wil ik echter niet, ik wil uitgaan van bestaande standaarden en niet m'n eigen encryptie gaan schrijven.

Heeft iemand hier een beter idee?

[ Voor 12% gewijzigd door Hmail op 26-08-2016 15:45 ]

[stager]

Volgens mij staat de data door transposition algoritmes helemaal niet meer op dezelfde plaats. Hierdoor hangt er dus sterk van af wat voor encryptie je gebruikt of het überhaupt mogelijk is.

[NaliXL]

Wellicht kun je de bestaande lijst met checksums van je server ophalen en vervolgens een diff uitvoeren met je nieuwe lijst met checksums?

[Hmail]

stager schreef op vrijdag 26 augustus 2016 @ 16:20:
Volgens mij staat de data door transposition algoritmes helemaal niet meer op dezelfde plaats. Hierdoor hangt er dus sterk van af wat voor encryptie je gebruikt of het überhaupt mogelijk is.

Ik vergelijk de originele data, dus niet de encrypted data. De data op de server blijft op de server, die levert mij alleen een lijst met checksums.

NaliXL schreef op vrijdag 26 augustus 2016 @ 16:26:
Wellicht kun je de bestaande lijst met checksums van je server ophalen en vervolgens een diff uitvoeren met je nieuwe lijst met checksums?

Het probleem is dat zodra er een bit bij of af gaat de blokken niet meer uitlijnen en dus alle checksums erna ongelijk zijn. Daar zoek ik een oplossing voor.

Dit is ongeveer wat ik wil:


Deze afbeelding is van Tarsnap, zij hebben het over ongelijke blocksizes waardoor het beter uitlijnt, maar dat begrijp ik niet helemaal. Ik vond dit toevallig zojuist, dus ik wil binnenkort die broncode eens gaan bestuderen, maar wellicht weet iemand anders wat hiermee bedoeld wordt?

[NaliXL]

Ik denk dat je al héél veel alignment verschil kan opvangen door het verschil in bestandsgrootte te vergelijken. Je zou als eerste poging eens kunnen proberen om vanaf het punt waarop je checksums niet meer kloppen het verschil aan bestandsgrootte over te slaan en vervolgens vanaf dat punt, minus de hoeveelheid data waarvan jij een checksum maakt, de eerst volgende kloppende checksum te vinden door steeds een byte op te schuiven en daarvan een checksum te maken.

Maar die vlieger gaat natuurlijk niet op op het moment dat er alleen data gewijzigd is, of wanneer er zowel ergens data toegevoegd als verwijderd is. Om dat op te lossen kun je misschien het beste, zodra je een niet overeenkomend blok gevonden hebt, beginnen met kijken of je checksum van het laatste blok van het bestand overeenkomt. Zo niet, maak een checksum vanaf (eind van je bestand - checksum_bloklengte - 1). Klopt niet, dan (eind van je bestand - checksum bloklengte - 2) enz. Net zolang tot je weer alignment hebt.