Come posso decodificare un messaggio che è stato crittografato con un pad singolo?

One-Time Pad è indistruttibile, assumendo che il pad sia perfettamente casuale, tenuto segreto, usato una sola volta e non sia noto alcun testo in chiaro. Ciò è dovuto alle proprietà dell'operazione esclusiva o (xor).

Ecco la sua tabella di verità:

A xor B = X

A | B | X
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0

Number of 0s in column A = 2
Number of 1s in column A = 2
Number of 0s in column B = 2
Number of 1s in column B = 2
Number of 0s in column X = 2
Number of 1s in column X = 2

Si noti che non introduce alcun bit-skew - il numero di 0 e 1 negli input è uguale al numero di 0 e 1 nell'output, cioè due di ciascuno. Inoltre, se conosci solo un elemento di una riga, non puoi prevedere i valori degli altri due, poiché sono ugualmente probabili.

Per esempio, diciamo che sappiamo che X è 0. C'è una probabilità uguale che A = 0 e B = 0, o A = 1 e B = 1. Ora diciamo che sappiamo che X è 1. C'è un uguale probabilità che A = 0 e B = 1, o A = 1 e B = 0. È impossibile prevedere. Quindi, se conosci solo un elemento, non puoi determinare alcuna informazione su A o B.

La prossima proprietà interessante è che è reversibile, cioè

A xor A = 0
B xor B = 0

A xor 0 = A
B xor 0 = B

A xor B xor B  =  A xor 0  =  A
A xor B xor A  =  B xor 0  =  B

Quindi, se prendiamo qualsiasi valore e lo facciamo con se stesso, il risultato viene cancellato e sempre risulta in 0. Ciò significa che, se abbiamo un valore A con un valore B, poi più tardi xo quel risultato con A o B, otteniamo rispettivamente B o A. L'operazione è reversibile.

Questo presta bene alla crittografia, perché:

• xor non introduce alcun bit
• xor ha input altrettanto probabili per ogni dato output
• dati qualsiasi due di A, B, X possiamo calcolare il terzo

Come tale, il seguente è perfettamente sicuro:

ciphertext = message xor key

ma solo se il messaggio ha la stessa lunghezza della chiave, la chiave è perfettamente casuale, la chiave viene utilizzata solo una volta e solo un elemento è noto a un utente malintenzionato. Se conoscono il testo cifrato, ma non la chiave o il messaggio, è inutile per loro. Non possono forse romperlo. Per decodificare il messaggio, deve conoscere l'intera chiave e il testo cifrato.

Ricorda che la chiave deve essere completamente casuale, cioè ogni bit deve avere uguale probabilità di essere 1 o 0 ed essere completamente indipendente da tutti gli altri bit nella chiave.

Questo in realtà risulta piuttosto poco pratico, per alcuni motivi:

• Generare chiavi perfettamente casuali è difficile. I generatori di software (e molti generatori di hardware) hanno spesso imperfezioni minuscole e proprietà di ripetizione strane. È quasi impossibile ottenere dati veramente casuali in qualsiasi cosa tranne piccole quantità.
• Se l'utente malintenzionato conosce il testo cifrato e può indovinare correttamente parti del messaggio (ad esempio sa che è un eseguibile di Windows, e quindi deve iniziare con MZ ), può ottenere i bit chiave corrispondenti per l'intervallo noto. Questi bit sono inutili per decifrare altre parti del messaggio, ma possono rivelare modelli nella chiave se sono generati male.
• Devi essere in grado di distribuire la chiave e la tua chiave deve essere uguale al tuo messaggio. Se riesci a mantenere la tua chiave al 100% segreta tra quelli che sono autorizzati a leggere il messaggio, perché non mantenere il tuo messaggio al 100% segreto?

Il link debole qui è il tuo generatore di numeri casuali. La sicurezza di one time pad è completamente limitata dalla sicurezza del tuo generatore. Dal momento che un generatore perfetto è quasi impossibile, un pad perfetto per una volta è quasi impossibile.

Il problema finale è che la chiave può essere utilizzata solo una volta. Se lo usi per due diversi messaggi e l'autore dell'attacco conosce entrambi i testi cifrati, può crearli insieme per ottenere lo xor dei due testi in chiaro. Questo perde ogni tipo di informazione (ad esempio, quali bit sono uguali) e interrompe completamente il codice.

Quindi, in conclusione, in un pad istantaneo perfetto hai bisogno di conoscere il testo cifrato e la chiave per decrittografarlo, ma i pad monouso perfetti sono quasi impossibili.

I pad monouso sono estremamente difficili da rompere, infatti sono ancora utilizzati in alcune situazioni come se fossero eseguiti correttamente, quindi sono essenzialmente indistruttibili. In un sistema one-time pad ogni carattere viene modificato da un flusso di dati casuali condiviso da entrambe le parti, senza una copia del pad non sarà possibile rompere il codice.

Uno dei pochi punti deboli del sistema è l'origine dei dati casuali. Durante la seconda guerra mondiale, le pastiglie inglesi venivano rotte e la tracciavano a un lavoratore il cui compito era estrarre le palline numerate casualmente da un tamburo. Il modo in cui avrebbe dovuto funzionare era che il lavoratore girasse il tamburo, tirasse fuori una palla a caso senza guardarlo, girasse di nuovo, riprendeva, ecc. Ecc. Il lavoratore iniziò a prendere scorciatoie tirando fuori più di una palla dopo ogni giro e guardando i numeri, scegliendo i preferiti. Ha introdotto schemi che hanno permesso all'opposizione di rompere i pad, e di conseguenza le vite sono andate perse.

Lo stesso è vero oggi con fonti di numeri pseudo-casuali. I protocolli di crittografia che dovrebbero richiedere millenni di interruzione dureranno davvero solo per anni o decenni senza una vera fonte di dati casuali.

Supponendo che la crittografia sia stata eseguita in modo competente, l'unico modo per decodificare è quello di ottenere il pad.

Sebbene la crittografia one-time-pad sia probabilmente impossibile da interrompere, si noti che è anche straordinariamente raro.

Parte della definizione di OTP è che il pad deve contenere dati veramente casuali e per i computer è davvero difficile trovare dati veramente casuali. Invece, spesso il pad è composto da dati pseudo-casuali , che è generalmente quello che ottieni quando chiedi a un computer un numero casuale.

In questo caso, non hai più la crittografia infrangibile. Invece, hai un messaggio XORed con l'output di un algoritmo deterministico e spesso reversibile, che può essere attaccato riproducendo la stessa stringa pseudo-casuale. Questo attacco è particolarmente devastante se si conosce l'algoritmo utilizzato e ancor di più se si conosce come viene generato il seme. In tal caso, il codice può essere rotto in pochi secondi. Ma anche senza conoscere il seme PRNG, spesso il modello può essere derivato dal messaggio stesso.

Inoltre, la crittografia OTP è particolarmente ingombrante perché la chiave è lunga quanto il messaggio crittografato e deve in qualche modo essere trasmessa al destinatario senza essere intercettata. Qualsiasi software che affermi di utilizzare la crittografia OTP che non richiede di scambiare un blocco chiave grande quanto il tuo messaggio (o più grande) non sta utilizzando dati veramente casuali e pertanto non utilizza la crittografia OTP.

Inoltre, una delle caratteristiche chiave di OTP è che non è possibile riutilizzare i vecchi pad. Se riutilizzi uno vecchio anche solo una volta, ciò può essere sufficiente per consentire l'interruzione del codice.

La domanda era: come decifrare un messaggio che è stato creato da un time pad, piuttosto sicuro di non aver ancora ricevuto risposta.

Originariamente il time pad era usato solo con caratteri, ed è molto semplice. Diciamo che hai un messaggio "killtheking" (preso da una risposta) e vuoi crittografarlo in modo da avere bisogno di una chiave. Per la chiave è necessario almeno lo stesso numero di caratteri del messaggio, quindi tira un dado che ha 26 lati (uno per ogni lettera) 11 volte, perché nel messaggio ci sono 11 caratteri.

Supponiamo che il risultato sia aqheivlekrw

ora sottraiamo la posizione nell'alfabeto della lettera nella loro chiave, dalla posizione nell'alfabeto della lettera nel messaggio, e il numero risultante è la posizione nell'alfabeto del testo cifrato. Avvolgi tutte le lettere che creano un risultato negativo come di seguito (come se il risultato fosse 30, quindi utilizza 26-30 = 4 o "d".

es .:

k - a = (11 - 1) = 10 = j 

'j' è la decima lettera dell'alfabeto, quindi la usiamo.

per il resto del messaggio otteniamo:

i - g = (9 - 7) = 2 =   b
l - h = (12 - 8) = 4 =  d
l - e = (12 - 5) = 7 =  g
t - i = (16 - 9) = 7 =  g
h - v = (8 - 22) = -14 (26 - 14 = 12) = l
e - l = (5 - 12) = - 7 (26 - 7 = 19) = s
k - e = (11 - 5) = 6 = f
i - k = (9 - 11) = -2 (26 - 2 = 24) = x
n - r = (14 - 18) = -4 (26 - 4 = 22) = v
g - w = (7 - 23) = -16 (26 - 16 = 10) = j

quindi alla fine

your message    = killtheking
you key         = agheivlekrw
your cypher     = jbdgglsfxvj

passa il testo cifrato a chi vuoi riceverlo e fanno l'opposto di quello che hai fatto per crittografarlo, devono aggiungere la chiave al testo cifrato:

j + a = (10 + 1 = 11) k
b + g = (2 + 7 = 9)   i
d + h = (4 + 8 = 12)  l
g + e = (7 + 5 = 12)  l
...

e così via.

I computer usano XOR perché fa la stessa cosa ed è molto più veloce e facile da implementare, ma per capire come funziona, ho scoperto che è bello vedere l'esempio usabile "umano". Quindi su un computer puoi crittografare il messaggio facendo:

Cypher = Chiave XOR del messaggio

e decrittalo di nuovo usando:

Messaggio = Chiave XOR Cypher

È così semplice.

Se non hai la chiave ...

Forza brutale il testo cifrato (permutalo) e analizza l'output per un potenziale testo chiaro nel linguaggio previsto.

L'analisi statistica può aiutare a rilevare il potenziale linguaggio generato dall'uomo nell'output (forse chi quadrato)?

un time pad potrebbe facilmente rompersi se si conosce il formato di output. Come intestazioni audio, immagini GIF, ecc. Con il reverse engineering del flusso indietro. Potrebbe essere buono per alcuni tipi di caratteri, ma non per altri campi in cui il formato di output potrebbe essere facilmente identificato con altri mezzi. Al giorno d'oggi niente è sicuro al 100%.