Crittanalisi differenziale impossibile
# Crittanalisi differenziale impossibile

La crittanalisi differenziale impossibile è una particolare forma della crittanalisi differenziale operata su cifrari a blocchi. La crittanalisi differenziale si basa sull'analisi delle differenze che si trovano nel codice cifrato con probabilità maggiore di quella standard. Contrariamente, la crittanalisi differenziale impossibile considera principalmente le differenze che sono impossibili da ottenere (in termini probabilistici dette "con probabilità 0"). Sfruttando tale tecnica, sono stati proposti svariati attacchi ai più diffusi sistemi di cifratura a blocchi come AES, cifrari SPN e Rijndael.

## Storia

Una delle prime applicazioni della crittanalisi differenziale impossibile, nonostante tale nome sia stato definito nel 1998 da Biham, Biryukov e Shamir, fu durante la seconda guerra mondiale. Durante i tentativi di decifratura dei testi prodotti dalla macchina Enigma da parte dei servizi segreti inglesi, venne sfruttata una peculiarità del cifrario prodotto: non era possibile ottenere in output la stessa lettera del testo passato in input. In questo modo, ogni chiave che fosse stata provata per la decifratura del testo, poteva essere scartata se questa avesse prodotto un testo in output con le stesse lettere nelle stesse posizioni del testo in input.

## Meccanismo di attacco

Questo tipo di crittanalisi opera in modo simile alla crittanalisi differenziale considerando la probabilità con cui appaiono gli stati del processo di cifratura (eventi). Vengono quindi intercettati gli eventi che hanno probabilità 1. Dato che la combinazione di due eventi con probabilità 1 non è possibile, questa caratteristica fa sì che sia possibile scartare la chiave (o le chiavi) che hanno condotto a quel particolare processo di cifratura. Il processo di individuazione di due eventi con probabilità 1 viene definito da Biham, Alex, Biryukov e Shamir miss in the middle, in contrapposizione alla tecnica crittanalitica meet-in-the-middle. La metafora indica due individui (eventi) che, provenendo da due direzioni differenti (due condizioni di partenza diverse) non si incontrano mai a metà del cammino (due stati con probabilità 1 non possono coesistere). Al procedimento di eliminazione progressiva di chiavi impossibili viene dato il nome di "setacciatura".

