È possibile definire uno schema che assicuri una copertura assoluta, allo stesso modo del cifrario a blocco monouso in crittografia?

Supponiamo che Alice usi un segnale video digitale non compresso come copertura C, e che codifichi il testo segreto E nelle frequenze veramente basse. Per esempio, il k-esimo bit di E diventa il bit meno importante di uno dei pixel del k-esimo fotogramma del video, e la scelta del pixel è specificata dalla k-esima parola di un cifrario a blocco monouso condiviso con Bob. Intuitivamente ci aspettiamo che un attacco sia impossibile: il testo segreto sarà completamente nascosto nel rumore intrinseco del video. C'è qualche modo per dimostrarlo?

Dobbiamo prima chiederci come deve essere una prova di copertura. Una definizione accettabile di stegosistema sicuro potrebbe essere un sistema nel quale nessun intruso possa accorgersi di differenze tra il testo di copertura C e il testo steganografato S contenente l'informazione nascosta E, a meno che non conosca la chiave K. Come per la crittografia, possiamo supporre che l'intruso sia una macchina di Turing probabilistica polinomiale nel caso necessitassimo di sicurezza computazionale, e possiamo assumere che possa esaminare tutte le possibili chiavi nel caso necessitassimo di sicurezza assoluta.

Alla fine, l'intruso riuscirà a vedere il messaggio nascosto, e quindi lo stegosistema sicuro deve generare un numero sufficiente di messaggi nascosti sensati da un qualsiasi stego-testo S dato, e il numero di questi messaggi non deve essere distinguibile in alcun modo dallo stego-testo e da un qualsiasi testo di copertura.

Quello che rende la steganografia più complessa dei problemi di segretezza o autenticazione è che dipendiamo tantissimo dal nostro modello di testo di copertura.

Chi lavora in Teoria dell'Informazione spesso assume che qualsiasi sorgente di informazione può essere compressa in modo tale che non vi sia nessuna ridondanza. Questa assunzione può essere molto utile per trovare limiti asintotici o risultati di capacità, ma ha anche un effetto abbastanza curioso se applicata alla steganografia.

Supponiamo di aver creato un sistema perfetto di codifica in una scatola nera fisica che può sia comprimere sia decomprimere dati di un tipo particolare (audio, video, o qualsiasi altra cosa). Per compressione perfettamente efficiente si intende che gli oggetti compressi saranno condensati in una serie di stringhe di bit di lunghezza uguale. In questo modo Alice potrà prendere un qualsiasi testo segreto che voglia nascondere e farlo passare dentro il compressore. Il risultato sarà una registrazione audio, video o altro, perfettamente accettabile.

Questo esempio non è una prova rigorosa. È possibile, per esempio, che un dispositivo possa decomprimere una stringa di bit casuale di lunghezza n in un tipo particolare di oggetto con probabilità polinomiale di 1/n. Questo risultato può essere sufficiente ad andare avanti in molti casi di teoria delle informazioni, ma non va bene per l'esempio sopra. Infatti mostra che molte intuizioni classiche di teoria delle informazioni possono servire a poco per descrivere il comportamento di sistemi steganografico. Abbiamo quindi che la steganografia pratica può funzionare solo se la compressione è inefficiente. Se fosse efficiente sarebbe impossibile risalire al testo nascosto.

Se Alice e Bob usano un blocco a cifratura monouso condiviso per decidere quale bit del testo di copertura sarà sostituito da un bit di testo segreto, possiamo considerare il blocco come a un canale di selezione. Se Eva è veramente molto potente, può provare tutte le possibili cifrature (inclusa quella corretta), e quindi il numero di cifrature con le quali nascondere il testo segreto deve essere abbastanza grande da non far sospettare che Alice stia mandando del testo steganografato piuttosto che un testo in chiaro.

Può essere utile a questo punto richiamare l'esempio del libro usato per la cifratura. Alice e Bob condividono un libro e cifrano un messaggio come una serie di puntatori a parole. In questo modo il numero "78216" può significare pagina 78, paragrafo 2 e 16-esima parola. I libri con i codici devono essere scelti in modo che Eva non sappia quali possano essere, e bisogna far attenzione a non riutilizzare la medesima parola del libro. La cifratura tramite un libro è un esempio di canale di selezione. In questo caso si parte dal libro e successivamente viene generato il testo segreto, mentre in uno stegosistema si parte dal testo da nascondere e si genera successivamente lo stego-testo; ma nel caso in cui il canale di selezione sia veramente random (un blocco a cifratura monouso), allora sono la stessa cosa, perché un messaggio qualunque può essere nascosto in un testo di copertura qualsiasi o sufficientemente lungo.

Un libro ripetitivo avrà quindi una bassa capacità, e sarà possibile usare una piccola percentuale delle sue parole per costruire degli attacchi seri. Allo stesso modo, se il testo di copertura usato nello stegosistema gode di statistiche insolite (ad esempio un numero non equilibrato di uni e zeri) allora la sua capacita steganografica sarà bassa, in quanto solo una piccola porzione dei possibili messaggi cifrati potrà sembrare abbastanza casuale.

L'approccio coi canali di selezione può suggerire un'idea migliore.
Continuiamo ad usare un blocco a cifratura monouso non per selezionare un pixel ma una serie di essi, e nascondiamo il bit di testo segreto in base alla loro parità. In questo modo l'informazione può essere nascosta cambiando uno qualsiasi dei pixel che possono essere cambiati senza che creino troppo rumore.

Dal punto di vista della teoria dell'informazione, se ciascun bit del testo di copertura e "1" con probabilità 0.6, allora la probabilità che un paio di bit abbiano parità 1 è 0.52; se consideriamo tre bit, la parità è 1 con probabilità 0.504, e così via. Allora codificando ciascuno bit nascosto in base alla parità di k bit dello stego-testo, possiamo ridurre l'effetto che il processo steganografico ha sulle statistiche dello stego-testo sotto qualsiasi soglia arbitraria; e poiché il miglioramento è geometrico, non dovremo in pratica incrementare k di molto. È come se utilizzando più bit nel canale di selezione (ad esempio incrementando il valore di k) aumentassimo anche i bit che possiamo nascondere nel nostro testo di copertura.