Quando parliamo di steganografia, le persone immaginano terroristi, pedofili, spie, o nel migliore dei casi, crypto-anarchici e altri scienziati. E in effetti, chi altro potrebbe averne bisogno? nascondere qualcosa agli sguardi esterni? Quale utilità può mai avere per una persona comune?
A quanto pare, c'è una qualche utilità. Ed è per questo che oggi compressiamo dati utilizzando metodi di steganografia. Alla fine, il lettore potrà anche utilizzare i propri preziosi archivi fotografici in JPEG per aumentare il numero di gigabyte liberi nel proprio sistema di file.
Cosa?
Se il lettore ricorda, la steganografia è quegli strani algoritmi che consentono di nascondere la presenza di un'informazione all'interno di un'altra. In termini più semplici: immagine + file == più o meno la stessa immagine, ma non proprio (al posto delle immagini può esserci qualsiasi cosa, ma di solito è più comprensibile). Non dovrebbe esserci un modo semplice per determinare se c'è qualcosa dentro o meno.
Ma se non si può distinguere uno dall'altro, c'è davvero una differenza? Dal punto di vista del consumatore, all'utente non interessa la precisione matematica (riflessa da un insieme specifico di bit), solo ciò che percepisce.
Ad esempio, vediamo tre immagini di un dolce cane:
Attenzione, JPEG!
Nonostante la colossale differenza di dimensione, in pochi sceglierebbero la terza versione. D'altra parte, la differenza tra le prime due fotografie non è così evidente, e la quantità di informazioni in esse (dal mio punto di vista) può essere equiparata.
Il principio stesso è già vecchio e da molti anni viene sfruttato attivamente dai metodi di compressione delle informazioni con perdita. Ma rompere non è costruire, ci interessa un lato più avanzato della questione. È possibile incorporare informazioni aggiuntive di dimensione N in un file in modo che la sua dimensione aumenti di M < N, e le modifiche non siano visibili all'utente?
Certo, è possibile. Ma vale la pena fare subito un paio di precisazioni:
- Innanzitutto, il metodo deve essere universale e dare un risultato positivo nella maggior parte dei dati di input. Cioè, mediamente, per un input casuale, dovrebbe avvenire una riduzione effettiva della quantità di informazioni memorizzate. "In media" significa che possono verificarsi casi opposti, ma non devono prevalere.
- In secondo luogo, la dimensione del contenitore compresso prima dell'inserimento delle informazioni deve essere maggiore rispetto alla modifica compressa in modo simile. Inserire semplicemente una marea di bit in un'immagine BMP utilizzando il metodo LSB non costituisce una compressione steganografica, poiché, dopo essere stata elaborata da qualche DEFLATE, l'immagine originale sarà probabilmente visibilmente più piccola.
- In terzo luogo, è necessario condurre e confrontare il risultato relativamente a dati già compressi con metodi classici. Questo consentirà di rimuovere l'effetto probabilistico delle loro ridondanze e di ottenere una compressione più efficace in generale.
Dove?
L'uso della steganografia implica che, oltre alle informazioni compresse, siano necessari contenitori in cui esse verranno inserite. La quantità massima di informazioni insertabili dipende in larga misura da proprietà specifiche, ma si scala molto più facilmente con il loro numero. Pertanto, il formato dei contenitori deve essere comune, affinché l'utente abbia una quantità sufficiente da utilizzare per ottenere un qualche ritorno dal processo di 'compressione'.
In questo contesto, file grafici, audio e video diventano buoni candidati. Tuttavia, a causa della varietà di formati, codec, ecc., nella pratica ci rimane solo un numero non così elevato di opzioni.
Considerando tutto ciò, la mia scelta è ricaduta sul JPEG. È praticamente presente per tutti, ampiamente utilizzato sia per scopi personali che aziendali, rappresentando quasi il formato de facto per la maggior parte delle immagini.
Come?
Successivamente ci sono schemi e descrizioni tecniche e ulteriori senza particolari spiegazioni, quindi coloro che lo desiderano possono saltarli, passando alla sezione 'Alta tecnologia'.
Caratteristiche comuni
Per inserire i dati in qualche posto, è necessario prima determinare dove. Possono esserci numerose fotografie in un file system, tra cui l'utente potrebbe volerne utilizzare solo alcune. Questo insieme desiderato di contenitori sarà chiamato biblioteca.
Si forma in due casi: prima della compressione e prima della decompressione. Nel primo caso, è possibile semplicemente utilizzare un insieme di nomi (o meglio, una espressione regolare per essi) dei file, ma nel secondo è necessario qualcosa di più affidabile: l'utente può copiare e spostare i file all'interno del sistema, rendendo difficile la loro identificazione corretta. Quindi, è necessario memorizzare i loro hash (md5 è sufficiente) dopo aver effettuato tutte le modifiche.
Non ha senso effettuare una ricerca iniziale tramite espressione regolare su tutto il filesystem; è sufficiente specificare una certa directory radice. In questa directory verrà anche salvato un file-archivio speciale, dove si troveranno quegli hash, insieme ad altre informazioni meta necessarie per il successivo ripristino delle informazioni compresse.
Tutto ciò è applicabile in egual misura a qualsiasi implementazione di qualsiasi algoritmo di compressione steganografica dei dati. I processi stessi di compressione e ripristino dei dati possono essere chiamati imballaggio e sballaggio.
F5
Ora che è chiaro cosa stiamo facendo e perché, rimane da descrivere l'algoritmo per raggiungere l'obiettivo. Ricordiamo il processo di codifica di un file JPEG (grazie alla wiki della Biblioteca Nazionale di Bauman):
Osservandolo, è opportuno fare subito alcune osservazioni:
- Le dimensioni di un file JPEG possono essere considerate ottimali, anche senza provare a comprimere con qualche programma come WinRAR;
- Si possono modificare solo le informazioni memorizzate (quella in uscita dalla trasformazione discreta del coseno, DCT), per garantire almeno una performance accettabile.
- Per non perdere dati in larga misura visibili all'utente, è necessario apportare il minimo delle modifiche a ciascuna immagine singola;
Sotto queste condizioni, si adatta un'intera famiglia di algoritmi, con cui è possibile familiarizzare . Il più avanzato di essi è l'algoritmo a cura di Andreas Westfeld, che lavora con i coefficienti DCT del componente di luminosità (l'occhio umano è meno sensibile proprio a queste variazioni). Il suo schema generale quando si lavora con un file JPEG esistente si riflette nel seguente schema:
Il Blocco F5 utilizza una metodologia avanzata di inserimento basata sulla codifica della matrice. I lettori possono approfondire il tema e l'algoritmo stesso tramite il link sopra; ci interessa innanzitutto il fatto che, grazie a questo metodo, si possono apportare meno modifiche nell'inserimento della stessa quantità di informazioni, maggiore è la dimensione del contenitore utilizzato. Inoltre, per eseguire l'algoritmo stesso, sono necessarie solo semplici operazioni di (de)codifica di Huffman e RLE.
Le modifiche stesse avvengono sui coefficienti interi e consistono nella riduzione del loro valore assoluto di un'unità, il che permette, in realtà, di utilizzare F5 per la compressione dei dati. Infatti, un coefficient ridotto nel valore assoluto occuperà probabilmente un numero minore di bit dopo la codifica di Huffman a causa della distribuzione statistica dei valori in JPEG.
Nel caso si formi uno zero (cosiddetta riduzione), la quantità di informazioni memorizzate si ridurrà della sua dimensione, poiché l'ultimo coefficient sarà parte della sequenza codificata RLE di zeri:
Modifiche
La protezione dei dati e la loro compressione sono compiti ortogonali, quindi si può trascurare la permutazione segreta della password dall'algoritmo originale. Inoltre, dobbiamo sapere esattamente come estrarre i dati, quindi tutte le informazioni necessarie a tal fine (quali contenitori sono stati utilizzati, in quale ordine, ecc.) devono essere registrate in un file separato e disponibili per la lettura libera dall'archiviatore.
L'algoritmo originale è progettato per l'invio di messaggi segreti, pertanto funziona contemporaneamente solo con un contenitore, presumendo che l'utente dividerà manualmente il contenitore in parti se necessario. Inoltre, nel caso di inserimenti indipendenti in ciascun contenitore, sarà necessario sapere in anticipo quanti bit di dati posizionare in ognuno. Pertanto, i coefficienti di ciascun elemento della libreria dovrebbero essere uniti in un unico grande astratto e lavorati secondo l'algoritmo originale.
Poiché l'originale F5 consente di utilizzare fino al 12% della dimensione del contenitore, tale modifica aumenterà anche la capacità massima: "fino al 12%" della dimensione dell'intera libreria è maggiore o uguale alla somma di "fino al 12%" di ciascuno dei suoi elementi.
Lo schema generale codificato appare come segue:
L'algoritmo stesso
Ora è il momento di descrivere l'algoritmo stesso dall'inizio alla fine, per non tenere il lettore all'oscuro:
- L'utente definisce i dati binari comprimibili M e la libreria L utilizzando espressioni regolari e la directory radice di ricerca;
- In ordine di sequenza nel FS, gli elementi della libreria formano MC:
- Da un file vengono decodificati una serie di coefficienti C;
- MC <- MC | C;
- Viene determinato il parametro k sulla base della terribile disuguaglianza:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Si prende a turno
n = (1 << k) - 1i bit meno significativi degli elementi non nulli da MC e vengono registrati ina:- Si calcola la funzione hash magica
f, che mappa una parola n-bitain k-bits; - Se
s == 0, quindi non è necessario apportare modifiche e l'algoritmo passa ai coefficienti successivi; - Ridurre il valore assoluto del coefficiente che corrisponde al
s-esimo bit della parolaa; - Se il risultato della riduzione ha portato a una contrazione (il coefficiente è diventato 0), ripetere il passaggio dall'inizio;
- Si calcola la funzione hash magica
- Tutti i coefficienti vengono codificati in RLE e Huffman, registrati nei file sorgente;
- Nel file dell'archivio viene registrato il parametro k;
- Per ciascun file L, nell'ordine in cui si trovano originariamente, viene calcolato l'hash MD5 e registrato nel file dell'archivio.
Tecnologie avanzate
Una forma naïve dell'algoritmo e implementazioni in altri linguaggi di alto livello (soprattutto quelli con garbage collection) avrebbero dato prestazioni orrende, quindi tutte queste complessità le ho implementate in puro C e ho effettuato una serie di ottimizzazioni sia per la velocità di esecuzione che per la memoria (non potete immaginare quanto pesino queste immagini senza compressione nemmeno fino a DCT). Ma anche così, inizialmente la velocità di esecuzione lasciava molto a desiderare, quindi non descriverò l'intero processo e i metodi utilizzati.
La cross-platform è stata raggiunta utilizzando una combinazione delle librerie libjpeg, pcre e tinydir, a cui va il mio grazie. Di default, tutto viene compilato tramite il normale make, quindi gli utenti Windows devono installare qualche Cygwin o gestire la Visual Studio e le librerie da soli.
L'implementazione è disponibile sotto forma di utility da console e libreria. Maggiori informazioni sull'uso di quest'ultima possono essere trovate nel README del repository su GitHub, il cui link inserirò alla fine del post. Ora passiamo alla descrizione e alla dimostrazione del funzionamento.
Come usare?
Con cautela. Le immagini utilizzate possono essere spostate, rinominate e copiate a piacimento. Tuttavia, è consigliabile prestare la massima attenzione e non modificarne il contenuto. Cambiare anche un solo bit porterà a una violazione dell'hash e renderà impossibile il recupero delle informazioni.
Supponiamo di aver ottenuto un file eseguibile f5ar dopo la compilazione. Possiamo analizzare la dimensione della libreria per calcolarne le possibilità di utilizzo con il flag -a: ./f5ar -a [cartella di ricerca] [espressione regolare compatibile con Perl]. L'imballaggio è effettuato con il comando ./f5ar -p [cartella di ricerca] [espressione regolare compatibile con Perl] [file da imballare] [nome dell'archivio], mentre lo spostamento avviene tramite ./f5ar -u [file dell'archivio] [nome del file ripristinato].
Dimostrazione del funzionamento
Per dimostrare l'efficacia del metodo, ho caricato una collezione di 225 fotografie di cani completamente gratuite dal servizio . Ognuno di essi ha una qualità leggermente superiore rispetto alle normali foto degli utenti, ma pur sempre. Ognuno di essi è stato ricodificato utilizzando libjpeg, per attenuare l'impatto delle particolarità di codifica della libreria sulla dimensione complessiva. Per contrassegnare il peggior esempio di dati comprimibili, è stato generato un file casuale uniformemente distribuito di 36 metri (poco più del 5% della dimensione totale) utilizzando dd.
Il processo di test è piuttosto semplice:
$ ls
binary_data dogs f5ar
$ du -sh dogs/
633M dogs/
$ du -h binary_data
36M binary_data
$ ./f5ar -p dogs/ .*jpg binary_data dogs.f5ar
Lettura del file di compressione... ok
Inizializzazione dell'archivio... ok
Analisi della capacità della libreria... completata in 16.8s
Capacità garantita rilevata di 48439359 bytes
Capacità possibile rilevata fino a 102618787 bytes
Compressione... completata in 32.6s
Salvataggio dell'archivio... ok
$ ./f5ar -u dogs/dogs.f5ar unpacked
Inizializzazione dell'archivio... ok
Lettura del file dell'archivio... ok
Riempimento dell'archivio con i file... completato in 1.2s
Decompressione... completata in 17.5s
Scrittura dei dati estratti... ok
$ sha1sum binary_data unpacked
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 binary_data
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 unpacked
$ du -sh dogs/
563M dogs/Oppure uno screenshot per gli amanti
Come si può vedere, partendo dai 633 + 36 == 669 megabyte di dati sul disco rigido siamo arrivati a un più piacevole 563, con un coefficiente di compressione di ~1,188. Questa differenza radicale è spiegata da perdite estremamente ridotte, simili a quelle ottenute con l'ottimizzazione dei file JPEG mediante metodi classici (tipo tinyjpg). Naturalmente, utilizzando la compressione steganografica, le informazioni non vengono semplicemente "perse", ma utilizzate per codificare altri dati. Inoltre, il numero di coefficienti "ottimizzati" grazie all'uso di F5 è molto inferiore rispetto all'ottimizzazione tradizionale.
Qualsiasi modifica sia stata apportata, non è affatto visibile ad occhio nudo. Sotto il spoiler qui sotto, il lettore può valutare la differenza sia visivamente che sottraendo i valori della componente modificata da quella originale (maggiore è la sfumatura del colore, minore è la differenza):
Link alle immagini che non sono state caricate su habrastorage
Originale —
Modificato —
Differenza —
In conclusione
Spero di essere riuscito a convincere il lettore che tali metodi sono possibili e meritano di esistere. Tuttavia, acquistare un disco rigido o un canale aggiuntivo (per la trasmissione in rete) può sembrare una soluzione molto più semplice rispetto a tentare di risparmiare in questo modo. Da un lato, è davvero così, lo sviluppo estensivo è spesso più semplice e affidabile. Dall'altro, non bisogna dimenticare la parte intensiva. Non ci sono garanzie che domani si possa andare in negozio e acquistare un altro disco rigido da mille terabyte, mentre utilizzare quelli già presenti a casa è sempre possibile.
->
Fonte: habr.com
