==Phrack Inc.== Volume 0x0b, Issue 0x3f, Phile #0x03 of 0x14 |=---------------------=[ L I N E N O I S E ]=---------------------------=| |=-----------------------------------------------------------------------=| |=------------------------=[ phrack staff ]=-----------------------------=| |=------------=[ Traduit par TboWan pour arsouyes.org ]=-----------------=| ...tout ce qui ne rentrait pas ailleur mais qui merite d'etre mentionne dans notre merveilleux magazine.... appreciez le linenoise. 0x03-1 Analyse de binaires soupconnables par Boris Loza 0x03-2 TCP Timestamp pour compter les hotes derriere du NAT par Elie aka Lupin 0x03-3 Cryptographie par courbes ellibtiques par f86c9203 |=-------------------------=[ 0x03-1 ]=----------------------------------=| |=--------Analyse de binaires et de processus soupconnables--------------=| |=-----------------------------------------------------------------------=| |=----------------------Par Boris Loza, PhD------------------------------=| |=-------------------bloza@tegosystemonline.com--------------------------=| |=-----------------------------------------------------------------------=| 1. Introduction 2. Analyse d'un etrange binaire 3. Analyse d'un etrange processus 4. Investigations grace a Dtrace 5. Conclusion --[ Introduction L'art de l'investigation en sécurite requiert beaucoup de patience, de creativite et d'observation. Vos efforts ne seront pas toujours couronnes de succes mais vous aiguiserez constamment votre esprit en pratiquant, en apprenant plus de choses et c'est ce qui, en fin de compte, vous aidera. Dans cet article, j'aimerais partager mon experience personnelle dans l'analyse de binaires et de processus soupconnables que vous pourriez rencontrer dans votre systeme. Nous n'utiliseront que des outils UNIX standart. Les exemples fournis dans l'articles ont été realises sous Solaris OS. --[ Analyse d'un étrange binaire Pendant vos investigations, vous rencontrerez certains fichiers executables (des binaires) dont vous ne comprenez pas l'utilite dans le systeme. Quand vous voulez lire son contenu, il n'affiche que des miettes. Vous ne reconnaissez pas son nom et vous n'Útes pas sur de l'avoir deja  vu avant. Malheureusement, vous ne pouvez pas lire ces binaires avec more, cat, pg, vi ou tout autre utilitaire que vous utilisez d'habitude pour les fichiers textes. Vous allez avoir besoin d'autres outils. Pour pouvoir lire ce genre de fichiers, j'utilise les outils suivants: strings, file, ldd, adb, et d'autres. Admettons, par exemple, que nous avons trouve un fichier nomme cr1 dans le repertoire /etc. La premiere commande que nous lancons sur ce fichier est strings(1). Il nous fournira toutes les chaines de caracteres lisibles du fichier objet ou du binaire. $ strings cr1 | more %s %s %s%s%s -> %s%s%s (%.*s) Version: 2.3 Usage: dsniff [-cdmn] [-i interface] [-s snaplen] [-f services] [-t trigger[,...]] [-r|-w savefile] [expression] ... /usr/local/lib/dsniff.magic /usr/local/lib/dsniff.services ... La sortie est tres longue, alors, une partie a ete tronquee. Mais on peut voire qu'il s'agit de l'utilitaire dsniff. Parfois, vous ne serez pas si chanceux en trouvant le nom du programme, sa version et son usage dans le fichier. Si vous ne savez toujours pas ce que peut faire le fichier, essayer de lancer strings avec le flag 'a' ou '-'. Avec ces options, strings cherchera des chaines de caracteres partout dans le fichier. Si ces flags sont ommis, strings ne regarde que dans l'espace des données initialisées du fichier objet : $ strings cr1 | more Essayez de comparer ceci avec la sortie de fichier bien connus pour avoir une idée de ce que le programme fait. Sinon, vous pouvez utiliser la commande nm(1) pour recuperer la liste de noms d'un fichier objet : $ /usr/ccs/bin/nm -p cr1 | more cr1: [Index] Value Size Type Bind Other Shndx Name [180] |0 | 0| FILE | LOCL | 0 |ABS | decode_smtp.c [2198] |160348| 320| FUNC | GLOB | 0 | 9 | decode_sniffer Notez que la sortie peut contenir des centaines de lignes, en fonction de la taille du fichier objet. Vous pouvez rediriger la sortie de nm vers more ou pg, ou encore vers un fichier pour l'analyser plus tard. Pour regarder la table des symboles de l'éditeur de liens dynamiques - les appels à des librairies partagees, utilisez nm avec l'option '-Du'. -D permet d'afficher la table des symboles utilisee par ld.so.1 et est même presente dans les executables dynamiques depouilles. -u imprime un long listing pour chaque symbole non defini. Vous pouvez aussi copier une partie selectionnee de nimporte quel binaire avec les outils dump(1) et elfdump(1). La commande suivante copiera la table des chaines du binaire cr1 : $ /usr/ccs/bin/dump -c ./cr1 | more You may use the following options to dump various parts of the file: -c Dump the string table(s). -C Dump decoded C++ symbol table names. -D Dump debugging information. -f Dump each file header. -h Dump the section headers. -l Dump line number information. -L Dump dynamic linking information and static shared library information, if available. -o Dump each program execution header. -r Dump relocation information. -s Dump section contents in hexadecimal. -t Dump symbol table entries. Note : pour afficher des informations de version interne contenue dans les fichiers ELF, utilisez l'outil pvs(1). Si vous n'ete toujours pas sur de la nature du fichier, lancez la commande file(1) : $ file cr1 cr1: ELF 32-bit MSB executable SPARC32PLUS Version 1, V8+ Required, UltraSPARC1 Extensions Required, dynamically linked, not stripped Avec ces resultats, nous pouvons dire que c'est un fichier executables pour SPARC qui requiert des librairies chargees par l'OS (liee dynamiquement). Ce fichier n'est pas non plus depouille, ce qui signifie que la table des symboles n'a pas ete retiree du fichier compile. Ceci nous aidera beaucoup lors d'analyses futures. Note : pour se depouiller des symboles, faites strip . La commande file permet aussi de savoir qu'un fichier est lie statiquement, avec des informations de deboguage ou même depouille. Les fichiers lie statiquement contiennent toutes leurs fonctions au sein du binaire, mais ces fichiers sont aussi plus gros. Les informations de deboguage incluent les symboles de deboguage, comme les noms de variables, de fonctions, les symboles internes, les numero des lignes du source, et des informations sur le fichier source. Si le fichier est depouille, sa taille est plus petite. La commade file identifie le type du fichier en testant, parmis d'autres tests, si le fichier commence par certains nombres magiques (voire le fichier /etc/magic). Ce nombre magique est en fait une constante numerique ou chaine de caractere qui indique le type de fichier. Voire magic(4) pour les explication du format du fichier /etc/magic. Si vous ne savez toujours pas à quoi peut servir le fichier, regardez de quelles librairies partagees le fichier a besoin en utilisant la commande ldd(1) : $ ldd cr1 ... libsocket.so.1 => /usr/lib/libsocket.so.1 librpcsvc.so.1 => /usr/lib/librpcsvc.so.1 ... Ce resultat nous montre que l'application requiert des librairies reseaux partagees (libsocket.so.1 et librpcsvc.so.1). Le debogueur adb(1) peut aussi etre tres utile. Par example suivant montre, pas a pas, l'execution du binaire : # adb cr1 :s adb: target stopped at: ld.so.1`_rt_boot: ba,a +0xc ,5:s adb: target stopped at: ld.so.1`_rt_boot+0x58: st %l1, [%o0 + 8] Vous pouvez aussi analyser le fichier, ou le lancer et voire comment il fonctionne. Mais soyez prudent quand vous lancez une application parce que vous n'en connaissez pas le but. Par example : # adb cr1 :r Using device /dev/hme0 (promiscuous mode) 192.168.2.119 -> web TCP D=22 S=1111 Ack=2013255208 Seq=1407308568 Len=0 Win=17520 web -> 192.168.2.119 TCP D=1111 S=22 Push Ack=1407308568 On peut voire que ce programme est un snigger. Voire adb(1) pour plus de details sur comment utiliser le debogueur. Si vous decidez malgre tout de lancer le programe, vous pouvez utiliser truss(1). La commande truss permet de lancer un programme tout en affichant les appels et signaux systemes. Note : truss affiche beaucoup de choses. Redirigez la sortie vers un fichier : $ truss -f -o cr.out ./cr1 listening on hme0 ^C $ Maintenant, vous pouvez examiner tranquillement le fichier cr.out. Comme vous pouvez le voire, beaucoup d'outils et de techniques permettent d'analyser d'etranges binaires. Mais tous les fichiers ne sont pas facile a analyser. Si un fichier est lie statiquement et depouille, il sera beaucoup plus difficile de savoir ce que le binaire (programme) est sense faire. Si vous n'obtenez rien de bon en utilisant des outils comme string et ldd, essayer de le deboguer avec truss. L'experience d'analyse avec ces outils, ajoutee a beaucoup de patience, vous recompensera de succes. --[ Analyse d'un etrange processus Que faire quand on trouve un processus qui tourne sur notre systeme mais dont on ne sais pas ce qu'il fait ? Oui, sous UNIX tout est fichier, meme un processus. Il se peut tout de meme qu'une application fonctionne sur le systeme mais son fichier aie ete supprime. Dans cette situation, le processus continue a fonctionner car il existe toujours un lien vers le fichier /proc/[PID]/object/a.out, mais vous ne trouverez pas le fichier par son nom avec la commande find(1). Par exemple, admettons que nous analysons le processus ID 22889 de l'applicaion suspecte srg que nous avons vu fonctionner sur notre systeme : # ps -ef | more UID PID PPID C STIME TTY TIME CMD ... root 22889 16318 0 10:09:25 pts/1 0:00 ./srg ... Parfois, c'est aussi simple que de lancer la commande strings(1) sur le fichier /proc/[PID]/object/a.out pour l'identifier. # strings /proc/22889/object/a.out | more ... TTY-Watcher version %s Usage: %s [-c] -c turns on curses interface NOTE: Running without root privileges will only allow you to monitor yourself. ... On peut voire que cette commande est un TTY-Watcher, application qui peut ecouter toutes les frappes au clavier de n'importe quel terminal du systeme. Supposons que nous n'avons pas pu utiliser strings pour identifier ce que le processus fait. Nous pouvons l'examiner avec d'autres outils. Vous pourriez vouloir suspendre l'execution du processus jusqu'a ce que vous en sachiez plus sur lui. Par exemple, lancer "kill -STOP 22889" en super-utilisateur. Verifiez le resultat. Nous cherchons apres un 'T' qui signifie que le processus est arrete : # /usr/ucb/ps | grep T root 22889 0.0 0.7 3784 1720 pts/1 T 10:09:25 0:00 ./srg On reprend l'execution du processus, si necessaire, avec "kill -CONT ". Pour des analyses futures, nous allons faire un "core dump" (capture) des variables et de la pile du processus : # gcore 22889 gcore: core.22889 dumped Ici, 22889 est l'ID (PID) du processus. On examine le contenu de core.22889 avec strings : # strings core.22889 | more ... TTY-Watcher version %s Usage: %s [-c] -c turns on curses interface NOTE: Running without root privileges will only allow you to monitor yourself. ... Vous pourriez aussi utiliser coreadm(1M) pour analyser le fichier core.22889. L'outil coreadm fournis une interface pour choisir les parametres qui influe sur la creation du fichier core.. La commande coreadm modifie le fichier /etc/coreadm.conf. Ce fichier est lu au demarrage du systeme et positionne les parametres globaux pour la creation de core dump. Tout d'abord, essayons que le nom de fichier soit de la forme "core... Nous ne ferons cela que pour les processus executes dans ce shell (la notation $$ est similaire au PID du shell courant) : $ coreadm -p core.%f.%p $$ Le "%f" indique que le nom de programme sera inclu, le "%p" indique que le PID sera attache au nom du fichier core. Vous pourriez aussi utiliser adb pour analyser le processus. Si vous ne disposez pas du fichier objet, utilisez /proc/[PID]/object/a.out. Vous pouvez utiliser un fichier core du processus capture ("dumped") par gcore ou specifier un '-' comme fichier core. Si un tiret ('-') est specifie pour fichier core, adb utilisera la memoire systeme pour executer le fichier. Vous pouvez en fait lancer le fichier obet sous le controle d'adb (ce peut etre dangereux puisque vous ne savez pas ce que fait le processus exactement). # adb /proc/22889/object/a.out - main:b :r breakpoint at: main: save %sp, -0xf8, %sp ... :s stopped at: main+4: clr %l0 :s stopped at: main+8: sethi %hi(0x38400), %o0 $m ? map ... b11 = ef632f28 e11 = ef6370ac f11 = 2f28 `/usr/lib/libsocket.so.1' $q On commance la session en placant un point d'arret ("break point") au debut du main() et ensuite en commancant l'execution de a.out en donnant la commande ':r' a adb. Nous nous arretons directement au main(), la ou nous avons place le point d'arret. Ensuite, nous listons les premieres instructions du fichier objet. La commande ':s' demande a adb de poursuivre d'un pas (une instruction assembleur) a la fois l'execution du processus. Note : lisez le livre Panic!, par Drake et Brown, pour plus d'informations sur l'utilisation d'adb dans l'analyse des core dump. Pour analyser le processus qui tourne, utilisez truss : # truss -vall -f -o /tmp/outfile -p 22889 # more /tmp/outfile Sur d'autres systemes UNIX, quand c'est disponible, vous pourriez tracer un processus avec les commandes ltrace et strace. Pour commencer la trace du processus, faite "ltrace -p ". Pour voir l'environement d'execution du processus, vous pouvez faire comme suit : # /usr/ucb/ps auxeww 22889 USER PID %CPU %MEM SZ RSS TT S START TIME COMMAND root 22889 0.0 0.4 1120 896 pts/1 S 14:15:27 0:00 - sh _=/usr/bin/csh MANPATH=/usr/share/man:/usr/local/man HZ= PATH=/usr/sbin:/usr/bin:/usr/local/bin:/usr/ccs/bin:/usr/local/sbin: /opt/NSCPcom/ LOGNAME=root SHELL=/bin/ksh HOME=/ LD_LIBRARY_PATH=/usr/openwin/lib:/usr/local/lib TERM=xterm TZ= Le repertoire /usr/ucd contient les commandes comptatibles SunOS/BSD. La commande /usr/ucd/ps affiche des informations sur les processus. Nous avons utilise les options suivantes (tire du manuel de ps(1B)) : -a (autre) presente egalement les processus d'autres utilisateurs. -u (utilisateur) affiche les resultats suivant les utilisateurs. Ca inclu les champs USER, %CPU, o %MEM, SZ, RSS et START comme decrit plus bas. -x Inclu les processus qui n'ont pas de terminal de controle. -e (environnement) Presente l'environnement a la suite de la ligne de commande executee. -w (wide) utilise un affichage plus large (132 colonnes plutot que 80). Si w est double ('-ww'), utilise un affichage arbitrairement large. Cette information est utilisee pour savoir combien de commande imprimer. Pour voir l'adresse de la memoire faites : # ps -ealf | grep 22889 F S UID PID PPID C PRI NI ADDR SZ WCHAN STIME TTY TIME CMD 8 S root 3401 22889 0 41 20 615a3b40 474 60ba32e6 14:16:49 pts/1 0:00 ./srg Pour voire l'utilisation memoire, faites : # ps -e -opid,vsz,rss,args PID VSZ RSS COMMAND ... 22889 3792 1728 ./srg On peut voire que ./srg utilise 3.792 K de memoire virtuelle, dont 1.728 a ete allouee dans la memoire physique. On peut aussi utiliser l'outil /etc/crash(1M) pour examiner le contenu de la structure "proc" ("proc structure") du processus courant : # /etc/crash dumpfile = /dev/mem, namelist = /dev/ksyms, outfile = stdout > p PROC TABLE SIZE = 3946 SLOT ST PID PPID PGID SID UID PRI NAME FLAGS ... 66 s 22889 16318 16337 24130 0 58 srg load > p -f 66 PROC TABLE SIZE = 3946 SLOT ST PID PPID PGID SID UID PRI NAME FLAGS 66 s 22889 16318 16337 24130 0 58 srg load Session: sid: 24130, ctty: vnode(60b8f3ac) maj( 24) min( 1) ... > Après avoir invoque crash, nous avons utilise la fontion p pour recuperer le contenu de la table (66 dans notre cas). Ensuite, pour capturer la structure "proc" du processus PID 22889, nous avons encore utilise la fonction p mais avec le flag "-f" et le numero de la case de la table. Comme la structure du processus, la uarea contient le support des donnees pour les signaux, incluant un tableau qui defini la disposition de chaque signal possible. La disposition des signaux dis au systeme d'exploitation quoi faire quand un signal survient (s'il doit l'ignorer, le capturer, utiliser une methode definie par l'utilisateur ou encore utiliser l'action par default). Pour capturer l'uarea d'un processus : > u 66 PER PROCESS USER AREA FOR PROCESS 66 PROCESS MISC: command: srg, psargs: ./srg start: Mon Jun 3 08:56:40 2002 mem: 6ad, type: exec su-user vnode of current directory: 612daf48 ... > La fonction 'u' prend le numero dans la table comme argument. Pour capturer l'espace d'adressage d'un processus, faites : # /usr/proc/bin/pmap -x 22889 Pour avoir la liste des fichiers ouverts par le processus, utilisez la commande /usr/proc/bin/pfiles : # /usr/proc/bin/pfiles 22889 La commande liste le nom du processus et le PID des fichiers ouverts par le processus. Notez que divers bits d'informations sont fournis pour chaque fichier ouvert, comme le type, les flags, le mode et la taille. Si vous ne pouvez pas trouver le binaire et que le processus est seulement en memoire, vous pouvez quand même utilisez les methodes decrites plus haut sur le fichier objet du processus. Par exemple : # /usr/ccs/bin/nm a.out | more a.out: [Index] Value Size Type Bind Other Shndx Name ... [636] | 232688| 4|OBJT |GLOB |0 |17 |Master_utmp [284] | 234864| 20|OBJT |GLOB |0 |17 |Mouse_status Vous pourriez aussi utiliser mdb(1) - un debogueur modulaire pour analyser le processus : # mdb -p 22889 Loading modules: [ ld.so.1 libc.so.1 libnvpair.so.1 libuutil.so.1 ] > ::objects BASE LIMIT SIZE NAME 10000 62000 52000 ./srg ff3b0000 ff3dc000 2c000 /lib/ld.so.1 ff370000 ff37c000 c000 /lib/libsocket.so.1 ff280000 ff312000 92000 /lib/libnsl.so.1 --[ Investigation grace a Dtrace Un nouvel outil a ete introduit dans la Solaris 10 pour le tracage dynamique dans l'environnement systeme - dtrace. C'est un outil tres puissant qui permet aux administrateurs systeme d'observer et de deboguer le comportement de l'OS ou meme de modifier le noyau dynamiquement. Dtrace a son propre langage de programmation (proche du C/C++) appele 'langage D' et fournis plein d'options differentes que je ne vais pas detailler ici. Allez voire les page de manuel dtrace(1M) ou la page http://docs.sun.com/app/docs/doc/817-6223 pour plus d'information. Bien que, a la base, cet outils ait ete developpe pour les developpeurs et les administrateurs, je vais expliquer comment on peut l'utiliser pour analyser les binaires et les processus suspects. Nous allons travailler sur une etude de cas. Par exemple, assumons que nous allons etudier le processus ID 968 de l'application suspecte srg que nous avons vu fonctionner sur notre systeme. En donnant la commande suivante, on va pouvoir lister tous les fichiers ouverts par le processus pendant qu'on le surveille. Laissons la fonctionner un petit moment pour la fermer ensuite par control + c : # dtrace -n syscall::open:entry'/pid == 968/ { printf("%s%s",execname,copyinstr(arg0)); }' dtrace: description 'syscall::open*:entry' matched 2 probes ^C CPU ID FUNCTION:NAME 0 14 open:entry srg /var/ld/ld.config 0 14 open:entry srg /lib/libdhcputil.so.1 0 14 open:entry srg /lib/libsocket.so.1 0 14 open:entry srg /lib/libnsl.so.1 Le langage D vient avec sa propre terminologie, que je vais essayer de decrire brievement ici. La contruction complete "syscall::open:entry" est appelee une "sonde" ("probe" en anglais) et definis l'endroit ou les evenement auxquels dtrace doit lier un ensemble d' "actions". L'element "syscall" de la sonde est appele le "fournisseur" ("provider" en anglais) et, dans notre cas, permet d'activer notre sonde sur "entry" (le demarage de l'evenement a surveiller) pour tout appel systeme a "open" (cet appel systeme demande au noyau d'ouvrir un fichier pour lire ou ecrire). Le predicat ( /pid == 968/) utilise la varaible pid predefinie dans dtrace, qui est toujours evaluee par l'ID du processus qui a lance la sonde correspondante. Le "execname" (respectivement "copyinstr(arg0)") est appelle "action" et definit le nom du fichier executable du processus courant (resp. converti le premier argument entier de l'appel systeme (arg0) en chaine de caracteres). L'action "printf" utilise la meme syntaxe qu'en C et sert a la meme chose - formater la sortie. Chaque programme D contient une serie de clauses, chaque clause decrit une ou plusieurs sondes a mettre en place et un ensemble optionnel d'action a faire quand la sonde correspondante est lancee. Les actions sont listee comme une serie de commandes entouree d'accolades ('{' et '}') apres la sonde. Chaque commande est terminee par un point-virgule (';'). Vous pouvez lire l'introduction du "Solaris Tracing Guide" (http://docs.sun.com/app/docs/doc/817-6223) pour plus d'options et pour comprendre la syntaxe. Note : comme le nom le suggere, l'utilitaire dtrace (tracage dynamique) montre des informations des processus qui changent (dynamiquement). Autrement dit, si le processus "idle" (ne fait aucun appel systeme ou n'ouvre aucun fichiers), vous ne recolterez aucune informations. Pour analyser le processus, redemarrez-le ou utilisez les autres techniques decrites des les sections precedantes de ce papier. Maintenant, nous allons utiliser la commande suivante pour lister tous les appels systemes fait par srg. Laissons-la tourner un moment puis arretons-la par ctrl+c : # dtrace -n 'syscall:::entry /execname == "srg"/ { @num[probefunc] = count(); }' dtrace: description 'syscall:::entry ' matched 226 probes ^C pollsys 1 getrlimit 1 connect 1 setsockopt 1 ... Vous pouvez reconnaitre quelques elements de contruction de ce petit programme D. En plus, cette clause definis un tableau appelle "num" associant aux "probefunc" (les appels systemes executes) le nombre de fois qu'ils ont ete executes (cout()). En utilisant dtrace, on peut facilement emuler tous les outils que nous avont utilises dans les sections precedantes pour analyser les binaires et processus suspects. Mais dtrace est beaucoup plus puissant et nous fournis plus de fonctionnalites : par exemple, surveiller la pile d'un processus : # dtrace -n 'syscall:::entry/execname == "srg"/{ustack()}' 0 286 lwp_sigmask:entry libc.so.1`__systemcall6+0x20 libc.so.1`pthread_sigmask+0x1b4 libc.so.1`sigprocmask+0x20 srg`srg_alarm+0x134 srg`scan+0x400 srg`net_read+0xc4 srg`main+0xabc srg`_start+0x108 A partir de nos investigations (la liste des fichiers ouverts, les appels systemes et la surveillance de la pile), on peut conclure que srg est une application reseaux. Mais envoie-t-il des donnees par le reseaux ? Regardons ca avec la commande suivante : # dtrace -n 'mib:ip::/execname == "srg"/{@[execname]=count()}' dtrace: description 'mib:ip::' matched 412 probes dtrace: aggregation size lowered to 2m ^C srg 520 Et oui, il le fait. Nous avons utilise "mib" pour savoir si notre application envoye des choses sur le reseaux. Mais est-ce un sniffer ou une application du genre netcat qui est liee a un port precis ? Lancons dtrace en mode similaire a truss(1) pour repondre a la question (inspire de l'outil dtruss de Brendan Gregg) : #!/usr/bin/sh # dtrace=' inline string cmd_name = "'$1'"; /* ** Save syscall entry info */ syscall:::entry /execname == cmd_name/ { /* set start details */ self->start = timestamp; self->arg0 = arg0; self->arg1 = arg1; self->arg2 = arg2; } /* Print data */ syscall::write:return, syscall::pwrite:return, syscall::*read*:return /self->start/ { printf("%s(0x%X, \"%S\", 0x%X)\t\t = %d\n",probefunc,self->arg0, stringof(copyin(self->arg1,self->arg2)),self->arg2,(int)arg0); self->arg0 = arg0; self->arg1 = arg1; self->arg2 = arg2; } ' # Lancement de dtrace /usr/sbin/dtrace -x evaltime=exec -n "$dtrace" >&2 Sauvez en tant que truss.d et changer les permission pour le rendre executable. Ensuite, lancez : # ./truss.d srg 0 13 write:return write(0x1, " sol10 - > 192.168.2.119 TCP D=3138 S=22 Ack=713701289 Seq=3755926338 Len=0 Win=49640\n8741 Len=52 Win=16792\n\0", 0x5B) = 91 0 13 0 13 write:return write(0x1, "192.168.2.111 -> 192.168.2.1 UDP D=1900 S=21405 LEN=140\n\0", 0x39) = 57 ^C D'apres moi, ca ressemble a un sniffer, avec surement une identification distante (souvenez-vous des transmissions reseaux par ./srg decouvertes avec le fournisseur "mib" plus haut!). Vous pouvez en fait ecrire des programmes pratiques et assez sophistiques pour dtrace en langage D. Regardez /usr/demo/dtrace pour des exemples. Vous pourriez aussi utiliser dtrace pour d'autres investigations. Juste apres, vient un exemple de programme plus complexe qui permet de surveiller qui a lance l'application suspecte et commence a enregistrer la liste des fichiers ouverte par le processus : #!/usr/bin/sh command=$1 /usr/sbin/dtrace -n ' inline string COMMAND = "'$command'"; #pragma D option quiet /* ** Print header */ dtrace:::BEGIN { /* print headers */ printf("%-20s %5s %5s %5s %s\n", "START_TIME","UID","PID","PPID","ARGS"); } /* ** Print exec event */ syscall::exec:return, syscall::exece:return /(COMMAND == execname)/ { /* print data */ printf("%-20Y %5d %5d %5d %s\n",walltimestamp,uid,pid,ppid, stringof(curpsinfo->pr_psargs)); s_pid = pid; } /* ** Print open files */ syscall::open*:entry /pid == s_pid/ { printf("%s\n",copyinstr(arg0)); } ' Sauvez ce script en wait.d, changez les permission pour le rendre executable et lancez : # ./wait.d srg START_TIME UID PID PPID ARGS 2005 May 16 19:51:20 100 1582 1458 ./srg /var/ld/ld.config /lib/libnsl.so.1 /lib/libsocket.so.1 /lib/libresolv.so.2 ... ^C Une fois que srg est lance, vous verrez la sortie. En fait, la reelle puissance de dtrace vient du fait qu'on peut faires des choses avec lui qui ne seraient pas possible en ecrivant un programme C comprehensible. Par exemple, l'application shellsnoop ecrite par Brendan Gregg (http://users.tpg.com.au/adsln4yb/DTrace/shellsnoop) vous permet d'utiliser dtrace comme ttywatcher! Il n'est pas possible de montrer toutes les capacites de dtrace dans cette petite presentation de ce stupefiant outil. Dtrace est très puissant en tant qu'outil complexe au capacites quasi infinies. Bien que Sun insiste sur le fait qu'une connaissance profonde du noyau ne soit pas necessaire pour que dtrace nous soit utile, une connaissance des bases du noyau de Solaris est tres appreciable. Regarder dans le fichier d'inclusion dans le repertoire /usr/include/sys/ vous aidera a ecrire des scripts D plus complexes et vous aidera a mieux comprendre comment Solaris 10 est implemente. --[ Conclusion Soyez creatifs et observateurs. Appliquez toutes vos connaissances et votre experience pour analyser des binaires et des processus suspects. Soyez aussi patient et ayez un sens de l'umour! |=-------------------------=[ 0x03-2 ]=----------------------------------=| |=----=[ TCP Timestamp pour compter les hotes derriere du NAT ]=---------=| |=-----------------------------------------------------------------------=| |=-------------=[ Elie aka Lupin (lupin@zonart.net) ]=-------------------=| Sommaire *=*=*=*=* 1.0 - Introduction 2.0 - Le temps a quelque chose a nous dire - 2.1 Un peut d'histoire - 2.2 Et aujourd'hui ? - 2.3 Retour au debut du timestamps - 2.4 Retour au college - 2.5 Retour au NAT - 2.6 Faisons du PAT - 2.7 Il est temps de se defendre 3.0 L'histoire a quelque chose a nous dire - 3.1 Quelle classe ? - 3.2 mais d'ou vient-il ? - 3.3 Comment l'ai-je trouve ? - 3.4 Retour vers le futur - 4 Tirer les lecons du passe - A Remerciements - B Preuve de concept --[ 1.0 - Introduction Cet article va parler de l'option TCP timestamp. Cette option peut etre utilisee pour compter les machines derriere du NAT et faire de la detection d'empruntes ("OS fingerprinting") d'une maniere differente. Plus profondement, cet article essaye de donner une nouvelle vision d'une classe de bugs connue sous le nom d' "erreur de conception". Le bug decrit ici a de l'interet pour les raisons suivantes : - C'est nouveau. - Il affecte toutes les plateformes puisqu'il est du aux specifications plutot qu'a l'implementations. - C'est une bonne maniere pour expliquer comment on peut casser certaines specifications L'articles est organise de la facon suivante : tout d'abord, je vais essayer d'expliquer ce qui ne va pas avec le timestamp TCP. Ensuite, je decrirai la facon de l'exploiter, les limites de cette exploitation et les facon de l'eviter. Dans la seconde partie, je parlerai des origines de cette erreur et du pourquoi elle arrivera encore. A la fin, je fournirai une preuve de concept ("proof of concept") et des remerciements comme d'habitude. --[ 2.0 - Le temps a quelque chose a nous dire ----[ 2.1 Un peut d'histoire La detection d'emprunte et la detection NAT ont ete un sujet actif depuis un bon moment. Puisque vous lisez phrack, vous connaissez deja la detection d'emprunte via TCP/IP de Fyodor. Vous devriez aussi connaitre p0f ("passive of fingerprinting") par M. Zalewski. Avec la version 2, il a fait un outil merveilleux, introduisant une maniere intelligente de savoir si un hote utilise un mechanisme NAT en analysant les options TCP des paquets. Si vous etes interesses par cet outils (et vous devriez), lisez ce papier : "Dr. Jekyll had something to Hyde"[5]. En fait, la technique decrite ici est plus liee a p0f en le sens que, come p0f, elle peut etre totalement passive. Pour etre complet a propos de la detection NAT, je dois mentionner qu'AT&T on fait des recherches pour compter les hotes derriere du NAT[1]. Leur travail s'est concentre sur l'ID IP, en partant du fait que cette valeur est incrementee dans certains OS. En fait, ils parlent surtout des Windows qui incrementent les IP ID par 256 a chaque paquet. Decouvert par Antirez[7], Nmap[6] a utilise cette observation depuis longtemps (option -sI). Maintenant qu'on sait de quoi on va parler, il est temps de dire ce qu'on va en faire. ----[ 2.2 Et aujourd'hui ? Le NAT a ete invente pour contrer l'epuisement des adresses IP. Il a aussi ete utilise pour cacher plusieurs hotes derriere une adresse unique. L'option TCP timestamp[2] est mal geree par le traducteur d'adresses reseaux[3] (le fameux NAT - Network Address Translator). Autrement dit, meme se frotter au filtrage des paquets ne remplace pas l'option timestamp. Jusqu'a maintenant, cette propriete du NAT n'etait pas utile (du point de vue de la securite). C'est interessant de voire que cette option a deja ete utilisee pour devoiler des informations. Regardons maintenant brievement l'histoire de la securite du timestamp. ----[ 2.3 Retour au debut du timestamps Dans le passe, on utilisait le timestamp pour calculer l'uptime d'un PC[4]. Tout ceux qui ont essaye l'option de detection d'emprunte (-O) de Nmap on ete impressionnes par quelque chose dans ce genre : "Uptime 36.027 days (since Tue May 25 11:12:31 2004)". Bien sur, il n'y a pas de magie noir derriere tout ca, seulement deux faits : - Le temps ne marche en arriere que dans les films (desole les gars...). - Tous les systemes incrementent le timestamp toutes les n millisecondes. Donc, si vous connaissez l'OS, vous connaissez aussi la facon qu'il increpente le timestamp. Tout ce que vous devez faire pour connaitre l'uptime, c'est d'appliquer la formule de math trivial : timestamp / nombre_increment_oar_secondes = uptime en secondes Comme vous pouvez le voire, cette formule ne prend pas en compte les problemes des entiers. Ici, nous connaissons deux informations : le timestamp actuel, et le nombre d'increment par secondes. Ce ne peut etre fait que si nous connaissons le type d'OS. Voyons maintenant comment ameliorer la technique mais sans connaitre l'OS. ----[ 2.4 - Retour au college Souvenez-vous, il y a longtemps, au college, vous aviez entendu parler des fonctions affines. Un exemple de base : "y = Ax + B" Ou A est la pente et B, le point initial. Sa representation graphique est une droite. D'un point de vue du timestamp, on peut l'exprimer de la facon suivante : timestamp = numincbysec * secondes + nombre initial Quand vous faites de la detection d'emprunte, vous connaissez le timestamps et vous trouver le nombre d'increment par secondes (numincbysec) en cherchant l'OS. Maintenant, admettons qu'on ne peut pas chercher l'OS. Dans ce cas, vous ne connaissez ni la pente, ni l'uptime. Voici une autre maniere de connaitre la pente d'un OS. On doit recuperer le timestamp du PC deux fois. Nommons-les ts1 et ts2 et les temps (en secondes) auquel on les a recus t1 et t2. Avec ces informations, on peut trivialement trouver la pente puisque nous avons le systeme a deux equations : ts1 = A*s1 + B ts2 = A*s2 + B Qu'on resoud par l'equation suivante : ts1 - ts2 = A*(s1 - s2) <=> A = (ts1 - ts2) / (s1 - s2) Une application immediate de cette idee peut etre implementee dans un scanner actif : Demander deux fois le timestamps pour verifier que la pente calculee est la meme que la pente de reference. Ca peut etre utiliser pour contrer les outils anti-detection d'emprunte. Ca peut aussi etre utiliser comme technique solitaire de detection d'emprunte mais ne sera pas aussi juste que ceux bases sur TCP ou ICMP. Maintenant que la theorie est prete, revenons au NAT. ----[ 2.5 - Retour au NAT. Revenons au sujet du NAT. Puisque le NAT ne reecrit pas l'option timestamp, on peut compter les hotes derriere un NAT avec l'algorithme suivant : 1. Pour chaque hote deja decouvert, verifier que le paquet appartient a la meme droite. Chaque hote a une unique droite a moins qu'ils aient boote a la meme seconde. 2. Sinon, ajouter le paquet aux paquets non regroupes : un nouvel hote est decouvert. Regardez a la preuve de concept si ce n'est pas assez clair. Cet algorithme simple peut etre ameliore de plein de facons. Il a ete fait le plus simplement possible pour rester clair. Comme on le voit, l'option de timestamps peut etre utilisee pour compter les hotes derrieres du NAT de maniere efficace. Ca nous donnera aussi des informations sur les classes d'OS en presence. ----[ 2.6 - Faisons du PAT Le PAT ("Port Address Translation" - "redirecteur de ports" en francais) est utilise pour fournir un acces aux services d'une machine derriere du NAT. La question est de savoir quels ports sont rediriges ? En fait, le timestamps est encore notre amis. Si, pour deux ports differents, la pente est differente, alors, il y a un PAT et l'OS des deux machines est different. Si les droites sont differentes, l'OS est le meme mais pas le meme PC. Une autre utilisation interessante du PAT est le "round robin". Jusqu'a maintenant, il n'etait pas possible de savoir si u ntel mechanisme etait utilise. En comparant les different timestamps recoltes, on peut determiner le nombres d'hotes derriere un port. Ca peut etre une bonne fonctionnalite a ajouter a un scanneur actif. ----[ 2.7 - Il est temps de se defendre Puisqu'on utilise cette option pour trouver des informatons utiles, il y a quelques limitations a la technique. Principalement, les machines sous windows n'utilisent pas le timestamp quand elles initialisent une connection[8] a moins que vous l'activiez. Ca n'affecte que les analyses passives car si vous vous connectez en utilisant l'option timestamp a un windows, il l'utilisera aussi. D'ailleurs, certaines logiciels activent l'extension TCP dans windows. Pour etre complet, je dois mentionner que cette extension de TCP n'existe pas dans les windows 9X. Un autre probleme vient des temps d'attente. En mode passif, il peut y avoir desynchronisation entre les PC du aux PC ou au reseaux lui meme. Avec la preuve de concept, ce comportement peut arriver. Pour le gerer, vous devez ne plus vous baser sur l'horloge du PC mais sur les timestamps eux-meme. Que peut-on faire contre ca ? Puisque aucun vendeur excepter microsoft (1) (merci a Magnus) ne m'a repondu, la solution suivante n'est peut-etre pas possible. Voici une maniere theorique de pathcer le probleme : 1. Desactiver le timestamp TCP. C'est la pire solution puisque nous en avons besoin pour les raiseaux rapides[2]. 2. S'arranger pour que le NAT reecrive les timestamp et changer aussi les RFC pour NAT. 3. Changer les RFC pour specifier que l'option timestamp doit etreµ incrementee aleatoirement. Modifier chaque implementation pour propager ce changement. C'est une maniere propre de corriger le probleme puisque ce ne depend pas d'un systeme externe (le PC qui fait le NAT). J'ai essaye d'etre aussi complet que possible pour cette partie technique. La partie suivante sera plus "philosophique" puisqu'elle concerne plus les causes que les consequences. --[ 3 - L'histoire a quelque chose a nous dire Dans cette partie, je vais essayer de me concentrer sur la cause de ce bug et de ce qu'on peut en tirer. Ici, je ne parlerai pas de l'option timestamps elle-meme, mais sur l'interaction entre le timestamp et le mechanisme NAT. ----[ 3.1 - Quelle classe ? La premiere question est quel est ce bug ? Ce bug appartient a la classe des erreurs de conception. Pour etre plus precis, ce bug vient d'un probleme de chevauchement de specification de deux protocols. Le protocol IP a ete cree pour etre un protocole "un a un" : un client parle a un serveur. Le NAT viole cette specification en permettant des "multiples a un". En elle-meme, cette violation a cause tellement de problemes que j'en ai perdu le compte, mais c'est presque sur que le plus gros d'entre eux concerne le transfert FTP. Si vous utilisez FTP, vous voyez de quoi je parle (les autres peuvent regarder au tracage de connexion ftp). ----[ 3.2 - Mais d'ou vient-il ? Le probleme d'FTP est un bon exemple pour expliquer l'origine du probleme de chevauchement de specifications. FTP a ete cree pour fonctionner sur une connection fiable un a un (TCP en fait). Le NAT a ete cree pour modifier IP. A cause des dependences entre protocoles, ca a influence TCP et donc FTP. Pendant la specification de NAT, il n'a pas ete pris en compte que tous les protocoles dependant de IP pouvaient entrer e nconflit avec ces specifications modifiees. En verite, meme si les gens qui ont concu le mechanisme NAT avait voulu que tout les protocoles au dessus d'IP fonctionnent correctement avec NAT, ils n'auraient pas pu. Pourquoi ? Parce que les specifications sont dans les RFC et que ces RFC sont en anglais. L'anglais n'est pas une bonne maniere de specifier, surtout si vous avez un graphe de dependances dans vos specifications. Par exemple, beaucoup de langages de programmation ont des specifications formelles. Ce qui facilite les preuves. La raison de ce manque de formalisme dans les specification vient de l'histoire d'internet[9]. A ce moment la, ecrire un bon texte en anglais etait largement assez. De nos jours, ca peut etre tres problematique. ----[ 3.3 - Comment l'ai-je trouve ? La grosse question est, comment ai-je trouve ce bug ? En fait, j'ai trouve ce probleme en formalisant une partie des RFC de TCP et en confrontant le resultat avec une analyse de trace d'executions reelles. Mon analyser (2) m'a alerte qu'un timestamp etait plus petit que le precedant rencontre et comme vous le savez, le temps ne marche pas en arriere... J'ai cherche pourquoi et j'ai trouve le probleme. Ce qui est interessant ici, c'est que le point de depart dans la decouverte du bug est la specification au lieu de l'implementation (qui est plus courantes pour trouver les "buffer overflow" ("debordement de tableau" en francais) par exemple). I check out why and found this problem. What's interesting here is that the start point to find the bug is the specification rather than the implementation as it usually does to find a buffer overflow for example. ----[ 3.4 - Retour vers le futur Que va-t-il nous arriver maintenant ? En fait, de plus en plus d'erreurs de conception vont etre decouvertes car nous ne pouvont pas changer le passe et nous devons vivre avec. Ce ne serait pas raisonnable de dire que nous pourrions effacer toutes les applis au dessus de TCP et recommencer depuis le debut. Internet et les reseaux sont simplement trop gros pour pouvoir les faire bouger comme ca. Pensez simplement deux secondes au deploiment d'IP v6 et vous en serez convaincu. Tout ce qu'on peut faire, c'est d'etre aussi prudent que possible quand on concoit un nouveau protocol. Voire si notre nouvel appli n'entre pas en conflit avec les anciennes specifications et qu'elle ne casses pas les dependances. On peut aussi essayer de formaliser au maximum le protocole et essayer de detecter et corriger les erreurs avant qu'elle n'apparaissent. Appliquer betement les patch est la seule solution pour les prochaines annees. --[ 4.0 - Tirer des lecons du passe Le passe nous montre que les protocols ne sont pas assez bien specifies et menent a des erreurs (bugs, conflit, ...). Il est peut etre temps de changer nos habitudes et d'essayer quelque chose en adequation avec notre epoque. Par exemple, concevoir les choses avec toujours la securite a l'esprit. Dans cet article, j'ai essaye de vous montrer comment, simplement en comprennant les specification et avec l'aide de mathematiques de base, vous pouvez : - Trouver un grain de sable qui embete tout le monde. - Exploiter ce grain de maniere elegante avec une theorie toute simple. - Ajouter sa pierre au fingerprinting. J'espere que ca vous convaincra que la theorie et les outils formels sont une necessite en securite. La prochaine fois, je me concentrerai sur des outils formels simples pour trouver des bugs. J'espere que vous serez-la ;). --[ A Remerciements Tout d'abord, j'aimerais remercier Romain Bottier pour son aide et sa patience. Je remercie aussi Plops et Poluc de m'avoir rencontre. Regardez les mecs, on l'a fait ! J'aimerais insister sur le fait que je n'ai pas garde l'information pour moi. J'ai informer les grandes enseignes (Kernel.org, freeBSD, Cisco...) il y a un mois. Comme je l'ai dit, je n'ai recu aucun retour; je suppose donc qu'ils n'ont pas fait attention. References *=*=*=*=*= [1] AT&T Steven M. Bellovin. A Technique for Counting NATted Hosts http://www.research.att.com/~smb/papers/fnat.pdf [2] Jacobson, Braden, & Borman. RFC 1323 :TCP Extensions for High Performance . [3] K. Egevang, Cray Communications, P. Francis. RFC 1631 : The IP Network Address Translator (NAT). [4] Bret McDanel. TCP Timestamping - Obtaining System Uptime Remotely originally posted to Bugtraq Security Mailing List on March 11, 2001. [5] Michal Zalewski. p0f 2:Dr. Jekyll had something to Hyde. [6] Fyodor. Nmap - Free Security Scanner For Network Exploration & Security Audits. [7] Antirez. dumbscan original BUGTRAQ posting (18 Dec 1998) [8] Microsoft. TCP timestamp in windows : KB224829. [9] Hafner, Katie, Matthew Lyon. Where Wizards Stay Up Late: The Origins of the Internet. Post Scriptum *=*=*=*=*=*=*= (1) Le point de vue de Microsoft est que le NAT n'est pas un mechanisme de securite, ils ne compte pas faire de patch. (2) Si vous etes interesses par mon analyseur. J'espere publier prochainement un papier theorique sur son fonctionnement. J'espere sortir une version de l'outil un de ces jours. A la question "avez vous trouve d'autres choses interessantes", je repond que peut etre, je dois encore chercher plus profondement. --[ B - Preuve de concept /* * Proof Of Concept : counting host behind a NAT using timestamp * To compile this file, you will need the libpcap * Copyright Elie Bursztein (lupin@zonart.net) * Successfully compiled on FreeBSD 5.X and Linux 2.6.X * * $gcc natcount.c -o natcount -I/usr/local/include -L/usr/local/lib * -lpcap */ #define __USE_BSD 1 #include #include #include #include #ifdef __FreeBSD__ # include #endif /* __FreeBSD__ */ #ifdef __linux__ # include #endif /* __linux__ */ #include #include #include #include #include #include #include #include #include #include #ifdef __linux__ # define th_off doff #endif /* __linux__ */ u_int32_t addr = 0; /* chain lists structures */ typedef struct listes_s { struct listes_s *next; void *elt; } listes_t; /* Structures for TCP options */ typedef struct { u_int32_t ts, ts_r; } timestamp_t; typedef struct { timestamp_t *ts; } tcp_opt_t; /* Structures for datas storage */ typedef struct { u_int32_t from, first_timestamp; struct timeval first_seen; } machine_t; typedef struct { u_int32_t host, nat; struct timeval first_seen; } nat_box_t; #define TIMESTAMP_ERROR_MARGIN 0.5 #define DELAY 1 /* * List functions */ int add_in_list(listes_t **list, void * elt) { listes_t *lst; lst = malloc(sizeof (listes_t)); lst->next = *list; lst->elt = elt; *list = lst; return (1); } void show_nated(listes_t *list) { nat_box_t *nat; struct in_addr addr; printf("-- Begin of nated IP list --\n"); while (list) { nat = (nat_box_t *) list->elt; if (nat->nat > 1) { addr.s_addr = nat->host; printf("I've guess %i computers sharing the same IP address (%s)\n", nat->nat, inet_ntoa(addr)); } list = list->next; } printf("-- End of nated IP list --\n"); } /* * Function used to get all TCP options * Simple TCP options parser */ int tcp_option_parser(const u_char *options, tcp_opt_t *parsed, unsigned int size) { u_int8_t kind, len, i; bzero(parsed, sizeof(tcp_opt_t)); i = 0; kind = *(options + i); while (kind != 0) /* EO */ { switch (kind) { case 1: i++; break; /* NOP byte */ case 2: i += 4; break; case 3: i += 3; break; case 4: i += 2; break; case 5: /* skipping SACK options */ len = (*options + ++i) - 1; i += len; break; case 6: i += 6; break; case 7: i += 6; break; case 8: i += 2; parsed->ts = (timestamp_t *) (options + i); i += 8; return (1); break; default: i++; } kind = *(options + i); } return (0); } /* * Most interesting function ... Here we can know if a TCP packet is * coming from someone we already know ! * Algo : * finc (seconds) = current_packet_time - first_packet_time <- time * between 2 packets * ts_inc = inc_table[i] * finc <- our supposed timestamp increment * between 2 packets * new_ts = first_timestamp + ts_inc <- new = timestamp we should have * now ! * * Now we just have to compare new_ts with current timestamp * We can authorize an error margin of 0.5% * * Our inc_table contain timestamp increment per second for most * Operating System */ int already_seen(machine_t *mach, tcp_opt_t *opt, struct timeval temps) { int inc_table[4] = {2, 10, 100, 1000}; unsigned int new_ts; float finc, tmp, ts_inc; int i, diff; finc = ((temps.tv_sec - mach->first_seen.tv_sec) * 1000000. + (temps.tv_usec - mach->first_seen.tv_usec)) / 1000000.; for (i = 0; i < 4; i++) { ts_inc = inc_table[i] * finc; new_ts = ts_inc + mach->first_timestamp; diff = ntohl(opt->ts->ts) - new_ts; if (diff == 0) { /* Perfect shoot ! */ return (2); } tmp = 100. - (new_ts * 100. / ntohl(opt->ts->ts)); if (tmp < 0.) tmp *= -1.; if (tmp <= TIMESTAMP_ERROR_MARGIN) { /* Update timestamp and time */ mach->first_seen = temps; mach->first_timestamp = ntohl(opt->ts->ts); return (1); } } return (0); } /* * Simple function to check if an IP address is already in our list * If not, it's only a new connection */ int is_in_list(listes_t *lst, u_int32_t addr) { machine_t *mach; while (lst) { mach = (machine_t *) lst->elt; if (mach->from == addr) return (1); lst = lst->next; } return (0); } /* * This function should be call if a packet from an IP address have been * found, * is address is already in the list, but doesn't match any timestamp * value */ int update_nat(listes_t *list, u_int32_t addr) { nat_box_t *box; while (list) { box = (nat_box_t *) list->elt; if (box->host == addr) { box->nat++; return (1); } list = list->next; } return (0); } int check_host(listes_t **list, listes_t **nat, u_int32_t from, tcp_opt_t *opt, struct timeval temps) { listes_t *lst; machine_t *mach; int found, zaped; found = zaped = 0; lst = *list; while (lst && !(found)) { mach = (machine_t *) lst->elt; if (mach->from == from) { if ( temps.tv_sec - mach->first_seen.tv_sec > DELAY ) { found = already_seen(mach, opt, temps); } else zaped = 1; } lst = lst->next; } if (!(zaped) && !(found)) { mach = malloc(sizeof (machine_t)); mach->from = from; mach->first_seen = temps; mach->first_timestamp = ntohl(opt->ts->ts); add_in_list(list, mach); update_nat(*nat, from); show_nated(*nat); return (1); } return (0); } void callback_sniffer(u_char *useless, const struct pcap_pkthdr* pkthdr, const u_char *packet) { static listes_t *list_machines = 0; static listes_t *list_nat = 0; const struct ip *ip_h; const struct tcphdr *tcp_h; tcp_opt_t tcp_opt; machine_t *mach; nat_box_t *nat; struct in_addr my_addr; ip_h = (struct ip *) (packet + sizeof(struct ether_header)); if (ip_h->ip_p == IPPROTO_TCP) { tcp_h = (struct tcphdr *) (packet + sizeof(struct ether_header) + sizeof(struct ip)); if (tcp_h->th_off * 4 > 20) { if (tcp_option_parser((u_char *) (packet + sizeof(struct ether_header) + sizeof(struct ip) + sizeof(struct tcphdr)), &tcp_opt, tcp_h->th_off * 4 - 20)) { if (is_in_list(list_machines, (ip_h->ip_src).s_addr)) { check_host(&list_machines, &list_nat, (u_int32_t) (ip_h->ip_src).s_addr, &tcp_opt, pkthdr->ts); } else { if (ntohl(tcp_opt.ts->ts) != 0) { addr = (ip_h->ip_src).s_addr; my_addr.s_addr = addr; mach = malloc(sizeof (machine_t)); mach->from = (ip_h->ip_src).s_addr; mach->first_seen = pkthdr->ts; mach->first_timestamp = ntohl(tcp_opt.ts->ts); nat = malloc(sizeof (nat_box_t)); nat->host = (u_int32_t) (ip_h->ip_src).s_addr; nat->nat = 1; nat->first_seen = mach->first_seen; add_in_list(&list_machines, mach); add_in_list(&list_nat, nat); } } } } } } int main(int ac, char *argv[]) { pcap_t *sniff; char errbuf[PCAP_ERRBUF_SIZE]; struct bpf_program fp; char *device; bpf_u_int32 maskp, netp; struct in_addr my_ip_addr; char filter[250]; if (getuid() != 0) { printf("You must be root to use this tool.\n"); exit (2); } if (--ac != 1) { printf("Usage: ./natcount xl0\n"); return (1); } device = (++argv)[0]; pcap_lookupnet(device, &netp, &maskp, errbuf); my_ip_addr.s_addr = (u_int32_t) netp; printf("Using interface %s IP : %s\n", device, inet_ntoa(my_ip_addr)); if ((sniff = pcap_open_live(device, BUFSIZ, 1, 1000, errbuf)) == NULL) { printf("ERR: %s\n", errbuf); exit(1); } bzero(filter, 250); snprintf(filter, 250, "not src net %s", inet_ntoa(my_ip_addr)); if(pcap_compile(sniff,&fp, filter, 0, netp) == -1) { fprintf(stderr,"Error calling pcap_compile\n"); exit(1); } if(pcap_setfilter(sniff,&fp) == -1) { fprintf(stderr,"Error setting filter\n"); exit(1); } pcap_loop(sniff, -1, callback_sniffer, NULL); return (0); } |=-----------------------------=[ 0x03-3 ]=------------------------------=| |=---=[ All Hackers Need To Know About Elliptic Curve Cryptography ]=----=| |=-----------------------------------------------------------------------=| |=----------------------------=[ f86c9203 ]=-----------------------------=| ---[ Sommaire 0 - Resume 1 - Groupes algebriques et cryptographie 2 - Finite Fields, Especially Binary Ones 3 - Elliptic Curves and their Group Structure 4 - On the Security of Elliptic Curve Cryptography 5 - The ECIES Public Key Encryption Scheme 6 - The XTEA Block Cipher, CBC-MAC and Davies-Meyer Hashing 7 - Putting Everything Together: The Source Code 8 - Conclusion 9 - Outlook A - Appendix: Literature B - Appendix: Code ---[ 0 - Resume La cryptographie a clef publique a gagne beaucoup de populatite depuis sont invention il y a une trantaine d'annee. Les systemes de cryptographie asymetrique comme le chiffrement RSA, la signature RSA et l'echange de clef Diffie-Hellman (DH) sont beaucoup etudies et jouent un role fondamental dans les protocol de cryptographie modernes comme PGP, SSL, TLS, SSH. Les trois methodes decrite plus haut fonctionnent bien en pratique, mais ont un inconvenient majeur : les structures de donnees sont grandes, par exemple, les systemes de securite doivent gerer des entiers jusqu'a 2048 bits. Elles peuvent etre facilement geree par des PC modernes; a l'oppose, les systemes embarques, les PDA, et specifiquement les cartes a puce atteignent rapidement leur limites en puissance de calcul. Un deuxieme probleme, logiquement, est le fait que trasferer des entiers longs "gaspille" la bande passante. Sur 2048 bits, une signature RSA prends 256 octets; ce qui est beaucoup, surtout pour les reseaux a faible debit. Pour construire une alternative a RSA, DH et leurs cousins, la cryptographie par courbes elliptiques ("Elliptic Curve Cryptography" - "EEC") a ete inventee dans le milieu des annees 80. La theorie qui se cache derriere est tres compliquee et plus difficile que le calcul sur les entiers longs. C'est pourquoi on a mis du temps a les utiliser, bien que ses avantages sur les systemes cryptographiques classiques soient accablant : la taille des clef et les puissances de calcul necessaires sont plus petites (les systemes sur commencent avec des clefs de 160 bits). En fait, chaque fois que le processeur, la memoire et la bande passante sont des ressources critiques, la ECC est une bonne alternative a RSA et DH. Cet article a deux buts : 1. C'est une introduction a la theorie de la cryptographie par courbes elliptiques. Autant que les connaissances mathematiques, les aspects pratiques de l'implementation sont traites. 2. Il fournis un code pret a l'emploi. Le code C fournis et decrit dans l'article (presque 500 lignes au total) contient un systeme cryptographique a clef complet (incluant des composants symetriques : chiffrement par blocs, une fonction de hashage et un MAC) et appartient au domaine publique. Le code n'utilise pas de librairies externes, que ce soit bigint, cryptographic et autres; la glibc suffit. Il satisfait aussi la necessite typique des hacker pour les codes compacts et independant qui doivent fonctionner en environnement hostile; les rootkit et les backdoor ("portes derobees" en francais) pourraient les utiliser. Comme mentionne plus haut, la theorie derriere la cryptographie par EC est assez complexe. Pour garder cet article court et lisible par un hacker M. Toutlemonde, seul les importants resultats sont mentionnes, les theoremes ne sont pas prouves, certains details sont ommis. Si, par contre, vous etes matheux et voulez devenir expert en ECC, je vous encourage a lire [G2ECC] ou [ECIC]. ---[ 1 - Groupes algebriques et cryptographie Definition. Un ensemble G mini d'une operation G x G -> G ecrite '+' est appele un groupe (algebrique abelien) si les proprietes suivantes sont verifiees : G1. '+' est associatif et commutatif : (a + b) + c = a + (b + c) pour tout a,b,c dans G a + b = b + a pour tout a,b dans G G2. G contient un element neutre (nomme '0') tel que a + 0 = a = 0 + a pour tout a dans G G3. Tout element 'a' de G a un element "inverse" note '-a' tel que : a + (-a) = 0 Pour un groupe G, le nombre d'elements de G est appelle le cardinal et est ecrit |G|. Example. Les ensembles Z, Q et R (d'entier, ratioonnels et de reels respectivement) forment chaqu'un un groupe de cardinal infini quand on considere l'addition classique. Les ensembles Q* et R* (Q et R sans 0) sont aussi des groupes si on considere la multiplication (le neutre est ici '1' et 1/x est l'inverse de x). Definition. Soit G munis de '+' un groupe. Un sous ensemble H de G est appele sousgroupe de G si H munis de '+' est aussi un groupe. Example. Z est un sous groupe de Q, lui meme sous groupe de R (quand on les munis de l'addition). Si on considere la multiplication, Q* est sous groupe de R*. Theoreme (de Lagrange). Soit G un groupe de cardinal finis et H sous-groupe de G. Alors, |H| divise |G|. On en conclu que si |G| est premier, il contient seulement deux sous-groupes : {o} et lui meme. On dit que G est premier. On definis la "multiplication scalaire" d'un naturel k avec un element g d'un groupe comme suit : k * g := g + g + .. + g + g \____ k fois ____/ Theoreme. Pour un groupe finis G et un element g dans G, l'ensemble de tous les elements k*g (k est un naturel) forme un sousgroupe de G. Ce sousgroupe est appele "le sousgroupe cyclique genere par g". On en conclu qu'un groupe premier est genere par tous ses elements sauf 0. Nous allons introduire maintenant le protocole d'echange de clef Diffi-Hellman. Soit G un groupe premier et g un element different de 0. Soit deux participants appele Alice (A) et Bob (B). Ils se comporte comme suit : 1. Alice choisi un naturel aleatoire (secret) 'a' et calcul P = a * g et envoie G a bob. 2. Bob choisi un naturel aleatoire (secret) 'b', calcul Q = b * g et envoie Q a Alice. 3. Alice calcule S = a * Q = a * (b * g). 4. Bob calcul T = b * P = b * (a * g). Par definition de la multiplication scalaire, il est clair que S = T. Conclusion, apres l'etape 4, Alice et Bob possedent la meme valeur S. L'espionne Eve, qui a tout entendu de l'echange de P et de Q peut calculer S (et donc T) uniquement si elle connait 'a' ou 'b'. Ce probleme (trouver 'a' a partir de G, g et 'a * g') est appele le probleme de logarithme discret ("Discrete Logarithme Problem" - DLP). Dans les groupes ou le DLP est trop "difficile" pour etre resolvable en pratique, on estime qu'il est impossible a EVE (la mechante) de determiner S, et donc que Alice et Bob peuvent construire une clef secrete qui protegera leur prochaines communications. Par contre, si un attaquant intercepte les communications de P et Q et les remplace pas l'element neutre du groupe, il est clair qu'Alice et Bob obtiennent S = 0 = T comme clef. On doit considere ca comme un succes pour casser le systeme cryptographique. C'est pourquoi autant Alice que Bob doivent etre sur que P et Q ne sont pas neutre (genere bien tout le groupe de base). Le protocole d'echange DH presente ci-dessus peut aussi servir comme algorithme de chiffrement (appelle algorithme de chiffrement ELGamal) : Alice choisi un naturel aleatoire comme clef privee. L'element P = a * g est la clef publique correspondante. Si Bob veut lui ecrite un message, il choisi un naturel aleatoire 'b', chiffre le message avec la clef T = b * P et transmet le texte crypte plus le nombre Q = b * g pour Alice. Elle n'a plus qu'a reconstruire T avec Q et a (T = a * Q) et dechiffrer le message. Notez la relation directe entre cet algorithme et le protocole DH! Conclusion, les cryptographes sont toujours en train de chercher des groupes premier avec un DLP difficile. C'est ici que les courbes elliptiques entrent en jeux : elles introduisent des groupes algebriques, dont certains sont utiles pour les algorithmes DH et ELGamal. En plus, l'arithmetique sur les courbes elliptiques (l'addition, l'inverstion) est implementable efficacement. Vous trouverez plus d'information sur les groupes et leurs proprietes dans [Groups], [Lagrange], [CyclicGroups] et [GroupTheory]. Des details sur le DLP, l'echange de clef DH et le cryptage ELGamal se trouvent dans [DLP], [DH] et [ELGamal]. ---[ 2 - Corps finis et particulierement les binaires Definition. Un ensemble F muni des deux operations F x F -> F et nommees '+' et '*' est un corps si les proprietes suivantes sont verifiees : F1. (F, +) est un groupe commutatif F2. (F*, *) est un groupe (ou F* sans l'element neutre de la loi "+") F3. Pour tout a,b,c dans F, la loi de distributivite est verifiee : a * (b + c) = (a * b) + (a * c) [NDT : Dans la version anglaise, l'auteur utilise le terme "field" qui denote des corps commutatifs. Un corp est commutatif si en plus d'être un corps, sa deuxieme loi est commutative. En France (comme chez les anglophones), on sous-entend souvent qu'un corps est commutatif; la precision n'est faite que si le corps n'est pas commutatif. Dans la suite, le mot "corps" denotera de corps commutatifs. Notez que dans la suite, on ne considere que les corps finis, qui sont, eux, toujours commutatifs.] "a + (-b)" est reecrit "a - b", de meme "a / b" denote a multiplie par l'inverse de b. En d'autre termes, un corps est une structure munie de l'addition, la soustraction, la multiplication et la division qui fonctionne comme on est habitue avec les nombre courants. Exemple. Les ensembles Q et R sont des corps. Theoreme. Pour tout naturel m, il existe un corp finis GF(2^m) contenant exactement 2^m elements. Les corps de ce type sont appelles des corps binaires. Les elements des corps binaires GF(2^m) peuvent etre representes par des vecteurs de bits de longueur m. Chaque bits represente le coeficient d'un terme d'un polynome de degre < m a coeficient modulo 2. Pour additionner deux elements g et h de ces corps, on effectue l'addition de leurs polynomes respectifs (ce qui veut dire que l'addition est faite element par element, ou encore, on fait un XOR bits a bits des vecteurs). La multiplication est une multiplication polynomiale modulo un certain polynome p : l'element produit de g par h est le reste de la division (g * h) / p. Le fait que l'addition dans ces corps consiste juste en un XOR nous indique que chaque element est son propre inverse additif (aussi appele son opose), c'est a dire : a + a = 0 pout tout a dans F. En sonsequent, quels que soit a et b dans F, 2*a*b = a*b + a*b = 0. Ce qui nous mene a l'equation (surprenante au premier abord) : (a + b)^2 = a^2 + b^2 pour tout a et b dans F On peut trouver plus d'information sur les corps finis et leur arithmetique dans [FiniteField], [FieldTheory], [FieldTheoryGlossary] et plus particulierement [FieldArithmetic]. ---[ 3 - Les courbes elliptiques et leur structure de groupe Definition. Soit F un corps binaire et 'a' et 'b' deux de ses elements. L'ensemble E(a,b) contenant l'element 'o' (le point a l'infinis) plus toutes les paires (x,y) d'elements de F satisfaisant l'equation : y^2 + x*y = x^3 + a*x^2 + b est a appelle l'ensemble des points de la courbe elliptique binaire E(a,b). Theoreme. Soit E = E(a,b) l'ensemble des points d'une courbe elliptique binaire sur le corps F = GF(2^m). Alors 1. E contient approximativement 2^m elements. 2. Si (x,y) est un point de E (x et y satisfont l'equation ecrite plus haut), alors, le point (x,y+x) est aussi dans E. 3. Si deux points P (x1, y1) et Q = (x2, y2) de E avec x1 != x2 sont sur une même droite (dans le genre y = mx+b), alors, il y a exactement un troisieme point R (x3, y3) dans E qui est aussi sur cette droite. On en deduit une application f : (P,Q) -> R, parfois appellee l'application "courbes et tangeantes" ("chord-and-tangent mapping"). Exercice. Prouvez la deuxieme propriete. Cette application f est tres importante pour la structure de groupe donnee naturellement sur les courbes elliptiques : a) L'element bonus 'o' nous servira d'element neutre, qui, additionne a n'importe quel point n'a aucun effet. b) Pour tout point P = (x,y) sur la courbe, on definis le point inverse -P = (x,y+x). c) Pour tout points P = (x1,y1) et Q = (x2,y2), la somme 'P + Q' est definie par -f(P,Q). On pourrait montrer que E munis de cette loi d'addition et de l'element neutre 'o' est trivialement un groupe. Si les coefficients 'a' et 'b' sont choisis avec soins, il existe des points de E qui genere un sous-groupe de E premier pour lequel le DLP est difficile. Avec ces groupes, on peut construire des systemes cryptographiques surs. L'addition des points sur ces courbes dans le corps des reels (R) peut etre visualisee. allez voire [EllipticCurve] pour avoir de jolies images. Pour implementer les ECC, il est essentiel de disposer des operations d'addition, de doublement, d'inversion, ... Voici le pseudo-code pour les plus importantes de ces operations : Soit (x,y) un point de la courbe E(a,b). Le point (x'; y') := 2 * (x,y) peut etre calcule par : l = x + (y / x) x' = l^2 + l + a y' = x^2 + l*x' + x' return (x', y') Pour deux points P = (x1, y1), Q = (x2, y2) la somme (x3, y3) = P + Q peut etre calculee par l = (y2 + y1) / (x2 + x1) x3 = l^2 + l + x1 + x2 + a y3 = l(x1 + x3) + x3 + y1 return (x3, y3) Certains cas pathologiques ou on doit considerer les points a l'infinis ('o') n'ont pas ete expliques. Allez voir [PointArith] pour recuperer le pseudo code complet. Mais de toute facons, on voit que l'arithmetique est assez facile et expeditive a implementer. Une louche d'additions et de multiplications plus une petite division fait tres bien le travail. L'existance de fonctions pour calculer le doublement et l'addition est suffisante pour calculer efficacement la multiplication scalaire ; multiplier un point P par un naturel k. L'algorithme de doublement-et-somme fonctionne comme suit : H := 'o' Soit n le rang du plus haut bits a un de k while(n >= 0) { H = 2 * H; Si le nieme bit de k est a un H = H + P; n--; } return H; Example. Sopposons que nous voulons calculer k*P pour k = 11 = 1011b. Dans ce cas n est initialise a 3 et H est calcule comme : H = 2 * (2 * (2 * (2 * 'o' + P)) + P) + P = 2 * (2 * (2 * P) + P) + P = 2 * (5 * P) + P = 11 * P Certaines courbes elliptiques qui sont utiles pour la cryptographie ont ete stadardisees. Le NIST recommande 15 courbes (voire [NIST]), parmis lesquelles, 5 courbes binaires sont appelees B163, B233, B283, B409 et B571. Les parametres de la B163 sont les suivants ([NISTParams]): Corps : GF(2^163) Polynôme de reduction : p(t) = t^163 + t^7 + t^6 + t^3 + 1 Coefficient a : 1 Coefficient b : 20a601907b8c953ca1481eb10512f78744a3205fd coordonnee x de g : 3f0eba16286a2d57ea0991168d4994637e8343e36 coordonnee y de g : 0d51fbc6c71a0094fa2cdd545b11c5c0c797324f1 Cardinal du groupe : 2 * 5846006549323611672814742442876390689256843201587 La taille de ce corps est de 2^163, un systeme symmetrique sur equivalent ferait 80 bits (voire chapitre 4). Les elements du corps sont en hexadecimal, le cardinal de la courbe en decimal de la forme h * n, ou h (le "cofacteur") est petit et n est un grand nombre premier. Le point g est choisi pour que le sous-groupe genere par g soit de cardinal n. Le code source fournis dans l'article fonctionne avec la B163. Il peut etre facilement patche pour suporter tout autre courbe NIST; et pour cela, changer 6 lignes est suffisant. exercice. Essayer de patcher le code pour avoir un systeme cryptographique pour B409. Vous trouverez les parametres de cette courbe a [NISTParams]. Pour plus d'informations, lisez [EllipticCurve], [PointArith] et [DoubleAndAdd]. ---[ 4 - Sur la securite de la cryptographie par courbes elliptiques Nous avons vu que la securite de l'echange de clefs DH est base sur la difficulte du DLP du groupe considere. Des algorithmes sont connus pour trouver les logarithmes discrets dans n'importe quel groupe; pour cette tache, aucune meilleur complexite en temps n'est connue que celle de la methode de Pollard : "Rho Method" ([PollardRho]): Theoreme. Soit G un groupe finis (cyclique). Alors, il existe un algorithme qui resoud le DLP en approximativement racine(|G|) etapes (et peut de memoire utilisee). Pour les courbes elliptiques, aucun algorithme meilleur que celui decrit plus haut n'est connus. Il est donc considere que le ECCDLP est "completement exponentiel" vis-a-vis de la longueur binaire de |G|. RSA et les systemes classiques DH, a l'oppose, peuvent etre casse en temps "sousexponentiel". C'est pourquoi leur longueur de clef doivent etre plus longues qu'avec les ECC pour avoir un meme degre de securite. Nous avons deja vu que les courbes elliptiques sur GF(2^m) contiennent plus ou moins 2^m points. Le DLP peut donc etre resolu en racine(2^m) etapes, c'est a dire 2^(m/2). En conclusion, un systeme ECC de m-bits est equivalent, point de vue securite, a un systeme symetrique sur (m/2) bits. La table suivante compare les tailles de clef equivalentes pour divers systemes cryptographiques. clef ECC | clef RSA | clef DH | clef AES ----------+-----------+---------+---------- 160 | 1024 | 1024 | (80) 256 | 3072 | 3072 | 128 384 | 7680 | 7680 | 192 512 | 15360 | 15360 | 256 ---[ 5 - Le systeme de chiffrement a clef publique ECIES Plus tôt, nous avons presente l'echange de clef DH et le systeme cryptographique ElGamal construit au dessus. ECIES ("Elliptic Curve Integrated Encryption Scheme", voire ANSI X9.63) est une amelioration d'ElGamal construite specialement pour les groupes EC. ECIES fournis une mesure pour se defendre d'attaques actives comme celle presentee plus haut. Soit E une courbe elliptique de cardinal h * n avec n un grand nombre premier. Soit G le sous-groupe de E avec |G| = n. Choississont un point P de G different de 'o'. On commence par la generation de clef ECIES: Alice choisi comme clef privee un nombre aleatoire 'd' avec 1 <= d < n; Elle distribue le point Q := d * P comme clef publique. Si bob veut chiffre un message m pour Alice, il procede la maniere suivante : 1. Choisir un nombre aleatoire 'k' avec 1 <= k < n. 2. Calculer Z = h * k * Q. 3. Si Z = 'o', retour en 1. 4. Calculer R = k * P. 5. Calculer (k1, k2) = KDF(Z, R) (voire plus bas) 6. Chiffrer m avec la clef k1. 7. Calculer le MAC du texte chiffre en utilisant k2 comme clef MAC. 8. Transmettre R, le texte chiffre et le MAC a Alice. Alice dechiffre le texte en utilisant l'algorithme suivant : 1. Verifier que R est un point valide sur la courbe elliptique. 2. Calculer Z = h * d * R. 3. Verifier que Z != 'o'. 4. Calculer (k1, k2) = KDF(Z, R) (voire plus bas) 5. Verifier la validite du MAC en utilisant k2. 6. Dechiffre m en utilisant k1. Quand un test est rate, on rejette le message. KDF est la fonction de creation des clef symmetriques k1 et k2 a partir de pairs de points de la courbe elliptique. Considerez KDF comme une fonction de hash quelconque. ECIES fournis deux propriétés importantes : 1. Le fait qu'un attaquent injecte un point de la courbe qui ne genere pas un grand groupe (c'est ce qu'il se passe dans le cas mentionne plus haut), est detecte lors des etapes 2 et 3 du processus de dechiffrement (le cofacteur joue un role fondamentale a cet endroit). 2. Le message n'est pas simplement chiffre de maniere sure, il est aussi protege de la modification par le MAC. Exercice. Implementer un échange de clef DH. Soit E une courbe elliptique binaires d'ordre h * n. Soit G un sous-groupe de E avec |G| = n. Soit g un point de G different de 'o'. Alice et Bob agissent comme suit : 1. Alice choisi un nombre aleatoire 'a' avec 1 <= a < n et envoie P = a * g à Bob. 2. Bob choisi un nombre aleatoire 'b' tel que 1 <= b < a et envoie Q = b * g a Alice. 3. Alice verifie que Q est un point de la courbe qui genere un groupe de cardinal n (voire la fonction ECIES_public_key_validation routine). Alice calcule S = a * Q. 4. Bob verifie que P est un point de la courbe qui genere un groupe de cardinal n. Il calcul T = b * P. Si tout s'est bien passe, on doit avoir S = T. ---[ 6 - Chiffrement par blocs XTEA, hashage CBC-MAC et Davies-Meyer. XTEA est le nom d'un algorithme de chiffrement par blocs libre de droits inventé par Wheeler et Needham en 1997. La taille des blocs est de 64 bits, les clefs sont de 128 bits. Le principal avantage d'XTEA sur ses concurents AES, TwoFish, etc est la petitesse de son algorithme : void encipher(unsigned long m[], unsigned long key[]) { unsigned long sum = 0, delta = 0x9E3779B9; int i; for(i = 0; i < 32; i++) { m[0] += ((m[1] << 4 ^ m[1] >> 5) + m[1]) ^ (sum + key[sum & 3]); sum += delta; m[1] += ((m[0] << 4 ^ m[0] >> 5) + m[0]) ^ (sum + key[sum >> 11 & 3]); } } Soit E, une fonction symetrique de chiffrement par blocs de longueur n, initialises avec une clef k. Le CBC-MAC d'un message m est calcule comme suit : 1. Diviser m en des sous-messages de longueur n : m1, m2, m2, ... 2. Calculer les valeurs intermediaires t0 = E(length(m)), t1 = E(m1 XOR t0), t2 = E(m2 XOR t1), t3 = E(m3 XOR t2), ... 3. Retourner la derniere valeur obtenue en etape 2 en tant que MAC(k,m) et detruire les t0, t1, t2, ... Maintenant, nous allons voire comment utiliser un chiffrement par blocs pour construire une fonction cryptographique de hashage d'apres la methode de "Davies-Meyer". Soit m le message qu'il faut hasher. Soit E(clef,bloc) une fonction symetrique de chiffrement par blocs de longueur n avec une clef de longueur l. 1. Diviser m en sous-messages de taille l : m1, m2, m3, ... 2. Calculer les valeurs intermediaires h1 = E(m1, 0), h2 = E(m2, h1) XOR h1, h3 = E(m3, h2) XOR h2, ... 3. Si h est la derniere valeur obtenue en etape 2, retourner E(longueur(m),h) XOR h comme valeur et detruire les h1, h2, h3, ... Le code inclu dans cet article utilise le chiffrement par blocs XTEA en mode avec conteur (CTR) pour le chiffrement, un CBC-MAC garantis l'authenticite du message.; enfin, le KDF (voire chapitre 5) est implemente en utilisant XTEA e nmode Davies-Meyer. Lisez [XTEA] et [DMhashing] pour en aprendre plus sur le chiffrement par blocs XTEA et sur la methode Davies-Meyer. ---[ 7 - regrouper le tout ensemble : le code source Le code source du domaine publique que vous trouverez a la fin du document implemente le chiffrement par clef ECIES sur la courbe B163. Le code est commente mais nous allons souligner sa conception ici. 1. La structure centrale est un vecteur de bits de taille fixe mais "grande". C'est le type de base pour representer les ellements du corps et autres. Son nom de type est bitstr_t. Il existe des fonctions pour la manipulation, le decalage, le comptage des bits a partir de leur representations ASCII/HEX. 2. Les fonctions avec le prefixe "field_" effectue les operations arithmetiques : l'addition, la multiplication et le calcul d'un inverse multiplicatif sont les plus importantes d'entre elles. 3. Les points de l'ECC sont representes par des paires d'elem_t (un alias pour bitstr_t), le point a l'infini est la paire (0,0). Les fonctions prefixees par "point_" effectuent les operations de base sur la courbe elliptique : l'addition, le doublement, etc. 4. La fonction "point_mult" implemente l'algorithme de doublement-et-sommes pour calculer "k * (x,y)" de la facon decrite au chapitre 3. 5. Les fonctions prefixees par "XTEA" implementent le chiffrement par blocs XTEA mais aussi le CBC-MAC et la methode Davies-Meyer. 6. Les procedures en "ECIES_" sont relatices à ECIES. ECIES_generate_key_pair() genere une paire de clef privee/publique, ECIES_public_key_validation() verifie que le point fournis est bien sur la courbe et genere le groupe de cardinal "n". ECIES_encryption/ECIES_decryption font comme leur noms l'indique (chiffrement et dechiffrement). 7. Une demonstration des fonctionnalites principales d'ECIES est fournie dans la section main() du programme. Le code peut etre compile de la facon suivante : gcc -O2 -o ecc ecc.c ---[ 8 - Conclusion Nous avons vu comment les systemes cryptographiques sont construits au dessus des groupes algebriques qui ont certaines proprietes. Nous avons poursuivi en introduisant une classe de groupe appropriee et sa theorie, les courbes binaires elliptiques. Enfin, nous avons presente l'algorithme de chiffrement securise ECIES (avec certains composants symetriques). Tout ceci a ete implemente dans le code source inclu dans cet article. Nous rappelons qu'au dela de la securite, le but principal du code etait sa petitesse, et pas la vitesse en general. Des librairies specialisees sur la cryptographie sur les EC basees sur des fionctions sur les corps codees a la main en assembleur vont une centaine de fois plus vite que ce code. Si la petitesse n'est pas essentielle pour votre application, vous pouvez opter pour un des liens suivants vers des librairies de cryptographie sur ECC libres et performantes : Crypto++ (C++) http://www.eskimo.com/~weidai/cryptlib.html Mecca (C) http://point-at-infinity.org/mecca/ LibTomCrypt (C) http://libtomcrypt.org/ borZoi (C++/Java) http://dragongate-technologies.com/products.html ---[ 9 - Perspectives Vous avez appris beaucoup de choses sur les courbes elliptiques en lisant cet article, mais il reste un paquet d'idees non mentionnees. Nous presentons une listes d'entre elles ici : 1. Les courbes elliptiques peuvent etre definies sur d'autres corps que les corps binaires. Soit p un nombre premier et Z_p l'ensemble des entiers non negatifs plus petits que p. Alors, Z_p forme un corps finis (l'addition et la multiplications se font modulo p, voir [ModularArithmetic] et [FiniteField]). Pour ces corps, la courbe elliptique E(a,b) est definie comme l'ensemble des solutions de l'equation y^2 = x^3 + ax + b avec le point a l'infinis 'o' en plus. Bien sur, les fonctions d'addition et de doublement different de celles presentees plus haut, mais ces "courbes premieres" forment des groupes algebriques de la meme maniere que les courbes binaires. Elles fournissent simplement une autre classe de groupes pratique pour des buts cryptographiques. Le NIST recommende cinq courbes premieres: P192, P224, P256, P384 et P521. 2. Dans cet article, nous avons presente le protocol de chiffrement par clef ECIES. On se doit de mentionner que des protocoles de signatures bases sur ECC (voir [ECDSA]) et d'etablissement d'authentification de clefs ([MQV]) existent aussi. Leur implementations est laissee en exercice au lecteur. 3. Notre multiplication par doublement et somme est tres rudimentaire. De meilleurs implementations peuvent calculer "k * p" en la moitie de temps. Nous donnons juste une idee d'une premiere amelioration : Supposont que nous voulons calculer 15 * P pour un point de la courbe P. L'algorithme par doublement-et-somme le fait de la facon suivante : 15 * P = 2 * (2 * (2 * (2 * 'o' + P) + P) + P) + P Ce qui demande trois doublement et trois additions (les calculs sur 'o' ne sont pas pris en compte). Nous aurions pu calculer 15 * P de maniere plus intelligente : 15 * P = 16 * P - P = 2 * 2 * 2 * 2 * P - P Qui n'utilise que quatre doublements et une seule addition; on peut donc considerer que cette technique est plus performante que la methode standar de doublement-et-somme. En pratique, cette technique peut ameliorer la vitesse de la multiplication de 30%. Voir [NAF] pour plus d'informations sur ce sujet. 4. Dans l'implementation, l'operation la plus couteuse en temps est toujours l'inversion d'elements. Nous avons vu que l'addition et le doublement d'un point de la courbe necessitent tout les deux une division dans le corps. Voici un truc pour reduire le nombre de divisions lors d'un calcul de "k * P" en juste une seule division. L'idee est de representer les points de la courbe (x,y) comme des triplets (X,Y,Z) ou x = X/Z, y = Y/Z. Avec ces coordonnees homogenes, toutes les divisions dans le corps peuvent etre diferees vers la fin du calcul, ou elle seront faites en une seule fois Differents types de systems de coordonnees de type homogenes sont presentees dans [CoordSys]. ---[ A - Annexe : Bibliographie Il existe beaucoup de literature sur la cryptographie sur les courbes elliptique. Je recommande de commencer avec [G2ECC] et [ECIC]. D'autres bonnes references sont donnees dans [ECC]. Les courbes elliptiques et les protocoles cryptographique qui les utilisent ont ete standardisees par IEEE [P1363], ANSI (X9.62, X9.63) et SECG [SECG], pour n'en siter que quelques unes. Allez voire [Certicom] et [ECCPrimer] pour deux tutoriels sur l'ECC. La meilleur reference sur la cryptographie classique est [HAC]. [G2ECC] Hankerson, Menezes, Vanstone, "Guide to Elliptic Curve Cryptography", Springer-Verlag, 2004 http://www.cacr.math.uwaterloo.ca/ecc/ [ECIC] Blake, Seroussi, Smart, "Elliptic Curves in Cryptography", Cambridge University Press, 1999 http://www.cambridge.org/aus/catalogue/catalogue.asp?isbn=0521653746 [HAC] Menezes, Oorschot, Vanstone: "Handbook of Applied Cryptography", CRC Press, 1996, http://www.cacr.math.uwaterloo.ca/hac/ [Groups] http://en.wikipedia.org/wiki/Group_(mathematics) [Lagrange] http://en.wikipedia.org/wiki/Lagrange's_theorem [CyclicGroups] http://en.wikipedia.org/wiki/Cyclic_group [GroupTheory] http://en.wikipedia.org/wiki/Elementary_group_theory [DLP] http://en.wikipedia.org/wiki/Discrete_logarithm [DH] http://en.wikipedia.org/wiki/Diffie-Hellman [ElGamal] http://en.wikipedia.org/wiki/ElGamal_discrete_log_cryptosystem [AliceAndBob] http://en.wikipedia.org/wiki/Alice_and_Bob [FiniteField] http://en.wikipedia.org/wiki/Finite_field [FieldTheory] http://en.wikipedia.org/wiki/Field_theory_(mathematics) [FieldTheoryGlossary] http://en.wikipedia.org/wiki/Glossary_of_field_theory [FieldArithmetic] http://en.wikipedia.org/wiki/Finite_field_arithmetic [ModularArithmetic] http://en.wikipedia.org/wiki/Modular_arithmetic [ECC] http://en.wikipedia.org/wiki/Elliptic_curve_cryptography [EllipticCurve] http://en.wikipedia.org/wiki/Elliptic_curve [PointArith] http://wikisource.org/wiki/Binary_Curve_Affine_Coordinates [DoubleAndAdd] http://en.wikipedia.org/wiki/Exponentiation_by_squaring [NIST] http://csrc.nist.gov/CryptoToolkit/dss/ecdsa/NISTReCur.ps [NISTParams] http://wikisource.org/wiki/NIST_Binary_Curves_Parameters [PollardRho] http://en.wikipedia.org/wiki/ Pollard's_rho_algorithm_for_logarithms [XTEA] http://en.wikipedia.org/wiki/XTEA [DMhashing] http://en.wikipedia.org/wiki/Davies-Meyer_construction [ECDSA] http://en.wikipedia.org/wiki/Elliptic_Curve_DSA [MQV] http://en.wikipedia.org/wiki/MQV [NAF] http://en.wikipedia.org/wiki/Non-adjacent_form [CoordSys] http://wikisource.org/wiki/Wikisource:Cryptography [P1363] http://en.wikipedia.org/wiki/IEEE_P1363 [SECG] http://en.wikipedia.org/wiki/SECG [Certicom] http://www.certicom.com/index.php?action=ecc,ecc_tutorial [ECCPrimer] http://linuxdevices.com/articles/AT7211498192.html ---[ B - Appendix: Code $ cat ecc.c.uue begin 644 ecc.c M+RH@"B`@5&AI7!E('=I;&P@"D@ M+R`S,ET@/CX@*"AI9'@I("4@,S(I*2`F(#$I"B-D969I;F4@8FET2A!+"!"+"!S:7IE;V8H8FET2AH+"!!*3L@8FETF5O9BAB:71S=')?="DI*0H*:6YT(&)I='-T"LK.R!I*RLI.PH@(')E='5R;B!I M(#T]($Y535=/4D13.PI]"@H@("`@("`@("`@("`@("`@("`@("`@("`@("`@ M("`O*B!R971UF5I;F)I=',H8V]N"D*>PH@(&EN="!I.PH@('5I;G0S,E]T(&UA"`F(&UA"`K/2!.54U73U)$4RP@:2`](#`[(&D@/"!.54U73U)$4SL@:2LK+"!S M("L](#0I"B`@("`J+2UX(#T@0TA!4E,R24Y4*',I.PI]"@H@("`@("`@("`@ M("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@+RH@*')A=RD@ M97AP;W)T('1O(&$@8GET92!A2`J+PIV;VED(&)I='-T'!O"D*>PH@(&EN="!I.PH@(&9O'!O"`K/2!. M54U73U)$4RP@:2`](#`[(&D@/"!.54U73U)$4SL@:2LK+"!S("L](#@I"B`@ M("!S<')I;G1F*',L("(E,#AX(BP@*BTM>"D["GT*"B`@("`@("`@("`@("`@ M("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@+RH@:6UP;W)T M(&9R;VT@82!H97@@"P@8V]NPH@(&EN="!L96X["B`@:68@*"AS6VQE M;B`]('-TPH@("`@"D["B`@("`J>"`^/CT@,S(@ M+2`T("H@*&QE;B`E(#@I.PH@("`@F5O9BAE;&5M7W0I("T@-"D@*0H*:6YT(&9I M96QD7VES,2AC;VYS="!E;&5M7W0@>"D*>PH@(&EN="!I.PH@(&EF("@J>"LK M("$](#$I(')E='5R;B`P.PH@(&9OPH@(&EN="!I.PH@ M(&9OBLK(#T@*G@K M*R!>("IY*RL["GT*"B-D969I;F4@9FEE;&1?861D,2A!*2!-04-23R@@05LP M72!>/2`Q("D*"B`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@ M("`@("`@("`@("`@("`@("`@("\J(&9I96QD(&UU;'1I<&QI8V%T:6]N("HO M"G9O:60@9FEE;&1?;75L="AE;&5M7W0@>BP@8V]N2D[("HO"B`@8FET"D["B`@:68@ M*&)I='-T2P@,"DI"B`@("!B:71S=')?8V]P>2AZ+"!X*3L* M("!E;'-E"B`@("!B:71S=')?8VQE87(H>BD["B`@9F]R*&D@/2`Q.R!I(#P@ M1$5'4D5%.R!I*RLI('L*("`@(&9OBP@ M>BP@8BD["B`@?0I]"@IV;VED(&9I96QD7VEN=F5R="AE;&5M7W0@>BP@8V]N M"D["B`@8FET2D["B`@8FETBD["B`@=VAI;&4@*"$@9FEE;&1? M:7,Q*'4I*2!["B`@("!I(#T@8FETF5I;F)I=',H=2D@+2!B:71S M=')?PH@("`@("!B:71S M=')?BD[(&D@/2`M:3L*("`@ M('T*("`@(&)I='-T"P@>2D@*&)I='-T#(L('DR*2!-04-2 M3R@@8FET#$L('@R*3L@7`H@("`@("`@("`@("`@("`@("`@ M("`@("`@("`@("`@("`@("`@("`@("!B:71S=')?8V]P>2AY,2P@>3(I("D* M"B`@("`@("`@("`@("`@("`@("`@("`@("`@("\J(&-H96-K(&EF('E>,B`K M('@J>2`]('A>,R`K("IX7C(@*R!C;V5F9E]B(&AO;&1S("HO"FEN="!I"P@8V]NF5R;RAX+"!Y*2D* M("`@(')E='5R;B`Q.PH@(&9I96QD7VUU;'0H82P@>"P@>"D["B`@9FEE;&1? M;75L="AB+"!A+"!X*3L*("!F:65L9%]A9&0H82P@82P@8BD["B`@9FEE;&1? M861D*&$L(&$L(&-O969F7V(I.PH@(&9I96QD7VUU;'0H8BP@>2P@>2D["B`@ M9FEE;&1?861D*&$L(&$L(&(I.PH@(&9I96QD7VUU;'0H8BP@>"P@>2D["B`@ M2D@*B\*>PH@(&EF("@A(&)I='-TPH@("`@96QE;5]T(&$["B`@("!F:65L9%]I;G9E"D["B`@("!F:65L9%]M=6QT*&$L(&$L('DI.PH@("`@9FEE;&1?861D*&$L M(&$L('@I.PH@("`@9FEE;&1?;75L="AY+"!X+"!X*3L*("`@(&9I96QD7VUU M;'0H>"P@82P@82D["B`@("!F:65L9%]A9&0Q*&$I.R`@("`@("`@"B`@("!F M:65L9%]A9&0H>"P@>"P@82D["B`@("!F:65L9%]M=6QT*&$L(&$L('@I.PH@ M("`@9FEE;&1?861D*'DL('DL(&$I.PH@('T*("!E;'-E"B`@("!B:71S=')? M8VQE87(H>2D["GT*"B`@("`@("`@("`@("`@("`@("`O*B!A9&0@='=O('!O M:6YT#$L('DQ*2`Z/2`H>#$L('DQ*2`K("AX,BP@>3(I M("HO"G9O:60@<&]I;G1?861D*&5L96U?="!X,2P@96QE;5]T('DQ+"!C;VYS M="!E;&5M7W0@>#(L(&-O;G-T(&5L96U?="!Y,BD*>PH@(&EF("@A('!O:6YT M7VES7WIE#(L('DR*2D@>PH@("`@:68@*'!O:6YT7VES7WIE#$L M('DQ*2D*("`@("`@<&]I;G1?8V]P>2AX,2P@>3$L('@R+"!Y,BD["B`@("!E M;'-E('L*("`@("`@:68@*&)I='-T#(I*2!["@EI M9B`H8FET3$I.PH)96QS92`*"2`@<&]I;G1?#$L('DQ*3L*("`@ M("`@?0H@("`@("!E;'-E('L*"65L96U?="!A+"!B+"!C+"!D.PH)9FEE;&1? M861D*&$L('DQ+"!Y,BD["@EF:65L9%]A9&0H8BP@>#$L('@R*3L*"69I96QD M7VEN=F5R="AC+"!B*3L*"69I96QD7VUU;'0H8RP@8RP@82D["@EF:65L9%]M M=6QT*&0L(&,L(&,I.PH)9FEE;&1?861D*&0L(&0L(&,I.PH)9FEE;&1?861D M*&0L(&0L(&(I.PH)9FEE;&1?861D,2AD*3L*"69I96QD7V%D9"AX,2P@>#$L M(&0I.PH)9FEE;&1?;75L="AA+"!X,2P@8RD["@EF:65L9%]A9&0H82P@82P@ M9"D["@EF:65L9%]A9&0H>3$L('DQ+"!A*3L*"6)I='-T'!? M="!B87-E7V]R9&5R.PH*("`@("`@("`@("`@("`@("`@("`@("`@("\J('!O M:6YT(&UU;'1I<&QI8V%T:6]N('9I82!D;W5B;&4M86YD+6%D9"!A;&=O2P@8V]N M2AX+"!Y+"!8 M+"!9*3L*?0H*("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("\J(&1R M87<@82!R86YD;VT@=F%L=64@)V5X<"<@=VET:"`Q(#P](&5X<"`\(&X@*B\* M=F]I9"!G971?PH@(&-H87(@ M8G5F6S0@*B!.54U73U)$4UT["B`@:6YT(&9H+"!R+"!S.PH@(&1O('L*("`@ M(&EF("@H9F@@/2!O<&5N*$1%5E]204Y$3TTL($]?4D1/3DQ9*2D@/"`P*0H@ M("`@("!&051!3"A$159?4D%.1$]-*3L*("`@(&9O2`K(#`I.R!K6S%=(#T@0TA!4E,R24Y4*&ME>2`K M(#0I.PH@(&M;,ET@/2!#2$%24S))3E0H:V5Y("L@."D[(&M;,UT@/2!#2$%2 M4S))3E0H:V5Y("L@,3(I.PI]"@H@("`@("`@("`@("`@("`@("`@("`@("`@ M("`@("`@("`@("`@("`@("`@("`@("`@("`@("\J('1H92!85$5!(&)L;V-K M(&-I<&AE2`]($-(05)3 M,DE.5"AD871A*3L@>B`]($-(05)3,DE.5"AD871A("L@-"D["B`@9F]R*&D@ M/2`P.R!I(#P@,S([(&DK*RD@>PH@("`@>2`K/2`H*'H@/#P@-"!>('H@/CX@ M-2D@*R!Z*2!>("AS=6T@*R!K6W-U;2`F(#-=*3L*("`@('-U;2`K/2!D96QT M83L*("`@('H@*ST@*"AY(#P\(#0@7B!Y(#X^(#4I("L@>2D@7B`HF4@+3T@;&5N.PH@('T*?0H* M("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@ M("`@("`@("`O*B!C86QC=6QA=&4@=&AE($-"0R!-04,@*B\*=F]I9"!85$5! M7V-B8VUA8RAC:&%R("IM86,L(&-O;G-T(&-H87(@*F1A=&$L(&EN="!S:7IE M+"!C;VYS="!C:&%R("IK97DI"GL*("!U:6YT,S)?="!K6S1=.PH@(&EN="!L M96XL(&D["B`@6%1%05]I;FET7VME>2AK+"!K97DI.PH@($E.5#)#2$%24RAM M86,L(#`I.PH@($E.5#)#2$%24RAM86,@*R`T+"!S:7IE*3L*("!85$5!7V5N M8VEP:&5R7V)L;V-K*&UA8RP@:RD["B`@=VAI;&4HPH@("`@;&5N M(#T@34E.*#@L('-I>F4I.PH@("`@9F]R*&D@/2`P.R!I(#P@;&5N.R!I*RLI M"B`@("`@(&UA8UMI72!>/2`J9&%T82LK.PH@("`@6%1%05]E;F-I<&AE65R(&-O;G-T65R*&-H87(@*F]U="P@8V]N2!P86ER("HO"GL*("!C M:&%R(&)U9ELX("H@3E5-5T]21%,@*R`Q72P@*F)U9G!T"P@>2P@8F%S95]X+"!B87-E7WDI.PH@('!O:6YT7VUU;'0H>"P@ M>2P@:RD["B`@<')I;G1F*")(97)E(&ES('EO=7(@;F5W('!U8FQI8R]P2!P86ER.EQN(BD["B`@8FET"AB=68L('@I.R!P M5]V86QI9&%T:6]N M*&-O;G-T(&5L96U?="!0>"P@8V]N2D@?'P@(2!I"P@4'DI(#\@+3$@ M.B`Q.PI]"@H@("`@("`O*B!S86UE('1H:6YG+"!B=70@8VAE8VL@86QS;R!T M:&%T("A0>"Q0>2D@9V5N97)A=&5S(&$@9W)O=7`@;V8@;W)D97(@;B`J+PII M;G0@14-)15-?<'5B;&EC7VME>5]V86QI9&%T:6]N*&-O;G-T(&-H87(@*E!X M+"!C;VYS="!C:&%R("I0>2D*>PH@(&5L96U?="!X+"!Y.PH@(&EF("@H8FET M2P@4'DI M(#P@,"DI"B`@("!R971UF5R;RAX+"!Y*2`_(#$@.B`M,3L*?0H*=F]I9"!%0TE%4U]K9&8H M8VAA'!O2D["B`@8G5F6S$R("H@3E5-5T]21%-=(#T@,#L@6%1%05]D879I97-?;65Y M97(H:S$L(&)U9BP@8G5F65R*&LR("L@."P@8G5F+"!B M=69S:7IE("\@,38I.PI]"@HC9&5F:6YE($5#24537T]615)(14%$("@X("H@ M3E5-5T]21%,@*R`X*0H*("`@("`@("`@("`@("`@("`@+RH@14-)15,@96YC M7!T:6]N*&-H87(@*FUS9RP@8V]N2P@6G@L(%IY.PH@(&-H87(@:S%; M,39=+"!K,ELQ-ET["B`@97AP7W0@:SL*("!D;R!["B`@("!G971?"D["B`@("!B M:71S=')?<&%R"P@6GDI.R`@("`@("`@("`@("`@("`@ M("`@("`@("`@("\J(&-O9F%C=&]R(&@@/2`R(&]N($(Q-C,@*B\*("!]('=H M:6QE*'!O:6YT7VES7WIE2A2>"P@ M4GDL(&)A"P@8F%S95]Y*3L*("!P;VEN=%]M=6QT*%)X+"!2>2P@:RD[ M"B`@14-)15-?:V1F*&LQ+"!K,BP@6G@L(%)X+"!2>2D["@H@(&)I='-T'!O"D["B`@8FET7!T*&US9R`K(#@@*B!.54U73U)$4RP@ M;&5N+"!K,2D["B`@6%1%05]C8F-M86,H;7-G("L@."`J($Y535=/4D13("L@ M;&5N+"!M2D*>PH@(&5L96U?="!2>"P@4GDL M(%IX+"!:>3L*("!C:&%R(&LQ6S$V72P@:S);,39=+"!M86-;.%T["B`@97AP M7W0@9#L*("!B:71S=')?:6UP;W)T*%)X+"!M"P@4GDI(#P@,"D*("`@(')E M='5R;B`M,3L*("!B:71S=')?<&%R2D["B`@<&]I;G1? M8V]P>2A:>"P@6GDL(%)X+"!2>2D["B`@<&]I;G1?;75L="A:>"P@6GDL(&0I M.PH@('!O:6YT7V1O=6)L92A:>"P@6GDI.R`@("`@("`@("`@("`@("`@("`@ M("`@("`@("`@+RH@8V]F86-T;W(@:"`](#(@;VX@0C$V,R`J+PH@(&EF("AP M;VEN=%]I2DI"B`@("!R971U2D["B`@"B`@6%1%05]C8F-M86,H;6%C M+"!M2AT97AT+"!M'0L M(&-O;G-T(&-H87(@*G!U8FQI8U]X+`H)"0D)8V]N'0I("L@,3L*("!C:&%R("IE;F-R>7!T960@/2!M86QL;V,H;&5N("L@ M14-)15-?3U9%4DA%040I.PH@(&-H87(@*F1E8W)Y<'1E9"`](&UA;&QO8RAL M96XI.PH*("!P'0Z("5S7&XB+"!T97AT*3L*("!% M0TE%4U]E;F-R>7!T:6]N*&5N8W)Y<'1E9"P@=&5X="P@;&5N+"!P=6)L:6-? M>"P@<'5B;&EC7WDI.R`@("\J(&5N8W)Y<'1I;VX@*B\*"B`@:68@*$5#2453 M7V1E8W)Y<'1I;VXH9&5C7!T960L(&QE;BP@<')I=F%T M92D@/"`P*2`O*B!D96-R>7!T:6]N("HO"B`@("!P7!T:6]N+V1E8W)Y<'1I;VXZ("5S7&XB+"!D96-R>7!T960I.PH@(`H@(&9R M964H96YCR`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@ M("`@("`@("\J('1H92!C;V5F9FEC:65N=',@9F]R($(Q-C,@*B\*("!B:71S M=')?<&%R2P@(C@P,#`P,#`P,#`P,#`P,#`P,#`P,#`P,#`P,#`P M,#`P,#`P,#`P,&,Y(BD["B`@8FET2!P86ER("HO"@H@(&5N8W)Y<'1I;VY?9&5C7!T960B+`H)"0D@("`@("(Q8S4V9#,P,F-F-C0R83AE,6)A-&(T.&-C M-&9B93(X-#5E93,R9&-E-R(L(`H)"0D@("`@("(T-68T-F5B,S`S961F,F4V M,F8W-&)D-C@S-CAD.3