16

POCZĄTKI

HAKIN9 5/2008

I

stnieje wiele programów, które pomagają

złamać hasło lub sprawdzają, czy hasła

użytkowników zarejestrowanych w jakimś

systemie są wystarczająco skomplikowane.

Sami użytkownicy, aby zapamiętać hasło, zwykle

używają imienia swojego partnera, zwierzęcia,

przezwiska szkolnego itd. Dzięki temu znacznie

ułatwiają potencjalnemu włamywaczowi dostęp

do swoich danych. Co jednak zrobić, jeśli hasło

jest na tyle mocne, że standardowe słowniki nie

wystarczą? Możemy użyć naszego osobistego

uroku i oczarować ofiarę – tak, aby zdradziła

nam hasło. Jednym słowem zastosować bardzo

obecnie modne socjotechniki. Gdy to nie zadziała,

pozostaje nam tylko tzw. metoda brute force,

czyli siłowa. Nie chodzi tu oczywiście o próbę

zastraszenia, tylko o automatyczne generowanie

wszystkich możliwych haseł. Musimy się więc

zmierzyć z problemem generacji możliwych

ciągów dla danego alfabetu (zbioru znaków). Dla

przypomnienia – liczba wszystkich kombinacji

dla zbioru n-elementowego wynosi

n!

. Oznacza

to, że dla

n=5

liczba ta wyniesie

1*2*3*4*5 =

120

. Jak szybki jest wzrost tej funkcji, można

się przekonać licząc np.

10!

,

12!

czy

64!

. W

przypadku próby znalezienia odpowiedniego

hasła możemy nałożyć sobie więzy, które znacznie

skrócą czas obliczeń. Więzy te to długość hasła.

Nasze zadanie skraca się zatem do problemu

NK

, gdzie

N

liczbą znaków w alfabecie, natomiast

przez

K

oznaczamy długość hasła. Dramatycznie

zmniejsza to przestrzeń naszych poszukiwań.

SŁAWOMIR ORŁOWSKI

Z ARTYKUŁU
DOWIESZ SIĘ

podstawy języka Java.

CO POWINIENEŚ
WIEDZIEĆ

rekurencyjne wywołanie funkcji,

jak używać klasy BigInteger do
reprezentacji dużych liczb,

jak generować dowolne
permutacje dla pewnego
alfabetu.

Rozważmy alfabet o długości 35 znaków, który

zwiera wszystkie litery i cyfry. Liczba możliwych

kombinacji wyniesie:

35! = 1,0333147966386144929666651337523e+40

Natomiast jeżeli szukamy słowa, powiedzmy, o

długości 8 znaków, to:

358 = 2251875390625

Mogę śmiało zar yzykować stwierdzenie, że

hasła o długości 1 lub 2 zdarzają się dosyć

rzadko. Realnie używane hasła zwykle też nie są

zbyt długie.

Tradycyjne podejście programistyczne

nakazuje użycie rekurencyjnego wywołania funkcji.

Jest to jakiś sposób. Należy jednak pamiętać,

że przy rekurencji nie jesteśmy w stanie w prosty

sposób przewidzieć zużycia pamięci. Często

zdarza się również, że programista, który napisał

funkcję rekurencyjną, sam nie jest pewny, czy

działa ona poprawnie. Listing 1. przedstawia

przykładową metodę w języku Java, która

rekurencyjnie generuje wszystkie możliwe ciągi dla

danego alfabetu. Należy jeszcze zadeklarować

pola

sb

oraz

alphabet

:

private static StringBuilder sb = new

StringBuilder(len);

private static String alphabet = "0123456789

abcdefghijklmnopqrstuvwxyz";

Stopień trudności

Automatyczna
generacja
ciągów

Niestandardowe rozwiązania dla standardowych problemów
potrafi ą znacznie uprościć i przyspieszyć pracę. W tym artykule
przedstawiam ciekawą metodę rozwiązującą problem generacji
wszystkich możliwych ciągów znaków z danego zbioru.

17

AUTOMATYCZNA GENERACJA CIĄGÓW

HAKIN9

5/2008

Zmienna

len

będzie określała długość

generowanego ciągu.

W tym artykule chciałbym

zaproponować Czytelnikowi nieco inne

podejście do tego problemu. Sama

idea tego rozwiązania jest prosta. Każdy

z ciągów utworzony z liter danego

alfabetu może być reprezentowany przez

pewną niepowtarzalną liczbę. Liczba

ta jednoznacznie reprezentuje daną

kombinację. Dzięki temu w kodzie może

być użyty zwykły mechanizm indeksowania,

co znacznie upraszcza i przyspiesza całą

sprawę. Przyjrzyjmy się bliżej, na jakiej

zasadzie to działa. W systemie dziesiętnym

dowolną liczbę możemy zapisać jako

sumę cyfr z tego systemu pomnożonych

przez kolejne potęgi dziesiątki. Liczba 1978

będzie zapisana jako:

1978 = 1*103 + 9*102 + 7*101 + 8*100

Jest to wiedza serwowana nam już chyba

w szkole podstawowej. W podobny sposób

możemy pomyśleć o ciągach z danego

alfabetu. Niech nasz alfabet składa się z

sześciu znaków:

? = {a,b,c,d,e,f}

Litera a ma pozycję numer 1,

b

numer 2

itd. My będziemy szukać wszystkich ciągów

o długości 4. Wiemy już, że takich ciągów

będzie 64, czyli 1296. Spróbujmy teraz

przedstawić ciąg cafe za pomocą naszej

notacji:

cafe = 3*63 + 1*62 + 6*61 + 5*60 = 725

Znak

c

jest trzecim znakiem w alfabecie,

długość alfabetu wynosi 6. Mnożymy

więc 3 i 6 podniesione do trzeciej potęgi,

ponieważ licząc od prawej i indeksując

począwszy od zera,

c

zajmuje trzecią

pozycję w ciągu cafe. Możemy również

uznać, że litera a ma pozycję 0, wówczas:

cafe = 2*63 + 0*62 + 5*61 + 4*60 = 466

Należy tylko pamiętać, że odnosi się to

jedynie do ciągów o tej samej długości.

W przeciwnym wypadku mielibyśmy

kłopot z sekwencjami typu a, aa, aaa

itd., ponieważ za każdym razem ich

reprezentacja wynosiłaby 0. Nie byłoby

to więc wzajemnie jednoznaczne. Proszę

zwrócić uwagę na fakt, że znając jakąś

permutację możemy powiedzieć, jaka

będzie następna. Co więcej, możemy

wskazać k-tą permutację dla danych

warunków początkowych (alfabet, długość

szukanego ciągu). Jest to niewątpliwą

zaletą tego rozwiązania w porównaniu do

rekurencyjnego wywoływania funkcji. Jeśli z

jakiś powodów nagle przerwiemy działanie

metody rekurencyjnej z Listingu 1. to aby

wygenerować wszystkie ciągi, jesteśmy

zmuszeni wywoływać funkcję jeszcze raz

Listing 1.

Rekurencyjne generowanie ciągów o danej długości

private

static

void

Brute

(

int

len

)

{

if

(

len

==

0

)

{

System

.

out

.

println

(

sb

.

toString

());

}

else

{

for

(

int

i

=

0

;

i

<

length

;

i

++)

{

sb

.

setCharAt

(

len

-

1

,

alphabet

.

charAt

(

i

));

Brute

(

len

-

1

);

}

}

}

Listing 2.

Metoda main

public

static

void

main

(

String

[]

args

)

{

s

=

new

StringBuilder

();

bia

=

new

BigInteger

[

2

];

alphabet

=

"0123456789abcdefghijklmnopqrstuvwxyz"

;

length

=

alphabet

.

length

();

int

min

=

2

;

int

max

=

3

;

String

message

=

"passbrute.exe [min] [max]

\n

where min is a minimum length of

the password and max is a maximum length of the password. For

example: passbrute.exe 4 5"

;

/*

if(args.length !=2) {

System.out.println(message);

return;

}

if (!Character.isDigit((char)args[0].charAt(0)) || !Character.isDigit((char)args

[1].charAt(0))) {

System.out.println(message);

return;

}

**/

for

(

int

i

=

min

;

i

<=

max

;

i

++)

{

BigInteger

all

=

BigInteger

.

valueOf

(

length

);

all

=

all

.

pow

(

i

);

BigInteger

number

=

BigInteger

.

ZERO

;

while

(

number

.

compareTo

(

all

)

<

0

)

{

System

.

out

.

println

(

Count

(

number

,

i

));

number

=

number

.

add

(

BigInteger

.

ONE

);

}

}

}

Listing 3.

Metoda Count

private

static

String

Count

(

BigInteger

base

,

int

stlen

)

{

s

.

setLength

(

0

);

for

(

int

i

=

stlen

-

1

;

i

>=

0

;

i

--)

{

bia

=

base

.

divideAndRemainder

(

BigInteger

.

valueOf

(

length

));

int

step

=

base

.

remainder

(

BigInteger

.

valueOf

(

length

))

.

intValue

();

s

.

append

(

alphabet

.

charAt

(

bia

[

1

]

.

intValue

()));

base

=

bia

[

0

];

}

return

s

.

toString

();

}

18

POCZATKI

HAKIN9 5/2008

od nowa. W przypadku proponowanej

metody możemy wznowić poszukiwania po

przerwaniu generacji (np. na liczbie 466),

ponieważ znamy liczbę reprezentującą

następny ciąg. Jest to liczba o jeden

większa od tej, na której przerwaliśmy

poszukiwania (467).

Mój tekst jest inspirowany artykułem pt.

Using Permutations in .NET for Improved

Systems Security, który napisał James

McCaffrey dla MSDN. Implementacja

tej metody jest również przedstawiona w

artykule pochodzącym z witryny Code

Project . Linki do nich znajdują się w ramce

W Sieci. Zachęcam do przestudiowania

tych tekstów.

Przejdźmy teraz do napisania

programu. Będzie to aplikacja konsolowa.

Językiem programowania będzie Java.

Nasz program będzie miał możliwość

określenia długości generowanych ciągów

poprzez podanie wartości minimalnej i

maksymalnej. Rozpoczniemy od definicji

statycznych pól naszej klasy:

private static StringBuilder s;

private static String alphabet;

private static long length;

private static BigInteger[] bia;

Pole

alphabet

przechowywać

będzie alfabet, jaki użyjemy w trakcie

generowania ciągów. Jego długość

będzie przechowywana w zmiennej

length

. Referencja klasy

StringBulider

posłuży nam do konstrukcji ciągu z danej

reprezentacji liczbowej. Jest to znacznie

lepsze rozwiązanie niż użycie klasy

String

, ponieważ zużywa znacznie mniej

pamięci i jest prawdopodobnie szybsze.

Innym rozwiązaniem może być użycie

tablicy znaków. Jednak moim zdaniem

wygodniejsze jest użycie właśnie klasy

StringBuilder

. Liczby reprezentujące

ciągi mogą być znacznych rozmiarów.

Dlatego zdecydowałem się wykorzystać

klasę

BigInteger

. Jest to bardzo wygodna

klasa do reprezentacji dużych liczb, dla

których zakresy double lub long są za

małe. Aby mieć dostęp do tej klasy, musimy

zaimportować odpowiedni pakiet:

import java.math.BigInteger;

Na pierwszy rzut oka dziwić może fakt

deklaracji tablicy

bia

. Do czego może

się przydać? Otóż klasa

BigInteger

posiada metodę

divideAndRemainder

,

która zwraca wynik zwykłego dzielenia

i dzielenia modulo jako tablicę

dwuelementową. Metoda ta przyda

nam się nieco dalej do zamiany liczby

na odpowiadający jej ciąg. Inicjalizację

wszystkich pól przeprowadzimy w

metodzie main, której kod przedstawia

Listing 2. Jest to zabieg raczej estetyczny,

ponieważ moglibyśmy je inicjalizować

również przy definiowaniu.

Na początek powołujemy do życia

pola

s

i

bia

. W kolejnym kroku określamy

alfabet oraz jego długość. Dalej

definiujemy zmienne min i max, które

będą przechowywały zakres długości

generowanych ciągów. Na początku

niech będzie to 2 i 3. Sam zakres będzie

mógł wprowadzać użytkownik poprzez

wywołanie programu z parametrami

min

i

max

. Do tego służą właśnie dwie

kolejne instrukcje warunkowe, które

sprawdzają poprawność argumentów. Na

potrzeby testów można je zakomentować,

tak, jak jest to zrobione na Listingu 2.

Najważniejszy fragment kodu to dwie

zagnieżdżone pętle. Zewnętrzna pętla

for

(indeksowana przez

i

) wskazywać

będzie aktualną długość szukanego

ciągu. Druga pętla będzie generowała

liczby jednoznacznie reprezentujące ciągi.

Ich sposób reprezentacji przedstawiony

był we wstępie. Zakres pętli zawiera się

pomiędzy zerem a maksymalną liczbą

ciągów dla danej długości alfabetu i

danej długości ciągu, czyli

length^i

.

Użyłem tutaj typu

BigInteger

, ponieważ

te liczby mogą być znacznych rozmiarów.

Z racji tego, że nie możemy przeciążać

operatorów, zmuszeni jesteśmy do

użycia metod klasy

BigInteger

, które

realizują odpowiednie działania. Metoda

compareTo

porównuje ze sobą dwie liczby

BigInteger

(

this i

argument wywołania

metody). Zwraca -1, jeśli liczba

this

jest

mniejsza od argumentu, 0 jeśli są równe

i

1 – jeśli

this

jest większy od argumentu.

Ze względu na to wygodnie jest użyć pętli

while, której zmienna iteracyjna będzie

zwiększana za pomocą metody

add

. W

tej pętli wywoływana jest metoda

Count

,

która na podstawie długości ciągu

i

liczby będzie zwracała reprezentujący

ją ciąg. Jak widać, ciągi te wypisywane

są na konsolę. Należy pamiętać, że w

przypadku długich obliczeń potrafi to

znacznie spowolnić proces generacji

ciągów. Ostatnim krokiem w pisaniu

tego programu będzie zdefiniowanie

wspomnianej wcześniej metody Count. Jej

kod przedstawia Listing 3.

Argument base odpowiada za

liczbę, którą chcemy zamienić na ciąg,

a

argument

stlen

określa długość tego

ciągu. Na początku metoda

setLength

W Sieci

•

http://msdn2.microsoft.com/en-us/library/aa302371.aspx – artykuł J. McCaffrey, Using

Permutations in .NET for Improved Systems Security, 2003 MSDN,

•

http://www.codeproject.com/KB/security/Hacking_BruteForce.aspx – artykuł F. Waeytens,

A small and elegant bruteforcing class, 2006 Code Project,

•

http://java.sun.com/j2se/1.4.2/docs/api/java/math/BigInteger.html – specyfikacja klasy

BigInteger,

•

http://pl.wikipedia.org/wiki/Atak_brute_force – opis ataku brute force wraz z przykładową

implementacją w języku C.

Terminologia

•

Atak brute force – jest to tzw. atak siłowy. Polega on na sprawdzeniu wszystkich możliwych

kombinacji ciągów w celu poszukiwania hasła lub klucza szyfrującego. Jest to atak najbardziej

prymitywny, niemniej jednak potrafi być skuteczny. W teorii zawsze gwarantuje sukces, jednak

przy haśle składającym się z większej liczby znaków jego czas wykonywania może być bardzo

długi.

•

Atak słownikowy – jest zbliżony do ataku brute force. Polega on również na sprawdzaniu

pewnych ciągów. Jednak ich lista jest ograniczona do pewnego podzbioru – słownika.

Istnieje wiele sposobów tworzenia słownika. Ogranicza on czas potrzebny do odgadnięcia

hasła, jednak nie gwarantuje sukcesu.

resetuje nam referencję klasy

StringBuilder

, ustawiając jej

długość na zero. Zamiast tego moglibyśmy tutaj użyć operatora

new

, który tworzyłby nowy egzemplarz, jednak takie rozwiązanie

zmniejszyłoby wydajność tej metody. Budowanie nowego

egzemplarza klasy trwa dosyć długo – właśnie dlatego referencja

s

jest powoływana do życia w metodzie

main

, a nie tutaj. W pętli

for

będziemy wyłuskiwać kolejne znaki tworzące ciąg. Znaki te

dodawane są do pola s za pomocą metody

append

. Aby obliczyć

dla danej pozycji, jaki znak z alfabetu ona reprezentuje, musimy

zastosować dzielenie modulo zmiennej

base

przez długość

alfabetu. Następnie powinniśmy zmniejszyć zmienną

base

poprzez zwykłe podzielenie jej przez długość alfabetu. W Javie

można to robić za pomocą jednej metody

divideAndRemainder

.

Zwraca ona dwuelementową tablicę, w której znajduje się wynik

standardowego dzielenia (indeks 0) oraz dzielenia modulo (indeks

1). Po zakończeniu pętli zwracamy uzyskany ciąg. I to wszystko.

Program jest już gotowy. Zachęcam do jego testów.

Jedną z podstawowych metod testowania szybkości

algorytmów, jest ich czas wykonywania. Przed wywołaniem metody

realizującej badany algorytm można umieścić linijkę:

long start = System.currentTimeMillis();

Po wywołaniu metody umieszczamy w kodzie wpis:

long stop = System.currentTimeMillis();

Teraz wartość stop-start odzwierciedla nam czas działania

programu. Celowo użyłem tu słowa programu, ponieważ taka

metoda mierzy czas działania programu (lub jego fragmentu)

w systemie operacyjnym. A system operacyjny może w trakcie

jego działania przełączać się pomiędzy pamięcią fizyczną a

plikiem wymiany na dysku, może przełączać zadania, zmieniać

priorytet, obsługiwać jakieś zdarzenie itd. Jest to więc metoda

mało wiarygodna. Dodatkowo głównym czynnikiem, które będzie

generować opóźnienia w programie, są operacje wejścia/

wyjścia, czyli np. wypisywanie ciągów do pliku czy na ekran. W

związku z tym programy wykorzystujące czy to rekurencję, czy to

zaproponowaną przeze mnie metodę będą działały z podobną

prędkością właśnie ze względu na operacje we/wy.

Pisząc ten artykuł wyszedłem z założenia, że odrobina

matematyki programistom na pewno nie zaszkodzi. Przedstawione

rozwiązanie odbiega od standardowych metod, które stosuje

się zwykle w takich przypadkach. Być może nie jest optymalne

i można je jeszcze przyspieszyć. Jednak sama idea, oprócz

tego, że nietypowa – jest prosta, a to przecież znacznie ułatwia

implementację. Wiedza tu przedstawiona może posłużyć nie

tylko do prób uzyskania hasła, ale przede wszystkim w testach

bezpieczeństwa. Łatwo możemy zbudować z tego kodu klasę,

której będziemy używać w innych aplikacjach.

Sławomir Orłowski

Z wykształcenia fizyk. Obecnie jest doktorantem na Wydziale Fizyki, Astronomii
i Informatyki Stosowanej Uniwersytetu Mikołaja Kopernika w Toruniu. Zajmuje się
symulacjami komputerowymi układów biologicznych (dynamika molekularna) oraz
bioinformatyką. Programowanie jest nieodzowną częścią jego pracy naukowej
i dydaktycznej. Ma doświadczenie w programowaniu w językach C, C++, Delphi, Fortran,
Java, C# i Tcl. Współzałożyciel i koordynator grupy .NET WFAiIS. Jest autorem artykułów
i książek informatycznych. Strona domowa: http://www.fizyka.umk.pl/~bigman.
Kontakt z autorem: [e-mail]