È possibile crackare g ++ rand ()?

5

Quindi, ho questo:

So che un codice è stato usato per generare una sequenza casuale, e sembrava più o meno come questo:

#include <iostream>
#include <string>

int main() {
    const std::string alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    std::string temp = "1234567890";
    srand(MAGICNUMBER);
    for (int i = 0;; ++i) {
        for (int j = 0; j < 10; ++j) {
            temp[j] = alphabet[rand() % alphabet.size()];
        }
        std::cout << temp << std::endl;
    }
}

È stato usato per generare una sequenza di 124660967 stringhe, l'ultima delle quali era "2lwd9JjVnE", e poi si è fermata. Il compilatore utilizzato era g ++ 4.8 a 64 bit per Linux. Quello che voglio è trovare la stringa 124660968th, cioè quella che sarebbe stata stampata in seguito. L'avvertenza, ovviamente, è che non conosco il MAGICNUMBER . Sono abbastanza sicuro che sia possibile forzare tutte le possibilità, ma ci vorranno millenni, a quanto pare. Ho provato a curiosare in rand() del codice sorgente, ma non lo capisco davvero, tanto meno lo sfrutto. È possibile trovare quella stringa in un tempo più o meno ragionevole?

UPD È persino possibile generare ciò che dovrebbe andare dopo che la mia stringa senza ha trovato il seme?

    
posta Akiiino 30.03.2016 - 16:03
fonte

2 risposte

6

Il compilatore stesso è irrilevante; la funzione rand() è implementata in libc .

L'implementazione di glibc utilizza un generatore di congruenza lineare (LCG) o un registro di spostamento di feedback lineare (LFSR) per il suo rand() . Questi possono essere facilmente decifrati a causa di alcune uscite (che sembra che tu abbia). I dettagli possono essere trovati nella risposta a un'altra domanda già posta qui , ma il punto cruciale è che LCG e LFSR non sono sicuri e alcuni semplici calcoli matematici e probabilità possono ottenere la risposta giusta abbastanza rapidamente.

Avrai bisogno di capire quale versione di glibc è stata usata, ma la versione del compilatore dovrebbe darti un'idea approssimativa dello stato della patch del sistema, quindi puoi dedurlo da quello.

Puoi trovare più risorse su Google, ma ecco una breve serie di link per aiutare:

risposta data 30.03.2016 - 16:26
fonte
1

Google dice:

In order to generate random-like numbers, srand is usually initialized to some distinctive runtime value, like the value returned by function time (declared in header <ctime\>). This is distinctive enough for most trivial randomization needs.

Se si utilizza questa tecnica e si conosce una stima più o meno prossima del tempo (come se fosse possibile ridurla a un giorno), un attacco di forza bruta sullo spazio di input sinistro sarà probabilmente fattibile.

Oltre a questo, se segui ancora google trovi una serie di post di blog questo potrebbe portarti sulla giusta strada.

    
risposta data 30.03.2016 - 16:20
fonte

Leggi altre domande sui tag