\documentclass[11pt]{article}
\usepackage{graphicx}
\graphicspath{ {images/} }
\usepackage{a4wide}
\usepackage{graphicx, float, subcaption, array, tabu, adjustbox, enumitem}
\begin{document}
\section{Research}
\subsection{Dual\_EC\_DRBG}
Dual Elliptic Curve Deterministic Random Bit Generator (Dual\_EC\_DRBG) is an algorithm based on elliptic curve cryptography to generate a random bit stream designed by NSA [NIST SP 800-90A]. Its security relies on the mathematics of the elliptic curve discrete logarithm problem (ECDLP) where given points \begin{math}P\end{math} and \begin{math}Q\end{math} on an elliptic
curve of order \begin{math}n\end{math}, finding a such that \begin{math}Q=aP\end{math} is hard. It was standardised in NIST SP 800-90A, ANSI X9.82 and ISO 18031.
\begin{figure}[H]
\centering
\includegraphics[width=0.9\linewidth]{NIST.png}
\caption{Dual\_EC\_DRBG [xx]}
\end{figure}
\noindent
Notation:
\begin{itemize}
\item[] \begin{math}x(A)\end{math} is the x-coordinate of the point A on the curve given in affine coordinates.
\item[] \begin{math}\varphi(x)\end{math} maps field elements to non-negative integers, taking the bit vector representation of a field element and interpreting it as the binary expansion of an integer.
\item[] * is the symbol representing scalar multiplication of a point on the curve.
\end{itemize}
NIST Special Publication 800-90A January 2012 by Elaine Barker and John Kelsey provides the specifications of an elliptic curve and two points \begin{math}P\end{math} and \begin{math}Q\end{math} on the elliptic curve for Dual\_EC\_DRBG as in figure 1. To ensure the desired security strength and certification under the Federal Information Processing Standard (FIPS) Publication 140, applications must use an appropriate elliptic
curve and points on one of the NIST approved curves including Curve P-256, Curve P-384 and Curve P-521. In this project, Curve P-256 is used with associated points and constants as follows.\\\\
The NIST approved curves is given by the equation:
\begin{equation}y^2=x^3-3x+b\ (mod\ p)\end{equation}
Notation:
\begin{itemize}
\item[] \begin{math}p\end{math} - Order of the field \begin{math}F_p\end{math} , given in decimal
\item[] \begin{math}n\end{math} - Order of the Elliptic Curve Group, in decimal
\item[] \begin{math}a\end{math} - (-3) in the above equation
\item[] \begin{math}b\end{math} - Coefficient above
\end{itemize}
The \begin{math}x\end{math} and \begin{math}y\end{math} coordinates of the base point, i.e., generator \begin{math}G\end{math}, are the same as for the point \begin{math}P\end{math}.\\\\
\textbf{Curve P-256}
\begin{itemize}
\item[] \begin{math}p\end{math} = 11579208921035624876269744694940757353008614\textbackslash\\3415290314195533631308867097853951
\item[] \begin{math}n\end{math} = 11579208921035624876269744694940757352999695\textbackslash\\5224135760342422259061068512044369
\item[] \begin{math}b\end{math} = 5ac635d8 aa3a93e7 b3ebbd55 769886bc 651d06b0 cc53b0f6 3bce3c3e 27d2604b
\item[] \begin{math}Px\end{math} = 6b17d1f2 e12c4247 f8bce6e5 63a440f2 77037d81 2deb33a0 f4a13945 d898c296
\item[] \begin{math}Py\end{math} = 4fe342e2 fe1a7f9b 8ee7eb4a 7c0f9e16 2bce3357 6b315ece cbb64068 37bf51f5
\item[] \begin{math}Qx\end{math} = c97445f4 5cdef9f0 d3e05e1e 585fc297 235b82b5 be8ff3ef ca67c598 52018192
\item[] \begin{math}Qy\end{math} = b28ef557 ba31dfcb dd21ac46 e2a91e3c 304f44cb 87058ada 2cb81515 1e610046
\end{itemize}
\subsection{Dual\_EC\_DRBG algorithms and backdoor}
\begin{figure}[H]
\centering
\includegraphics[width=0.9\linewidth]{prng.png}
\caption{General schematic of a state-based PRNG with functions f and g [xx].}
\end{figure}
In this section the mathematical algorithms of Dual\_EC\_DRBG including general schematic, basic Dual\_EC\_DRBG without additional input, Dual\_EC\_DRBG version 2006 and 2007 with additional input according to NIST SP 800-90A with their relevant stast-based diagrams will be described. Following each version of Dual\_EC\_DRBG, the deails of how the related backdoor works will also be explained.
\subsubsection{State-based PRNG}
To understand how Dual\_EC\_DRBG works, it is important to realise a general schematic of a state-based pseudorandom number generator (PRNG) as described by Daniel J. Bernstein, Tanjan Lange, and Ruben Niederhagen [xx].\par
From figure 2, an internal state \begin{math}s_i\end{math} maintained in the PRNG begins with the initial state \begin{math}s_0\end{math} which is initialised from an entropy source. When some random bits are requested from the PRNG, the internal state is updated from the initial state \begin{math}s_0\end{math} to \begin{math}s_1\end{math} using function f, \begin{math}s_1 = f(s_0)\end{math}. After that the PRNG compute the output random bits \begin{math}r_1\end{math} using another function g, \begin{math}r_1 = g(s_1)\end{math}. If more random bits are requested, the internal state \begin{math}s_1\end{math} is updated again to \begin{math}s_2\end{math} using function f, \begin{math}s_2 = f(s_1)\end{math} and output \begin{math}r_2\end{math} using function g, \begin{math}r_2 = g(s_2)\end{math}. Then some bits of \begin{math}r_2\end{math} are appended to \begin{math}r_1\end{math}. The process is continued repeatedly until a certain number of requested random bits is satisfied.\par
It can be seen that the knowledge of an internal state \begin{math}s_i\end{math} can be used to compute the following states \begin{math}s_{i+1}, s_{i+2}, ...\end{math} and finally all output \begin{math}r_i, r_{i+1}, r_{i+2}, ...\end{math} . For this reason, a state-based pseudorandom number generator (PRNG) is secure as long as the internal state is kept secret and cannot be derived from any output. Hence, function g must be a one-way function without a backdoor so that the attacker are not able to compute the internal state of the PRNG from the output.
\begin{figure}[H]
\centering
\includegraphics[width=0.9\linewidth]{basic.png}
\caption{Basic Dual\_EC\_DRBG algorithm without additional input [xx]}
\end{figure}
\subsubsection{Basic Dual\_EC\_DRBG}
The basic DUAL\_EC\_DRBG algorithm [xx] follows the the general schematic of a state-based PRNG in the previous section. The algorithm uses points \begin{math}P\end{math} and \begin{math}Q\end{math} on the standard NIST P-256 elliptic curve which the internal state is a 256-bit integer \begin{math}s_i\end{math}. From figure 3, the internal state is updated from the initial state \begin{math}s_0\end{math} to \begin{math}s_1\end{math} using function \begin{math}f\end{math}, \begin{math}f(s_0) = s_1 = x(s_0P)\end{math}, which is the x-coordinate of the \begin{math}s_0\end{math}th multiple of \begin{math}P\end{math} on an elliptic curve. Then random bits \begin{math}r_1\end{math} is derived using function g, \begin{math}g(s_1) = r_1 = x(s_1Q)\end{math}, which is the x-coordinate of the \begin{math}s_1\end{math}th multiple of \begin{math}Q\end{math} on an elliptic curve. Finally, the most significant 16 bits of \begin{math}r_1\end{math} are discarded and outputs 30-byte random bits. In case of more than 30 bytes are required, the process will repeat and concatenate the output bits like \begin{math}r_2\end{math} and \begin{math}r_3\end{math}.\par
It can be seen that the internal state is large enough (256-bit integer), hence, both functions f and g above are cryptographically secure one-way function because it is infeasible to solve the elliptic discrete-logarithm problem (ECDLP), to compute the internal state \begin{math}s_i\end{math} given either \begin{math}s_iP\end{math} and \begin{math}P\end{math} or \begin{math}s_iQ\end{math} and \begin{math}Q\end{math}.
\subsubsection{Basic Dual\_EC\_DRBG backdoor}
The backdoor is the knowledge of a random secret integer \begin{math}d\end{math} by the attacker who controls the initialisation of points \begin{math}P\end{math} and \begin{math}Q\end{math} such that \begin{math}P = dQ\end{math} or \begin{math}Q = eP\end{math} where \begin{math}d = e^{-1} (mod\ n) \end{math} and \begin{math}n\end{math} is the order of \begin{math}P\end{math} [Shumow, Ferguson 2007]. If the random output \begin{math}r_1\end{math} in figure 2 is known by the attacker, for example from a public nonce, he can recompute point \begin{math}R = (x_{r_1}, y_{r_1}) = s_1Q\end{math}. A 32-byte x-coordinate \begin{math}x_{r_1}\end{math} is obtained by concatenating \begin{math}2^{16}\end{math} possibilities of the discarded most significant 2 bytes with 30 bytes of \begin{math}r_1\end{math}. The corresponding 32-byte y-coordinate \begin{math}y_{r_1}\end{math} is computed by assigning \begin{math}x_{r_1}\end{math} to equation 1. After that \begin{math}dR = ds_1Q = s_1dQ = s_1P\end{math} can be derived to obtain the candidates of internal state \begin{math}s_2 = x(s_1P)\end{math}. If the random output \begin{math}r_2\end{math} is also known by the attacker, he can find the correct internal state by predicting the next random output bits using each candidate and comparing with \begin{math}r_2\end{math}. Therefore, the attacker learns the next internal state and can reproduce all the following output.
\begin{figure}[H]
\centering
\includegraphics[width=0.9\linewidth]{2006.png}
\caption{Dual\_EC\_DRBG algorithm version 2006 with additional input [xx]}
\end{figure}
\subsubsection{Dual\_EC\_DRBG version 2006}
In the June 2006 release of NIST SP 800-90A, the internal state of DUAL\_EC\_DRBG can be refreshed with some high-entropy additional input. From figure 4 the initial state \begin{math}s_0\end{math} is bitwise xor'ed with the hash of additional input \begin{math}adin_0\end{math} using one of the appropriate hash functions specified in Table 4: Definitions for the Dual\_EC\_DRBG in NIST SP 800-90A for example SHA-1, SHA-224, SHA-512/224, SHA-256, SHA-512/256, SHA-384 and SHA-512 for Curve P-256 to get the seedlen-bit unsigned integer \begin{math}t_0\end{math}. This intermediate value is used to multiply with point \begin{math}P\end{math} and derive the next internal state \begin{math}s_1\end{math}. Finally the random bits \begin{math}r_1\end{math} is computed from \begin{math}r_1 = x(s_1Q)\end{math} while the most significant 2 bytes are discarded.\par
In case of more than 30 bytes of random bits are requested, the current internal state \begin{math}s_1\end{math} is again refreshed by being bitwise xor'ed with the hash of next additional input \begin{math}adin_1\end{math} to obtain \begin{math}t_1, s_2\end{math} and \begin{math}r_2\end{math} as the previous steps. To compute the next 30 bytes of random bits, the next internal state \begin{math}s_3\end{math} can be directly determined from \begin{math} s_2\end{math}, \begin{math}s_3 = x(s_2P)\end{math} and so on until the output random bits satisfy the number of bytes requested. However, when the random bits are asked for again, the internal state \begin{math}s_3\end{math} needs to be bitwise xor'ed with the hash of another additional input \begin{math}adin_3\end{math}.
\subsubsection{Dual\_EC\_DRBG version 2006 backdoor}
It can be seen that even though the attacker observes \begin{math}r_1\end{math}, he can no longer use the backdoor computation as described before to work out the next internal state \begin{math}s_2\end{math}. However, if more than 30 bytes of random bits are requested and the attacker knows the random output \begin{math}r_2\end{math} and \begin{math}r_3\end{math}, he can recompute point \begin{math}R = (x_{r_2}, y_{r_2}) = s_2Q\end{math}. After that \begin{math}dR = ds_2Q = s_2dQ = s_2P\end{math} can be derived to obtain the candidates of internal state \begin{math}s_3 = x(s_2P)\end{math}. Then he can find the correct internal state by predicting the next random output bits using each candidate and comparing with \begin{math}r_3\end{math}.\par
Therefore, the additional input does not only limit the backdoor but also slow down the attacker because even the attacker can find out the internal state \begin{math}s_3\end{math}, he still need to guess the high entropy additional input \begin{math}adin_3\end{math} to predict the following random output.
\begin{figure}[H]
\centering
\includegraphics[width=0.9\linewidth]{2007.png}
\caption{Dual\_EC\_DRBG algorithm version 2007 with additional input [xx]}
\end{figure}
\subsubsection{Dual\_EC\_DRBG version 2007}
In March 2007, NIST SP 800-90A was revised to require an additional update of the internal state at the end of each random bit invocation. From figure 5, the internal state \begin{math}s_1\end{math} is updated into the next internal state \begin{math}s_2\end{math}, \begin{math}s_2 = x(s_1P)\end{math}, after being used to generate the random bits \begin{math}r_1\end{math}, \begin{math}r_1 = x(s_1Q)\end{math}. The reason for this revision was to provide "backtracking resistance" or "forward secrecy" where the attacker will not be able to recompute earlier random numbers [xx]. The attacker who knows the current state cannot recompute the current random output because the internal state has already been updated, \begin{math}s_1\end{math} is replaced with \begin{math}s_2\end{math}.
\subsubsection{Dual\_EC\_DRBG version 2007 backdoor}
Because of the additional update of the internal state, the attacker who only has 30 bytes of random bits can have the knowledge of the internal state. Given \begin{math}r_1\end{math}, point \begin{math}R\end{math} can be derived as \begin{math}R = (x_{r_1}, y_{r_1}) = s_1Q\end{math} then \begin{math}dR = ds_1Q = s_1dQ = s_1P\end{math} and finally obtains the internal state \begin{math}s_2\end{math} as \begin{math}s_2 = x(s_1P)\end{math}. However, like version 2006 the attacker still need to guess the high entropy additional input \begin{math}adin_2\end{math} to predict the following random output.
\subsection{Use of Dual\_EC\_DRBG}
In NIST official website [xx] (last update: 12/4/2015), the DRBG validation list shows the implementations that have been validated as conforming to the Deterministic Random Bit Generator (DRBG) Algorithm, as specified in NIST SP 800-90A, Recommendation for Random Number Generation Using Deterministic Random Bit Generators. From 984 validation no., there are 82 implementations that include Dual\_EC\_DRBG as their random bit generator. In this project, RSA BSAFE will be briefly discussed followed by investigation of Windows Schannel and OpenSSL FIPS Object Module implementation.
\begin{figure}[H]
\centering
\includegraphics[width=1\linewidth]{chat.png}
\caption{Live Chat with RSA}
\end{figure}
\subsubsection{RSA BSAFE}
RSA BSAFE is a FIPS 140-2 validated cryptography toolkits developed by RSA Security. It offers developers the tools to add privacy and authentication features to their applications [xx]. There are two main families including RSA BSAFE CRYPTO-C and RSA BSAFE CRYPTO-Java. They are both designed to provide the security tools for a wide range of applications, such as digitally signed electronic forms, virus detection, or virtual private networks. However, from the conversation with EMC Sales Specialist on 28 June 2016 in figure 6 and RSA Product Version Life Cycle website RSA is no longer taking on new customers for RSA BSAFE and its Extended Opportunity Programs and Services (EOPS) will end in January 2017 for both RSA BSAFE CRYPTO-C and RSA BSAFE CRYPTO-Java. However, it is still worthwhile to study RSA BSAFE because it enabled Dual\_EC\_DRBG as a default DRBG from 2004 to 2013 [xx].\par
A paper "On the practical exploitability of Dual EC in TLS implementations" [xx] explains how RSA BSAFE uses Dual\_EC\_DRBG in the TLS implementation. To begin with RSA BSAFE CRYPTO-C version 1.1, it still does not support elliptic curve cryptography so that it uses the preferred cipher suites including TLS\_DHE\_DSS\_WITH\_AES\_128\_CBC\_SHA and TLS\_DHE\_RSA\_WITH\_AES\_128\_CBC\_SHA. During TLS handshake, it generates a 32-byte session ID, a 28-byte server random, a 20-byte ephemeral Diffie-Hellman (DH) secret key and a 20-byte nonce when using DSA respectively. The DH parameters and the server's public key are signed with the server' RSA or DSA certificate and the session ID, server random, public key, and signature are sent in the ServerHello message to the client.\par
While RSA BSAFE-Java version 1.1 already supports elliptic curve cryptography and uses the cipher suite TLS\_ECDHE\_ECDSA\_WITH\_AES\_128\_GCM\_SHA256. The values generated by Dual\_EC\_DRBG in this cases are a 28-byte server random, a 32-byte ECDHE secret key and a 32-byte ECDSA nonce in order.\par
Because both RSA BSAFE CRYPTO-C and RSA BSAFE CRYPTO-Java do not cache unused output bytes and Dual\_EC\_DRBG does not refresh the internal state with additional input by default, a passive network attacker can easily use the basic backdoor attack as explained in the previous section to recover the internal state. Then he can reproduce all the following random output such as DHE or ECDHE secret key, DSA or ECDSA nonce and finally recompute the session keys and the server's long-lived DSA secret key.
\subsubsection{Windows Schannel}
Secure Channel, also known as Schannel, is a security component comprising a set of security protocols that provide identity authentication and secure, private communication through encryption [xx]. Schannel is available in the Windows operating system since Windows 2000 and most commonly used for TLS on Microsoft's Internet Information Services (IIS) server and Internet Explorer (IE). It uses Microsoft's FIPS 140-2 validated Cryptograpy Next Generation (CNG) API which includes Dual\_EC\_DRBG as one of algorithm identifiers. Dual\_EC\_DRBG is distributed with Windows Vista, 7 and 8, Windows Server 2008 and 2012, though it is not enabled by default.\par
\begin{figure}[H]
\centering
\includegraphics[width=0.4\linewidth]{bcryptgenrandom.png}
\caption{BCryptGenRandom function}
\end{figure}
\begin{figure}[H]
\centering
\includegraphics[width=0.7\linewidth]{reg.png}
\caption{Windows random number generator registry}
\end{figure}
To use Dual\_EC\_DRBG as a pseudorandom number generator, an application calls the BCryptGenRandom function included in schannel.dll and specifies the pszAlgId attribute of the hAlgorithm parameter with BCRYPT\_RNG\_DUAL\_EC\_ALGORITHM value. Otherwise, Dual\_EC\_DRBG can be set to default by browsing through Windows Registry Editor in the \\ \textbackslash HKEY\_LOCAL\_MACHINE\textbackslash SYSTEM\textbackslash CurrentControlSet\textbackslash Control\textbackslash Cryptography\\\textbackslash Configuration\textbackslash Local\textbackslash Default\textbackslash
00000006 path as in figure 8 and reordering the list of algorithms in the Functions registry.
It can be seen that DUALECRNG is the least preference pseudorandom generator by default while RNG is the random number generator based on the AES counter mode specified in the NIST SP 800-90 standard.\par
\begin{figure}[H]
\centering
\includegraphics[width=0.7\linewidth]{bcryptprimitives.png}
\caption{Reverse engineering of DualEcRng\_Generate function in bcryptprimitives.dll}
\end{figure}
\begin{figure}[H]
\centering
\includegraphics[width=0.7\linewidth]{bcrypt.png}
\caption{point Q in bcryptprimitives.dll}
\end{figure}
When Schannel performs an ECDHE in TLS handshake, it requests random bytes from the BCryptGenRandom function in a different order than RSA BSAFE: a 32-byte session ID, a 40-byte ephemeral private key, a 32-byte irrelevant random, a 28-byte ServerHello nonce, and a 32-byte signature for ECDSA. When perform reverse engineering bcryptprimitives.dll as in figure 9 and 10, it is found that Dual\_EC\_DRBG does not refresh the internal state with additional input and point \begin{math}Q\end{math} from NIST SP 800-90A is located from offset 0003F390 to 0003F3C0. It can be replaced by a custom point \begin{math}Q\end{math} using the hex editor tool. Furthermore, the study of function called MSCryptDualECGen [xx] indicates that bcryptprimitives.dll implements Dual\_EC\_DRBG with the final update step at the end of each call but the result does not replace the internal state appearing to perform like Dual\_EC\_DRBG version 2006 by ignoring the result of the final update step. Besides, a 32-bit session ID of Schannel is different from RSA BSAFE because it replaces the first four byte with the fingerprint \begin{math}v' = v\ mod\ \end{math}CACHE\_LEN, where v is an unsigned integer of the original first four byte and CACHE\_LEN is fixed at 20,000.\par
For this reason, the basic attack can be performed using the server random in the previous handshake or the session ID in a current handshake message to recover the ECDHE private key. However, it is necessary to recompute the first four bytes which are substituted with the fingerprint. The result can be checked by generating the next 40 bytes of a private key, computing the corresponding public key and comparing against the value in the ServerKeyExchange message.
\subsubsection{OpenSSL FIPS Object Module}
From OpenSSL FIPS Object Module v2.0 User Guide , OpenSSL FIPS Object Module is a software component
intended for use with the OpenSSL cryptographic library and toolkit. It is designed to meet the requirements for validation under the FIPS 140-2 computer security standard by the National Institute of Standards and Technology's (NIST) Cryptographic Module Validation Program (CMVP) [xx]. The FIPS Object Module provides an API for invocation of FIPS approved cryptographic functions
from calling applications, and is designed for use in conjunction with standard OpenSSL 1.0.1 and
1.0.2 distributions. In this project the OpenSSL FIPS Object Module version 2.0.5 and OpenSSL 1.0.1e are used in the implementation section.\par
\begin{figure}[H]
\centering
\includegraphics[width=0.5\linewidth]{settype.png}
\caption{RAND\_set\_fips\_drbg\_type function in rand\_lib.c}
\end{figure}
Dual\_EC\_DRBG is one of the pseudorandom number generators provided in the FIPS Object Module 2.0 until version 2.0.5. Even though it is not the default PRNG, it can be manually enabled through an API call at run time using the RAND\_set\_fips\_drbg\_type function in rand\_lib.c or specify to OPENSSL\_DRBG\_DEFAULT\_TYPE macro at installation time as in figure 10 to override the default OpenSSL PRNG, NID\_aes\_256\_ctr (256-bit AES encryption with counter mode).
\begin{figure}[H]
\centering
\includegraphics[width=0.9\linewidth]{tls.png}
\caption{Dual\_EC\_DRBG}
\end{figure}
The OpenSSL version 1.0.1.e used in this project supports TLS 1.2 and its preferred cipher suites use ECDHE key exchange with either RSA or ECDSA signatures as described in the previous section. It follows the standard ECDHE based on NIST SP 800-90A, as in figure 11 it generates a 32-byte session ID, a 28-byte server random, a 32-byte ECDHE ephemeral private key, and optionally a 32-byte ECDSA nonce respectively. In addition, it can be seen that the implemetaion of Dual\_EC\_DRBG in OpenSSL does not cache unused random bytes but it refreshes the internal states with additional input. The additional input string is constructed from time in seconds, time in microseconds, counter and process id [xx].
\begin{equation}adin = (time\ in\ secs\ ||\ time\ in\ \mu secs\ ||\ counter\ ||\ pid)\end{equation}
Each of them is 4 bytes in length resulting 16-byte additional input string. The time fields are obtained from the system time while the counter starts at 0 and increments with each call and finally the pid is the process id of OpenSSL running. The hash of additional input is computed using the appropriate hash function and bitwise xor'ed with the internal state as explained in Dual\_EC\_DRBG version 2007 section.\par
The attacker who observes a 32-byte session ID in a Server Hello message during TLS handshake can perform the basic attack to recover the internal state \begin{math}s_2\end{math}. After that he has to update the internal state to \begin{math}s_3\end{math} as specified in Dual\_EC\_DRBG version 2007, guesses the additional input \begin{math}adin_2\end{math}, reproduce a server random and so on until he obtains an ECDHE private key. The details will be demonstrated in the implementation section.
\section{Implementation}
In this project, Dual\_EC\_DRBG is implemented in two parts, namely, SageMath programs and attack TLS on OpenSSL. The first implementation in SageMath programs is to realise a proof of concept of how Dual\_EC\_DRBG works on basic Dual\_EC\_DRBG without additional input, Dual\_EC\_DRBG version 2006 and 2007 with additional input according to NIST SP 800-90A. After that the attack is carried out on each case by replacing point \begin{math}Q\end{math} with a recomputed one to demonstrate how Dual\_EC\_DRBG backdoor works. The second implementation is to put the same backdoor on OpenSSL FIPS, learn an ECDHE server private key, reproduce TLS premaster secret key and decrypt TLS packets.
\subsection{SageMath programs}
The implementation in SageMath programs is based on NIST SP 800-90A specifications and the diagrams in figure 3 to 5 consisting of 6 SageMath worksheets (.sagews) as follows.
\begin{itemize}
\item[] Dual\_EC\_DRBG\_basic.sagews
\item[] Dual\_EC\_DRBG\_basic\_with\_backdoor.sagews
\item[] Dual\_EC\_DRBG\_2006.sagews
\item[] Dual\_EC\_DRBG\_2006\_with\_backdoor.sagews
\item[] Dual\_EC\_DRBG\_2007.sagews
\item[] Dual\_EC\_DRBG\_2007\_with\_backdoor.sagews
\end{itemize}
\subsubsection{Dual\_EC\_DRBG\_basic.sagews}
This SageMath program is designed to realise the basic Dual\_EC\_DRBG algorithm in figure 3 in Python code and demonstrate how to generate random bits without additional input.
\begin{figure}[H]
\centering
\includegraphics[width=0.9\linewidth]{sage1.png}
\caption{Curve P-256 initialisation}
\end{figure}
In figure 12, it shows how to initialise the elliptic curve using the values specified in NIST SP 800-90A including \begin{math}p, n, a, b\end{math} in equation 1 and obtain points \begin{math}P\end{math} and \begin{math}Q\end{math} on the curve using \begin{math}Px, Py, Qx,\end{math} and \begin{math}Qy\end{math} given in the standard.
\begin{figure}[H]
\centering
\includegraphics[width=0.5\linewidth]{sage2.png}
\caption{Dual\_EC\_DRBG random bit generator}
\end{figure}
The function in figure 13 illustrates the generation of random bits from the internal state \begin{math}s_i\end{math} and points \begin{math}P\end{math} and \begin{math}Q\end{math}. To begin with, the initial state \begin{math}s_0\end{math} is chosen at random and used as the internal state to compute the next internal state by multiplying with point \begin{math}P\end{math} which is then multiplied with point \begin{math}Q\end{math} to derive the random bits \begin{math}r_i\end{math}. Finally the random bits \begin{math}r_i\end{math} is bitwise AND'ed with the defined bitmask \begin{math}(2^{30*8} - 1)\end{math} to discard the most significant two bytes and output 30 bytes for each block. In this case there is no additional input and it remains 0, hence, it does not affect the internal state. Note that \begin{math}(t_i*P)[0]\end{math} means \begin{math}x(t_i*P)\end{math}, the x-coordinate of multiplication between \begin{math}t_i\end{math} and \begin{math}P\end{math} on the curve P-256. While lift() means \begin{math}\varphi(x)\end{math}, mapping field elements to non-negative integers, taking the bit vector representation of a field element and interpreting it as the binary expansion of an integer.
\begin{figure}[H]
\centering
\includegraphics[width=0.9\linewidth]{sage3.png}
\caption{Basic Dual\_EC\_DRBG algorithm result}
\end{figure}
The result in figure 14 shows that basic Dual\_EC\_DRBG without additional input using the standard points \begin{math}P\end{math} and \begin{math}Q\end{math} on curve P-256 takes approximately 0.05 seconds to generate 32 bytes of random bits.\\
\subsubsection{Dual\_EC\_DRBG\_basic\_with\_backdoor.sagews}
Since the secret backdoor value of the standard Dual\_EC\_DRBG is only known by the designer, NSA. This program is developed to insert a custom Dual\_EC\_DRBG backdoor to the basic Dual\_EC\_DRBG algorithm in the previous section instead of the standard one.
\begin{figure}[H]
\centering
\includegraphics[width=0.3\linewidth]{sage4.png}
\caption{Custom Dual\_EC\_DRBG backdoor}
\end{figure}
To create a custom Dual\_EC\_DRBG backdoor, the secret backdoor value must be determined. It can be a small number, for example, in figure 15 the secret backdoor value \begin{math}d\end{math} is chosen at 5. Then either point \begin{math}P\end{math} or \begin{math}Q\end{math} specified in NIST SP 800-90A has to be modified. To compute new point \begin{math}P\end{math}, it can be done by multiplying the secret backdoor value \begin{math}d\end{math} with the standard point \begin{math}Q\end{math}, while point \begin{math}Q\end{math} remains the same. On the other hand to change point \begin{math}Q\end{math}, the order of point \begin{math}P\end{math} or \begin{math}Q\end{math} has to be derived using the additive\_order function. The order is used to computed the multiplicative inverse of the secret backdoor value \begin{math}e\end{math} using the inverse\_mod function. Finally new point Q can be derived by multiplying the multiplicative inverse of the secret backdoor value \begin{math}e\end{math} with point P, while point \begin{math}P\end{math} remains the same. This new point \begin{math}P\end{math} or \begin{math}Q\end{math} is used in Dual\_EC\_DRBG to instead of the standard point to generate random bits. In this program point Q are substituted with a new value while point P is still the standard one.
\begin{figure}[H]
\centering
\includegraphics[width=0.9\linewidth]{sage5.png}
\caption{Get\_Internal\_State function}
\end{figure}
Once the custom Dual\_EC\_DRBG backdoor is in place, the next internal state can be recovered using the Get\_Internal\_State function in figure 16. The input of the function are points \begin{math}P\end{math} and \begin{math}Q\end{math}, \begin{math}p\end{math} and \begin{math}b\end{math} from the standard, the current random bit output \begin{math}r\end{math} and the secret backdoor value \begin{math}d\end{math}. As described in the previous section, the first 30 bytes of random bits are the least significant part of \begin{math}x\end{math} value in equation 1. To guess the candidate of \begin{math}x\end{math}, \begin{math}x\_cand\end{math}, it has to loop through all \begin{math}2^{16}\end{math} possibilities of the missing 2 bytes. The corresponding \begin{math}y\end{math} value, \begin{math}y\_cand\end{math}, is then derived using each \begin{math}x\_cand\end{math}. After that the pair of \begin{math}x\_cand\end{math} and \begin{math}y\_cand\end{math} is verified whether it is a valid coordinate on the standard curve. If so, this pair of \begin{math}x\_cand\end{math} and \begin{math}y\_cand\end{math} will represent point \begin{math}R\end{math} which is then multiplied with the secret backdoor value \begin{math}d\end{math} to get the candidate of internal state \begin{math}s\_cand\end{math}. The possible \begin{math}s\_cand\end{math}s are scoped down by multiplying themselves with point Q to generate the random bits which then are compared with the rest of current random bit output \begin{math}r\end{math}. If they are related, the function will output that \begin{math}s\_cand\end{math} which is later used as the internal state to predict all the following random bits.
\begin{figure}[H]
\centering
\includegraphics[width=1\linewidth]{sage6.png}
\caption{Basic Dual\_EC\_DRBG backdoor result}
\end{figure}
The result in figure 17 shows that it takes 452 seconds CPU time to recover the internal state \begin{math}s\end{math} from the random bits \begin{math}r_1\end{math} using the backdoor on basic Dual\_EC\_DRBG without additional input with the standard points \begin{math}P\end{math} and the modified point \begin{math}Q\end{math} on curve P-256. It spends approximately 0.05 seconds to predict 60 bytes of random bits which are exactly the same as the following generated random bits \begin{math}r_2\end{math} and \begin{math}r_3\end{math}
\subsubsection{Dual\_EC\_DRBG\_2006.sagews}
This program realise DUAL\_EC\_DRBG version 2006 in figure 4 of which the internal state is refreshed with some high-entropy additional input when the random bits are requested. In general the functions in this program are similar to the basic Dual\_EC\_DRBG program as in figure 12 and 13 except the additional input generator function.
\begin{figure}[H]
\centering
\includegraphics[width=0.85\linewidth]{sage7.png}
\caption{Get\_H\_Adin function}
\end{figure}
From the implementation of Dual\_EC\_DRBG in OpenSSL FIPS Object Module 2.0, the high-entropy additional input string can be constructed from time in seconds, time in microseconds, counter and process id as in equation 2. In Python, time in seconds is obtained using datetime.now().second function which returns the Unix epoch time. The Unix epoch time is the number of seconds that have elapsed since January 1, 1970 (midnight UTC/GMT) for example 1472391621 at the time this report is written. While time in microseconds can be retrieved using datetime.now().microsecond function. It varies from 0 to 999,999. Counter is the internal number that the pseudorandom generator starts at 0 and increments each time random bits are requested. Finally os.getpid() function returns the current process id ranging from 1 to 32768 as specified in /proc/sys/kernel/pid\_max in most Unix systems. After shifting and concatenating them into the high-entropy additional input string, a secure SHA-256 hash function from NIST SP 800-90A will digest it to produce a 32-byte bit string which is later used to refresh the internal state of Dual\_EC\_DRBG.
\begin{figure}[H]
\centering
\includegraphics[width=0.9\linewidth]{sage8.png}
\caption{Dual\_EC\_DRBG version 2006 with additional input result}
\end{figure}
The result in figure 19 shows that Dual\_EC\_DRBG version 2006 with 32-byte additional input using the standard points \begin{math}P\end{math} and \begin{math}Q\end{math} on curve P-256 takes approximately 0.06 seconds CPU time to generate 32 bytes of random bits which means it is 20\% slower than basic Dual\_EC\_DRBG without additional input
\subsubsection{Dual\_EC\_DRBG\_2006\_with\_backdoor.sagews}
The secret backdoor value \begin{math}d\end{math} and recomputed point \begin{math}Q\end{math} from basic Dual\_EC\_DRBG backdoor are also used in Dual\_EC\_DRBG version 2006 backdoor while point \begin{math}P\end{math} is still the standard one. Besides, the Get\_Internal\_State function in figure 16 is utilised in this program to recover the next internal state.\par
To compute the following random bits after the internal state is known, it is necessary to predict the next additional input. In the OpenSSL TLS implementation, the time in seconds is usually transmitted as part of the server random, however, time in microseconds, counter and process id can range from \begin{math}2^{20}\end{math}, \begin{math}2^{10}\end{math} and \begin{math}2^{15}\end{math} respectively. In total there are approximately \begin{math}2^{45}\end{math} possibilities of additional input. Once the correct additional input is recovered, the following additional input can be guessed within \begin{math}2^{20}\end{math} attempts since counter is increased by 1 and process id is the same. The demonstration of additional input prediction will be shown in the second implementation on OpenSSL FIPS.
\begin{figure}[H]
\centering
\includegraphics[width=0.5\linewidth]{sage9.png}
\caption{Predict\_Next function version 2006 with additional input}
\end{figure}
In this program additional input is assumed to be already known and its hash value is passed to the Predict\_Next function. The hash of predicted additional input is then bitwise xor'ed with the candidate of internal state \begin{math}s\_cand\end{math} at the start of each invocation. As in figure 20 the candidate of internal state \begin{math}s\_cand\end{math} is multiplied with point \begin{math}P\end{math} to get the next state which is then multiplied with point \begin{math}Q\end{math} to generate random bits \begin{math}r\_cand\end{math}. As explained before, the most significant 2 bytes of random bits are discarded by bitwise AND'ing with the defined bitmask. The result is concatenated with the previous one until the number of random bytes satisfy the request as specified in byte parameter.
\begin{figure}[H]
\centering
\includegraphics[width=1\linewidth]{sage10.png}
\caption{Dual\_EC\_DRBG version 2006 backdoor with predicted additional input result}
\end{figure}
The result in figure 21 shows that Dual\_EC\_DRBG version 2006 backdoor with predicted additional input \begin{math}h\_adin1\end{math} using the standard points \begin{math}P\end{math} and the modified point \begin{math}Q\end{math} on curve P-256 takes 638.62 seconds CPU time to recover the internal state from the random bit output \begin{math}r_1\end{math}. This value varies from 400 to 800 seconds depending on the missing most significant 2 bytes. It spends additional 0.06 seconds to execute the Predict\_Next function and generate 60 bytes of random bits using known additional input. For this reason the cost of computation is approximately 638.62 seconds plus 0.06 seconds per each guessing additional input. If the additional input in unknown, it would takes up to \begin{math}638.62 + (0.06 * 2^{45})\end{math} seconds. Therefore, it shows that the additional input makes the attack much more difficult but once it is recovered the following random bits can be correctly guessed like \begin{math}r_2\end{math} and \begin{math}r_3\end{math}
\subsubsection{Dual\_EC\_DRBG\_2007.sagews}
This program realise DUAL\_EC\_DRBG version 2007 in figure 5 of which the internal state is refreshed with some high-entropy additional input when the random bits are requested and additional update step of the internal state at the end of each invocation. In general the functions in this program are similar to the basic Dual\_EC\_DRBG and Dual\_EC\_DRBG version 2006 program except the additional update step.
\begin{figure}[H]
\centering
\includegraphics[width=0.7\linewidth]{sage11.png}
\caption{Random\_Generator function with additional update step}
\end{figure}
When the random bits are requested using the Random\_Generator function in figure 22, only the first block of random output bits of each invocation generated by the DUAL\_EC\_DRBG function in figure 13 involves the additional input. After the result meets the required bytes, the internal state is updated one more time by multiplying itself with point \begin{math}P\end{math}.
\begin{figure}[H]
\centering
\includegraphics[width=0.9\linewidth]{sage12.png}
\caption{Dual\_EC\_DRBG version 2007 with additional input and update step result}
\end{figure}
The result in figure 23 shows that Dual\_EC\_DRBG version 2007 with 32-byte additional input and update step of the internal state using the standard points \begin{math}P\end{math} and \begin{math}Q\end{math} on curve P-256 takes approximately 0.07 seconds CPU time to generate 32 bytes of random bits which means it is 40\% slower than basic Dual\_EC\_DRBG without additional input
\subsubsection{Dual\_EC\_DRBG\_2007\_with\_backdoor.sagews}
In addition to Dual\_EC\_DRBG version 2006, the secret backdoor value \begin{math}d\end{math} and recomputed point \begin{math}Q\end{math} from basic Dual\_EC\_DRBG backdoor are also used in Dual\_EC\_DRBG version 2007 backdoor while point \begin{math}P\end{math} is still the standard one. The functions in this program are generally utilised from Dual\_EC\_DRBG version 2006 backdoor program.
\begin{figure}[H]
\centering
\includegraphics[width=0.5\linewidth]{sage13.png}
\caption{Predict\_Next function version 2007 with additional input}
\end{figure}
In this program the additional input is also assumed to be already known and its hash value is passed to the Predict\_Next function. However, before the hash of predicted additional input is bitwise xor'ed with the candidate of internal state \begin{math}s\_cand\end{math}, it is necessary that the candidate of internal state \begin{math}s\_cand\end{math} has to be multiplied with point \begin{math}P\end{math} to update the state one more time. Then the steps as of Dual\_EC\_DRBG version 2006 backdoor can continue until the prediction process finishes.
\begin{figure}[H]
\centering
\includegraphics[width=1\linewidth]{sage14.png}
\caption{Dual\_EC\_DRBG version 2007 backdoor with predicted additional input result}
\end{figure}
Similar to Dual\_EC\_DRBG version 2006 backdoor, the result in figure 25 shows that Dual\_EC\_DRBG version 2007 backdoor with predicted additional input \begin{math}h\_adin2\end{math} using the standard points \begin{math}P\end{math} and the modified point \begin{math}Q\end{math} on curve P-256 takes 490.20 seconds CPU time to recover the internal state from the random bit output \begin{math}r_1\end{math}. This value also varies from 400 to 800 seconds depending on the missing most significant 2 bytes. However, it spends additional 0.07 seconds CPU time to execute the Predict\_Next function and generate 60 bytes of random bits using known additional input which is 0.01s longer than Dual\_EC\_DRBG version 2006 backdoor. For this reason the cost of computation is approximately 490.20 seconds plus 0.07 seconds per each guessing additional input. If the additional input in unknown, it would takes up to \begin{math}490.20 + (0.07 * 2^{45})\end{math} seconds. Once the additional input is recovered the following random bits can be correctly guessed like \begin{math}r_2\end{math} and \begin{math}r_3\end{math}\par
In conclusion, each SageMath program can realise how Dual\_EC\_DRBG works on basic Dual\_EC\_DRBG without additional input, Dual\_EC\_DRBG version 2006 and 2007 with additional input as in figure 3 to 5 respectively. In general to generate 32 bytes of random bits it takes 0.05 seconds for basic Dual\_EC\_DRBG, 0.06 seconds for Dual\_EC\_DRBG version 2006 and 0.07 seconds for Dual\_EC\_DRBG version 2007. Then the following attack on each case successfully recovers the internal state and predicts the next random bits. Even though, the additional input complicates the attack in Dual\_EC\_DRBG version 2006 and 2007.
\subsection{Attack TLS on OpenSSL}
In this section the attack against TLS based on OpenSSL will be demonstrated in details. The backdoor methodology described in the research section and proved in the previous implementation part will be put on real OpenSSL implementation. The objective of this attack are to learn an ECDHE server private key, reproduce TLS premaster secret and decrypt TLS packets. To conduct this section in more efficient way, the concept in software engineering is applied as below.
\subsubsection{Analysis}
The software system to be developed in this part is a program that has the capability of analysing the captured network packets during TLS handshake between the compromised server and a normal client which are produced by a network sniffer software like tcpdump or Wireshark. The application needs to be able to perform Dual\_EC\_DRBG computation with a given secret backdoor value such as elliptic curve point multiplication and polynomial equation calculation while communicating to the underline OpenSSL libraries to perform primitive cryptographic operation in order to recover the internal state, additional input and predict the following random output bits. Finally, it should output the required secret values including an ECDHE server private key and a TLS premaster secret in a proper format to be later used to decrypt captured TLS packets.
\begin{figure}[H]
\centering
\includegraphics[width=0.6\linewidth]{system.png}
\caption{System overview}
\end{figure}
The system overview in figure 26 shows the necessary components in this implementation including the server, the client and the attacker. The server is a web hosting to provide HTTPS service on port 443 for the client. The client initiates a connection to the server using its web browser. OpenSSL is needed on the server to provide cryptographic functions to establish a secure TLS connection with the client using ECDHE key exchange for example. In order to use Dual\_EC\_DRBG, OpenSSL FIPS is required and Dual\_EC\_DRBG also has to be enabled. In this project both TLS with RSA key transport and TLS with ECDHE exchange and ECDSA signature (P-256) are implemented. Hence, the certificate for each protocol is generated on the server using the relevant key file. Finally, the attacker who passively eavesdrops the connection between the server and the client can monitor and capture the TLS packets and later perform the cryptanalysis against the TLS protocol. To achieve the attack, he only needs Wireshark, SageMath and python package installed to run the attack scripts.
\subsubsection{Design}
\begin{figure}[H]
\centering
\includegraphics[width=0.19\linewidth]{layer.png}
\caption{Software architecture}
\end{figure}
This system software is designed with layered design pattern by splitting into 4 layers namely OpenSSL, C, Python and Wireshark as in figure 27. The details of each layer are as follow.\\\\
\noindent\textbf{OpenSSL}\\
The first layer concerns the underline OpenSSL libralies including libcrypto.a and libssl.a which are created once OpenSSL is installed. These libraries significantly involve in TLS communication and also can create a TLS server using s\_server command. To enable FIPS compliance, OpenSSL FIPS Object Module has to be installed prior to OpenSSL setup. After FIPS mode is enabled, OpenSSL will use the protocols provided by OpenSSL FIPS Object Module, fipscanister.o, instead. The application can then use the FIPS compliance functions including Dual\_EC\_DRBG. For this reason the Dual\_EC\_DRBG backdoor previously described can be found in OpenSSL FIPS Object Module. The next section will show how to verify, insert and enable the backdoor in OpenSSL FIPS Object Module source code.\\
\noindent\textbf{C}\\
The next layer is designed as a custom C library to interface between the OpenSSL layer and the upper layer, Python layer. This library operate as a part of attack script by calling the cryptographic functions provided by OpenSSL, reformatting and submitting result to the upper layer application.\\
\noindent\textbf{Python}\\
This layer is the most important part where the python attack scripts are executed. The application has the following 5 main functionalities. Firstly, it interfaces with the upper Wireshark layer, filters and analyses the captured TLS packets to extract necessary information including a session ID, a timestamp, a server and client random and a server and client public key. Secondly, it utilises the OpenSSL functions to perform cryptographic computation via the lower C layer. Thirdly, it performs some calculation to guess additional input. Fourthly, it recovers an ECDHE server private key. Finally, it computes a TLS premaster secret from a server random and a server private key and generates the output file in the format that is ready for the Wireshark layer to decrypt the captured TLS packets.\\
\begin{figure}[H]
\centering
\includegraphics[width=0.9\linewidth]{flow.png}
\caption{Program flow}
\end{figure}
The process of how the application works is designed as a program flow in figure 28. Each step is explained as follows
\begin{itemize}
\item[] Start - To start executing the attack scripts.
\item[] Generate adin list - To generate the list of possible additional input from available knowledge of time in seconds, time in microseconds, counter and process id.
\item[] Get 32-byte Session ID - To read a session ID from a Server Hello message.
\item[] Compute internal state - To recover the internal state from a 32-byte session ID.
\item[] Predict random - To apply the recovered internal state with each additional input to generate the corresponding 28-byte server random.
\item[] Compare server random - To compare the computed server random with the server random from captured packets. If they are equal, proceed to the next step. If not, try the next additional input from the list.
\item[] Get current counter, pid - To determine the counter and process id which make the computed server random match the server random from captured packets. Then produce the next additional input by incrementing the counter along with the known process id.
\item[] Predict 32-byte ECDHE priv.key - To generate random bits as a 32-byte ECDHE private key using the internal state and additional input from the previous step.
\item[] Compute ECDHE pub.key - To compute the corresponding ECDHE server public key from \begin{math}server\ public\ key = server\ private\ key * P\end{math}.
\item[] Compare server pub.key - To compare the computed server public key with the server public key from captured packets. If they match, continue to the next step. If not, go back to the step Predict 32-byte ECDHE priv.key again.
\item[] Compute premaster secret - To compute a TLS premaster secret using \begin{math}premaster\ secret = server\ private\ key * client\ public\ key\end{math}.
\item[] Export premaster.txt file - To output a TLS premaster secret in the appropriate format for Wireshark.
\item[] End - To stop the attack scripts and continue to the Wireshark layer.
\end{itemize}
\noindent\textbf{Wireshark}\\
The last layer concerns the Wireshark tool itself. Wireshark is a free and open source packet analyzer. It is used for network troubleshooting, analysis, software and communications protocol development. In this project, it is used to sniff and record the TLS communications between the server and client, probably by the attacker. It is a GUI tool to verify the content for example a session ID and a server random in a Server Hello message. To allow a python code to read a Wireshark packet, the additional pyshark module needs to be installed. The most facilitative feature in use is decrypting the TLS packets with a client random and a TLS premaster secret.
\subsubsection{Coding}
In this part, the program explained in the design section will be broken down in greater detail with the explanation of some important pieces of code. However the full program source code can be found as the attachment of the project.\\
\noindent\textbf{OpenSSL}\\
From the OpenSSL layer design, the implementation can be grouped into 4 main tasks.
\begin{figure}[H]
\centering
\includegraphics[width=0.75\linewidth]{q.png}
\caption{Custom Dual\_EC\_DRBG backdoor}
\end{figure}
\noindent
Insert a custom Dual\_EC\_DRBG backdoor to OpenSSL FIPS Object Module:
\begin{itemize}
\item Download OpenSSL FIPS Object Module version 2.0.5.\\
\textit{wget http://www.openssl.org/source/openssl-fips-2.0.5.tar.gz}
\item Extract the downloaded file.\\
\textit{tar -xzvf openssl-fips-2.0.5.tar.gz}
\item Edit Dual\_EC\_DRBG source code.\\
\textit{nano openssl-fips-2.0.5/fips/rand/fips\_drbg\_ec.c}
\item Verify \begin{math}Q\end{math} points from SP 800-90 A.1 in \begin{math}p\_256\_qx[]\end{math} and \begin{math}p\_256\_qy[]\end{math} variables.
\item Replace \begin{math}p\_256\_qx[]\end{math} and \begin{math}p\_256\_qy[]\end{math} value with the custom \begin{math}Qx\end{math} and \begin{math}Qy\end{math} from the SageMath section as in figure 29.
\item To fix a known bug of Dual\_EC\_DRBG on OpenSSL FIPS Object Module, insert \\\textit{t = s;} after line 330.
\end{itemize}
\noindent
Bypass OpenSSL FIPS Object Module validation:
\begin{itemize}
\item Edit fips\_drbg\_selftest.c.\\
\textit{nano openssl-fips-2.0.5/fips/rand/fips\_drbg\_selftest.c}
\item Insert \textit{return 1;} after line 201.
\end{itemize}
\noindent
Install OpenSSL FIPS Object Module:
\begin{itemize}
\item Go to OpenSSL FIPS Object Module directory.\\
\textit{cd openssl-fips-2.0.5}
\item Configure OpenSSL FIPS Object Module.\\
\textit{./config}
\item Compile OpenSSL FIPS Object Module source code.\\
\textit{make}
\item Install OpenSSL FIPS Object Module.\\
\textit{sudo make install}
\end{itemize}
\noindent
Enable a custom Dual\_EC\_DRBG backdoor on OpenSSL setup process:
\begin{itemize}
\item Download OpenSSL FIPS Capable Library version 1.0.1e.\\
\textit{wget http://www.openssl.org/source/openssl-1.0.1e.tar.gz}
\item Extract the downloaded file.\\
\textit{tar -xzvf openssl-1.0.1e.tar.gz}
\item Configure OpenSSL with fips option and specify the drbg default type to \textit{0x19f02a0} (Dual\_EC\_DRBG).\\
\textit{./config fips shared no-ssl2 -DOPENSSL\_DRBG\_DEFAULT\_TYPE=0x19f02a0 \\-DOPENSSL\_DRBG\_DEFAULT\_FLAGS=0 -DOPENSSL\_ALLOW\_DUAL\_EC\_DRBG}
\item Compile OpenSSL source code.\\
\textit{make all}
\item Install OpenSSL.\\
\textit{sudo make install}
\item Move existing OpenSSL.\\
\textit{sudo mv /usr/bin/openssl /usr/bin/openssl\_orig}
\item Link new OpenSSL.\\
\textit{sudo ln -s /usr/local/ssl/bin/openssl /usr/bin/openssl}
\item Append \textit{OPENSSL\_FIPS=1} to /etc/environment.
\end{itemize}
\noindent
Set up a TLS server:
\begin{itemize}
\item Create a certificate for TLS with RSA key transport.\\
\textit{openssl req -x509 -nodes -days 365 -newkey rsa:2048 -keyout certs/server.key \\-out certs/server.crt}
\item Create a certificate for TLS with ECDHE exchange and ECDSA signature (P-256).\\
\textit{openssl ecparam -genkey -out certs/eckey.pem -name prime256v1}\\
\textit{openssl req -x509 -new -key certs/eckey.pem -out certs/cert.pem}
\item Create a web page and save as page.html.
\item Start a TLS server using RSA key transport on port 443 with no TLS session ticket option.\\
\textit{openssl s\_server -key certs/server.key -cert certs/server.crt -accept 443 -WWW -no\_ticket}
\item Or start a TLS server using ECDHE exchange and ECDSA signature (P-256) on port 443 with no TLS session ticket option.\\
\textit{openssl s\_server -key certs/eckey.pem -cert certs/cert.pem -accept 443 -WWW -no\_ticket}
\end{itemize}
\noindent\textbf{C}\\
In the custom C library source code dual\_ec.c, there are 2 main functions that can be called by the upper Python layer while interfacing with the lower OpenSSL layer. These functions accept the input from python programs, submit to OpenSSL, and return the output to python programs in a proper format.\\\\
\noindent
get\_random function
\begin{figure}[H]
\centering
\includegraphics[width=0.8\linewidth]{getrandom.png}
\caption{get\_random function, dual\_ec.c}
\end{figure}
To begin with, this function calls another custom function init\_fips to create the OpenSSL DRBG context object then accepts the internal state and additional input computed from a python program. Next it executes the OpenSSL's FIPS\_drbg\_generate standard function passing the OpenSSL DRBG context object, number of required random bytes and additional input to request OpenSSL random bits using its default DBRG (Dual\_EC\_DRBG). Finally it returns the hex value of next internal state and the generated random bits.\\
\noindent
get\_adin function
\begin{figure}[H]
\centering
\includegraphics[width=0.5\linewidth]{getadin.png}
\caption{get\_adin function, dual\_ec.c}
\end{figure}
Another necessary custom function is the get\_adin function which is used to convert the additional input value received from a python program in the ADIN structure including the time in seconds \begin{math}tv\_sec\end{math}, time in microseconds \begin{math}tv\_usec\end{math}, counter \begin{math}pctr\end{math} and process id \begin{math}pid\end{math} into the acceptable format of OpenSSL's additional input string. In the end, it outputs additional input in the appropriate format along with its length.\\
\noindent\textbf{Python}\\
From the specifications and program flow in the design section, the python program is divided into 5 functionalities. Some important parts of code and their descriptions will be explained.\\\\
\noindent
Interfacing with the upper Wireshark layer.
\begin{figure}[H]
\centering
\includegraphics[width=0.9\linewidth]{py1.png}
\caption{Packet analyser, cap.py}
\end{figure}
The packet analyser program in figure 32 shows that the pyshark package is used. This package allows parsing from a capture file or a live capture, using all wireshark dissectors. The FileCapture function allows the program to scope the captured packets with Wireshark display filters for example \textit{ssl.handshake.type == 1} is a Client Hello message, \textit{ssl.handshake.type == 2} is a Server Hello message and \textit{ssl.handshake.type == 16} is a Client Key Exchange message. Then the required information can be extracted by navigating through the packet branches including
\begin{itemize}
\item Random time in seconds.\\
\textit{packet.ssl.handshake\_random\_time}
\item Session ID.\\
\textit{packet.ssl.handshake\_session\_id}
\item Server and client random.\\
\textit{packet.ssl.handshake\_random}
\item Server public key.\\
\textit{packet.ssl.handshake\_server\_point}
\item Client public key.\\
\textit{packet.ssl.handshake\_client\_point}
\end{itemize}
\noindent
Utilising the OpenSSL functions to perform cryptographic computation via the lower C layer.
\begin{figure}[H]
\centering
\includegraphics[width=0.9\linewidth]{py2.png}
\caption{C library utilisation, main.py}
\end{figure}
To include C library in a python program, cdll.Loadlibrary is a useful function. The python program loads libdual\_ec.so library and uses the get\_random and get\_adin function explained in the previous part. It is also important to specify the argument types and return type as in figure 33.\\
\noindent
Guess additional input.
\begin{figure}[H]
\centering
\includegraphics[width=0.6\linewidth]{py3.png}
\caption{Addition input list generation, adin.py}
\end{figure}
Because OpenSSL FIPS implements Dual\_EC\_DRBG version 2007, hence, it is required to guess the additional input before producing the next random output bits. From equation 2, the additional input string consists of time in seconds, time in microseconds, counter and process id. Time in seconds can always be found in a Server Hello message while the other values are still need to be guessed. However, from the experiments in this project, after a TLS server is started the first counter of TLS handshake is usually 11 and process id is predictable. For the performance reason, the counter and process id are specified as in figure 34. Finally, it calls the get\_adin function in C library to reformat and output all possible additional input string in the adin\_list file.
\begin{figure}[H]
\centering
\includegraphics[width=0.9\linewidth]{py4.png}
\caption{Guess addition input, main.py}
\end{figure}
Once the internal state is recovered using the Get\_Internal\_State function (the same function as in the SageMath programs), each additional string in the adin\_list file is submitted along with the internal state to the get\_random function to generate the corresponding random bits. This predicted random bits are compared with the server random from the captured packet. If they are equal, that particular additional input is the correct one and the internal state is updated to the new state. If not, try the next additional input in the adin\_list file.\\\\
\noindent
Recover an ECDHE server private key.
\begin{figure}[H]
\centering
\includegraphics[width=1\linewidth]{py5.png}
\caption{ECDHE server private key, main.py}
\end{figure}
After the previous additional input is known, the next additional input is easier because time in seconds and process id remain the same while counter is increased by 1 and only time in microseconds have to loop through all possible values again, 0 to 999,999. To generate random bits as a 32-byte ECDHE private key, the internal state and predicted additional input are sent to the get\_random function. The right 32-byte ECDHE private key can be checked by comparing the computed ECDHE server public key, \begin{math}predict\_pubkey = predict\_random * P\end{math}, with the ECDHE server public key from a Server Hello message.
\noindent
Compute the TLS premaster secret and generates the output file to decrypt the captured packets.
\begin{figure}[H]
\centering
\includegraphics[width=0.95\linewidth]{py6.png}
\caption{TLS premaster secret, main.py}
\end{figure}
Before the TLS premaster secret can be derived, the ECDHE client public key are splitted into 2 32-byte numbers, the most significant 32-byte \begin{math}C_x\end{math} and the least significant 32-byte \begin{math}C_y\end{math}. \begin{math}C_x\end{math} and \begin{math}C_y\end{math} are the coordinates of point C on curve P-256. The TLS premaster secret is the x-coordinate value of the multiplication between the ECDHE private key and point C. Finally the premaster secret is written to a file along with all the client randoms in the format PMS\_CLIENT\_RANDOM \textit{CLIENT\_RANDOM PREMASTER\_SECRET}.\\
\noindent\textbf{Wireshark}
\begin{figure}[H]
\centering
\includegraphics[width=0.8\linewidth]{monitor.png}
\caption{TLS premaster secret, main.py}
\end{figure}
Apart from the decryption process, Wireshark is also used on the attacker's machine to eavesdrop the TLS communication between the server and the client. To achieve this step, the monitor mode option on the listening network interface has to be enabled as in figure 38. The other network configurations are not in the scope of this project.
\subsubsection{Testing}
\appendix
\end{document}
