PROFILPELAJAR.COM

In crittografia, una funzione spugna o costruzione spugna è una classe di algoritmi con stati interni finiti che, preso un input di qualsiasi lunghezza, producono un output di lunghezza desiderata. Le funzioni spugna hanno sia usi teorici che pratici. Possono essere utilizzate per modellare o implementare molte primitive crittografiche come algoritmi crittografici di hashing, message authentication code, cifrari a flusso, cifrari a blocchi, generatori di numeri pseudo-casuali e authenticated encryption.^[1]

Costruzione

Una funzione spugna è costituita da 3 componenti:^[2]

una memoria a stati, S, contenente b bit,
una funzione, f, di lunghezza fissa che permuta o trasforma la memoria a stati,
una funzione di riempimento (padding) P

La memoria a stati è divisa in due sezioni, R di grandezza r bit e C di grandezza c = b - r. Il parametro r è chiamato bitrate, mentre il parametro c è chiamato capacità.

La funzione di riempimento aggiunge bit alla stringa in input in modo che la lunghezza della stringa sia un multiplo intero del bitrate r. La stringa in input arricchita può quindi essere divisa in blocchi di r bit.

Operazioni

La funzione spugna opera come segue:

Lo stato S viene inizializzato a zero
La stringa in input viene arricchita, ciò significa che l'input viene trasformato in blocchi di r bit utilizzando la funzione di riempimento P .
Viene calcolato lo XOR tra R e il primo blocco di r bit dell'input arricchito
S è sostituito da f(S)
Viene calcolato lo XOR tra R e il successivo blocco di r-bit (se esiste)
S è sostituito da f(S)
…

Il procedimento è ripetuto finché tutti i blocchi della stringa di input arricchita non sono elaborati ("assorbiti" nella metafora della spugna).

L'output della funzione spugna è quindi pronto per essere restituito ("strizzato") in questo modo:

I primi r bit dell'output equivalgono alla porzione R della memoria a stati,
Se si vogliono ottenere altri bit nella stringa di output allora S viene sostituita da f(S)
I prossimi r bit dell'output equivalgono alla porzione R della memoria a stati
…

Il procedimento è ripetuto finché non vengono prodotti tutti i bit di output desiderati. Se la lunghezza dell'output non è un multiplo di r allora sarà troncato.

È da notare che non viene mai applicato lo XOR tra i bit di input e la porzione C della memoria a stati, né vengono mai restituiti in output i bit di C. C viene unicamente modificata dai bit di input attraverso la funzione f. Nelle applicazioni di hashing la resistenza agli attacchi a collisione e di preimmagine dipende dal parametro C. La sua grandezza, la "capacità" c, è generalmente il doppio del livello di resistenza desiderato.

Applicazioni

Le funzioni spugna hanno sia usi teorici che pratici. Nella crittografia teorica, una funzione spugna casuale è una costruzione a spugna dove f è una permutazione o trasformazione casuale. Le funzioni spugna casuali superano più limitazioni pratiche delle primitive crittografiche di quanto faccia il modello oracolo random, ampiamente utilizzato. Questo avviene grazie alla memoria interna a stati finiti.^[3]

Le costruzioni a spugna possono anche essere utilizzate per creare primitive crittografiche. Per esempio, la funzione di hashing Keccak è implementata come funzione a spugna. Una versione di Keccak, implementata usando una memoria a stati di 1600 bit, è stata selezionata dal NIST come vincitore della competizione SHA-3. La robustezza di Keccak deriva dall'intricata permutazione ciclica della funzione f sviluppata dai suoi autori.^[4]

Note

^ (EN) The Keccak Team, Duplexing The Sponge (PDF), su sponge.noekeon.org.
^ (EN) Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche, Sponge Functions, su sponge.noekeon.org, Ecrypt Hash Workshop 2007.
^ (EN) Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche, On the Indifferentiability of the Sponge Construction, su sponge.noekeon.org, EuroCrypt 2008.
^ (EN) 2012-10-02, NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition, su nist.gov, NIST. URL consultato il 4 ottobre 2012.