One-time pad migliorato

One-time pad migliorato

Messaggioda rrronny il sab 4 feb 2012, 21:39

Introduzione all'invenzione. Il mio amico Fabio Buono (nevergreen@live.it) vuole proporre la seguente idea su come ottimizzare il cifrario one-time pad (d'ora in poi, OTP). Esso ha come notevole inconveniente il fatto che necessita di uno scambio iniziale, attraverso un canale sicuro, di un numero di chiavi grande quanto il numero di messaggi che si desidera inviare. Questo difetto, a suo dire, si potrebbe eliminare usando il seguente:

Protocollo nel capocollo. Assumiamo verificate delle ipotesi un po' più deboli di quelle relative al cifrario OTP: chiave lunga quanto il messaggio e perfettamente casuale; invio su canale sicuro di una chiave iniziale fra i comunicanti (i soliti Alice e Bob). Prima della comunicazione vera e propria, Alice consegna in modo sicuro a Bob una chiave k_0. A questo punto Bob comprime in un file m_1 il messaggio m'_1 da inviare ad Alice e una chiave k_1. Poi Bob cifra mediante OTP il file m_1 usando la chiave k_0 e lo invia ad Alice, la quale lo decifra ottenendo il messaggio a lei destinato m'_1 e una nuova chiave k_1. Alice, se vorrà proseguire la comunicazione, cifrerà con la chiave k_1 un nuovo messaggio m'_2 compresso assieme a una chiave k_2 scelta da lei e spedirà il crittogramma così ottenuto a Bob. E così via.

Affinché il protocollo sia utilizzabile, è necessario fissare a priori la lunghezza massima dei files m'_i.

Cosa ne pensate?
"Realtà virtuale", "social network", "realtà aumentata"? Io parlerei di "solitudine aumentata", quella che percepisci anche stando in mezzo agli altri, e che occorre della tecnologia per appianarla.
Avatar utente
rrronny
 
Messaggi: 737
Iscritto il: mer 17 giu 2009, 20:51
Località: Pisa

Eccomi

Messaggioda nevergreen il dom 5 feb 2012, 16:08

Salve a tutti sono Fabio, ho pensato che l'idea che rronny ha postato per me potrebbe essere integrata così; Al posto di mandare un solo messaggio cifrato, con la nuova chiave e il messaggio messi insieme, posso spedire prima il messaggio e poi la chiave in due messaggi distinti. Il che non dovrebbe creare problemi alla sicurezza del cifrario in quanto visto che entrambe le chiavi sono per assunto perfettamente casuali non si verrebbero a creare schemi di ripetizione utili a fare crittoanalisi statistica. Quest'ultima affermazione è un pò critica e non sono sicuro sia giusta... voi che ne pensate? FB
Avatar utente
nevergreen
 
Messaggi: 5
Iscritto il: dom 5 feb 2012, 2:53

Messaggioda rrronny il dom 5 feb 2012, 23:30

Aggiungo una considerazione quantitativa, di cui lascio al lettore la facile dimostrazione. Siano r_i \in (0,1) il rapporto di compressione per m_i, 0<n \in \mathbb{N} la dimensione fissa di ogni chiave utilizzata e \mu&#39;_ila dimensione del messaggio m&#39;_i. Allora deve valere la seguente disuguaglianza: \mu&#39;_i \le \frac{1-r_i}{r_i} n. Non è difficile accorgersi, al crescere di i, che r_i \to 1 e di conseguenza \mu&#39;_i \to 0. Cosa piuttosto spiacevole, direi...

Osservazione del lampione. Se m&#39; è un'immagine (quindi praticamente incomprimibile), allora si avrebbe solo la compressione r della chiave (contenuta in un banale file testo), per cui si otterebbe la limitazione \mu&#39; \le (1-r) n.

Esempio empio. Supponiamo di voler inviare un semplice file testuale di 150 \mbox{ kB}, e sia r = 2/5. Allora saranno necessarie delle password lunghe (almeno) 100 \mbox{ kB} \approx 10^5 \mbox{ b}.
Ultima modifica di rrronny il lun 6 feb 2012, 23:54, modificato 1 volta in totale.
"Realtà virtuale", "social network", "realtà aumentata"? Io parlerei di "solitudine aumentata", quella che percepisci anche stando in mezzo agli altri, e che occorre della tecnologia per appianarla.
Avatar utente
rrronny
 
Messaggi: 737
Iscritto il: mer 17 giu 2009, 20:51
Località: Pisa

Osservazione

Messaggioda nevergreen il lun 6 feb 2012, 13:14

rronny ti volevo far notare che la chiave essendo completamente casuale è incomprimibile per definizione! Inoltre per quale motivo le immagini non sarebbero comprimibili?
Avatar utente
nevergreen
 
Messaggi: 5
Iscritto il: dom 5 feb 2012, 2:53

Messaggioda rrronny il lun 6 feb 2012, 13:56

rrronny ha scritto:Osservazione del lampione. Se m&#39; è un'immagine (quindi praticamente incomprimibile), allora si avrebbe solo la compressione r della chiave (contenuta in un banale file testo), per cui si otterebbe la limitazione \mu&#39; \le (1-r) n.
nevergreen ha scritto:rrronny ti volevo far notare che la chiave essendo completamente casuale è incomprimibile per definizione!

Vabbe', allora sarà r=1.

nevergreen ha scritto:Inoltre per quale motivo le immagini non sarebbero comprimibili?

Ho preso un'immagine a caso, ho provato a comprimerla in formato zip e la dimensione è rimasta immutata.
"Realtà virtuale", "social network", "realtà aumentata"? Io parlerei di "solitudine aumentata", quella che percepisci anche stando in mezzo agli altri, e che occorre della tecnologia per appianarla.
Avatar utente
rrronny
 
Messaggi: 737
Iscritto il: mer 17 giu 2009, 20:51
Località: Pisa

Osseervazioni

Messaggioda nevergreen il lun 6 feb 2012, 21:14

Ho trovato un bug nella seconda versione del protocollo, quella che manda due messaggi diversi cifrati con la stessa chiave. Notiamo che se, ad esempio, il crittoanalista avesse a disposizione la seconda chiave cifrata con la prima potrebbe usarla sul messaggio cifrato con la prima ottenendo così il messaggio cifrato con la prima chiave! E cosi via potrebbe trattare ogni messaggio come se fosse cifrato con la stessa chiave, e quindi potrebbe fare analisi statistiche e forzare il cifrario.

Esempio:
Indichiamo con A//B il messaggio A cifrato con la chiave B, e siano m1=1111, m2=1110, due messaggi in chiaro e siano k0=0010, k1=1010 due chiavi.

Avremmo:
Inizialmente avremmo che m1//k0 = 1101 transita sul canale tra Alice e Bob, poi avremmo m2//k1 = 0100 e k1//k0 =  1000
entrambi che vanno da Bob e Alice e tutti questi sarebbero crittogrammi che il crittoanalista potrebbe prendere perchè spediti su un canale insicuro. Il problema ora sta nel fatto che se il crittoanalista mettesse in OXR m2//k1 con k1//k0, avrebbe come risultato m2//k0 e quindi potrebbe infrangere la sicurezza del cifrario, infatti iterando il procedimento ogni messaggio apparirebbe cifrato con k0!! L'unico modo per risolvere quest problema è applicare una qualche permutazione alla chiave prima di spedirla, evidentemente si dovrà provvedere a spedire anche la permutazione, oppure si dovrà usare la prima versione del protocollo, quella in cui il messaggio e la chiave vengono zippati insieme (con tutte le limitazioni del caso)!
Avatar utente
nevergreen
 
Messaggi: 5
Iscritto il: dom 5 feb 2012, 2:53

Messaggioda rrronny il mar 7 feb 2012, 13:25

nevergreen ha scritto:[...] Il problema ora sta nel fatto che se il crittoanalista mettesse in OXR m2//k1 con k1//k0, avrebbe come risultato m2//k0 e quindi potrebbe infrangere la sicurezza del cifrario, infatti iterando il procedimento ogni messaggio apparirebbe cifrato con k0!! [...]

Siano U,V,W \in \{0,1\} e indichiamo con \oplus l'operazione di disgiunzione esclusiva. Hai usato la catena di identità che segue, a quanto mi risulta:

    (U \oplus V) \oplus (W \oplus V) = (U \oplus W) \oplus (V \oplus V) =  (U \oplus W) \oplus 0 = U \oplus W.
Concordo. Probabilmente questo inconveniente può essere evitato usando un altro algoritmo cifrante.

Per quanto concerne il protocollo di cui al capothread, ho editato il mio primo commento. Nello specifico, oltre a quelli già palesati, esso presenta il pernicioso difetto di funzionare a patto di scambiare messaggi via via più corti.
"Realtà virtuale", "social network", "realtà aumentata"? Io parlerei di "solitudine aumentata", quella che percepisci anche stando in mezzo agli altri, e che occorre della tecnologia per appianarla.
Avatar utente
rrronny
 
Messaggi: 737
Iscritto il: mer 17 giu 2009, 20:51
Località: Pisa

Messaggioda nevergreen il mer 8 feb 2012, 4:35

Hai ragione caro rronny, e quando nel post "Osservazioni" scrivevo "con tutte le limitazioni del caso" mi riferivo proprio al problema che le chiavi o i messaggi dovrebbero diventare via via più brevi.

Si potrebbe risolvere la cosa solo in un modo, si dovrebbero mettere i bit della nuova chiave in una matrice ed effettuare su di essa una permutazione. A questo punto la dimensione della matrice unita alle permutazioni diventerebbero una seconda informazione da scambiarsi in un protocollo a doppio messaggio, mi spiego meglio.

Supponiamo che Alice e Bob abbiano una chiave K_0 che si sono scambiati su un qualche canale sicuro, e supponiamo che si siano scambiati anche due altre informazioni, Mat_0 e Perm_0 che saranno rispettivamente le dimensioni di una matrice e una permutazione sulle righe o le colonne della matrice.

A questo punto Alice prima di mangare il primo messaggio a Bob crea una nuova coppia Mat_1 e Perm_1, la lega (ad esempio zippandoli insieme) al messaggio da mandare a Bob e li cifra usando K_0, a questo punto prende una nuova chiave K_1 la inserisce bit a bit in una matrice di dimensione Mat_0, esegue su di essa la permutazione Perm_0 e cifra ancora con K_0 la matrice così ottenuta (il che ricordiamo non crea problemi al cifrario data la natura delle chiavi).

A questo punto Alice manda il secondo crittogramma con la nuova chiave cifrata a Bob il quale puoi recuperare il messaggio per lui, e le informazioni per continuare a comunicare con Alice.

Resterebbe solo il problema che un "uomo nel mezzo" potrebbe intercettare il messaggio con il crittogramma di una nuova chiave e sostituirlo e riuscire così a leggere un messaggio, ma solo uno in quanto se tentasse di rispondere sarebbe scoperto! Ma questo problema si potrebbe facilmente superare inserendo nel pacchetto con la chiave manipolata e cifrata un numero di sequenza che verrebbe inserito in modo "sparpagliato" nei nel pacchetto. Ma così facendo Alice e Bob avrebbero da aggiungere alle informazioni iniziali da scambiarsi sul canale sicuro anche altre informazioni: il numero di sequenza iniziale, il passo di avanzamento di tale numero e uno schema che dice in quali posizioni del messaggio con la nuova chiave inserire i bit di tale numero di sequenza, oltre ovviamente alle informazioni iniziali prima menzionate e cioè K_0, Mat_0 e Perm_0. Così facendo il malintenzionato non potrebbe fare nessun danno!!

Questa versione del protocollo dovrebbe funzionare... che ne pensi???
Avatar utente
nevergreen
 
Messaggi: 5
Iscritto il: dom 5 feb 2012, 2:53

Messaggioda rrronny il mer 8 feb 2012, 9:35

nevergreen ha scritto:[...] Si potrebbe risolvere la cosa solo in un modo [...] che ne pensi???

Penso di essere stanco di questo thread, il cui argomento cambia come la faccia della Luna. Lascio volentieri la "palla" agli altri utenti del forum; tuttavia, non mi meraviglierei se questa discussione fosse chiusa dai moderatori.
"Realtà virtuale", "social network", "realtà aumentata"? Io parlerei di "solitudine aumentata", quella che percepisci anche stando in mezzo agli altri, e che occorre della tecnologia per appianarla.
Avatar utente
rrronny
 
Messaggi: 737
Iscritto il: mer 17 giu 2009, 20:51
Località: Pisa

Messaggioda selvatico88 il mer 8 feb 2012, 19:39

Un grande saluto a tutto il forum mi chiamo Antonello e sono uno studente di informatica e mi sono appena iscritto. Ciao nevergreen, c'è una cosa che non mi è ben chiara, come mai cifrare la seconda chiave con la prima che è già stata usata non violerebbe i principi del OTP? O_o
selvatico88
 
Messaggi: 1
Iscritto il: mer 8 feb 2012, 19:35

Prossimo

Torna a Algoritmi e strutture dati

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite