ma: improve cryptography section

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<n\right)$ of $2n$ random strings of length $n$. The signer publishes a
@@ -1578,7 +1597,7 @@ derive additional signatures by ``mixing'' the two published signatures.
 \subsubsection{Winternitz signatures}
 
 An improvement to basic Lamport signatures as described above are Winternitz signatures as detailed in
-\textcite{merkle01} and \textcite{dods01}. Winternitz signatures reduce public key length as well as signature length
+\cite{merkle01,dods01}. Winternitz signatures reduce public key length as well as signature length
 for hash length $n$ from $2n$ to $\mathcal O \left(n/t\right)$ for some choice of parameter $t$ (usually a small number
 such as 4).
 
@@ -1595,36 +1614,37 @@ p_i$.
 
 To prevent an attacker from forging additional signatures from one signature by calculating $\sigma_i' =
 H\left(\sigma_i\right)$ matching $m_i' = m_i + 1$, this scheme is usually paired with a simple checksum as described in
-\textcite{merkle01}.
+\cite{merkle01}.
 
 \subsubsection{Using hash-based signatures for trigger authentication}
 
 The most basic possible trigger authentication scheme would be to simply generate a random bit string secret key $s$ and
-publish $p = H(s)$ for some hash function $H$. To activate the trigger, $\sigma = s$ would be published and listeners
-could verify that $H(\sigma) = p = H(s)$. This simplistic scheme has one main disadvantage: It is a fundamentally
-one-time construction. To prevent an attacker from re-triggering a listener a second time by replaying a valid trigger
-$\sigma$ all listeners have to blacklist any ``used'' $\sigma$. Alas, this means we can only ever trigger a listener
-\emph{once}. The good part is that any listener that missed this trigger can still be triggered later, but the bad part
-is that once $s$ is burned we are out of options. The trivial solution to this would be to simply inform each listener
-with a whole list of public keys in advance. This however takes $n$ times the amount of space for $n$-fold
-retriggerability. Luckily we can easily derive a scheme that yields $n$-fold retriggerability while using no more same
-space than the original scheme by taking some inspiration from Winternitz signatures above.
+publish $p = H(s)$ for some hash function $H$. To activate the trigger, $\sigma = s$ is published and receivers verify
+that $H(\sigma) = p = H(s)$. This simplistic scheme has one main disadvantage: It is a fundamentally one-time
+construction. To prevent an attacker from re-triggering a receiver a second time by replaying a valid trigger $\sigma$
+all receivers have to blacklist any ``used'' $\sigma$. Alas, this means we can only ever trigger a receiver \emph{once}.
+The good part is that any receiver that missed this trigger can still be triggered later, but the bad part is that once
+$s$ is burned we are out of options. The trivial solution to this would be to simply inform each receiver with a whole
+list of public keys in advance. This however takes $n$ times the amount of space for $n$-fold retriggerability. Luckily
+we can easily derive a scheme that yields $n$-fold retriggerability while using no more same space than the original
+scheme by taking some inspiration from Winternitz signatures above.
 
 In this scheme the secret key $s$ is still a random bit string. The public key is $p = H^n(s)$ for n-times
-retriggerability.  The $i$-th time the trigger is activated, $\sigma_i = H^n-i(s)$ is published, and every listener can
-verify that $\sigma_{i-1} = H\left(\sigma_i\right)$ with $\sigma_0 = p$. In case a listener missed one or more previous
+retriggerability.  The $i$-th time the trigger is activated, $\sigma_i = H^n-i(s)$ is published, and every receiver can
+verify that $\sigma_{i-1} = H\left(\sigma_i\right)$ with $\sigma_0 = p$. In case a receiver missed one or more previous
 triggers it can simply continue computing $H\left(H\left(\sigma_i\right)\right)$ and
 $H\left(H\left(H\left(\sigma_i\right)\right)\right)$ until either reaching the $n$-th recursion level (indicating an
 invalid signature) or finding $H^n\left(\sigma_i\right) = \sigma_j$ with $sigma_j$ being the last signature this
-listener recorded, or $p$ in case there is none.
+receiver recorded, or $p$ in case there is none.
 
-This scheme provides replay protection through listeners memorizing the last signature they activated to. Public key
+This scheme provides replay protection through receiver memorizing the last signature they activated to. Public key
 length is equal to the length of the hash function $H$ used. Even for our embedded systems use case $n$ can
 realistically be up to $\mathcal O\left(10^3\right)$, which is easily enough for our application.
 
-% FIXME here and in previous ~2 pages get transmitter/receiver and sender/listener terminology straight. Also perhaps do
-% some sort of scenario definition introducing those terms somewhere.
-% Also sort out term for "safety reset controller" throughout document
+The ``disarm'' message we discussed above can be integrated into this scheme by encoding the ``enable'' bit into the
+least significant bit of $n$ in our $H^n$ construction. In the chain of valid signatures every second one would be a
+disarm signature. Reset and disarm signatures would alternate in this scheme. By skipping a disarm signature two resets
+can still be triggered directly after one another.
 
 \chapter{Practical implementation}