Copy Link
Add to Bookmark
Report
BFi numero 08 anno 3 file 18 di 28
==============================================================================
------------[ BFi numero 8, anno 3 - 30/04/2000 - file 18 di 28 ]-------------
==============================================================================
-[ CRYPT0GRAPHY ]-------------------------------------------------------------
---[ RSA E CRiTT0GRAFiA SiMMETRiCA FTM (F0R THE MASS)
-----[ valv{0} <valvoline@s0ftpj.org> , vecna <vecna@s0ftpj.org>
-------------------------------------------------------------
RSA e Crittografia Simmetrica fTm (for the Mass) - 05/03/2000
-------------------------------------------------------------
Date: 05/03/2000
Written by: valv{0} - valvoline@tiscalinet.it
vecna - vecna@itapac.net
consumo : almeno 2 fegati propri. (vecna)
: ...e ki se lo rikorda! (valv0)
dedicato a: tendenzialmente a mAyhEm. (vecna)
La mia Lady, il mio prof. di Crittografia. (valv0)
X-warning : Io non sono responsabile se la mia libreria e' ciccata, ho
fatto molti test e gli ho dedicato abbastanza tempo per
farla, fatto sta' che sono ancora umano e come tale posso
ancora sbagliare. (vecna)
-------------------------------------------------------------
RSA e Crittografia Simmetrica fTm (for the Mass) - 05/03/2000
-------------------------------------------------------------
- Intro - (valv0 & vecna)
-------------------------
L'implementazione, che ci apprestiamo a presentare in questo articolo, è
frutto di alcuni mesi di sviluppo. Quest'articolo si compone di due parti, che
ad un primo sguardo potrebbero sembrare slegate, ma che come vedrete dalle
prossime righe e dai prossimi lavori insieme (!) sono molto strette. Non mi
sembra conveniente raccontarvi su cosa stiamo lavorando e a cosa mirano le
librerie che presentiamo in questo articolo - Ogni progetto che si rispetti
ha la sua privacy! - ma state pur certi che il lavoro sara' davvero notevole.
Un paio di note introduttive sulle due librerie fornite a corredo di questo
bell'articolo che per quanto mi riguarda e' il primo scritto a quattro mani.
Come avrete gia' capito si tratta di librerie: codice C da abbinare ad un po'
di spremitura di cervello. Per quanto riguarda le librerie RSA, tengo a precisare
che il pacchetto fornito e' stato sviluppato con un compilatore Visual C++.
Non e' stato fatto nessun utilizzo di librerie proprietarie Microsoft, l'unico
motivo che mi ha spinto ad utilizzare questo compilatore e' stata la felice
ed efficente interfaccia di sviluppo durante la stesura delle classi.
Il progetto potra' pertanto essere facilmente importato su macchine UNIX like.
Altra punto importante da segnalare e di fondamentale importanza e' che
questo progetto vuole essere una pratica ed efficiente libreria per lo
sviluppo di applicazioni con standard RSA. Esistono in giro nella rete ed in
commercio svariate implementazioni di RSA, ma tutte hanno alcuni problemi e/o
ralletnamenti dovuti a poco felici implementazioni delle operazioni di base
sui numeri. Le librerie che ci apprestiamo a presentare non sono una felice e
nuova scoperta (RSA, d'altronte, non e' lavoro nostro!), sono pero' una nuova
e piu' efficente (spero!) implementazione. Come si vedra' e' relativamente
facile, con opportune modifiche alle librerie, passare a codifiche davvero
STRONG: 384bit ed oltre.
Per quanto riguarda invece 'anekkev', essa e' una libreria per la cifratura
simmetrica, resistente ad attacchi di bruteforcing. Scopo che il bel vecna
si e' prefisso e' quello di dimostrare la validita' degli algoritmi senza
checksum, dimostrare come un operatore semplice puo' far miscelare un testo
e una key in modo irreversibile se non con la stessa key. E per quanto mi
riguarda, direi che ci e' riuscito benissimo.
A breve (speriamo) vi faremo vedere come queste due librerie si fonderanno
insieme, per dar vita ad un sistema di codifica efficiente e strong.
Ultimo punto e concludo questa annoiante (ma necessaria) prefazione:
tengo a precisare che il materiale fornito con queste implementazioni e'
classificato dalle vigenti norme americane (STRONG ENCRYPTION).
Cosa significa? Per chi non fosse a conoscenza di queste norme, esse vietatano
di importare e/o esportare in qualunque modo algoritmi e/o testi riguardanti
crittografia classificata come STRONG. In pratica, se non si vuole essere
soggetti a provvedimenti federali, sara' necessario evitare di postare e/o
uploadare, etc. questo articolo e/o le implementazioni sorgente e/o compilate
fornite a corredo, che comunque rimangono completamente libere di girare in
tutta in Italia.
Il progetto, per la filosofia con cui e' nato ed anche perche' non abbiamo
inventato noi l'RSA(!), e' di tipo Free Source. Questo vuol dire che potete
farci quello che vi pare (nei limiti della legalita' e di quello spiegato
sopra).
Buon Divertimento! - valv{0} & vecna / s0ftpj
----------------------------------------------------------------
- Crittografia Simmetrica - (vecchie note e pericoli da evitare)
----------------------------------------------------------------
Sorvolando su Giuglio Cesare e i cifrari monoalfabetici (rot) o sostituzioni
monoalfabetiche (craccabili in pochi minuti con un pentium attuale usando
tabelle di probabilita' di ripetizione delle lettere e studiando i risultati
dei vari tentativi) vediamo che la crittografia moderna si basa
prevalentemente su algoritmi basati su sostituzioni, scambi fatti in relazione
a tabelle.
Tuttavia, durante il passaggio dagli scambi monoalfabetici alla crittografia
moderna, e' stata ampliamente utilizzata (e lo e' ancora) la crittografia
mediante l'utilizzo di cifrari polialfabetici. Anche questi tramontarono
quando si capi' che, studiando le ripetizioni che si avevano nel testo ed in
seguito a vari tentativi, si poteva poco a poco ottenere la chiave procedendo
per tentativi. Questo si poteva fare con chiavi di lunghezza inferiori al
testo da crittare (al tempo era inutile e difficile di trasportare chiavi di
lunghezza superiore o uguale al testo, ORA NON LO E' PIU').
Attualmente pero' possono essere ancora usati gli algoritimi polialfabetici
se dipendenti da una password di lunghezza infinita (matematicamente e
intuitivamente e' dimostrata la sua incrakkabilita'); una chiave di lunghezza
infinita (ovvero generate in modo pseudo-casuale in modo dipendente dalla
password) non serve se piu' lunga del testo da crittare (in questo modo non si
possono creare ripetizioni di key).
Poi vi fu' l'avvento del DES ed altri sistemi basati su sostituzioni e scambi,
ma alla fine, che il nostro algoritmo esegua una somma o 43263 milioni di
operazioni cambia poco e se l'algoritmo si e' dimostrato sicuro e la
crittoanalisi fallisce, l'unica cosa che puo' ancora fotterlo e' il
bruteforce.
---------------------------------------------
- Implementazioni & Immunita' Al Bruteforce -
---------------------------------------------
Su cosa si basa il bruteforce? Bhe, uno prova tutte le chiavi in modo
incrementale (o nel caso di una chiave "umana" si prova prima con un
dizionario di password), dopo aver decrittato il testo controlla con il
checksum del testo in chiaro se quello che ha trovato e' giusto o no e, a
seconda del risulato, riprova o smette (o continua ugualmente... il
checksum puo' essere esatto anche se il testo da cui si e' calcolato e'
differente).
Il checksum non e' detto che sia del testo in chiaro, potrebbe essere
anche il checksum della chiave, e' evidente che i checksumm vengono
calcolati in modo one-way con perdita di dati, in modo da non poter
fornire vantaggi ad alcun cracker se non la possibilita' di un confronto.
Ma perche' non levare questo confronto? In fin dei conti la sua utilita'
e' di dire "password giusta, ecco il testo decrittato" o "password errata,
ritenta e sarai + fortunato".
Quindi se eliminiamo il checksum e non commettiamo gli stessi errori dei
cifrari polialfabetici (usando crittosistemi differenti) possiamo avere un
codice cifrato che non dia ad un cracker alcuna base di calcolo ed alcuna
base per poter dire "password errata" o "password giusta".
Questo significa che dovremo avere un testo cifrato completamente
dipendente dalla chiave, ovvero che se solo un bit e' sbagliato nella
chiave il desto decrittato sara' completamente incomprensibile ed inutile
per confronti tra i vari testi decrittati.
Nota bene: ho applicato il sistema di crittografia senza checksum a una
base (alla fine anche della base rimane poco :) della tecnica usata per i
cifrari polialfabetici, ma nulla e nessuno nega di applicare questo sistema a
un sistema come 3DES o IDEA o altri algoritmi conosciuti... o anche di
applicarli entrambi.
-----------------------------------------------------------
- Algoritmi a Chiave Pubblica - (Un po' di teoria e storia)
-----------------------------------------------------------
Quando si parla di comunicazione sicura, e' necessario parlare di sistemi di
cifratura. Per sistema di cifratura si intende un tipico sistema, del tipo
illustrato qui di seguito:
.------------.
| Attaccante |
'------------'
.----------. .-----------.
| Mittente |--->01010101010101010101010101010101010101--->| Ricevente |
'----------' '-----------'
^\________________________|CHIAVE|____________________________/^
Il mittente spedisce un messaggio (testo in chiaro) al ricevente, applicando
una funzione ed una chiave segreta. Per leggere il messaggio il ricevente
dovra' apportare al testo ricevuto (testo cifrato) le operazioni inverse
corrispondenti.
Di norma bisogna supporre che il testo cifrato venga spedito attraverso linee
di comunicazione prive di sicurezza (internet) e che sia dunque a disposizione
di possibili attaccanti. I metodi di cifratura e/o decifratura devono inoltre
essere resi disponibili agli analisti, il cui scopo sara' la ricostruzione del
messaggio in chiaro a partire da quello cifrato, ignorando pero' le chiavi di
lettura. Si osservi come l'intero sistema dipenda da una precedente
comunicazione separata mediante la quale mittente e ricevente definiscono la
natura e la qualita' delle chiavi. Come regola, piu' sono le chiavi, piu' e'
sicuro il sistema cifrato.
L'idea alla base dei sistemi di criptazione a chiave pubblica e' quella di
utilizzare una lista di "chiavi di codifica". La chiave di codifica di un
qualsiasi utente (nel seguito rappresentata con P) e' di pubblico dominio.
Inoltre, tutti sono in possesso di un'altra chiave, segreta, di decifratura;
questa chaive segreta (detta S) non e' conosciuta da nessun altro.
Per trasmettere un messaggio M, il mittente preleva la chive pubblica del
destinatario e la utilizza per cifrare il messaggio che verra' poi trasmesso
al ricevente. Il messaggio cosi' cifrato viene rappresentato con C = P(M).
Il destinatario impiega la propria chiave privata per decifrare il testo
ricevuto e leggere quindi il messaggio. Perche' un sistema del genere
funzioni, devono essere soddisfatte almeno le seguenti condizioni:
o. S(P(M)) = M per qualsiasi messaggio M
o. Tutte le coppie (S, P) sono distinte
o. Derivare S da P deve essere altrettanto difficile che leggere M
o. Sia S che P sono semplici da calcolare
La prima regola e' una proprieta' fondamentale della crittografia, la seconda
e la terza ne garantiscono la sicurezza, la quarta rende fattibile un sistema
del genere.
Questo schema di base era stato definito senza pero' riuscire a descrivere un
metodo in grado di soddisfarne tutti e quattro i punti.
Un metodo del genere fu' scoperto subito dopo da R. Rivest, A. Shamir e
L.Adleman. Il loro schema, divenuto famoso come il sistema di cifratura a
chiavi pubbliche RSA, e' basato sull'applicazione di algoritmi aritmetici a
grandi valori interi. La chiave P e' in realta' una coppia di interi (N, p),
mentre la chiave S e' una coppia di interi (N, s) con s segreto.
Questi numeri devono essere estremamente grandi (tipicamente, N potrebbe
essere di 200 cifre, p ed s di 100). I metodi utilizzati per cifrare e
decifrare sono semplici: innanzitutto si scompone il messaggio in numeri
minori di N (ad esempio, considerando Log(N) bit alla volta della stringa
binaria corrispondente alla rappresentazione per caratteri del messaggio).
Questi numeri sono indipendentemente elevati ad una potenza modulo N: per
cifrare il messaggio M (in realta' una sua parte), si calcola:
C = P(M) = M^p mod N
per decifrare un testo cifrato C si calcola:
M = S(C) = C^s mod N.
Occupiamoci adesso di scegliere le crittovariabili N, p ed s in modo tale da
soddisfare la prima e la terza condizione. E' necessario, introdurre alcuni
concetti di teoria dei numeri che vanno ben oltre le mie conoscenze, ma e'
possibile accennare alle idee di base. Per prima cosa, e' ncessario generare
tre grandi numeri primi (approssimativamente di 200 cifre) "casuali": il
maggiore verra' preso come s, mentre gli altri due verranno chiamati x ed y.
A questo punto, si pone N uguale al prodotto di x ed y e si sceglie p in modo
che soddisfi la relazione:
ps mod (x-1)(y-1)=1
E' possibile dimostrare che, scegliendo N, p ed s in questo modo, risulti:
M^ps mod N = M
per tutti i messaggi M.
Ad esempio, sfruttando una codifica binaria del tipo:
-----------------------------------------------------------------------------
A |B |C |D |E |F |G |H |I |J |K |L |M |N |O |P |Q |R |S |T |U |V |W |X |Y |Z
-----------------------------------------------------------------------------
01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26
-----------------------------------------------------------------------------
il messaggio "FUCK THE NSA" potrebbe corrispondere al seguente numero:
062103110020080500141901
A questo punto, per non rendere l'esempio troppo complicato, si parte con dei
numeri primi di 2 cifre (invece delle almeno 100 richieste): si ponga:
x = 47
y = 79
s = 97.
Questi valori definiscono N = 3713 (il prodotto di x ed y) e p = 37
(l'unico intero che da' resto 1 se moltiplicato per 97 e diviso per 3588).
A questo punto, per codificare il messaggio, lo si scompone in blocchi di 4
cifre e li si eleva alla p-esima potenza (modulo N). Queste operazioni portano
ad una codifica del tipo:
0621^37 (mod N) = 3286
0311^37 (mod N) = 3536
0020^37 (mod N) = 3413
.
.
.
1901^37 (mod N) = 335
Il processo di decodifica e' lo stesso, ma si utilizza s al posto di p; cosi'
si riottiene lo stesso messaggio di partenza poiche' 3286^97 (mod 3713)=0621,
etc.
La parte piu' importante del calcolo richiesto e' la codifica del messaggio.
Pur richiedendo sofisticati concetti di teoria dei numeri e programmi
piuttosto elaborati per la gestione di numeri di notevole lunghezza, il tempo
richiesto per il calcolo delle chiavi tende ad essere inferiore al quadrato
della loro lunghezza.
---------------------------------------
- RSA fTm - (L'implementazione) - valv0
---------------------------------------
L'implementazione fornita, si compone di 6 file sorgenti:
o. prime.cpp
o. prime.hpp
o. vlong.cpp
o. vlong.hpp
o. rsa.hpp
o. rsa.cpp
I primi due file contengono alcune procedure indispensabili per la riuscita
del progetto: la ricerca dei numeri Primi.
La ricerca si basa su un teorema matematico di Fermat che afferma che:
" Se p e' primo, allora, a^(p-1) = 1 (mod p) "
Al di la' delle speculazioni puramente matematiche, questo teorema fornisce
un metodo efficiente e veloce per la ricerca dei numeri primi:
.....
for ( unsigned i=0; i<rep; i+=1 )
if ( modexp( any[i], p-1, p ) != 1 )
.....
Questo stralcio di codice, estrapolato da "prime.cpp", effettua cio' che e'
stato spiegato prima; ovviamente i numeri trovati saranno passati
successivamente ad un altro test per confermare la loro natura di numeri
primi. Viene utilizzata una funzione di appoggio, presente in "vlong.cpp":
vlong modexp( const vlong & x, const vlong & e, const vlong & m )
quello che fa' e' un semplice elevamento a potenza, con opportune conversioni
e semplificazioni. "monty", effettua tutto questo:
.....
while (1)
{
if ( e.value->bit(i) )
mul( result, t);
i += 1;
if ( i == bits ) break;
mul( t, t );
}
.....
Il terzo ed il quarto file forniscono un nuovo tipo, che potra' essere
utilizzato per le operazioni di codifica e/o decodifica. Il nuovo tipo e'
stato nominato (vlong - very long), che fantasia! Al di la' delle
dichiarazioni, punto cruciale di questi due file e' la funzione di
moltiplicazione asm:
inline unsigned dmul(unsigned m,unsigned count,unsigned * src,unsigned * dst )
La procedura si occupa appunto di una delle parti piu' importanti del
progetto.
Purtroppo sono presenti alcune problematiche, che ne rendono il suo uso poco
affidabile su alcuni processori e/o in alcune circostanze. Ci stiamo
lavorando!
Poco da dire, si tratta puramente di una moltiplicazione con riporto.
.....
unsigned char bittab[256] =
......
........
Questa e' la nostra base di lavoro, ci fa da filtro su cui andremo ad
effettuare le codifiche e interpretazioni dei numeri per i nostri calcoli.
Nel file "vlong.hpp" e' presente la classe che si occupa della definizione del
tipo vlong e delle operazioni permesse su di esso:
.....
class vlong // very long integer - eheheh, adesso possiamo usarlo come long!
{
public:
// Reimplementazione degli operatori aritmetici...
.....
Il resto del codice presente in questi due file costituisce la
reimplementazione di tutte le operazioni comuni, per poter lavorare con il
nostro nuovo tipo.
Ho visto in giro molte implementazioni (funzionanti e non) che toppavano
proprio in questo punto. Reimplementavano cioe' le operazioni in modo poco'
efficiente.
Alcune interpretavano i numeri come stringhe, reimplementando le operazioni
numero a numero, altri invece utilizzavano matrici di interi. Insomma, tutte
piu' o meno funzionanti, ma con un unico problema: la velocita'.
L'implementazione da noi proposta cerca di sorpassare questo problema,
basandosi su funzioni asm. Come specificato prima, esistono ancora alcuni
problemi, ma saranno risolti al piu' presto!
---------------------------------------
- anekkev - (L'implementazione) - vecna
---------------------------------------
Sebbene sia implementabile un algoritmo chiper di produzione propria, ho
pensato che il semplice XOR sarebbe bastato (logicamente non un xor
semplice, fatto applicando la key + volte sul testo da crittare: in questo
modo si sarebbe trattato di un sistema polialfabetico).
In questo caso applico prima l'xor in modo polialfabetico, poi tutto il
testo crittato viene xorrato con un carattere dipendente da tutta la key,
(un carattere calcolato facendo l'xor di key[1]^key[2]^...^key[KEYLEN]),
poi ripetendo l'operazione per un numero di round definibile in NOFRNDCRIPT,
dopo aver ricostruito la key. In pratica:
ABCDEFGHILMNOPRSTUVZ e' il testo da crittare
0987654321 e' la key
La prima passata del primo round viene fatta cosi':
A^0 B^1 C^2 D^3 E^4 F^5 G^6 H^7 I^8 L^9 M^0 N^1 ecc..
si ripete la key, poi si calcola l'xor della key (la funzione lame_sum lo fa)
e si critta con quel carattere tutto il testo dopo la prima passata.
Questa operazione viene eseguita per il numero di round specificato: in
questo modo gia' dalla prima passata, se uno inserisce una key che
differisce da quella esatta per solo un bit, l'xor della key sara' differente
e questo non consentira' alcun tipo di studio sulle ripetizioni. Inoltre la
key usata nei successivi round e' sempre diversa e sempre a poco a poco piu'
piccola (diminuisce di 2 byte ogni round), questo per essere ancora piu'
sicuri e al riparo da calcoli sulle ripetizioni.
La key viene ricreata ogni round con la funzione build_key : questa divide
la parte pari della key in un array, la parte dispari in un altro, poi
mette in sequenza le due meta' (prima la pari e poi la dispari) di cui
ognuna xorrata con il proprio lame_sum . Volutamente ogni parte perde un
byte ogni volta che viene ricreata, appunto per usare chiavi che diminuiscono
sempre di grandezza.
-------------------------------------
- Considerazioni & Intenzioni - vecna
-------------------------------------
I problemi che possono evidenziarsi arriveranno quando verra' immessa una
password errata e non potremo sapere se essa sara' giusta o no finche' non
apriremo il file (quando trovate gli scarabocchi in ASCII significa che la key
e' sbagliata o il file e' binario :)
Anche la compressione del file sottostante deve essere fatta senza
checksum (le zlib hanno le funzioni di compressione e di calcolo del CRC
indipendenti tra loro) perche' altrimenti si fornirebbe ad un cracker la
possibilita' di basarsi su un cheksum per determinare se la key sia giusta
o no (se lasciassimo i CRC dello zip dopo aver tentato la key potrebbe
tentare di scompattare il file e, rilevando un fallimento, scartare la
possibilita'); il bello di questo e' invece che ogni chiave da' un
risultato, ma solo una chiave da' quello giusto (e qual'e' il cracker che
legge 4 miliardi di possibili testi in chiaro :) ?
---------------------
- Conclusioni - valv0
---------------------
Cosa fare di tutto questo? In realta' le procedure sono state scritte per
dare la possibilita' a chiunque, con un minimo di competenze C/C++, di
scrivere i propri programmi sfruttando la potenza di RSA. Spero di avere fatto
un buon lavoro e sopratutto un favore gradito a tutti quelli che hanno sempre
desiderato di vedere nel suo cuore l'algoritmo di codifica RSA. A breve mi
concetrero' sulla stesura di una DLL di crypting per sistemi MIME. Ma questa
e' un'altra storia!
----------------------------
- Crediti e Ringraziamenti -
----------------------------
\sPIRIT\ - per la competenza assembler, la simpatia e la disponibilita'
Berry - per tutto quello che ha fatto e continua a fare
smaster - per la sua insuperabile professionalita'
Cavallo - terrrrrrrrruuuuuuuuuuuuuuuuuuuun! :)
- Tutta s0ftpj, per il grande lavoro che ha fatto e continua a fare
- R. Rivest, A. Shamir e L.Adleman., per la scoperta, l'implementazione e la
codifica di RSA
- La mia ragazza, per il suo supporto morale e di altro tipo! :)
- Il mio professore di C, per la sua immensa disponibilita' e competenza
...tutti quelli che non ci tornano in mente!
-------------------------------
vecna / s0ftpj - e' raggiungibile al seguente indirizzo:
email: vecna@itapac.net
valv{0} / s0ftpj / VrL - e' raggiungibile al seguente indirizzo:
email: valvoline@tiscalinet.it
-------------------------------
==============================================================================
--------------------------------[ EOF 18/28 ]---------------------------------
==============================================================================
