Gli umani sono un RNG strong o debole? [duplicare]

23

Thomas Pornin ha ha dichiarato in passato in più occasioni (non ho intenzione di trovarli, può discutere con me se lo desidera) che gli umani sono RNG cattivi.

Mentre sono d'accordo sul fatto che il RNG umano per la generazione di password nella mente sia abissale di solito, volevo chiedere se l'RNG assistito da un computer è ugualmente cattivo. KeePass ha una funzione in cui si semina l'RNG spostando il mouse per un po ', e mentre so che se KeePass sta usando / dev / urandom è abbastanza o meno abbastanza sicuro, in passato ho usato il RNG con il mouse.

Ho sempre pensato che l'RNG aiutato dall'input umano sarebbe stato migliore del semplice PRNG come previsto da un sistema operativo. Come potrebbe qualcuno prevedere esattamente come avrei spostato il mio mouse, a che velocità, quanto spesso sto facendo una pausa, ecc.?

    
posta Naftuli Kay 15.01.2015 - 20:05
fonte

7 risposte

44

I cervelli umani sono poveri RNG. Le persone sono cattive nel generare valori casuali nella privacy delle loro teste. Non riescono a pensare casualmente; anche se possono convincersi che lo fanno.

I processi fisici, d'altra parte, sono piuttosto buone fonti di entropia. Prendi i tuoi movimenti del mouse. Alcune decine di volte al secondo, il mouse misura quanto è stato spostato dall'ultimo tick e invia tali informazioni al server. Quando la mano scuote, tende a farlo in modo un po 'regolare, ma la biologia è tale che ogni movimento elementare sarà soggetto a qualche jitter, che risulta essere sostanzialmente più grande della precisione del mouse; anche con molto allenamento, è molto difficile per una mano umana fare esattamente la stessa mossa ripetutamente (altrimenti ci sarebbero molte più persone come Yehudi Menuhin ). Quindi la linea di fondo è che le misure di movimento del mouse contengono alcune entropia. (Ricordate che "entropia" è qui definita come "ciò che l'attaccante non sa", il mouse certamente sa quanto è stato spostato, dal momento che è quel mouse che effettivamente invia i valori su cui è costruito l'RNG.)

L'altra metà della risposta è aggregazione . Un RNG basato sul mouse utilizzerà centinaia o anche migliaia di misure, le accumulerà tutte e le condenserà in un seme appropriato che concentrerà tutta quell'entropia. Questo è abbastanza semplice: basta inserire tutti i valori in una funzione hash crittografica, ad es. SHA-256, e otterrai un seme a 256 bit che ha tutta l'entropia di origine, ovunque si nascondesse nei movimenti misurati del mouse. Le funzioni di hash sono buone per questo; riducono la dimensione ma mantengono l'entropia (fino alla dimensione dell'output della funzione hash, ma 256 bit è più che sufficiente per tutti gli scopi).

Un utente malintenzionato può indovinare che l'utente farà cerchi, ma avrà difficoltà a riprendere tutti i movimenti individuali, soprattutto perché la psicologia non lo aiuterà: l'utente umano stesso non ha idea di come i suoi movimenti della mano siano trasformati in numeri. Dato che stiamo parlando di centinaia di numeri, il numero di combinazioni possibili (ad esempio "entropia") aumenta esponenzialmente. Confrontalo con un utente umano che pensa a una nuova password: l'utente sceglierà le lettere seguendo una linea di pensiero interiore "spiritoso", che l'attaccante può indovinare più o meno brutalmente (ad esempio se le lettere sono tutte le prime lettere di alcune parole in una frase da un libro, l'attaccante può automaticamente provare tutte le frasi da tutti i libri che riesce a trovare in formato elettronico); e, cosa più importante, l'utente umano non si preoccuperà di produrre più di una dozzina di personaggi "apparentemente casuali".

Nelle password, la lunghezza non fa la forza, ma la mancanza di lunghezza può essere abbastanza efficace nel prevenire la forza.

    
risposta data 15.01.2015 - 22:06
fonte
4

Gli umani sono molto poveri generatori di casualità, specialmente su richiesta.

La maggior parte degli utenti farà una di queste cose poiché il comportamento umano è abbastanza prevedibile. Usando il mouse come esempio, è probabile che gli utenti lo spostino lateralmente o in alto e in basso fino a quando viene generata una "casualità" sufficiente in base al programma. Forse lo spostano in un cerchio. Quello che è improbabile da fare è muovere il mouse in modo veramente casuale. Se qualcuno ha cura di poter analizzare una serie di utenti, estrapolare comportamenti probabili ed estrarre informazioni utili da tali studi per scoprire schemi che potrebbero essere utilizzati per attaccare tale sistema.

È davvero difficile ottenere dati veramente casuali.

Da Secure Programming Cookbook per C e C ++: sfortunatamente, la maggior parte dei movimenti del mouse segue traiettorie semplici con pochissima entropia. La maggior parte dell'entropia si verifica quando il puntatore raggiunge la vicinanza generale della sua destinazione e inizia a rallentare per bloccarsi su un bersaglio. C'è spesso anche un bel po 'di entropia all'avvio. Il movimento intermedio di solito è abbastanza prevedibile. Tuttavia, se gli attacchi locali non sono nel tuo modello di minaccia e l'attaccante può solo indovinare su quali parti del tuo schermo sono stati posizionati il mouse in un determinato periodo di tempo in base all'osservazione del comportamento del programma, c'è potenzialmente un bel po 'di entropia in ogni mouse evento, perché l'attaccante non sarà in grado di indovinare il pixel in cui si trova il cursore in un dato momento.

    
risposta data 15.01.2015 - 21:00
fonte
2

Con il seguente piccolo script python, prova a produrre una sequenza di 42 zero o uno spostando il mouse in uno schema "ripetibile".

import Tkinter

root = Tkinter.Tk()

lx,ly = (0, 0)
while True:
        x,y = root.winfo_pointerxy()
        if ((x-lx)**2+(y-ly)**2) > 42:
                print (x ^ y ^ lx ^ ly) & 1
                lx,ly = (x,y)

Se hai Python 3.x, puoi usare anche quanto segue:

import tkinter
tkinter.NoDefaultRoot()
root = tkinter.Tk()
x = y = 0
while True:
    x2, y2 = root.winfo_pointerxy()
    if (x - x2) ** 2 + (y - y2) ** 2 > 42:
        print((x ^ y ^ x2 ^ y2) & 1)
        x, y = x2, y2
    
risposta data 16.01.2015 - 02:22
fonte
1

La qualità di un RNG è una questione di correlazioni con gli input o qualche altro insieme di parametri non segreti. Ovviamente se l'output di un RNG è correlato a qualcosa che sai, che riduce drasticamente l'entropia consentendo di tagliare ampie fasce del possibile spazio di output - forse un dato RNG ora può realisticamente prevedere di produrre solo uno su 1.000 numeri come contrapposto alle 1.000.000 pubblicizzate, il che rende la forza bruta molto più pratica.

L'RNG costruito da chiedendo a un umano di pensare a parole o frasi casuali è in effetti scarso. Il motivo sono molti forti correlazioni:

  • Correlazione con la cultura, che consente di utilizzare un dizionario inglese per obiettivi nordamericani o di concentrarsi su 1900-2000 per PIN (anche perché le password in altre lingue rappresentano una strategia decente di sicurezza attraverso l'oscurità)
  • Correlazione con gli altri, che consente di creare dizionari delle prime X password più comuni
  • Correlazione con il comportamento storico di sé, che consente di sfruttare password passate o i miei social media per indizi come la data di nascita o la città natale

Si noti che molti PRNG "sicuri" sono anche basati su un input molto prevedibile, vale a dire il tempo di sistema.

La chiave è riconoscere che l'umano non è necessariamente l'unico elemento del RNG. Funziona solo come un seme. Non vi è alcun motivo per cui è consentito solo l'output del seme così com'è, quindi è possibile applicare varie funzioni ad esso per diluire la correlazione (un esempio di base ma debole è quello di aggiungere un numero molto grande, moltiplicare per un numero molto grande e quindi prendi il modulo).

I movimenti del mouse sono usati solo come seme per RNG di Keepass. Se la funzione che usano è ragionevolmente in grado di restituire un input non correlato, non c'è motivo di sospettare che non sia sicuro. (concesso, non saprei dirti perché esattamente non saltano il mouse e usano l'ora del sistema come loro seme, o quale funzione usano esattamente e quanto è sicura)

    
risposta data 16.01.2015 - 01:45
fonte
0

Penso che gli umani stiano bene, ma dipende da come chiedi loro di generare il numero. Inoltre sono tenuti a essere in grado di replicarlo? Per numeri più piccoli gli umani sono facilmente influenzati e altamente prevedibili. C'è anche il problema che gli umani spesso iniziano con schemi simili prima di iniziare a generare qualcosa che somiglia alla casualità. Prendi il seguente esempio

952167493 ... all'inizio, ho iniziato con un numero familiare, forse un numero di telefono che è nella mente delle persone o il numero civico, quindi gli umani potrebbero cercare di essere casuali e la probabilità di due numeri seguendo un ordine di conteggio regolare sarà basso, dopo di che potrebbero saltare cercando di riempire lo spettro del numero.

dati abbastanza campioni, penso che molti umani seguirebbero schemi simili, e otterresti grandi numeri che non sono affatto casuali. Potresti anche trovare interi segmenti di numeri che non appaiono, semplicemente perché non si sentono casuali per un umano mentre li stanno creando, come 123123123123123 o 44455523534333666

Non mi fiderei di un umano per creare un numero casuale a meno che non avessero alcune istruzioni che avrebbero diminuito la probabilità di errori di numero / modello umani, anche allora è una cattiva idea

    
risposta data 15.01.2015 - 21:24
fonte
0

Ci sono già alcune ottime risposte qui, quindi voglio solo fornire alcune prove aneddotiche. Sembra già chiaro che negli RNG basati sul movimento gli umani possono fornire una strong fonte di entropia dovuta alla riproduzione inesatta dei movimenti.

Nel caso in cui si chiedesse agli umani di selezionare un numero casuale, tuttavia, iniziano a essere mostrate forti tendenze. Ricordo una lezione di matematica all'ottavo anno in cui abbiamo generato 100 numeri "casuali" chiedendo alle persone che ci siamo imbattuti e i risultati hanno mostrato quanto possano essere prevedibili gli umani. Non riesco a ricordare i risultati esatti, ma il numero 7 per esempio è venuto tre volte più spesso rispetto alla successiva risposta più popolare, nessuna persona ha dato una risposta che fosse più di due cifre e tutte le risposte fossero numeri interi. Sono sicuro che se questo fosse stato eseguito su una scala più ampia, sarebbe stata prodotta una tendenza simile.

    
risposta data 16.01.2015 - 10:42
fonte
0

È mia opinione che gli umani siano molto poveri nel generare casualità su richiesta. Ci sono modi per "estrarre" la casualità dalle interazioni umane. Il movimento del mouse è un buon esempio. La casualità non viene dalle intenzioni dell'utente (la maggior parte delle persone disegnerà linee o cerchi) ma dall'errore nel movimento. Gli umani non possono semplicemente disegnare figure esattamente ripetibili usando un mouse.

Mentre cercavo le risposte, ho trovato due documenti "interessanti":

  • Gli umani possono generare coscientemente sequenze numeriche casuali: un test possibile per l'intelligenza artificiale. [ 1 ]
  • Gli umani non possono generare coscientemente sequenze di numeri casuali: studio polemico [ 2 ]

Purtroppo, entrambi sono disponibili solo commercialmente, e se non sei uno studente o ricercatore in qualche università dovresti pagare. (non farlo per questi documenti!) Penso che i titoli siano abbastanza divertenti.

Ho trovato anche documenti più seri e interessanti, puoi leggere:

  • Giochi per estrarre casualità [ 3 ]
  • Valutare casualità e complessità nelle traiettorie del movimento umano attraverso l'analisi di sequenze simboliche [ 4 ] ( non completamente sull'argomento, ma molto interessante)
  • Questa risposta sullo scambio di stack delle scienze cognitive elenca alcuni

Tutto questo suggerisce (tranne il primo articolo, ma non lo considero molto serio) che gli umani sono cattivi quando viene chiesto di generare casualità casualmente, ma se lo fai bene puoi estrarre la buona casualità dai movimenti umani!

    
risposta data 16.01.2015 - 11:26
fonte

Leggi altre domande sui tag