Cryptography: What is it? Why is it important?
(2000)

This note addresses two major questions “What is cryptography?” and, in particular, “Why is cryptography important”?

Cryptography has moved to the centre of information security due to a convergence of major changes.

Until relatively recently, cryptography was used mainly for the protection of military and intelligence information, but this monopoly was broken as corporations, universities and individuals began to market cryptographic products in the mid-1970s.

The growth of information technology, the discovery of easily penetrated system vulnerabilities, inadequacies in “traditional” information security approaches (such as passwords), and the expansion of electronic commerce, especially over the Web, have taken cryptography beyond its earlier classified communication role.

Cryptography – from the Greek hidden writing – is the discipline of creating and using cryptosystems, methods of scrambling messages so that only certain people can unscramble the message.

Cryptanalysis is the art of breaking cryptosystems.

Cryptology is the study of both cryptography and cryptanalysis.

The original message is called a plaintext (or a cleartext) and the scrambled message is called a ciphertext. The procedure to convert plaintext into ciphertext is encryption; the reverse, decryption.

A cipher is a particular method of encryption.

The first known use of a modern cipher was by Julius Caesar (100 – 44 BCE), who did not trust his messengers when communicating with his governors and officers. For this reason he created a system in which each letter in his messages was replaced by a letter three positions later in the alphabet. For example, the message ALEA IACTA EST might have been encrypted as DOHD MDFYD HXY (the classical Latin alphabet had no j, u, or w!).

Some ciphers work by simply manipulating the plaintext in some consistent pattern. However, almost all serious ciphers use both a key (a variable that is combined in some way with the plaintext) and an algorithm (a mathematical formula for combining the key with the text).

The strength of a cipher depends on the algorithm and on the key length.

A strong algorithm is one that resists cryptanalysis. In some cases, it is possible to prove mathematically that an algorithm is strong; often, however, it is simply demonstrated by continued resistance to expert cryptanalysis.

For a given algorithm, the longer the key, the stronger the cipher. An 8-bit key, for example, would allow only 256 values, making it quite feasible to try all possible values in a brute-force attack. Advances in technology and computing performance will always make exhaustive key search an increasingly practical attack against keys of a fixed length. Today, even a 64-bit key (nearly 20 million million million values) is vulnerable; an 80-bit key (more than one million million million million values) should offer an acceptable level of security for another 10 or 15 years

There are two basic types of cryptography: secret-key cryptography and public-key cryptography.

In secret-key cryptography, a single key is used for both encryption and decryption. This approach is also called symmetric cryptography and sometimes private-key cryptography (but this is misleading, as the key is not strictly private but shared – securely! – by a number of parties).

The most popular secret-key cryptosystem in use today is DES, the Data Encryption Standard. However, DES is now vulnerable (it uses only 56-bit keys); other ciphers, including triple-DES and Blowfish, are increasingly used.

The main problem with secret-key cryptosystems is getting the sender and recipient(s) to agree on the secret key without anyone else finding out. This requires a method by which the parties can communicate without fear of eavesdropping: to establish a secure channel one uses cryptography, but secret-key cryptography requires a secure channel! This Catch-22 is known as the key-distribution problem.

In public-key cryptography, each party has a public key and a private key. The public key is published, the private key remains strictly private. Anyone can encrypt a message using the public key, but the message can be decrypted only with the private key that is in the sole possession of the intended recipient.

The RSA public-key algorithm is arguably the most popular. (RSA stands for Rivest, Shamir, and Adleman, the inventors of the cryptosystem.) Philip Zimmermann’s PGP is a popular software package that makes use of public-key cryptography for e-mail.

A user’s private key is mathematically related to their public key. To defy cryptanalysis, determining the private key from the public key needs to be “as hard as possible”. This, in part, leads to longer key lengths than in comparably strong secret-key cryptography. Hence, the major disadvantage of public-key encryption is that it is significantly slower than secret-key encryption.

However, public-key cryptosystems solve the key-distribution problem. The need for the sender and recipient(s) to share secret information is eliminated: all communications involve only public keys, and no private key is ever transmitted or shared.

The only requirement is that public keys can be reliably associated with their users – for instance, in a trusted directory. In fact, this is a non-trivial requirement!

The protocols, services, and standards supporting public-key cryptography form a public-key infrastructure, or PKI. Among the services likely to be found in a PKI are:

• Key registration: issuing a digital certificate, a document binding a public key to an individual or other entity.
• Certificate revocation: cancelling a previously issued certificate.
• Key selection: retrieving an individual’s public key.
• Trust evaluation: determining whether a certificate is valid and what operations it authorises.

There is no single pervasive PKI today. It seems likely that multiple independent PKIs will evolve with varying degrees of coexistence and interoperability: certificate formats and trust mechanisms are generally defined in an open and scalable manner. In particular, most PKI definitions are based on standard ITU-T X.509 certificates; the Internet Engineering Task Force’s SPKI (Simple PKI) is a notable exception.

The importance of cryptography becomes clear when we look at the ways cryptography can be applied. Applications make use of either secret-key or public-key cryptography, or a combination of both, to achieve the following objectives:

• Confidentiality – ensuring secure data storage and transmission.
• Integrity – tamper-proofing data.
• Authentication – confirming the identity of involved parties or the origin or destination of a message.
• Non-repudiation – ensuring that the originator of a message (e.g., an order for goods) cannot at a later time deny that they originated the message.

Secure data storage is the most straightforward use of cryptography. Entire files or discrete records or data items can be encrypted to keep data confidential, especially where others can legitimately have access to that file outside the cryptosystem. Secret-key encryption is usually most appropriate for this application.

For example, in RACF, IBM’s access control facility for OS/390 mainframes, users’ passwords are held on the RACF database in a DES-encrypted form. (Actually, it is the users’ IDs that are encrypted using the password as part of the cipher: this hardens the passwords against cryptanalysis.) Security administrators may be able to read the RACF database – in fact this is a requirement with some administrative tools – but can’t discover the users’ passwords.

Secure communication (data transmission) is also straightforward. Two (or more) parties can communicate securely by encrypting the messages sent between them. This application has existed for millennia, but, until the advent of public-key cryptography, the key-distribution problem had prevented it from becoming commonplace. In fact, the best solution is to combine public-key and secret-key systems in order to get the security advantages of the one and the speed advantages of the other: such a protocol is called a digital envelope.

A digital envelope typically consists of a message encrypted using secret-key cryptography and a random secret key – the message-encryption key or session key – encrypted using public-key cryptography (although secret-key cryptography could be used here too!). For example, if Alex wants to send a confidential message to Ben, he encrypts the message with the session key, then encrypts this key with Ben’s public key, and sends both ciphertexts to Ben. Ben then uses his private key to decrypt the session key, then uses that key to decrypt the message. This protocol has particular advantages where there are multiple recipients: if Alex wants to send the message to Chris as well, the only other thing he needs to do is to encrypt the message-encryption key with Chris’s public key – the message itself is encrypted only once.

A special instance of secure communication is in e-commerce. To let people bank, trade, and make credit-card purchases online, without worrying that any of their account information is being compromised, all of the data being transmitted between the business’s server and the customer’s Web browser is encrypted.

The integrity of a message can be ensured using a message authentication code (or MAC), a tag or checksum derived by applying an authentication scheme, together with a secret key, to a message. One MAC scheme uses a hash function, a transformation that takes a message of arbitrary length and creates a fixed-length hash value, called the message digest, a “digital fingerprint” of the message.

(A hash function must be one way – i.e., the message can’t be recovered from the hash value – and collision free – i.e., any two different messages should generate different hash values.)

If the recipient of the message can generate the same checksum (using the same secret key and hash function as the sender), then the message is “authentic”; if not, then either the message has been tampered with, or there was an error in transmission.

Digital signatures are a widely used application of public-key cryptography. Naïvely, a sender can “sign” a message by encrypting some simple text (e.g., an e-mail “.sig”) with their private key, so that the recipient can decrypt it sensibly with their public key. However, as a way of authenticating the sender, this is seriously flawed: the signature ciphertext would be fixed, and could be simply copied by someone else wanting to impersonate the original sender!

Typically, a secure digital signature is created by encrypting a message digest, unique (or practically so!) for each message, with the sender’s private key.

A recipient authenticates the signature by applying the same hash function to the message, decrypting the signature using the sender’s public key, and comparing the two values. If these are the same, the signature is authentic; if not, then either someone is impersonating the sender, the message itself has been modified, or an error occurred during transmission. (In some schemes, the recipient uses a verification function to match the digest to the message, rather than reapplying the hash function.)

Note that, by using a message digest, a digital signature not only authenticates the sender of the message, but also checks its integrity of the message, much like a MAC.

In addition, digital signatures provide non-repudiation: as the sender is in sole possession of their private key, only they can generate a digital signature that can be verified using their public key. Hence, they cannot at a later time deny that they sent the message. This is of considerable importance in e-commerce; e.g., ensuring that a customer cannot repudiate an order for goods or services.

Central to all public-key cryptography is a public-key infrastructure (PKI) in which public-keys are “bound” to individuals via digital certificates.

In their simplest form, a certificate contains a public key and a name. As commonly used, a certificate also contains an expiration date, the name of the certification authority (CA) that issued the certificate, a serial number, and perhaps other information. Most importantly, the certificate is digitally signed by the CA.

A CA can be any trusted central administration willing to vouch for the identities of those to whom it issues certificates.

The most secure use of authentication involves associating one or more certificates with every signed message. The receiver of the message verifies the certificate using the CA’s public key and, now confident of the public key of the sender, verifies the message’s signature. There may be two or more certificates enclosed with the message, forming a hierarchical certificate chain, wherein one certificate testifies to the authenticity of the previous certificate. The public-key of any top-level CA must be independently known, for example, by being widely published.

Another trust mechanism relies on users to distribute and track each other’s keys and trust in an informal distributed fashion, a “peer-to-peer” rather than hierarchical PKI. This has been popularised as a viable alternative by PGP, which calls the model the web of trust.

Because cryptography is such a good hammer, people are looking for ways to turn their problems into nails. It is tempting to rely on sexy, leading-edge cryptographic techniques alone to solve information security problems.

No-one can guarantee 100% security, but it’s hard to build a cryptosystem that provides strong authentication on top of systems that can be penetrated by knowing someone’s mother’s maiden name! Security is a chain, and a single weak link can break the entire system. One ring of art thieves in California defeated home security systems by taking a chain saw to the house walls. Computer thieves come through walls too: practical cryptography is rarely broken through mathematics; other parts of the systems are much easier to break!

Nevertheless, cryptography is a valid – even necessary – approach in many situations, and is of increasing importance. Every day hundreds of thousands of people interact electronically. From email to cellular phones, from secure Web access to digital cash, cryptography helps to provide accountability, fairness, accuracy, and confidentiality. And in the future, as commerce and communications continue to move to computer networks, cryptography will become ever more vital.