Niech P oznacza reprezentację protokołu w przestrzeni nici, Q oznacza zbiór sekretów posiadanych przez uczestników, ja reprezentuję początkową informację dostępną z penetratorem, a PQ reprezentuje prawdopodobieństwo, z jakim penetrator zna elementy Q. Algorytm ( o nazwie DPFS-I) przyjmuje powyższe parametry jako dane wejściowe i zwraca DPFS protokołu. Zbiór R, potęga sekretów pomniejszona o zbiór zerowy, z elementami ułożonymi w rosnącym porządku liczności, jest obliczana jako pierwsza. Zmienna E sukcesywnie oznacza każdy element R. Algorytm przechodzi przez pętlę przez R, sprawdzając, czy nie ma ataków na protokół, gdy sekrety w zestawie E są łączone z początkowymi informacjami penetratora. CHECK_SECRECY wykonuje powyższą funkcję i zwraca atak lub NIL. Funkcja CHECK_ SECRECY może być zrealizowana przy użyciu dowolnych praktycznych narzędzi, takich jak Athena.
DPFS-I (P, Q, PQ, I)
- m ← 0
- R ← 2Q\{φ}
- while R ≠ φ
- do E ← head(R)
- if (t ← CHECK_SECRECY(P, I ∪ E)) ≠ NIL)
- then p ← PROB_OF_FAILURE(P, Q, P_Q, t, I ∪ E)
- m ← MAX (p, m)
- R ← R\{E}
- return (m)
Funkcja CHECK_SECRECY zwraca NIL, jeśli przeciek elementów w E nie narusza kluczy sesji. Zwraca atak, wartość inną niż NIL, jeśli wyciek elementów E naraża klucze sesji. Jeśli atak zostanie zwrócony, prawdopodobieństwo naruszenia klucza sesji jest obliczane za pomocą funkcji PROB_OF_FAILURE. Funkcja przyjmuje reprezentację protokołu, zestaw sekretów, prawdopodobieństwo kompromitacji każdego z sekretów, reprezentację ataku oraz wstępne informacje penetratora i zwraca prawdopodobieństwo kompromitacji klucza sesji. Rozszerzony model przestrzeni pasm, jak wyjaśniono w sekcji „Rozszerzenia modelu przestrzeni pasm”, dostarcza szczegółowych informacji na temat obliczania prawdopodobieństwa naruszenia klucza sesji. Model opiera się na założeniu, że penetrator wybrałby najłatwiejszą (z najwyższym prawdopodobieństwem) opcję ataku na protokół, gdyby była dostępna więcej niż jedna opcja. W związku z tym powyższe działania są powtarzane dla wszystkich elementów w R, a największe prawdopodobieństwo kompromitacji klucza sesji jest obliczane jako DPFS. Złożoność DPFS-I jest wykładnicza pod względem liczby sekretów, | Q |, ponieważ algorytm zapętla się przez potęgę sekretów R. Jednak nie jest to poważny problem, ponieważ sekrety można podzielić na typy, w większości protokoły, a następnie należy wziąć pod uwagę wyciek tylko określonego typu tajemnicy, zamiast ujawnienia wszystkich tajemnic tego typu. Wtedy złożoność byłaby wykładnicza pod względem liczby typów, co jest stałą w większości protokołów. Role odgrywane przez różnych uczestników protokołu są proponowane do wykorzystania do identyfikacji typów tajemnic. Wystąpienie protokołu można uznać za zbiór ról i instancji ról. Na przykład protokół A-GDH.2, który jest analizowany w sekcji „Analiza protokołów GKA w sprawie częściowej poufności przekazywania”, działa z n uczestnikami. Można go zamodelować jako pojedyncze wystąpienie roli inicjatora, n – 2 wystąpienia ról pośredniczących i pojedyncze wystąpienie roli kontrolera. Każda rola, wraz z charakterem klucza, czy to krótko- czy długoterminowego, jest definiowana jako typ. Dlatego protokół A-GDH.2 ma pięć typów kluczy: (1) klucz krótkoterminowy inicjatora, (2) klucz długoterminowy inicjatora, (3) klucz krótkoterminowy pośrednika, (4) klucz długoterminowy pośrednika, oraz (5) klucz krótkoterminowy administratora. Zatem liczba typów byłaby stała. DPFS-II to poprawiony algorytm, wykorzystujący losowanie typów. Algorytm DPFS-II przyjmuje protokół P, jako dane wejściowe reprezentowane przez przestrzenie nici, zestaw typów sekretów, QT i początkową informację z intruzem I. Zbiór sekretów QT zawiera elementy, które są krotkami odpowiadającymi każdemu sekretowi rodzaj. Format krotki to typ klucza, liczba jego wystąpień i prawdopodobieństwo, z jakim wystąpienie tego typu będzie znane intruzowi. QI reprezentuje zbiór wszystkich wystąpień wszystkich sekretów. Algorytm sprawdza najpierw, czy są ataki, gdy początkowa informacja penetratora jest wzmocniona z ustawionym QI, to znaczy, że protokół nie spełnia silnej doskonałej tajności przekazywania. Jeśli nie spełnia on idealnej poufności przekazywania, algorytm przechodzi do znalezienia DPFS. Zbiór RT reprezentuje zestaw mocy typów sekretów innych niż zbiór zerowy, uporządkowanych w kolejności rosnącej liczności, przy czym ET jest pierwszym elementem. Algorytm wykonuje iterację przez zestaw (RT), sprawdzając atak i obliczając prawdopodobieństwo niepowodzenia za każdym razem, gdy nastąpi atak. Dla każdego zestawu typów sekretów, które prowadzą do ataku, jego superzestawy są usuwane z RT. Powyższe kroki są powtarzane dla wszystkich elementów zestawu RT, a najwyższe prawdopodobieństwo naruszenia klucza sesji jest zwracane jako DPFS. DPFS-II ma wykładniczą złożoność czasową pod względem liczby typów. Ponieważ liczba typów jest praktycznie stała dla protokołu, wykładnicza złożoność czasowa nie jest poważnym problemem.
DPFS_II (P, QT, I)
- QI ← set of all secrets
- if QI ≠ φ
- then
- if (t ← Check Secrecy (P, I ∪ QI)) ≠ NIL
- then
- RT ← 2QT\{φ}
- m ← φ
- while RT ≠ φ
- do
- if (t = Check_Secrecy (P, I ∪ ET)) ≠ NIL
- then p ← Prob_of_Failure(P, QT, t, I ∪ ET)
- m ← Max (p, m)
- while RT ≠ NULL
- do if F ⊃ ET | F ∈ RT
- then RT ← RT\{F}
- U ← U\{ET}
- return (m)-++
Klasyfikacja sekretów na typy musiałaby być specyficzna dla protokołu, a uogólnienie nie pozwoliłoby uchwycić niuansów wszystkich protokołów. Oparta na typach klasyfikacja tajemnic w protokołach GKA sama w sobie wymaga pewnych interesujących i trudnych badań. Na przykład, czy w niektórych protokołach może być możliwe, że więcej niż jedna instancja tego samego typu roli mogłaby ujawnić klucz sesji, podczas gdy instancje różnych typów nie? Sprawdzanie takich przypadków wymagałoby powrotu do DPFS-I. Niespełnienie idealnej tajemnicy przekazywania, po którym następuje uruchomienie DPFS-II zwracającego 0 jako prawdopodobieństwo kompromitacji klucza sesji, sugeruje, że istnieje potrzeba wykonania DPFS-I. Obliczony w ten sposób DPFS może być używany do porównywania różnych protokołów GKA, a tym samym pozwala użytkownikom dowiedzieć się, jakie są szanse na złamanie ich kluczy sesji. Kilka protokołów GKA opublikowanych w literaturze jest analizowanych, jak podano w następnej sekcji