Verso la Verifica Formale degli Algoritmi di Generazione Password nei Password Manager

1. Introduzione

I password manager (PM) sono strumenti critici raccomandati dagli esperti di sicurezza per mitigare le vulnerabilità associate all'autenticazione tramite password. Facilitano l'uso di password forti e uniche, alleviando il carico cognitivo per gli utenti. Tuttavia, l'adozione diffusa da parte degli utenti è ostacolata da una mancanza di fiducia in queste applicazioni. Questo documento identifica la funzione di generazione casuale di password (RPG) come un fattore chiave che influenza la fiducia degli utenti. Gli autori sostengono che un'implementazione RPG formalmente verificata e dimostrabilmente sicura è essenziale per colmare questo divario di fiducia e incoraggiare l'adozione dei PM. Il contributo principale del documento è proporre tale implementazione di riferimento, con dimostrazioni formali di correttezza funzionale e proprietà di sicurezza utilizzando il framework EasyCrypt.

2. Algoritmi Correnti di Generazione Password

Il documento esamina 15 password manager, concentrandosi su tre esempi open-source e ampiamente utilizzati: il gestore integrato di Google Chrome, Bitwarden e KeePass. L'analisi rivela schemi comuni e carenze critiche nelle implementazioni esistenti.

2.1 Politiche di Composizione delle Password

I PM consentono agli utenti di definire politiche che vincolano le password generate. Queste politiche specificano la lunghezza, i set di caratteri consentiti (es. minuscole, maiuscole, numeri, caratteri speciali) e le occorrenze minime/massime per set. Il documento fornisce una tabella comparativa dettagliata (Tabella 1 nel PDF) che mostra le opzioni di politica nei tre PM studiati. Osservazioni chiave includono lunghezze massime variabili (fino a 30.000 in KeePass), definizioni diverse di "caratteri speciali" e una gestione incoerente dei "caratteri simili" (come 'l', '1', 'O', '0') per evitare ambiguità visive. KeePass offre il controllo più granulare, consentendo set personalizzati di inclusione/esclusione e la rimozione dei duplicati.

2.2 Generazione Casuale di Password

Gli algoritmi esaminati seguono generalmente un processo in due fasi: 1) Generare caratteri casuali per soddisfare le occorrenze minime richieste per ogni set di caratteri specificato. 2) Riempire la lunghezza rimanente della password con caratteri casuali da qualsiasi set che non abbia raggiunto il suo limite massimo di occorrenze. Infine, la sequenza di caratteri viene permutata casualmente. Il documento implica che, sebbene questa logica sia semplice, la sua implementazione—in particolare la fonte di casualità e l'applicazione di vincoli complessi—è raramente specificata o verificata formalmente, lasciando spazio a bug sottili che potrebbero indebolire la sicurezza.

3. Approccio di Verifica Formale

Gli autori sostengono l'uso di metodi formali per eliminare gli errori di implementazione. Hanno selezionato EasyCrypt, un framework per costruire e verificare dimostrazioni crittografiche basate su giochi. L'approccio prevede:

1. Specifica: Definire formalmente i requisiti funzionali dell'RPG (politica di input -> password di output che soddisfa la politica).
2. Implementazione: Scrivere il codice dell'algoritmo all'interno di EasyCrypt.
3. Verifica: Dimostrare che l'implementazione riflette correttamente la specifica (correttezza funzionale).
4. Dimostrazione di Sicurezza: Modellare l'algoritmo come un gioco crittografico per dimostrare proprietà come la distribuzione uniforme degli output dallo spazio definito (sicurezza).

Questa metodologia fornisce la certezza matematica che il codice si comporti esattamente come previsto e possieda le proprietà di sicurezza desiderate, assumendo che i primitivi crittografici sottostanti (generatore di numeri casuali) siano sicuri.

4. Implementazione di Riferimento Proposta

Il documento propone un nuovo design RPG modulare destinato a servire come riferimento verificato. Sebbene il codice completo non sia mostrato nell'estratto fornito, il design separa logicamente:

• Parser e Validatore della Politica: Garantisce che le politiche definite dall'utente siano internamente coerenti (es. i minimi non superano i massimi, i minimi totali non superano la lunghezza della password).
• Campionatore Vincolato: Il motore principale che esegue la generazione in due fasi sotto i vincoli della politica.
• Permutazione Casuale: Applica un rimescolamento finale alla sequenza di caratteri.

Ogni modulo avrebbe una specifica formale e un'implementazione verificata in EasyCrypt.

5. Dettagli Tecnici e Formulazione Matematica

La sicurezza di un RPG dipende dall'entropia e dalla distribuzione uniforme del suo output. Sia $\mathcal{P}$ l'insieme di tutte le password definite da una politica (lunghezza $l$, set di caratteri $C_1, C_2, ..., C_n$ con vincoli min/max). L'RPG ideale è una funzione $G$ che campiona uniformemente da $\mathcal{P}$.

La probabilità che una password specifica $p \in \mathcal{P}$ venga generata dovrebbe essere: $$Pr[G() = p] = \frac{1}{|\mathcal{P}|}$$ dove $|\mathcal{P}|$ è la dimensione dello spazio delle password. Un difetto comune nelle implementazioni naive è introdurre un bias, rendendo alcune password più probabili di altre. Ad esempio, se l'algoritmo prima sceglie caratteri per i set obbligatori e poi riempie il resto, le password con caratteri obbligatori all'inizio sono sovrarappresentate a meno che non venga applicato un rimescolamento perfetto. La verifica formale dimostra l'assenza di tale bias.

L'entropia $H$ della password generata (in bit) è: $$H = \log_2(|\mathcal{P}|)$$ La verifica garantisce che l'implementazione non riduca questa entropia al di sotto del massimo teorico per la politica.

6. Risultati Sperimentali e Descrizione del Grafico

Sebbene l'estratto del PDF fornito non contenga risultati sperimentali tradizionali o grafici, il suo "risultato" principale è la dimostrazione formale stessa. La verifica riuscita in EasyCrypt funge da prova definitiva. Si potrebbe concettualizzare un grafico che confronta i livelli di garanzia:

Grafico Ipotetico: Livello di Garanzia vs. Metodo di Sviluppo

• Test Tradizionali: Alta confidenza per i casi testati, ma sconosciuta per i casi limite non testati (conflitti di politica, valori limite). La copertura è limitata.
• Code Review: Confidenza moderata. Dipende fortemente dalle capacità del revisore. Potrebbe non rilevare errori logici sottili o problemi di canale laterale.
• Verifica Formale (come proposta): Garanzia massima possibile. Fornisce una dimostrazione matematica della correttezza per tutti i possibili input e proprietà di sicurezza esplicite. Il "grafico" mostrerebbe questo come il punto massimo sull'asse "Garanzia".

Il contributo del documento è spostare l'RPG dalle prime due categorie alla terza.

7. Quadro di Analisi: Un Caso di Studio Non-Codice

Considera una politica: Lunghezza=8, richiedi almeno 1 maiuscola, 1 numero, 1 carattere speciale. Un algoritmo difettoso potrebbe:

1. Posizione 1: Scegli una maiuscola casuale.
2. Posizione 2: Scegli un numero casuale.
3. Posizione 3: Scegli un carattere speciale casuale.
4. Posizioni 4-8: Riempi con caratteri casuali da tutti i set.
5. Rimescola tutti gli 8 caratteri.

Difetto: L'ordinamento iniziale fisso (M, N, S) prima del rimescolamento crea un bias. Sebbene il rimescolamento randomizzi le posizioni finali, il processo parte da una distribuzione non uniforme degli stati intermedi. Un algoritmo formalmente verificato costruirebbe l'intera password attraverso un unico processo di campionamento imparziale dallo spazio vincolato $\mathcal{P}$, o dimostrerebbe in modo provabile che il suo processo multi-step è equivalente a tale campionamento uniforme.

8. Intuizione Fondamentale e Prospettiva dell'Analista

Intuizione Fondamentale: Il documento identifica correttamente una superficie di attacco critica, ma spesso trascurata, nei password manager: l'affidabilità del generatore di password stesso. Non basta avere una cassaforte forte; se il materiale di partenza (le password) è debole o prevedibile a causa di un generatore difettoso, l'intero sistema fallisce. La mossa degli autori di applicare metodi formali—una tecnica più comune nell'hardware o nel software aeronautico—a questo problema di sicurezza consumer è sia ambiziosa che necessaria.

Flusso Logico: L'argomentazione è solida: 1) La fiducia è una barriera all'adozione dei PM. 2) L'RPG è un componente critico per la fiducia. 3) Gli RPG attuali sono implementati in modo ad-hoc senza garanzie rigorose. 4) La verifica formale fornisce il massimo livello di garanzia. 5) Forniamo un progetto per un RPG verificato utilizzando EasyCrypt. La logica collega un problema centrato sull'utente (fiducia) con una soluzione tecnica profonda (metodi formali).

Punti di Forza e Difetti:
Punti di Forza: La focalizzazione sui PM open-source è pragmatica. L'analisi comparativa delle politiche è preziosa. Proporre un'implementazione di riferimento è più utile che criticare semplicemente gli altri; stabilisce uno standard. L'uso di EasyCrypt lega il lavoro alla pratica consolidata della verifica crittografica, simile alla verifica di algoritmi come quelli in "The Security of Cryptographic Primitives" (M. Bellare, P. Rogaway).
Difetti: L'estratto fornito è un punto di partenza. La vera prova è la complessità delle dimostrazioni EasyCrypt complete per politiche del mondo reale. L'approccio assume un RNG perfetto; una vulnerabilità lì bypassa tutte le garanzie formali. Inoltre, non affronta gli attacchi di canale laterale (timing, memoria) nel binario compilato finale, una limitazione nota in altri progetti di verifica formale come la verifica del microkernel seL4.

Approcci Pratici:
1. Per gli Sviluppatori di PM: Integrare questo nucleo verificato, o uno simile, come libreria. Il costo della verifica formale è inizialmente alto ma riduce gli oneri a lungo termine delle revisioni di sicurezza e la responsabilità.
2. Per Auditor e Ricercatori: Utilizzare questo lavoro come modello per analizzare altri PM. La tabella di confronto delle politiche è una checklist pronta per le valutazioni di sicurezza.
3. Per gli Organismi di Standardizzazione (es. NIST, FIDO): Considerare la verifica formale come un requisito per certificare i moduli di generazione password, simile a come Common Criteria impone processi di sviluppo rigorosi per prodotti ad alta garanzia.
4. Per gli Utenti: Richiedere trasparenza. Preferire PM che pubblicano i loro algoritmi RPG e, idealmente, le loro prove di verifica. Questo documento fornisce il vocabolario per chiederlo.

In sostanza, questa ricerca è un invito ad alzare gli standard ingegneristici per un componente di sicurezza fondamentale. Sposta l'obiettivo da "speriamo sia sicuro" a "dimostrabilmente corretto", che è l'unico punto di riferimento accettabile per gli strumenti che proteggono le nostre identità digitali.

9. Applicazioni Future e Direzioni di Ricerca

Le implicazioni si estendono oltre i password manager:

• Token API e di Servizio: I servizi cloud e le architetture di microservizi spesso richiedono token generati. Un generatore verificato garantisce che questi segreti siano crittograficamente forti.
• Generazione di Chiavi Crittografiche: I principi si applicano alla generazione di codici di recupero leggibili dall'uomo o passphrase (tramite metodi simili a diceware) per chiavi crittografiche, dove il bias è altrettanto pericoloso.
• Integrazione con la Sicurezza Hardware: Il lavoro futuro potrebbe verificare l'interazione tra il software RPG e i generatori hardware di numeri veramente casuali (TRNG) o gli ambienti di esecuzione affidabili (TEE).
• Analisi Automatica delle Politiche: Costruire strumenti che analizzino formalmente le politiche definite dall'utente per individuare punti deboli (es. spazi di ricerca effettivamente piccoli nonostante la complessità apparente) prima ancora che avvenga la generazione.
• Standardizzazione: La direzione futura più grande è trasformare questa implementazione di riferimento in uno standard ampiamente adottato, forse come libreria autonoma (come libsodium per la crittografia) che qualsiasi applicazione possa utilizzare per la generazione verificata di segreti.

10. Riferimenti

1. Grilo, M., Ferreira, J. F., & Almeida, J. B. (2021). Towards Formal Verification of Password Generation Algorithms used in Password Managers. arXiv preprint arXiv:2106.03626.
2. Bellare, M., & Rogaway, P. (2005). Introduction to Modern Cryptography. Capitolo su Pseudorandom Functions and Permutations.
3. Klein, G., et al. (2009). seL4: Formal verification of an OS kernel. Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles.
4. National Institute of Standards and Technology (NIST). (2017). Digital Identity Guidelines (SP 800-63B).
5. Common Criteria Recognition Agreement (CCRA). Common Criteria for Information Technology Security Evaluation.
6. Chiasson, S., van Oorschot, P. C., & Biddle, R. (2006). A second look at the usability of click-based graphical passwords. Proceedings of the 3rd symposium on Usable privacy and security.
7. EasyCrypt Proof Assistant. Documentazione Ufficiale e Tutorial. https://easycrypt.info/