# Salsa20

Il Salsa20 è un cifrario a flusso sviluppato da Daniel J. Bernstein nel 2005 e selezionato per il portafoglio del progetto eSTREAM per il Profilo 1 (implementazione software). È costruito su una funzione pseudo-casuale basata sull'addizione a 32 bit, sull'OR esclusivo (XOR) e sulle operazioni di rotazione dei bit, che utilizza chiavi a 256 bit (ma possono essere utilizzate anche chiavi a 128 bit) e nonce a 64 bit. La funzione lavora effettuando 20 passaggi, da cui il nome dell'algoritmo.

## Implementazione

Il Salsa20 è stato sviluppato focalizzandosi su due punti principali:
* utilizzare operazioni semplici;
* ottenere elevata velocità di calcolo.
Il primo punto è stato soddisfatto utilizzando semplici operazioni di addizione modulo 32, operazioni di XOR e rotazioni delle word a 32 bit.
Il secondo punto è stato soddisfatto in parte con l'uso delle operazioni di cui al precedente punto ed in parte strutturando l'algoritmo in modo che la chiave di cifratura ed il nonce fossero utilizzati direttamente come input della funzione interna senza dover ricorrere a processi iniziali di gestione della chiave (key scheduling) e setup del vettore di inizializzazione (IV setup), operazioni in genere abbastanza gravose in termini di complessità elaborativa.
Il Salsa20 espande la chiave a 256 bit ed il nonce a 64 bit in un keystream di 2$^{70}$ byte. Per cifrare o decifrare un messaggio di n byte l'algoritmo combina tramite XOR questi byte con i primi n byte del keystream, scartando i restanti. Il keystream è generato in blocchi di 512 bit, ed ogni blocco è costituito da un hash indipendente della chiave, dal nonce e dal numero del blocco stesso espresso con un contatore a 64 bit. Grazie a questo contatore il keystream può essere anche utilizzato con accesso casuale permettendo così all'utente di utilizzare qualsiasi blocco desideri.

## Varianti

Il Salsa20 deve il suo nome al fatto che esegue 20 passaggi di mescolamento del suo input. Esistono anche versioni con il numero dei passaggi ridotti ad 8 e 12 chiamate, rispettivamente, Salsa20/8 e Salsa20/12. Queste versioni sono state introdotte non per sostituire l'algoritmo originale ma per ottenere migliori prestazioni nei benchmark eseguiti all'eSTREAM: proprio il Salsa20/12 è stato selezionato per essere inserito nel portafoglio finale degli algoritmi selezionati dal progetto, grazie all'ottimo bilanciamento fra prestazioni e sicurezza.

## Sicurezza

Il primo attacco condotto positivamente contro il Salsa20 è di Paul Crowley, che nel 2005 ha utilizzato la crittoanalisi differenziale troncata per violare una versione ridotta con soli 5 passaggi (Salsa20/5) dell'algoritmo, con un tempo di calcolo stimato in 2$^{165}$. Nel 2006 Fischer, Meier, Berbain, Biasse e Robshaw hanno descritto un attacco simile condotto contro il Salsa20/6, con un tempo di calcolo stimato in 2$^{177}$, ed uno contro il Salsa20/7 (2$^{217}$).
Nel 2008 Aumasson, Fischer, Khazaei, Meier e Rechberger hanno descritto sia un attacco contro il Salsa20/7, con un tempo computazionale di 2$^{151}$, sia uno contro il Salsa20/8, con un tempo di calcolo di 2$^{251}$. Quest'ultimo attacco si basa sull'utilizzo di un nuovo concetto di analisi probabilistica di bit neutri nella chiave per il rilevamento probabilistico di un probabile attacco differenziale troncato. Questo attacco può essere utilizzato per recuperare una chiave a 128 bit del Salsa20/7.
Non esistono attacchi noti al Salsa20/12 ed al Salsa20.