Offline RSA strong primo test simile al Phuctor?

2

Uno dei modi in cui le chiavi RSA vengono costantemente acquisite è quando vengono generate senza sufficiente entropia. Dan Kaminsky fa riferimento a uno studio che ha rilevato che 1 su 200 chiavi RSA sono state generate male e queste erano quelle che sono stati trovati , per non parlare dei milioni di altri che non sono stati trovati.

Quindi, è necessario un RNG buono e correttamente seminato durante la generazione di chiavi rapide RSA per GPG, SSL, SSH, ecc. ovunque si verifichi la generazione di chiavi RSA.

Phuctor è uno strumento online che cerca le coppie di chiavi RSA PGP e li tiene in considerazione. Sorprendentemente, hanno persino preso in considerazione una chiave RSA 4096bit nel set strong che è stato generato male con il primo fattore essendo il numero 231 (3 * 77). (Secondo Polynomial, hanno preso in considerazione solo una sottochiave corrotta, che non dovrebbe avere alcun impatto sul mondo reale.)

Quando sto generando keypair RSA pubblici / privati per SSL, SSH, GPG, ecc., c'è uno strumento offline che posso usare per determinare quanto sono difficili e quanto grandi sono i numeri primi? Posso stimare la difficoltà computazionale nel fattorizzare questo data la coppia di chiavi RSA, così posso determinare se sono state generate correttamente?

Ovviamente, utilizzo un computer desktop sicuro per la generazione di coppie di chiavi (e facoltativamente /dev/random ), poiché l'RNG di Linux è seminato da "attività mouse e tastiera, operazioni di I / O su disco e interrupt specifici" ( origine, PDF ) che le macchine virtuali spesso non hanno. Mentre questo dovrebbe essere sufficiente, mi piace capire i metodi sottostanti e vorrei testare le mie coppie di chiavi per garantire la sicurezza.

    
posta Naftuli Kay 20.05.2015 - 21:46
fonte

3 risposte

3

In generale, non esiste una chiara distinzione tra chiavi RSA "difficili da fattori" e "non difficili da fattori". Questo è un continuum. Ad esempio, l'algoritmo ECM (che utilizza le curve ellittiche in modo intelligente per calcolare i numeri interi) tende ad avere un costo computazionale che dipende dalla dimensione del fattore più piccolo del numero intero di destinazione. Se ci provi di più, puoi trovare più fattori. La conseguenza è che anche se trascorri un'intera giornata di calcoli per "provare" con ECM il tuo modulo per piccoli fattori, e non trovare nessuno, allora non sai se un attaccante con più pazienza potrebbe non trovare un fattore dedicando due giorni di calcolo.

Non esiste un metodo noto in grado di testare un dato numero intero e restituire la dimensione dei suoi fattori, senza ricalcolare effettivamente i fattori, che è (si spera!) computazionalmente non fattibile per una corretta chiave RSA.

Testare le chiavi RSA dopo la generazione è una ricerca folle. Questa è una buona cosa da fare per rilevare alcune cattive implementazioni, non chiavi scadenti. Inoltre, rileva solo alcune classi di chiavi povere (in particolare, quelle con piccoli fattori). Non rileva il RNG con un numero di serie errato utilizzato in una generazione di chiavi private RSA altrimenti corretta. Ciò evidenzia un punto importante: mentre avere fattori molto piccoli è un sicuro segno di generazione di chiavi errate, avere solo grandi fattori non garantisce una generazione sicura.

Per sicurezza, assicurati che le chiavi siano generate correttamente controllando il processo di generazione delle chiavi, non il risultato.

    
risposta data 20.05.2015 - 22:09
fonte
2

Che dire di le altre chiavi che abbiamo trovato ? Alcuni di questi hanno autoprogrammi validi. Come in, un utente ingenuo che interroga SKS per un indirizzo email senza riguardo all'impronta digitale sarà mostrato uno di questi come il risultato di ricerca superiore. E, per quel che ne sappiamo, mostreranno un'impronta digitale valida su qualche sistema PGP-compatibile guasto.

Se, come vorrebbe far credere il signor Böck, avremmo scoperto che i "raggi cosmici" o "corruzione del disco" sono in grado di generare autoprogrammi chiave PGP validi - per questo dovremmo raccogliere l'oro a Stoccolma trovare, piuttosto che accontentarsi di questo piccolo cambiamento.

    
risposta data 20.05.2015 - 22:25
fonte
0

Offline RSA strong prime test similar to Phuctor?

Sì. link . Ho provato con successo contro le chiavi a 128 bit. Non ho ancora avuto il tempo di provarlo con le chiavi a 1024 bit, ma funziona come pubblicizzato - i valori deboli durante la generazione producono chiavi più deboli.

    
risposta data 05.08.2016 - 05:24
fonte

Leggi altre domande sui tag