Błąd w popularnym algorytmie kompresji istniał od 20 lat

W bardzo popularnym algorytmie kompresji LZO, używanym w wielu systemach i urządzeniach, odkryto błąd przepełnienia zmiennej, który istniał od roku 1994. Gdzie używany jest ten algorytm i jakie jest ryzyko zdalnego wykonania kodu?

Nagłówki w mediach krzyczą „20-letni błąd, który pojechał na Marsa„, czy jednak za odkryciem błędu idzie istotne ryzyko jego wykorzystania? Zdania są podzielone a temat wart jest analizy.

Kompresja sprzed 20 lat

Algorytm LZO powstał w roku 1994 i szybko zyskał dużą popularność dzięki dobrej wydajności – np. w procesie dekompresji był 4-5 razy szybszy od bzipa czy zliba. Przez 20 lat, pod postacią różnych wersji i implementacji, algorytm trafił do takich projektów jak OpenVPN, MPlayer2, Libav, FFmpeg, jądro Linux, Juniper Junos, MySQL a przy okazji także na pokład kilku sond marsjańskich. Ostatnia wersja algorytmu, LZ4, używana jest obecnie w systemach Solaris, Illumos czy FreeBSD. LZO również używany jest przez jądro Linux w systemach androidowych Samsunga i prawdopodobnie w setkach, jeśli nie tysiącach różnych otaczających nas urządzeń.

Sam algorytm doczekał się co najmniej 6 różnych, nieznacznie różniących się między sobą implementacji. Błąd znajdował się jednak tak głęboko w kluczowym algorytmie, że został powielony – chociaż czasem w lekko zmodyfikowanej formie – w każdej z nich.

Na czym polega błąd

Nie będziemy udawać, że rozumiemy cały wieloetapowy wywód z artykułu go opisującego (wnikliwym polecamy lekturę oryginału), ale w uproszczeniu problem zaczyna się z jedną ze zmiennych, która może rosnąć w sposób nieograniczony, by następnie trafić do funkcji, która nie sprawdzi jej rozmiaru. Wskutek tego jeden z warunków logicznych kontroli rozmiaru bufora funkcji może zostać spełniony mimo iż bufor przekroczy dozwolony rozmiar, powodując możliwość nadpisania fragmentu pamięci. W systemach 32-bitowych wystarczy do tego celu 16MB zer, wysłanych do przetworzenia przez funkcję dekompresji.

Fragment kodu, od którego zaczyna się problem

Wykorzystanie błędu wymaga spełnienia dodatkowych warunków, które mogą być różne dla różnych implementacji kodu i nie zawsze – nawet teoretycznie – musi prowadzić do zdalnego wykonania kodu. W większości przypadków skuteczne wywołanie błędu powinno przynajmniej skutkować atakiem odmowy usługi.

Kontrowersje

Don Bailey, który błąd opisał i zgłosił autorom wszystkich najważniejszych implementacji, twierdzi, że w wielu scenariuszach może dojść do zdalnego wykonania kodu. Z jego opinią nie zgadza się Yann Collet, autor LZ4, będącego wariantem LZO również podatnym na ten błąd.

Po pierwsze Yann wskazuje, że to nie Don Bailey odkrył błąd. Autorem odkrycia – ponad rok wcześniej – był Ludvig Strigeus, twórca uTorrenta. Ludvig nie wywołał jednak wokół swojego odkrycia takiej afery, ponieważ nie uznał błędu za poważne zagrożenie bezpieczeństwa. Jak podnosi Yann, by dokonać skutecznego ataku w systemie 32-bitowym, należy znaleźć implementację, która w jednym cyklu dekompresji będzie przetwarzała bufor o rozmiarze co najmniej 16MB. Nie może to być implementacja LZ4 zgodna z dokumentacją, ponieważ ta narzuca maksymalny rozmiar bufora 8MB. Do tego oczywiście możliwość wykorzystania błędu nie istnieje w systemach 64-bitowych, bo potrzebny byłby blok danych o niewyobrażalnym rozmiarze.

Yann wskazuje zatem, że w praktyce nie istnieje możliwość skutecznego ataku na LZ4. Na jego zarzuty Don odpowiada prowadząc potyczkę słowną wokół stosowanej terminologii (czy błąd wymagający bufora o rozmiarze miliardów terabajtów dalej można wykorzystać?), wskazuje także, że stworzył działającego w wielu architekturach exploita dla Mplayer2.

Podsumowanie

Wygląda zatem na to, że błąd faktycznie istnieje a jego wagę należy badać dla każdej implementacji osobno. Pomyślcie tylko o wszystkich antywirusach czy bramkach antyspamowych domyślnie rozpakowujących archiwa LZO/LRZ. Jeśli więc w Waszych projektach korzystacie z LZO/LZ4, to polecamy dokładne przyjrzenie się odpowiedniemu fragmentowi kodu zanim będzie za późno.