Ein Modell für Name-Stamp Protokolle

In der Betrachtung von Cascade Protokollen war die innere Struktur der Nachrichten beliebig. Nun wird ein Modell betrachtet in dem ein Teil der übertragenen Nachricht für den Namen des Senders reserviert ist. Zuerst führen wir einige neue Operationen auf Wörtern über die bereits bekannte Ver- und Entschlüsselung hinaus ein:

Definition 14 (Anhängen und Matchen)
Seien $\Sigma$ ein Alphabet und $x,y,z \in W(\Sigma)$, dann ist $i_x$ das Anhängen mit $i_x(y) = yx$, $d_x$ bezeichnet das Matchen mit:

$$d_x(y) = \left\{ \begin{array}{r@{\quad:\quad}l} z & y =zx \\ n.d. & sonst \\ \end{array}\right.$$

Bemerkung: Offensichtlich gilt für zwei beliebige Wörter $x$ und $y$:

$$d_x(i_x(y)) = y \;\;(\star)$$

Um sicherzustellen, daß die Kommunikation zwischen zwei Teilnehmern $X$ und $Y$ nicht terminiert, weil die Anwendung von $d_x$ in einem undefinierten Zustand verharrt fordern wir, daß alle $d_x$ Operationen durch wiederholtes Anwenden von $(\star)$ beseitigt wurden.

Aufgrund der neu eingeführten Operationen erweitern wir nun die Definition 7 der vollständig reduzierten Form:

Definition 15 (vollständig reduzierte Form, nicht weiter reduzierbar)
Sei $\Sigma$ ein Alphabet und $\gamma \in W(\Sigma)$. Dann bezeichnet $\overline{\gamma}$ Die vollständig reudzierte Form von $\gamma$ dergestalt, daß $\overline{\gamma}$ nach Defintion 7 vollständig reduziert ist und zusätzlich alle Teilwörter $d_x(i_x(y))$ von $\gamma$ für beliebige $x$ und $y$ zu $y$ reduziert wurden. Das Wort $\gamma$ ist nicht weiter reduzierbar, wenn $\overline{\gamma} = \gamma$ gilt.

Definition 16 (Zwei-Parteien Name-Stamp Protokoll)
Seien $X$ und $Y$ zwei Teilnehmer sowie $t,t' \in I\!N$ mit $t'=t$ oder $t'=t-1$. $T=\{\alpha_i(X,Y),\beta_j(X,Y)\}$ ist dann ein Zwei-Parteien Name-Stamp Protokoll mit:

$$\begin{eqnarray*} & \alpha_i(X,Y) \in W(\{E_x,E_y,D_x,i_x,i_y,d_x,d_y\}), & 1 \l... ...) \in W(\{E_x,E_y,D_y,i_x,i_y,d_x,d_y\}), & 1 \leq j \leq t' \\ \end{eqnarray*}$$

und

$$\begin{eqnarray*} N_1(X,Y) & = & \alpha_1(X,Y) \\ N_{2j}(X,Y) & = & \beta_j(X,Y... ...,Y) & = & \alpha_{i+1}(X,Y)N_{2i}(X,Y) ,\; 1 \leq i \leq t-1 \\ \end{eqnarray*}$$

Im $i$-ten Schritt wird zwischen $X$ und $Y$ die Nachricht $N_i(X,Y)M$ mit dem Klartext $M$ ausgetauscht. (Beide Teilnehmer senden also abwechselnd.)

Als erstes wird nun analog zum Vorgehen bei den Cascade Protokollen eine Definition für die Sicherheit angeboten.

Definition 17 (Sicheres Name-Stamp Protokoll (1))
Sei $T=\{\alpha_i,\beta_j\}$ ein Zwei-Parteien Name-Stamp Protokoll mit den Teilnehmern $X$, $Y$ und $Z$ ein dritter Teilnehmer sowie

$$\begin{eqnarray*} V_Z & := & \{\alpha_i(X,Y)\;\vert\;X \neq Y \wedge i \geq 2 \}... ...cup D_z) \\ & \cup & W(\{i_a,d_a\;\vert\;A \in \{X,Y,Z\}\}) \\ \end{eqnarray*}$$

Dann ist $T$ unsicher, wenn

$$\exists_{\gamma \in V_Z}: \overline{\{\gamma,N_i(X,Y)\}^\star} = \lambda$$

Anderenfalls ist $T$ sicher.

Beispiel 5
Das als Beispiel 3 eingeführte Beispiel notiert man für zwei Teilnehmer $X$ und $Y$ gemäß der vorangegangen Definition wie folgt: $X$ sendet $Y$

$$\begin{eqnarray*} N_1(X,Y)M & = & \alpha_1(X,Y)M \\ & = & E_yi_xE_yM \\ & = & E_y(E_y(M)X) \\ \end{eqnarray*}$$

woraufhin $Y$ antwortet

$$\begin{eqnarray*} N_2(X,Y)M & = & \beta_1(X,Y)N_1(X,Y)M \\ & = & E_xi_yE_xD_yd_... ..._xi_yE_xD_yE_yM \\ & = & E_xi_yE_xM \\ & = & E_x(E_x(M)Y)) \\ \end{eqnarray*}$$

Dieses Protokoll ist unsicher weil mit

$$\begin{eqnarray*} \beta_1(Z,X) & = & E_zi_xE_zD_xd_zD_x \\ \gamma & = & D_zd_xD_z\beta_1(Z,X)E_xi_zd_yD_zd_xD_z\beta_1(Z,X)E_xi_z \end{eqnarray*}$$

gilt:

$$\begin{eqnarray*} \overline{\gamma N_2(X,Y)} & = & D_zd_xD_z\beta_1(Z,X)E_xi_zd_... ..._z \\ & = & D_zd_xi_xE_z \\ & = & D_zE_z \\ & = & \lambda \\ \end{eqnarray*}$$