From: cguyeux Date: Wed, 12 Sep 2012 12:32:25 +0000 (+0200) Subject: Fin des travaux sur l'article X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/commitdiff_plain/5ccd7174adc0881aa861c67d36462da62a3cb158?ds=sidebyside;hp=a12a11a39f112c043de69e8694f29b32b8c7dbc5 Fin des travaux sur l'article --- diff --git a/mabase.bib b/mabase.bib index 41edde2..658392c 100644 --- a/mabase.bib +++ b/mabase.bib @@ -14,6 +14,19 @@ timestamp = {2009.06.29} } +@BOOK{Knuth97, + title = {Seminumerical Algorithms}, + publisher = {Addison-Wesley, Reading, MA, USA}, + year = {1997}, + author = {D. E. Knuth}, + volume = {3}, + edition = {Third Edition}, + owner = {guyeux}, + timestamp = {2012.02.15} +} + + + @book{guyeux12:bc, inhal = {no}, domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO}, diff --git a/prng_gpu.tex b/prng_gpu.tex index a32d94a..2156752 100644 --- a/prng_gpu.tex +++ b/prng_gpu.tex @@ -207,10 +207,11 @@ Section~\ref{sec:experiments}. We show in Section~\ref{sec:security analysis} that, if the inputted generator is cryptographically secure, then it is the case too for the generator provided by the post-treatment. +\begin{color}{red} A practical +security evaluation is also outlined in Section~\ref{sec:Practicak evaluation}.\end{color} Such a proof leads to the proposition of a cryptographically secure and chaotic generator on GPU based on the famous Blum Blum Shub -in Section~\ref{sec:CSGPU}, \begin{color}{red} to a practical -security evaluation in Section~\ref{sec:Practicak evaluation}, \end{color} and to an improvement of the +in Section~\ref{sec:CSGPU} and to an improvement of the Blum-Goldwasser protocol in Sect.~\ref{Blum-Goldwasser}. This research work ends by a conclusion section, in which the contribution is summarized and intended future work is presented. @@ -672,8 +673,8 @@ N \text{ if }\sum_{i=0}^{N-1}{C^i_{32}}\leqslant{y^n}<1.\\ \subsection{Improving the Speed of the Former Generator} -Instead of updating only one cell at each iteration,\begin{color}{red} we now propose to choose a -subset of components and to update them together, for speed improvements. Such a proposition leads\end{color} +Instead of updating only one cell at each iteration, \begin{color}{red} we now propose to choose a +subset of components and to update them together, for speed improvements. Such a proposition leads \end{color} to a kind of merger of the two sequences used in Algorithms \ref{CI Algorithm} and \ref{Chaotic iteration1}. When the updating function is the vectorial negation, this algorithm can be rewritten as follows: @@ -1522,7 +1523,9 @@ version\label{IR}} \label{algo:gpu_kernel2} \end{algorithm} -\subsection{Theoretical Evaluation of the Improved Version} +\begin{color}{red} +\subsection{Chaos Evaluation of the Improved Version} +\end{color} A run of Algorithm~\ref{algo:gpu_kernel2} consists in an operation ($x=x\oplus t$) having the form of Equation~\ref{equation Oplus}, which is equivalent to the iterative @@ -1620,18 +1623,27 @@ as it is shown in the next sections. \section{Security Analysis} + + +\begin{color}{red} +This section is dedicated to the security analysis of the + proposed PRNGs, both from a theoretical and a practical points of view. + +\subsection{Theoretical Proof of Security} \label{sec:security analysis} -\PCH{This section is dedicated to the analysis of the security of the - proposed PRNGs from a theoretical point of view. The standard definition +The standard definition of {\it indistinguishability} used is the classical one as defined for - instance in~\cite[chapter~3]{Goldreich}. It is important to emphasize that - this property shows that predicting the future results of the PRNG's - cannot be done in a reasonable time compared to the generation time. This + instance in~\cite[chapter~3]{Goldreich}. + This property shows that predicting the future results of the PRNG + cannot be done in a reasonable time compared to the generation time. It is important to emphasize that this is a relative notion between breaking time and the sizes of the keys/seeds. Of course, if small keys or seeds are chosen, the system can be broken in practice. But it also means that if the keys/seeds are large - enough, the system is secured.} + enough, the system is secured. +As a complement, an example of a concrete practical evaluation of security +is outlined in the next subsection. +\end{color} In this section the concatenation of two strings $u$ and $v$ is classically denoted by $uv$. @@ -1653,7 +1665,15 @@ internal coin tosses of $D$. Intuitively, it means that there is no polynomial time algorithm that can distinguish a perfect uniform random generator from $G$ with a non -negligible probability. The interested reader is referred +negligible probability. +\begin{color}{red} + An equivalent formulation of this well-known +security property means that it is possible +\emph{in practice} to predict the next bit of +the generator, knowing all the previously +produced ones. +\end{color} +The interested reader is referred to~\cite[chapter~3]{Goldreich} for more information. Note that it is quite easily possible to change the function $\ell$ into any polynomial function $\ell^\prime$ satisfying $\ell^\prime(m)>m)$~\cite[Chapter 3.3]{Goldreich}. @@ -1741,6 +1761,100 @@ proving that $H$ is not secure, which is a contradiction. \end{proof} + +\begin{color}{red} +\subsection{Practical Security Evaluation} +\label{sec:Practicak evaluation} + +Pseudorandom generators based on Eq.~\eqref{equation Oplus} are thus cryptographically secure when +they are XORed with an already cryptographically +secure PRNG. But, as stated previously, +such a property does not mean that, whatever the +key size, no attacker can predict the next bit +knowing all the previously released ones. +However, given a key size, it is possible to +measure in practice the minimum duration needed +for an attacker to break a cryptographically +secure PRNG, if we know the power of his/her +machines. Such a concrete security evaluation +is related to the $(T,\varepsilon)-$security +notion, which is recalled and evaluated in what +follows, for the sake of completeness. + +Let us firstly recall that, +\begin{definition} +Let $\mathcal{D} : \mathds{B}^M \longrightarrow \mathds{B}$ be a probabilistic algorithm that runs +in time $T$. +Let $\varepsilon > 0$. +$\mathcal{D}$ is called a $(T,\varepsilon)-$distinguishing attack on pseudorandom +generator $G$ if + +\begin{flushleft} +$\left| Pr[\mathcal{D}(G(k)) = 1 \mid k \in_R \{0,1\}^\ell ]\right.$ +\end{flushleft} + +\begin{flushright} +$ - \left. Pr[\mathcal{D}(s) = 1 \mid s \in_R \mathds{B}^M ]\right| \geqslant \varepsilon,$ +\end{flushright} + +\noindent where the probability is 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{definition} + +Let us recall that the running time of a probabilistic algorithm is defined to be the +maximum of the expected number of steps needed to produce an output, maximized +over all inputs; the expected number is averaged over all coin flips made by the algorithm~\cite{Knuth97}. +We are now able to define the notion of cryptographically secure PRNGs: + +\begin{definition} +A pseudorandom generator is $(T,\varepsilon)-$secure if there exists no $(T,\varepsilon)-$distinguishing attack on this pseudorandom generator. +\end{definition} + + + + + + + +Suppose now that the PRNG of Eq.~\eqref{equation Oplus} will work during +$M=100$ time units, and that during this period, +an attacker can realize $10^{12}$ clock cycles. +We thus wonder whether, during the PRNG's +lifetime, the attacker can distinguish this +sequence from truly random one, with a probability +greater than $\varepsilon = 0.2$. +We consider that $N$ has 900 bits. + +Predicting the next generated bit knowing all the +previously released ones by Eq.~\eqref{equation Oplus} is obviously equivalent to predict the +next bit in the BBS generator, which +is cryptographically secure. More precisely, it +is $(T,\varepsilon)-$secure: no +$(T,\varepsilon)-$distinguishing attack can be +successfully realized on this PRNG, if~\cite{Fischlin} +\begin{equation} +T \leqslant \dfrac{L(N)}{6 N (log_2(N))\varepsilon^{-2}M^2}-2^7 N \varepsilon^{-2} M^2 log_2 (8 N \varepsilon^{-1}M) +\label{mesureConcrete} +\end{equation} +where $M$ is the length of the output ($M=100$ in +our example), and $L(N)$ is equal to +$$ +2.8\times 10^{-3} exp \left(1.9229 \times (N ~ln(2)^\frac{1}{3}) \times ln(N~ln 2)^\frac{2}{3}\right) +$$ +is the number of clock cycles to factor a $N-$bit +integer. + + + + +A direct numerical application shows that this attacker +cannot achieve its $(10^{12},0.2)$ distinguishing +attack in that context. + +\end{color} + + \section{Cryptographical Applications} \subsection{A Cryptographically Secure PRNG for GPU} @@ -1864,46 +1978,41 @@ It should be noticed that this generator has once more the form $x^{n+1} = x^n where $S^n$ is referred in this algorithm as $t$: each iteration of this PRNG ends with $x = x \wedge t$. This $S^n$ is only constituted by secure bits produced by the BBS generator, and thus, due to -Proposition~\ref{cryptopreuve}, the resulted PRNG is cryptographically -secure. - - +Proposition~\ref{cryptopreuve}, the resulted PRNG is +cryptographically secure. \begin{color}{red} -\subsection{Practical Security Evaluation} -\label{sec:Practicak evaluation} - -Suppose now that the PRNG will work during -$M=100$ time units, and that during this period, -an attacker can realize $10^{12}$ clock cycles. -We thus wonder whether, during the PRNG's -lifetime, the attacker can distinguish this -sequence from truly random one, with a probability -greater than $\varepsilon = 0.2$. -We consider that $N$ has 900 bits. - -The random process is the BBS generator, which -is cryptographically secure. More precisely, it -is $(T,\varepsilon)-$secure: no -$(T,\varepsilon)-$distinguishing attack can be -successfully realized on this PRNG, if~\cite{Fischlin} -$$ -T \leqslant \dfrac{L(N)}{6 N (log_2(N))\varepsilon^{-2}M^2}-2^7 N \varepsilon^{-2} M^2 log_2 (8 N \varepsilon^{-1}M) -$$ -where $M$ is the length of the output ($M=100$ in -our example), and $L(N)$ is equal to -$$ -2.8\times 10^{-3} exp \left(1.9229 \times (N ~ln(2)^\frac{1}{3}) \times ln(N~ln 2)^\frac{2}{3}\right) -$$ -is the number of clock cycles to factor a $N-$bit -integer. - -A direct numerical application shows that this attacker -cannot achieve its $(10^{12},0.2)$ distinguishing -attack in that context. - +As stated before, even if the proposed PRNG is cryptocaphically +secure, it does not mean that such a generator +can be used as described here when attacks are +awaited. The problem is to determine the minimum +time required for an attacker, with a given +computational power, to predict under a probability +lower than 0.5 the $n+1$th bit, knowing the $n$ +previous ones. The proposed GPU generator will be +useful in a security context, at least in some +situations where a secret protected by a pseudorandom +keystream is rapidly obsolete, if this time to +predict the next bit is large enough when compared +to both the generation and transmission times. +It is true that the prime numbers used in the last +section are very small compared to up-to-date +security recommends. However the attacker has not +access to each BBS, but to the output produced +by Algorithm~\ref{algo:bbs_gpu}, which is quite +more complicated than a simple BBS. Indeed, to +determine if this cryptographically secure PRNG +on GPU can be useful in security context with the +proposed parameters, or if it is only a very fast +and statistically perfect generator on GPU, its +$(T,\varepsilon)-$security must be determined, and +a formulation similar to Eq.\eqref{mesureConcrete} +must be established. Authors +hope to achieve to realize this difficult task in a future +work. \end{color} + \subsection{Toward a Cryptographically Secure and Chaotic Asymmetric Cryptosystem} \label{Blum-Goldwasser} We finish this research work by giving some thoughts about the use of