27.06.2014 | 15:14

Adam Haertle

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

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.

Powrót

Komentarze

  • 2014.06.27 15:21 Michal

    no i po co ta klotnia. nie ma POC niema bledu :) bedzie POC nie bedzie sie juz jak wytlumaczyc

    Odpowiedz
    • 2014.06.27 16:06 Przemek

      Ale sama informacja ciekawa. No trochę nie zgodzę się ze stwierdzeniem, że bez POC nie ma błędu.

      Odpowiedz
  • 2014.06.27 16:59 Cezar

    Od 1984 roku minęło 30, a nie 20 lat.

    Odpowiedz
    • 2014.06.27 17:30 Adam

      Dzięki, poprawione.

      Odpowiedz
  • 2014.06.30 22:34 adrb

    Zamiast tyle debatować, autorzy powinni rok temu dostawić jednego if-a sprawdzającego rozmiar bufora i zamknąć zgłoszenie ze statusem minor/fixed

    Odpowiedz
  • 2018.09.25 16:22 Władek

    Według mnie to może być niezły śmiech i zagwozdka.No bo weźmy teraz na wesoło. Poleciała sonda z tym niby „błędem” na Marsa lub jeszcze dalej. Teraz za lat… ( co najmniej „kilka”) przy czym jeden dzień u Pana Boga trwa tyle co na Ziemi jakieś …2000 lat. Jakaś cywilizacja znajdzie ten „softłer” :) i okaże się że będą zachodzić w głowę ” a dlaczego to działa skoro nie powinno?” tu nie chodzi o „kompromitacje ” przed Ufonautami którzy bedą moze analizować systemy tylko że taki błąd moze w przyszłości nas ochronić przed hipotetycznym cyber atakiem z Ich strony. No bo skoro ta sonda tak działała to abstrahując ich sposobem myslenia wirus aby nas rozwalić też będzie musiał miec nadpisane pliki! A takim czymś nie da sie rozłozyc nawet najprostszego systemu zabezpieczeń. Przepraszam że tak na wesoło ale mam dzisiaj wesoły dzień.

    Odpowiedz

Zostaw odpowiedź do Cezar

Jeśli chcesz zwrócić uwagę na literówkę lub inny błąd techniczny, zapraszamy do formularza kontaktowego. Reagujemy równie szybko.

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

Komentarze