W naszym codziennym życiu coraz częściej spotykamy różne zautomatyzowane systemy weryfikujące uprawnienia. Wszystkie były projektowane przez ludzi, zatem warto czasem zweryfikować, czy ludzie ci nie popełnili prostych błędów.
Ron Reiter, programista i przedsiębiorca, opisał ciekawą analizę bezpieczeństwa kodów kreskowych uprawniających do darmowego parkowania. Pokazał w niej jak krok po kroku złamał algorytm tworzenia sumy kontrolnej i uzyskał możliwość darmowego parkowania.
Parkometry i sumy kontrolne
W miejscu, w którym Ron parkuje swój pojazd trzeba pobrać z parkomatu bilet parkingowy wyposażony w kod kreskowy. Pracodawca Rona wykupił od firmy zarządzającej parkingiem specjalne naklejki z dodatkowym kodem kreskowym który nakleja się na bilet parkingowy by otrzymać możliwość wyjazdu bez opłacenia postoju. Każda z takich naklejek ma wartość ok. 10 dolarów, zatem Ron z ciekawości przyjrzał się zamieszczonym na nim kodom.
Przykładowe kody kreskowe
Po zeskanowaniu sporej partii kodów z naklejek można było zauważyć wyraźną prawidłowość. Ich seria wyglądała następująco:
03001909 0788 03001910 0956 03001919 0642 03001946 0642 03001920 0810 03001921 0664 03001922 0518 03001923 0372 03001932 0372 03001933 0226 03001934 0080 03001935 0934 03001947 0496
Jak pewnie widzicie, numery kodów są liczbami całkowitymi z wąskiego przedziału wartości a po nich występuje czterocyfrowa suma kontrolna. Wygląda zatem na to, że wystarczy odtworzyć mechanizm tworzenia sumy kontrolnej by móc generować własne prawidłowe wartości. Jeśli lubicie wyzwania to możecie spróbować sami sprostać temu zadaniu – jeśli jednak wolicie szybkie odpowiedzi, to czytajcie dalej.
W puli kodów znaleźć można dwie pary wartości posiadających tę samą sumę kontrolną – to wskazówka dająca duże nadzieje na sukces. Tę samą wartość 0372 dają liczby 03001923 oraz
03001932. Różnią się one tylko kolejnością cyfr, co oznacza, że algorytm sumy kontrolnej najwyraźniej jest niezależny od kolejności występowania cyfr w liczbie. Takie właściwości ma dodawanie oraz operacje bramki logicznej. Spójrzmy teraz na drugą parę wartości, które dają wspólny wynik 0642. Są to 03001919 oraz 03001946. Różnią się one tylko dwoma ostatnimi cyframi – 19 i 46. Ich wspólną cechą jest suma, co sugeruje, że to dodawanie cyfr jest pierwszym krokiem algorytmu obliczania sumy kontrolnej.
Przyjrzyjmy się teraz wartościom, jakie przyjmuje suma kontrolna. Wszystkie zaobserwowane stany znajdują się w przedziale 000-999. Biorąc pod uwagę najpopularniejsze mechanizmy zapewnienia takiego wyniku możemy roboczo założyć, że używana jest reszta z dzielenia przez 1000. Możemy zatem teraz poszukać brakujących wartości przyjmując założenie, że algorytm wygląda tak: weź sumę cyfr, pomnóż przez x, podziel przez 1000 i weź resztę z tego dzielenia. Trzeba zatem znaleźć x.
Weźmy na przykład 03001919 0642. Suma cyfr liczby z lewej strony to 23. Suma kontrolna to 642. 642 musi być zatem resztą z dzielenia wyniku 23*x przez 1000.
642/23 = 27.913043478
Niestety nie otrzymujemy liczby całkowitej, zatem trzeba szukać dalej. Reszta z dzielenia przez 1000 to ostatnie 3 cyfry, zatem spróbujmy odgadnąć, jakie poprzedzają je wartości:
1642/23 = 71.391304348 2642/23 = 114.869565217 ... 18642/23 = 810.52173913 19642/23 = 854
Zdecydowanie 854 wygląda na najlepszego kandydata. Zweryfikujmy zatem hipotezę dla ciągu 03001947 0496:
(3+1+9+4+7)*854 = 24*854 = 20496
W ten oto prosty sposób Ron uzyskał możliwość generowania prawidłowych kodów kreskowych w systemie parkingowym. Z możliwości podobno nie skorzystał – oprócz względów etycznych na jego decyzję mógł mieć wpływ fakt, że rejestracje pojazdów korzystających z parkingu są automatycznie zapisywane i kojarzone z konkretnym biletem parkingowym…
Ćwiczenie
Rozejrzyjcie się wokół siebie i sprawdźcie, czy nie macie pod ręką podobnych kodów kreskowych uprawniających do uzyskania dowolnych korzyści – może to Wy będziecie bohaterami kolejnego artykułu na ten temat.
Komentarze
„Takie właściwości ma dodawania oraz operacje bramki logicznej.” Nie bardzo rozumiem to zdanie…
Zarówno dodawanie, jak i operacje logiczne, dają identyczny wynik niezależnie od kolejności składników.
Wszystko fajnie, artykuł bardzo ciekawy, tylko skąd się wzięły te informacje?
„Biorąc pod uwagę najpopularniejsze mechanizmy zapewnienia takiego wyniku możemy roboczo założyć, że używana jest reszta z dzielenia przez 1000. Możemy zatem teraz poszukać brakujących wartości przyjmując założenie, że algorytm wygląda tak: weź sumę cyfr, pomnóż przez x, podziel przez 1000 i weź resztę z tego dzielenia. Trzeba zatem znaleźć x.”
Zawsze ciekawiły mnie metody generowania kodów, ale tutaj pojawia się informacja, która wygląda jak wzór na hakowanie, a przecież to nie jest tak proste jak wzór na pole koła.
Podstawy kryptografii asymetrycznej, gdzie reszta z dzielenia jest świetnym podstawowym przykładem.
Kiedyś doładowania prepaid do sim plusa były tak generowane, że połowa cyfr była z numeru seryjnego zdrapki.
Myślę, że artykuł ma trochę niewłaściwy tytuł :). Nie było to łamanie kodu jako takiego a jedynie wykrycie luki bezpieczeństwa niewłaściwie zaprojektowanego _systemu_ parkingowego.
System zresztą wcale nie był górnolotny skoro brak było bazy autoryzowanych kart/biletów a jedynie jakiś mikrokontroler wyliczał, czy suma kontrolna się zgadza…
Błąd polegał na zbytnim zaufaniu do jawnego i reprodukowalnego nośnika jakim jest kod kreskowy.
Nadchodzą święta Bożego Narodzenia. Wiele sklepów internetowych ma promocje. Trzeba jednak podać kod. Proponuję poeksperymentować i w pole na kod wpisać ŚWIĘTA2015. Lub podobne hasła kojarzące się z tymi świętami.
Przed minioną Wielkanocą kupiłem tak okulary 25% taniej.
Już ktoś zwrócił uwagę na zdanie „Takie właściwości ma dodawanie oraz operacje bramki logicznej.” ale pozwolę sobie raz jeszcze się przyczepić. Co to są „operacje bramki logicznej” w kontekście matematyki? Ja rozumiem, że ostatnio matematyka jest w odwrocie i program szkolny dramatycznie został przycięty a i nauczyciele nie mają pojęcia co i jak ale środowisko IT powinno jakiś poziom trzymać. Mówimy tu o podstawach matematyki a nie o zagadnieniach zaawansowanych, więc warto dopilnować terminologii.
Chętnie się czegoś przy okazji nauczę – zaproponuj proszę prawidłowe brzmienie tego zdania.
W cytowanym zdaniu lepiej pasuje „działanie logiczne” (lub funkcja logiczna). Finalnie może on brzmieć – takie właściwości ma dodawanie oraz niektóre działania logiczne. Pozostaje jeszcze kwestia dodawania, które warto zastąpić „sumą” ale to już kosmetyka.
zapewne co działo o matematykę dyskretną. zręcznie chyba napisać „takie własności mają opacje arytmetyczne i logiczne”
O jej chodzi o bramki logiczne. Takie operacje jak AND, OR, XOR, NOT, NAND, NOR, EX-NOR. Skrót myślowy, ale dla informatyka zrozumiały. Table prawdy bramek logicznych na wiki: https://pl.wikipedia.org/wiki/Bramka_logiczna
Pzdr.
Ludzie ku… ogarnijcie się. Jeden czepia się semantyki, która w żaden sposób nie wypływa na wartość merytoryczną, inna osoba nie rozumie idei „hipotezy”, czy naprawdę dyskusja na portalu technicznym musi odbywać się na tak żałosnym poziomie?
Ciekawostka nt. sumy kontrolnej w PESEL. PESEL ma formę RRMMDDxxxxK (gdzie K to suma kontrolna). Niestety algorytm ma pewną wadę. Przy częstej pomyłce – zapisie daty w formie DDMMRR – suma kontrolna będzie ta sama :)
Chodzą pogłoski o numerach PESEL ze złą sumą kontrolną, ale nie udało mi się co do tego upewnić. Może to tylko legenda albo jakieś stare, nieaktualne sprawy. Jedynie jestem pewien, że zdarzają się zdublowane numery.
Ja tak kiedyś złamałem kod Paszportu Polsatu :) Codziennie wieczorem panowie z telewizji „losowali” kolejną liczbę, którą trzeba było wpisać w odpowiednią kratkę w owym „paszporcie”, i uzbieranie wszystkich liczb uprawniało do udziału w losowaniu nagród. Jako że liczby nie przekraczały rozmiaru alfabetu, z ciekawości postanowiłem zdekodować je na litery i pojawił się początek tekstu „POLSAT UCZY INFORMUJE BAWI” :) Widok twarzy rodzinki, gdy zacząłem „przewidywać” kolejne liczby zanim panowie z telewizora je „wylosowali” – bezcenny :)