Authorization

The persnickety reader might point out that in a closer reading of this problem, what matters is not the “identity” (e.g., name) of the party, but whether they are the “right” party. For a human-space example, when hospital patient Alice is about to receive an injection from someone dressed in white, what matters to Alice is not the name of this person, but that he or she is a genuine clinician. As Chapter 4 hinted, this problem can be messy even in the IoC.

The Somewhat Impossible

Casual discussions of applied cryptography often refer to impossibilities. “If Alice does not have the key $K$, then she cannot calculate $y=D_K\left(X\right)$.” One may wonder: what exactly does “cannot” mean?

The answer is both satisfyingly precise and annoyingly ambiguous. Building on early 20th-century work in logic, computer science has developed nice mathematical formalisms for the concept of possible computation:

Computability

Can a computational algorithm actually exist for a given problem?

Size and Complexity

Thinking of a computational problem as a family of instances, one for each possible value of its input parameters, we can define its size in terms of the size of the input parameters. For a particular algorithm solving a computational problem, we can precisely talk about how the sizes of the necessary computational resources (e.g., time or space) grow with the size of the problem instance.

Complexity theory nicely factors out the differences due to low-level details of particular computing platforms. It lets us talk about upper bounds (the maximum resources necessary to solve some problem) and, less often, lower bounds (the minimum resources required). It also lets us talk about reduction: sometimes, whenever we have an instance of a problem $P_1$, we can turn it into an instance of $P_2$. Reduction thus lets us connect the complexity of one problem to that of the other; for example, $P_1$ can be no harder than $P_2$ plus the transformation. (And yes, a full treatment would require thinking about more general variations, such as solving $P_1$ using subroutine calls to a $P_2$-solver.)

Complexity lets computer scientists talk about intractability. A problem is intractable when, even though it can be computed, the minimum resources necessary grow far too quickly as problem instance size grows—so once the instance becomes nontrivial, it would take more time than remains in the known universe’s lifetime to finish the calculation.

When computer scientists talk about “impossibility,” they’re usually using this framework. However, the framework gives a range of definitions:

Impossible

• The problem is in fact not computable.

Practically impossible

• The problem is computable, but provably intractable.

Believed practically impossible

• The problem is computable and not yet proven intractable, but has been shown to be at least as hard as a large family of problems everyone believes are probably intractable (e.g., NP-hard).

Hopefully practically impossible, with some evidence

• The problem is computable and, while not known to be NP-hard, is at least as hard as another problem (e.g., factoring) whose difficulty is unknown but which everyone suspects is hard.

Hopefully practically impossible, with no evidence

• The problem is computable and not known to be as hard as a suspected-hard problem, but it looks difficult.

The reason the “annoying ambiguity” comes in is that, in practical cryptography, the “impossibility” definition is usually one of these last two: “hopefully practically impossible.”

Symmetric Cryptography

A basic way to approach it is to think of it as a pair of transformations: $E$, taking plain text to ciphertext, and $D$, doing the reverse—so $D\left(E\right(x\left)\right)=x$ for any $x$. (Think “encipher” and “decipher,” as the perhaps more natural terms “encrypt” and “decrypt” have more specialized meanings to some subcommunities.) However, for this to be useful, the system needs the additional constraint that at least one of these functions (if not both) requires a special privilege to be able to carry it out. This privilege gets embodied as an additional numeric parameter called a key.

For most of human history, there was only symmetric cryptography, where the key necessary to perform $E$ was the same key necessary to perform $D$. If $y=E(k,x)$, then only a party who knew $k$ could take $y$ back to $x$ via $D(k,y)$.

Common symmetric algorithms include DES (the US standard for a few decades, now retired) and AES (the new US standard).

The impossibility criterion here (that one must know $k$ to take $E(k,x)$ back to $x$) is generally the weakest: “hopefully impossible.” For all practical cryptographic schemes, an adversary can certainly perform a forbidden transformation by brute force: trying all possible keys. Hence, discussions of crypto schemes usually talk about key length: the longer the key, the longer a successful brute-force attack would take. Deployments ended up hoping that the keys were long enough that this type of attack was essentially infeasible.

However, history provides some cautionary tales. Consider last century’s DES: a widely used security textbook still said it was safe to use even after a team coordinated by the Electronic Frontier Foundation (EFF) had built and demonstrated a machine that could brute-force crack its 56-bit keys. Another noteworthy trend was the emergence (in the public world) of successful side-channel attacks. The computers that perform the cryptographic computation are themselves machines in the physical world, and it turned out that by measuring properties of these machines (such as the time they took or the power they consumed), one could often learn the key they were using. (I personally saw a commercial DES device reveal its key with only one computation: when we looked at the power consumption, there were 56 spikes, some short, some long.)

Perhaps the most natural use of symmetric cryptography is to protect messages for secrecy. If Alice wants to send a message $M$ to Bob and have confidence that no one else can read it during transit, she can instead send $E(k,M)$—as long as she and Bob already know $k$. Symmetric cryptography can also be used for authentication. For a simple and occasionally dangerous example:

1. Bob might send Alice some random $x$.

2. Alice encrypts it with her key $k$ and returns it.

3. Bob decrypts the returned value and checks that he gets $x$ back.

Again, Alice and Bob need to share $k$ first.

Another variation is message authentication. Again, for a simple and occasionally dangerous example:

• Alice and Bob share a secret key $k$.

• Alice wants to send a message $M$ to Bob, but have Bob have assurance that Alice really sent it.

• So, she uses her secret key and favorite symmetric cryptosystem to calculate some short message authentication code based on $M$. For example, maybe she calculates the full $E(k,M)$, but then uses the last 16 bytes as the MAC.

• Alice sends the message and the MAC to Bob.

• Bob then calculates the MAC on the message he received, and compares it to the MAC that he received. If they match, then he has high confidence that the sender of the message also knows the secret key $k$.

Public Key Cryptography

As the previous examples kept repeating, use of symmetric cryptography requires that the parties involved share a key. This requirement can be problematic. One reason is logistics: if Alice and Bob need cryptography to set up a secure communication channel, then what channel do they use to set up the shared key? Another is scalability: if Alice wants to talk to $n$ parties, she will need $n$ different secret keys; if $n$ players need pairwise communication, the system needs about $n^2$ different keys. Yet another reason is semantic: a shared key is useful only among the parties who share it. When Bob receives a message $M$ from Alice, he can conclude it came from Alice by verifying its MAC with the key he shares with her. But he can’t use this MAC to prove to anyone else that Alice said $M$.

Public key cryptography (also known as asymmetric cryptography) provides ways to overcome these limitations.

From the dawn of time to the age of disco (as I like to point out each time I teach about this material), humanity only had symmetric cryptography. In the 1970s, the idea emerged of replacing the single key with a keypair $k_e,k_d$, such that enciphering under $k_e$ is inverted by deciphering under $k_d$. At least one of these keys cannot be derived from knowing the other—hence the term “public key,” since this latter one can be made public without harm. For standard public key cryptosystems such as RSA, the impossibility criteria is “probably impossible”: deriving the nonpublic key from the public information appears to be as hard as factoring.

Public key cryptography can do the same things symmetric cryptography does, except now Alice and Bob no longer need to share a secret key:

Encryption

If Alice wants to send message $M$ to Bob and keep the contents secret from anyone else, she need only encipher it with Bob’s public key. Only someone knowing Bob’s private key can then transform this back to $M$.

Message authentication

If Alice wants Bob to know that she sent message $M$, she can digitally sign it by doing a transformation with her private key. Bob—or anyone else—can verify that this signature matches $M$ using Alice’s public key.

Entity authentication

Alice can authenticate herself to Bob by digitally signing a random challenge he provides.

How do parties know the public keys of other parties? Read on.

As before, these examples are just simple sketches. Real-world uses of public key cryptography usually have more complexity; encryption will also use symmetric cryptography (discussed previously), signatures will also use cryptographic hash functions (described shortly), and both will likely use various padding functions.

Public Key Infrastructure

Initially, using public key cryptography brings the number of keys a device needs to know down to $n$: its own keypair, and the public key of each other device it wants to communicate with. However, the ability of public key cryptography to enable digital signatures—a party can use its private key to sign an assertion verifiable by anyone knowing its public key—brings the number down to two: a device only needs to know its own keypair and the public key of the trust root it trusts to sign assertions saying what the public keys are of the other devices with which it needs to work. In either case, the number of secrets a device needs to know is exactly one: its own private key. This constraint limits the damage that compromise of a device can cause.

Public key infrastructure is the catch-all term for the mechanics necessary to establish, maintain, and distribute these assertions (certificates) and keypairs. Typically, PKI includes components to solve these problems:

• How does a keyholder obtain a certificate from a trust root?

• How does a relying party decide who its trust roots are?

• How does a relying party get its hands on a path from a trust root to a particular certificate?

• What exactly should a relying party conclude from discovering a path with each link apparently signed properly?

• What do we do when the assertion a certificate makes (e.g., “$X$ has public key $E_x$”) is no longer true and needs to be revoked?

X.509 is the family of standards and techniques (e.g., [9]) that has come to dominate the way most PKI is done in practice, although other rivals (e.g., [5, 14]) surface now and then, as do regular critiques (e.g., [8]). X.509 allows for identity certificates (assertions about the name of a keyholder) as well as attribute certificates (assertions about some more general properties), although use of the latter is more experimental. X.509 (and other PKI approaches) also defines some semantics for what should be concluded from a chain of certificates: if Alice issues a signed assertion about Bob, and Bob issues one about Cathy, what conclusion should Dave draw if he sees both assertions?

Cryptographic Hashing

Another item in the standard toolkit is cryptographic hash functions—essentially, encryption that cannot be decrypted. (In the context of security, these are often just called hash functions; the “cryptographic” is implied.)

A hash function $H$ takes an arbitrarily long string $x$ down to some fixed-length strength $H\left(x\right)$, but with the property that this transformation cannot be inverted: given a $z$, one cannot find a $y$ such that $H\left(y\right)=z$. (The impossibility criterion is usually “hopefully impossible.”) This impossibility still holds even if one is given a number of other hints, such as a $y^{\text{'}}$ that hashes to something close to $z$, or the first half of a $y$ that hashes to $z$.

An early application of such one-way functions was for checking whether an entered password was correct (do the one-way transformation, then compare that to some stored value) without allowing an adversary who gets hold of the file of transformed passwords to recover the originals.

SHA-2 is an example of a hash function currently in use.

One use of hashing is to shorten digital signatures: instead of applying her RSA private key to a whole message $M$, Alice will first calculate $H\left(M\right)$ and then apply her private key to that. Another is to almost do an asymmetric proof-of-knowledge: if Alice knows a secret $x$, she can publish $z=H\left(x\right)$ without compromising its secrecy—and then later prove to Bob she’s Alice by exhibiting $x$ (Bob can hash it and check). Of course, this only works once, but schemes exist where Alice can extend the lifetime by publishing a cascaded value like $H\left(H\right(H\left(H\right(x\left)\right)\left)\right)$ and unraveling it one step at a time.

Hashing can also be used to tie values together. If block $B_2$ contains a hash of block $B_1$, then changing something in $B_1$ invalidates the hash in $B_2$. This dependency can extend to a chain: if we have a sequence $B_1,B_2,...,B_N$ with each $B_{k+1}$ containing $H\left(B_k\right)$, then someone examining $B_N$ can tell whether any previous $B_i$ has been altered (see Figure 5-1).

Figure 5-1. If we have a chain of data blocks, having the hash of each block depend on the previous hash means someone examining $B_N$ can tell whether any previous $B_i$ has been altered.

We can also tie this dependence in with the “hard to invert, even with hint” property described earlier. For example, if we have four (digital) documents $D_0,...,D_3$, we can organize them into a binary Merkle tree, walk the tree from the bottom to the top, and label each node with a hash of its children (as Figure 5-2 (A) shows). If we then publish the root in the New York Times, we can prove that any of these documents existed before that publication by (as Figure 5-2 (B) shows) exhibiting the right sequence of hints that show how that document contributed to the published root. In fact, Stuart Haber and colleagues created a company that did just this—and for good measure, had each published root depend on the previously published root, to make it that much harder to forge history.

Figure 5-2. (A) A Merkle tree puts the hashes of $2^k$ documents as leaves in a binary tree and labels each non-leaf with a hash of the concatenation of its children. (B) The owner of a document can prove it contributed to the root by exhibiting the correct sibling hashes.

In its general presentation, hashing is a public operation: anyone can perform $H$. A variation is a keyed hash, where the hash operation requires a secret key. The accepted standard here is HMAC: a way of building a keyed message authentication code function from a public hash function.

The Price Tag

Public key cryptography sounds much more attractive than symmetric key, because it eliminates the hassles and restrictions of all these shared secrets. But these benefits come with a price: it’s significantly more computationally intensive than either symmetric key cryptography or hashing. For tiny devices and for devices communicating over constrained channels, these costs can be problematic—and the IoT will have plenty of both. (The use of newer public key schemes such as elliptic curve cryptography reduces but does not eliminate this problem.)

It’s worth pointing out that, as a consequence of these engineering constraints, many computing infrastructures use symmetric key cryptography. Historically, automatic teller machines (ATMs) used a scheme based on symmetric keys to validate customer transaction requests, although that is being supplanted by public key schemes. Cellphone authentication essentially works by having each device share a symmetric key with a master server associated with the service provider, and then having provider-to-provider bridging arrangements. However, again, as telephony merges with the internet and the World Wide Web, we’re seeing more adaption of public key techniques.

Macaroons

One such tool is the macaroon, from Google (e.g., [3]).

Suppose we have a sequence of IoT computing machines $C_0,C_1,C_2$ where order corresponds with size and authority. For example, $C_0$ might be a big server at a local electric power utility, $C_1$ a smart meter that utility installed at a consumer’s house, and $C_2$ a smart appliance that consumer buys—an appliance that offers some useful features with regard to power consumption. In a natural authority flow, the utility blesses the smart meter and the smart meter blesses the appliance. In this scenario, it might be useful for the utility server $C_0$ and appliance $C_2$ to be able to establish mutually authenticated communications: for instance, so the appliance can report usage information to the server, and the server can ask the appliance to use less power when the grid is under stress. However, this can be tricky if the utility and the appliance have never met.

PKI provides a natural solution to this problem. Each party has a keypair. $C_0$ signs an assertion about $C_1$, and then $C_1$ signs one about $C_2$. The pair of assertions could then suffice to tell $C_0$ that the holder of the $C_2$ keypair is in fact that appliance at that house; standard PK techniques would then allow $C_0$ and $C_2$ to set up a secure, mutually authenticated communication channel.

However, as noted earlier, public key cryptography is expensive. The idea of macaroons is to use the more lightweight HMAC to achieve similar functionality.

Figure 5-3 (A) shows the basic construction of a macaroon. Computer $C_0$ has a secret $k_0$. It generates a random nonce $n_1$ and appends some information (caveats); it uses $k_0$ to then generate the HMAC $k_1$ of these items. We now have the public macaroon (consisting of the nonce and the caveats) and the private $k_2$. If $C_0$ then passes the macaroon and $k_1$ (over a secure channel) to machine $C_1$, then $C_1$ shares a secret with $C_0$. So later, $C_1$ can interact over an open channel with $C_0$, announce its macaroon, and then they both can use the shared secret $k_2$ to set up a mutually authenticated channel.

So far, this doesn’t buy us much; $C_0$ could do the same thing by storing a huge database of pairs of macaroon text and corresponding key. But we can start to see the power when we start chaining macaroons together. For example, consider the scenario in Figure 5-3 (C). After $C_1$ receives its macaroon and key $k_1$, it can use these items to generate a second macaroon and key $k_2$, and implant these in computer $C_2$. Now $C_2$ can mutually authenticate with $C_0$—even though $C_0$ may never have heard of $C_2$ before—simply by presenting its macaroon, which can be thought of as a publicly readable ticket that enables $C_0$ to derive the shared secret $k_2$.

As Figure 5-3 (B) shows, the public macaroon corresponds roughly to a PKI certificate, saying that according to the creator of the macaroon, the party knowing the matching secret key has the properties specified in the caveats. As Figure 5-3 (D) shows, macaroon chaining is similar to certificate chaining. The downsides are that macaroons cannot be verified by the general public, but only by parties higher up in the macaroon chain (who know or can derive the generating secret), and that they don’t have the asymmetry and nonrepudiation of keypairs: anyone higher in the chain can also do things with a party’s secret key. However, the upside is that instead of having expensive operations such as RSA’s modular exponentiation on massive integers, we have lightweight hashing and symmetric cryptography.

Figure 5-3. (A) With macaroons, an entity exhibits a macaroon to prove its identity and uses this shared secret to authenticate itself to a relying party knowing the trust root’s secret key. (B) With PKI, an entity exhibits a certificate to prove its identity and uses its private key to authenticate itself to any relying party knowing the trust root’s public key. (C,D) Both approaches can be chained.

Blockchains

Blockchains are another tool currently receiving much attention for many applications, including the IoT.

Blockchains burst into public awareness with the emergence of Bitcoin, a set of protocols and related infrastructure for cryptocurrency. The idea of cryptocurrency is to use the magic of cryptography and such to mint “coins” that are just strings of bits, but which have the properties of cash: that is, a coin can only be spent once. Cryptocurrency schemes usually have a strong antiauthoritarian bent, and so value decentralization. The Bitcoin protocol, published in 2008 by the probably pseudonymous Satoshi Nakamato [12], addresses this double-spending problem by using hash chaining (and some other tricks) across a decentralized peer-to-peer network to build a hard-to-forge immutable record of transactions—so if someone tries to cheat by spending money he or she has already spent, the entire network can testify.

The basic idea is to represent each transaction as a data block. The blocks are chained together in a master sequence. Each block in this chain contains a hash of the previous block (Nakamato cites Haber’s timestamping work) so that modifying history would require rewriting all the blocks following the modification. The chain is shared universally among nodes in a peer-to-peer network, who use techniques such as “go with the longest chain” to establish consensus in case of disagreement. To keep a malicious party from appending a long stream of blocks to the chain in order to suppress a legitimate transaction an honest party is trying to add (since the malicious extension would then be the “longest chain”), the system uses a proof-of-work mechanism to limit the rate at which blocks can be created. Each block needs to contain a special value $x$ whose hash value begins with a specific number of zero bits (and this number differs and increases for each block in the chain). By the impossibility assumptions underlying hashing, the only way for the would-be constructor of a block to find such an $x$ is to expend computing power doing brute-force searching.

The term “blockchain” has come to denote this general idea of using a distributed network to maintain a hashed chain of blocks whose creation is rate-limited. Its value for cryptocurrencies (and other applications) is that it provides a decentralized, immutable ledger of a transaction stream:

• All nodes agree on the current history of valid transactions.

• All nodes can then witness that a new transaction is valid before appending it to the history.

We can look at currency transactions as transitions in a state machine:

• At any given point, the state of the system is who has how much currency.

• A transaction is valid for a given state when the state satisfies its precondition: the spender actually has the money he or she is spending in the transaction.

• Accepting the transaction as valid thus changes the state: money has shifted.

This view—transactions with preconditions modifying state—can quickly generalize to any kind of computation, and blockchain projects have done this. Transactions can be written as smart contracts or chaincode, firing automatically when their preconditions are satisfied. The Ethereum blockchain project even adds a Turing-complete programming language to its transaction model. Other blockchain extensions include adding permissions/access control to blocks and their fields, although (at first glance) this would seem to reduce effectiveness by reducing the population of witnesses and verifiers. Many players—including large corporations and the Linux Foundation—are now exploring blockchains for applications other than cryptocurrency.

As the start of this section mentioned, one such application is the IoT. The motivation is that blockchains in the IoT may hit several “sweet spots”:

• Projections of exponentially growing numbers of things suggest that the backend server and communication channels between the things and the backend may become bottlenecks. Replacing the centralized backend with a decentralized ledger eliminates this problem.

• The IoT things themselves are already a distributed population, interacting.

• The IoT may involve so many players—consumers, vendors, service providers, utilities, retail stores, etc.—that relying on any kind of centralized authority may be impractical.

At CES 2015, IBM and Samsung even demonstrated using the Ethereum blockchain and smart contracts to enable an IoT-aware washing machine to order detergent when necessary, to negotiate sharing power usage with the household TV, and to arrange warranty service. IBM touts this approach to the IoT of autonomous peers as “device democracy.”

As happens with any hot, potentially disruptive technology, blockchains (in the IoT or elsewhere) are currently going through a bit of churn. Some enthusiasts insist that permissioned blockchains don’t really count as blockchains. In the cryptocurrency world, the Mt. Gox bitcoin exchange collapsed in 2014 (with close to half a billion dollars missing, perhaps gone to hackers); in June 2016 the Ethereum-based DAO lost about $60 million, apparently to hackers, and in August the Bitfinex exchange suffered a high-profile attack. Stay tuned.

PUFs

Having devices use cryptography with secret or private keys requires that devices keep their keys secret—since if an adversary learns a device’s special key, then the adversary can start impersonating the device. Historically, protecting secrets inside computational devices has been a cat-and-mouse game, with each side—attacker and defender—successively coming up with innovations; see my survey article [17] for more information.

Simply by vastly increasing the number of computation devices, the IoT risks making this problem hard. That the computational part of IoT devices may need to be inexpensive will make it harder still. As a consequence, some researchers are considering using physically unclonable functions (PUFs) to help address this problem in the IoT.

PUFs emerged from Srini Devadas’s lab at MIT in 2002 [6]. The basic idea is to “magically” embed a nonpredictable number in a computational device, such that the device can make computational use of this number, but an adversary who tries to access the number in some other way (e.g., by prying off the lid and probing) will not be able to read it. The number is accessible only when it is being used in the circuit itself—it’s a physical artifact of the circuit in operation.

This number and the computations a device does with it can thus be used as a foundation for cryptographic identification and other operations.

Of course, PUFs are not really made by magic. Rather, the technology depends on subtle physical and electrical properties and manufacturing variations—which is how they aspire to resist the standard FIPS 140 attack of “opening up and looking, and building a clone.” The adversary might look but not see; the adversary might know but cannot clone. At least, that’s the design. As someone who worked on the first full top-level FIPS 140–validated device, I can also testify to another potential advantage of PUFs for the IoT: straight-on tamper resistance/detection/response is expensive and tricky, and perhaps not economical for devices that need to be cheap and live in environments more extreme than machine rooms in data centers. PUFs may overcome these limitations.

They have potential, but whether PUFs will stand the test of time as a robust but inexpensive way to hide secrets remains to be seen.

Addresses and Names

“Connection to Other Computers” discussed how networking protocols such as IPv6 can give us the ability to give each IoT thing a unique address and (if everyone behaves) send data there. However, this doesn’t itself solve the identity problem.

What does the name mean? An IP address itself doesn’t carry much semantic information; that’s why people use hostnames such as “www.cs.dartmouth.edu” rather than IPv4 addresses like “129.170.213.101”—and even then, the semantics in the hostname (e.g., the web server of the “CS” part of “dartmouth,” which is some kind of educational institution) follow from convention, and are often misinterpreted by humans. This mapping is determined by the Domain Name System (DNS), and securing the DNS is a continuing challenge. DNS Security Extensions (DNSSEC) is one ongoing attempt to build a giant PKI to make sure the mapping is authentic.

How do we actually route data to a particular thing? The legacy IoT uses the Border Gateway Protocol (BGP) to figure out how to get data to the right IP address—but BGP is widely lamented for being built on the assumption that the big nodes in the internet actually tell the truth when they share routing information with one another. As a consequence, malevolent actors can trick parts of the internet into sending data to the wrong places. Addressing the problem of routing security is another area of ongoing research.

Ontologies of Association

In the IoT, what does a thing need to know about another thing?

• What attributes do listeners need to know?

• Who is in a position to witness to these attributes? (When does it become my washing machine?)

• When will the binding change? (What if I sell the car or move out of the apartment?)

Traditional cryptographic approaches to identity and authentication focus on binding a secret key or public/private keypair to the keyholder’s identity, which is implicitly assumed to be a well-defined, relatively static thing—such as, in PKI, an individual’s full name or email address, or the hostname of a public web server.

However, in the envisioned IoT, the relevant properties of the keyholder are not just the device’s identity (“this is a meter made by ACME”; “this is a refrigerator made by GE”) but its context (“this is a refrigerator in the apartment rented by Alice, who buys power from X”). This context information will not necessarily be known until device installation, and it may change dynamically. (What if Alice sells her fridge on Craigslist or sublets her apartment to Bob? What if repair person Cathy replaces Alice’s meter?). This information may also not be particularly simple. (What if Alice’s landlord owns many apartment buildings, and changes power vendors to get a better rate?)

If a cryptographic infrastructure is going to enable relying parties to make the right judgments about these smart devices, this additional information needs to be somehow available. We can try to modify a traditional identity-based PKI to attest to these more dynamic kinds of identities, or we could try instead to adapt the largely experimental world of attribute certificates (e.g., [4]) to supplement the identity certificates in the IoT PKI. Or we might go with the more lightweight but more constrained macaroons. Any of these approaches breaks new ground. Alternatively, we can leave the identity PKI in place and use some other method of maintaining and distributing this additional data; this requires supplementing our scalable PKI with a nonscalable database.

In any of these approaches, we also need to think about who is authorized to make these dynamic updates. Who witnesses that Alice has sold her refrigerator? Thinking about this organizational structure of smart grid devices also complicates the revocation problem. If we can’t quite figure out who it is that speaks for where a device currently lives, how will we figure out who it is who is authorized to say it has been compromised?

Ontologies of Interaction

In the previous section we considered the granting of names. Another angle is to consider how names must be used. Which thing needs to talk to which other thing, and how often? How broad or narrow are the patterns of communication that need to carry this naming and attribute data? Every traffic light in the US does not need to talk with my washing machine—but they might need to talk with my car.

The standard argument that public key technology makes it easier to have large populations talk to one another starts losing impact if we don’t need to solve that fully general problem. For example, in the power grid, name management (and the corresponding management of keys for identity and authentication) is much simpler for legacy high-voltage transmission lines—since they don’t change endpoints every often—than for future electric cars which may charge as they drive. If we have an IoT structure where smart things in a household talk to one another but must go through a proxy before leaving the house, then it might be feasible just to have the proxies visible.

Indeed, this problem space has many dimensions:

• What needs to be known about an IoT thing

• Who is in a position to testify to this name or attribute

• Who needs to know this information

PKI and Large Populations

As this chapter has noted, public key technology may seem like a natural solution to this large-scale IoT problem. However, it comes with engineering challenges. We’ll start with some of the issues relevant to PKI for any large-scale population—and the IoT, with billions of entities, is likely to be larger than any computing population we have tried so far.

Constrained Devices and Channels

Cryptographic computation can be expensive, in terms of both time and space. For example, calculating an RSA digital signature may require raising a 2,048-bit integer to the power of another 2,048-bit integer—intensive for a CPU whose native word size may be only 32 bits. And if the item being signed is only a few bytes, an RSA signature that may take 2,048 bits of storage represents a rather large overhead (although newer elliptic curve techniques can reduce this overhead somewhat). The computation costs arise when we think about devices; the data size costs arise when we think about device memory and communication channels, where slow channels may turn data cost into additional time cost.

These costs have already proven problematic in the incipient IoT. Embedded systems often use previous-generation processors, and avoid expensive cryptography as a result. Devices with limited electric power also need to consider computational cost: for example, it has been observed that the “obvious” solution to securing the wireless interface on an embedded cardiac device—adding strong cryptographic authentication—enables a new way of killing the patient, by repeated attempting cryptographically flawed authentication and draining the battery.

The current power grid still makes extensive use of slow serial networks, where the additional time necessary to collect the bits for a digital signature on a control message—even before verification—delays the message unacceptably. In my own lab’s prior work on BGP, which controls the routing behavior of the IoC, we found that adding standard cryptographic authentication (and many variations) killed performance, both in terms of the time it takes for the system to reachieve stability after a significant routing change and in message and caching costs (e.g., [21]).

If we project to the envisioned IoT, it’s natural to expect more of these constrained devices and channels, and the concomitant engineering challenges for cryptography. One response to these constraints is to focus on more lightweight schemes, such as Google’s macaroons (as already mentioned) or the Simon and Speck symmetric ciphers, designed by researchers at the NSA and tuned for limited-power devices [2]. Over the last 15 years, there has also been a lot of attention paid to elliptic curve cryptography (as noted previously), a branch of public key cryptography that get can get more security with smaller keys and signatures and such.

Another response is to offload complex cryptographic work from the IoT device itself to an avatar somewhere in the cloud. The device then merely needs to maintain a secure connection to its avatar, which does all the heavy lifting. Zebra Technologies explicitly uses the “avatar” term in this context, although it’s essentially the approach taken by other early IoT deployments, such as NEST.

Privacy Side Effects

A cryptographic protocol to do something like prove identity is usually intended to do just that—at the end of the dance between Bob and Alice, Bob has some kind of evidence that the party at the other end is Alice. However, in straightforward implementations, Bob may learn a whole lot more. For example, if Alice is using standard X.509 PKI, then Bob learns everything in her certificate, as well as who issued it, and what the issuer’s certificate looks like, and so on up the trust chain. The trust path supporting the certificate of a smart appliance $X$ may betray the path of ownership, landlord, and subletting; the revocation or directory queries a substation server $S$ receives from neighborhood consumer devices can betray their activity.

To use a current real-world example, suppose all cash transactions were suddenly replaced with credit cards. Purchasing a book with physical cash suffices for the buyer Alice to authenticate to the seller Bob that she has sufficient funds; but if Alice uses a credit card, then a far more extensive data trail emerges. If this larger data spill is a concern, cryptographic means exist (at least in the research world) to limit Bob from learning extra information about Alice—and even from learning anything except that she is authorized. However, this dimension of lost anonymity needs to be considered and addressed before the IoT is built, not afterward.

Cryptographic Decay

The mechanisms for identification and authentication in the IoT will likely depend on cryptographic techniques, as they did in the IoC. At this book has repeated, the IoT will differ from the IoC in many aspects, including these two:

Lifetime

IoT things, such as household appliances or sensors embedded in urban infrastructure, will likely live much longer than traditional IoC computers.

Patching

IoT things may be much harder to reach with software updates—and the vendors responsible for developing and pushing those updates may no longer exist.

As a result, the software an IoT thing has when it ships may be the software it has for decades. This means the cryptographic algorithms and their relevant parameters (such as key length) could remained fixed for decades.

This is of concern for several reasons. To begin with, as this chapter noted earlier, practical cryptography usually has unsatisfyingly soft impossibility thresholds. To discover a private or secret key, brute-force searches are always potentially possible, and in the best case for defenders, they are limited only by the current level of computational power—which historically tends to increase exponentially. For example, if an adversary can factor the public modulus for an RSA keypair, he or she can quickly calculate the private key. RSA modulus lengths of 1,024 to 2,048 bits are considered secure today, but are projected to be breakable by 2030. Should devices that ship today become by default insecure by 2030?

Cryptographic analysts try to make well-founded predictions today about key length lifetime, but it’s important to note that, historically, the field has often overestimated security against brute-force. For example, the original RSA paper proposed modulus lengths of less than 700 bits—something considered completely insecure now.

Of even more concern than the gradual decay from Moore’s Law is the potential of sudden decay due to new insights into algorithms or computation. Looking forward, it has already been shown that if quantum computers (see, section 8.5 in my security textbook [15]). can be built, then factoring large numbers will become efficient. A sudden breakthrough in this engineering problem will break the cryptography baked into the IoT—and even without quantum, the possibility still exists that a clever theoretician somewhere will show that factoring is efficient even on traditional computers.

Looking backward, we see that sudden breaks like this have already happened:

• In a few short years after the turn of the century, the MD5 hash algorithm went from being considered probably secure, to having semantically meaningless collisions creatable with prohibitively large amounts of computing power, to having semantically meaningful collisions creatable in negligible time on a laptop.

• In the same period, the ISO9796-1 algorithm used to extend hash values to full modulus length went from being a best practice for secure digital signatures to completely breakable.

Of course, this discussion does not even into take into account the fact that IoT cryptography, like any other software, may suffer from bugs. IoC cryptography has already seen fatal implementation blunders, such as predictable numbers being used for critical values such as keys, or private keys being discoverable from observables such as computation time—and embedded system cryptography has already been shown vulnerable to attacks via power measurement or carefully chosen interruption of power.

In a nutshell, expecting IoT devices to remain secure if they remain baked in with cryptography considered secure at shipping time does not bode well. Potential countermeasures include ensuring that all devices can be patched quickly, or can easily die if they persist beyond their secure lifetime, or can be shipped with aggressively future-proof cryptography. Again, challenges remain.