5. Introduction to Cryptography¶

This not talks about the idea of cryptography, starting with a brief history, and then talking about some terms that will be used in future notes.

Brief History of Cryptography¶

Cryptography comes from Latin roots crypt, and graphia, meaning secret writing. Schemes for sending secret messages go back to antiquity. Caesar created the "Caesar cypher," which consists of permuting the alphabet by some fixed amount.

The second phase of cryptography, the "mechanical era," found cryptographers using mechanical devices to encode and decode messages. The German project "Enigma" found a way to encrypt a message that seemed unbreakable. However, the British did find a way to break the Enigma code, which probably shorted the war by about a year.

Modern cryptography is distringuished by its reliance on mathematics and electronic computers. Its early roots are found in the work of Claude Shannon following WW2. 1970s saw the introduction of a standardized cryptosystem, DES, by the National Insitute for Standards in Technology (NIST). DES answered the growing need for digital encryption standards in banking and other businesses. After the 1970s, we saw an explosion of work on a computational theory of cryptography.

Definitions¶

Alice, Bob, Eve, and Mallory¶

Alice and Bob wish to communicate securely as though they were in the same room or were provided with a dedicated, untappable line. However, they are subject to tapping by an eavesdropping adversary, Eve. Sometimes, Eve might be replaced with Mallory, who can tamper with communications in addition to eavesdropping on them.

Our goal will be designing a scheme to scramble messages between Alice and Bob such that Eve has no clue about the contents of their exchange, and Mallory is unable to tamper with the contnts of their exchange without being detected.

Keys¶

A key is the most basic building block of any cryptographic system. The key is a secret value that helps us secure messages. There are two main key models in modern cryptogrpahy 1. Symmetric key model: Alice and Bob both know the value of a secret key, and must secure their communications using this shared secret value 2. Asymmetric key model: each person has a secret key and a corresponding public key.

Confidentiality, Integrity, Authenticity¶

Confidentiality is the property that prevents adversaries from reading our private data. If a message is confidential, then an attacker does not know its contents.

Many cryptographic algorithms that guarantee confidentiality work as follows:

• Alice uses a key to encrypt a message by changing it into a scrambled form that the attacker cannot read. She then sends this encrypted message over the insecure channel to Bob

• When Bob receives the encrypted message, he uses the key to decrpt the message by changing it back to its original form

• Call the message "plaintext" when it is unencrypted and "ciphertext" when it is encrypted.

• Even if the atttacker can see the encrypted ciphertext, they should not be able to decrypt it back into the corresponding plaintext

Integrity is the property that prevents adversaries from tampering with our private data. If a message has integrity, then an attacker cannot chang its contents without being detected.

Authenticity is the property that lets us determine who created a given message. If a message has authenticity, then we can be sure that the message was written by the person who claims to have written it.

Most cryptographic algorithms that guarantee integrity and authenticity work as follows:

• Alice generates a tag or signature on a message. She then sends it to Bob

• When Bob receives the message and the tag, he verifies that the tag is valid for th e message that was sent.

• If the message was modified by an attacker, the tag should no longer be valid, and Bob's verification will fail.

• This lets Bob detect altered messages. The attacker should not be able to generate valid tags for their malicious messages

Another property is deniability. If Alice and Bob want to communicate securely, Alice might want to publish a message from Bob and show it to a judge, claiming that it came from Bob. If the cryptosystem has deniability, there is no cryptographic proof available to guarantee that Alice's published message came from Bob. For example, consider a case where Alice and Bob use the same key to generate a signature on a message, and Alice publishes a message with a valid signature. Then the judge cannot be sure that the message came from Bob–the signature could have plausibly been created by Alice.

Overview of Schemes¶

Let's look at cryptographic primitives that provide confidentiality, integrity, and authentication in both the symmetric-key and asymmetric-key settings.

1. Symmetric-key encryption: Alice uses her secret key to encrypt a message, Bob uses the same secret key to decrypt the message
2. Public-key encryption: Bob generates a matching public key and private key, and shares the public key with Alice (but does not share the private key with anyone). Alice can encrypt her message under Bob's public key, and then Bob will be able to decrypt using his private key.

In syymmetric key setting, message authentication codes (MACs) provide integrity and authenticity. Alice uses the shared secret key to generate a MAC on her message, and Bob uses the same secret key to verify the MAC.

In asymmetric-key setting, public-key signatures (known as digital signatures) provide integrity and authenticity. Alice generates a matching public and private key, and shares the public key with Bob. Alice computes a digital signature of her message using her private key, and appends the signature to her message. When Bob receives the mssage and its signature, he will be able to use Alice's public key to verify that no one has tampered with or modified the message.

Here are some other primitives. They don't guarantee confidentiality, integrity, or authenticity by themselves, but they have desirable properties that will help s build secure cryptosystems: 3. Cryptographic hashes: provide a one way digest. They enable someone to condense a long message into a short sequence of what appear to be random bits. They are irreversible, so you can't go from the resulting hash back to the original message but you can quickly verify that a message has a given hash 4. Pseudorandom number generator: process which takes a small amount of true randomness and stretches it into a long sequence that should be indistinguishable from actual random data 5. Key exchange schemes: (e.g Diffie-Hellman key exchange) will allow Allice and Bob to use an insecure communication channel to agree on a shared random secret key that is subsequently used for symmetric-key encryption.

Kerckhoff's Principle¶

Cryptosystems should remain secure even when the attacker knows all internal details of the system. The key should be the only thing that must be kept secret, and the system should be designed to make it easy to change keys that are leaked (or suspected to be leaked). If your secrets are leaked, it is usually a lot easier to change the key than to replace every instance of the running software. (This principle is closely related to Shannon’s Maxim: Don’t rely on security through obscurity.) 1. Security Principles.

We will assume that the attacker knows the encryption and decryption algorithms. The only information the attacker is missing is the secret key(s).

Threat Models¶

Here are several possibilites about how much access an eavesdropping attacker Eve has to the insecure channel: 1. Eve has managed to intercept a single encrypted message and wishes to recover the plaintext. This is known as ciphertext-only attack 2. Eve has intercepted an encrypted message and also already has some partial info about the plaintext, which helps with deducing the nature of the encryption. This is known as known plaintext attack 3. Even can capture an encrypted message from Alice and Bob and re-send the encrypted message to Bob again. This is known as a replay attack. “Hey Bob’s Automatic Payment System: pay Eve $100” and sends it repeatedly to Bob so Eve gets paid multiple times. Eve might not know the decryption of the message, but she can still send the encryption repeatedly to carry out the attack. 4. Eve can trick Alice to encrypt arbitrary messages of Eve's choice, for which Even can then observe the resulting ciphertexts. At some other point in time, Alice encrypts a message that is unknown to Eve; Eve intercepts the encryption of Alice's message and aims to recover the message given what Eve has observed about previous encryptions. This is known as chosen-plaintext attack 5. Even can trick Bob into decrypting some ciphertexts. Eve would like to use this to learn the decryption of some othe rciphertext. This is known as chosen-ciphertext attack 6. Even can do a combination of the previous two cases, tricking Alice into encrypting some messages of Eve's choosing, and trick Bob into decrypting ciphertexts of Eve's choosing. This case is known as chosen-plaintext/ciphetext attack, and is the most serious threat model.

Today, we usually insist that our encryption algorithms provide security against chosen-plaintext/ciphertext attacks, both because those attacks are practical in some settings, and because it is in fact feasible to provide good security even against this very powerful attack model.

However, for simplicity, this class will focus primarily on security against chosen-plaintext attacks.