Protokół łamigłówki wycieczki z przewodnikiem

Protokół Guided Tour Puzzle (GTP) to protokół kryptograficzny służący do łagodzenia ataków typu „odmowa usługi” w warstwie aplikacji . Ma na celu przezwyciężenie wad protokołów puzzli opartych na obliczeniach , w których klienci są zobowiązani do obliczania zagadek związanych z twardym procesorem lub pamięcią, które faworyzują klientów z obfitymi zasobami obliczeniowymi. Protokół łamigłówki z przewodnikiem może być postrzegany jako forma protokołu dowodu pracy (POW).

Przegląd

Etapy protokołu w protokole łamigłówki wycieczki z przewodnikiem są podobne do protokołu łamigłówki klienta. Wszyscy klienci są zobowiązani do rozwiązania zagadki wycieczki z przewodnikiem przed otrzymaniem usługi z serwera , jeśli serwer podejrzewa, że jest obecnie atakowany w celu odmowy usługi lub jego obciążenie przekracza określony próg. Mówiąc najprościej, wycieczka z przewodnikiem to wycieczka, którą należy ukończyć, odbywając wiele podróży w obie strony do zestawu specjalnych węzłów, zwanych przewodnikami , w kolejności sekwencyjnej. Nazywa się to wycieczką z przewodnikiem , ponieważ kolejność zwiedzania przewodników jest nieznana klientowi, a każdy przewodnik musi skierować klienta do następnego przewodnika, aby klient ukończył oprowadzanie we właściwej kolejności. Pojedynczy przewodnik może pojawiać się wielokrotnie podczas wycieczki, dlatego termin przystanek jest używany do określenia pojedynczego pojawienia się przewodnika podczas wycieczki. Klient wie, który przewodnik jest na następnym przystanku, dopiero po zakończeniu wizyty na bieżącym przystanku. ^{[ potrzebne źródło ]}

Rozwiązanie zagadki związanej z wycieczką z przewodnikiem jest zasadniczo równoznaczne z ukończeniem wycieczki z przewodnikiem we właściwej kolejności. Począwszy od pierwszego przystanku, klient kontaktuje się z każdym przystankiem i otrzymuje odpowiedź. Każda odpowiedź zawiera unikalny token. Token w wiadomości zwrotnej z aktualnego przystanku służy do obliczenia adresu następnego przystanku przewodnika. Adres przewodnika pierwszego przystanku jest obliczany na podstawie tokena zawartego w pierwszej wiadomości zwrotnej serwera, która informuje klienta o rozpoczęciu procesu układania puzzli. ^{[ potrzebne źródło ]}

Klient musi wysłać token otrzymany od przewodnika z obecnego przystanku do przewodnika z następnym przystankiem, który użyje go jako danych wejściowych do funkcji obliczania tokena. Token otrzymany od przewodnika z ostatniego przystanku oraz token z wiadomości puzzli serwera są wysyłane na serwer jako dowód ukończenia wycieczki. Serwer może skutecznie zweryfikować te dwa tokeny i świadczy usługę klientowi dopiero po udowodnieniu ich ważności. ^{[ potrzebne źródło ]}

Kroki protokołu

Przykład układanki wycieczki z przewodnikiem, gdy liczba przewodników wynosi 2, a długość wycieczki wynosi 5. Kolejność wycieczki jest następująca: G1 -> G0 -> G1 -> G1 -> G0.

$Zanim$ zagadka wycieczki z przewodnikiem będzie mogła się rozpocząć, ${\ displaystyle N \ geq 2}$ systemie należy skonfigurować przewodników, gdzie . W międzyczasie serwer ustanawia $wspólny$ $≤$ z przewodnikiem za pomocą bezpiecznego kanału, gdzie $0\leq j<N$ . The server keeps a short-lived secret ${\ displaystyle K_ {s}}$ do obliczania pierwszej wartości skrótu, która jest zwracana klientowi jako część wiadomości układanki. Wiadomość z puzzlami $zawiera$ również długość trasy która służy do kontrolowania trudności układanki z przewodnikiem. Rysunek przedstawia przykład wycieczki z przewodnikiem, gdy i ${\ displaystyle N = 2}$ i ${\ displaystyle L = 5}$ .

Poniżej wyjaśniono szczegóły każdego etapu protokołu w protokole układanki z przewodnikiem.

$żądanie$ usługi : Klient wysyła usługi do serwera. Jeśli obciążenie serwera jest normalne, żądanie klienta jest obsługiwane jak zwykle; jeśli serwer jest przeciążony, przechodzi do początkowego etapu generowania puzzli .
Początkowe generowanie puzzli : serwer odpowiada klientowi wiadomością z $puzzlami$ , która informuje klienta o ukończeniu wycieczki z przewodnikiem $Wiadomość$ układanki zawiera długość $.$ i skrótu Serwer oblicza przy użyciu następującego wzoru: ${\ displaystyle h_ {0}}$

{\ Displaystyle h_ {0} = hash (A_ {x} \;||\; L \;||\; ts \ ;||\;K_{s})}

gdzie,

}

s

oznacza konkatenację, to adres (lub dowolna unikalna wartość) klienta, ZA x {\ displaystyle A_ {x}} ,

{

}

skrótu,

znacznikiem czasu i jest taką jak SHA- .

Rozwiązywanie zagadek : klient oblicza indeks przewodnika na $przystanku$ swojej wycieczki, korzystając z następującego wzoru:

{\ Displaystyle S_ {l }=(h_{l-1}\;mod\;N)}

gdzie,

{\ Displaystyle 0 <l \ równoważnik L}

. Gdy kontaktuje się z klientem , przewodnik turystyczny

l \leq L}

wartość skrótu

{\ displaystyle h_ {l}}

<

l

) korzystając ze wzoru:

js}}}

{\ Displaystyle h_ {l} = hash (h_ {l-1} \;||\; l \;||\; L \;||\; A_ {x} \;||\;

gdzie

{\ displaystyle l}

oznacza

-ty przystanek wycieczki klienta,

{\ displaystyle k_ {js}}

wspólny

między przewodnikiem a . Po kliencie

{\ displaystyle x}

S_ {l}}

odpowiedź serwera, rozpoczyna wycieczkę z przewodnikiem, obliczając indeks przewodnika za pomocą wzoru na

displaystyle

.

displaystyle

klient wysyła zestaw wartości ( ,

.

{

}

) do przewodnika , gdzie druga wartość oznacza, na którym przystanku wycieczki aktualnie znajduje się klient.

}

odpowiedzi klient otrzymuje wartość skrótu

\ displaystyle

, gdzie

h_

jest obliczany przy użyciu wzoru na

{\ displaystyle h_ {l}}

. Klient powtarza ten proces

L

1}

Displaystyle G_ {S_ {2}}, G_ {S_ {3}}, ..., G_ {S_ {L}}}

przewodnikami . Wiadomość zwrotna od przewodnika z ostatniego przystanku

\

wartość skrótu

sol

a klient wysyła

x}

(

{\ displaystyle h_ {0}, \; h_ {L}}

) do serwera jako odpowiedź na zagadkę.

{

Weryfikacja puzzli : gdy serwer otrzymuje żądanie od klienta $z$ odpowiedzią na zagadkę ( ${L}} )$ L $h'_$ załączeniu ${0}}$ najpierw sprawdza, czy $jest$ równe wartości obliczonej przy użyciu wzoru na $h_$ . $}$ tak, serwer oblicza $,$ wielokrotnie używając formuły dla sprawdza, czy jest $h_$ równa ${\ displaystyle h_ {L}}$ . Jeśli obie wartości skrótu są prawidłowe, serwer przydziela zasoby do przetworzenia żądania klienta. Ponieważ serwer zna współdzielone klucze ${\ Displaystyle k_ {1s}, k_ {2s}, \ kropki, k_ {Ns}}$ , może obliczyć łańcuch skrótów ${\ displaystyle h_ {1}, h_ {2}, ..., h_ {L}} bez kontaktowania się$ żadnym przewodnikiem. Luźna synchronizacja czasu między serwerem a przewodnikami jest wymagana w celu obliczenia tej samej wartości skrótu na serwerze i przewodnikach.

Porównanie z innymi protokołami puzzli

Protokoły łamigłówek obliczeniowych związanych z procesorem, takie jak Client Puzzle Protocol , mogą złagodzić skutki ataku typu „odmowa usługi”, ponieważ im bardziej atakujący chce przeciążyć serwer, tym więcej zagadek musi obliczyć i tym bardziej musi wykorzystywać swoje własne zasoby obliczeniowe. Klienci o dużej mocy obliczeniowej mogą rozwiązywać zagadki znacznie szybciej niż klienci bez środków do życia i mogą w niepożądany sposób zajmować większość zasobów serwera.

Inną istotną wadą protokołów łamigłówek obliczeniowych jest to, że wszyscy klienci, w tym wszyscy legalni klienci, są zobowiązani do wykonywania takich obliczeń intensywnie wykorzystujących procesor, które nie przyczyniają się do żadnej znaczącej usługi lub aplikacji.

Protokół układanki z przewodnikiem wymusza opóźnienia na klientach poprzez opóźnienia w obie strony , dzięki czemu żądania klientów docierają z szybkością, która jest znośna dla serwera. Zaletą korzystania z opóźnień w obie strony, w przeciwieństwie do trudnych problemów obliczeniowych, jest to, że opóźnienie w obie strony małego pakietu jest określane głównie przez opóźnienia przetwarzania, opóźnienia kolejkowania i opóźnienia propagacji na routerach pośrednich , dlatego jest poza kontrolą hostów końcowych (klientów). W związku z tym nawet osoba atakująca dysponująca dużymi zasobami obliczeniowymi nie może przedkładać siebie nad źle wyposażonych legalnych klientów. ^{[ potrzebne źródło ]}

Co więcej, w protokole łamigłówki z przewodnikiem obliczenia wymagane od klienta są trywialne. Ponieważ długość wycieczki z przewodnikiem jest zwykle niewielka, rzędu dziesiątek lub mniej, narzut związany z przepustowością związany z ukończeniem wycieczki z przewodnikiem jest również niewielki. W rezultacie klienci nie są obciążani ciężkimi obliczeniami (które są zwykle wymagane przez protokoły puzzli związane z procesorem lub pamięcią). ^{[ potrzebne źródło ]}

Zobacz też

^ ^a ^b Mehmud Abliz i Taieb Znati. Zagadka z przewodnikiem do zapobiegania atakom typu „odmowa usługi”. W Proceedings of the Annual Computer Security Applications Conference (ACSAC) 2009 , strony 279-288, Honolulu, HI, grudzień 2009.
^ „Pułapki bezpieczeństwa cybernetycznego” . Zarchiwizowane od oryginału w dniu 21 sierpnia 2016 r . Źródło 2 sierpnia 2016 r .
^ Martin Abadi, Mike Burrows, Mark Manasse i Ted Wobber. Umiarkowanie trudne, ograniczone pamięcią funkcje. W Proceedings of NDSS 2003 , strony 25-39, 2003.
^ Cynthia Dwork, Andrew Goldberg i Moni Naor. O funkcjach związanych z pamięcią do walki ze spamem. W Proceedings of CRYPTO 2003 , strony 426-444, 2003.

Linki zewnętrzne

Program Dorocznej Konferencji Aplikacje Bezpieczeństwa Komputerowego 2009

[Abliz09-1] Mehmud Abliz i Taieb Znati. Zagadka z przewodnikiem do zapobiegania atakom typu „odmowa usługi”. W Proceedings of the Annual Computer Security Applications Conference (ACSAC) 2009 , strony 279-288, Honolulu, HI, grudzień 2009.

[2] „Pułapki bezpieczeństwa cybernetycznego” . Zarchiwizowane od oryginału w dniu 21 sierpnia 2016 r . Źródło 2 sierpnia 2016 r .

[Abadi03MBP-3] Martin Abadi, Mike Burrows, Mark Manasse i Ted Wobber. Umiarkowanie trudne, ograniczone pamięcią funkcje. W Proceedings of NDSS 2003 , strony 25-39, 2003.

[Dwork03MBP-4] Cynthia Dwork, Andrew Goldberg i Moni Naor. O funkcjach związanych z pamięcią do walki ze spamem. W Proceedings of CRYPTO 2003 , strony 426-444, 2003.