Recentemente ho visto Poker shuffles che sono stati hackerati e fatti supporre essere ragionevoli, e questo a causa della debolezza degli shuffles. È possibile creare un shuffle che sia cripticamente sicuro, anche se il codice per il client e il server è disponibile?
Sì. In effetti, la maggior parte di questi broken meccanismi di shuffling sono in realtà rotti perché utilizzano algoritmi di shuffling "segreti".
In generale, un meccanismo di shuffling ha due componenti:
Sebbene l'algoritmo di shuffling possa avere un certo pregiudizio, l'intero meccanismo di shuffling non può avere meno pregiudizi rispetto al PRNG stesso. In altre parole, un algoritmo di shuffling non può essere più casuale del suo PRNG. Diamo un'occhiata a uno degli algoritmi di shuffling più efficienti là fuori, il Fisher-Yates shuffle .
Il codice sorgente (o, piuttosto, lo pseudocode ) della moderna mescolanza Fisher-Yates è stato pubblicamente disponibile dal 1964, con implementazioni in decine di lingue.
To shuffle an array a of n elements (indices 0..n-1):
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
Tuttavia, rimane ancora uno degli algoritmi più utilizzati per questo scopo.
Se guardi da vicino, l'algoritmo dipende da random integer . È qui che entra in gioco il PRNG. Se il tuo PRNG è imparziale e la tua implementazione è corretta, anche il tuo shuffles dovrebbe essere imparziale.
Sono disponibili molti buoni PRNG che sono ben controllati, testati nel tempo e provati per essere imparziali. Dal momento che un PRNG è deterministico (per lo stesso stato iniziale, restituisce sempre lo stesso valore) la sicurezza / casualità dell'intero meccanismo di mischia si basa sulla casualità dello stato iniziale del PRNG, il suo wikipedia.org/wiki/Random_seed">seed. Questo affidamento sulla qualità del seme è un'estensione del Principio di Kerckhoffs , poiché senza conoscere la conoscenza seme del l'algoritmo non ti dice nulla. Fortunatamente, i PRNG più buoni utilizzano buone "fonti di casualità" fornite dal sistema operativo, come /dev/urandom .
Per completare la risposta di @ Adnan: c'è il codice e ci sono dati. "Shuffling" sta applicando una permutazione su un dato spazio, che è molto simile alla crittografia. Quindi la tua domanda può essere riformulata come: è possibile crittografare i dati in modo sicuro, quando l'hacker conosce il codice? E la risposta è: sì, a patto che l'attaccante non conosca il tasto . La chiave concentra il segreto. Abbiamo separato la chiave dal codice precisamente in modo che il codice non debba essere segreto, e lo facciamo perché è molto difficile mantenere il codice segreto.
L'algoritmo Fisher-Yates (anche noto, in modo improprio, come "Knuth shuffle") può essere visto come un algoritmo di crittografia, la cui chiave è la sequenza di valori casuali ottenuti dalla fonte casuale. Il codice è ben noto, ma si presume che l'autore dell'attacco non conosca questi valori. Finché gli interi casuali restituiti sono ottenuti da una sorgente crittograficamente strong e imparziale, questo è "perfetto" (ogni permutazione tra le 52! permutazioni possibili di uno spazio di dimensione 52 può essere selezionata con probabilità uniforme ). La generazione di interi non distorti in un determinato intervallo, da una sorgente che produce byte, è soggetta ad alcune sottigliezze che possono essere superate (vedere cosa ho scritto a pagina 3 di questo articolo ).
Il caso generale (che permuta in modo sicuro uno spazio di alcune dimensioni arbitrarie, non necessariamente una potenza di 2) è coperto da Formato Preserving crittografia . Quando vuoi il codebook completo, cioè vuoi la permutazione completa (è il caso di un shuffle, dove devi sapere dove è andata ogni carta), lo shuffle di Fisher-Yates è buono come te può ottenere. Altre soluzioni per FPE consentono la valutazione parziale (cioè senza avere una matrice contenente il full shuffle) ma possono indurre bias (in particolare, gli schemi di Feistel sono sempre permutazioni uniformi). Non ha molto senso cercare di fare nient'altro che Fisher-Yates per le carte.
Un generatore di numeri pseudo casuali crittograficamente sicuro, con opportune fonti di entropia, dovrebbe soddisfare le vostre esigenze in modo abbastanza piacevole. Un CSPRNG deve comportarsi nello stesso modo, poiché essere in grado di prevedere valori futuri o determinare valori precedenti potrebbe rendere vulnerabili molti sistemi di crittografia. Essere in grado di prevedere numeri casuali era il cuore del famigerato bug di Netscape.
Ecco un elenco: link
Leggi altre domande sui tag random cryptography