Za spolupráci na článku děkuji kolegům Lukáši Ondráčkovi a Vladimíru Čunátovi z CZ.NIC.
Tento vývoj je součástí projektu DNS4EU, kofinancovaného Evropskou unií1, jehož jsme hrdou součástí. K dosažení tohoto cíle do Knot Resolveru přidáváme dva nové mechanismy:
Za prvé implementujeme omezování četnosti (rate-limiting) dotazů, které přicházejí od stejného hostitele či sítě, pomocí efektivního mechanismu pro počítání dotazů. Tím zamezujeme i potenciálně částečně distribuovaným útokům.
Za druhé pracujeme na prioritizaci dotazů na základě měření využití procesorového času stráveného na zpracování požadavků, kde vyšší spotřeba procesoru do budoucna snižuje prioritu dotazů od konkrétních klientů tak, aby klienti, kteří server vytěžují, neomezovali klienty méně vytěžující.
Většina kódu, která v rámci tohoto projektu vznikla, je rovněž sdílena s autoritativním DNS serverem Knot DNS. Díky tomu mohou z této ochrany proti DoS útokům těžit uživatelé obou projektů. Jak je již s projekty od CZ.NIC zažitou tradicí, veškerý nový kód je svobodný a dostupný pod GPL licencí. Může do něj tedy kdokoliv nahlížet a adaptovat jej pro své vlastní použití.
V tomto příspěvku, který je volným pokračováním článku Novinky v Knot Resolver 6.x o novém Manageru a jeho fungování, si nejprve popíšeme základy rate-limitingu pro jednotlivé hostitele. Poté jej rozšíříme na celé sítě a přidáme další metody omezení. Nakonec se přesuneme k prioritizaci.
V tomto prvním díle se soustředíme na koncepční popis mechanismu z pohledu uživatele či operátora. Dopustíme se tak záměrně několika (viditelně popsaných) nepřesností za účelem zjednodušení tohoto vysokoúrovňového náhledu. Tyto nepřesnosti uvedeme na pravou míru v dalším článku, ve kterém se ponoříme do nízkoúrovňových detailů technického řešení rate-limitingu.
Popisované funkcionality plánujeme přidat letos do nadcházejícího vydání Knot Resolveru 6.
Omezování jednotlivých hostitelů, exponenciální pokles, okamžitý a dlouhodobý limit
Představme si, že pro každou adresu v adresních prostorech IPv6 a IPv4 máme čítač dotazů2. Pro každý požadavek přičteme jedničku čítači patřícímu jeho zdrojové adrese, dokud nepřesáhne svůj limit. Pokud limit přesáhneme, dotaz nebude řešen a buď na něj vůbec neodpovíme, nebo pošleme tzv. zkrácenou odpověď. Koncept zkrácených odpovědí si popíšeme v pozdější sekci, nejprve se zaměřme na funkci samotných čítačů.
Každou milisekundu se všechny čítače sníží o konstantní zlomek své hodnoty. Tomu říkáme exponenciální pokles3. Ten připomíná rozpad radioaktivních atomů, který je popisován svým poločasem rozpadu – v našem případě se jedná o čas, za který čítače klesnou na polovinu své původní hodnoty.
Chování čítačů popisujeme (a konfigurujeme) pomocí dvou parametrů, tzv. okamžitého a dlouhodobého limitu:
- Okamžitý limit (angl. instant limit, jak jej naleznete v kódu a v dokumentaci) nám říká, kolik dotazů se vejde do čítače za jednotku času (v našem případě za dobu jedné milisekundy), pokud měl čítač původně hodnotu nula; např. pro nového hostitele.
- Dlouhodobý limit (angl. rate limit, jak jej naleznete v kódu a v dokumentaci) je pak použit k odvození poločasu rozpadu čítače. Jedná se o maximální hodnotu frekvence dotazů (queries per second / QPS), které jsou posílány za delší časový úsek. Jinými slovy, pokud je průměrná frekvence dotazů vyšší než hodnota dlouhodobého limitu, je jisté, že čítač v nějakou chvíli narazí na okamžitý limit a dotazy budou blokovány.
Na následujícím grafu vidíme okamžitý limit LI, dlouhodobý limit LR a poločas rozpadu (half-life). Černá schodovitá čára reprezentuje snižující se hodnotu čítače (jeho zatížení – load) v čase poté, co byl naplněn (a uživatel byl omezen) a žádné další pro něj relevantní dotazy po naplnění nechodily. Všimněte si, že dlouhodobý limit LR se udává v dotazech za sekundu, ale v grafech je vždy dělen 1000, aby v nich byla vidět jeho hodnota za milisekundu, neboť taková je granularita měření v programu. Zároveň je nutno podotknout, že ve skutečnosti by hodnota LR byla o několik řádů menší (ale takový graf by byl nečitelný, takže používáme vyšší hodnoty, abychom mohli lépe ilustrovat chování čítače).
Řekněme, že na náš server zaútočí jeden nový hostitel. Zprvu odpovídáme na jeho dotazy až do okamžitého limitu; čítač se naplní. Poté blokujeme odpovědi, dokud se čítač dostatečně nesníží natolik, aby se do něj vešel další dotaz (nebo více dotazů). Odpovíme na to, co se vešlo, a poté blokujeme dále. V této druhé fázi se průměrný počet dotazů za sekundu řídí právě dlouhodobým limitem. V závislosti na tomto dlouhodobém limitu se tak může stát, že za jednu milisekundu odpovíme na několik dotazů, nebo naopak odpovíme pouze na jeden dotaz za několik milisekund.
Toto chování je ilustrováno dalším grafem, který ukazuje, jak se hodnota čítače vyvíjí pod útokem s konstantním počtem dotazů za sekundu QR v případě, že byla jeho hodnota původně nulová. Dotazy poslané v červených oblastech jsou blokovány. Abychom lépe ilustrovali chování za různých podmínek, měníme v animaci počet dotazů za sekundu QR, zatímco okamžitý limit LI i dlouhodobý limit LR zůstávají stejné.
Okamžitý limit má být konfigurován tak, aby nový klient dostal v krátkém čase odpovědi na takový počet dotazů, kolik je očekávané při jeho běžném chování. Dlouhodobý limit pak může být nastaven na nižší hodnotu, která říká, že přijímáme toto běžné chování jednou za několik sekund, nebo vyšší, pokud je náš server schopen jej obsluhovat rychleji. Tedy nastavujeme okamžitý limit podle očekávaného chování klientů a dlouhodobý limit podle výkonu našeho serveru.
Důležitou poznámkou je, že dlouhodobého limitu čítače dosáhnou pouze tehdy, jsou-li dotazy posílány pravidelně. To je způsobeno snižováním jejich hodnoty po zlomcích jejich aktuální hodnoty, tedy jejich pokles je vždy nejrychlejší, pokud byla hodnota těsně pod limitem. Počká-li klient nějakou chvíli po dosažení limitu, jeho čítač bude stále klesat, zároveň se ale klesání bude stále zpomalovat. Strategie posílání většího množství dotazů jednou za několik sekund tedy bude z dlouhodobého hlediska omezována striktněji než posílání dotazů po jednom v pravidelných časových intervalech.
Omezování sítí
Sledování dotazů (pouze) z jednotlivých IP adres by nefungovalo příliš dobře, obzvláště v IPv6, kde samostatný útočník může velmi snadno získat obrovské množství adres. Toto se obvykle řeší tak, že se vybere nějaká délka prefixů adres a omezuje se s takto pevně danou granularitou. To však umožňuje jednomu stroji vyplýtvat limit pro celý prefix (tedy potenciálně pro větší síť, jako je ISP). Jinými slovy, jediný potížista by mohl vyřadit službu celé síti i v případě, že by útočil jen z jedné adresy. Proto jsme zvolili komplexnější hierarchický přístup.
Namísto jedné pevné délky zvolíme délek prefixů více. Pro každou z takto vybraných délek pak zvolíme konstantu, kterou násobíme již nakonfigurované dlouhodobé a okamžité limity, které na prefixy dané délky aplikujeme. Pro každý požadavek pak zvedáme čítač všech (čtyř, nebo pěti – podle verze IP) prefixů adresy, ze které požadavek přišel, včetně celé adresy. Pokud by některý z čítačů měl přesáhnout svůj limit, nebude inkrementován žádný a dotaz je zablokován. Kratší prefixy tedy mají vyšší limity, jelikož reprezentují součet požadavků z větších sítí. Násobením jak okamžitého, tak dlouhodobého limitu stejnou konstantou ponecháváme poločas rozpadu na stejné hodnotě, což je žádoucí.
V současné době zvažujeme následující prefixy a násobitele:
IPv4 prefix | /32 | /24 | /20 | /18 |
---|---|---|---|---|
Násobitel | 1 | 32 | 256 | 768 |
IPv6 prefix | /128 | /64 | /56 | /48 | /32 |
---|---|---|---|---|---|
Násobitel | 1 | 2 | 3 | 4 | 64 |
Naši volbu prefixů a jejich násobitelů ovlivňuje mj. následující: – jednotlivé adresy – nezávisle na tom, zda jsou IPv6, nebo IPv4 – mají stejnou váhu, aby konfigurace byla co nejméně matoucí, – koncová síť v IPv6 má v praxi typicky délku prefixu mezi /64 a /48 (vizte politiku RIPE ohledně přiřazování prefixů koncovým uživatelům (v angličtině)). V případě IPv4 má koncová síť maximálně jednu adresu (délka /32), či dokonce se může za jednou adresou schovávat vícero sítí pomocí CGNAT. – Úroveň ISP/LIR: v IPv4 je nejmenší směrovatelný prefix /24 a kvůli nedostatku adres je adresní prostor velmi hustý a fragmentovaný. V IPv6 je situace velmi odlišná – každý LIR v RIPE dostane prefix o délce /32, nebo i kratší, pokud je třeba (vizte politiku RIPE o alokaci a přiřazování IPv6 adres (v angličtině)).
Na tomto místě bychom rádi poděkovali naší kolegyni Marii Matějce z týmu vyvíjejícího routovacího daemona BIRD za konzultaci těchto skutečností, zejména v oblasti IPv6.
Metody blokování dotazů, víceúrovňové omezování
Jak bylo již dříve zmíněno, máme dvě možnosti blokování dotazů. Můžeme je buď zcela zahodit, nebo na ně můžeme poslat jen minimální oříznutou odpověď, pomocí které jsme schopni ověřit klientovu autenticitu.
Nejprve se pojďme podívat na UDP dotazy a oříznuté odpovědi, které jsou existujícím mechanismem v DNS. DNS komunikace ve své výchozí podobě běžně probíhá přes rychlý, ale nespolehlivý protokol UDP. V případě, že by celá odpověď na dotaz byla příliš dlouhá pro přenos v UDP datagramu, je oříznuta a takzvaný TC bit je v ní nastaven na 1, čímž je klient požádán, aby dotaz položil znovu, ale tentokrát přes spolehlivý, ale zároveň výpočetně náročnější protokol TCP.
Důvod pro posílání takto oříznutých odpovědí při omezování provozu je následující: jednou z nevýhod DNS na protokolu UDP je jeho náchylnost na tzv. amplifikační útoky. Zjednodušeně řečeno, UDP klient snadno zfalšuje svou IP adresu, jelikož v UDP nedochází k žádnému handshake či jinému ověřujícímu procesu. To znamená, že útočníci mohou zneužít DNS servery k zahlcení strojů svých obětí relativně velkým objemem nevyžádaných UDP datagramů4.
Útočník tedy může zfalšovat svou IP adresu a přinutit náš server, aby tzv. amplifikoval útok směrem k dalšímu hostiteli. Pod takovým útokem se může stát, že bude přicházet velké množství falešných UDP požadavků a jen malé množství autentických. Zahazování všech by sice vyřešilo amplifikační útok, ale zároveň by narušilo službu pro autentické uživatele.
Alternativou je tedy posílání pouze krátkých UDP odpovědí označených TC bitem. Jelikož TCP vyžaduje handshake k navázání spojení, zdrojová adresa se tím ověří a efekt amplifikace se tím zníží, jelikož UDP pakety s odpověďmi od DNS serveru budou relativně malé. Lze také očekávat, že útočníci nebudou své požadavky přeposílat přes TCP, jelikož na něm amplifikační útok nefunguje.
To nás přivádí k důležitému zjištění: mohli jste si všimnout, že tímto dochází k určitému posunu ve významu rate-limitingu. Místo, aby DNS server využívající tento mechanismus chránil sám sebe, chrání ve skutečnosti ostatní účastníky na internetu před zahlcením jeho DNS odpověďmi.
Obě metody omezení (posílání zkrácených odpovědí a zahazování dotazů) můžeme kombinovat. Zkrácené odpovědi můžeme posílat pouze pevně určenému zlomku dotazů a zbytek můžeme zahazovat. Tento přístup je zvažován pro autoritativní Knot DNS.
Dalším přístupem je zavedení nižšího měkkého limitu (angl. soft limit) pro krátké odpovědi a ostrého limitu (angl. hard limit) pro zahazování. Měkký limit může být definován jako procento z okamžitého a dlouhodobého limitu, které jsou zavedeny jako limity ostré. Toto je přístup, který zvažujeme pro použití v Knot Resolveru.
Mezi měkkým a ostrým limitem je ještě jeden důležitý rozdíl. Aby bylo možné ostrého limitu dosáhnout, musíme hodnotu čítačů stále zvyšovat i v případě, že se dostanou přes měkký limit. To znamená, že pokud útočník posílá dostatek dotazů, aby dosáhl měkkého limitu, ale ne dost, aby dosáhl ostrého, všechny jeho dotazy budou zodpovězeny s nastaveným TC bitem. Na druhou stranu, jakmile jsou požadavky omezeny ostrým limitem, systém je již nepočítá, dokud čítač neklesne5, a tedy čas od času může přijít dotaz, který bude omezen opět jen měkkým limitem. Jinými slovy: ostrý limit – trochu paradoxně – pouze zpomaluje frekvenci odpovědí a čas od času některé dotazy propustí; zatímco měkký limit omezuje vše, dokud klient dostatečně nezpomalí své dotazování.
Tento rozdíl můžeme vidět v následujícím grafu. Je velmi podobný tomu předchozímu, ale kromě ostrých limitů LI a LR obsahuje také měkké limity L’I a L’R a oranžové oblasti značící čas, kdy byly dotazy omezeny měkkým limitem.
Pro dotazy přijaté přes TCP (vč. šifrovaných protokolů DNS-over-TLS a DNS-over-HTTPS) je dostačující použití pouze ostrého limitu, neboť zdrojová adresa je vždy autentická.6 Zvažujeme také, že Knot Resolver nebude tuto formu rate-limitingu na TCP aplikovat vůbec a namísto toho se u spojovaných protokolů spolehne na mechanismus prioritizace popsaný v následující sekci.
Různé ceny pro různé dotazy a prioritizace
Dosud jsme pracovali pouze s počty dotazů. Mezi jednotlivými druhy dotazů jsou však nezanedbatelné rozdíly ve využití CPU. Kupříkladu: vyřešení kešovaných dotazů přes UDP bude mnohem levnější, než vyřešení dotazů zatím nekešovaných a navíc třeba přes TLS.
Abychom tuto skutečnost mohli vzít v potaz, ponecháváme jednoduchý počítací mechanismus popisovaný výše a přidáváme prioritizaci dotazů, která započítává procesorový čas. Abychom mohli spotřebu zdrojů odhadovat s nějakou přesností, definujeme nové čítače pro hostitele a sítě velmi podobně jako v případě rate-limitingu, ale měříme procesorový čas strávený na jednotlivých dotazech a k čítačům přičítáme ten (namísto pouhé inkrementace o jedničku, jako je tomu u rate-limitingu). Čekání na odpovědi od autoritativních serverů přitom nezapočítáváme, jelikož Knot Resolver využívá asynchronního I/O a během čekání se může zabývat dalšími úlohami.
V tomto mechanismu nepoužíváme limity pro blokování. Namísto toho seskupujeme dotazy do několika úrovní priorit na základě hodnot čítačů jejich původců. Přiřazujeme tak nižší prioritu těm hostitelům/sítím, jejichž vytížení bylo v minulosti vysoké. Požadavky s nejvyšší prioritou jsou zpracovány okamžitě, zatímco jiné jsou zařazeny do několika front na základě úrovně a odloženy k pozdějšímu zpracování.
Konkrétní způsob práce s různými prefixy a určení, kdy se již požadavky nezabývat a zahodit je, protože jsou již příliš staré, je v současné době předmětem interních diskuzí. Zvažujeme také zahazování dotazů s nejnižší prioritou, když je server přetížený.
Příště nízkoúrovňová implementace
Zde zakončujeme první část Ochrany před DoS v Knot Resolveru 6.
Popsali jsme si koncept počítání a omezování dotazů, nejprve pro jednotlivé adresy, poté pro celé sítě. Pak jsme přimíchali vícero metod omezení, kdy jsme zjistili, že mechanismus rate-limitingu slouží k ochraně před DNS amplifikačními útoky.
V poslední sekci jsme se přesunuli k prioritizaci dotazů využívající modifikace mechanismu vyvinutého pro rate-limiting.
V příštím článku se zaměříme na nízkoúrovňovou implementaci celého mechanismu a objasníme si některé nepřesnosti, které jsme zde zanechali za účelem zjednodušení tohoto vysokoúrovňového pohledu.
- Project number: 101095329 21-EU-DIG-EU-DNS
Project name: DNS4EU and European DNS Shield.
This project is co-funded by the European Union.↩︎ - Velké zjednodušení! Takové množství čítačů je ve skutečnosti nemožné, protože bychom potenciálně potřebovali 232 čítačů pro IPv4 adresy a 2128 čítačů pro IPv6 adresy. I kdyby čítače byly jednobajtové (což nejsou), potřebovali bychom více paměti než je byť jen teoretické maximum 64bitových počítačů. Skutečně implementované technické řešení tohoto problému bude popsáno v dalším článku.↩︎
- V ideálním světě by exponenciálně ubývající čítače nikdy nedosáhly nuly, pouze by k ní v čase donekonečna konvergovaly. V počítačích toto samozřejmě není pravda. Čítače mají technicky vynucenou přesnost, takže v nějakou chvíli opravdu nabydou hodnoty nula, pakliže nějakou dobu nedorazí žádný dotaz, nicméně o tomto případu nemá valný smysl uvažovat. Pro většinu úvah je užitečnější předpokládat, že čítače jsou vždy nenulové, pokud nebyly právě inicializovány.↩︎
- Detailnější popis amplifikačního útoku v DNS od CloudFlare (v angličtině): https://www.cloudflare.com/learning/ddos/dns-amplification-ddos-attack/↩︎
- To je dáno i technickými omezeními, která budou blíže popsána v dalším článku.↩︎
- TC=1 navíc může být pouze v čistém UDP. Pro čisté UDP by tuto vlastnost přinesly také DNS Cookies (RFC 7873), ale v době psaní tohoto článku je podporuje pouze autoritativní Knot DNS a míra jejich použití ve světě DNS celkově je velmi nízká.↩︎
(Původně vyšlo na blogu sdružení CZ.NIC.)