Newsgroup: it.comp.sicurezza.crittografia
Titolo: risallire all'algoritmo di cifratura

Immaginate di avera una scatola nera, alla quale in input arriva una chiave 
di 8 byte e in uscita fornisce un messaggio criptato (utilizzando la chiave 
di 8 byte da noi fornita) della dimensione di 64000 byte.
La mia domanda č:
- sapendo che se la chiave č 00 00 00 00 00 00 00 00,
 in uscita la scatola nera ci fornisce il messaggio in chiaro
-potendo fornire a nostro piacere la chiave e analizzare
il messaggio in uscita,
č possibile risalire all'algoritmo di criptazione?
Ripeto, quello che a noi interessa non č il messaggio ma l'algoritmo
con il quale vengono criptati i dati, quindi sarebbe possibile, avendo a 
disposizione un numero molto grande di coppie chiavi-messaggi,risalire
all'algoritmo? 


Concettualmente sì, perché il numero di algoritmi con messaggi di
dimensione finita e chiavi di dimensioni finita è finito. In pratica però
la ricerca esaustiva dell'algoritmo corretto è impossibile per le
dimensioni di interesse pratico (come nel tuo caso).
Detto questo, la soluzione al tuo problema è
- semplice se hai un elenco di algoritmi candidati, che semplicemente
devi verificare sul materiale (chiavi-messaggi) che hai a disposizione.
- complicata, ma ancora possibile, se l'algoritmo è particolarmente
semplice e dall'osservazione delle coppie (terne?) chiavi-messaggi
riesci ad intuirlo.
- credo impossibile altrimenti
Certo è che un algoritmo che con chiave 00...0 restituisca in chiaro
il messaggio è strano ed esclude immediatamente tutti gli algoritmi
noti con chiave di quella dimensione.
Anacleto

 dimensioni di interesse pratico (come nel tuo caso).
La cosa è generamente quasi impossibile, ma PROPRIO nel suo caso sarebbe
relativamente fattibile: 8 byte difatti sono solo 64 bit, e oggigiorno
una ricerca esaustiva sui 64 bit la si fa in modo "relativamente"
agevole ^_^
Comunque, per rispondere alla domanda originale: cercare l'algoritmo è
sbagliato di per sé, in quanto l'algoritmo non dovrebbe essere segreto e
non è utile che lo sia (anzi, spesso è disutile per la falsa impressione
di sicurezza che questo dà).
Per quasi tutti gli algoritmi esistenti esiste un "certo numero" di
coppie di messaggiche permettono di capire la chiave in "meno" che una
ricerca esaustiva completa, normalmente però questo numero di coppie è
comunque parecchio elevato.
(btw: quello di cui parli si chiama "known-plaintext attack" e anche
nella realtà è molto meno raro di quanto si possa pensare: spesse volte
una attaccante può avere accesso in modo più o meno diretto alla
macchina per cifrare, o comunque chiedere a un utente normale di
cifrargli un testo dato, a prescindere che questa terza persona ne sia
consapevole o meno)
  Lapo
- --
L a p o   L u c h i n i
l a p o @ l a p o . i t
w w w . l a p o . i t /
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (Cygwin)
Comment: Using GnuPG with Thunderbird - 
http://enigmail.mozdev.org
iEYEARECAAYFAkKRjcsACgkQaJiCLMjyUvtnrwCg2FMuCX/zpPqXX4S5Zm6a/ZWa
QpwAoIRBHW3XdItMYwXaLmKWBLE66Pq8
=5zA6
-----END PGP SIGNATURE-----

 una ricerca esaustiva sui 64 bit la si fa in modo "relativamente"
agevole ^_^
Dissento dissento dissento!
Lui non vuole determinare LA CHIAVE conoscendo l'algoritmo (allora sì,
la complessità sarebbe 2^64), ma determinare L'ALGORITMO. Secondo me
determinare l'algoritmo significa per definizione stabilire ad ogni
coppia (input, chiave) quale output corrisponde.
Ammesso di essere nelle condizioni di poterlo fare (chosen plaintext,
chosen key), la complessità è 2^(PLAINTEXT_SIZE+KEY_SIZE). Ora,
stando
agli elementi che ci ha fornito ****, secondo me PLAINTEXT_SIZE deve
essere intesa a rigore 64000*8, ma se anche più realisticamente fosse
per esempio PLAINTEXT_SIZE=64, risulterebbe una complessità totale
2^128,
cioè nella pratica intrattabile.
Naturalmente quanto descritto è un attacco esaustivo ed è pertanto un
limite superiore alla complessità; ciò detto è possibile che si
riesca
per uno specifico algoritmo ad individuare regolarità che permettono
di "indovinarlo" con una complessità minore.
Be', per lo meno così mi sembra.
Anacleto.

 stando
Secondo me invece la complessità è "numero di algoritmi"... che è un
numero di PARECCHI ordini di grandezza inferiore a
2^(PLAINTEXT_SIZE+KEY_SIZE).
Anzi, è un numero del tutto indipendente da PLAINTEXT_SIZE e da
KEY_SIZE: quella è la cardinalità del dominio, ma non certo tutti i
valori sono "interessanti"; sarebbe come dire che l'algoritmo "aggiungi
un numero costante" avesse infinite varianti e non che fosse uno solo
(benché con un parametro, ovvero la chiave).
IMHO è un numero che si aggira tra 2^3 e 2^10 a seconda delle stime...
In ogni caso non colgo particolarmente l'utilità di cercare l'algoritmo
data la chiave: questo non è un problema "difficile" di ricerca di dato
segreto, ma piuttosto un problema affrontabile in genere "in altri modi"
con il reverse engineering.
(certo, "rompere la cifratura" significAVA "ricavare l'algoritmo", PRIMA
del principio di Kerckhoffs... ma non più, voglio sperare!)
Secondo me questi casi si dividono largamente in due casi:
quelli che conoscono la crittografia SANNO che è inutile tenere segreto
l'algoritmo e quindi non c'è bisogno di "capirlo" a priori, tutti gli
altri, in media, usano algoritmi "inventati" e assolutamente deboli...
  Lapo
- --
L a p o   L u c h i n i
l a p o @ l a p o . i t
w w w . l a p o . i t /
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (Cygwin)
Comment: Using GnuPG with Thunderbird - 
http://enigmail.mozdev.org
iEYEARECAAYFAkKSXPIACgkQaJiCLMjyUvspqwCgwnQavipJlzis4HCVb+hpq0ct
fswAoNxN2wbl7+PQMAOx0AOQPfILNXzk
=etkP
-----END PGP SIGNATURE-----

   Lapo
Su questo sono completamente d'accordo. 
Ciao
Anacleto

Rettifico i dati del problema da me posto nel primo post.
In realtà la chiave è di 20 byte, prima avevo detto 8 byte solo per 
semplificare.
Ribadisco invece che se la chiave è posta a zero, si ottiene
il messaggio in chiaro. Ho scaricato il programma Truecrypt, il quale 
permette di fare un test sui vari algoritmi supportati: 
AES,Blowfish,Serpent,Triple DES,TwoFish CAST5 e altri, e ho potuto 
verificare che anche se la chiave è posta a zero e il messaggio in chiaro è 
posto a zero, il messaggio cifrato è diverso da zero.
Si può dedurre che nel mio caso l'algoritmo è piuttosto semplice?
Come posso fare a capire qual è la lunghezza del blocco dati su cui agisce 
l'algoritmo?

 l'algoritmo?
Dipende. Innanzitutto sei certo che l'algoritmo in questione sia un block
cipher e non uno stream cipher? Se è un block cipher, in che modalità
opera (ECB, CBC, ...)? Se è in ECB puoi provare a cifrare un blocco
di 2L byte, costituito da due semiblocchi identici ciascuno di L byte.
Se i 2L byte risultanti hanno la stessa struttura (cioè 2 metà identiche)
allora il blocco su cui opera l'algoritmo ha lunghezza L, altrimenti provi
ad incrementare L e a ripetere il tentativo fino a che trovi la lunghezza
corretta.
Se è in CBC la cosa è un po' più complicata. Però il CBC richiede un
vettore di inizializzazione, che non so se nel tuo caso sia presente (a meno
che abbia un valore implicito).
Ciao
Anacleto

 l'algoritmo?
Se lavora in CBC o modi simili va a "blocchi" interi, quidni è facile:
dagli ni pasto 1 solo carattere, e il numero di caratteri che uscirà (8,
16, 32...) è la dimensione del blocco, con tutta probabilità.
Se invece lavora in OFB, CTR o modi simili non credo ci sia modo
"semplice" di capirlo.
La domanda è: ma tu questo algoritmo puoi accederci quando vuoi ma "da
remoto" o hai diretto controllo dell'eseguibile?
Il primo caso (attacco online) pone maggiori problemi, nel secondo caso
invece ti consglio di lanciarlo in un debugger e "leggertelo"
direttamente in assembler: è certo MOLTO più facile che non capirlo "per
prove".. in tal caso sarebbe come APRIRE la scatola nera...
- --
L a p o   L u c h i n i
l a p o @ l a p o . i t
w w w . l a p o . i t /
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (Cygwin)
Comment: Using GnuPG with Thunderbird - 
http://enigmail.mozdev.org
iEYEARECAAYFAkKUTy8ACgkQaJiCLMjyUvuowQCg1nJLu/Cfd987Ffh3wOhDHSAN
ZQAAmgM0KqBgznAXPZ1iPb9x3UK5A+m4
=95Lv
-----END PGP SIGNATURE-----

 Probabilmente sì.
Nota: un algoritmo MOLTO semplice e che ha la caratteristica che dici
(chiave 0 non cifra nulla) è "XOR in ECB"... ovvero prendi una chiave
lunga un blocco e la applichi "in XOR" blocco per blocco.
Tristemente è un algoritmo che alcuni usano, credendolo un OTP
ultrasicuro, invece, come dire... fa schifo ^_^
In tal caso ti basta un velocissimo calcolo delle frequenze per
"romperlo" e tra l'altro lo XOR tra due blocchi cifrati è identico allo
XOR tra due blocchi non cifrati, con queste equazioni puoi facilmente
recuperare i contenuti, sopratutto se i dati in chiaro erano testo o
altre cose "riconoscibili" e a bassa densità di entropia.
(il testo, più o meno in tutte le lingue, si stima intorno ai 2 bit per
carattere, ma in genere ne vengono usati 8 per immagazzinarlo, quindi la
densità di entropia è meno di 0.25 bit/bit)
- --
L a p o   L u c h i n i
l a p o @ l a p o . i t
w w w . l a p o . i t /
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (Cygwin)
Comment: Using GnuPG with Thunderbird - 
http://enigmail.mozdev.org
iEYEARECAAYFAkKUU1IACgkQaJiCLMjyUvvF2wCg+YIUUzSJ743kbUJO9Wg6OSw8
oaYAoJKQT7WnaD9MswTY5v6r/XO7CDDM
=1mFm
-----END PGP SIGNATURE-----