Tag: algorytm

Opublikowane w

Guetzli – lepsza kompresja JPEG

Przedwczoraj Google ogłosiło na blogu nowe narzędzie do kompresji JPEG o nazwie Guetzli, wydawane na wolnej licencji (Apache License). Ma dawać lepsze optycznie rezultaty przy mniejszym rozmiarze wynikowym (mowa nawet o 35% mniejszych plikach). Cena? Oczywiście czas kompresji.

Postanowiłem przetestować na szybko, co mogło by się zmienić, gdybym wykorzystał grafiki skompresowane przy pomocy Guetzli na blogu. W tym celu sięgnąłem po obrazki z backupu bloga i uruchomiłem program (domyślne opcje kompilacji, domyślne ustawienia jakości, czyli 90%) na moim laptopie (CPU: Intel(R) Core(TM) i3 CPU M 380 @ 2.53GHz). Zdziwiło mnie to, że aż przy 12 plikach nie udało się ukończyć działania – program zgłosił błąd:

Invalid input JPEG fileGuetzli processing failed

Udało się przetworzyć 66 plików, całość trwała prawie 17 minut (sic!). Czyli jest bardzo wolno. Kompresor wykorzystywał tylko jeden rdzeń CPU. Efekty są obiecujące, zarówno wizualne, jaki i objętościowe. Mimo, że algorytm jest zaprojektowany z myślą o działaniu na możliwie nieprzetworzonych obrazach wejściowych, a te na blogu raczej są już zoptymalizowane, to łączny rozmiar udało się zmniejszyć o 14% (z ok. 3,3 MB do ok. 2,8 MB).

Jeśli wezmą się za wykorzystanie i optymalizację duże firmy, a jest na to szansa po uwolnieniu programu, może to oznaczać mniej przesyłanych danych po sieci, czyli szybsze ładowanie się stron, widoczne zwłaszcza na komórkach. Chwilowo główną barierą jest czas działania, który wygląda na zależny bezpośrednio od wielkości pliku wejściowego.

Zrobiłem jeszcze jeden test – plik JPG bezpośrednio z aparatu, rozmiar 2560×1440, rozmiar wejściowy 1,2 MB. Po kompresji (trwającej kilka minut) brak zauważalnych zmian jakości, natomiast rozmiar zmniejszony aż o 50% (614 kB).

Opublikowane w

Niebezpieczny świat.

Ostatnie wydarzenia coraz bardziej skłaniają mnie do – paranoicznego, przyznaję – wniosku, że żadne dane, niezależnie od tego jak zabezpieczane, nie są bezpieczne i prędzej czy później nastąpi ich ujawnienie. O ile tylko komuś będzie zależało.

Na początek – hasła. Niektóre portale, jak Allegro, trzymają hasła otwartym tekstem. Niezależnie od podjętych środków bezpieczeństwa, przy takim podejściu wyciek tych haseł jest IMHO kwestią czasu.

Wiele nie zmienia trzymanie skrótów (hashy) haseł. Ostatnio – poza małymi wyciekami polskimi typu JP – wyciekły hashe haseł z Gawkera i niesolone hashe haseł z FSF. To drugie jest wielką porażką, bo mówimy o środowisku z – teoretycznie – wysoką świadomością dotyczącą bezpieczeństwa i spraw technicznych, a tymczasem korzystano z najsłabszej funkcji skrótu i w najgorszym wydaniu. Powinno być najlepiej, było najgorzej. Klasyczne szewc bez butów chodzi.

Zresztą, pomału można zacząć stawiać znak równości między wyciekiem hashy haseł (zwł. niesolonych), a wyciekiem samych haseł – crackery MD5 są coraz szybsze. Co prawda to tylko benchmark, ale najnowsza wersja crackera whitepixel, który podobno jest chyba obecnie najszybszy, sprawdza 33 miliardy (nie miliony, miliardy) kombinacji na sekundę (dla pojedynczego hasha). Na potężnym, co prawda (4 dwurdzeniowe GPU; 1,2 kW poboru prądu przy obciążeniu, 2700 USD w tej chwili), ale pojedynczym komputerze PC.

Inne funkcje skrótu też nie są wiele lepsze. SHA1 to wg tego benchmarku w tym momencie 390 milionów kombinacji na sekundę, oczywiście na pojedynczej maszynie. A przecież bez problemu można mieć tych maszyn więcej, i to za niewielkie pieniądze.

Ale nie tylko haseł się to tyczy. Dane, które nie powinny ujrzeć światła dziennego wyciekły z „wewnętrznego”, rządowego systemu. Oczywiście mowa o wikileaksowym Cablegate. Swoją drogą ciekawe, jak długo w tych okolicznościach w stanie nieujawnionym pozostanie polisa Wikileaks (dead link)?

Głośno też było o rzekomym backdoorze w OpenBSD, a konkretniej IPSEC, który miało zamieścić FBI 10 lat temu (celowo nie linkuję, AFAIK rozeszło się po kościach i backdoora nie było, ale nie śledziłem). Co nie jest takie niemożliwe, bo korzystając z różnych „dziwnych” właściwości matematyki, da się zmusić algorytm szyfrujący, by „wyciekał” klucze. W mało zauważalny sposób – na przykład 128 bajt zaszyfrowanej wiadomości, przexorowany przez arbitralny klucz, będzie ujawniał klucz, którym była szyfrowana cała wiadomość. Albo coś na podobnej zasadzie – sky – i wiedza matematyczna – is the limit.

I raczej nie wierzę w to, żeby programista – czy użytkownik, który zwykle nie ma wielkiej wiedzy matematycznej/kryptograficznej, był w stanie coś takiego zauważyć. Przykład tego widać było przy dziurze w OpenSSL w Debianie. Efekt był dość spektakularny – do każdego konta umożliwiającego logowanie SSH po kluczach można się było dostać przy – IIRC – maksimum 65 tys. prób (bo tylko tyle różnych kluczy było generowanych). Na dowolnym systemie. O ile tylko klucz publiczny użytkownika był generowany na podatnym Debianie.

Niedowiarkom przykład ciekawych właściwości matematycznych można łatwo i zrozumiale zaprezentować na przykładzie listy 18 ulubionych filmów. Oto test (przetłumaczyłem na polski, z wyjtkiem tytułów, polecam IMDB):

Zrób test i dowiedz się, jaki film jest twoim ulubionym. Ten prosty matematyczny quiz przewiduje, który z 18 filmów spodoba ci się najbardziej. Nie pytaj w jaki sposób, ale to działa!

  • Wybierz cyfrę z zakresu 1-9.
  • Pomnóż ją przez 3.
  • Do wyniku dodaj 3.
  • Otrzymany wynik ponownie pomnóż przez 3.
  • Zsumuj obie cyfry otrzymanej liczby. Wynik to numer twojego przewidzianego ulubionego film na poniższej liście:

Lista filmów:

  1. Gone With The Wind
  2. E.T.
  3. Blazing Saddles
  4. Star Wars
  5. Forrest Gump
  6. The Good, The Bad, and the Ugly
  7. Jaws
  8. Grease
  9. The Joy of Anal Sex With A sheep
  10. Casablanca
  11. Jurassic Park
  12. Shrek
  13. Pirates of the Caribbean
  14. Titanic
  15. Raiders Of The Lost Ark
  16. Home Alone
  17. Mrs. Doubtfire
  18. Toy Story

W zasadzie koniec mijającego roku widzę trochę na zasadzie do kogóż to włamano się dzisiaj? I to tylko patrząc na najgłośniejsze i ujawnione sprawy i dziury (taki wariant minimum dla administratora – trochę wypada się w security orientować)…

Korzystając z okazji – bo to ostatni wpis, życzę wszystkim użytkownikom komputerów (ze specjalnym uwzględnieniem adminów) w nadchodzącym Nowym Roku mniej dziur bezpieczeństwa i awarii.

UPDATE: Paranoje dotyczące postępującej szybkości łamania hashy studzi ten wpis o przechowywaniu haseł. Polecam.

Opublikowane w

Security – ostatnie różności (zabezpieczenia moBILETu ponownie).

Wczorajszy dzień jakoś tak obfitował w wydarzenia związane z bezpieczeństwem, że postanowiłem to podsumować.

Po pierwsze, po dyskusji z netu na ten temat, postanowiłem się przyjrzeć moBILTowi. W sumie po raz kolejny bo i na zabezpieczenia patrzyłem (i to dwa razy). Przy dyskusji zeszło oczywiście na temat jak oni to sprawdzają (jak pisałem, sprawdzają źle) oraz jak mogą sprawdzać. Oczywiście najdoskonalsza wersja, to sprawdzenie online (odpytanie bazy o fakt skasowania danego biletu). Ponieważ twierdziłem, że jakby napisanie fake’owej aplikacji było proste (grafiki są – jak pisałem – dostępne, cudów tam nie ma, zwykła Java ME i trzy semi statyczne ekrany), to na pewno studenci (taki gatunek człowieka, co to nigdy kasy nie ma, dostęp do wiedzy i czas ma (chyba, że akurat pije, co mimo braku kasy zdarza się często, albo sesja), więc do skutecznego kombinowania pierwszy) by to zrobili. I że pewnie jest algorytm, który na podstawie cyfr/kodu z biletu pozwala zweryfikować prawdziwość biletu offline.

Nie ukrywam, że pozazdrościłem Niebezpiecznikowi opisu hackowania karty IKEI w celu dostania kawy, więc był czas, kawa, motywacja…

Bliższe przyjrzenie się ujawniło, że to, co brałem za QR code, to raczej Aztec code. Na dodatek odwrócone kolory ma (nie doczytałem, czy oryginalny Aztec na to pozwala, na wiki wszystkie są odwrotne). Ale Neoreader czyta to. Po przeczytaniu okazuje się, że twórcy nie ułatwili kontrolerom pracy – nie ma żadnego unikatowego ID zaszytego w tym kodzie. Jest tylko dokładny timestamp kasowania biletu. Opieram się wyłącznie na screenach dołączonych do instrukcji na stronie (dead link) – wyglądają na prawdziwe.

Niestety, inaczej niż w przypadku Niebezpiecznika, ludzie zawiedli. Apel na blipie pozostał może nie tyle bez odpowiedzi (odezwały się 2 osoby, z czego tylko jedna mogłaby pomóc), co bez danych. Pozostali znajomi nie odezwali się jak na razie z danymi, więc zostałem tylko ze swoimi danymi. Szybka analiza wykazuje, że są tak naprawdę 3 dane brane pod uwagę. Dokładny czas kasowania, numer ze strony pierwszej, bieżący numer ze strony drugiej i… tyle. Przy czym numer ze strony pierwszej jest stały (być może dla danego użytkownika, typu usługi, regionu) w trakcie jednego dnia. Natomiast bieżacy numer to po prostu inkrementowane ID w bazie (też nie wiem, czy dla danego typu usługi i regionu, czy transakcji globalnie, ale wiem, ile przyrasta dobowo).

Szybkie odświeżenie wiadomości z pracy magisterskiej i naklepanie prostego AG (algorytmu genetycznego) w Perlu nie przyniosło rezultatu w postaci znalezienia korelacji między datą danego dnia, a numerem ze strony pierwszej, choć na oko wygląda, że taka może istnieć (Perl i algorytm wolne i nie do końca przemyślane). Tak naprawdę czekam na więcej danych, w szczególności chcę porównać, czy dany numer jest stały dla wszystkich użytkowników (i usługi) w danym dniu. Jeśli jest, to ewidentny błąd twórców moBILETu – nawet jeśli nie ma algorytmu, to wystarczy, że jeden student skasuje bilet w danym dniu i przekaże numer innym. I nie da się zweryfikować offline, na podstawie sumy kontrolnej czy czegoś takiego, czy to autentyczny bilet…

Po drugie, za sprawą wpisu u Marcina Kasperskiego dowiedziałem się, że wbrew temu, co mówili sceptycy, słynną Nokię 1100 da się wykorzystać do przechwytywania SMSów z kodami jednorazowymi do transakcji. Czarny scenariusz się sprawdza – kody SMS nie są bezpieczne, istnieje metoda na oszukanie czytnika kart chipowych… Nadchodzą niedobre dni dla banków internetowych?

Po trzecie, atak phishingowy na Lucas Bank (dead link). Tu lekka lipa ze strony banku, bo korzystajac z formularza kontaktowego na stronie nie możemy wprost zgłosić takiego zdarzenia. Co więcej, wymagane jest podanie adresu email. A korzystając z tego formularza wyrażamy zgodę na przysyłanie spamu przez bank. Słowo kretyn w stosunku do osoby, która to wymyśliła nie oddaje w pełni tego, co chcę wyrazić…

UPDATE: Szybkie sprawdzenie z mobiletem kumpla pokazuje, że numer ze strony pierwszej jest stały w obrębie danego dnia dla wszystkich użytkowników (danej usługi, w danym regionie, kupujących dany typ biletu).