MDJ 2020.02.05

Trust but Verify

Last time (MDJ 2020.02.03), we talked about a misconception of what notarizing Mac software does—it’s for verifying the integrity of software, not exercising control over it—but we didn’t discuss how it works. To get there, we’ve got to go through some building blocks of verification—public-key cryptography, hash functions, and digital signatures. We know some of you already have this internalized, but laying it out really will help. Let’s go!

The building blocks

Cryptography is the science of encoding and decoding information, from the most basic substitution cipher you used as a kid (and as seen in daily cryptogram puzzles) to the Kryptos sculpture outside CIA headquarters and its message that still hasn’t been decoded after 30 years. A message encoded with a key known to both the sender and receiver is safe in transit unless an intercepting party (sometimes called an attacker) either has the key or can derive it by cracking the code.

Online security would be very hard that way—you couldn’t communicate securely with a merchant, for example, unless you and that merchant had already agreed upon a unique, secure cipher and you both had the key. If you think you couldn’t handle having a separate key for every website, imagine being Amazon and trying to have a key for every customer!

We don’t have to do that because of public-key cryptography, a mathematical breakthrough in the 1970s that splits every key into two parts—public and private. Panayotis Vryonis created a very good explanation using a physical lock, but here’s the focal point: the sender and the receiver each have a public and private key (known as a key pair). Anything encoded with one of the keys in the pair is decodable by the other one.

The encryption algorithm is both secure and publicly known, much in the same way that people know how padlocks work but still need the right key to open one. Anyone can use this encryption algorithm to encode a message with the recipient’s public key, but only the recipient with the matching private key can decrypt it successfully. Similarly, anything a sender signs with the private key can be decoded by anyone who has the public key.  That is far from pointless.

Why? Now we can encode data (the more generic form of “message”).  Files, groups of files, all the files—you name it. What if we take an application bundle, compress it into a single file, and encrypt it with our private key? The resulting encrypted pile of bits would not be “secret” in any meaningful way. Anyone who could find our public key, which we presumably made, you know, public, could decrypt and decompress it to get the application bundle back.

But what that would do, in a way, is verify that we are the ones who encrypted the application. Key pairs are generated with huge numbers and random information so they’re unique. (CloudFlare famously uses a wall of 80 lava lamps to generate truly random information.) If our public key decrypts it, then our private key had to be the one that encrypted it. If you are satisfied that our public key belongs to us, then you should be satisfied that data encrypted with our private key came from us.

Hashing it out

Such a method of verification would be wasteful—encryption algorithms are usually a bit computationally intensive, and they often increase the size of the data multiple times over. Instead, why don’t we encrypt a small message that says what the file contains?

Well, how do we do that? One of the earliest ways computer scientists verified data transmission was with a checksum. The first checksums were as simple as making a running total of every byte in the data. The odds that two blobs of data would add up to the same number were remote. Unfortunately, the odds that two bits got corrupted were not that remote. If one bit in the “ones” position was wrongly set to 0 while a different bit in another byte’s “ones” position was incorrectly set to 1, this simple checksum would pass even though there were errors in transmission.

So computer scientists got after this problem! First came the cyclic redundancy check, or CRC, an algorithm that uses exclusive-or operations instead of plain addition to get better validation. CRCs also limit the output to a predetermined number of bits, like 32 for CRC-32.

Great! We can make a CRC of our data, encrypt that, and use it to verify that the application bundle is the same one we—oh, no, we can’t, too many bad things can happen.

  • We know how the CRC algorithm works, so it’s easy (if not trivial) to create a separate application bundle that adds up to the same CRC. That would fool people into thinking we’d verified something we hadn’t.

  • Even if not maliciously built, there are only 4.2 billion possible CRC-32 values, and a lot more than 4.2 billion messages transmitted every day.  Multiple inputs will produce the same output, and that’s bad for the same reasons, even if it’s accidental.

  • It’s even theoretically possible to reconstruct the original data if we know both its size and its CRC, although this gets a lot more difficult when the data gets larger. Still, what good is verification if it can be faked?

What we need is a verification function that eliminates these problems:

  • It needs to turn any set of input, from one bit to all the bytes that exist, into a fixed number of bits (probably more than 32—let’s say 256 for now).  This was already a thing in computer science called a hash function, used in applications like databases to turn big sets of data into easily searched indexes.

  • Hash functions, like the function we need, should output a value (called a hash) that varies widely among inputs—changing one bit in the input should produce an entirely different hash, not a hash that’s one bit different from the original hash.

  • On second thought, that’s not enough. We need a hash function that cannot be inverted. That is, there should be no computationally feasible way to turn a hash back into any source data, even if you know the original size or other structural information about it (like that it’s a Zip archive).

Every single word in the dictionary for every language should ideally produce an entirely different hash when passed through our algorithm. Every misspelling should produce a different hash. Every sentence should produce a different hash to any of the others. There’s likely room for this: the maximum unsigned value you can store in 256 bits is, according to Wolfram|Alpha, 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936, or one value for roughly every 1,200 atoms in the visible universe.

Functions that can do this with broad success already exist. They’re called cryptographic hash functions or cryptographic hashes, and they’re extremely critical to modern computing. We can put our application bundle through a cryptographic hash function and get back a 256-bit value that, in theory, has less than a 1-in-115 quattuorvigintillion chance of matching any other input.  No cryptographic hash function is perfect, so we can’t get perfect distribution like that, but even if it’s half that good, it’s still very, very good.

It’s also why these functions are under constant attack, and successful attacks compromise everyone using a broken one. A long-time secure hashing function, MD-5, was broken in the 1990s and is no longer recommended, although plenty of code still uses it. (The majority of uses for hashes are transient and have no real value weeks later. No attacker wants to know what gift-wrapping options you picked for the moustache wax you stuck in the white elephant gift exchange.) SHA-1 is now broken as well. SHA-256, which we’ve been kind of hinting at here, is still secure but is about 40% as fast as MD-5. The source control system Git uses SHA-1 and is now trying to replace it, but that’s not trivial.

Keys to the Kingdom

OK, great! We have a secure hashing algorithm, so now our path is clear. We create a message listing the contents of our application bundle and a secure hash for each file. We then encrypt that message with our private key, allowing anyone with our public key to decrypt it.  They can fetch the application bundle, calculate the secure hash for every file, and compare it to the encrypted message to make sure everything is fine. In general terms, this defines a digital signature—a message signed with a specific private key containing a secure hash to verify that the contents of the message have not changed since the signature was created.

That’s it! We sign the application bundle and we’re done…provided people know where to find our private key.  In the PGP system, carried forward in GnuPG on macOS, people sign their own keys and each other’s keys, creating a “web of trust.”  If you trust John Doe, you’d sign John Doe’s key and publish it to a key server, a collection of lots of public keys. Anyone who trusts you would then at least partially trust John Doe because you’ve “vouched” for him with your signature.

The rest of the cryptographic world does not work this way, as governments and corporations and people with sticks in unusual places require top-down trust. “You will trust my communications because I am the CEO. I do not care if your cubicle-mate does not trust me; she’s fired. You will trust me or you’re fired.”

This model of trust is implemented through public key infrastructure, usually abbreviated PKI. The basic unit in PKI is not the key, but rather the certificate: a document containing a public key that is signed by a higher authority in your system of trust. An entity that creates, signs, and issue certificates is called a certificate authority, or CA.

Certificates seem complicated but just think of one as a public key signed by a CA. There is usually a lot of other stuff in there—uses for which the certificate is valid, an expiration date, information about the issuer and the requesting party (you, if it’s your certificate), algorithms used, and so forth.  On a Mac, you can launch Keychain Access, pick “System Roots” from the left sidebar, and look at a whole bunch of root certificates.

Those are the top of the trust tree for a CA—the certificate the CA created for itself that signs all certificates that it issues.  Since only the CA signs its own root certificate, you have to decide if you’ll trust it or not. Most modern operating systems, including iOS and macOS, include a wide variety of root certificates so you never have to worry about that in normal use.  Our production system’s keychain has 171 root certificates from companies, including Amazon, Apple, Verisign, GoDaddy, Visa, and more. In theory, if you trust a CA, you trust the certificates it issued and signed—the top-down model.

You can see this at work in Safari when connected to any secure web page. Click on the padlock icon in the URL field and click “Show Certificate.” We tried a simple Google search and found it secured via a certificate for that was signed by “GTS CA 101,” short for “Google Trust Services Certificate Authority.” Google, like Apple, is its own CA and issues its own root certificates with their own subordinate CAs. You can view all of Google’s root certificates here.  GTS CA 101 was, in turn, issued by GlobalSign, an international PKI company whose root certificate is trusted by default in macOS and iOS.

Back to Home

Now you can see the big picture. We have certificates in the keychain, trusted by macOS, containing public keys. Before distributing applications, they get their code signed using keys issued by Apple. The company trusts the corresponding public keys because it issued the certificates.  Your system can then validate the code signature, check the secure hashes, and verify that not one bit of the application has changed since the developer signed it, meaning it has not been compromised on disk. macOS also checks to see if any of the signing certificates were revoked by Apple, a protection of last resort that warns the system something has gone terribly wrong, and that you must not run the application in question.

For “code signed” applications, developers sign their own code with a certificate supplied by Apple for one of a set of specific uses (testing, distribution, and debugging come to mind). For notarized applications, Apple signs the code with its own certificate, sending the results back to the developers who “staple” it to their code. (If they don’t or can’t, the system can look up the results online.)

One method uses a developer-controlled certificate that Apple can revoke; the other uses Apple’s own certificate without developer input. You can see why some developers are nervous about it!  In the final part of this series, we’ll explain why those fears are overblown.

In most cases.