Tag: Python

Opublikowane w

Sprawdzanie DNS sinkhole

W poprzednim wpisie o phishingu w Polsce pisałem, że chcę zbadać jak wygląda adopcja listy hole.cert.pl wśród ISP do DNS sinkhole zapytań o domeny używane do phishingu. Odzew był mniejszy, niż się spodziewałem, ale coś udało się zrobić. Trochę się nauczyłem i może się to przydać także do względnie łatwego, samodzielnego sprawdzania np. cenzury w sieci, nie tylko w Polsce.

Wyniki

Jeśli kogoś interesują wyniki DNS sinkhole na podstawie hole.cert.pl wśród ISP, to znajdzie je w repo. Jak widać próbka jest mała, ale pewien trend daje się zauważyć. Nawet duzi ISP kablowi nie wykorzystują listy od CERT Polska. Na pewno – co oczywiste – wykorzystują ją sygnotariusze porozumienia. CERT trafnie zauważa, że lista może być wykorzystywana nie tylko na DNS operatorów, ale także na innych poziomach (Pi-hole, filtry AdBlock). Przypomnę jednak, że chodziło mi o sprawdzenie jaka jest adopcja listy na poziomie infrastruktury ISP. Czyli bez wymagania dodatkowych urządzeń czy działań po stronie użytkowników.

Pierwotny pomysł, czyli skrypty uruchamiane przez osoby trzecie w zasadzie ląduje w koszu. Wykorzystanie sond z projektu RIPE Atlas probe pozwala sprawdzić wszystko samodzielnie, bez angażowania innych ludzi. Wyniki się pokrywają, więc w repo zostawiłem zebrane ręcznie. Przy okazji widzę, że przy wynikach przydała by się data pomiaru. Do wyciągnięcia z commitów, ale lepsza byłaby podana jawnie.

RIPE Atlas probe

Dawno temu pisałem już o RIPE Atlas probe. Ogólnie są to małe pudełka dystrybuowane przez RIPE i uruchamiane przez ochotników (zarówno firmy jak i osoby fizyczne) w swoich sieciach na całym świecie. Pozwalają na wykonywanie pomiarów zlecanych przez panel RIPE. Istnieje też wersja programowa.

Użycie RIPE Atlas probe daje całkiem spore, zwłaszcza jeśli chodzi o zasięg pomiarów, możliwości ale… nie jest proste. Po pierwsze, trzeba mieć konto i kredyty. O ile założenie konta to moment, o tyle zebranie kredytów chwilę trwa – trzeba mieć uruchomioną sondę. No chyba, że dostaniemy je od kogoś, kto już je zgromadził (dziękuję!).

Po drugie, parametrów jest dużo i podobnie jak zwracane wyniki nie są do końca oczywiste. Np. w JSON szczegółowa odpowiedź jest zakodowana w base64, przez co początkowo uznałem (nie tylko ja…), że jej tam nie ma. Dekodowanie odpowiedzi DNS jest proste i opisane w dokumentacji, z przykładami w różnych językach. Niemniej, bariera wejście jest większa, niż się spodziewałem.

Sytuacji nie poprawiał fakt, że panel RIPE jest właśnie aktualizowany czy też przerabiany i nie wszystko wydaje się działać poprawnie. Np. wyszukiwania sond zwracają różne wyniki po API i przez stronę WWW.

RIPE Atlas Tools

Ostatecznie stanęło na tym, że korzystałem z API za pośrednictwem RIPE Atlas Tools. Do prototypowania i sprawdzeń ręcznych całkiem użyteczne. Nie jest to narzędzie idealne, na przykład status jest podawany numerycznie i… nie znalazłem opisu, który co oznacza. TBH szybciej było mi sprawdzić metodą porównania z wynikami z panelu. W każdym razie status connected to 1. Opis użycia w CLI:

Usage: ripe-atlas probe-search [-h] [--asn asn] [--asnv4 asnv4] [--asnv6 asnv6] [--prefix prefix] [--prefixv4 prefixv4] [--prefixv6 prefixv6]
[--location location | --center center | --country country] [--radius radius] [--tag tag] [--limit limit]
[--field {id,asn_v4,asn_v6,country,status,prefix_v4,prefix_v6,coordinates,is_public,description,address_v4,address_v6,is_anchor}]
[--aggregate-by {country,asn_v4,asn_v6,prefix_v4,prefix_v6}] [--all] [--max-per-aggregation max_per_aggregation] [--ids-only] [--status {0,1,2,3}]

Pora na parę przykładów użycia. W zasadzie wystarczają one do sprawdzenia jak z sieci danego ISP na określonym serwerze DNS jest resolvowana domena, czyli tego, co było przedmiotem projektu. Znalezienie aktywnych sond w sieci Orange (AS5617):

ripe-atlas probe-search --asn 5617 --country pl --ids-only --status 1

Sprawdzenie rozwiązywania domeny (tu: example.com) na wskazanym serwerze DNS (tu: 8.8.8.8) i sondzie (ID 1234):

ripe-atlas measure dns --query-argument example.com --from-probes 1234 --target 8.8.8.8

Powyższe zwróci w konsoli wynik w postaci już zdekodowanej. Dodatkowo będzie tam link do wyniku w panelu RIPE, który można pobrać w postaci JSON. Wtedy trzeba zdekodować odpowiedź DNS samodzielnie w sposób linkowany wyżej.

Na koniec wystarczy porównać, czy oczekiwany wynik jest taki sam, jak z serwera co do którego mamy pewność, że nie zmienia odpowiedzi i już wiemy, czy mamy do czynienia z DNS sinkhole. No prawie, bo domena może mieć np. zróżnicowane rozwiązywania nazwy na podstawie geolokalizacji. Można oczywiście sprawdzać większe ilości sond itp., ale do sprawdzania ew. cenzurowania stron lepsze mogą być zapytania HTTP – blokada bowiem może być na innym poziomie niż rozwiązywanie nazw domen.

Co dalej?

Ustalić adresy IP serwerów DNS przydzielanych klientom przez największych polskich ISP. Sądziłem, że będzie trywialne. Niestety myliłem się. Kiedyś można było bez problemu znaleźć je w sieci na stronach poszczególnych ISP. Teraz często nie chwalą się oni tą informacją. Np. nie udało mi się znaleźć tej informacji np. dla operatorów Vectra i Toya[1]. Tu liczę na pomoc czytelników w postaci podania nazwy ISP i przydzielonych przez niego adresów serwerów DNS.

Pełny automat. Powyższe przykłady są dobre do ręcznego wykorzystania. Mam wrażenie, że odpytywanie przy pomocy RIPE Atlas Tools słabo nadaje się do oskryptowania. Obsługa timeoutów, parsowanie odpowiedzi, zapisywanie wyników – wydaje mi się, że lepiej będzie napisać wszystko w Pythonie.

Badanie czasu od pojawienia się domeny na liście do czasu zablokowania u danego ISP. Bez pełnego automatu nie ma co podchodzić do tematu. I pewnie do przemyślenia jak to potem sensownie interpretować, pewnie trzeba będzie wspomóc się statystyką.

Motywacja mi nieco siadła, więc pewnie zejdzie dłuższa chwila nim coś nowego się pojawi.

[1] Dla Netii z kolei znalazłem serwery DNS, ale nie było ochotnika do zrobienia testu wersją ze skryptem. Przy pomocy sond RIPE Atlas ustaliłem, że nie korzystają z listy CERT Polska, ale z publikacją tego poczekam na zmianę flow zamieszczania danych.

Opublikowane w

711 wyrazów o optymalizacji – część 3

Była część pierwsza i część druga, pora na kolejną, niezupełnie planowaną. Jak pamiętamy w części drugiej udało się ograniczyć sprawdzane liczby do 49 sztuk. To, co chodziło mi od czasu do czasu po głowie to pytanie, czy da się rozwiązać tę zagadkę „na piechotę”, bez użycia komputera?

Rozejrzałem się za możliwymi uproszczeniami i zauważyłem kolejne potencjalne pole do optymalizacji, czyli zmniejszenia liczby potrzebnych obliczeń. Jak wiadomo, 711 jest liczbą nieparzystą. Aby suma dwóch liczb była nieparzysta, jedna z nich musi być parzysta, druga nieparzysta. Z kolei aby suma dwóch liczb była parzysta, albo obie muszą być parzyste, albo nieparzyste. Tu mamy do czynienia z sumą czterech liczb, więc są dwa przypadki. Albo jedna z liczb jest nieparzysta, a trzy są parzyste, albo odwrotnie.

Z naszych 49 liczb, 37 jest parzystych, a 12 nieparzystych. Jak to wpływa na przestrzeń rozwiązań? Z 49^4, czyli ok. 5,8 mln przechodzimy na 12*37^3 + 37*12^3 czyli ok. 672 tys. Nadal trochę dużo jak na ręczne liczenie, ale jak to wpłynie na czas obliczeń? Nasz skrypt będzie miał postać:

number = 711
iterations = 0
divs_odd = list()
divs_even = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        if i % 2 == 0:
            divs_even.append(i)
        else:
            divs_odd.append(i)

for a in range(0, len(divs_even)-1):
    for b in range(a, len(divs_odd)-1):
        for c in range (0, len(divs_odd)-1):
            for d in range (c, len(divs_odd)-1):
                iterations += 1
                if divs_even[a] + divs_odd[b] + divs_odd[c] + divs_odd[d] == 711:
                    if divs_even[a] * divs_odd[b] * divs_odd[c] * divs_odd[d] == 711000000:
                        print("Solved: ", divs_even[a], divs_odd[b], divs_odd[c], divs_odd[d], iterations)
                        exit()

for a in range(0, len(divs_odd)-1):
    for b in range(0, len(divs_even)-1):
        for c in range (b, len(divs_even)-1):
            for d in range (c, len(divs_even)-1):
                iterations += 1
                if divs_odd[a] + divs_even[b] + divs_even[c] + divs_even[d] == 711:
                    if divs_odd[a] * divs_even[b] * divs_even[c] * divs_even[d] == 711000000:
                        print("Solved: ", divs_odd[a], divs_even[b], divs_even[c], divs_even[d], iterations)
                        exit()

Niezależnie od kolejności bloków (najpierw 1 liczba parzysta i 3 nieparzyste, co jest teoretycznie korzystniejszym wariantem, czy odwrotnie), potrzebować będziemy poniżej 95 tys. iteracji. Czas to 0,08 sekundy dla zwykłego interpretera Pythona lub 0,12 sekundy dla Pypy.

Możliwa jest też wersja „w dół”:

number = 711
iterations = 0
divs_odd = list()
divs_even = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        if i % 2 == 0:
            divs_even.append(i)
        else:
            divs_odd.append(i)

for a in range(len(divs_even)-1, 0, -1):
    for b in range(len(divs_odd)-1, 0, -1):
        for c in range (b, 0, -1):
            for d in range (c, 0, -1):
                iterations += 1
                if divs_even[a] + divs_odd[b] + divs_odd[c] + divs_odd[d] == 711:
                    if divs_even[a] * divs_odd[b] * divs_odd[c] * divs_odd[d] == 711000000:
                        print("Solved: ", divs_even[a], divs_odd[b], divs_odd[c], divs_odd[d], iterations)
                        exit()

for a in range(len(divs_odd)-1, 0, -1):
    for b in range(len(divs_even)-1, 0, -1):
        for c in range (b, 0, -1):
            for d in range (c, 0, -1):
                iterations += 1
                if divs_odd[a] + divs_even[b] + divs_even[c] + divs_even[d] == 711:
                    if divs_odd[a] * divs_even[b] * divs_even[c] * divs_even[d] == 711000000:
                        print("Solved: ", divs_odd[a], divs_even[b], divs_even[c], divs_even[d], iterations)
                        exit()

Ilość potrzebnych iteracji waha się od 18 do 28 tys. w zależności od kolejności bloków. Natomiast czas wykonania to 0,06 sekundy dla zwykłego interpretera Pythona i 0,1 sekundy dla Pypy.

Nadal nie jest to optymalizacja powodująca, że da się policzyć „na piechotę”, ale… coraz bliżej.

Opublikowane w

711 wyrazów o optymalizacji – część 2

Tym, co nie czytali polecam lekturę części pierwszej. Tymczasem pojawił się wpis z rozwiązaniem i pojawiło się tam znacznie lepsze podejście do tematu. Optymalizacja polega na tym, że korzysta ono z właściwości, że wszystkie składowe muszą być dzielnikami 7,11 i wielokrotnością 0,01. W wersji całkowitej – muszą być liczbami całkowitymi będącymi dzielnikami. Następnie generuje kombinacje tych liczb i sprawdza właściwe warunki. Lekko dostosowany kod to:

import itertools
number = 711
iterations = 0
divs = list()
for i in range(1, number + 1):
    if 711000000 % i == 0:
        divs.append(i)

for i in itertools.combinations_with_replacement(divs, 4):
    iterations += 1
    if sum(i) == 711 and i[0] * i[1] * i[2] * i[3] == 711000000:
        print(i, iterations)

print(len(divs))

Dodałem wyświetlanie ilości dzielników – jest ich raptem 62, więc przeszukiwana przestrzeń to 62^4 czyli… niecałe 15 mln. Rozwiązanie jest znajdowane po nieco ponad 600 tys. iteracji w czasie… pomijalnym, bowiem ok. 0,2 sekundy, niezależnie od interpretera. Przy pomiarze tak niskich czasów wykonania wypadałoby się pobawić już w uśrednianie, ale chodzi o wartości orientacyjne.

W zasadzie dalsza optymalizacja nie ma sensu, ale pobawić się można. Przede wszystkim, można wyeliminować samo 711. Jeśli którakolwiek wartość byłaby taka, to pozostałe musiałyby być zerami, co jest sprzeczne z warunkami zadania. Kolejny całkowity dzielnik to połowa 711. Po uwzględnieniu tego, skrypt przyjmie postać:

import itertools
number = 711
iterations = 0
divs = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        divs.append(i)

for i in itertools.combinations_with_replacement(divs, 4):
    iterations += 1
    if sum(i) == 711 and i[0] * i[1] * i[2] * i[3] == 711000000:
        print(i, iterations)

print(len(divs))

Ogranicza nam to liczbę sprawdzanych dzielników do 49, przestrzeń do niecałych 6 mln, a liczbę iteracji potrzebnych do znalezienia rozwiązania do 266 tys. Dla przypomnienia, w pierwszym rozwiązaniu, które było czystym brute force zaczynaliśmy od przestrzeni 225 miliardów, czyli 44 tys. razy większej.

A gdyby tak nadal korzystać z dzielników, ale zapomnieć o itertools i wrócić do starych, dobrych pętli, tym razem nie na wartościach, tylko na indeksach w liście divs? Wersja naiwna to:

number = 711
iterations = 0
divs = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        divs.append(i)

for a in range(0, len(divs)-1):
    for b in range(0, len(divs)-1):
        for c in range (0, len(divs)-1):
            for d in range (0, len(divs)-1):
                iterations += 1
                if divs[a] + divs[b] + divs[c] + divs[d] == 711:
                    if divs[a] * divs[b] * divs[c] * divs[d] == 711000000:
                        print("Solved: ", divs[a], divs[b], divs[c], divs[d], iterations)
            exit()

Wyraźny krok wstecz – 3,6 mln iteracji i prawie sekunda (PyPy nadal ~0,2s). Ale otwiera nam to drogę do znanych już optymalizacji:

number = 711
iterations = 0
divs = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        divs.append(i)

for a in range(0, len(divs)-1):
    for b in range(a, len(divs)-1):
        for c in range (b, len(divs)-1):
            for d in range (c, len(divs)-1):
                iterations += 1
                if divs[a] + divs[b] + divs[c] + divs[d] == 711:
                    if divs[a] * divs[b] * divs[c] * divs[d] == 711000000:
                        print("Solved: ", divs[a], divs[b], divs[c], divs[d], iterations)
            exit()

Jest tak dobrze, jak przy itertoolsach: ~0,2s oraz 246 tys. iteracji. Pamiętamy jednak, że najlepsze wyniki były dla sprawdzania od największych do najmniejszych, zatem:

number = 711
iterations = 0
divs = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        divs.append(i)

for a in range(len(divs)-1, 0, -1):
    for b in range(a, 0, -1):
        for c in range (b, 0, -1):
            for d in range (c, 0, -1):
                iterations += 1
                if divs[a] + divs[b] + divs[c] + divs[d] == 711:
                    if divs[a] * divs[b] * divs[c] * divs[d] == 711000000:
                        print("Solved: ", divs[a], divs[b], divs[c], divs[d], iterations)
            exit()

Wynik znajdowany jest już po 30 tys. iteracji, w czasie poniżej 0,1s na zwykłym interpreterze Pythona. Co ciekawe, w tym wariancie PyPy jest nieco wolniejsze, z czasem nieco ponad 0,1s, zapewne większy narzut na uruchomienie interpretera.

UPDATE Dostępna jest kolejna część traktująca o optymalizacji.