Garantire una previsione su un evento futuro

12

Voglio fare una previsione su un evento futuro, ma solo rivelare che la previsione dopo l'evento si verifica per timore che la conoscenza della mia previsione influenzi l'esito.

Ad esempio, supponiamo che Alice preannunci che Bob si verserà il bicchiere di latte il 24 aprile alle 9:17. Scrive in un file di testo:

Bob spills his glass of milk on April 24th at 9:17 AM.

Alice non vuole che Bob conosca le specifiche della previsione prima dell'evento, altrimenti Bob potrebbe evitare il latte quel giorno per impedire l'esito della predizione di Alice. Tuttavia, se Alice rivela solo la previsione dopo che si è verificato l'evento, Bob può affermare che Alice ha fabbricato la previsione dopo che l'evento si è già verificato.

Naturalmente, Alice dovrebbe fornire una verifica dell'autenticità della sua predizione a Bob prima dell'evento - una verifica che non rivela le specifiche della previsione fino a dopo l'evento, ma che conferma che la previsione è stata fatta prima dell'evento .

Ho individuato due possibili metodi di verifica:

  1. Codifica
    • Alice applica un algoritmo di crittografia a chiave simmetrica (come AES) sul file di testo
    • Alice fornisce a Bob il file crittografato
    • Dopo l'evento, Alice fornisce a Bob la password segreta
    • Bob decrittografa il file crittografato e legge la previsione
  2. di hashing
    • Alice applica un algoritmo di hashing (come SHA-256) sul file di testo
    • Alice fornisce a Bob l'hash calcolato
    • Dopo l'evento, Alice fornisce a Bob il file di testo originale
    • Bob applica lo stesso algoritmo di hashing sul file di testo e verifica l'hash

Quale metodo di verifica è il più sicuro (cioè che teoricamente sarebbe più difficile per Bob superare e quindi scoprire la previsione prima che si verifichi l'evento)?

Quale metodo di verifica è più pratico (ad esempio gli hash occupano uno spazio significativamente più piccolo di un file crittografato)?

    
posta Vilhelm Gray 30.01.2014 - 17:46
fonte

1 risposta

12

Encryption non offre la funzionalità che cerchi; non direttamente almeno. Come caso estremo, considera One-Time Pad : la chiave è lunga quanto i dati da crittografare e la crittografia è fatto con un XOR bit-by-bit: dato il tasto K e il testo semplice P , il testo cifrato è C = P XOR K . Supponi di aver usato OTP per la tua crittografia; hai previsto P e pubblicato la versione criptata C . Più tardi, la previsione si rivelò sbagliata; Bob non versa latte ma vino (alle 9:17, che vergogna!). Ora vuoi apparire come se lo avessi previsto correttamente tutto il tempo; quindi, vuoi che il testo cifrato C decifri come P ', non P (nota che P' ha il stessa lunghezza di P ). È facile: calcola il tasto K '= C XOR P' e pubblica K ' come chiave che hai usato. Puoi verificare che C sia effettivamente il risultato della crittografia di P ' di K' .

Quindi, con OTP, puoi falsificare a posteriori il messaggio iniziale. Questa è la caratteristica che rende OTP un sistema di crittografia teoricamente infrangibile: ogni testo in chiaro possibile è possibile (con la stessa probabilità) per un determinato testo cifrato.

Pertanto, se si utilizza un altro sistema di crittografia (ad esempio, alcuni AES), allora potrebbe fornire il tipo di impegno che si sta cercando solo essendo imperfetto come un sistema di crittografia. Questo non sembra un buon fondamento per la sicurezza: deve essere buono, ma non troppo bello.

Hashing è un candidato molto migliore. Hash la previsione P in H = SHA-256 ( P ), quindi pubblica il valore hash. Più tardi, rivela P : tutti possono annullare l' P rivelato e vedere che corrisponde al valore hash precedentemente pubblicato H . Questo è sicuro fintanto che la funzione hash è resistente alla collisione, cioè finché non è possibile creare due predizione P e P ' quale hash allo stesso valore (perché altrimenti potresti scegliere di rivelare quello che è successo)

Come nota a margine, la pubblicazione può assumere diverse forme. Considera timestamp attendibile : questo è un metodo pubblico per gli impegni. La Time Stamping Authority (TSA) riceve un valore hash, lo incapsula in una struttura che contiene anche la data e l'ora correnti (come noto dalla TSA) e firma la struttura. In effetti, la TSA, con la sua firma, dice (in modo verificabile): "che il valore hash H è stato pubblicato alla data T o prima, perché l'ho visto a data T ". In un mondo non computerizzato, tale lavoro viene svolto con una busta di Soleau .

Il valore hash ha uno svantaggio: potenzialmente consente a qualcuno di provare a forzare la previsione. Dato il valore hash H , si potrebbero provare le possibili previsioni P e cancellarle tutte fino a trovare una corrispondenza, ricostruendo quindi la previsione prima della sua rivelazione. Ad esempio, si potrebbe sapere che si prevede lo sversamento di alcune bevande in una certa data e provare tutte le combinazioni di bevande e date. Poiché l'hashing può procedere ad una velocità di miliardi di messaggi al secondo (con una buona GPU), alcune previsioni strutturate potrebbero essere a rischio di rivelazione anticipata. Per prevenire questo attacco, aggiungi padding casuale alla fine:

Bob spills his glass of milk on April 24th at 9:17 AM, and
here is random padding:sef9yb94bo3qr7yqwnc67sb32

Assicurati di usare nuovi personaggi casuali ogni volta che fai una previsione (non riutilizzarli!). Si noti che si può costruire un esempio forzato di una funzione di hash che è "sicura" nel senso che non consente il calcolo delle collisioni, ma non riesce ancora a nascondere il valore di predizione; tuttavia, questo sarebbe un esempio forzato. Con SHA-256, il padding casuale farà il lavoro, purché ne aggiungiate abbastanza (un carattere casuale aggiungerà 5 o 6 bit di entropia, a 80 bit i nemici saranno completamente sconfitti, quindi 16 caratteri sono sufficienti). Uno svantaggio del metodo è che devi mantenere la stringa di input completa, cioè la previsione imbottita , con i caratteri casuali; questo può essere fastidioso se hai intenzione di tenerlo in testa.

    
risposta data 30.01.2014 - 19:10
fonte

Leggi altre domande sui tag