oxford: jusqu'à la sécurité

[hdrcouchot.git] / oxford.tex

\JFC{Dire que c'est une synthèse du chapitre 22 de la thèse de Tof}


\section{Processus de marquage}

Par la suite, le message numérique qu'on cherche à embarquer est 
noté $y$ et le support dans lequel se fait l'insertion est noté $x$. 

Le processus de marquage est fondé sur les itérations unaires d'une fonction 
selon une stratégie donnée.  Cette fonction et cette stratégie 
sont paramétrées par un entier naturel permettant à la méthode d'être
appliquable à un média de n'importe quelle taille.
On parle alors respectivement de \emph{mode} et d'\emph{adapteur de stratégies} 

\subsection{Embarquement}


\begin{Def}[Mode]
\label{def:mode}
Soit $\mathsf{N}$ un entier naturel. 
Un mode est une application de $\mathds{B}^{\mathsf{N}}$
dans lui même.
\end{Def}



\begin{Def}[Adapteur de Stratégie]
  \label{def:strategy-adapter}
  
  Un  \emph{adapteur de stratégie} est une fonction $\mathcal{S}$ 
  de  $\Nats$ dans l'ensemble des séquences d'entiers 
  qui associe à chaque entier naturel
  $\mathsf{N}$ la suite 
  $S \in  \llbracket 1, n\rrbracket^{\mathds{N}}$.
\end{Def}


On définit par exemple  l'adapteur CIIS (\emph{Chaotic Iterations with Independent Strategy})
paramétré par $(K,y,\alpha,l) \in [0,1]\times [0,1] \times ]0, 0.5[ \times \mathds{N}$
qui associe à chque entier  $n \in \Nats$  la suite
$(S^t)^{t \in \mathds{N}}$ définie par:
 \begin{itemize}
 \item $K^0 = \textit{bin}(y) \oplus \textit{bin}(K)$: $K^0$ est le nombre binaire (sur 32 bits)
   égal au ou exclusif (xor) 
   entre les décompositions binaires sur 32 bits des réels $y$ et  $K$
   (il est aussi compris entre 0 et 1),
 \item $\forall t \leqslant l, K^{t+1} = F(K^t,\alpha)$,
 \item $\forall t \leqslant l, S^t = \left \lfloor n \times K^t \right \rfloor + 1$,
 \item $\forall t > l, S^t = 0$,
 \end{itemize}
où  est la fonction chaotique linéaire par morceau~\cite{Shujun1}.
Les paramètres $K$ et $\alpha$ de cet adapteur de stratégie peuvent être vus
comme des clefs. 
On remarque que cette stratégie est unaire.




On peut attribuer à chaque bit du média hôte $x$ sa valeur d'importance 
sous la forme d'un réel.
Ceci se fait à l'aide d'une fonction de signification. 


\begin{Def}[Fonction de signification ]
Une  \emph{fonction de signification } 
est une fonction $u$ qui a toute 
séquence finie de bit $x$ associe la séquence 
$(u^k(x))$ de taille $\mid x \mid$ à valeur dans les réels.
Cette fonction peut dépendre du message $y$ à embarquer, ou non.
\end{Def}

Pour alléger le discours, par la suite, on nottera $(u^k(x))$ pour $(u^k)$ 
lorsque cela n'est pas ambigüe.
Il reste à partionner les bits  de $x$ selon qu'ils sont 
peu, moyennement ou très significatifs. 

\begin{Def}[Signification des bits]\label{def:msc,lsc}
Soit $u$ une fonction de signification, 
$m$ et  $M$ deux réels  t.q. $m < M$.  Alors:
$u_M$, $u_m$ et $u_p$ sont les vecteurs finis respectivements des 
\emph{bits les plus significatifs  (MSBs)} de $x$,
\emph{bits les moins significatifs (LSBs)} de $x$ 
\emph{bits passifs} of $x$ définis par:
\begin{eqnarray*}
  u_M &=& \left( k ~ \big|~ k \in \mathds{N} \textrm{ et } u^k 
    \geqslant M \textrm{ et }  k \le \mid x \mid \right) \\
  u_m &=& \left( k ~ \big|~ k \in \mathds{N} \textrm{ et } u^k 
  \le m \textrm{ et }  k \le \mid x \mid \right) \\
   u_p &=& \left( k ~ \big|~ k \in \mathds{N} \textrm{ et } 
u^k \in ]m;M[ \textrm{ et }  k \le \mid x \mid \right)
\end{eqnarray*}
 \end{Def}

On peut alors définir une fonction de décompostion  
puis de recomposition pour un hôte $x$:


\begin{Def}[Fonction de décomposition ]
Soit $u$ une fonction de signification, 
$m$ et $M$ deux réels t.q  $m < M$.  
Tout hôte $x$ peut se décomposer en
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$
avec 
\begin{itemize}
\item $u_M$, $u_m$, et  $u_p$ construits comme à la définition~\label{def:msc,lsc},
\item $\phi_{M} = \left( x^{u^1_M}, x^{u^2_M}, \ldots,x^{u^{|u_M|}_M}\right)$,
\item $\phi_{m} = \left( x^{u^1_m}, x^{u^2_m}, \ldots,x^{u^{|u_m|}_m} \right)$,
\item $\phi_{p} =\left( x^{u^1_p}, x^{u^2_p}, \ldots,x^{u^{|u_p|}_p}\right) $.
\end{itemize}
La fonction qui associe $(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$
pour chaque hôte $x$ est la  \emph{fonction de décomposition}, plus tard notée 
$\textit{dec}(u,m,M)$ puisqu'elle est paramétrée par 
$u$, $m$ and $M$. 
\end{Def} 


\begin{Def}[Recomposition]
Soit un sextuplet 
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p}) \in 
\mathfrak{N} \times 
\mathfrak{N} \times 
\mathfrak{N} \times 
\mathfrak{B} \times 
\mathfrak{B} \times 
\mathfrak{B} 
$ tel que
\begin{itemize}
\item les ensembles $u_M$, $u_m$ et  $u_p$ forment une partition de  $[n]$;
\item $|u_M| = |\varphi_M|$, $|u_m| = |\varphi_m|$ et $|u_p| = |\varphi_p|$.  
\end{itemize}
Soit la base canonique sur l'espace vectoriel $\mathds{R}^{\mid x \mid}$ composée des vecteurs 
 $e_1, \ldots, e_{\mid x \mid}$.
On peut construire le vecteur 
\[
x = 
\sum_{i=1}^{|u_M|} \varphi^i_M . e_{{u^i_M}} +  
\sum_{i=1}^{|u_m|} \varphi^i_m .e_{{u^i_m}} +  
\sum_{i=1}^{|u_p|} \varphi^i_p. e_{{u^i_p}} 
\]
La fonction qui associe $x$ à chaque sextuplet 
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ défini comme ci-dessus est appelée 
\emph{fonction de recomposition}.
\end{Def}

Un embarquement consiste à modifier les valeurs de  
$\phi_{m}$ (de $x$) en tenant compte de $y$. 
Cela se formalise comme suit:

\begin{Def}[Embarquement de message]
Soit une fonction de décomposition  $\textit{dec}(u,m,M)$,  
$x$ un support, 
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ son image par $\textit{dec}(u,m,M)$, 
et $y$ un média numérique de taille $|u_m|$.
Le média $z$ résultant de l'embarquement d'$y$ dans $x$ est l'image de 
$(u_M,u_m,u_p,\phi_{M},y,\phi_{p})$
par la fonction de recomposition $\textit{rec}$.
%  avec 
% $g : \Bool^{|u_m|} \times \Bool^{|u_m|} \to \Bool^{|u_m|} $
% est la fonction de modification des bits de $u_m$ selon $y$.
\end{Def}

 
On peut étendre l'algorithme dhCI~\cite{gfb10:ip} d'embarquement de message comme suit:  

\begin{Def}[Embarquement dhCI étendu]
 \label{def:dhCI:ext}
Soit $\textit{dec}(u,m,M)$ une function de décomposition,
$f$ un mode, 
$\mathcal{S}$ un adapteur de stratégie,
$x$ un hôte, 
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ 
sont image par  $\textit{dec}(u,m,M)$,
$q$ un entier naturel positif
et $y$ un média numérique de taille $l=|u_m|$.

L'algorithme d'embarquement de message associe à chaque 
couple $(x,y)$  le média  $z$ résultat de l'embarquement de 
$\hat{y}$ dans $x$, t. q.:

\begin{itemize}
\item le mode $f$ est instancié avec le paramètre $l=|u_m|$, engendrant la 
  fonction $f_{l}:\Bool^{l} \rightarrow \Bool^{l}$;
\item l'adapteur de stratégie $\mathcal{S}$ est intancié avec le paramètre
$y$, engendrant une stratégie $S_y \in [l]$;
\item on itère la fonction $G_{f_l}$ en prenant la configuration
  initiale $(S_y,\phi_{m})$ selon le schéma défini 
  à l'équation~(\ref{eq:sch:unaire}). 
\item $\hat{y}$ est le second membre du $q^{\textrm{ème}}$ terme obtenu.
\end{itemize}
\end{Def}


La figure~\ref{fig:organigramme} synthétise la démarche.

\begin{figure}[ht]
\centering
%\includegraphics[width=8.5cm]{organigramme2.pdf}
\includegraphics[width=8.5cm]{organigramme22}
\caption{The dhCI dissimulation scheme}
\label{fig:organigramme}
\end{figure}




\subsection{Détection d'un media marqué}\label{sub:wmdecoding}

On caractérise d'abord ce qu'est un média marqué selon la méthode énoncée 
à la section précédente. On considère que l'on connaît
la marque à embarquer $y$, le support $x$ et que l'on a face à soit un média 
$z$.


\begin{definition}[Média marqué]
Soit $\textit{dec}(u,m,M)$ une fonction de décomposition
$f$ un  mode, 
$\mathcal{S}$ un adapteur de stratégie
$q$ un entier naturel strictement positif,
$y$ un média digital et soit  
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ l'image par 
$\textit{dec}(u,m,M)$  du média  $x$. 
Alors, $z$ est \emph{marqué} avec $y$ si l'image 
par $\textit{dec}(u,m,M)$ of $z$ is 
$(u_M,u_m,u_p,\phi_{M},\hat{y},\phi_{p})$, où
$\hat{y}$ est le second membre de  $G_{f_l}^q(S_y,\phi_{m})$.
\end{definition}

% Plusieurs stratégies peuvent être utilisées pour déterminer si une image $z$ 
% est marquée, en particulier si l'image a été attaquée entre temps.
% On s'intéressera aux mesures de similarité entre $x$ et $z$.

\section{Analyse de sécurité}\label{sec:security}




As far as we know, Cachin~\cite{Cachin2004}
produces the first fundamental work in information hiding security:
in the context of steganography, the attempt of an attacker to distinguish 
between an innocent image and a stego-content is viewed as an hypothesis 
testing problem.
Mittelholzer~\cite{Mittelholzer99} next proposed the first theoretical 
framework for analyzing the security of a watermarking scheme.
Clarification between  robustness and security 
and classifications of watermarking attacks
have been firstly presented by Kalker~\cite{Kalker2001}.
This work has been deepened by Furon \emph{et al.}~\cite{Furon2002}, who have translated Kerckhoffs' principle (Alice and Bob shall only rely on some previously shared secret for privacy), from cryptography to data hiding. 

More recently~\cite{Cayre2005,Perez06} classified the information hiding  
attacks into categories, according to the type of information the attacker (Eve)
has access to:
\begin{itemize}
\item in Watermarked Only Attack (WOA) she only knows embedded contents $z$;
\item in Known Message Attack (KMA) she knows pairs $(z,y)$ of embedded
  contents and corresponding messages;
\item in Known Original Attack (KOA) she knows several pairs $(z,x)$ 
  of embedded contents and their corresponding original versions;
\item in Constant-Message Attack (CMA) she observes several embedded
  contents $z^1$,\ldots,$z^k$ and only knows that the unknown 
  hidden message $y$ is the same in all contents.
\end{itemize}

To the best of our knowledge, 
KMA, KOA, and CMA have not already been studied
due to the lack of theoretical framework.
In the opposite, security of data hiding against WOA can be evaluated,
by using a probabilistic approach recalled below.




\subsection{Stego-security}\label{sub:stegosecurity}
%\input{stegosecurity}


In the Simmons' prisoner problem~\cite{Simmons83}, 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 named Eve, who eavesdrops all contents and can choose
to interrupt the communication if they appear to be stego-contents.

Stego-security,  defined in  this well-known  context, is  the  highest security
class in Watermark-Only  Attack setup, which occurs when Eve  has only access to
several marked contents~\cite{Cayre2008}.


Let $\mathds{K}$ be the set of embedding keys, $p(X)$ the probabilistic model of
$N_0$ initial  host contents,  and $p(Y|K)$ the  probabilistic model  of $N_0$
marked contents s.t. each host  content has  been marked
with the same key $K$ and the same embedding function.

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





%Let $\mathds{K}$ be the set of embedding keys, $p(X)$ the probabilistic model of
%$N_0$ initial  host contents,  and $p(Y|K)$ the  probabilistic model  of $N_0$
%marked contents s.t. each host  content has  been marked
%with the same key $K$ and the same embedding function.

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

 Stego-security  states that  the knowledge  of  $K$ does  not help  to make  the
 difference  between $p(X)$ and  $p(Y)$.  This  definition implies  the following
 property:
 $$p(Y|K_1)= \cdots = p(Y|K_{N_k})=p(Y)=p(X)$$ 
 This property is equivalent to  a zero Kullback-Leibler divergence, which is the
 accepted definition of the "perfect secrecy" in steganography~\cite{Cachin2004}.


\subsection{The negation mode is stego-secure}
To make this article self-contained, this section recalls theorems and proofs of stego-security for negation mode published in~\cite{gfb10:ip}.

\begin{proposition} \emph{dhCI dissimulation}  of Definition \ref{def:dhCI} with
negation mode and  CIIS strategy-adapter is stego-secure, whereas  it is not the
case when using CIDS strategy-adapter.
\end{proposition}


\begin{proof}   On   the    one   hand,   let   us   suppose    that   $X   \sim
\mathbf{U}\left(\mathbb{B}^n\right)$  when  using  \linebreak CIIS$(K,\_,\_,l)$.
We  prove  by  a
mathematical   induction   that   $\forall    t   \in   \mathds{N},   X^t   \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^t
\sim  \mathbf{U}\left(\mathbb{B}^n\right)$  holds  until for  some $t$. 
Let  $e  \in
\mathbb{B}^n$   and   \linebreak   $\mathbf{B}_k=(0,\cdots,0,1,0,\cdots,0)   \in
\mathbb{B}^n$ (the digit $1$ is in position $k$).

So    
$P\left(X^{t+1}=e\right)=\sum_{k=1}^n
P\left(X^t=e\oplus\mathbf{B}_k,S^t=k\right)$ where  
$\oplus$ is again the bitwise exclusive or. 
These  two events are  independent when
using CIIS strategy-adapter 
(contrary to CIDS, CIIS is not built by using $X$),
 thus:
$$P\left(X^{t+1}=e\right)=\sum_{k=1}^n
P\left(X^t=e\oplus\mathbf{B}_k\right) \times  P\left(S^t=k\right).$$ 

According to the
inductive    hypothesis:   $P\left(X^{n+1}=e\right)=\frac{1}{2^n}   \sum_{k=1}^n
P\left(S^t=k\right)$.  The set  of events $\left \{ S^t=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^t=k\right)=1$.                  Finally,
$P\left(X^{t+1}=e\right)=\frac{1}{2^n}$,   which    leads   to   $X^{t+1}   \sim
\mathbf{U}\left(\mathbb{B}^n\right)$.   This  result  is  true  for all  $t  \in
\mathds{N}$ and then for $t=l$.

Since $P(Y|K)$ is $P(X^l)$ that is proven to be equal to $P(X)$,
we thus  have established that, 
$$\forall K  \in [0;1], P(Y|K)=P(X^{l})=P(X).$$ 
So   dhCI   dissimulation   with   CIIS
strategy-adapter is stego-secure.

On  the  other  hand,  due  to  the  definition  of  CIDS,  we  have  \linebreak
$P(Y=(1,1,\cdots,1)|K)=0$. 
%\JFC{Pourquoi? Justifier davantage là ou dans la def de CIDS}
So   there  is   no  uniform  repartition   for  the stego-contents $Y|K$.
\end{proof}



To sum up, Alice  and Bob can counteract Eve's attacks in  WOA setup, when using
dhCI dissimulation with  CIIS strategy-adapter.  To our best  knowledge, this is
the second time an information hiding scheme has been proven to be stego-secure:
the   former  was   the  spread-spectrum   technique  in   natural  marking
configuration with $\eta$ parameter equal to 1 \cite{Cayre2008}.





\subsection{A new class of $\varepsilon$-stego-secure schemes}

Let us prove that,
\begin{theorem}\label{th:stego}
Let $\epsilon$ be positive,
$l$ be any size of LSCs, 
$X   \sim \mathbf{U}\left(\mathbb{B}^l\right)$,
$f_l$ be an image mode s.t. 
$\Gamma(f_l)$ is strongly connected and 
the Markov matrix associated to $f_l$ 
is doubly stochastic. 
In the instantiated \emph{dhCI dissimulation} algorithm 
with any uniformly distributed (u.d.) strategy-adapter 
that is independent from $X$,  
there exists some positive natural number $q$ s.t.
$|p(X^q)- p(X)| < \epsilon$. 
\end{theorem}


\begin{proof}   
Let $\textit{deci}$ be the bijection between $\Bool^{l}$ and 
$\llbracket 0, 2^l-1 \rrbracket$ that associates the decimal value
of any  binary number in $\Bool^{l}$.
The probability $p(X^t) = (p(X^t= e_0),\dots,p(X^t= e_{2^l-1}))$ for $e_j \in \Bool^{l}$ is thus equal to 
$(p(\textit{deci}(X^t)= 0,\dots,p(\textit{deci}(X^t)= 2^l-1))$ further denoted by $\pi^t$.
Let $i \in \llbracket 0, 2^l -1 \rrbracket$, 
the probability $p(\textit{deci}(X^{t+1})= i)$  is 
\[
 \sum\limits^{2^l-1}_{j=0}  
\sum\limits^{l}_{k=1} 
p(\textit{deci}(X^{t}) = j , S^t = k , i =_k j , f_k(j) = i_k ) 
\]
\noindent 
where $ i =_k j $ is true iff the binary representations of 
$i$ and $j$ may only differ for the  $k$-th element,
and where 
$i_k$ abusively denotes, in this proof, the $k$-th element of the binary representation of 
$i$.

Next, due to the proposition's hypotheses on the strategy,
$p(\textit{deci}(X^t) = j , S^t = k , i =_k j, f_k(j) = i_k )$ is equal to  
$\frac{1}{l}.p(\textit{deci}(X^t) = j ,  i =_k j, f_k(j) = i_k)$.
Finally, since $i =_k j$ and $f_k(j) = i_k$ are constant during the 
iterative process  and thus does not depend on $X^t$, we have 
\[
\pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0}
\pi^t_j.\frac{1}{l}  
\sum\limits^{l}_{k=1} 
p(i =_k j, f_k(j) = i_k ).
\]

Since 
$\frac{1}{l}  
\sum\limits^{l}_{k=1} 
p(i =_k j, f_k(j) = i_k ) 
$ is equal to $M_{ji}$ where  $M$ is the Markov matrix associated to
 $f_l$ we thus have
\[
\pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0}
\pi^t_j. M_{ji} \textrm{ and thus }
\pi^{t+1} = \pi^{t} M.
\]

% The calculus of $p(X^{t+1} = e)$ is thus equal to 
% $\pi^{t+1}_i$. 

First of all, 
since the graph $\Gamma(f)$ is strongly connected,
then for all vertices $i$ and $j$, a path can
be  found to  reach $j$  from $i$  in at  most $2^l$  steps.  
There  exists thus $k_{ij} \in \llbracket 1,  2^l \rrbracket$ s.t.
${M}_{ij}^{k_{ij}}>0$.  
As all the multiples $l \times k_{ij}$ of $k_{ij}$ are such that 
${M}_{ij}^{l\times  k_{ij}}>0$, 
we can  conclude that, if
$k$ is the least common multiple of $\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^l \rrbracket  \}$ thus 
$\forall i,j  \in \llbracket  1, 2^l \rrbracket,  {M}_{ij}^{k}>0$ and thus 
$M$ is a regular stochastic matrix.


Let us now recall the following stochastic matrix theorem:
\begin{theorem}[Stochastic Matrix]
  If $M$ is a regular stochastic matrix, then $M$ 
  has an unique stationary  probability vector $\pi$. Moreover, 
  if $\pi^0$ is any initial probability vector and 
  $\pi^{t+1} = \pi^t.M $ for $t = 0, 1,\dots$ then the Markov chain $\pi^t$
  converges to $\pi$ as $t$ tends to infinity.
\end{theorem}

Thanks to this theorem, $M$ 
has an unique stationary  probability vector $\pi$. 
By hypothesis, since $M$ is doubly stochastic we have 
$(\frac{1}{2^l},\dots,\frac{1}{2^l}) = (\frac{1}{2^l},\dots,\frac{1}{2^l})M$
and thus $\pi =  (\frac{1}{2^l},\dots,\frac{1}{2^l})$.
Due to the matrix theorem, there exists some 
$q$ s.t. 
$|\pi^q- \pi| < \epsilon$
and the proof is established.
Since $p(Y| K)$ is $p(X^q)$ the method is then $\epsilon$-stego-secure
provided the strategy-adapter is uniformly distributed.
 \end{proof}

This section has focused on security with regards to probabilistic behaviors. 
Next section studies it in the perspective of topological ones.



%\subsection{Security in KMA, KOA and CMA setups}
%\input{KMOA.tex}