From 37efb07f30ef9723406752ac81fa856433b06ac2 Mon Sep 17 00:00:00 2001 From: jaseg Date: Mon, 25 May 2020 15:22:23 +0200 Subject: ma: improve cryptography section --- ma/safety_reset.bib | 18 ++++++ ma/safety_reset.tex | 164 +++++++++++++++++++++++++++++----------------------- 2 files changed, 110 insertions(+), 72 deletions(-) diff --git a/ma/safety_reset.bib b/ma/safety_reset.bib index 77a0d3b..f8fa07e 100644 --- a/ma/safety_reset.bib +++ b/ma/safety_reset.bib @@ -1497,4 +1497,22 @@ publisher = {{Heise Online}}, } +@Article{kerckhoff01, + author = {Auguste Kerckhoff}, + date = {1883}, + journaltitle = {Journal des sciences militaires}, + title = {La cryptographie militaire}, + pages = {5-38}, + volume = {IX}, +} + +@Online{kerckhoff02, + author = {Fabien Petitcolas}, + date = {2020}, + title = {Kerckhoffs' principles from ``La cryptographie militaire''}, + url = {https://www.petitcolas.net/kerckhoffs/index.html}, + language = {English}, + urldate = {2020-05-25}, +} + @Comment{jabref-meta: databaseType:biblatex;} diff --git a/ma/safety_reset.tex b/ma/safety_reset.tex index 371de28..5645feb 100644 --- a/ma/safety_reset.tex +++ b/ma/safety_reset.tex @@ -984,11 +984,11 @@ infringement. In order to gain anything by adding our reset controller to the smart meter's already complex design we must satisfy two interrelated conditions. \begin{enumerate} -\item \textsc{security} means our reset controller itself does not have any remotely exploitable flaws -\item \textsc{safety} menas our reset controller will perform its job as intended +\item \emph{security} means our reset controller itself does not have any remotely exploitable flaws +\item \emph{safety} menas our reset controller will perform its job as intended \end{enumerate} -Note that our \textsc{security} property includes only remote exploitation, and excludes any form of hardware attack. +Note that our \emph{security} property includes only remote exploitation, and excludes any form of hardware attack. Even though most smart meters provide some level of physical security, we do not wish to make any assumptions on this. In the following section we will elaborate our attacker model and it will become apparent that sufficient physical security to defend against all attackers in our model would be infeasible, and thus we will design our overall system @@ -1047,7 +1047,7 @@ Using an asymmetric cryptographic design centered around the \emph{reset authori denial-of-service attacks on our system by any of the four attacker types. All reset commands in our system originate from the \emph{reset authority} and are cryptographically secured to provide authentication and tamper detection. Under this model, attacks on the electrical grid components between the \emph{reset authority} and the customer device -degrade into man-in-the-middle attacks. To ensure the \textsc{safety} criterion from Section \ref{sec_criteria} holds we +degrade into man-in-the-middle attacks. To ensure the \emph{safety} criterion from Section \ref{sec_criteria} holds we must make sure our cryptography is secure against man-in-the-middle attacks and we must try to harden the system against denial-of-service attacks by the attacker types listed above. Given our attacker model we cannot fully guard against this sort of attack but we can at least choose a commmunication channel that is resilient against denial of service @@ -1061,7 +1061,7 @@ out-of-scope. \subsection{Complex microcontroller firmware} -The \textsc{security} property from \ref{sec_criteria} is in a large part reliant on the security of our reset +The \emph{security} property from \ref{sec_criteria} is in a large part reliant on the security of our reset controller firmware. The best method to increase firmware security is to reduce attack surface by limiting external interfaces as much as possible and by reducing code complexity as much as possible. % FIXME formalize this as something like "Design Goal DG-023-42-1" ? @@ -1486,76 +1486,95 @@ error-correcting codes and we had no particular difficulty finding either. \label{sec-crypto} Informally the system we are looking for can be modelled as consisting of three parties: The trusted -\textsc{Transmitter}, one of a large number of untrusted \textsc{Receivers}, and an \textsc{Attacker}. These three play +\emph{transmitter}, one of a large number of untrusted \emph{receivers}, and an \emph{attacker}. These three play according to the following rules: -\begin{enumerate} - \item \textsc{Transmitter} and \textsc{Attacker} can both transmit any bit sequence - \item \textsc{Receiver} receives any transmission by either \textsc{Transmitter} or \textsc{Attacker} but cannot - distinguish between the two on the signal level - \item \textsc{Attacker} knows anything a \textsc{Receiver} might know - \item \textsc{Transmitter} is stronger than \textsc{Attacker} and will ``win'' in simultaneous transmission - \item Both \textsc{Transmitter} and \textsc{Receiver} can be seeded with some information on each other such as +\begin{description} + \item[Access.] Both transmitter and attacker can transmit any bit sequence. + \item[Indistinguishability.] The receiver receives any transmission by either but cannot distinguish between them. + \item[Kerckhoff's principle.] The attacker knows anything any receiver might know\cite{kerckhoff01,kerckhoff02}. + \item[Priority.] The transmitter is stronger than an attacker and will ``win'' during simultaneous transmission. + \item[Seeding.] Both transmitter and receiver can be seeded out-of-band with some information on each other such as public key fingerprints. -\end{enumerate} +\end{description} -We are not interested in congestion scenarios where an attacker attempts to disrupt an ongoing transmission by the -transmitter. In practice there are several avenues to prevent such attempts including the following. Compromised loads -that are being abused by the attacker can be manually disconnected by the utility. Error-correcting codes can be used to -provide resiliency against small-scale disturbances. Finally, the transmitter can be designed to have high enough power -to be able to override any likely attacker. +We are not interested in congestion scenarios where an attacker attempts to disrupt an ongoing transmission. In practice +there are several avenues to prevent such attempts. Compromised loads that are being abused by the attacker can be +manually disconnected by the utility. Error-correcting codes can be used to provide resiliency against small-scale +disturbances. Finally, the transmitter can be designed to have high enough power to be able to override any likely +attacker. Our goal is to find a cryptographic primitive that has the following properties: \begin{enumerate} - \item \textsc{Transmitter} can produce a transmission bit sequence $\mathbf{s}$ (or equivalently a set of such - sequences) that \textsc{Receiver} can uniquely identify as being generated by \textsc{Transmitter}: - $\mathcal{R}\left(\mathbf{s}\right) = 1$. Upon reception of this sequence, \textsc{Receiver} performs the safety - reset. - \item \textsc{Attacker} cannot forge $\mathbf{s}$, that is find $\mathbf{s}'$ such that + \item The transmitter can produce a message bit sequence $\mathbf{s}$ that a subset of receivers can identify + as being generated by the transmitter: $\mathcal{R}\left(\mathbf{s}\right) = 1$. On reception of this sequence, + all addressed receivers performs a safety reset. + \item The attacker cannot forge $\mathbf{s}$, i.e.\ find $\mathbf{s}'$ such that $\mathbf{s} \neq \mathbf{s}' \land \mathcal{R}\left(\mathbf{s}'\right) = 1$ - \item Our system conforms to an at-most-once semantic. That is, upon transmission of a valid bit sequence coded for - a particular \textsc{Receiver} or set of receivers each one either performs exactly one safety reset or none at - all. We cannot achieve an exactly-once semantic since we are using an unidirectional lossy communication - primitive. More coloquially, \textsc{Receiver} might be offline due to a localized power outage and might thus - not hear \textsc{Transmitter} even if our broadcast primitive is reliable. The practical impact of this - limitation can be mitigated by transmitter simply repeating itself until the desired effect has been achieved. + \item Our system conforms to an at-most-once semantic. This means upon transmission of a valid bit sequence coded + for a set of receivers each one either performs exactly one safety reset or none at all. We cannot achieve an + exactly-once semantic since we are using an unidirectional lossy communication primitive. A receiver might be + offline (e.g.\ due to a localized power outage) and then would not hear the transmission even if our broadcast + primitive was reliable. Since there is no back-channel, the transmitter has no way of telling when that happens. + The practical impact of this can be mitigated by the transmitter by repeating the transmission a number of + times. + \item The message should be short. Our communications channel is outrageously slow compared to anything else used in + modern telecommunications and every bit counts. \end{enumerate} -An important limitation from the rules of our setup above is that \textsc{Attacker} can always record the bit sequence -\textsc{Transmitter} transmits and replay that same sequence later. Before considering any cryptographic approaches we -can make the preliminary observation that we can trivially prevent \textsc{Attacker} from violating the -at-most-once criterion by simply requiring \textsc{Receiver} to memorize all bit sequences that have been transmitted -thus far and only reacting to new bit sequences. This means an attacker might be able to cause offline receivers to -reset at a later point, but considering our goal is to reset them in the first place this would not pose a danger to the -system. -% FIXME elaborate why this is not a threat, and possible mitigations - -As it seems we need a cryptographic primitive that looks somewhat like a signature. Different from a signature however, -we have somewhat relaxed constraints here: While cryptographic signatures need to work over arbitrary inputs, all we -want to ``sign'' here is the instruction to perform a safety reset. Since this is the only message we might ever want to -transmit, our message space has only one entry and thus the informational content of our message is 0 bit! All the -information we want to transmit is already encoded \emph{in the fact that we are transmitting}, and we do not require -any further payload to be transmitted. This means we can omit the entirety of the message and just transmit whatever -``signature'' we produce. This is useful since we have to conserve transmission bits so our transmissions do not take -exceeedingly long time over our extremely slow communication channel. +Along with the indistinguishability property the first requirement implies that we need a cryptographic +signature\cite{lamport01}. However, we have relaxed constraints on this signature compared to cryptographic practice. +While cryptographic signatures need to work over arbitrary inputs, all we want to ``sign'' here is the instruction to +perform a safety reset. This is the only message we might ever want to transmit so our message space has only one +entry. The information content of our message thus is 0 bit! All the information we want to transmit is already +encoded \emph{in the fact that we are transmitting}. We do not require any further payload to be transmitted. We can +omit the entirety of the message and just transmit whatever ``signature'' we produce. This is useful to conserve +transmission bits so our transmission does not take an exceeedingly long time over our extremely slow +communication channel. + +We can modify this construction to allow for a small number of bits of information content in our message (say two or +three instead of zero) at no transmission overhead. We could transmit the cryptographic signature as usual but simply +omit the message. The message is only a few bits and we are dealing with minutes of transmission time so the receiver +can reconstruct the message through brute-force. Though this tradeoff between computation and data transmission might +seem inelegant it does work for our extremely slow link for very few bits. + +There is an important limitation in the rules of our setup above: The attacker can always record the reset bit sequence +the transmitter transmits and replay that same sequence later. Even without cryptography we can trivially prevent an +attacker from violating the at-most-once criterion. If every receiver memorizes all bit sequences that have been +transmitted so far it can detect replays. With this mitigation by replaying an older authentic transmission an attacker +can cause receivers that were offline during the original transmission to reset at a later point. Considering our goal +is to reset them in the first place this should not pose a danger to the system's safety or security. + +A possible scenario would be that an attacker first causes enough havoc for authorities to trigger a safety reset. The +attacker would record the trigger transmission. We can assume most meters were reset during the attack. Due to this the +attacker cannot cause a significant number of additional resets immediately afterwards. However, the attacker could +wait several years for a number of new meters to be installed. These new meters might not yet have updated firmware +including the lastest transmission. This means the attacker could cause them to reset by replaying the original +sequence. + +A possible mitigation for this risk would be to introduce one bit of information into the trigger message that is +ignored by the replay protection mechanism. This \emph{enable} bit would be $1$ for the actual reset trigger message. +After the attack the transmitter would then perform scheduled transmissions of a ``disarm'' message that has this bit +set to $0$. This message informs all new meters and meters that were offline during the original transmission of the +original transmission for replay protection without actually performing any further resets. We could use any of several traditional asymmetric cryptographic primitives to produce these signatures. The comparatively high computational effort required for signature verification would not be an issue. Transmissions take several minutes anyway and we can afford to spend some tens of seconds even in signature verification. Transmission length and by proxy system latency would be determined by the length of the signature. For RSA signature length is the -modulus length (i.e. larger than 1000 bit for even basic contemporary security). For elliptic curve-based systems -signature size is approximately twice the curve length (i.e. ~300 bit for contemporary security). However, we can do -better than this: We can exploit the strange nature of our setting that our effective message entropy is 0 bit to derive -a more efficient scheme. +modulus length (i.e. larger than \SI{1000}{bit} for very basic contemporary security). For elliptic curve-based systems +signature size is approximately twice the curve length (i.e. $\SI{\approx 300}{bit}$ for contemporary security). +Thanks to our unique setting we can do better than this. We can exploit that our effective message entropy is 0 bit to +derive a more efficient scheme. \subsubsection{Lamport signatures} -In 1979, \textcite{lamport02} introduced a signature scheme that is based only on a one-way function such as a +1979, Lamport in \cite{lamport02} introduced a signature scheme that is based only on a one-way function such as a cryptographic hash function. The basic observation is that by choosing a random secret input to a one-way function and publishing the output, one can later prove knowledge of the input by simply publishing it. In the following paragraphs we will describe a construction of a one-time signature scheme based on this observation. The scheme we describe is the -one usually called a ``Lamport Signature'' in modern literature and is slightly different from the variant described in -the 1979 paper, but for our purposes we can consider both to be equivalent. +one usually called a ``Lamport Signature'' in modern literature but is slightly different from the variant described in +the 1979 paper. For our purposes we can consider both to be equivalent. \paragraph{Setup.} In a Lamport signature, for an n-bit hash function $H$ the signer generates a private key $s = \left(s_{b, i} | b\in\left\{0, 1\right\}, 0\le i