Problem zabezpieczania danych: Różnice pomiędzy wersjami

Aktualna wersja na dzień 22:32, 30 kwi 2007

Autorem tego artykułu jest
morty

W wielu grach zachodzi potrzeba zapisu pewnych elementów do pliku zewnętrznego, by można go później było odczytać. Artykuł ten porusza kwestia zabezpieczania danych przed modyfikacjami i edycją zapisów.

Tak się tego nie robi

Najczęściej wybieraną metodą przez twórców gier jest zapis danych do pliku w postaci pliku INI. Ma to oczywistą zaletę - jest wygodne w obsłudze, szybkie i pozwala na skupieniu się na właściwych zdarzeniach w grze, a nie technice odczytywania danych. Przykładowy plik zapisu mógłby wyglądać tak:

[bohater]
zycie=30
ekran=2
bron=3
amunicja=30
[bronie]
1=1
2=0
3=0
4=0

Jak widać, wszystkie dane są na wierzchu. Można się pokusić o łatwe "podkręcenie" pliku zapisu - zwiększenie liczby żyć, broni, zdrowia i tak dalej. Jak widać, otwarty zapis ma zdecydowanie sporo wad. Spróbujmy się zastanowić, jak ulepszyć metodę zapisu.

Metoda pierwsza: prosta suma kontrolna

Jak więc wykryć, czy plik był zmieniany przez nieutoryzowaną aplikację? Bardzo prosto. Spróbujmy do pliku INI oprócz danych z zapisu dodać jeszcze ich sumę kontrolną, wyliczaną prostym sposobem. Sposób wyliczania musi być tajny, na potrzeby tego artykułu załóżmy taką metodą - mnożymy wszystkie zapisywane wartości zwiększone o jeden przez siebie.

Suma kontrolna dla danych w powyższym pliku wyniesie:

31*3*4*31*2*1*1*1=23064

Liczba 23064 to nasza suma kontrolna. Zapiszmy ją do pliku INI, by otrzymać następującą jego zawartość:

[bohater]
zycie=30
ekran=2
bron=3
amunicja=30
[bronie]
1=1
2=0
3=0
4=0
[inne]
kontrola=23064

Teraz, przy odczytywaniu gry odczytujemy sumę kontrolną. Następnie niezależnie od odczytanej wartości sprawdzamy ustaloną metodą (iloczyn wszystkich wartości powiększonych o jeden) i sprawdzamy, czy tak otrzymana liczba równa jest sumie kontrolnej zapisanej w pliku INI. Jeśli ktoś po zapisaniu gry zmieni sobie w pliku zapisu liczbę żyć na 32 a resztę parametrów zostawi bez zmian, to gra sprawdzając plik otrzyma sumę kontrolną równą 33*3*4*31*2*1*1*1 = 24552. Porównując te dwie liczby widzimy różnicę - wiemy, że plik był modyfikowany bez naszej wiedzy, a zatem możemy odmówić jego wczytania.

Metoda druga: ulepszona suma kontrolna

Powyższy przykład ma jedną istotną wadę. Jeśli ktoś wyjściowy plik np. w sposób następujący:

[bohater]
zycie=30
ekran=1
bron=30
amunicja=3
[bronie]
1=2
2=0
3=0
4=0
[inne]
kontrola=23064

(zamieniono miejscami broń i amunicję oraz ekran i broń 1) to po wyliczeniu sumy kontrolnej okaże się, że wyniesie ona 23064 czyli dokładnie tyle ile przed modyfikacjami. Oczywiście, jest to wina tego, że mnożenie jest przemienne. Ten problem można częściowo wyeliminować poprzez skomplikowanie działań - przyjmijmy inny sposób wyliczania sumy kontrolnej:

suma kontrolna = (zycie+1)*(ekran+2)*(bron+3)*(amunicja+4)*(bron1+5)*(bron2+6)*(bron3+7)*(bron4+8)

Nowa suma kontrolna to 31*3*33*7*10*6*7*8 = 72182880

Zamiana którejś z wartości zostanie teraz wychwycona. Przykładowo, zamieńmy miejscami ekran z życiem. Nowa suma kontrolna:

suma kontrolna = 2*32*33*7*10*6*7*8 = 51448320

Jak widzimy, suma kontrolna się zmieniła, a zatem możemy stwierdzić, że plik był modyfikowany

Dywagacja nad poprzednią metodą

Czy poprzednia metoda jest doskonała? Niestety nie. Zdesperowany gracz zauważy, że zmiana wartości stanu amunicji jest liniowa - jeśli ktoś zapisze plik, następnie zmieni żądaną wartość o jeden i zapisze ponownie, odczytując nową sumę kontrolną to odkryje, jaki ma ona wpływ na sumę kontrolną. Ponowienie tej operacji pozwoli upewnić się (po żmudnych obliczeniach) o ile należy zmieniać sumę kontrolną, gdy zmieniamy pewną wartość.

Aby zapobiec temu, warto zastanowić się nad mechanizmem, który nie jest liniowy.

Metoda trzecia

Okazuje się, że najlepszymi sposobami wyliczania sum kontrolnych są takie, które tracą część danych, przez co odszyfrowanie i zamiana w drugą stronę są niemożliwe. Najlepsze pod tym względem jest stosowanie szyfrowania algorytmem MD5, ale o nim będzie w następnej sekcji. Na razie spróbujmy napisać własny sposób:

Ustalmy, że tym razem sumę kontrolną wyliczamy w sposób następujący:

1. mnożymy kolejne elementy, które chcemy zapisać uprzednio powiększając je o jeden a następnie mnożąc przez ustalony mnożnik, na przykład: suma kontrolna=(1+0.0001*zycia)*(2+0.0002*ekran)*....*(8+0.0008*bron4)
2. z tak obliczonej wartości odrzucamy część całkowitą
3. otrzymana wartość po przecinku to nasza suma kontrolna

W naszym przykładzie, otrzymamy następującą sumę kontrolną:

suma kontrolna = 348 (0.348, po przecinku to nasza suma kontrolna).

Złamanie takiej sumy kontrolnej to nie lada gratka dla matematyków, ale teoretycznie może być złamana przez szereg różnych obliczeń. Na potrzeby gier taka metoda jest wystarczająca, ale ma jedną ważną wadę - a co, jeśli chcemy się zabezpieczyć przed zmianą wartości tekstowych?

MD5

Można oczywiście próbować pisać własny algorytm, generujący klucze z podanych napisów. Jest to jednak strata czasu w obliczu tego, że do dyspozycji mamy potężny i bardzo funkcjonalny algorytm MD5. Jego implementacje są dostępna zarówno dla GM jak i w postaci pluginu String Parser 2 dla TGF/MMF.

Klucze generowane przez MD5 składają się z 32 znaków i mogą wyglądać tak jak ten: 75d7d2e31a11aab924eb5c7e22ed538f.

Wynika stąd bardzo prosty wniosek: skoro mamy tylko x³² możliwości stworzenia klucza MD5 (gdzie x to ilość znaków, jaką możemy wykorzystać - przyjmijmy, że jest to ilość wszystkich znaków, jakie można wprowadzić z poziomu klawiatury) to pozostaje to niewielką ilością w porównaniu do x^{nieskończoności} ciągów, jakie możemy stworzyć. Co z tego wynika? Ano to, że mając hash MD5 nie jesteśmy w stanie w jakikolwiek sposób otrzymać liczby początkowej. Oczywiście, istnieje nieskończenie wiele wyrazów, których MD5 będzie identyczny, ale tu z pomocą przychodzi ciekawa właściwość MD5 - zmieniony choćby w drobnym stopniu wyraz będzie miał zupełnie inny hash niż początkowy, bez żadnego podobieństwa. Jak wykorzystać tę ciekawą właściwość MD5?

Przyjmijmy, że w pliku gry musimy zapisać hasło do profilu, które umożliwia zalogowanie się pod profil gry. Jeśli hasło to hasełko, to jego hash będzie wynosił edabc62080d739f4abecfc2f42bf6c2d. Jeśli nie wierzysz, że minimalna zmiana daje całkowicie inny hash to porównaj sobie hash dla słów haselko (przez l), haselk, haseklo - kolejno: 534993fc4955eb98a89a0beb4e8a92e2, c64e6eb74b518e584bafb3603daf7ffd, c031d9be490f595e3787bcd8332b30f6 - zero podobieństwa.

Do pliku INI wystarczy więc zapisać jedynie hash MD5 wymaganego hasła. Potem, przy próbie dostępu do profilu wystarczy poprosić o hasło, policzyć jego hash MD5 i porównać, czy zgadza się z tym, który zapisano w pliku. Jeśli nie, to podano hasło błędne.

Jak nietrudno zauważyć, drobną niedogodnością tej metody może być fakt, że zapomnianego hasła nie da się przywrócić.

Ulepszenie hashowania za pomocą MD5

Stosowanie MD5 jest bardzo bezpieczne, i daje niemalże 100% pewność, że dane nie zostaną złamane przez człowieka. W tym momencie jednak należy zwrócić uwagę na fakt, że duża moc obliczeniowa dzisiejszych maszyn daje im nad człowiekiem znaczną przewagę. Znając hash, maszyna może metodą losową porównywać go z kolejno hashowanymi wyrazami - np. zaczynając od aaaaaaa zapewne kiedyś trafi na hash o który chodzi, przy czym niekoniecznie musi on być z hasła, o które nam chodziło.

Można ten proces znacznie utrudnić, hashując niebezpośrednio wartości.

Im dłuższy wyraz do złamania, tym prawdopodobieństwo złamania przez komputer jest mniejsze. Zamiast hashować ciąg haselko, zrób więc hash wyrazu tajnykod_haselko, a następnie przy próbie logowania najpierw poproś o hasło, następnie dołącz z przodu ustalony prefix (np. tajnykod_), policz z takiej wartości hash i porównaj z tym, który zapisany został w pliku (zamiast tajnykod najlepiej umieścić kilkudziesięcioznakowy, nic nie znaczący ciąg znaków, np. #$%ghds123#dsg&532FFv^jv9(673kvsb...0&*9sda^h).

Wydaje Ci się, że jest to bezcelowe? Otóż nie :) Porównując hash z pewnego wyrazu z prefixem znacznie ograniczasz możliwość złamania metodą brute force i nie tylko. Załóżmy hipotetycznie, że nasze hasło (samo, bez prefixu) ma hash X. Niewątpliwie powinieneś wiedzieć z tego artykułu, że znajdzie się nieskończenie wiele innych haseł, które również będą miały hash X.

Co się stanie, jeśli hashujemy z prefiksem? Nawet, jeśli maszyna trafi metodą prób i błędów na hash z pliku INI (np. c031d9be490f595e3787bcd8332b30f6) i będzie to hash wyrazu A, to i tak program zwróci błąd, bo do tego wyrazu doda swój prefix i hash będzie inny. Innymi słowy, ta metoda znacznie redukuje prawdopoodbieństwo odgadnięcia hasła, redukując je w praktycznie 100% do zera.

Inny przykład zastosowania MD5

Przyjmijmy, że zapisujemy do pliku trzy wartości: imię, numer gracza oraz najlepszy wynik. Jak efektywnie zahashować dane, by zabezpieczyć się przed edycją? Nie ma potrzeby hashowania oddzielnie każdej wartości. Zrób zamiast tego hash z takiej wartości:

prefix_jakis_tajny14142;Marcin;2;123446

poszczególne wartości oddzieliłem średnikami. Jest to konieczne, bo inaczej można by w pliku INI usunąć numer gracza, i dwójkę dopisać do wyniku, a hash (bez średników) nie zmieniłby się. Ich użycie ten problem eliminuje.

Hash z tego co napisałem wyniesie abcf9d763413ad494bdcea5beecd7472. Dalej już wiadomo - porównujemy, sprawdzamy, akceptujemy lub odrzucamy

Więcej przykładów użycia sum kontrolnych

• w edytorze plansz - można powyższą metodą policzyć hash dla całej planszy
• w zapisywaniu poufnych haseł
• w zapisywaniu osiągnięć i najlepszych wyników (hash potwierdza ich prawdziwość)
• i tak dalej i tak dalej

Czy da się złamać MD5

Wielu pytało się mnie, czy można rozszyfrować wartość, znając jedynie jej hash MD5. Teoretycznie, matematyczne prawdopodobieństwo odgadnięcia jest w zasadzie równe zero. Okazuje się jednak, że w dzisiejszych czasach istnieje kilka zaawansowanych metod, które znacznie ulepszają proces poszukiwania hasha MD5 do tego stopnia, że znalezienie wartości o podanym hashu zajmuje dobrej maszynie jedynie kilka godzin.

Ciekawostką pozostaje osiągnięcie pewnego czeskiego naukowca, który stworzył dwa dokumenty - jeden to prośba o podwyżkę w pracy, a drugi prośba o natychmiastowe zwolnienie. Co w tym interesującego? Oba dokumenty miały ten sam hash MD5, co zostało osiągniętę zapewne przez stosowanie różnorakich znaków specjalnych.

Abstrahując od tej ciekawostki, dowodzi to że MD5 jest mimo wszystko podatny na odszyfrowanie. Czy jednak jest się czym bać? Wg mnie nie. Do złamania hasha trzeba nie lada umiejętności hackerskich, a zastosowanie metody z prefiksem, którą opisałem w tym artykule jest szczepionką na wszystkie próby. Średniozaawansowany czy nawet zaawansowany użytkownik komputera z hashem MD5 sobie nie poradzi. Dlatego też ta metoda jest jak najbardziej warta polecenia.

Zakończenie

Mam nadzieję, że ten teoretyczny artykuł przyda się twórcom gier, którzy borykają się z problemem zabezpieczania swoich zapisów gry, zabezpieczeniami przy przesyłaniu wyników online na serwer i w wielu innych sytuacjach. Powyższe metody z powodzeniem zostały zastosowane w wiodących grach, takich jak Frikik i Tankwars - jeśli ktoś je złamie to zgadzam się na upublicznienie kodu obu gier (czytaj, mam stuprocentową pewność, że nikt nie złamie)

Źródło

• http://otorowski.com/publicystyka/zabezpieczanie-danych-przed-edycja-w-game-makerze/