A Novel Memory-Efficient MitM Attack on Ascon-Hash

Nel mondo digitale, la sicurezza si affida spesso a un delicato equilibrio tra forza ed efficienza. Per i miliardi di piccoli dispositivi alimentati a batteria che compongono l'Internet delle Cose — sensori nelle fabbriche, contatori intelligenti e monitor medici — la potenza di calcolo è scarsa, e la memoria lo è ancora di più. Questi dispositivi hanno bisogno di strumenti crittografici che siano abbastanza robusti da mantenere sicuri i dati, ma abbastanza leggeri da funzionare senza esaurire una batteria o riempire un minuscolo chip. Ascon è una soluzione leader per questa sfida, una famiglia di metodi di cifratura e hashing progettata specificamente per questi ambienti con risorse limitate. Per garantire che Ascon rimanga sicuro, i ricercatori lo testano costantemente contro attacchi sofisticati, cercando di trovare la via più breve per violarne il codice. Uno degli strumenti più potenti in questo arsenale è l'attacco "meet-in-the-middle" (incontro a metà), una strategia in cui un attaccante lavora a ritroso dal risultato finale e in avanti dal punto di partenza, sperando di incontrarsi a metà con una corrispondenza. Tuttavia, questa strategia ha tradizionalmente richiesto una quantità massiccia di memoria per memorizzare i milioni di passaggi intermedi, un requisito che spesso rendeva l'attacco impraticabile per i medesimi dispositivi che Ascon è destinato a proteggere.

Un team di ricercatori ha ora sviluppato un nuovo modo per eseguire questo attacco che riduce drasticamente la memoria necessaria, rendendo il test molto più realistico per i sistemi leggeri. In uno studio focalizzato sulla funzione Ascon-Hash, gli autori hanno dimostrato di poter eseguire l'attacco su una versione ridotta del sistema utilizzando significativamente meno spazio di archiviazione rispetto a quanto precedentemente ritenuto possibile, senza sacrificare la velocità del calcolo. Trattando il problema come un complesso puzzle di vincoli logici, hanno trovato un modo per filtrare i dati non necessari prima ancora che dovessero essere memorizzati. Il loro lavoro mostra che, per una versione a tre round dell'hash, la memoria richiesta può essere ridotta da una complessità di 2^24 a 2^14. Per una versione a quattro round, la riduzione è ancora più drammatica, facendo scendere il requisito da una complessità di 2^34 a 2^12. Questo traguardo non si limita ad abbassare il costo dell'attacco; fornisce un quadro più nitido e accurato di quanto sia realmente sicura Ascon di fronte a un avversario con risorse limitate.

I ricercatori hanno iniziato riconoscendo che i precedenti tentativi di violare Ascon utilizzando strumenti di ricerca automatizzata si erano scontrati con un muro di utilizzo della memoria. Sebbene i computer fossero diventati più veloci nel trovare il percorso corretto attraverso la cifratura, il processo richiedeva comunque che l'attaccante tenesse in memoria una vasta libreria di risultati intermedi, proprio come cercare di risolvere un labirinto scrivendo ogni singola svolta su un foglio di carta separato. Se il labirinto è abbastanza grande, finisci la carta molto prima di trovare l'uscita. Il team ha capito che la chiave per risolvere questo problema non era solo trovare il percorso più velocemente, ma essere più intelligenti su cosa scrivere. Hanno utilizzato un metodo chiamato "satisfiability solving" (risoluzione di soddisfacibilità), che è essenzialmente un modo per chiedere a un computer di trovare un insieme di condizioni che renda vera una complessa affermazione logica. Ciò ha permesso loro di mappare i punti specifici nel processo di cifratura in cui i calcoli in avanti e all'indietro potrebbero potenzialmente incontrarsi.

Una volta mappati questi potenziali punti di incontro, i ricercatori hanno applicato una serie di filtri algebrici per pulire i dati. Hanno notato che molti dei vincoli che governano la cifratura potevano essere separati in relazioni lineari semplici e in altre più complesse e non lineari. Le parti lineari erano dirette; potevano essere semplificate utilizzando tecniche matematiche standard per rimuovere le informazioni ridondanti, restringendo efficacemente l'elenco delle possibilità che il computer doveva tracciare. Le parti non lineari erano più difficili, ma il team ha sviluppato un metodo per riorganizzarle in una forma triangolare, consentendo di risolvere certe variabili in base ad altre. Questo processo ha eliminato la necessità di calcolare ed esplicitare e memorizzare quelle specifiche variabili, riducendo ulteriormente l'impronta di memoria.

L'innovazione più significativa è arrivata nel modo in cui hanno gestito i vincoli complessi rimanenti che non potevano essere facilmente semplificati. Invece di memorizzare ogni possibile risultato, i ricercatori hanno utilizzato questi vincoli rimanenti per creare un "indice residuo", una sorta di etichetta o tag digitale. Mentre generavano l'elenco dei potenziali percorsi in avanti, assegnavano a ciascuno un tag basato sulle sue proprietà specifiche. Fondamentalmente, si sono resi conto che il percorso all'indietro poteva corrispondere a un percorso in avanti solo se i loro tag erano compatibili. Ciò significava che il computer non aveva bisogno di tenere in memoria ogni singolo percorso in avanti; doveva solo tenere quelli che portavano un tag che il percorso all'indietro poteva potenzialmente raggiungere. Nelle specifiche configurazioni testate, questo filtraggio è stato così efficace che ha ridotto l'intero elenco di necessari percorsi in avanti a un unico, minuscolo secchio di dati.

I risultati di questo nuovo approccio sono stati sorprendenti. Quando applicato a una versione a tre round di Ascon-Hash, il metodo ha mantenuto la stessa velocità degli attacchi precedenti ma ha ridotto il requisito di memoria da una complessità di 2^24 a 2^14. Per la versione a quattro round, la riduzione è stata ancora più profonda, tagliando il bisogno di memoria da una complessità di 2^34 a 2^12 rispetto al precedente miglior metodo. I ricercatori hanno verificato che questo filtraggio aggressivo non avesse accidentalmente scartato soluzioni valide; hanno controllato che i dati rimanenti soddisfacessero ancora tutte le regole originali del sistema di cifratura. Lo studio conferma che, analizzando attentamente la struttura della cifratura e applicando questi filtri logici, è possibile eseguire test di sicurezza profondi con una frazione delle risorse precedentemente ritenute necessarie. Questo lavoro suggerisce che il margine di sicurezza di Ascon negli ambienti con risorse limitate viene valutato con maggiore precisione, garantendo che gli standard crittografici che proteggono il nostro mondo connesso siano robusti quanto appaiono.