intro.tex

\section{Introduction}

\outlinecomment{Comments on the structure/outline are in blue.}

\comment{Comments on what to write and other notes to myself are in
  forest green.}

\outlinecomment{Document status: Second, still drafty draft.  not enough on bitcoin, not enough on
  quantum attacks in symmetric crypto.  It'll have to do.}
\outlinecomment{At the moment, there are zero figures in this
  document, which absolutely must be remedied.}

\comment{Reducing the Cost of Implementing the Advanced Encryption Standard as a Quantum Circuit, Landenberg (TQE)}
\comment{Iqbal high-dim semiquantum cryptography}
\comment{X25519 128-bit elliptic curve}
\comment{\cite{mueller20:pqc-dnssec}}
\comment{differential privacy, federated learning, split learning, homomorphic encryption, secure multi-party computation: privacy-preserving ML (Guiseppe Ateniese, Stevens)}

\comment{ Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, and María NayaPlasencia. Quantum differential and linear cryptanalysis. IACR Trans.
Symmetric Cryptol., 2016(1):71–94, 2016.
[17] Hidenori Kuwakado and Masakatu Morii. Security on the quantum-type
even-mansour cipher. In Proceedings of the International Symposium on
Information Theory and its Applications, ISITA 2012, Honolulu, HI, USA,
October 28-31, 2012, pages 312–316. IEEE, 2012.
[18] Gregor Leander and Alexander May. Grover meets simon - quantumly
attacking the FX-construction. In Tsuyoshi Takagi and Thomas Peyrin,
editors, Advances in Cryptology - ASIACRYPT 2017 - 23rd International
Conference on the Theory and Applications of Cryptology and Information
Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part II,
volume 10625 of Lecture Notes in Computer Science, pages 161–178.
Springer, 2017.
[19] Brandon Langenberg, Hai Pham, and Rainer Steinwandt. Reducing the
cost of implementing AES as a quantum circuit. IACR Cryptol. ePrint
Arch., 2019:854, 2019. IEEE Transactions on Quantum Engineering, vol.
1, pp. 1-12, 2020, 2500112. DOI: 10.1109/TQE.2020.2965697.}

\comment{Crawshaw says WireGuard is simpler, and therefore better, than IPsec~\cite{crawshaw20:vpn}.}

\comment{\url{https://www.theregister.com/2021/09/01/nsa_quantum_computing_faq/}}

\comment{L. Jean Camp, 210927 IP-Asia, great summary of events in surveillance+Crypto, esp. Apple on-device scanning.}

\comment{\url{https://datatracker.ietf.org/doc/draft-irtf-cfrg-spake2/}}

\comment{Barak~\cite{2005.02421,barak:cryptoeprint:2017:365} and his thread on complexity and PKE \url{https://twitter.com/boazbaraktcs/status/1452749576457367557}.}

\comment{https://csrc.nist.gov/publications/detail/journal-article/2021/development-of-the-advanced-encryption-standard}

https://eprint.iacr.org/2021/1637
By Hilarie Orman, who was our program manager from ARPA for the Netstation project back in the mid-90s.

\comment{https://csrc.nist.gov/projects/post-quantum-cryptography/selected-algorithms-2022}
\comment{https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms}

Those who study the fields of quantum computing and quantum
communication quickly become familiar with Shor's algorithm for
factoring large numbers and calculating discrete
logarithms~\cite{shor:siam-factor}, and with quantum key
distribution~\cite{bennett:bb84,PhysRevLett.68.557,ekert1991qcb,PhysRevLett.108.130503,xu2015measurement,Vazirani:2019:FDI:3321370.3310974,RevModPhys.81.1301,PhysRevLett.85.441}.
These two independent discoveries both impact classical cryptography,
one by making it more vulnerable, the other by making it stronger --
in theory.

However, the direct, organized study of cryptography often ends there,
despite the importance of cryptography as a driving force in funding
and potential deployment of quantum technology.  The target audience
for this document is quantum computing researchers who are familiar
with Shor's algorithm, Grover's algorithm and QKD, but who have only a
very rough idea of what it means to actually encrypt data and to use
encryption in a real-world setting.  This document will help to orient
such readers so that they can communicate effectively with the
classical communications and cryptography communities, and help them
to ask the right research questions, such as:

\begin{itemize}
\item What QKD key generation rate (measured in both steady-state rate
  and latency to begin a connection) is appropriate for
  quantum-protected activities such as:
  \begin{itemize}
  \item e-commerce, especially web browsing; and
  \item intra-organization network-to-network connection?
  \end{itemize}
  Especially, under what performance conditions will existing mechanisms
  be replaced effectively one-for-one, and under what conditions will new
  capabilities be enabled?
\item When will quantum computers be able to effectively attack:
  \begin{itemize}
  \item the generation of cryptographic keys used for communications;
  \item bulk data encryption itself;
  \item digital signatures and hashes; and
  \item blockchain?
  \end{itemize}
\item What mathematical techniques commonly used in cryptography might
  be adaptable to use in new quantum-based attacks?
\item What is the response of the classical cryptographic and Internet
  protocol and operations communities to the potential development of
  quantum computers?
\end{itemize}

Addressing all of these questions in depth in a single document is
impossible, but to help quantum researchers and engineers effectively
answer these questions in concrete ways that help guide their own
work, this document introduces four key areas of modern cryptographic
practice and associated historical background:

\begin{enumerate}
\item the mathematics of encryption, including how math can be used to
  attack encryption;
\item how encryption is incorporated into complete communication
  systems;
\item how those systems are used to achieve the ``CIA'' goals of
  confidentiality, integrity and availability; and
\item how cryptography influences and is influenced by policy, both
  corporate/organizational and governmental.
\end{enumerate}

What this document is \emph{not}:

\begin{itemize}
\item a survey or tutorial on either QKD or Shor's algorithm;
\item a full survey of the massive amounts of clever research done in
  quantum security algorithms
  (e.g.,~\cite{PhysRevA.100.052326,buhrman14:_posit_based_quant_crypt,ben-or2005fast,Crepeau:2002:SMQ:509907.510000});
\item a survey of techniques for certifying the quantumness of states~\cite{eisert2019cert}; or
\item a full tutorial on cryptography.
\end{itemize}

\subsection{Security and Encrypted Communications}

\begin{figure}
  {\color{Magenta} Add a figure with basic messages and actors.}
  \caption{Encrypted communications can roughly be divided into the
    tasks of authentication, encryption, and bulk data transfer,
    consisting of encrypt-transmit-decrypt.}
  \label{fig:encrypted-comm}
\end{figure}

Before we dive into encryption, it is useful to be aware that computer
and communications security people do not think of encryption itself
as an end goal, but rather as a tool used in service of achieving three
goals:

\begin{itemize}
\item {\bf integrity:} the condition that the data has not been
  modified or tampered with by an adversary
\item {\bf confidentiality or privacy:} the data hasn't been disclosed to anyone unauthorized
\item {\bf availability:} access to data (or a computational or
  communication service) cannot be denied by an attacker
\end{itemize}

Encryption helps with all three of those goals, but does not directly
achieve any of them without substantial infrastructure around the
encryption itself.  Achieving these goals is the subject of intensive
research and engineering.  To give a feel for the relative importance
of cryptography, a canonical textbook devotes about 10\% of its length
to cryptography~\cite{bishop2002art}.

For the purposes of this paper, we will focus on encryption, with the
working assumption of a two-party exchange of data across an otherwise
unsecured network.  In this paper, we will study only mathematical
attacks on cryptography, not \emph{side channel} attacks such as
observing the time or energy used for encryption or other weaknesses
of the systems themselves.  An encrypted conversation involves, at the
macro level, three phases:

\begin{enumerate}
\item {\bf Authentication:} proving that you are who you say you are;
\item {\bf Key generation:} creating the keys used for bulk data encryption,
  possibly including regeneration of keys mid-connection
  (\emph{rekeying}); and
\item {\bf Encryption/sending/decryption:} secure exchange of the
  user's valuable bulk data.
\end{enumerate}

That's a bit of an oversimplification, as we'll see below when we talk
about IPsec (Sec.~\ref{sec:ipsec}), but good enough for now.

Rekeying, the changing of the cryptographic keys used during long
communication sessions mentioned above, raises the question: how often
\emph{should} keys be changed?~\footnote{This question, in fact,
  prompted the development of this entire document.}  This question
proved to be \emph{remarkably} hard to answer from basic Internet
searches, including reading cryptography research papers and the
\emph{extensive} mailing list archives from development of key
Internet protocols.  Consequently, some parts of this document
(annotated where appropriate) are derived from direct conversation
with the principals.

\rdv{Dives a little too directly into rekeying here.  Needs more on
  e.g. latency first.}
There are two fundamental reasons for periodic rekeying:

\begin{enumerate}
\item Having a long string of data encrypted with the same key increases
the probability of an attacker being able to find the key.
\item As a practical matter, reducing the amount of data that is exposed
in the event that a key is broken is good stewardship of your data.
\end{enumerate}

Intuitively, changing the key ``often'' makes it both harder and less
valuable for an attacker to find a key.  Turning this observation into
concrete, numeric recommendations is hard, but as we will see
(Secs.~\ref{sec:birthday}, \ref{sec:ipsec-cryptan} and
\ref{sec:tls-rekeying}) rekeying every half hour comfortably meets
basic cryptanalysis constraints, if the key generation rate isn't high
enough to support one-time pad.

\subsection{Concepts and Terminology}

\emph{Cryptography} is the science of secrets, and has a history going
back several thousand years~\cite{kahn1996codebreakers,singh1999code}.
Modern practice with digital communications effectively began in the
1970s~\cite{schneier96:_applied_crypto,menezes1996handbook}.
\emph{Computer security} often involves cryptography, but is a far
broader field tasked with ensuring the confidentiality, integrity and
availability of data, computing and communication
resources~\cite{bishop2002art}.

There are two major kinds of cryptography: {\bf symmetric key
  cryptography} and asymmetric key, also known as {\bf public key
  cryptography}.  Due to the high costs of computation for public key,
bulk data encryption is done using symmetric key.  Symmetric
encryption comes in two kinds, block ciphers and stream ciphers.
These days pretty much everything seems to be block, but I'm not sure
why.  \aonolook{}

For clarity, several terms are applied to data:

\begin{itemize}
\item {\bf cleartext:} data that isn't encrypted; generally, data for
  which encryption is unnecessary or not planned
\item {\bf plaintext:} the original, unencrypted message
\item {\bf ciphertext:} the encrypted message
\end{itemize}

Several important terms are used when discussing the keys and their
management:

\begin{itemize}
\item {\bf forward secrecy:} keeping your data secret in the future, esp. by
  building a cryptosystem that doesn't reuse keys
\item {\bf cryptoperiod:} the time that a specific key is authorized for use
\item {\bf session keys:} the keys used for one communication session
\item {\bf subkeys:} keys used for a portion of an encryption process, derived
  from a subset of the bits of the session key
\item {\bf rekeying:} changing the keys used in the middle of a session
\item {\bf public key:} the half of a public/private key pair that is
  used by the sender, and which can be published to the world at
  large
\item {\bf private key:} the half of a public/private key pair that is
  kept secret by the receiver, used to decrypt a message encrypted
  with the public key
\end{itemize}

Mathematical attacks on encrypted communications
generally fall into one of three categories:

\begin{itemize}
\item {\bf unknown plaintext:} this is the most basic form of the
  problem, and the hardest, for two reasons.  First, with no knowledge
  of the original input, it is impossible to work the encryption
  forward to test key candidates.  Second, when trying decryption
  using a candidate key, how can the attacker recognize when they have
  found the message (and hence the key)?  \rdv{connection btw
    sentences here is clunky} Failure to decrypt properly
  will leave only unintelligible, random data, while success will
  produce words from the dictionary or other recognizable text, or
  more generally, data with low \emph{entropy} (Sec.~\ref{sec:defense}).
\item {\bf known plaintext:} when an attacker knows what the plaintext
  corresponding to a particular ciphertext is, and attempts to find
  the key; not uncommon given the regularity of communications such as
  web browsing or email
\item {\bf chosen plaintext:} when the attacker can control the text to be
  encrypted, but obviously not the key; rarer than known plaintext,
  but can happen with small devices that a person may "own" but not
  always completely control, or if the attacker partially controls
  some subset of resources, such as a related web server, or has
  compromised one or more hosts behind an encryption gateway
\end{itemize}

We also need these definitions:

\begin{itemize}
\item {\bf brute force/exhaustive search:} checking every possible key, which of
  course is $2^n$ for an $n$-bit key.  The expected hit time will be
  after half that number.  If you have a method that will find a
  key in substantially less than $2^{n-1}$ trials, you have "broken" the
  cipher, even if your attack isn't necessarily practical in the short
  run.
\item {\bf pentesting:} penetration testing, deliberate attempts by
  ``white hat'' or ``red team'' researchers to crack the system.
\end{itemize}

\aonolook{}
And three mathematical definitions I know for algebra on the real
numbers, but I'm a little fuzzy on in the bitwise, cryptographic
context:

\begin{itemize}
\item {\bf linear function:} I think in this context, $f(x,y)$ is a linear
  function of some bits if it involves only a linear addition of
  the inputs, and $f(0,0) = 0$ (origin is preserved).  Multiplication
  (AND) is disallowed?  Importantly, $f(x_1 + x_2) = f(x_1) + f(x_2)$.
\item {\bf affine function:} same as a linear function, but an offset is
  allowed, such that $f(0,0) = 1$ (origin isn't necessarily preserved)
  (equivalent to a translation in a real space $R^n$).
\item {\bf nonlinear function:} A nonlinear function is one in which $f(x+y) \ne f(x) + f(y)$ for some values $x$ and $y$. An affine function is one type of nonlinear function. I'm definitely fuzzy here...multiplication and
  arbitrary mappings are allowed?
\end{itemize}