tt

[HindawiJournalOfChaos.git] / IH / IIHMSP13_2.tex

\section{A Cryptographic Approach for Steganography}

Our last reflections in the field of information hiding are theoretical ones, 
discussing the relevance of current security notions in this field. Results
of these thoughts, published in a second accepted paper at IIHMSP'13
(9th Int. Conf. on Intelligent Information Hiding and Multimedia Signal Processing, Beijing, China)
 are given thereafter~\cite{bgh13:ip}.

\subsection{Drawbacks of the stego-security notion}
\label{sec:drawbacks}

Theoretically speaking, the stego-security notion matches well with the idea of a perfect 
secrecy in the WOA category of attacks. However, its concrete verification raises
several technical problems difficult to get around. These difficulties impact drastically
the effective security of the scheme, as explained in~\cite{bgh13:ip}.

For instance, in a stego-secure scheme, the distribution of the set of watermarked 
images must be the same than the one of the original contents, no matter the chosen keys.
But \emph{how to determine practically the distribution of the original contents?} 
Furthermore, claiming that Alice can constitutes her own subset of well-chosen images having 
the same ``good'' distribution is quite unreasonable in several contexts of 
steganography: Alice has not \emph{always} the choice of the supports. Moreover, 
it introduces a kind of bias, as the warden can find such similarities surprising.
 Suppose however that Alice is in the best situation for her, that is, she has the possibility to 
constitute herself the set of original contents. How can she proceed practically 
to be certain that all media into the set follow a same distribution $p(X)$?
According to the authors opinion, Alice has two possible choices:
\begin{enumerate}
\item Either she constitutes the set by testing, for each new content, whether this media has a same distribution than the ones that have been already selected.
\item Or she forges directly new images by using existing ones. For instance, she can replace all the
least significant bits of the original contents by using a good pseudorandom number generator.
\end{enumerate}

In the first situation, Alice will realize a $\chi^2$ test, or other statistical tests of this kind,
 to determine if the considered image (its least significant bits, or its low frequency coefficients, etc.) has a same distribution than images already selected. In that situation, Alice
 does not have the liberty to choose the distribution, and it seems impossible to find a scheme
being able to preserve any kind of distribution, for all secret keys and all hidden messages.
Furthermore, such statistical hypothesis testings are not ideal ones, as they only regard if a result is unlikely to have occurred by chance alone \emph{according to a pre-determined threshold probability} (the significance level). Errors of the first (false positive) and second kind (false negative) occur necessarily, with a certain probability. In other words, with such an approach, Alice
cannot design a perfect set of cover contents having all the same probability $p(X)$. 
This process leads to a set of media that follows a distribution Alice does not have access to.

The second situation seems more realistic, it will thus be 
further investigated in the next section~\cite{bgh13:ip}.







% \section{New Scenarios of (Secure) Information Hiding}
% \label{scenarii}
% We give in this section some original situations that are
% obviously related to steganography, while being out of scope of
% the topics usually investigated by the information hiding community.
% These basic scenarios deal with hidden messages embedded into
% cover contents in a secure manner. In these scenarios, the 
% channel obviously appears as sleazy, but the observer cannot
% deduce anything else (if he cannot break the channel, then
% he lost everything). The theoretical framework that will 
% be presented in the next sections can be used to evaluate the
% security of the approaches proposed thereafter.
% 
% \subsection{A First Theoretical Scenario}
% 
% Let us suppose that the set of supports $\mathcal{A}$ is constituted by random binary words. In that condition, a perfect secret hiding can be obtained by replacing a given part of a support with the encrypted hidden message, where the encryption has been obtained by a one time pad method: a bitwise exclusive or between the hidden message and a given random sequence, called the keystream.
% If Alice and Bob have previously shared the keystream, they can thus attain by this way the level of perfect secrecy, as it is defined in the theory of Shannon, and applied in information
% hiding. It is true that this example is somewhat unrealistic:
% man can reasonably think that Alice should prefer to simply
% encrypt her messages instead of hiding them into encrypted data.
% However, it is a proof of concept in steganography showing 
% that, if Alice has the choice of the cover set and Eve cannot
% break the channel, then Alice can reach a perfect secrecy in
% information hiding. And she can be certain that (1) it is
% impossible for the warden to determine which cover images 
% contain hidden messages and (2) the content of these messages.
% Additionally of being a proof of concept, this example 
% illustrate that a clear framework must be provided, taking
% into account who chooses the set of cover images, the 
% objectives Eve wants to reach and the means she can use, and
% so on.
% 
% In practice, Alice and Bob can construct their set $\mathcal{A}$ by using several times a cryptographically secure pseudorandom number generator (PRNG) as ISAAC~\cite{Jenkins96} or BBS~\cite{BBS}.
% The keystream can be produced too by this kind of PRNG, leading to a practicable exchange of media that can embed, with no risk, hidden messages: the proposed stegosystem is obviously both realizable and cryptographically secure. Another 
% possibility is to put such encrypted hidden messages into 
% encrypted media, both encryption being realized by a 
% cryptographically secure cryptosystem. Indeed, in these two 
% situations, no one can
% make in practice the distinction between images of $\mathcal{A}$ with hidden messages and images without such messages.
% 
% %An adversary can have some suspicions, because it is not very common to possess random images in his hard disk. However such suspicions can be at least limited by the following arguments. Firstly, 
% Even though this first scenario do not pretend to be applicable
% for Internet exchanges, it can however provide a first
% concrete operational and secured steganographic scheme for 
% file storage. Indeed,
% anyone has the right to possess encrypted data. The set $\mathcal{A}$ can be constituted by encrypted data and random data, some of these latter embedding hidden messages. Encrypted data can be corrupted: the encrypted data that contain hidden messages will not return a problem of wrong decryption key, but of corrupted file. Obviously, it is not the fault of Alice if her file system has some problems.
% Concerning random files, technicians, scientists, or engineers can justify their presence by experiments related to their works.
% Finally, when trying to recover data after a clash of the system, or an hard drive critical problem, recovered data are often partial or corrupted. Thus, a third possibility is to dissimulate the stegocontent into the free space of the disk, to make that it appears as a residue of a removed encrypted file. A practical solution is to remove the encrypted file after having dissimulated an hidden message in it: it will be possible to recover it by using appropriate recovery tools.
% 
% 
% 
% \subsection{A Second Scenario}
% 
% A second more realistic scenario to achieve in practice the
%  cryptographically secures information hiding is
% to erase all the least significant bits (LSBs) of all the images (stored in a disk, exchanged through the Internet, etc.), and replace them by using a cryptographically secure PRNG.
% The cover set can be constituted by images that have LSBs
% closed to a random law.
% Then, some of these media will embed hidden messages in some places of their LSBs, the hidden messages being encrypted as previously.
% 
% By doing so, the allure of the media can appears suspicious, but no adversary can deduce anything else: in practice, they cannot determine whether an image has an hidden message or not. This randomness in LSBs can be explained in several ways
% (images of low quality, filters, etc.). Moreover Alice, being accused by Eve to have possibly hidden messages in their suspicious images, can discover some unimportant secrets, without revealing important messages: Eve has no possibility to determine how much messages have been hidden.
% 
% It is true that Eve can remove all these LSBs, because they are suspicious. Indeed, natural images have not, in general, random LSBs. For instance, in the image depicted in Fig.~\ref{Chibouki}, produced by a camera, the LSBs are not random.
% The number of 0's is 1825023 when the number of 1's is equal to 1876161. Thus a chisquared test of adaptation to an uniform distribution, with risk $\alpha=0.05$, fails completely, as
% $$ \dfrac{(x_0-\overline{x}_0)^2}{\overline{x}_0}+ \dfrac{(x_1-\overline{x}_1)^2}{\overline{x}_1} = 706.556 > 3.841,$$
% \noindent where $\overline{x}_0=\overline{x}_1=1850592$ are the intended occurrences of 0's and 1's in a binary sequence of size 3701184 when considering a uniform distribution, whereas $x_0$ and $x_1$ are for the obtained occurrences.
% 
% \begin{figure}
% \centering
% \includegraphics{chibouki.jpg}
% \caption{Chibouki, the natural image}
% \label{Chibouki}
% \end{figure}
% 
% 
% Thus Eve, finding surprisingly a uniform distribution in LSBs, can consider it as suspicious.
% And then, even if she cannot determine the subset of these suspicious images that contains hidden messages,
% she can at least remove the hidden channel (in case of communications through the Internet, for instance).
% 
% However, Alice and Bob knows that LSBs are not the good place to hide their messages.
% Indeed, they can find bits in images that seems to be random
%  (for instance, a well chosen subset of LSBs), 
% systematically replace these bits
% by other ones produced using a cryptographically secure PRNG, and hide in some of them their encrypted
% messages. More concretely, let us consider the matrix H2 of the Daubechies db1 decomposition of Chibouki
% of level 2. For each coefficient of this matrix of size $444 \times 521$, we take the bit parity
% of its integral part. By doing so, we obtain a binary sequence that follows an uniform distribution
% on $\{0,1\}$, according to the chisquared test of risk 0.01:
% $$ \dfrac{(x_0-\overline{x}_0)^2}{\overline{x}_0}+ \dfrac{(x_1-\overline{x}_1)^2}{\overline{x}_1} = 0.073 \leqslant 6.635 .$$
% 
% Thus these bits can be replaced by other ones produced by a cryptographically secure PRNG, and 
% some of these modified images can embed securely encrypted images. To improve the robustness
% of the method, batteries of tests as TestU01 can be applied on bits candidates (in images, movies, 
% sounds) to be replaced by a PRNG, to check if this designed channel can be used not only
% securely, but non suspiciously too.
% \emph{Mutatis mutandis}, the test can be replaced by the
% return of the steganalyzer of Eve: in a fair game that 
% respects the Kerckhoffs' principle, all except the private
% keys are known by the two opposed parties.
% 
% 
% 


\subsection{Toward a cryptographically secure hiding}
\label{sec4}
We recall in this section the theoretical framework for information
hiding security we have proposed in~\cite{bgh13:ip}, which is more closely resembling that
of usual approaches in cryptography, as those presented for PRNGs in Definitions~\ref{cryptoPRNGdef} and \ref{cryptoPRNGdef2}. 
It allows to define the 
notion of steganalyzers, it is compatible with the new original
scenarios of information hiding that have been dressed 
above, and it does not have the drawbacks
 of the stego-security definition.


\subsubsection{Definition of a stegosystem}


\begin{Def}[Stegosystem]
Let $\mathcal{S}, \mathcal{M}$, and $\mathcal{K}=\mathds{B}^\ell$ 
three sets of words on $\mathds{B}$ called respectively the sets of 
supports, of messages, and of keys (of size $\ell$).

A \emph{stegosystem} on $(\mathcal{S}, \mathcal{M}, \mathcal{K})$ 
is a tuple $(\mathcal{I},\mathcal{E}, inv)$ such that:
\begin{itemize}
\item $\mathcal{I}$ is a function from $\mathcal{S} \times \mathcal{M} \times \mathcal{K} $ to $ \mathcal{S}$, 
$(s,m,k) \longmapsto \mathcal{I}(s,m,k)=s'$, 
\item $\mathcal{E}$ is a function from $\mathcal{S} \times \mathcal{K}$ to $\mathcal{M}$, 
$(s,k) \longmapsto \mathcal{E}(s,k) = m'$.
\item $inv$ is a function from $\mathcal{K} $ to $\mathcal{K}$, s.t. $\forall k \in
 \mathcal{K}, \forall (s,m)\in \mathcal{S}\times\mathcal{M},$ \linebreak
$ \mathcal{E}(\mathcal{I}(s,m,k),inv(k))=m$.
\item $\mathcal{I}(s,m,k)$ and $\mathcal{E}(c,k^\prime)$ can be computed in
 polynomial time. 
\end{itemize}
 $\mathcal{I}$ is called the insertion or embedding
function, $\mathcal{E}$ the extraction function, $s$ the host content,
$m$ the hidden message, $k$ the embedding key, $k'=inv(k)$ the extraction key, and
$s'$ is the stego-content. If $\forall k \in \mathcal{K}, k=inv(k)$, the stegosystem is symmetric (private-key), otherwise
it is asymmetric (public-key).
\end{Def}




\subsubsection{Heading notions}



\begin{Def}[$(T,\varepsilon)-$distinguishing attack]
Let $S=(\mathcal{I},\mathcal{E}, inv)$ 
a stegosystem on $(\mathcal{A}, \mathcal{M}, \mathcal{K})$, with 
$\mathcal{A} \subset \mathds{B}^M$.
A $(T,\varepsilon)-$distinguishing attack on the stegosystem $S$
is a probabilistic 
algorithm $\mathcal{D}:\mathcal{A} \longrightarrow \{0,1\}$ in running time $T$, such that
there exists $m \in \mathcal{M}$, %for all $m \in \mathds{B}^{f(\ell(S_i))}$, 
%for all sufficiently large $i$'s,
$$\left| Pr\left[\mathcal{D}\left(\mathcal{I}(s,m,k)\right)=1 \mid k \in_R \mathcal{K}, s \in_R \mathcal{A}\right]
 -Pr\left[\mathcal{D}\left(x\right)=1 \mid x \in_R \mathcal{A}\right]\right|\geqslant \varepsilon ,$$
where the probability is also taken over the internal coin flips of $\mathcal{D}$,
 and the notation $\in_R$ indicates the process of selecting an element at 
random and uniformly over the corresponding set. 
\end{Def}

\begin{Def}
A stegosystem is $(T,\varepsilon)-$un\-dis\-tin\-gui\-sha\-ble if there exists no 
$(T,\varepsilon)-$distinguishing attack on this stegosystem.
\end{Def}



Intuitively, it means that there is no polynomial-time probabilistic algorithm
being able to distinguish the host contents from the stego-contents~\cite{bgh13:ip}.


\subsubsection{A cryptographically secure information hiding scheme}
\label{findutout}
To show the effectiveness of the approach, we have provided and 
proven in~\cite{bgh13:ip} a first cryptographically secure information 
hiding scheme, according to the definition above. 


\begin{Th}
 Let $$\mathcal{S} = \left\{s_1^1, s_2^1,\ldots,s_{2^N}^1, s_1^2,
 s_2^2,\ldots,s_{2^N}^2,\ldots,s_1^r, s_2^r,\ldots,s_{2^N}^r\right\}$$
a subset of $\mathds{B}^M = \mathcal{A}.$
Consider $G:\mathds{B}^L \longrightarrow \mathds{B}^N$ a $(T,\varepsilon)-$secure
pseudorandom number generator, and
$\mathcal{I}(s_j^i,m,k)=s^i_{m\oplus G(k)}$. Assuming that $r$ is a
constant, and that from $i,j$ one can
compute the image $s^i_j$ in time $T_1$, the stegosystem is
$(T-T_1-N-1,\varepsilon)$-secure. 
\end{Th}

Intuitively, $\mathcal{S}$ is built from $r$ images containing $N$ bits
of low information. The image $s^i_j$ corresponds to the $i$-th image where
the $N$ bits are set to $j$.