Kostas Kalafatis

Posted on

Introduction To Cryptography

Cryptography is the science of keeping secrets secret. Assume a sender referred to here and in what follows as Alice (as is commonly used) wants to send a message `m` to a receiver referred to as Bob.

She uses an insecure communication channel. For example, the channel could be a computer network
or a telephone line. There is a problem if the message contains confidential information. The message could be intercepted and read by an eavesdropper. Or, even worse, the adversary, might be able to modify the message during transmission in such a way that the legitimate recipient Bob does not detect the manipulation.

To prevent these attacks from the adversary are the goals of cryptography.

The Goals of Cryptography

In essence, cryptography concerns four main goals:

• Confidentiality
• Integrity
• Authentication
• Non-repudiation

Confidentiality

When discussing about a cryptographic system for the purpose of confidentiality, we must think about two different states of data.

Data at rest, or stored data, are the data residing in a permanent location awaiting access. This can include data stored on hard drives, cloud storage devices, USB devices and other storage media.

Data in transit, or data "on the wire", are data being transmitted across a network between two systems. This can include data that travel on a wireless network, a corporate network or the public Internet.

So, confidentiality ensures that data remain private while at rest, and in transit. This is perhaps the most widely cited goal of cryptosystems — the preservation of secrecy for stored information or for communications between individuals and groups.

Integrity

Integrity ensures that data is not altered without authorization. If integrity mechanisms are in place, the recipient of a message can be certain that the message received is identical to the message that was sent. In other words, integrity ensures us that the message we received is identical to the message that was originally sent.

Also, integrity checks ensure that stored data were not altered between the creation time and the access time. These controls protect against all forms of alteration. Both intentional alteration from a malicious third party attempting to manipulate the data, and unintentinal alteration by faults in the transmission process.

Authentication

Authentication verifies the claimed identity of system users. Authentication can be split into two functions, entity authentication and data origin authentication.

Imagine for a moment that we have two people, Alice and Bob that want to communicate.

Entity authentication ensures that both parties should be able to verify each other's identities.
In other words, during the initiation of communication, Alice and Bob can identify each other.

Data origin authentication ensures the receiver of the message should be able to verify the message's origins. In other words, no one can be able to send a message to Bob and pretend to be Alice.

Non-repudiation

Non-repudiation provides assurance to the recipient that the message was originated by the sender and not someone masquerading as the sender. This concept looks similar to authentication but, it serves another purpose.

Once again lets imagine our three parties, Alice, Bob and Charlie. In this scenario, Alice sends a message to Bob, and Bob forwards the message to Charlie.

Authentication ensures Bob that some data received by Alice, really comes from Alice.

Non-repudiation on the other hand ensures that there is some way to not only for Alice to prove to Bob that a message really comes from Alice, but also prove to Charlie that the message forwared to him by Bob is sent by Alice, even if Charlie does not trust Bob.

In other words non-repudiation "ties" a message with the original sender and can be used as proof amongst non trusting parties. A byproduct of this operation is that the original sender of the message, cannot claim that they never sent the message in the first place.

Cryptanalytic Attacks

The primary goal of cryptography is to keep the plaintext secret from eavesdroppers trying to get some information about the plaintext. Also, adversaries may also be active and try to modify the message. Then, cryptography is expected to guarantee the integrity of messages. Adversaries are always assumed to have complete access to the communication channel.

Attacks on the secrecy of an encryption scheme try to recover plaintexts from ciphertexts, or even more drastically, to recover the secret key. The attacks listed here are restricted to passive attacks. The adversary, we will call her Eve, does not try to modify the messages.

She monitors the communication channel and the end points of the channel. So she may not only intercept the ciphertext, but (at least from time to time) she may be able to observe the encryption and decryption of messages. She has no information about the key.

For example, Eve might be the operator of a bank computer. She sees incoming ciphertexts and sometimes also the corresponding plaintexts. Or she observes the outgoing plaintexts and the generated ciphertexts. Perhaps she manages to let encrypt plaintexts or decrypt ciphertexts of her own choice.

The possible attacks depend on the actual resources of the adversary. They are usually classified as follows:

1. Ciphertext-only attack. The adversary has the ability to obtain ciphertexts but has no knowledge about the plaintext content or the encryption key.
2. Known-plaintext attack. The adversary has the ability to obtain plaintext-ciphertext pairs. Using this information from these pairs, the adversary attempts to decrypt a ciphertext for which they do not have the plaintext.
3. Chosen-plaintext attack. The adversary has the ability to obtain ciphertexts for plaintexts of their choosing. Then they attempt to decrypt a ciphertext for which they do not have the plaintext.
4. Adaptively-chosen plaintext attack. This is the same as the previous attack, except know the adversary may do some analysis on the plaintext-ciphertext pairs, and subsequently obtain more pairs.
5. Chosen- and adaptively-chosen ciphertext attack. These two attacks are similar to the above plaintext attacks. The adversary can choose ciphertexts and get the corresponding plaintexts.

Ciphertext-only Attack

This is an attack model for cryptanalysis where the attackser is assumed to have access only to a set of ciphertexts. The attack is successful if the corresponding plaintexts or the key can be deduced.

Early ciphers, such as the rail fence cipher, or the Caesar cipher, can be broken using only the ciphertext and statistical techniques such as frequency analysis.

Mechanical encryption devices such as the Enigma machine made these attacks increasingly difficult.

Modern ciphers can also prove vulnerable to ciphertext-only attacks. The Wired Equivalent Privacy (WEP), the first security protocol for WiFi, proved vulnerable to ciphertext-only attacks.

Known-plaintext Attack

This is an attack model for cryptanalysis where the attacker is assumed to have access to samples of both the plaintext and its ciphertext and is at liberty to make use of them to further reveal information such as keys.

Again, early ciphers are susceptible to this attack. For example, a Caesar cipher can be solved using a single letter of corresponding plaintext and ciphertext to decrypt entirely.

Modern encrypted file archives such as ZIP are prone to known plaintext attacks. An adversary that has both an encrypted zip file and the same unencrypted file, can perform an attack to the Traditional PKWARE Encryption method.

Chosen-plaintext Attack

This is an attack model for cryptanalysis where the attacker is assumed to be capable of choosing arbitrary plaintexts to be encrypted and obtain the corresponding ciphertexts.

Non-randomized public key encryption algorithms are vulnerable to simple dictionary-type attacks, where the attacker builds a table of likely messages and their corresponding ciphertexts. To find the plaintext of some observed ciphertext, the adversary can simply look the ciphertext up in the table.

This is an attack model for cryptanalysis where the attacker is assumed to be capable of asking for the ciphertexts of arbitrary plaintext messages. The attacker's goal is to reveal all or part of the secret encryption key.

In World War II US Navy cryptanalysts discovered that Japan was planning to attack a location referred to as "AF". They believed that "AF" might be Midway Island, because other locations in the Hawaiian Islands had codewords that began with "A". To prove their hypothesis that "AF" corresponded to "Midway Island" they asked the US forces at Midway to send a plaintext message about low supplies. The Japanese intercepted the message and immediately reported to their superiors that "AF" was low on water, confirming the Navy's hypothesis.

Chosen plaintext attacks (CPAs) are often used to break symmetric ciphers

This is an attack model for cryptanalysis where the attacker is assumed to be capable of asking for the plaintexts of arbitrary ciphertext messages. The attacker;s goal once again is to reveal the secret encryption key.

Adaptive-chosen ciphertext attacks were largely considered to be a theoretical concern until 1998, when the RSA encryption in concert with the PKCS1 encoding function was successfully broken. This allowed an SSL session key to be exposed in a reasonable amount of time, perhaps a day or less.