Il poker (online) richiede casualità crittograficamente sicura?

19

Ecco una citazione da una discussione reddit :

… for poker [a cryptographically secure RNG] is completely unnecessary. If you have an appropriate unpredictable seed, and you are throwing away a lot of the randomness, MT is perfectly safe.

Normalmente lo scriverei come ignoranza, ma questo continua:

I've actually implemented a real-money poker backend, and the company even had it certified

E dal momento che nessuno si trova su Internet , questo mi fa meravigliarsi. Detta persona espande questo in un'altra parte della discussione :

[To prevent predictability] you would not use 624 consecutive values produced from [the MT generator]. If you want a real-money app. certified, one of the criteria is to throw away a large and unpredictable amount of the output of the PRNG.

You also don't know the specifics of how the PRNG was used to produce a shuffle. So, you have no way to map the cards you see on the table to a sequence from the PRNG.

You also don't know when the PRNG is reseeded.

One last thing. You need to store (219937 − 1) * 4 bytes of data for lookup, in order to find the pattern you need to predict.

Ad eccezione dell'ultimo paragrafo, questi argomenti sembrano sospetti come la sicurezza per oscurità. L'ultimo paragrafo sembra meno, ma qualcun altro nella discussione ha affermato che l'affermazione non è vera e che non è necessaria una tabella di ricerca così grande.

Giusto per chiarire, sono consapevole che MT19937 non è crittograficamente sicuro (e così è la persona che sto citando). Tuttavia, la mia ipotesi fino a quel momento era che il gioco d'azzardo (e il poker) richiedesse una fonte casuale protetta da crittografia - e non solo un seme sicuro - (a) per essere a prova di manomissione e (b) per la certificazione. È sbagliato?

    
posta Konrad Rudolph 11.02.2014 - 10:09
fonte

3 risposte

23

Ecco il punto di vista del crittografo. La persona che hai citato dice : "non hai bisogno di un PRNG crittograficamente sicuro", ma quello che in realtà afferma è "quando uso MT 19937 e faccio qualche mumbo-jumbo come buttare via gran parte dell'output, in qualche modo diventa un PRNG crittograficamente sicuro ".

Il suo commento sull'archiviazione di "(2 19337 -1) * 4 byte per la ricerca" è sufficiente per dimostrare che non è molto chiaro nella sua testa su quali siano la sicurezza, la crittografia, la casualità e l'imprevedibilità siamo. Questa cifra è il "periodo"; il periodo era usato in (molto) vecchi tempi come misura di sicurezza, perché il PRNG conosciuto da quel tempo aveva periodi molto piccoli, al punto che la ripetizione si verificava nella pratica. Questo ha generato un'intera famiglia di PRNG non criptati, in cui i progettisti cercavano di sopraffare i loro concorrenti fiorendo il periodo più lungo possibile. Questo non ha alcun senso dal punto di vista crittografico. La sicurezza di un PRNG riguarda l'imprevedibilità e un periodo molto breve è un problema solo perché consente di prevedere l'output futuro. AES usato in modalità CTR è un PRNG con un periodo di 2 135 (bit), una cifra molto inferiore a 2 19337 -1, e tuttavia non è affatto un problema.

Il "lancio di quantità di imprevedibili quantità di output" illustra anche la confusione. Rimuovere i bit dall'output può nascondere una perdita di stato da un PRNG debole; questo può anche trasformare un PRNG debole in uno strong, come studiato con il generatore di restringimento . Tuttavia, non fa nulla sulla prevedibilità dei semi; in effetti, se parte dell'output viene "gettato via", allora c'è un meccanismo che decide cosa tenere e cosa buttare via, e quel meccanismo è anche parte del PRNG. Se tutto questo è seed con l'ora corrente, allora la ricerca esauriente sui possibili valori di "ora corrente" sarà efficiente (il tempo corrente non è un segreto) e sarà il tutto.

Tuttavia potremmo obiettare che sebbene MT non sia crittograficamente sicuro, ciò non significa che fare un attacco efficace sia facile . Esistono tre tipi di PRNG:

  • Gli algoritmi terribilmente deboli, sia attraverso l'elaborazione molto scarsa (perdita dello stato interno), o seme prevedibile, o entrambi. Questi sono interrotti nella pratica.
  • Il PRNG "crittograficamente strong", che resiste agli attacchi anche nelle condizioni ridicole che gli accademici assumono (un accademico considererà un algoritmo "rotto" se rivendica la sicurezza a 128 bit ma offre solo 2 123.4 resistenza).
  • La zona grigia in mezzo: rotta come da accademici, ma un attacco pratico non è immediato.

Con il suo Mersenne Twister , si trova nella zona grigia e crede che le sue manipolazioni voodoo lo manterranno modo. È del tutto plausibile che possa anche convincere un auditor che il voodoo funziona. Questo in nessun modo implica che l'algoritmo sia sicuro ; solo che un auditor era pronto a firmare un documento in cui si affermava che l'algoritmo soddisfa alcuni requisiti legali. A quel punto, è bene ricordare che alcuni altri revisori hanno ritenuto opportuno firmare documenti sostenendo che Enron è stata un'impresa finanziariamente sana e pulita: questo aiuta a mettere le cose nella giusta prospettiva.

Da ciò che descrive, è probabile che il seme iniziale sia basato sul tempo e la sicurezza attuale si basi interamente sulla non pubblicazione dei dettagli dell'algoritmo. Questa è sicurezza attraverso l'oscurità al suo meglio (o peggio, a seconda del punto di vista).

    
risposta data 11.02.2014 - 21:25
fonte
6

Prima di tutto, c'è una cosa molto importante: cosa intendi quando diciamo "richiesto"? Il gioco stesso (poker online) non richiede realmente quel livello di casualità. Probabilmente puoi farcela con il vecchio rand() .

Tuttavia, i giochi di poker online legali e regolamentati devono seguire alcune regole, una delle quali è che il RNG dovrebbe essere verificato da una società di revisione indipendente. Questo è il caso nel Regno Unito. Aziende di revisione ( PwC , EY , Cigital , Gaming Laboratories International ) e organismi di regolamentazione ( Kahnawake Gaming Commission ) in molti luoghi del mondo hanno avuto e di solito gestisci casi del genere.

Tali società di revisione e organismi di regolamentazione richiedono che il RNG sia di una casualità molto elevata, imparziale e imprevedibile. Ora, quali RNG sappiamo che sono facili da implementare e utilizzare e sono adatti a tali regolamenti? Bene, indovinate; il tuo buon vecchio fidato CSPRNG .

Come @Ladadadada menziona, oltre alla regolamentazione e alle leggi, è nell'interesse dell'operatore del gioco rendere il gioco il più equo possibile perché l'ingiustizia e la "crackabilità" allontanano gli utenti. Pertanto, al fine di raggiungere tale livello di equità, hai bisogno di casualità di alta qualità e di imprevedibilità fornite da un CSPRNG.

Con una rapida sessione di Google troverai numerosi CSPRNG altamente testati, controllati e ben controllati che possono essere presi così com'è e utilizzati nel tuo progetto di poker online.

    
risposta data 11.02.2014 - 11:08
fonte
6

Il tizio ha torto quando afferma che un CSRNG era "completamente inutile". Lo conferma anche quando dice che hai bisogno di un "seme imprevedibile".

Che cosa significa un seme imprevedibile?

Quando ti do una quantità ragionevole di numeri pseudo-casuali derivati da quel seme, non sarai in grado di calcolare il numero successivo. Semplice. Da un punto di vista matematico, la sicurezza di tali generatori può essere dimostrata da un semplice gioco.

Ti mando una sequenza di numeri e devi decidere se sono completamente casuali o derivati da una funzione (F). Se il tuo tasso di successo medio è migliore della metà (+/- un importo ammissibile) vinci.

Scoprirai che le tue possibilità di vincere dipendono (almeno) dalla quantità di input che la funzione ottiene. Se ho usato solo pochi bit di input, puoi sicuramente distinguere tra il rendering completo e l'output di funzione molto meglio di mezzo.

Fino a questo punto non c'è modo di aggirare un buon seme. Che dire della magic throw-away?

L'eliminazione di qualche output lo rende più sicuro?

Trovo che la dichiarazione di "buttare via una quantità grande e imprevedibile" in qualche modo divertente. Quello che fanno qui è saltare le parti dell'output della funzione. Ma quanti byte esattamente? Dichiara "una quantità ampia e imprevedibile". Ciò significa che si modifica la funzione dall'alto.

Tuttavia, sei ancora al punto in cui hai iniziato. Si gioca e si tenta di distinguere tra casualità completa e output di una nuova funzione (F '). Dopo tutto, c'è un algoritmo in esecuzione e deve decidere esattamente quanti byte saltare. Quindi questo valore è in qualche modo calcolato e può essere visto come una parte aggiuntiva della funzione originale.

Che cosa puoi fare?

Come puoi vedere buttare via una quantità imprevedibile di output non rende la funzione più sicura. Al contrario, se scegli di eliminare una quantità completamente casuale di byte, questo colud porta a un algoritmo più sicuro.

Se un algoritmo emette i bit 0101010101 ... e così via, le tue possibilità di vincere la partita sono abbastanza buone. Se ignoro una quantità casuale di output e ti mando un bit, salta un'altra quantità e ti mando un bit, e così via, quale sarebbe? Le tue possibilità di vincere erano le tue possibilità di prevedere la quantità di bit saltati. Alla fine dovresti pronosticare la casualità e le tue possibilità di vincita non sarebbero più così buone.

Tuttavia, la sicurezza del mio generatore di numeri ha il vantaggio di saltare solo in determinate condizioni, la cui valutazione andrebbe oltre questa discussione. Solo per avere la giusta impressione: cosa porterebbe il salto se la mia funzione emette il bit "1" nel 99% delle volte e "0" solo nell'1%? Troverai che anche se salti una quantità casuale di bit, la distribuzione statistica è ancora costante.

Conclusione

Sicuramente vorresti la casualità in un gioco di poker, per il seme o il salto di uscita o entrambi. Ma è sufficiente usare questa casualità costosa come input per funzioni ben definite che funzionano come CSPRNG.

Solo per la cronaca: è possibile creare una funzione che resista a tutti i test citati utilizzando primitive crittografiche in modo che la sequenza sia prevedibile se si conosce una chiave segreta. Senza la conoscenza della chiave segreta sembra così casuale, che le tue possibilità di vincere la partita sono all'incirca la metà.

    
risposta data 11.02.2014 - 21:16
fonte

Leggi altre domande sui tag