X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/4797365cf4607caea2473f7ce2f4fe6c3bbf9c51..0be2ff183726ec026c763c2d0f9b4d3a326360fd:/prng_gpu.tex?ds=sidebyside diff --git a/prng_gpu.tex b/prng_gpu.tex index f985e03..38431e5 100644 --- a/prng_gpu.tex +++ b/prng_gpu.tex @@ -40,6 +40,9 @@ \newcommand{\alert}[1]{\begin{color}{blue}\textit{#1}\end{color}} + +\newcommand{\PCH}[1]{\begin{color}{blue}#1\end{color}} + \title{Efficient and Cryptographically Secure Generation of Chaotic Pseudorandom Numbers on GPU} \begin{document} @@ -166,6 +169,25 @@ property. Last, but not least, we propose a rewriting of the Blum-Goldwasser asymmetric key encryption protocol by using the proposed method. + +\PCH{ +{\bf Main contributions.} In this paper a new PRNG using chaotic iteration +is defined. From a theoretical point of view, it is proven that it has fine +topological chaotic properties and that it is cryptographically secured (when +the based PRNG is also cryptographically secured). From a practical point of +view, experiments point out a very good statistical behavior. Optimized +original implementation of this PRNG are also proposed and experimented. +Pseudorandom numbers are generated at a rate of 20GSamples/s, which is faster +than in~\cite{conf/fpga/ThomasHL09,Marsaglia2003} (and with a better +statistical behavior). Experiments are also provided using BBS as the based +random generator. The generation speed is significantly weaker but, as far +as we know, it is the first cryptographically secured PRNG proposed on GPU. +Note too that an original qualitative comparison between topological chaotic +properties and statistical test is also proposed. +} + + + The remainder of this paper is organized as follows. In Section~\ref{section:related works} we review some GPU implementations of PRNGs. Section~\ref{section:BASIC RECALLS} gives some basic recalls on the well-known Devaney's formulation of chaos, @@ -185,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. @@ -650,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: @@ -1040,7 +1063,7 @@ not only sought in general to obtain chaos, but they are also required for rando \end{itemize} -We have proven in our previous works~\cite{} that chaotic iterations satisfying Theorem~\ref{Th:Caractérisation des IC chaotiques} are, among other +We have proven in our previous works~\cite{guyeux12:bc} that chaotic iterations satisfying Theorem~\ref{Th:Caractérisation des IC chaotiques} are, among other things, strongly transitive, topologically mixing, chaotic as defined by Li and Yorke, and that they have a topological entropy and an exponent of Lyapunov both equal to $ln(\mathsf{N})$, where $\mathsf{N}$ is the size of the iterated vector. @@ -1500,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 @@ -1598,9 +1623,27 @@ as it is shown in the next sections. \section{Security Analysis} -\label{sec: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} + +The standard definition + of {\it indistinguishability} used is the classical one as defined for + 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. +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$. @@ -1622,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}. @@ -1647,7 +1698,7 @@ PRNG too. \end{proposition} \begin{proof} -The proposition is proved by contraposition. Assume that $X$ is not +The proposition is proven by contraposition. Assume that $X$ is not secure. By Definition, there exists a polynomial time probabilistic algorithm $D$, a positive polynomial $p$, such that for all $k_0$ there exists $N\geq \frac{k_0}{2}$ satisfying @@ -1710,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} @@ -1833,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