Cryptography grows ever more prominent in our lives. Every time you log into an app or send an email, you are relying on an ingenious cryptographic infrastructure that is descended largely from breakthroughs in the 1970s.
Beyond just specialist software developers, beyond just coders, even the non-programming general public can benefit from understanding how cryptography works, especially in an age of crypto currency and crypto investment.
All of us use cryptography in our daily lives, whether we know it or not.
What is cryptography?
Cryptography is the practice of securing communications. This is achieved using a variety of techniques that boil down to implementing protocols that prevent unwelcome parties from viewing or altering data.
The discipline of cryptography can be described as having four aspects:
- Confidentiality: Data is not exposed to unintended parties.
- Integrity: Data is not manipulated or destroyed.
- Authentication: Parties are able to reliably verify each other’s identity.
- Non-repudiation: Communication can be confirmed, and not later denied by participants.
Symmetric ciphers
Cryptography before the advent of computers relied on the use of ciphers. A cipher is a mapping from readable text to gibberish, and back again. For instance, a simple cipher would be to add four to every letter in the text (so A becomes E). Decoding then would involve simply subtracting four from each letter. These processes are called encryption and decryption.
Shifting four places in the alphabet is very obvious, and not secure. More secure is creating a complex mapping that requires a key for translation. Such a key must be distributed to all participating parties. This necessity implies all sorts of logistical weaknesses.
A famous example of a symmetric cipher is the Enigma machine employed during WWII.
One-way functions
With the advent of computers and attendant advancements in mathematics, the possibilities of encryption grew more complex. Many new techniques arose, but among the most fundamental is what is known as a one-way function (which includes one-way hashes, for generating fixed-length output). One-way functions are considered a cryptographic primitive. Like the name suggests, a one-way function works in only one direction.
A common use for one-way functions, and a good way to understand them, is hashing passwords when they are persisted to the database (for instance, in Java and in JavaScript). The password is taken from plain text (“fluffy123”) and the one-way algorithm turns it into a random-looking string (“XFcbe2d3bh0sa”). Even if an attacker gains access to the database, the passwords are secure. There is no known method (using current computer systems) to efficiently reverse the process.
It’s a curious fact to observe that even though attackers have full access to the logic of the algorithm (for example, here’s the source for BCrypt), they are generally unable to reverse the function. That said, one-way hashing is not perfect and a variety of techniques have been introduced for cracking them (like Rainbow tables).
Modern hashing libraries include the capability to increase the difficulty of the hash (thereby allowing the hash strength to increase as computing power increases) and to introducing “salt” into the algorithm (thereby ensuring that hashes of identical inputs are nevertheless unique). As long as the salt is kept secret, passwords hashed with it are basically uncrackable.
For a succinct understanding of the theory behind one-way hashing, take a look at this Stack Overflow answer.
Pseudo-random functions
Along with one-way functions, algorithms for generating random-like numbers are considered cryptographic “primitives,” i.e., fundamental building blocks necessary for securing communications. Why is that? Simply put, any secret communication system depends on values that are known to the securing party, and unknown to the outside. That depends on generating random numbers. (Often, user supplied input is also incorporated, but humans are notoriously unreliable in providing such input.)
Most types of random seeding (like pulling from the system clock) are only “sort of” random. If a hacker knows how the numbers are generated, they could devise random number attacks. The ingenuity of hackers seems to keep pace with that of white hat coders. Indeed, the story of cryptography is one of back and forth jockeying, a kind of call and response of innovation.
More secure means of generating random numbers have been developed to foil random number attacks. Most crypto libraries include facilities for these generators.
Asymmetric keys
Perhaps the most ingenious and influential development in modern cryptography is the asymmetric key pair, also referred to as public-private key pairs. The basic idea is that two keys are generated, one for encrypting and one for decrypting. The encryption key is safe to distribute, the decryption key is kept private.
This innovation was pioneered in the late 1970s by two programmers and a mathematician, who gave their initials to the groundbreaking crypto system they invented: RSA. (An interesting side note: A similar system was invented several years earlier by a British intelligence mathematician, but the invention was kept secret and the system deemed impractical at the time given the limitations of computer systems.)
RSA and other asymmetric key systems take the idea of the one-way function a big step forward by creating two keys that work in an asymmetric fashion: The first key is used to create encrypted messages (the public key) and the second is used to decrypt them (the private key). See Figure 1.
Figure 1. Public-private keys
IDGThe math behind this trick is not simple. In fact, for a time, the researchers involved held serious doubts as to whether it was even possible in theory. Today public-private key cryptography underlies much of modern internet security infrastructure, including the “transport layer” security used by SSL/TLS, digital signatures, and cryptocurrencies like Bitcoin.
It’s important to note that asymmetric keys do not create impossible-to-crack systems. But so long as the private key is kept private, it is practically impossible to break the encryption. Besides numerous in-the-wild exploits (including random number attacks, timing attacks, and others) that have been brought to light, the security of even the most secure public-private key pair is based on how long it would take to reverse the process of factoring the numbers involved.
This may not seem very secure, but to quote Brett Slatkin’s article on public key crypto math, “even fancy solutions on the fastest computer on Earth would take until the end of the universe” to crack modern asymmetric encryption. Barring the introduction of practical quantum computing, which would make cracking RSA-like encryption a polynomial time solvable problem (not necessarily a distant possibility), modern algorithms are considered viable for practical applications.
In current applications, asymmetric keys are often used as a kind of handshake to establish a secure channel for the exchange of symmetric keys. (This is what is happening when your browser is “negotiating TLS.”) Because symmetric keys are in practice much faster, the server and client verify each other via asymmetric keys, then hand over symmetric keys for use in further communication. This communication is then safe from eavesdropping or manipulation even over non-confidential channels.
Public key infrastructure
Another important caveat to asymmetric cryptography is that it typically requires a trusted, centralized authority. This is because the problem of verifying that someone is who they say they are isn’t limited to just proving that someone holds a private key (something asymmetric encryption can do on its own). Instead, to ensure that (for example) a web server’s SSL/TLS certificate is not only technically valid, but also authentic (truly represents the organization it claims to), a central authority (Google, for example) must be referred to.
This creates more opportunities for hackers, as any breach within the hierarchy of validating keys compromises all the keys below. Although such breaches do happen, much of the internet relies on this system. The system as a whole is known as public key infrastructure (PKI). A trusted party that issues certificates is a certification authority (CA).
An alternative to PKI is pretty good privacy (PGP), wherein users trust each other on a peer-to-peer, distributed basis, instead of relying on a centralized authority (here too asymmetric keys are used to exchange symmetric keys). PGP is commonly used to encrypt email and to verify that downloads have not been tampered with.
The most sophisticated use of asymmetric keys and cryptography in general is found in blockchain systems, exemplified by Bitcoin. By eliminating the need for a centralized authority and moving the validation of cryptographically signed transactions to the network, a blockchain opens up the possibilities for new kinds of systems built on a distributed-yet-secure layer atop the internet infrastructure. We are just now witnessing the teasing out of these possibilities.
Blockchains and the systems built on them are essential cryptographic structures. Key pairs are used to sign transactions, and crypto hashes are used to validate the links in the chain.
This has been a whirlwind tour of the current crypto landscape. Although there is much complexity involved, understanding the lay of the land is increasingly valuable to all of us, programmers and non-programmers alike.