Diffie Hellman - quanto dovrebbe essere grande il numero casuale?

Risposta breve. Sì, penso che sia corretto scegliere x come un numero casuale a 160 bit. (Non ci scommetterei la vita, ma sono abbastanza sicuro che vada bene.)

Dettagli tecnici. Ci sono (almeno) due modi per attaccare Diffie-Hellman.

1. Un modo è utilizzare algoritmi elaborati per calcolare il logaritmo discreto, ad esempio, in base al setaccio di campi numerici o simili. Il tempo di esecuzione di questi algoritmi dipende dal modulo primario p, e hai bisogno che p sia grande (certamente almeno 1024 bit) per resistere a questi attacchi.

2. Un altro modo è usare algoritmi più elementari, come l'algoritmo passo passo di baby-step o l'algoritmo di Pollard. Il tempo di esecuzione di questi algoritmi dipende dalla dimensione minore di q o dalla dimensione dell'esponente x. Hai bisogno che q sia grande (almeno 160 bit) per resistere a questi attacchi. È necessario che l'esponente sia scelto da un grande spazio (ad esempio, almeno 160 bit di entropia) per resistere a questi attacchi.

Dato che ci sono due diversi attacchi, dovrai scegliere i tuoi parametri per sconfiggerli entrambi. Ecco perché hai bisogno che il tuo esponente abbia almeno 160 bit.

Ora, la cosa più prudente da fare è scegliere x in modo casuale a caso nell'intervallo [0, q-1] (o [2, q-2] se preferisci, non ha molta importanza). Questo sarà sicuramente sicuro, purché p e q siano abbastanza grandi. La citazione che hai estratto sembra dire che X9.42 ti consiglia di utilizzare questo approccio conservativo.

Tuttavia in molti casi è possibile ottenere un'ottimizzazione, a volte nota come ottimizzazione dell'esponente breve. L'idea è di scegliere x uniformemente a caso da un intervallo più piccolo, ad esempio [0, 2 ¹⁶⁰ - 1]. Questo di solito è sicuro, se il protocollo è progettato correttamente, anche se ci sono state alcune eccezioni. Il vantaggio è che se q è grande, scegliere una x più corta come questa può migliorare significativamente le prestazioni.

Per il gruppo che hai citato, q = (p-1) / 2. (*) In altre parole, q è lungo circa 1023 bit. Ciò significa che la cosa più conservativa da fare è scegliere la tua x nell'intervallo completo [0, q-1], ma credo che tu possa probabilmente cavartela usando l'ottimizzazione dell'esponente breve. Ho provato a leggere i documenti IKE e non ho trovato immediatamente una dichiarazione esplicita sull'ottimizzazione dell'ottimizzazione a breve esponente per IKE, anche se ho trovato alcune osservazioni che sembrano indicare che gli sviluppatori hanno anticipato potrebbe essere OK da usare.

Nota a piè di pagina (*): puoi dedurlo come segue. RFC 2409 dice che "le proprietà di questi gruppi sono descritte in [RFC2412]". La sezione E.2 di RFC 2412 elenca il gruppo corrispondente ed elenca il più grande fattore primo dell'ordine di gruppo. Il primo fattore più grande può essere verificato (p-1) / 2. Da ciò segue che q = (p-1) / 2.

Modifica 3/24: Ho appena notato, grazie alla risposta di @ CodeinChaos, che hai menzionato la ragione per cui utilizzi un breve esponente non è la performance ma piuttosto l'entropia limitata nel tuo PRNG. Lo trovo un po 'strano. Quale PRNG stai usando? Sei sicuro di avere un PRNG cripto-resistente? La maggior parte dei PRNG crittografici può essere usata per tirare una stringa pseudocasuale di lunghezza arbitraria. Se il tuo non lo fa, puoi sempre prendere l'output del tuo PRNG ed espanderlo a una stringa pseudocasuale a 1024 bit: ad esempio, generare una chiave AES a 128 bit K, quindi utilizzare AES (K, 0), AES (K , 1), AES (K, 2), AES (K, 3), ..., AES (K, 7) per generare una stringa pseudocasuale a 1024 bit. Una volta che hai una stringa pseudocasuale a 1024 bit (purché sia di cripto-qualità e l'RNG originale abbia abbastanza entropia in esso), puoi usarlo come esponente a 1024 bit a lunghezza intera.

Verifica che il tuo RNG / PRNG sia criptato. Ad esempio, /dev/urandom e CryptGenRandom sono buoni, ma rand() , random() , drand48() sono tutti negativi. ( /dev/random è strong ma non necessario; usa invece /dev/urandom e sarai in grado di disegnare un esponente a lunghezza intera senza problemi.) Cerca su questo sito per ulteriori informazioni sui PRNG di qualità crittografica.

Needless to say I have a noise-generation capacity problem and I'm hurting already, so I need the least amount of noise that still keeps the system secure (at a roughly 112 bit equivalent bits of security which is approximately the level of security provided by the DH with a 1024 bit prime).

Cercherò di usare un buon CRPto PRNG che tu semini (e occasionalmente ri-semina) con la tua effettiva entropia. In questo modo puoi facilmente creare grandi quantità di numeri casuali. Credo che fortuna sia una scelta popolare per un PRNG.

Una volta che la generazione di numeri casuali è a buon mercato, non vi è alcun motivo per utilizzare numeri minori della gamma massima. Ma dal momento che non ho molta familiarità con DH, non so quale sia questo intervallo.

160 bit sono sufficienti per 1024 bit DH, ma questo sarà più debole del tuo AES a 256 bit. Vedere ad esempio la Tabella 2 in NIST SP 800-57 o questa calcolatrice della lunghezza della chiave . (Per l'equivalenza con le chiavi simmetriche a 256 bit raccomandano il DH da 15360 bit (con un numero casuale a 512 bit) o, più praticamente, usando una curva ellittica da 512 bit.)

Quindi, se il tuo sistema legacy smette di utilizzare uno scambio di chiavi più strong, l'uso di una chiave a 256 bit potrebbe essere una perdita di tempo.