tt

[HindawiJournalOfChaos.git] / IH / iihmsp13 / securityci1.tex

\subsection{Classification of Attacks}\label{sec:attack-classes}

In the steganography framework, attacks have been classified
in~\cite{Cayre2008} as follows. 


\begin{definition}
Watermark-Only Attack (WOA) occurs when an attacker has only access to several watermarked contents.
\end{definition}

\begin{definition}
Known-Message Attack (KMA) occurs when an attacker has access to several pairs of watermarked contents and
corresponding hidden messages.
\end{definition}

\begin{definition}
Known-Original Attack (KOA) is when an attacker has access to several pairs of watermarked contents and
their corresponding original versions.
\end{definition}

\begin{definition}
Constant-Message Attack (CMA) occurs when the attacker observes several watermarked contents and only knows that the
unknown hidden message is the same in all contents.
\end{definition}

The synthesis of this classification is illustrated in the
Table~\ref{table:attack-classification}~\vpageref{table:attack-classification}.


\begin{table*}
\begin{center}

 \begin{tabular}{|c||c|c|c|}
  \hline
   \textbf{Attack} &  \textbf{Original content} &  \textbf{Stego
  content} &  \textbf{Hidden message}\\ 
    \hline 
    \hline 
 \textbf{Watermark-Only Attack (WOA)} &   &    $\times$ & \\
  \hline
 \textbf{Known-Message Attack (KMA)}  & & $\times$ & $\times$ \\
  \hline
 \textbf{ Kown-Original Attack (KOA)} & $\times$ & $\times$ & \\
 \hline
 \textbf{Constant-Message Attack (CMA)} & & & $\times$ \\
  \hline 
  \end{tabular}
  \caption{Watermarking attacks classification in context of~\cite{Kalker2001}}
  \end{center}
  \label{table:attack-classification}
  \end{table*}
  

\subsection{Stego-Security of $CI_1$}\label{sec:stego-security}

In the prisoner problem of Simmons~\cite{Simmons83,DBLP:conf/ih/BergmairK06}
illustrated by the
Figure~\ref{fig:simmons-prisonner-problem}~\vpageref{fig:simmons-prisonner-problem}, Alice and Bob are in jail, and they want to, possibly, devise an escape plan by exchanging hidden messages in innocent-looking cover contents. These messages are to be conveyed to one another by a common warden, Eve, who over-drops all contents and can choose to interrupt the communication if they appear to be stego-contents.

\begin{figure*}
\begin{center}
%\includegraphics[width=10.5cm]{./img/prisoner-problem.png}
\includegraphics[width=15cm]{./img/prisoner-problem}
\end{center}
\caption{Simmons' prisoner problem~\cite{Simmons83}}
\label{fig:simmons-prisonner-problem}
\end{figure*}

The stego-security, defined in this
framework, is the highest security level in WOA setup~\cite{Cayre2008}.
To recall it, we need the following notations:
\begin{itemize}
  \item $\mathds{K}$ is the set of embedding keys,
  \item $p(X)$ is the probabilistic model of $N_0$ initial host contents,
  \item $p(Y|K_1)$ is the probabilistic model of $N_0$ watermarked contents.
\end{itemize}

Furthermore, it is supposed in this context that each host content has been watermarked with the same secret key $K_1$ and the same embedding function $e$.


It is now possible to define the notion of stego-security:

\begin{definition}[Stego-Security]
\label{Def:Stego-security}
The embedding function $e$ is \emph{stego-secure} if and only if:
$$\forall K_1 \in \mathds{K}, p(Y|K_1)=p(X).$$
\end{definition}

To the best of our knowledge, until now, only two schemes have been proven to be stego-secure.
On the one hand, the authors of \cite{Cayre2008} have established that the spread spectrum technique called Natural Watermarking is stego-secure when its distortion parameter $\eta$ is equal to $1$.
On the other hand, it has been proven in~\cite{gfb10:ip} that: 

\begin{proposition}
Chaotic Iterations with Independent Strategy (CIIS)  are stego-secure.
\label{prop:CIIS-stego-security}
\end{proposition}



\begin{proof}
Let us suppose that $X \sim
\mathbf{U}\left(\mathbb{B}^N\right)$ in a CIIS setup. 
We will prove by a mathematical induction that $\forall n \in \mathds{N}, X^n \sim
\mathbf{U}\left(\mathbb{B}^N\right)$. The base case is immediate, as $X^0 = X \sim
\mathbf{U}\left(\mathbb{B}^N\right)$. Let us now suppose that the statement
 $X^n \sim
\mathbf{U}\left(\mathbb{B}^N\right)$ holds for some $n$. 
Let $e \in \mathbb{B}^N$ and $\mathbf{B}_k=(0,\cdots,0,1,0,\cdots,0) \in \mathbb{B}^N$ (the digit $1$ is in position $k$).
%\begin{equation*}
So $P\left(X^{n+1}=e\right)=\sum_{k=1}^N
P\left(X^n=e+\mathbf{B}_k,S^n=k\right).$
%\end{equation*}
These two events are independent in CIIS setup, thus:
%\begin{equation*}
$P\left(X^{n+1}=e\right)=\sum_{k=1}^N
P\left(X^n=e+\mathbf{B}_k\right) \times P\left(S^n=k\right)$.
%\end{equation*}
%According to the recurrence hypothesis ($X^n \sim
%\mathbf{U}\left(\mathbb{B}^N\right)$):
According to the inductive hypothesis:
%\begin{equation*}
%\begin{array}{ll}
%P\left(X^{n+1}=e\right) & =\sum_{k=1}^N
%\frac{1}{2^N} \times P\left(S^n=k\right) \\
%& =\frac{1}{2^N} \sum_{k=1}^N
% P\left(S^n=k\right)\\
%\end{array}
%\end{equation*}
%\begin{equation*}
$P\left(X^{n+1}=e\right)=\frac{1}{2^N} \sum_{k=1}^N
 P\left(S^n=k\right)$.
%\end{equation*}
The set of events $\left \{ S^n=k \right \}$ for $k \in \llbracket 1;N
\rrbracket$ is a partition of the universe of possible, so
$\sum_{k=1}^N P\left(S^n=k\right)=1$.

%Evaluate now $ P\left(S^n=k\right)$.
%\newline
%We have: $K^0 = M \otimes K \sim
%\mathbf{U}\left([0;1]\right)$, so $K^\prime=F\left( K^0,p \right) \sim
%\mathbf{U}\left([0;1]\right)$, because for PLCMs, ``Uniform input generate
%uniform output''~\cite{Lasota}.
%Well with an immediate proof by recurrence we have:
%$K^n \sim \mathbf{U}\left([0;1]\right)$. As $S^n = \left \lfloor N \times X^n
%\right \rfloor + 1$ we can deduce that: $S^n \sim
%\mathbf{U}\left([1;N]\right)$. Therefore: $ P\left(S^n=k\right)=\frac{1}{N}$.
Finally, 
%\begin{equation*}
%\begin{array}{llr}
%P\left(X^{n+1}=e\right) & =\frac{1}{2^N} \sum_{k=1}^N
% P\left(S^n=k\right) & \\
% & =\frac{1}{2^N} \sum_{k=1}^N \frac{1}{N} & \\
% & =\frac{1}{2^N} & \\
%\end{array}
%\end{equation*}
%\begin{equation*}
%$\begin{array}{llr}
%P\left(X^{n+1}=e\right) & =\frac{1}{2^N} \sum_{k=1}^N
% P\left(S^n=k\right) & \\
%P\left(X^{n+1}=e\right) & =\frac{1}{2^N} \sum_{k=1}^N \frac{1}{N} &
% =\frac{1}{2^N} \\
%\end{array}$.
$P\left(X^{n+1}=e\right)=\frac{1}{2^N}$, which leads to $X^{n+1} \sim
\mathbf{U}\left(\mathbb{B}^N\right)$.
This result is true $\forall n \in \mathds{N}$, we thus have proven that, $$\forall K \in [0;1], Y_K=X^{N_0} \sim
\mathbf{U}\left(\mathbb{B}^N\right) \text{ when } X \sim
\mathbf{U}\left(\mathbb{B}^N\right)$$

%already corrected
So CIIS defined in
Section~\ref{sec:data-hiding-algo-chaotic iterations} are stego-secure.
\end{proof}

We will now prove that,

\begin{proposition}
%already corrected
Chaotic Iterations with Dependent Strategy (CIDS)  are not stego-secure.
\end{proposition}

\begin{proof}
Due to the definition of CIDS, we have $P(Y_K=(1,1,\cdots,1))=0$. So there is
no uniform repartition for the stego-contents $Y_K$.
\end{proof}







\subsection{Chaos-Security of the $CI_1$ scheme}\label{sec:chaos-security}

To check whether an information hiding scheme $S$ is chaos-secure or not, $S$
must be written as an iterate process $x^{n+1}=f(x^n)$ on a metric space
$(\mathcal{X},d)$. This formulation is always possible~\cite{ih10}. So,


\begin{definition}[Chaos-Security]
\label{Def:chaos-security-definition}
An information hiding scheme $S$ is said to be chaos-secure on
$(\mathcal{X},d)$ if its iterative process has a chaotic
behavior according to Devaney.
\end{definition}

In the approach presented by Guyeux \emph{et al.}, a data hiding scheme is secure if it is unpredictable. 
Its iterative process must satisfy the Devaney's chaos property and its level of chaos-security increases with the number of chaotic properties satisfied by it. 

This new concept of security for data hiding schemes has been proposed in~\cite{ih10} as a complementary approach to the existing framework. 
It contributes to the reinforcement of confidence into existing secure data hiding schemes. 
Additionally, the study of security in KMA, KOA, and CMA setups is realizable in this context. 
Finally, this framework can replace stego-security in situations that are not encompassed by it. 
In particular, this framework is more relevant to give evaluation of data hiding schemes claimed as chaotic. 




We can establish that,

\begin{proposition}
%already corrected
CIIS and CIDS are chaos-secure.
\end{proposition}

\begin{proof}
It is due to the fact that chaotic iterations have a chaotic behavior, as defined by Devaney. 
\end{proof}



In the two following sections, we will study the qualitative and quantitative
properties of chaos-security for chaotic iterations. These properties can measure the
disorder generated by our scheme, giving by doing so some important informations about the
unpredictability level of such a process.

\subsection{Quantitative property of
chaotic iterations}\label{sec:chaos-security-quantitative}

\begin{definition}[Expansivity]
A function $f$ is said to be \emph{expansive} if $
\exists \varepsilon >0,\forall x\neq y,\exists n\in \mathds{N}%
,d(f^{n}(x),f^{n}(y))\geqslant \varepsilon .$
\end{definition}

\begin{proposition}
 $G_{f_{0}}$ is an expansive chaotic dynamical system on $\mathcal{X}$ with a constant of expansivity is equal to 1.
\end{proposition}
\begin{proof}
If $(S,E)\neq (\check{S};\check{E})$, then either $E\neq \check{E}$, so at least
one cell is not in the same state in $E$ and $\check{E}$. Consequently the distance between $(S,E)$ and $(%
\check{S};\check{E})$ is greater or equal to 1. Or $E=\check{E}$. So the
strategies $S$ and $\check{S}$ are not equal. Let $n_{0}$ be the first index in which the terms $S$ and $\check{S}$
differ. Then $
\forall
k<n_{0},\tilde{G}_{f_{0}}^{k}(S,E)=\tilde{G}_{f_{0}}^{k}(\check{S},\check{E})$,
and $\tilde{G}_{f_{0}}^{n_{0}}(S,E)\neq \tilde{G}_{f_{0}}^{n_{0}}(\check{S},\check{E})$. As $E=\check{E},$ the cell which has changed in $E$ at the $n_{0}$-th
iterate is not the same as the cell which has changed in $\check{E}$, so
the distance between $\tilde{G}_{f_{0}}^{n_{0}}(S,E)$ and $\tilde{G}_{f_{0}}^{n_{0}}(\check{S%
},\check{E})$ is greater or equal to 2.
\end{proof}

\subsection{Qualitative property of
chaotic iterations}\label{sec:chaos-security-qualitative}

\begin{definition}[Topological mixing]
A discrete dynamical system is said to be topologically mixing
if and only if, for any couple of disjoint open set $U, V \neq \varnothing$,
$n_0 \in \mathds{N}$ can be found so that $\forall n \geqslant n_0, f^n(U) \cap
V \neq \varnothing$.
\end{definition}
\begin{proposition}
$\tilde{G}_{f_0}$ is topologically mixing on $(\mathcal{X}', d')$.
\end{proposition}

This result is an immediate consequence of the lemma below.

\begin{lemma}
For any open ball $B$ of $\mathcal{X}'$, an index $n$ can be found such that $\tilde{G}_{f_0}^n(B) = \mathcal{X}'$.
\end{lemma}

\begin{proof}
Let $B=B((E,S),\varepsilon)$ be an open ball, which the radius can be considered as strictly less than 1.
All the elements of $B$ have the same state $E$ and are such that an integer $k \left(=-\log_{10}(\varepsilon)\right)$ satisfies:
\begin{itemize}
\item all the strategies of $B$ have the same $k$ first terms,
\item after the index $k$, all values are possible.
\end{itemize}

Then, after $k$ iterations, the new state of the system is $\tilde{G}_{f_0}^k(E,S)_1$ and all the strategies are possible (all the points $(\tilde{G}_{f_0}^k(E,S)_1,\textrm{\^{S}})$, with any $\textrm{\^{S}} \in \mathbb{S}$, are reachable from $B$).

We will prove that all points of $\mathcal{X}'$ are reachable from $B$. Let
$(E',S') \in \mathcal{X}'$ and $s_i$ be the list of the different cells between
$\tilde{G}_{f_0}^k(E,S)_1$ and $E'$. We denote by $|s|$ the size of the sequence
$s_i$. So the point $(\check{E},\check{S})$ of $B$ defined by: $\check{E} = E$,
$\check{S}^i = S^i, \forall i \leqslant k$, $\check{S}^{k+i} = s_i, \forall i
\leqslant |s|$, and $\forall i \in \mathds{N}, S^{k + |s| + i} = S'^i$
is such that $\tilde{G}_{f_0}^{k+|s|}(\check{E},\check{S}) = (E',S')$. This concludes the proofs of the lemma and of the proposition.
\end{proof}



\subsection{Comparison between spread-spectrum and chaotic iterations}\label{sec:comparison-application-context}

The consequences of topological mixing for data hiding are multiple. Firstly, 
security can be largely improved by considering
the number of iterations as a secret key. An attacker
will reach all of the possible media when iterating without this key.
Additionally, he cannot benefit from a KOA setup, by studying media in the
neighborhood of the original cover. Moreover, as in a topological mixing
situation, it is possible that any hidden message (the initial condition), is
sent to the same fixed watermarked content (with different numbers of
iterations), the interest to be in a KMA setup is drastically reduced. Lastly, as
all of the watermarked contents are possible for a given hidden message, depending
on the number of iterations, CMA attacks will fail.


%Already corrected
The property of expansivity reinforces drastically the sensitivity in the aims of
reducing the benefits that Eve can obtain from an attack in KMA or KOA setup. For
example, it is impossible to have an estimation of the watermark by moving the
message (or the cover) as a cursor in situation of expansivity: this cursor will
be too much sensitive and the changes will be too important to be useful. On the
contrary, a very large constant of expansivity $\varepsilon$ is unsuitable: the
cover media will be strongly altered whereas the watermark would be undetectable.


% %Indeed, let us consider the same cover $E$ twice with two different watermarks
% $S,S'$. Thus $d(X,Y) < 1$, where $X=(E,S), Y=(E,S')$ and $d$ is for the distance
% previously defined. However, due to expansivity, $\exists n \in \mathds{N},
% d\left(G^n (X) ; G^n (Y) \right) \geqslant \varepsilon.$ Thus, $d_\infty
% \left(G^n (X)_1 ; G^n (Y)_1 \right) \geqslant \varepsilon - 1$, so either
% $d_\infty \left(X_1 ; G^n (X)_1 \right) \geqslant \dfrac{\varepsilon - 1}{2}$, or
% $d_\infty \left(Y_1 ; G^n (Y)_1 \right) \geqslant \dfrac{\varepsilon - 1}{2}$. If
% $\varepsilon$ is large, then at least one of the two watermarked media will be
% very different than its original cover.

Finally, spread-spectrum is relevant when
a discrete and secure data hiding technique is required in WOA setup. However,
this technique should not be used in KOA and KMA setup, due to its lack of
expansivity.% In the next section, we will present a new class of data hiding
schemes, which are expansive.