XOR di molti cicli di prime dimensioni: sicuro?

@Mark è sulla strada giusta, ma non del tutto a posto. È possibile considerare gli elementi dell'array e l'output RNG come un sistema di equazioni lineari, ma non sono linearmente indipendenti. Infatti, non è mai possibile ripristinare completamente gli elementi dell'array, poiché l'assegnazione dello stesso valore in tutti i valori in due degli array darà lo stesso output RNG - il valore xored è incluso due volte in ciascun elemento dell'output RNG, quindi annulla stesso.

In realtà questo rende il lavoro dell'aggressore più facile, perché non è necessario dedurre l'intero array per prevedere tutti i risultati futuri, quindi non hanno bisogno di tante equazioni (/ output). È possibile prevedere tutti gli output da just (somma dei primi) - (numero di primi) + 1 output consecutivi.

Ecco un esempio, utilizzando matrici di lunghezze 2, 3 e 5. Chiama gli array A (lunghezza 2), B (lunghezza 3) e C (lunghezza 5) e l'uscita R. Quindi abbiamo:

R0 = A0 ⊕ B0 ⊕ C0
R1 = A1 ⊕ B1 ⊕ C1
R2 = A0 ⊕ B2 ⊕ C2
R3 = A1 ⊕ B0 ⊕ C3
R4 = A0 ⊕ B1 ⊕ C4
R5 = A1 ⊕ B2 ⊕ C0
R6 = A0 ⊕ B0 ⊕ C1
R7 = A1 ⊕ B1 ⊕ C2
R8 = A0 ⊕ B2 ⊕ C3
R9 = A1 ⊕ B0 ⊕ C4

Si consideri:

R0 ⊕ R3 ⊕ R5 = (A0 ⊕ B0 ⊕ C0) ⊕ (A1 ⊕ B0 ⊕ C3) ⊕ (A1 ⊕ B2 ⊕ C0)
 = A0 ⊕ B2 ⊕ C3
 = R8

Quindi xoring delle uscite zeroth, third e fifth predice l'ottavo. E xorizzare il primo, il quarto e il sesto darebbe il nono, ecc.

Risultato netto: completamente inutile come RNG crittografico.

Posso mettere un limite superiore alla forza: un attaccante che può osservare un numero di uscite consecutive uguale alla somma delle lunghezze dei singoli array può dedurre i valori degli array e tutti gli output successivi.

Considera il caso semplice di tre array, con le lunghezze 2, 3 e 5: i primi dieci valori (le variabili a ), ei valori nascosti che li generano (le variabili x ), sono mostrati sotto . Ogni colonna è i tre valori nascosti che sono xored per produrre l'output visibile.

x1 x2 x1 x2 x1 x2 x1 x2 x1 x2
x3 x4 x5 x3 x4 x5 x3 x4 x5 x3
x6 x7 x8 x9 x0 x6 x7 x8 x9 x0
-----------------------------
a0 a1 a2 a3 a4 a5 a6 a7 a8 a9

Se lo giri di lato, sembra molto simile a un sistema di dieci equazioni su dieci incognite, il genere di cose che la gente impara a risolvere nell'algebra introduttiva. Sebbene la lunghezza del ciclo sia 30, sono necessari solo 10 valori consecutivi per caratterizzare completamente il generatore e prevedere il valore successivo.

Man mano che aumenta il numero di array, aumenta anche la disparità tra la durata del ciclo e la facilità di interruzione: dieci array di lunghezza 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 indicano una durata del ciclo di 6.469.693.230, ma richiede solo 129 valori da interrompere.

Potrebbe essere possibile per un utente malintenzionato che conosce già il contenuto degli array di rompere la sicurezza con un numero inferiore di valori, ma non sono sicuro di come sarebbe fatto.

NON ARRIVA MAI IL TUO CRYPTO . Ok ora che è fuori mano.

Ciao,

Hai già risposto alla tua domanda quando lo hai chiesto, questo è un PRNG. PRNG non è lo stesso di CSPRNG (generatore di numeri pseudo-casuali crittograficamente sicuro) che indica un generatore di numeri pseudo-casuali per il quale si ritiene impossibile prevederne l'output senza conoscere i semi. Anche se la tua soluzione è valida come PRNG di default nelle librerie integrate, non importa. Pseudo-casuale implica un certo livello di prevedibilità che consentirebbe agli aggressori di predire i futuri valori di sale e nonce (tra le altre cose, come i cookie di sessione) e consentire loro di eludere molti dei meccanismi di difesa come i token anti-CSRF, gli ID di sessione nei cookie, e la password salata nel tuo DB.

Pertanto, nulla che sia mai stato definito come pseudo-casuale è sicuro. Inoltre, posso quasi garantire che qualsiasi soluzione CSPRNG che tu, io o quasi chiunque abbia in mente abbia un certo livello di prevedibilità e un matematico riderebbe di noi.

Quindi no, non sarebbe effettivamente sicuro. Idea interessante però e in base al tuo commento non avevi intenzione di usarlo nelle applicazioni del mondo reale in ogni modo quindi finirò il mio rant breve.

EDIT: seguendo il commento di AndrolGenhald sulla mia scarsa terminologia di "cripto-casuale" ho aggiornato la lingua per fare affidamento sul termine accurato, CSPRNG. Scuse.