============================================================================== ------------[ BFi numero 8, anno 3 - 30/04/2000 - file 18 di 28 ]------------- ============================================================================== -[ CRYPT0GRAPHY ]------------------------------------------------------------- ---[ RSA E CRiTT0GRAFiA SiMMETRiCA FTM (F0R THE MASS) -----[ valv{0} , vecna ------------------------------------------------------------- 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; ibit(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 ]--------------------------------- ==============================================================================