<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">% File              : tmn.tex
% Version           : $Revision: 1.1 $
% Last-modified     : $Date: 2005/01/04 11:45:32 $
% Last-modifier     : FJ

\documentclass{splib}

\begin{document}
% main environment
\begin{protocol}%
% name
{TMN}%
% authors
{M. Tatebayashi, N. Matsuzaki, and D.B. Newman}%
% date of the first publication
{1989}%
% editor name
{}%
% date of submission
{}%
% date of last change, empty or = date of submission
{16/01/2003}

\begin{abstract}
Distribution of a fresh symmetric key and authentication.
Symmetric keys, trusted server and
public keys  (only the public key of the server is used).
\end{abstract}

\begin{core}
\begin{declarations}
\dcl{A, B, S}{principal}
\dcl{Ka, Kb}{key}
\dcl{PK, SK}{principal -&gt; key (keypair)}
\end{declarations}

\begin{messages}
\msg{1}{A}{S}{B, \crypt{Ka}{PK(S)}}
\msg{2}{S}{B}{A}
\msg{3}{B}{S}{A, \crypt{Kb}{PK(S)}}
\msg{4}{S}{A}{B, \crypt{Kb}{Ka}}
\end{messages}
\end{core}

\begin{explanation}
We assume that both \code{A} and \code{B} initially know
the public key \code{PK(S)} of \code{S}.

\code{Ka}, \code{Kb} are
session symmetric keys freshly created by \code{A}, resp. \code{B}.

In message \code{4}, \code{Kb} is encrypted using a symmetric key
algorithm with the key \code{Ka}. Hence, the encryption operators
used in \code{4} on one hand and in \code{1} and \code{3} on the 
other hand differ (though the notation is the same).
\end{explanation}

\begin{remark}
The binary operator \code{\crypt{Kb}{Ka}} in 
the last message can be intepreted either by a xor operator
or by another symmetric key encryption algorithm,
according to the implementation of the protocol.

This choice may be important, as the attack 4. below shows.
\end{remark}

\begin{property}
The protocol must guaranty the secrecy of the new shared key
\code{Kb}:
in every session, the value of \code{Kb} must be known only by
the participants playing the roles of \code{A} and \code{B}
in that session.

The protocol must guaranty the secrecy of the auxiliary fresh key
\code{Ka}:
in every session, the value of \code{Ka} must be known only by
the participants playing the roles of \code{A} and \code{S}
in that session.
\end{property}

\begin{references}
\cite{TMN89}, 
see also \cite{Lowe97TMN}.
\end{references}

\begin{attacks}
\paragraph{1.}
\cite{Lowe97TMN}.
Authentication and secrecy failure: 
the intruder \code{I} impersonates \code{A},
and uses a session auxiliary key \code{Ki} of his choice
to learn the established session key \code{Kb} in the last message.
\begin{messages}
\msg{1}{I(A)}{S}{B, \crypt{Ki}{PK(S)}}
\msg{2}{S}{B}{A}
\msg{3}{B}{S}{A, \crypt{Kb}{PK(S)}}
\msg{4}{S}{I(A)}{B, \crypt{Kb}{Ki}}
\end{messages}
Note that this is a very simple attack 
without parallel session or replay.

\paragraph{2.}
\cite{Lowe97TMN}.
Authentication failure: the intruder \code{I} impersonates \code{B}
and establishes a new session key \code{Ki} of his choice.
\begin{messages}
\msg{1}{A}{S}{B, \crypt{Ka}{PK(S)}}
\msg{2}{S}{I(B)}{A}
\msg{3}{I(B)}{S}{A, \crypt{Ki}{PK(S)}}
\msg{4}{S}{I(A)}{B, \crypt{Ki}{Ka}}
\end{messages}
This attack demonstrates actually more than an authentication flaw, 
because the established session key is known to the intruder.
With the following additional fifth message representing further
communications between \code{A} and \code{B} using the new
established shared key \code{Kb}:
\begin{messages}
\msg{5}{A}{B}{\crypt{X}{Kb}}
\end{messages}
the protocol would not guaranty the secrecy 
of \code{X} as expected.

\paragraph{3.}
\cite{Lowe97TMN}.
Parallel session and replay attack combining the above attacks 1 and 2.
Secrecy and authentication failure: at the end of the second session, the intruder
knows the established session key \code{Kb}.
\begin{messages}
\msg{i.1}{I(A)}{S}{B, \crypt{Ki}{PK(S)}}
\msg{i.2}{S}{B}{A}
\msg{i.3}{B}{S}{A, \crypt{Kb}{PK(S)}}
\msg{i.4}{S}{I(A)}{B, \crypt{Kb}{Ki}}
\msg{ii.1}{A}{S}{B, \crypt{Ka}{PK(S)}}
\msg{ii.2}{S}{I(B)}{A}
\msg{ii.3}{I(B)}{S}{A, \crypt{Kb}{PK(S)}}
\msg{ii.4}{S}{I(A)}{B, \crypt{Kb}{Ka}}
\end{messages}
Note that after this attack, \code{A} 
and \code{B} shall communicate with
the compromised session key \code{Kb}. 
This was not the case with attacks 1 and 2, because
during these attacks, the authentication had been
performed only with one honest principal.

\paragraph{4.} \label{attack4}
The following secrecy attack, described in~\cite{Simmons88,Simmons94cacm}, 
see also~\cite{TMN89}, doesn't rely on an
authentication failure but on algebraic properties of the encryption method.

It assumes that the symmetric key encryption is performed
by a operator \code{+} such that:
\begin{quote}
\begin{tabular}{rclr}
\code{(x+y)+y} &amp; = &amp; \code{x} &amp; \quad (1)\\
\code{x+(x+y)} &amp; = &amp; \code{y} &amp; \quad (1')
\end{tabular}
\end{quote}
%is left associative and idempotent, i.e. such that:
%\begin{quote}
%\begin{tabular}{rclr}
%\code{0+x} &amp; = &amp; \code{x} &amp; \quad (1)\\
%\code{x + x} &amp; = &amp; \code{0} &amp; (2)\\
%\code{x + (y + z)} &amp; = &amp; \code{(x + y) + z} &amp; (3)
%\end{tabular}
%\end{quote}
Hence, the protocol reads:
\begin{messages}
\msg{1}{A}{S}{B, \crypt{Ka}{PK(S)}}
\msg{2}{S}{B}{A}
\msg{3}{B}{S}{A, \crypt{Kb}{PK(S)}}
\msg{4}{S}{A}{B, Kb + Ka}
\end{messages}
We \code{A}, knowing \code{Ka},
receives the message \code{4},
he can obtain \code{Kb} by (1).

Let \code{*} be a multiplication operator
such that the public key encryption algorithm verifies,
for all public key \code{PK(U)}:
\begin{quote}
\code{\crypt{x * \crypt{y}{PK(U)}}{PK(U)}} = \code{\crypt{x*y}{PK(U)}}
\quad (2)
\end{quote}
Moreover, we assume a partial division operator (associated to \code{*}).

These hypotheses are satisfied e.g. if the following choices are made for
the operators:
\begin{itemize}
\item \code{+} is \code{xor},
\item \code{\crypt{x}{n}} is \verb!x^3 mod n! (with \code{x &lt; n}),
\item \code{*} is integer multiplication.
\end{itemize}

The attack is then the following.
The intruder \code{I} has learned the message \code{3} from a first
session \code{i}, and will use the server \code{S} as an oracle in a
second session \code{ii} to learn the key \code{Kb}.
\code{D} is the identity of an honest principal (which can be \code{A}
or \code{B} or anyone else).
\begin{messages}
\msg{i.3}{B}{I(S)}{A, \crypt{Kb}{PK(S)}}
\msg{ii.1}{I}{S}{D, \crypt{Ki * \crypt{Kb}{PK(S)}}{PK(S)}
                 ( = \crypt{Ki*Kb}{PK(S)} by (2) )}
\msg{ii.2}{S}{I(D)}{I}
\msg{ii.3}{I(D)}{S}{I, \crypt{Kd}{PK(S)}}
\msg{ii.4}{S}{I}{D, Kd + (Ki * Kb)}
%                 ( = (Ki * Kb) + Kd by (1))}
\end{messages}
\code{Ki} and \code{Kd} are arbitrary values chosen by \code{I}.

After receiving \code{ii.4}, \code{I} 
can compute \code{Ki * Kb} = \code{Kd + (Kd + (Ki * Kb))}, using (1'),
and hence \code{Kb}.

Note that in this attack, the server \code{S} cannot detect the replay
of \code{\crypt{Kb}{PK(S)}} in message \code{ii.1} because it is
multiplied with the arbitrary value \code{Ki}.
\end{attacks}

\begin{addcomment}{Ralf Treinen}{13/01/2003}
Ralf Treinen has submitted the above \ahref{#attack4}{claimed attack number 4}.
\end{addcomment}

\end{protocol}
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
</pre></body></html>