Techniky skryté v p2p sieťach

Ondrej Mikle 26. 6. 2006

P2P siete samotné moc predstavovať netreba, zato niektoré technológie v nich použité sú dosť zaujímavé. V prvom dieli sa pozrieme hlavne rozličné techniky skryté v p2p sieťach určených na zdieľanie súborov, ktorými zaručujú vlastnosti ako integrita, konektivita, priepustnosť.

Úvod

Základnú podobu vnukol súčasným p2p sieťam asi Napster. Síce už pomerne dávno existovali p2p siete, ktoré dokázali distribuovať súbory – Usenet, Fidonet – dizajny dnešných vychádzajú skôr z Napstera. Z technologického hľadiska to bola sieť pomerne jednoduchá – myšlienka bola mať centrálny server, ktorý obsahoval informácie o umiestnení konkrétnych súborov a mnoho uzlov (koncových užívateľov), ktorí sa serveru najprv oznámili svoj zoznam súborov a neskôr sa dotazovali na súbory a vymieňali si ich medzi sebou. Súbory sa prenášali po častiach. Existencia centrálneho servera sa ukázala ako single point of failure, tj. stačilo zrušiť server a sieť sa viac-menej rozpadla.

Nasledovalo nasadenie neoficiálnych indexovacích serverov a ďalšie siete sa snažili vyhnúť zraniteľnosti jediného servera. To malo za následok (čiastočne) decentralizované siete, ktoré typicky používali viac indexovacích serverov (ed2k) alebo tzv. superuzly (Gnutella, FastTrack alias Kazaa), separované podsiete s jedným serverom – trackery (pôvodný BitTorrent).

V mini-seriáli o p2p sieťach si postupne prejdeme techniky overovania integrity, konektivity (týka sa účastníkov za NATom), spoľahlivosti proti výpadku určitých uzlov, presnosti a rýchlosti vyhľadávania. Predstavíme si aj spôsob šírenia dát iný ako klasický „rozdeľ súbor a pošli časti“. Nakoniec si predstavíme anonymné (pseudonymné) siete, ktoré z technologického hľadiska predstavujú asi najväčšiu výzvu.

Myslím, že vysvetľovať čitateľom roota základné znalosti o kryptografických hašovacích funkciách, ich účele a použití netreba, budú sa ale vyskytovať hojne. Pretože p2p sietí je skutočne veľmi veľa, nie je účelom tohto seriálu ich úplný a vyčerpávajúci popis, ale popísať niektoré zaujímavé techniky. Z rovnakého dôvodu sú niekedy tiež vynechané niektoré implementačné detaily.

Zaistenie integrity súborov

Integrita súborov je dosť dôležitá proti náhodným chybám, proti zámene súborov (meno neidentifikuje súbor jednoznačne) a proti zámerným útokom. Používa sa na to nejaký haš. FastTrack má zo všetkých asi najhorší algoritmus, UUHash, ktorý je síce rýchly, ale v mnohých prípadoch by nezabránil ani náhodnej chybe a je veľmi ľahko napadnuteľný. Jednoducho najprv zhašuje MD5 algoritmom prvých 300 kB a potom na hraniciach 1 MB, 2 MB, 4 MB, 8 MB, … zoberie ďalších 300 kB a pridá ich do hašu. O niečo lepšie je na tom ed2k, tam sa používa MD4 haš. MD4 je už síce prelomený natoľko, že k danému hašu je možné rýchlo nájsť nejaký blok, ktorý bude mať rovnaký haš. Noví klienti podporujú nové mechanizmy (AICH založené na SHA-1), dostaneme sa k tomu o chvíľu. Je ale aj dosť sietí, ktoré používajú kryptograficky silné haše, napr. SHA-1 v Kademlii a v BitTorrente.

Hašové zoznamy, Merklove hašové stromy

Samotné kryptografické hašovacie funkcie sa dajú použiť viacerými spôsobmi. Môžeme mať haš celého súboru, ale nevýhoda je, že ak po stiahnutí zistíme chybu, tak nevieme, kde nastala a musíme celý súbor stiahnuť znova. Najjednoduchšie riešenie je zoznam hašov – mať haš pre každú časť a po stiahnutí konkrétnej časti overiť. Tento postup používa napr. ed2k. Celkový haš súboru (ten čo sa vyskytuje v tzv. magnet linkoch), nie je v skutočnosti haš súboru, ale haš týchto čiastočných hašov. Okrem overenia samotného súboru má tento trik výhodu, že keď od servera (alebo niektorého klienta) získame tie čiastočné haše, môžeme overiť, že máme tie správne čiastočné haše.

Merklove hašové stromy sú rozšírením konceptu hašových zoznamov (viď obr. 1). Opäť, každý kus súboru je zhašovaný na čiastočné haše (na obrázku haš 0, .. haš 3). Zoberieme tieto čiastočné haše po dvojiciach ako idú za sebou a zhašujeme ich zreťazenie, dostaneme polovičný počet nových čiastočných hašov, napr. zhašovaním zreťazenia (haš 0 | haš 1) dostaneme haš 0–1, tie zase po dvoch zhašujeme, až kým neostane len jeden tzv. koreňový haš.

Merklov strom

Obrázok 1: Merklov hašový strom, žlté bloky sú samotné dátové bloky súboru, biele sú vypočítané haše

Výhoda hašových stromov oproti hašovým zoznamov spočíva v tom, že je možné deliť súbor na veľmi malé časti. To má za následok, že pri zistení chyby v nejakom bloku treba preniesť menej dát. V ľuvobolnom momente totiž netreba mať celý strom, keď treba zistiť len integritu určitého bloku. V prípade hašového zoznamu sme potrebovali na začiatku získať celý zoznam, aby sme overili, že jeho haš naozaj odpovedá celkovému hašu (tomu z magnet linku). V prípade našeho obrázka 1, keby sme chceli overiť haš bloku 0, potrebovali by sme získať haš 0–1, haš 2–3, haš 0 a haš 1. Potom by sme vedeli overiť, že z hašov 0–1 a 2–3 sedí koreňový haš a že z hašov 0 a 1 sedí haš 0–1, a teda môžme overiť haš bloku 0 oproti hašu 0. V prípade obrázka 1 zrovna žiadnu výhodu oproti hašovému zoznamu nezískame (musíme mať tak či tak na začiatku 4 haše). Prejavilo by sa to, ak by bol strom väčší, čo reálne býva. Klienti sietí DirectConnect a Gnutella klienti používajú Tiger-tree haš.

Inteligentné hľadanie chýb – algoritmy ICH a AICH

Niektorí klienti protokolu ed2k (eMule a aMule) používajú ešte inú techniku na zníženie počtu prenesených blokov – ICH (intelligent corruption handling). V protokole ed2k sú súbory delené na zhruba 9 MB veľké časti, z ktorých sa vytvorí už spomínaný hašový zoznam. Keď ale klient zistí, že niektorá časť je chybná, musel by znova prenášať celých 9 MB. Preto skúsi nasledovnú techniku: rozdelí ten 9 MB blok na 53 podblokov veľkosti 180kB. Skúsi najprv stiahnuť prvý 180kB podblok a spočíta haš bloku. Ak to nesedí, tak si skúsi stiahnuť ďalší 180 kB blok a znova spočíta haš bloku, atď. až kým nenarazí na chybný blok. Priemerne tak stiahne 50% menej než by musel, keby celý blok sťahoval znova (pri zjednodušenom predpoklade jedného chybného podbloku, ktorý sa vyskytuje na náhodnej pozícii s uniformným rozdelením).

V skutočnosti nie je naviac potrebné vždy počítať po stiahnutí každého podbloku haš celého 9 MB bloku znova, pretože MD4 je iteračná hašovacia funkcia (rovnako ako MDx, SHA-xxx, atď). To znamená, že je haš je možné počítať postupne, niekde zastať, a pokračovať ďalej. Pri každom zastavení je možné zistiť medzivýsledok. Jediná podmienka je, že to musí byť zarovnané na hranicu 16 bajtov. Klient pri opätovnom sťahovaní prvého podbloku spočíta čiastočný haš prvých 180 kB chybného bloku a po obdržaní nového podbloku spočíta čiastočný haš práve stiahnutého podbloku. Keď sú rovnaké, tak tam najskôr chyba nebola, tak sa v počítaní hašu chybného bloku posune o ďalších 180 kB a stiahne druhý podblok, tomu tiež spočíta haš a porovná, atď. Keď zistí nezrovnalosť v hašoch, len vtedy potrebuje dopočítať celý blok do konca, aby ho mohol porovnať s hašom bloku.

Druhý z algoritmov, AICH, znamená advanced intelligent corruption handling, ako ste si asi tipli podľa A na začiatku. Vylepšuje pôvodný ICH tak, že ho nahradí za hašový strom ;-) (použitá hašová funkcia je SHA-1). Pretože ale AICH stromy nie sú súčasťou ed2k protokolu a nie každý klient ich podporuje, nie vždy sa dajú použiť.

Samozrejme koreňový AICH haš sa líši od spomenutého „klasického“ MD4 ed2k hašu, ktorý je v magnet linkoch. Koreňový AICH haš môže, ale nemusí byť súčasťou magnet linku. Najčastejšie nastáva prípad, že nie je – to ale klient normálne nemôže overiť, či získaný AICH strom je správny. Rieši to tak, že sa skúša viacerých účastníkov pýtať (ktorí AICH podporujú), či ten AICH strom nemajú. Keď dostane strom aspoň od 10-tich a aspoň 92% stromov je rovnakých, prehlási, že strom je správny. Nie je to samozrejme 100% bezpečné, ale pre útočníka by to predstavovalo celkom problém. Naviac by to po stiahnutí kusu súboru klient zistil.

Ochrana proti „pijaviciam“ (leeching)

Celkom známym javom vo file-sharing p2p sieťach je leeching. Znamená to, že niektorý učastník len sťahuje, ale nedovoľuje iným účastníkom sťahovať od neho (v BitTorrent slangu ale leeching znamená proste sťahovanie). To jednak znižuje celkovú výkonnosť p2p siete a jednak nie je príliš čestné. Na niektorých spojeniach (ADSL) dochádza k tomuto javu sčasti kvôli parametrom pripojenia, kde downstream je rýchlejší ako upstream, ale stále sa nájde dosť ľudí, ktorí používajú programy typu NetLimiter na zníženie upstreamu. Iné veľmi bežné správanie je, že ľudia, ktorí určitý súbor dosťahujú, ho prestanú zdieľať.

Riešenia sú rôzne: v BitTorrent sieti môže byť klient dostať ban (jeho IP bude zakázaná), ak jeho pomer download:upload veľmi vychýli od pomeru 1:1. V ed2k sieti napr. eMule a aMule podporujú bodovanie – ak mi niekto pošle nejaké dáta, dostane určitý počet bodov. Podľa počtu bodov bude potom uprednostnený vo fronte ľudí, ktorí chcú odo mňa sťahovať – tým sa navzájom zvýhodňujú účastníci, ktorí naozaj zdieľajú. Výhoda tohoto prístupu je, že aj ten, kto neuploaduje, sa eventuálne dostane k dátam, ale oveľa neskôr ako tí, čo uploadujú. Ďalšia výhoda je, že účastník si body nemôže vynútiť, pretože nie sú uchovávané uňho, ale na protistrane. Toto je veľký rozdiel oproti FastTrack klientom, ktorí svoje body uchovávajú u seba a môžu podvádzať (táto dizajnová chyba spôsobila vznik klienta Kazaa Lite, ktorý si pridelí hneď maximum bodov). Nevýhody aMule/eMule bodovania sú dve: na začiatku dosť dlho trvá, kým sa účastník dostane na radu (hlavne v prípade zriedkavých súborov) a nie každý klient bodovanie podporuje – uploadovanie takým klientom nám nedáva žiadny bonus oproti pijaviciam.

Klienti aMule a eMule ešte limitujú maximálnu rýchlosť downloadu v závislosti na maximálnej rýchlosti uploadu (ak je príliš nízka), ktorú si užívateľ nastavil. Od nepriestrelného riešenia to má samozrejme ďaleko, pretože klient môže klamať, naviac sú obaja klienti open-source. V kóde je k limitovaniu možné nájsť komentár v zmysle: „Trocha tým limitujeme možnosť stať sa ‚zlým občanom‘, ale keďže sme open-source, aj tak si to hocikto môže zmeniť. Aj tak keby sa vyskytla modifikácia, ktorá toto zneužíva, tak takého klienta zabanujeme“.

Prekonávanie sieťových prekážok (NAT, firewall)

V dnešnom internete je mnoho počítačov skrytých za rozličnými NATmi a firewallmi. Ako určite viete, k počítaču za NATom sa bez predchádzajúceho nastavovania zvonka nepripojíte. Musí byť buď vytvorený tunel alebo použitá podobná technika. To je problém, ktorý musia všetky p2p siete riešiť (a nielen tie určené na zdieľanie súborov).

Relaying

Jedna možnosť je preposielať dáta klientov, čo sú schovaní za NATom, cez tzv. superuzly (má to rôzne názvy v rôznych sieťach: supernode, ultrapeer, atď). Ostatné uzly sa potom typicky nazývajú okrajové (edge-peers, ale mien je tiež niekoľko). Či sa daný uzol stane superuzlom, závisí od niekoľkých vecí, požaduje sa verejná IP (aby sa k nemu mohli iní pripojiť), nízka latencia, vysoká prenosová rýchlosť, rýchly procesor… Toto riešenie samozrejme funguje, jednoznačná nevýhoda sú nároky na výkon a šírku pásma. Napríklad Gnutella, FastTrack a Skype používajú relaying.

Obrátenie spojenia (connection reversal)

Ako názov napovedá, spojenie sa bude naväzovať v opačnom smere. Predpoklad je, že jeden účastník ma verejnú IP a chce sa spojiť s účastníkom, ktorý je za NATom. Účastník s verejnou IP požiada superuzol, nech doručí správu účastníkovi za NATom, že sa má pripojiť k danému uzlu siete (na určitú IP adresu a určitý port). Počítač za NATom teda vytvorí spojenie, aby od neho mohol počítač s verejnou IP žiadať nejaký súbor. Obrátenie spojenia sa často používa spolu s relayingom, aby nemuseli úplne všetky dáta putovať cez superuzly.

UDP hole punching

Vylučovacou metódou nám zostalo spojenie dvoch účastníkov, ktorí sú obaja za NATom. Na tento účel sa používa práve UDP hole punching (doslova sa prekopú diery do NATu/firewallu). Ako názov napovedá, funguje to pre UDP protokol (vďaka jeho bezstavovosti). Je to síce skôr hack, ale dokonca je to navrhnuté ako IETF draft. Na ilustráciu si popíšeme prípad, kde obaja účastníci sú za rozličnými NATmi. Ostatné prípady (obaja klienti za rovnakým NATom a obaja klienti za rozličnými NATmi schovanými za spoločným NATom) si môžte pozrieť v spomenutom IETF drafte. Na uskutočnenie treba ale ešte jedného „uvádzateľa“ (typicky je to nejaký superuzol). Situácia je na obrázku 2.

Hole punching

Obrázok 2: Klient A je schovaný za NATom A, klient B je schovaný za NATom B a obaja komunikujú so superuzlom cez ich NATy, ktoré majú verejnú IP

Predstavme si, že klient A chce nadviazať priame spojenie s klientom B. Ak by začal na NAT B na 66.17.120.4:20000 posielať nejaké pakety, tak budú zahodené. Využije ale fakt, že môže poslať klientovi B správu cez superuzol. Klient A sa najprv dozvie verejnú adresu klienta B od superuzlu. Nasledovne klient A začne posielať na verejnú adresu klienta B (66.17.120.4:20000) UDP pakety a zároveň požiada superuzol, nech klientovi B prepošle správu, že má začať posielať UDP pakety na verejnú adresu klienta A (81.22.38.7:30000). Keď klient A začne posielať pakety klientovi B na jeho verejnú adresu, NAT A si vytvorí novú session medzi privátnou adresou A a verejnou adresou B. Rovnako, keď klient B začne posielať pakety na verejnú adresu klienta A, NAT B si vytvorí novú session medzi privátnou adresou B a verejnou adresou A. Akonáhle je z oboch strán otvorená UDP session, A a B už nepotrebujú supernode na komunikáciu medzi sebou.

O metodě UDP hole punching jsme psali také v samostatném článku s názvem Přelez, přeskoč a podlez NAT, ve kterém popisujeme použití univerzálního programu nat-traverse.

Treba ešte ale poznamenať, že tento spôsob nefunguje so všetkými NATmi, veľmi závisí od toho, ako prideľujú čísla portov sessionom – na to, aby táto technika fungovala, je treba tzv. cone NAT. Podrobnejšie je podstata problému s rozličnými druhmi NATov rozobraná v uvedenom IETF drafte. Údajne je najviac práve tých „dobrých“ NATov, ktoré túto techniku podporujú, ale nie všetky.

Nabudúce

V nasledujúcej časti sa pozrieme na rôzne techniky vyhľadávania, porovnáme ich vlastnosti čo do presnosti, škálovateľnosti na veľký počet uzlov a odolnosti siete voči výpadku uzlov. Ukážeme si koncept distribuovanej hašovej tabuľky na príklade Kademlia algoritmu.

Anketa

Používáte P2P sítě?

Našli jste v článku chybu?
Vitalia.cz: Ženy, které milují příliš, jsou neštěstí

Ženy, které milují příliš, jsou neštěstí

Lupa.cz: Olympiáda zakázala GIFy. Moc to nepomáhá

Olympiáda zakázala GIFy. Moc to nepomáhá

DigiZone.cz: Sitcom Marta a Věra se vrací

Sitcom Marta a Věra se vrací

Podnikatel.cz: Kauza z Vinohrad pokračuje. Policie se omlouvá

Kauza z Vinohrad pokračuje. Policie se omlouvá

Podnikatel.cz: Týká se vás EET? Chtějte od berňáku posudek

Týká se vás EET? Chtějte od berňáku posudek

Měšec.cz: TEST: Vyzkoušeli jsme pražské taxikáře

TEST: Vyzkoušeli jsme pražské taxikáře

Podnikatel.cz: Pozor na vykuky, imitují služby České pošty

Pozor na vykuky, imitují služby České pošty

DigiZone.cz: Digi Slovakia: Eurosport 1 i 2 v HD

Digi Slovakia: Eurosport 1 i 2 v HD

Vitalia.cz: Vakcína Cervarix je oficiálně i pro chlapce

Vakcína Cervarix je oficiálně i pro chlapce

Lupa.cz: Samořídicí taxíky jsou tu. Začíná s nimi Uber

Samořídicí taxíky jsou tu. Začíná s nimi Uber

Měšec.cz: Do ostravské MHD bez jízdenky. Stačí karta

Do ostravské MHD bez jízdenky. Stačí karta

DigiZone.cz: ČTÚ červenec: rušení trochu vzrostlo

ČTÚ červenec: rušení trochu vzrostlo

DigiZone.cz: Hodlá Markíza skončit v DVB-T?

Hodlá Markíza skončit v DVB-T?

DigiZone.cz: E! a zákulisí turné Mariah Carey

E! a zákulisí turné Mariah Carey

Lupa.cz: Co najdete uvnitř kosmické sondy?

Co najdete uvnitř kosmické sondy?

Měšec.cz: Test: Výběry z bankomatů v cizině a kurzy

Test: Výběry z bankomatů v cizině a kurzy

Vitalia.cz: Galerie: Strouhanka ze starých rohlíků? Kdepak

Galerie: Strouhanka ze starých rohlíků? Kdepak

Lupa.cz: Kdo vykrádá LinkedIn? Zjistit to má soud

Kdo vykrádá LinkedIn? Zjistit to má soud

DigiZone.cz: Jetelín končí. Prima ho vyřadila

Jetelín končí. Prima ho vyřadila

Podnikatel.cz: OSA zdraží, ale taky přidá nový poplatek

OSA zdraží, ale taky přidá nový poplatek