Quando parliamo di steganografia, la gente immagina terroristi, pedofili, spioni, o al meglio crittografi anarchici e altri scienziati. E in effetti, chi altro potrebbe averne bisogno? nascondere qualcosa agli sguardi esterni? Quale potrebbe essere il vantaggio per una persona comune?
Evidentemente, c'è un certo beneficio. È per questo che oggi compressiamo i dati utilizzando metodi di steganografia. Alla fine, il lettore potrà persino utilizzare i propri preziosi archivi fotografici JPEG per aumentare lo spazio libero nel file system.
Cosa?
Se il lettore ricorda, la steganografia è quegli strani algoritmi che permettono di nascondere l'esistenza di un'informazione all'interno di un'altra. In parole più semplici: immagine + file == più o meno la stessa immagine, ma non proprio (al posto delle immagini può esserci qualunque cosa, ma di solito è tutto più chiaro). Non dovrebbe esserci un metodo semplice per determinare se c'è qualcosa all'interno oppure no.
Ma se non si può distinguere l'uno dall'altro, c'è davvero una differenza? Dal punto di vista del consumatore, l'utente non è preoccupato per la precisione matematica (riflessa in un insieme specifico di bit), ma solo per ciò che percepisce.
Ad esempio, guardiamo tre immagini di un adorabile cane:
Attenzione, JPEG!
Nonostante la enorme differenza di dimensioni, pochi sceglierebbero la terza versione. D'altra parte, la differenza tra le prime due foto non è così evidente e la quantità di informazioni in esse (dal mio punto di vista) può essere considerata equivalente.
Questo principio in sé è già antico e viene da molti anni utilizzato attivamente nei metodi di compressione delle informazioni con perdita. Ma demolire non è costruire, ci interessa il lato più avanzato della questione. È possibile incorporare informazioni aggiuntive nella dimensione N in un file in modo che la sua dimensione aumenti di M < N, e le modifiche non siano visibili all'utente?
Certo che è possibile. Ma vale la pena fare subito un paio di avvertenze:
- In primo luogo, il metodo deve essere universale e fornire risultati positivi nella maggior parte dei dati in ingresso. Cioè, in media, per un ingresso arbitrario, dovrebbe verificarsi una reale riduzione della quantità di informazioni memorizzate. "In media" significa che possono verificarsi casi opposti, ma non devono predominare.
- In secondo luogo, la dimensione del contenitore compresso prima dell'inserimento delle informazioni deve essere maggiore rispetto a quella di una modifica compressa in modo simile. Semplicemente inserire una serie di bit in un'immagine BMP utilizzando il metodo LSB non rappresenta una compressione steganografica, poiché, se sottoposta a un algoritmo DEFLATE, l'immagine originale sarà probabilmente visibilmente più piccola.
- In terzo luogo, è necessario condurre e confrontare i risultati rispetto ai dati già compressi con metodi classici. Questo permetterà di eliminare l'effetto probabilistico della loro ridondanza e di eseguire una compressione più efficace in generale.
Dove?
L'uso della steganografia implica che, oltre alle informazioni da comprimere, siano necessari dei contenitori in cui queste saranno integrate. La quantità massima di informazioni incorporabili dipende molto dalle proprietà specifiche, ma è molto più facile da scalare in base al loro numero. Pertanto, il formato dei contenitori deve essere comune, affinché l'utente ne abbia un numero sufficiente per ottenere anche un minimo risultato dal processo di "compressione".
In questo contesto, buoni candidati sono i file grafici, audio e video. Tuttavia, a causa della varietà di formati e codec, in pratica abbiamo a disposizione un numero di opzioni non così vasto.
Tenendo conto di tutto ciò, la mia scelta è ricaduta su JPEG. È presente praticamente ovunque, è ampiamente utilizzato sia per scopi personali che aziendali, diventando quasi il formato de facto per la maggior parte delle immagini.
C̶o̶m̶e̶?
Successivamente ci sono schemi e descrizioni tecniche senza particolari spiegazioni, quindi coloro che lo desiderano possono saltarli scorrendo fino alla sezione "Tecnologia avanzata".
Caratteristiche comuni
Per integrare i dati in un determinato luogo, è necessario prima stabilire dove. Nel file system possono essere presenti un numero illimitato di fotografie diverse, tra le quali l'utente potrebbe voler 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, si può semplicemente utilizzare un insieme di nomi (o, meglio ancora, un'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 file system, rendendo difficile la loro identificazione corretta. Pertanto, è necessario memorizzare i loro hash (md5 è sufficiente) dopo aver effettuato tutte le modifiche.
La ricerca iniziale tramite espressioni regolari non ha senso farla su tutto il file system; è sufficiente specificare una certa directory radice. Qui verrà anche salvato un file-archivio speciale che conterrà quegli hash, insieme ad altre informazioni meta necessarie per il ripristino successivo delle informazioni da comprimere.
Tutto ciò si applica in egual misura a qualsiasi implementazione di un algoritmo di compressione dati steganografica. I processi di compressione e decompressione dei dati possono essere chiamati imballaggio e disimballaggio.
F5
Ora che è chiaro cosa stiamo facendo e perché, resta da descrivere l'algoritmo per raggiungere l'obiettivo. Ricordiamo il processo di codifica di un file JPEG (grazie al wiki della biblioteca nazionale Bauman):
Osservandolo, è meglio fare subito qualche osservazione:
- La dimensione di un file JPEG può essere considerata ottimale, anche senza provare a comprimerlo con un qualche software come WinRAR;
- È possibile modificare solo le informazioni memorizzate (quella in uscita dalla trasformata discreta del coseno, DCT) per garantire prestazioni accettabili.
- Per non perdere dati in modo significativo per l'utente a livello industriale, è necessario apportare il minimo di modifiche a ciascuna singola immagine;
A queste condizioni si adatta una serie di algoritmi, con cui è possibile familiarizzare . Il più avanzato di essi è l'algoritmo a cura di Andreas Westfeld, che lavora con i coefficienti DCT della componente di luminanza (l'occhio umano è meno sensibile proprio ai suoi cambiamenti). Il suo schema generale di lavoro con un file JPEG esistente è rappresentato dalla seguente schematizzazione:
Il blocco F5 utilizza una tecnica avanzata di embedding basata sulla codifica della matrice. Maggiori dettagli su di essa e sull'algoritmo stesso possono essere trovati nel link sopra; ciò che ci interessa innanzitutto è che con questa tecnica è possibile apportare meno modifiche durante l'inserimento della stessa quantità di informazioni, man mano che aumenta la dimensione del contenitore utilizzato. Per eseguire l'algoritmo stesso, è necessaria solo una semplice operazione di (de)codifica di Huffman e RLE.
Le modifiche avvengono sui coefficienti interi e consistono nella riduzione del loro valore assoluto di un'unità, il che consente, in generale, di utilizzare F5 per la compressione dei dati. Infatti, un coefficiente ridotto nel valore assoluto occupa probabilmente meno bit dopo l'applicazione della codifica di Huffman, a causa della distribuzione statistica dei valori in JPEG.
Nel caso di formazione di uno zero (il cosiddetto accorciamento), la quantità di informazioni salvate diminuisce della sua dimensione, poiché l'ex coefficiente autonomo diventa parte della sequenza RLE codificata di zeri:
Modifiche
La protezione dei dati e la loro compressione sono compiti ortogonali; pertanto, si può trascurare la permutazione della password segreta dall'algoritmo originale. Inoltre, è fondamentale sapere esattamente come estrarre i dati, quindi tutte le informazioni necessarie al riguardo (quali contenitori sono stati utilizzati, in quale ordine, ecc.) devono essere registrate in un file separato e devono essere accessibili per la lettura da parte dell'archiviatore.
L'algoritmo originale è progettato per trasmettere messaggi segreti, quindi funziona solo con un contenitore alla volta, assumendo che l'utente divida manualmente i dati in parti se necessario. Inoltre, durante l'inserimento indipendente in ogni contenitore, è necessario sapere in anticipo quanti bit di dati inserire in ciascuno. Pertanto, è consigliabile unire i coefficienti di ciascun elemento della libreria in un grande astra e lavorare con esso secondo l'algoritmo originale.
Poiché l'originale F5 permette 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 di descrivere l'algoritmo dall'inizio alla fine, in modo da non tenere il lettore all'oscuro:
- L'utente definisce i dati binari compressibili M e la libreria L utilizzando un'espressione regolare e la directory principale di ricerca;
- In ordine di sequenza nel file system, gli elementi della libreria formano MC:
- Dai dati del file viene decodificata una serie di coefficienti C;
- MC <- MC | C;
- Si determina il parametro k partendo dalla terribile disuguaglianza:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Si prende successivamente
n = (1 << k) - 1i bit meno significativi degli elementi non nulli di MC e si scrivono ina:- Si calcola la funzione hash magica
f, che mappa una parola di n bitain k bits; - Se
s == 0, quindi non c'è nulla da modificare e l'algoritmo passa ai coefficienti successivi; - Ridurre il valore assoluto del coefficiente che risponde al
s-esimo bit nella parolaa; - Se a seguito della riduzione si è verificata una riduzione (il coefficiente è diventato 0), ripetere il passaggio dall'inizio;
- Si calcola la funzione hash magica
- Tutti i coefficienti sono codificati in RLE e Huffman, e sono scritti nei file originali;
- Nel file dell'archivio viene registrato il parametro k;
- Dal file L, nel loro ordine originale, si calcola l'hash MD5 e si scrive nel file dell'archivio.
Tecnologie avanzate
La forma naïve dell'algoritmo e la sua implementazione in altri linguaggi di alto livello (soprattutto quelli con garbage collection) avrebbero dato prestazioni terribili, quindi tutte queste complessità le ho realizzate in puro C e ho effettuato una serie di ottimizzazioni sia per la velocità di esecuzione che per la memoria (non potete immaginare quanto pesano queste immagini senza compressione, anche fino al DCT). Ma, ad ogni modo, inizialmente la velocità di esecuzione lasciava molto a desiderare, dunque non descriverò l'intero processo e i metodi utilizzati.
La portabilità è stata raggiunta utilizzando una combinazione delle librerie libjpeg, pcre e tinydir, per cui sono grato. Di default, tutto viene compilato tramite il solito make, quindi gli utenti Windows devono installare Cygwin o occuparsi di Visual Studio e delle librerie da soli.
L'implementazione è disponibile come utility da console e libreria. Maggiori dettagli sull'uso dell'ultima possono essere trovati nel README del repository su GitHub, il cui link fornirò alla fine del post. Ora passiamo alla descrizione e alla dimostrazione del lavoro.
Come si utilizza?
Fai attenzione. Le immagini utilizzate possono essere spostate, rinominate e copiate a piacere. Tuttavia, è importante prestare estrema attenzione e non alterare in alcun modo il loro contenuto. Modificare anche un solo bit porterà a violare l'hash e renderà impossibile il recupero delle informazioni.
Supponiamo che dopo la compilazione abbiamo ottenuto un file eseguibile f5ar. Possiamo analizzare la dimensione della libreria per calcolare le possibilità del suo utilizzo con il flag -a: ./f5ar -a [cartella di ricerca] [espressione regolare compatibile con Perl]. Il pacchetto viene creato con il comando ./f5ar -p [cartella di ricerca] [espressione regolare compatibile con Perl] [file da impacchettare] [nome dell'archivio], mentre l'estrazione avviene con ./f5ar -u [file dell'archivio] [nome del file ripristinato].
Dimostrazione del funzionamento
Per mostrare l'efficacia del metodo, ho caricato una collezione di 225 foto di cani completamente gratuite dal servizio . Ognuna di esse possiede una qualità leggermente superiore rispetto alle normali fotografie degli utenti. Tuttavia, ognuna è stata ricodificata utilizzando libjpeg per ridurre l'impatto delle peculiarità di codifica della libreria sulla dimensione complessiva. Per indicare il peggior esempio di dati comprimibili, è stato generato un file casuale di 36 metri (poco più del 5% della dimensione totale) distribuito uniformemente.
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 byte
Capacità possibile fino a 102618787 byte
Compressione... completata in 32.6s
Salvataggio dell'archivio... ok
$ ./f5ar -u dogs/dogs.f5ar estratto
Inizializzazione dell'archivio... ok
Lettura del file dell'archivio... ok
Riempimento dell'archivio con file... completato in 1.2s
Decompressione... completata in 17.5s
Scrittura dei dati estratti... ok
$ sha1sum binary_data estratto
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 binary_data
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 estratto
$ du -sh dogs/
563M dogs/O un'istantanea per gli appassionati
Come si può vedere, dai 633 + 36 == 669 megabyte di dati sul disco rigido siamo arrivati a un più piacevole 563, il che ci dà un rapporto di compressione di circa 1,188. Questa differenza radicale è spiegata da perdite estremamente piccole, simili a quelle ottenute con l'ottimizzazione dei file JPEG con metodi classici (come tinyjpg). Naturalmente, utilizzando la compressione steganografica, l'informazione non viene semplicemente "persa", ma utilizzata 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 percepibile ad occhio nudo. Sotto il spoiler qui sotto, il lettore può valutare la differenza sia visivamente che sottraendo i valori della componente modificata da quelli originali (più il colore è attenuato, minore è la differenza):
Link alle immagini che non sono riuscite a essere caricate su habrastorage
Originale —
Modificato —
Differenza —
In conclusion
Spero di aver convinto il lettore che tali metodi siano possibili e meritino di esistere. Tuttavia, acquistare un disco rigido o un canale aggiuntivo (per il trasferimento di rete) può sembrare un'uscita 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 dobbiamo dimenticare l'intensivo. Infatti, non c'è alcuna garanzia che domani si possa andare in negozio e comprare un altro disco rigido da mille terabyte, mentre utilizzare quelli che abbiamo già a casa è sempre un'opzione.
->
Fonte: habr.com
