Compromesso tempo-memoria

Il compromesso tempo-memoria (o compromesso spazio-tempo), in informatica, è una situazione dove l'utilizzo della memoria può essere ridotto al prezzo di un rallentamento della velocità di esecuzione del programma o, viceversa, il tempo di calcolo può essere ridotto al prezzo di un incremento dell'utilizzo della memoria. Al variare dei relativi costi di cicli di CPU, spazio RAM e spazio su disco rigido possono cambiare radicalmente le scelte per i compromessi tempo-memoria. Spesso, approntare un compromesso tempo-memoria può portare un programma ad essere eseguito molto più velocemente.

Applicazioni in campo informatico modifica

La situazione più comune è un algoritmo che opera su una tabella di associazione: una implementazione può includere l'intera tabella, cosa che riduce il tempo di calcolo ma incrementa la quantità di memoria necessaria; un'altra implementazione può calcolare la tabella al momento, cosa che incrementa il tempo di calcolo ma riduce la quantità di memoria necessaria.

Un compromesso spazio-tempo può essere applicato al problema della memorizzazione dei dati. Se i dati sono memorizzati in forma non compressa possono prendere molto spazio ma richiedono meno tempo per essere letti rispetto a dati memorizzati in forma compressa (questo a causa del fatto che la compressione dei dati riduce lo spazio richiesto per la loro archiviazione ma richiede del tempo per eseguire l'algoritmo di compressione). A seconda delle necessità può essere utile l'una oppure l'altra soluzione. Un altro esempio è la visualizzazione di formule matematiche su siti web con informazioni prevalentemente in formato testuale come ad esempio la Wikipedia stessa. La memorizzazione del solo sorgente LaTex ed il rendering come immagine solo al momento in cui la pagina è richiesta è un processo che permette di risparmiare spazio su disco ma comporta più tempo per la visualizzazione. L'altra soluzione è di renderizzare l'immagine quando la pagina viene modificata e di memorizzarla su disco per caricarla al momento della visualizzazione della pagina. Questa soluzione comporta un consumo maggiore di spazio su disco ma un tempo minore per l'accesso ai dati. È doveroso precisare che ci sono rare situazioni in cui è possibile lavorare direttamente con i dati compressi, come nel caso di indici di immagini compresse dove è più rapido lavorare con la compressione che senza di essa.

Applicazioni in campo crittografico modifica

In campo crittografico, dove un attaccante cerca di violare un cifrario con qualunque tecnica che gli consenta risultati migliori di quelli ottenibili applicando la semplice forza bruta, i vantaggi di un compromesso tempo-memoria sono chiaramente visibili.

La prima applicazione del compromesso tempo-memoria in questo ambito è ad opera di Martin Hellman che nel 1980 dimostrò come l'uso di tabelle precompilate per la ricerca delle possibili chiavi segrete dei cifrari a blocchi distribuisse lo spazio delle possibili chiavi tra la memoria ed il tempo di calcolo^[1]. Questo metodo crittanalitico fu poi applicato ai cifrari a flusso da Alex Biryukov ed Adi Shamir considerando anche di conoscere i dati in output. Recentemente Philippe Oechslin ha pubblicato una versione migliorata dell'idea originale di Hellman grazie alla quale il tempo computazionale si riduce ulteriormente utilizzando le tabelle arcobaleno^[2]. Oechslin ha utilizzato la sua tecnica anche come metodo per il recupero delle password del sistema operativo Microsoft Windows^[3]^[4].

Le tabelle arcobaleno sono particolari tabelle di associazione che utilizzano hash precompilati da una funzione crittografica di hash per violare le chiavi segrete in minuti invece che in settimane o mesi. Riducendo la dimensione della tabella arcobaleno si incrementa il tempo richiesto per iterare su tutti gli hash possibili. L'attacco Meet-in-the-middle usa un compromesso tempo-memoria per trovare la chiave crittografica con sole 2n + 1 cifrature (ed uno spazio di O(2n)) contro le 22n cifratura stimate (ma con uno spazio di soli O(1)) di un attacco semplice.