primitives.tex

\section{Cryptographic Primitives}
\label{sec:crypto-primitives}

In this section, we outline the cryptographic primitives/schemes that will be used to provide data confidentiality, authenticity, and integrity to our protocols. When choosing appropriate cryptographic schemes,\iflong we ensured that all of the following were true:
\begin{itemize}
    \item All cryptographic implementations and other dependencies are open-source and either audited, formally verified, and/or very well-used and trusted by the Rust cryptographic community;
    \item All cryptographic schemes handle relatively weak randomness gracefully, i.e. any potential statistical bias present in generated random inputs must not lead to catastrophic (and practical!) secret key leakage or forgery attacks;
    \item The scheme and/or implementation are known to be side-channel resistant (against timing attacks, cache attacks, power analysis, etc.) with control flow and power traces largely independent of the secret data used;
    \item Downstream dependencies include few (if any) memory accesses marked as \texttt{unsafe} and, regardless, do not induce any buffer overflow vulnerabilities, hidden API calls or errors which might leak secret data, variable/controllable memory allocations, etc.;
    \item The schemes and their implementation are not used in any way that might be cryptographically insecure at a protocol level.
\end{itemize}
\else
we ensured that all the cryptographic primitives, their implementations, and other dependencies were open-source and either audited or formally verified, were designed to be side-channel resistant, contained no memory access errors, contained no known vulnerabilities related to weak randomness, and were used together in secure ways.
\fi

In the rest of this section, we describe the cryptographic schemes which we use to implement our secure MISC design, as described in \Cref{sec:MISC}.

\subsection{Random Number Generation}

Randomness is the a fundamental building block of many cryptography schemes, allowing secrets to be generated in an unpredictable manner.
\iflong
The security of cryptographic protocols hence relies heavily on the security of its random number generator.
\fi


The ARM TrustZone True Random Number Generator (TRNG) \cite{TRNG} will be used as the primary source of hardware-level randomness.
\iflong
TRNG is known to provide (almost) full entropy bits, and complies with the NIST standard for random bit generation \cite{NIST-TRNG}.
%See the official documentation \cite{TRNG} for more details.
%When more random numbers are needed at the software level or performance issues related to TRNG arise,
\fi
To increase the rate of software-level random number generation and provide cryptographic assurances of continued high-entropy output, the TRNG will be used to seed a cryptographically-secure pseudorandom number generator (CSPRNG) as intended by the official documentation \cite{TRNG}.

We decided to use a ChaCha20-based CSPRNG for similar reasons as the underlying stream cipher (see below). We also tested the quality of our random generators---both the CSPRNG used by our protocols and the TRNG used to seed it---by using the NIST SP 800-22 and Dieharder test suites\!\!
\iflong
with 10mil samples
\fi
, evaluating its results to be free of statistical bias.

\subsection{HMAC}

A hash-based message authentication code (HMAC) is used to provide data integrity. As the name implies, HMAC relies on the security of cryptographic hash functions. Informally, it uses a symmetric key on the message to generate a \textit{tag} $\tau$, which can be verified re-computing the tag themselves and checking that the tag is the same.

Given a secret key $k$ and message $m$, HMAC can be built from a hash function $H$ as follows:
$$
\HMAC_k(m) \defeq H(k_1 \| H(k_2 \| m))
$$
where $k_1 \defeq k \oplus (\texttt{0x36} \cdots \texttt{0x36})$ and $k_2 \coloneqq k \oplus (\texttt{0x5c}\cdots \texttt{0x5c})$. For security purposes, we will be using SHA-256 for the hash function.
\iflong
The length of $k$ and the byte strings that they are XORed with are then chosen to be 32 Bytes. If the user wishes to use the key $k$ of a different length, they may use $H(k)$ instead of $k$ to make it satisfy the length requirement.
\fi
More details about HMAC can be found in the RFC 2104 standards document \cite{rfc2104}. 

%HMAC can be used to provide the authenticity and integrity of the message $m$. Upon receiving the message $m$ and its HMAC tag $\tau$, a verifier can compute the HMAC of $m$ using the shared secret key and verify whether it matches the provided HMAC tag $\tau$ that they received along with $m$. This shows whether $\tau$ truly was generated by the owner of the shared secret key or not, and whether $m$ was altered during the course of communication. However, using HMAC alone can make the protocol vulnerable against replay attacks where an eavesdropper seizes a message-MAC pair $(m, \tau)$ and uses it to impersonate the sender. To prevent this, we will be including nonce which will be used along with the message $m$ to generate the MAC value, and checked for uniqueness.

\subsection{ChaCha20 Authenticated Encryption}

Authenticated Encryption (AE) is a cryptographic primitive which can be used to provide both confidentiality and authenticity of messages. Informally, AE can be thought of as an encryption together with a MAC tag $\tau$, which is \textit{internally} included as part of the ciphertext $c$ and carefully checked during decryption.

Given a shared secret key $k$, encrypting an authenticated message $m$ into ciphertext $c$ is described as follows, where \nonce is a public random nonce (``number used once''):
\begin{align*}
c &\coloneqq \Enc_k(m, \nonce) \\
\Dec_k(c, \nonce) &\coloneqq m \text{ or } \mathsf{Error}
\end{align*}

We decided to use ChaCha20-Poly1305 as 
\iflong
it is much more resilient against timing and caching attacks than other popular private key encryption schemes such as AES \cite{Najm2018ChaCha20}, and is currently considered one of the most secure encryption schemes against cryptoanalytic attacks \cite{Mouha2013Salsa20}. Several experimental results such as \cite{DeStatis2017ChaCha20} show that ChaCha20 is more optimal for embedded systems due to its optimal performance.
\else
it is one of the most secure symmetric authenticated encryption schemes against various side-channel and RNG-based attacks, and is designed to work well on embedded systems.
\fi
As message authenticity is crucial to the design of MISC, ChaCha20-Poly1305 will provide an additional layer of authenticity in our protocol where needed.
%For the sake of brevity, however, we will leave out the details of the ChaCha20-Poly1305 construction.
Curious readers can reference the RFC 8439 standards document \cite{rfc8439} for more details on its construction

\subsection{Ed25519 Digital Signatures}

Digital signatures, similar to Message Authentication Codes (MACs), are used to authenticate the integrity of data. Unlike MACs, however, they have two separate keys: a \emph{private} signing key to sign some message $m$ and produce a \textit{signature}, and a \emph{public} verification key to check that the message has not been tampered with since signing. 
\iflong
Unlike HMACs, where both the ``signer'' and the verifier have access to the same secret key, having a public private signature keypair provides guarantees that only the owner of the signing key (not even the verifier!) can sign the message.
\fi

Given a public-private keypair $(\mathsf{pk}, \mathsf{sk})$, signing a message $m$ is described as follows:
\begin{align*}
    \sigma &\defeq \mathsf{Sign}_{\mathsf{sk}}(m) \\
    \mathsf{Ver}_{\mathsf{pk}}(m, \sigma) &\to \{0,1\}
\end{align*}

We decided to use Ed25519 (i.e., EdDSA over the Curve25519 Twisted Edwards elliptic curve) due to its robustness against various side-channel attacks
\iflong
%\cite{LCRYPT:FA19}
\cite{SSHSoK:OKBAK23}, weak random nonces \cite{rfc8032}, and key substitution attacks \cite{IEEESP:BCJZ21} compared to other popular digital signature schemes such as ECDSA and RSA, and is also easily compatible with embedded systems.
\else
and RNG-based attacks, and is also easily compatible with embedded systems.
\fi
Curious readers can reference the RFC 8032 standards document \cite{rfc8032} for more details on its construction.

%Lastly, while digital signatures (which rely on asymmetric public-private keypairs instead of symmetric secret keys) also provide message authentication, one crucial difference with MACs are that they do not allow for non-repudiation; that is, since the ``signer'' and ``verifier'' of the HMAC hold the same secret key $k$, the ``verifier'' can themselves impersonate the ``signer'' of a message $m$, in turn allowing the true ``signer'' to deny ever having generated the tag $\tau$.

%\jimmy{TODO for Jimmy}

%\jimmy{Which DS scheme we are gonna use? EdDSA?} \jw{Yes. Ed25519 = EdDSA defined over (elliptic curve) Curve25519.}

%\jimmy{Find and read papers about its performance and side-channel resilience.} \jw{Informally: it's relatively efficient and unlike ECDSA, doesn't need RNG for nonces after key generation, so much less able to get its private key from side-channel or bad randomness. Its first paper was ``High-speed high-security signatures'' by djb et al.}

\subsection{\texttt{bcrypt} Password Hashing}

Informally, a hash function $H : \{0,1\}^* \to \{0,1\}^\ell$ takes in an arbitrary-length output and compresses it into a fixed-length ($\ell$-bit) output.
\iflong 
Cryptographic hash functions must also satisfy a number of other useful properties, such as ensuring that very few collisions occur where two messages $m,m'$ can hash to the same digest $H(m) = H(m')$, similar inputs cascade into drastically different outputs and, most importantly, the hash is a one-way function that cannot be efficiently reversed by an attacker.

However, typical cryptographic hash functions such as SHA-2 are often designed to be computed \emph{incredibly} quickly, hashing millions of times per second on a typical PC. For some purposes such as passphrase verification, this is highly non-ideal, as an attacker who can know or guess candidate inputs can generate a \emph{rainbow table} or \emph{dictionary} of possible input-hash mappings in a matter of minutes, especially with access to highly parallelizable computations.

\fi
We decided to use \texttt{bcrypt} since it is a very well-established password-hashing scheme which provides memory-hardness guarantees which remain
\iflong
and allows us to tune the time/memory-tradeoffs via customizable parameters to maximize work factor, all while remaining .
\else
within the functional specifications of the relevant protocol and the operational limitations of the board.
\fi

% \jw{Hash, PRNG, HMAC, Encryption, maybe Digital Signature -- see comments below here in \LaTeX}

% \jimmy{How about we move this section so it comes right after the protocols?}

% \jimmy{I think for protocols we should be as abstract out all crypto parts (e.g., instead of mentioning HMAC, just say MAC) because we should first tell and convince the readers which primitives will be used (e.g., they need to know that we are using MAC first). Then in the crypto section (i.e., this section) we say `We will use HMAC for MAC'. }

% \jw{In typical papers and technical reports, primitives usually comes before proposed design/protocol (``here are the building blocks you need to understand what we did''). For example, tell them what encryption is, what a MAC is, what a random number generator is, etc. I agree we can talk more specifically about instantiations later. ("Implementation" section, where we can bring up build and deployment details too?). I lumped it all into one last year and put it before protocols, but I agree we should put details after.}

% \jimmy{Okay then let's put the primitives here. }

%\subsection{Authenticated Encryption}

 %Authenticated Encryption with Associated Data, or AEAD for short, is a cryptographic primitive which guarantees both confidentiality and also integrity/authenticity for the messages it encrypts.
 %\iflong
 %AEAD allows for the addition of public \textit{associated data} (AD) as input into encryption/decryption, effectively binding the ciphertext to a shared context (often, the ciphertext's packet header). More formally, an
 %\else An \fi AEAD scheme can be defined as follows:

 %\begin{description}
 %   \item[$\mathsf{AEAD}.\enc(K,N,A,P) \to (C,T)$:] Authenticated Encryption (AE) takes as input a symmetric key $K$, a \emph{unique} nonce $N$, public associated data $A$, and plaintext $P$. It outputs its ciphertext $C$ along with an authentication tag $T$ used to verify its authenticity.
 %   \item[$\mathsf{AEAD}.\dec(K,N,A,C,T) \to P$:] Verified Decryption takes as input the symmetric key $K$, the nonce $N$ and associated data $A$ used to encrypt, the ciphertext $C$, and the tag $T$. While decrypting, it uses tag $T$ to verify that $(K,N,A,C)$ was unmodified. It outputs the decrypted plaintext $P$, or error ($\bot$) if the verification check fails.
 %\end{description}

 %We choose to instantiate our AEAD with the authors' implementation of theNIST Lightweight Cryptography winner, A\textsc{scon}-128~\cite{JC:DEMS21}. A\textsc{scon} uses a duplex sponge-based mode of operation. We use the recommended parameters with uniformly random 128-bit key $K$, $r=64$ bit rate (i.e., the block length for processing associated data, plaintext, and ciphertext), and a capacity of $c=256$ bits. The output has $|C| = |P|$ with a 128-bit tag $T$. We choose 128-bit nonces $N$ uniformly randomly.

 %A\textsc{scon}-128 was chosen primarily for its impressive resistance against nonce-misuse even compared to AES-GCM-SIV, small code binaries, and resistance to various side-channel attacks (SCA).
 %\iflong
 %Internally, A\textsc{scon}'s AEAD uses only a 320-bit internal state. For both encryption and decryption it uses a $a=12$ round permutation $p^a$ for initializing the state with key/nonce and finalizing with a tag, and a $b=6$ round permutation $p^b$ for iteratively ``absorbing'' the associated data and input blocks then ``squeezing'' out the output blocks.
 %\else
 %Its permutations use $a=12$ rounds for initialization/finalization and $b=6$ rounds for data processing (i.e., encryption/decryption).
 %\fi
 %See \cite{JC:DEMS21} for more details about how A\textsc{scon} works.

 %\subsection{Cryptographic Hash Functions}

%Cryptographic hash functions are a one-way function which takes an arbitrary-length input and produces a (short) fixed-length output which minimizes the number of potential \emph{collisions} (i.e., two distinct inputs producing the same output) and cannot be efficiently inverted:
%$$H : \{0,1\}^* \to \{0,1\}^\ell$$
%We choose to instantiate our hash function with A\textsc{scon} hash~\cite{JC:DEMS21}, which uses a sponge-based mode of operation. We use the recommended parameters with a rate/block-length of $r=64$ bits, a capacity of $c=256$ bits, and a hash ``digest'' (output) size of $\ell=256$ bits. Its permutations use 12 rounds for both initialization/finalization and data processing.

%A\textsc{scon}-H\textsc{ash} was chosen primarily for its collision resistance (particularly, against identical-prefix attacks) due to the sponge construction, resistance to SCA, and minimal binary size.
%\iflong
%A large proportion shares code with A\textsc{scon}'s AEAD mode as well, which greatly reduces the code binary size.
%\fi
%\newpage

%\subsection{Pseudo-random Number Generators}

%A pseudo-random number generator (PRNG), also known as a deterministic random-bit generator (DRBG), is a function which takes a random and ideally high-entropy \emph{seed} as input to produce a stream of pseudo-random bits which remain unpredictable unless the seed is known.
%\iflong
%With cryptographically-secure PRNGs, one should not be able to infer the seed, internal state between executions, or prior/future inputs \emph{even if an attacker sees the random bits it generates}. PRNGs are especially useful for scenarios such as these, where the operating system or hardware only has access to weak and/or infrequent sources of entropy for generating ``true'' random values, and needs to generate significantly longer ``random-looking'' bitstrings than hardware sources can allow.
%\fi
%More formally, a PRNG can be defined by the following algorithms:

%\begin{description}
%    \item[$\mathsf{PRNG}.\mathsf{init}(s) \to \sigma$:] Given a high-entropy random seed $s$, initialize the internal state $\sigma$.
%    \item[$\mathsf{PRNG}.\mathsf{gen}(\sigma, b, \mathsf{aux}\!=\!\texttt{NULL}) \to (r, \sigma')$:] Given the internal state $\sigma$, \#bits requested $b$, and\\optional auxiliary data $\mathsf{aux}$, update the state and return a $b$-bit pseudo-random $r$.
%    \item[$\mathsf{PRNG}.\mathsf{reseed}(\sigma, e, \mathsf{aux}\!=\!\texttt{NULL}) \to \sigma':$] Given the current internal state $\sigma$, a high-entropy random input $e$, and optional auxiliary data $\mathsf{aux}$, update the state with fresh entropy.
%\end{description}

%\iflong
%There are many ways of constructing PRNGs. A common approach to constructing PRNGs, as defined by NIST SP 800-90A Rev.1~\cite{NIST-DRBG}, is to rely on the security of an underlying cryptographic primitive: for example, using counter-based modes of operation for encryption, hashes, or message authentication codes (MACs) / keyed PRFs. Such constructions are especially useful with limited access to cryptographic libraries or sources of randomness.

%And, as we could not find any cryptographically-secure PRNGs provided by the board's drivers or any other system-level sources of randomness (which most libraries' RNGs often rely on). Many other approaches were deemed too inefficient given the functional constraints of the competition as well, so we chose to use the HMAC/keyed PRF function in the A\textsc{scon} cryptosuite to implement a suitable PRNG. In particular, we chose the HMAC\_DRBG implementation as specified in NIST SP 800-90A since we could not find any SCA-resistant counter-based ciphers to implement CTR\_DRBG with.

%The security of PRNG schemes rely on the security of the primitives used to construct them~\cite{NIST-DRBG} and, in turn, HMACs are less reliant on the collision resistance properties of their underlying hash functions~\cite{NIST-HMAC-MD5}. While the NIST specifications offered such security claims without proofs, HMAC\_DRBG was later formally proven to be secure assuming only that the underlying HMAC acts as a keyed PRF~\cite{WISA:Hirose08}.
%\else
%We implement the HMAC-based DRBG as specified by NIST SP 800-90A Rev.1~\cite{NIST-DRBG} which has been proven secure as long as the underlying HMAC primitive satisfies the properties of a keyed PRF~\cite{WISA:Hirose08}. Furthermore, HMACs are well-known to be less reliant on the collision resistance of their underlying hash functions~\cite{NIST-HMAC-MD5}.
%\fi
%Indeed, the authors' official implementation of A\textsc{scon}
%\iflong
%\footnote{A\textsc{scon} source code: \url{https://github.com/ascon/ascon-c}}
%\fi
%provides a combined HMAC/keyed PRF construction to use.

%See the NIST SP 800-90A specifications for more details on how the PRNG works.

%Regardless of how secure the PRNG algorithm is,
%\iflong
%the randomness of its output relies on the entropy of the seed it was instantiated with, and choices of seed and reseeding policies must be modified as appropriate for the particular device and application using it.
%\else
%it is also important to consider the quality of the entropy sources used to instantiate the seed.
%\fi
%And so, we briefly discuss how we obtained sources of entropy on the board as well.

%\paragraph{Seed generation.}
%\iflong
%Soon after powering on, many hardware-level sources of randomness commonly used for PRNGs are ill-suited for seeding on this microcontroller, either producing obviously non-random values or being easily manipulatable.
%\fi
%One of the most robust sources we could find to create the initial seed on the board was SRAM since, immediately after a power cycle, most memory blocks contain random data prior to initialization, and most blocks remain untouched by the bootloader. We construct the seed by hashing together large blocks of SRAM along with other random data we store on EEPROM as entropy sources. Together, this ensures that the seed will change unpredictably across both power cycles and resets.

%\paragraph{Reseeding policies.} After the board has had time to ``warm up'', we have access to many other sources of entropy. In particular, we incorporate current \texttt{CPUUsageTick} as a source of randomness along with entropy provided by UART packet sends from previous protocol executions, if available. Then, as per NIST recommendations, we hash the entropy inputs and nonce together with the current state of the PRNG to incorporate additional entropy. We deviate slightly from the original specifications, fine-tuning its usage to this specific application by enforcing a reseed after the very first 128-bit random value that's generated. We also chose a significantly more conservative reseed interval of 8192 random values.

%We have vetted the quality of our on-board PRNG implementation using an implementation of the test suites defined in NIST SP 800-22 Rev. 1A~\cite{NIST-PRNG-TESTS}.
%\iflong
%A summary of the test suites' $p$-values are below, where $0.0$ indicates that the test distinguishes the PRNG output from random and $1.0$ indicates that it is indistinguishable:


%\par In the remaining sections, we will discuss at a high-level how each of these primitives are used to implement each PARED protocol, and how this achieves the security requirements.