Un Server di Password Cracking Oblivious: Combinazione di Tabelle di Hellman e Protocolli PIR

Indice dei Contenuti

• 1. Introduzione
• 2. Prerequisiti
  • 2.1 Tabelle di Inversione degli Hash
  • 2.2 Recupero di Informazioni Privato (PIR)
• 3. Panoramica della Soluzione
• 4. Dettagli Tecnici & Costruzione dell'Algoritmo
• 5. Protocolli PIR & Analisi della Complessità
• 6. Risultati Sperimentali
• 7. Conclusione & Lavori Futuri
• 8. Analisi Originale & Commento Esperto
• 9. Dettagli Tecnici & Formulazione Matematica
• 10. Quadro di Analisi & Caso di Studio
• 11. Applicazioni Future & Direzioni
• 12. Riferimenti

1. Introduzione

Questo articolo affronta una sfida critica per la privacy nelle operazioni di sicurezza offensiva: eseguire il cracking delle password tramite un server di terze parti senza rivelare gli hash target. Lo scenario coinvolge un penetration tester con risorse locali limitate (ad es., uno smartphone) che necessita di interrogare grandi tabelle di hash precalcolate (come le tabelle Rainbow o Hellman) ospitate in remoto. Il problema centrale è costruire un server di password cracking oblivious in cui il server non possa apprendere quali coppie password-hash il client sta tentando di craccare, preservando così il segreto operativo.

2. Prerequisiti

2.1 Tabelle di Inversione degli Hash

I sistemi di password spesso memorizzano hash crittografici. Gli attaccanti utilizzano tabelle precalcolate per invertire questi hash. I metodi principali includono:

• Tabelle di Hellman (1980): Un compromesso tempo-memoria che utilizza catene di hash e password, memorizzando solo i punti di inizio e fine catena.
• Punti Distinti di Rivest (1982): Un'ottimizzazione che utilizza valori hash "distinti" speciali come endpoint delle catene per ridurre le ricerche.
• Tabelle Rainbow (Oeschlin, 2003): Utilizza una diversa funzione di riduzione ad ogni passo della catena, generalmente più veloce ma meno adatta al modello di query basato su PIR proposto.

L'articolo sostiene che per questa specifica applicazione, le tabelle di Hellman (o varianti con punti distinti) sono più compatibili con i protocolli PIR rispetto alle tabelle Rainbow.

2.2 Recupero di Informazioni Privato (PIR)

Il Recupero di Informazioni Privato (PIR) consente a un client di recuperare un elemento da un database senza che il server apprenda quale elemento è stato accessato. Per un singolo database che contiene una stringa di n bit, uno schema PIR coinvolge:

1. Generazione della Query (Client)
2. Trasmissione della Query
3. Elaborazione della Query (Server)
4. Trasmissione della Risposta
5. Decodifica della Risposta (Client)

La complessità è misurata come $O_C$ (elaborazione client), $O_S$ (elaborazione server) e $O_T$ (trasferimento). Un limite inferiore fondamentale è che $O_S$ deve essere almeno $O(n)$ per garantire la privacy, il che significa che il server deve svolgere un lavoro proporzionale alla dimensione del database.

3. Panoramica della Soluzione

La soluzione proposta combina in modo ingegnoso le tabelle di Hellman (o tabelle a punti distinti) con un protocollo PIR a singolo database. Il server memorizza le tabelle di cracking precalcolate. Quando un client vuole craccare un hash, utilizza una query PIR per recuperare privatamente le informazioni necessarie dalle posizioni specifiche nelle tabelle di Hellman che corrispondono a potenziali corrispondenze di catena, senza rivelare gli indici di ricerca.

4. Dettagli Tecnici & Costruzione dell'Algoritmo

La costruzione si concentra sull'adattamento delle tabelle di Hellman per il PIR. Una tabella di Hellman è definita da una funzione hash crittografica $H$ e una funzione di riduzione $R$. Una catena inizia con un testo in chiaro $SP_i$, e calcola iterativamente: $X_0 = SP_i$, $X_{j+1} = H(R(X_j))$, memorizzando solo $(SP_i, EP_i)$ dove $EP_i$ è il valore finale dopo $t$ passi. Per verificare un hash $h$, il client calcola una catena di lunghezza $t$ a partire da $h$, controllando ad ogni passo se il valore intermedio corrisponde a un endpoint memorizzato. Il protocollo PIR viene utilizzato per recuperare privatamente questi confronti di endpoint dalla tabella del server.

5. Protocolli PIR & Analisi della Complessità

L'articolo analizza il sovraccarico computazionale e di comunicazione. Utilizzando un protocollo PIR computazionale standard (ad es., basato sull'assunzione di residuosità quadratica), il costo di elaborazione lato server $O_S$ scala con la dimensione della tabella. Il costo client $O_C$ e la comunicazione $O_T$ sono significativamente inferiori ma non banali. L'analisi mostra che mentre il PIR introduce un sovraccarico rispetto a una query in chiaro, questo è il prezzo necessario per una forte privacy delle query. La scelta delle tabelle di Hellman rispetto a quelle Rainbow è giustificata qui perché le tabelle Rainbow richiedono di controllare più colonne con diverse funzioni di riduzione, portando a più query PIR e a un costo complessivo più alto.

6. Risultati Sperimentali

È stato implementato un prototipo in Python. Gli esperimenti hanno dimostrato la fattibilità dell'approccio. Le metriche chiave includevano:

• Tempo di Query: Il tempo end-to-end per un tentativo di cracking oblivious, considerando il calcolo PIR e la latenza di comunicazione.
• Carico del Server: Il carico computazionale sul server per query, confermando il limite teorico $O(n)$.
• Tasso di Successo: La probabilità di craccare con successo un hash data la copertura della tabella, che si allinea con le probabilità di successo standard delle tabelle di Hellman.

I risultati hanno convalidato che il sistema funziona ma hanno evidenziato il compromesso prestazionale: la privacy ha un costo in termini di aumento del calcolo del server per query rispetto a un servizio non privato.

7. Conclusione & Lavori Futuri

L'articolo dimostra con successo un'architettura innovativa per un server di password cracking oblivious. Le direzioni per i lavori futuri includono:

• Esplorare protocolli PIR più efficienti per ridurre $O_S$ e $O_T$.
• Indagare l'uso di Ambienti di Esecuzione Fidati (TEE) come Intel SGX come alternativa o complemento al PIR crittografico.
• Estendere il modello a configurazioni PIR distribuite o multi-server per potenzialmente migliorare le prestazioni.

8. Analisi Originale & Commento Esperto

Intuizione Principale: Questo articolo non riguarda il craccare le password più velocemente; riguarda il craccarle in modo più silenzioso. Gli autori hanno identificato una vistosa lacuna operativa nella sicurezza offensiva: l'impronta digitale. Quando un red teamer interroga un servizio di cracking basato su cloud, i metadati di quella query sono un rischio. Questo lavoro propone di cifrare l'intento stesso utilizzando il PIR, rendendo il server "oblivious". È un classico esempio di applicazione di una teoria crittografica avanzata (PIR) a un problema reale e concreto dell'infosec. La rilevanza è simile alle considerazioni sulla privacy negli attacchi di inversione del modello o negli attacchi di inferenza di appartenenza contro le API di machine learning, dove la query stessa può rivelare informazioni sensibili.

Flusso Logico: L'argomentazione è logicamente solida. 1) Definire il modello di minaccia: un server di terze parti non fidato. 2) Selezionare il primitivo crittografico appropriato: PIR computazionale a singolo database, che è l'unica opzione praticabile per questo scenario a server singolo senza collusione. 3) Adattare il primitivo di cracking: Scegliere le tabelle di Hellman rispetto a quelle Rainbow perché la loro struttura richiede meno query PIR, più deterministiche, per tentativo di cracking. Questa è una decisione ingegneristica cruciale che mostra una profonda conoscenza del dominio. Il flusso dal problema allo strumento crittografico all'integrazione di sistema è coerente.

Punti di Forza & Debolezze: Il punto di forza principale è la novità e l'applicabilità diretta. Il prototipo prova la fattibilità del concetto. Tuttavia, le debolezze sono pratiche. Il sovraccarico prestazionale del PIR è enorme. Come notano gli autori, il lavoro del server è $O(n)$. Per tabelle di grandi dimensioni (terabyte), ciò è proibitivo per un servizio commerciale. È una soluzione che privilegia la privacy perfetta rispetto a qualsiasi parvenza di efficienza. Inoltre, protegge solo la query. Il server sa ancora che il client sta eseguendo un'operazione di cracking, il che potrebbe essere sufficiente per far scattare allarmi in alcune giurisdizioni. Rispetto agli approcci basati su crittografia completamente omomorfa (FHE) che stanno emergendo, questo metodo basato su PIR è più semplice ma molto meno flessibile.

Spunti Azionabili: Per i professionisti della sicurezza, questo è un progetto per strumenti offensivi ad alta garanzia che preservano la privacy. Per i ricercatori, apre una linea di lavoro su PIR efficiente e utilizzabile. Il passo successivo immediato è confrontare questo approccio con uno basato su TEE (ad es., eseguendo la logica di cracking all'interno di un enclave SGX). Il TEE gestirebbe il calcolo privatamente con un potenziale sovraccarico inferiore rispetto al PIR crittografico, sebbene introduca la fiducia nel produttore dell'hardware. La visione a lungo termine dovrebbe essere un modello ibrido: utilizzare il PIR per la ricerca iniziale dell'indice più sensibile, e forse hardware fidato per i passi successivi, bilanciando le assunzioni di fiducia e le prestazioni. Questo lavoro, come il fondamentale articolo su CycleGAN che combinava creativamente reti per la traduzione di immagini non accoppiate, mostra come combinare due tecnologie mature (tabelle di Hellman e PIR) possa creare una soluzione innovativa per un problema di nicchia ma importante.

9. Dettagli Tecnici & Formulazione Matematica

Il nucleo di una catena di Hellman per una funzione hash $H$ e una funzione di riduzione $R$ è definito in modo iterativo. Dato un testo in chiaro iniziale $P_0$: $$X_0 = P_0$$ $$X_{k+1} = H(R(X_k)) \quad \text{per } k = 0, 1, ..., t-1$$ L'endpoint della catena è $X_t$. La tabella memorizza le coppie $(P_0, X_t)$. Per invertire un hash $h$, si calcola una catena di prova da $h$: $Y_0 = h$, $Y_1 = H(R(Y_0))$, ..., $Y_t = H(R(Y_{t-1}))$. Ad ogni passo $j$, si controlla se $R(Y_j)$ è un punto distinto o se $Y_j$ corrisponde a un endpoint memorizzato $X_t$, innescando una rigenerazione della catena per trovare la preimmagine. Nella versione adattata al PIR, il controllo contro la lista degli endpoint memorizzati sul server viene eseguito tramite una query PIR sull'indice corrispondente a $R(Y_j)$ o $Y_j$.

10. Quadro di Analisi & Caso di Studio

Caso di Studio: Penetration Testing as a Service (PTaaS) Sicuro
Immagina una piattaforma PTaaS basata su cloud che offre audit delle password. Un'azienda cliente carica un elenco di hash di password dal proprio sistema per un audit di sicurezza. Utilizzando un servizio standard, il provider cloud apprende a quali hash specifici corrispondono le password dell'azienda, una potenziale violazione. Utilizzando il framework del server oblivious:

1. Lo strumento di audit del client pre-elabora ogni hash target $h$.
2. Per ogni $h$, calcola localmente gli indici necessari $i_1, i_2, ... i_k$ nelle tabelle di Hellman del provider.
3. Utilizza un protocollo PIR per generare query cifrate per questi indici e le invia al server PTaaS.
4. Il server elabora tutte le query (svolgendo lavoro sul suo intero database) e restituisce blocchi di dati cifrati.
5. Il client decifra le risposte e le elabora localmente per vedere se sono state trovate corrispondenze di catena, recuperando le password in chiaro.

Durante tutto questo processo, il provider PTaaS vede solo query cifrate, dall'aspetto casuale, e non apprende nulla su quali hash il client stava testando, preservando così la riservatezza dell'insieme di password interno del client.

11. Applicazioni Future & Direzioni

I principi di questa ricerca si estendono oltre il cracking delle password:

• Ricerca di Threat Intelligence che Preserva la Privacy: Interrogare indicatori di compromissione (IOC) da un database condiviso senza rivelare i propri asset.
• Corrispondenza di Sequenze di DNA Confidenziale: Un ospedale potrebbe interrogare un database genomico per marcatori di malattia senza esporre il genoma completo del paziente.
• Filtraggio Privato nell'Analisi dei Log: Cercare pattern di attacco nei log di sicurezza condivisi senza rivelare i pattern specifici a cui la propria organizzazione è vulnerabile.
• La convergenza con la Crittografia Completamente Omomorfa (FHE) è una direzione chiave. Mentre il PIR nasconde il pattern di accesso, la FHE potrebbe consentire al server di eseguire l'intero calcolo di cracking su dati cifrati, restituendo solo un risultato cifrato. Progetti come Microsoft SEAL e OpenFHE stanno rendendo questo più pratico.
• L'integrazione con la privacy differenziale potrebbe aggiungere un ulteriore livello di privacy statistica, assicurando che nemmeno il successo o il fallimento di una query riveli troppe informazioni.

12. Riferimenti

1. Calvo, A., Futoransky, A., & Sarraute, C. (2013). An Oblivious Password Cracking Server. arXiv preprint arXiv:1307.8186.
2. Hellman, M. (1980). A cryptanalytic time-memory trade-off. IEEE Transactions on Information Theory, 26(4), 401-406.
3. Rivest, R. L. (1982). How to reuse a "write-once" memory. (MIT Laboratory for Computer Science Technical Report).
4. Oechslin, P. (2003). Making a faster cryptanalytic time-memory trade-off. Advances in Cryptology - CRYPTO 2003 (pp. 617-630). Springer.
5. Chor, B., Goldreich, O., Kushilevitz, E., & Sudan, M. (1995). Private information retrieval. Proceedings of IEEE 36th Annual Symposium on Foundations of Computer Science (pp. 41-50). IEEE.
6. Zhu, J. Y., Park, T., Isola, P., & Efros, A. A. (2017). Unpaired image-to-image translation using cycle-consistent adversarial networks. Proceedings of the IEEE international conference on computer vision (pp. 2223-2232). (Citato come esempio analogo di combinazione creativa di tecnologie).
7. Microsoft Research. (n.d.). Microsoft SEAL (Simple Encrypted Arithmetic Library). Recuperato da https://www.microsoft.com/en-us/research/project/microsoft-seal/