What is Cryptography

• Encryption - With encryption, the idea is to scramble a message in such a way that only the intended recipient of the message can unscramble it, so that only the two of you know the message. The fundamental areas of cryptography involve two encryption methods. A method of encryption is called a cipher. A cipher is a method of transforming a message to conceal its original meaning. It should be immediately obvious to you that encryption is used to help provide confidentiality, what we'll see later is that it also helps with the other tenets of cybersecurity. The fundamental areas of cryptography are:
  • Symmetric Encryption is also known as secret-key encryption, for reasons that we will learn shortly, is one of the oldest and simplest forms of encryption. Symmetric means the same, so when we talk about symmetric encryption, we are talking about using the SAME key for both encrypting and decrypting information. It is for this reason that we must keep the key SECRET. This key can be a word, or a string of random letters, and is applied to the information (message) in a particular way (algorithm or CIPHER). One of the biggest issues with symmetric encryption is how to distribute the SECRET key to everyone you want to communicate with.
  • Asymmetric Encryption, also known as public-key cryptography, allows us to establish secure communications even when we have no opportunity to agree on a secret key ahead of time. Public-key cryptography does this by creating a pair of keys with unique properties. This key pair consists of a public key and a private key. The public key is meant to be shared and used for encryption, while the private key is meant to be kept SECRET and be used for decryption. If you encrypt a message with the key-pair public key, it can only be decrypted by using the key-pair's private key and vice-versa.

Symmetric Encryption:

First let us define symmetric encryption. Symmetric means the SAME, so when we talk about symmetric encryption, the SAME key is used for both encryption and decryption. The key used for encryption and decryption must first be a SECRET and it also must be the SAME when we are referring to symmetric encryption. The key can be a number, a word, or just a string of random letters, and is applied to the text of a message to change the content in a particular way. Both the sender and recipient must know the key before they can exchange messages.
After reading this, did you pick-up on one of the challenges of deploying symmetric encryption? That's right - key distribution - how are you going to make sure that everyone you want to communicate with has the required key and that the key remains a secret. The solution to this issue will come in a different lesson. For now, let's look at a few examples of symmetric encryption that has been and is currently being used in practice.

Simple Symmetric Encryption Example: Caesar Cipher

Every introduction to cryptography starts with the Caesar Shift Cipher, and who am I to buck tradition. To set the scene, we have two communicating parties: Alice and Bob. Alice is sending a message and Bob is receiving. Then we have an eavesdropper, Eve, who wants to know what's in the message. Alice's original message is called the plaintext. She wants to scramble the message to produce what we call the ciphertext, which should be unintelligible to Eve, but easily unscrambled by Bob. The scrambling process is called encrypting, while the unscrambling is called decrypting.



The Caesar Shift Cipher assumes your message is all capital letters, and replaces each letter in the plaintext with a new letter to produce the ciphertext. The replacement scheme is based on a secret key that Alice and Bob have agreed upon ahead of time — a number in the range 1-25 called the shift value. The replacement scheme is simple: if the shift value is s, the kth letter in the alphabet is replaced by letter k+s in the alphabet, circling back around to the front of the alphabet if necessary. So with a shift value of 3, the letter B (the 2nd letter in the alphabet) is replaced with the letter E (the letter number 2+3 = 5 in the alphabet). You can use the little applet below to help encrypt a message once you've chosen a shift value. The applet should also more clearly show you how the shift has the effect of mapping the original plaintext value to a new letter which when complete will become the new ciphertext value.

Shift Value 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Important: When encrypting you ADD the shift value and when decrypting you SUBTRACT the shift value. You might also notice that a shift value of 26 is equivalent to a shift value of 0. Let's follow this process through from start to finish:

1. At some earlier time, Alice and Bob agree to a secret key/shift-value k = 11.
2. Alice decides to send Bob the secret message "MEET ME AT NOON", i.e. plaintext = MEET ME AT NOON.
3. Alice encrypts the plaintext (using something like the table above) with key k=11 to get: ciphertext = XPPE XP LE YZZY.
4. Alice sends Bob the ciphertext.
5. Eve manages to read the message in transit, but since she reads the ciphertext, XPPE XP LE YZZY, she can't make sense of it. Not knowing the key, she can't decrypt it to recover the plaintext.
6. Bob receives the ciphertext and decrypts it using something like the table above, in reverse, with key k=11, recovering the plaintext MEET ME AT NOON.



Although very simple and, as we'll see, not very secure, the Caesar Cipher is a good example of how symmetric encryption works. It has the basic properties of any cryptosystem: two communicating parties Alice/Bob, nefarious eavesdropper Eve, plaintext/ciphertext, encryption/decryption. Moreover, it's representative of one of the two basic classes of cryptosystem, symmetric encryption (also called secret-key), where there is a secret key, shared by both Alice and Bob, that is used to encrypt and decrypt the message. With the Caesar Cipher the secret key is the shift value.

Encryption Key Management


Much of military communications are encrypted today for obvious reasons. What is not so obvious is how the Navy and Marine Corps manage all of the encryption keys used for encrypted communications. The system used throughout the military is called the Electronic Key Management System (EKMS) and is centrally controlled by the National Security Agency (NSA). EKMS is in place to provide communications security (COMSEC) material (i.e. encryption keys) and support tools for tracking and managing encryption key material, generation, distribution, and accounting.



Sound like an important job? It is and you might be the one doing it at your command as a junior officer. Every Naval or Marine unit that uses secure communications has at least two EKMS managers and it is common practice to have a junior officer act as one of them.

Cryptanalysis

Cryptanalysis is the study (art) of analyzing cryptographic systems with the goal of discovering vulnerabilities or weaknesses that can be used to exploit the system. Cryptanalysts will use a variety of techniques in achieving their ultimate goal of recovering plaintext from ciphertext, discovering the encryption key, or discovering some other weakness in the scheme. An example of just a few of these techniques include:
• Brute Force Attack: This involves trying to use every possible key with the aim of discovering the secret key in use. This is obviously a very time consuming process and in most cases not a practical technique. Is this a useful technique to attack the Caesar cipher? The answer is yes ... you only have to try 25 keys which shouldn't take too long.
• Frequency Analysis: This involves analyzing the frequency of letters used in a given ciphertext. The most common ciphertext letters are assumed to be directly related to the most common plaintext letters in the language being attacked. We will give you an in-depth look at using frequency analysis to target the Caesar cipher below.
• Known Plaintext Attack: In this attack the cryptanalyst has access to both the ciphertext and either some or all of the plaintext. The more ciphertext and plaintext pairs the cryptanalyst has access to will increase their chances of success. Success is defined by recovering any information previously unknown about the encryption key and the encryption scheme in use.
• Chosen Plaintext Attack (CPA) and Chosen Ciphertext Attack (CCA): These both involve the cryptanalyst having the ability to interact with the encryption device or system. In this case the cryptanalyst can provide the system with plaintext or ciphertext and look at the resulting output.

Frequency Analysis Example — breaking the Caesar cipher

Not all letters get used with the same frequency in English. E's get used all the time, whereas Z's are not very common. One kind of cryptographic attack, i.e. a way to foil a cryptosystem so you can read secret messages, is based on analyzing the frequencies of letters in the ciphertext to get information about what key value produced that ciphertext. If you can deduce the key, you can decrypt the message (crack the code).

Let's suppose you are Eve, and you've intercepted the message(ciphertext) XPPE XP LE YZZY. There are more P's than anything else, so you might guess (correctly in this case) that a P in the ciphertext came from an E in the plaintext. This would lead you to guess the key/shift-value k = 11.

It's not always going to be that easy of course. The ciphertext RNCP KU QHH has more H's than anything else. If we assume that H's in the ciphertext came from E's in the plaintext, we would deduce a key/shift-value of 3. Decrypting assuming k = 3 gives OKZM HR NEE... which is probably not the secret message. In fact, the plaintext that produced this message was PLAN IS OFF.

The problem with this approach is that we only considered one letter — the most common appearing in the ciphertext. Assuming H's came from E's gave us lots of E's in our "cracked" message, but it also gave us Z's and K's, which are pretty uncommon. To do frequency analysis properly, we should consider all the letters in the message. This is tedious, of course, but when something is tedious, it just means that we ought to write a program and let the computer do it for us. Try out this page which features a JavaScript program for cracking Caesar shift encryption via frequency analysis. It functions by calculating for each shift value the likelihood of that shift value being correct based on the frequencies of the letters that result from decrypting the given ciphertext with that shift value. It's very interesting to see how few characters of ciphertext are required to recover the key with a high degree of certainty.

So we see that the Caesar Shift Cipher is not very secure. In particular, it's quite vulnerable to attack via frequency analysis. Its problems are a) there are only 26 key values, so trying them all is a viable option, and b) since a given character in the plaintext is always replaced with the same character in the ciphertext, letter frequencies carry over from plaintext to ciphertext.

More Sophisticated Symmetric Encryption: The Vigenere Cipher

.

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

B

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

C

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

D

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

E

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

F

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

G

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

H

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

I

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

J

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

K

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

L

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

M

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

N

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

O

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

P

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

Q

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

R

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

S

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

T

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

U

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

V

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

W

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

X

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

Y

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Z

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Next we'll consider a more sophisticated (and, in fairness, more recent) cryptosystem called the Vigenere Cipher. It is a symmetric key encryption method, like the Caesar Cipher, but it addresses the problem of too few key possibilities and the carrying over of letter frequencies from plaintext to ciphertext.

The key is a string of letters like JOE. To encrypt, you take your plaintext (we'll reuse MEET ME AT NOON) and write it down. Then you write down the key string over the plaintext, with letters matching up. If the plaintext is longer than the key, you simply repeat the key. Like this:

JOEJ OE JO EJOE ← key (repeated as needed)
MEET ME AT NOON ← plaintext
  

Next you write down (or have on hand) the table you see on the right. The encrypted value of a plaintext character is the table entry whose row is given by the plaintext character and whose column is given by the key character written above it. Thus, the first letter of our message encrypts to the table entry at row M and column J, which is a V. (Check out this demo to see the process on a short message.) Decryption is straightforward if you understand encryption: write down the ciphertext with the key written above it (repeated as needed). To decrypt a character in the ciphertext, identify the column given by the key character above the ciphertext character. Find the ciphertext character in that column. The row at which it appears is labeled with decrypt value, i.e. with the corresponding plaintext character.

Think about how the Vigenere Cipher addresses the flaws in the Caesar Shift. The key is a string of characters, and since there are roughly 6 trillion strings of length less than 10, for instance, the problem of too few keys has been addressed. The same letter at different positions in the plaintext generally does not get mapped to the same character in the ciphertext, since the key-character written above plays a role in the encryption. So letter frequencies in the plaintext do not get carried over to the ciphertext.

Frequency Analysis Attacks on the Vigenere Cipher & the One Time Pad

The Venona Project: Poor Practice Defeats Perfect Security
One-time pads provide provably perfect security ... but at a price. Managing keys is really difficult! After all, you have to have as many bytes of key as you have bytes of plaintext to communicate. During WWII, the British and US intercepted a large amount of Soviet Russian communication that was encrypted with one-time pad encryption. However, cryptanalysis revealed that some of the one-time pad keys had been reused ... which is the big no-no with one-time pad encryption. This misuse of the system allowed small parts of the communication to be decrypted. NSA's effort to exploit this misuse of one-time pad keys to decrypt as much as possible of the traffic was code-named VENONA. Over the years (Venona lasted until 1980), this code-breaking effort revealed Soviet espionage campaigns and spies at places like Los Alamos National Labs, the State Department and the White House. It identified the Rosenbergs and Alger Hiss as spies.
• http://en.wikipedia.org/wiki/Venona_project
• http://www.nsa.gov/public_info/declass/venona/index.shtml
With any cryptographic protocol, even a small deviation from the protocol can compromise security. This fact should be a major take-away from the story of the Venona project!
Cyber Pigeons?
Before there was the Internet, there were pigeons. In late 2012, a British man found a dead carrier pigeon in his chimney. Turns out it was from WWII and it carried an encrypted message tied to its leg. CNN has a nice story, UK spies unable to crack coded message from WWII carrier pigeon, about it and the fact that nobody's been able to decrypt the message. Turns out, the sender used a one-time pad.
The Vigenere Cipher is still susceptible to a frequency analysis attack. First of all, you have to convince yourself that if the key length is n, what we see if we restrict ourselves to every nth character of the plaintext/ciphertext is simply a Caesar Shift. The shift value is simply the first key character's position in the alphabet (A=0, B=1, etc). Starting from the second position and restricting to every nth character gives us a shift value corresponding to the second character in the key, and so on. Since we can crack Caesar Shift (given enough characters), we can crack each of these "every nth character" problems and recover the key. Then we can decrypt just as easily as the recipient.

Finding the key length can be a problem, but one easy way given what we already know is this: for each possible key length n, form the string consisting of every nth character starting from the first, give that as a ciphertext input to our Caesar Shift Frequency Analysis page, and make a note of the probability of the shift index it gave you for that n. Whichever n value gave us the highest score is probably the actual length of the key. In class, we will actually have performed this exercise.

This kind of attack requires enough text that our Caesar Shift frequency analysis of every nth character finds the proper shift index with high probability. If the message length is L, and we assume we need about 20 characters to be assured of having a high probability with our Caesar Shift frequency analysis, we'd like to have L/n > 20. If L is short or n is long, our attack will fail. So, in general, a longer key gives you more security from frequency analysis. If you have a key that is a completely random sequence of letters, and which is as long or longer than the message, the Vigenere Cipher is unbreakable — provided you never use the key again. In this situation, the system becomes what is called a one-time pad. The problem with such a system is that arranging to have this one huge key is difficult.

Chosen Plaintext Attack & the Vigenere Cipher

A kind of chosen plaintext attack was done by the US during WWII. We knew a Japanese attack was imminent because we had cracked a code, but we didn't know whether the string designating the target was referring to Hawaii or Midway. So we leaked a story about a water shortage on Midway, and discovered that same symbol in a message that was, we were sure, relaying that leaked information.

The thing about the Vigenere and Caesar Shift Ciphers is that there are three strings — the key, the plaintext and the ciphertext — and knowing any two is enough to get the third. As an attacker, i.e. as "Eve", you know the ciphertext. If you haven't got that, you've got nothing. What if you knew the message? What if you could induce Alice to send a specific message to Bob? Or at least a message that contains some text you know. For instance, if Bob is a spy, and I leak to him that I'm planning an attack on Albuquerque, I can guess that the next message he sends will contain the word "Albuquerque" somewhere. So, suppose Bob goes and sends the message:

JZFDEYNFUDS MB KLNFI CVIH KMUZ ECHELY

We'll assume that "Albuquerque" is in fact the first word, so we have

???????????
ALBUQUERQUE
↓↓↓↓↓↓↓↓↓↓↓
JZFDEYNFUDS

We work through to recover the key like this: row A has a J in the J-column, so J is the first letter of the key. Row L has a Z in the O-column, so we have an O as the second letter, and so on. In this way we recover JOEJOEJOEJO and deduce that the key was JOE.

Real-World Symmetric (Secret Key) Encryption: AES (Advanced Encryption Standard)

A stick figure guide to AES
Check out the stick figure guide to AES which tells you as much or as little as you want to know about AES, how it came to be and how it works. Plus, it's pretty funny.

Encrypting Bitcoin


This Wired article is about a man’s quest to decrypt an encrypted zip file with $300,000 worth of bitcoin. This file was not encrypted with AES but a somewhat outdated encryption standard and was ultimately able to be decrypted.

Advanced Encryption Standard (AES) is a symmetric key (i.e. there is a single, shared secret key) encryption algorithm for encrypting digital data. It is a 128-bit block cipher, i.e., it always operates on 128 input bits at a time, although it has several variants with different key sizes. The variant we'll talk about uses 128-bit keys. It's widely used, and it has been approved by the National Security Agency (NSA) for encrypting top secret information.

Usually, AES is not a stand-alone tool. Instead, it is embedded in systems that use it for security. For example, the archiving tool PKZIP uses it to provide the option of creating a password protected .zip file. Windows offers BitLocker, which allows you to encrypt your hard disk. That way, if your computer, or disk, or backups are stolen, your data is still secure. Bitlocker uses AES. SSL traffic may use AES. IPSec, which is a standard for secure IP (Internet Protocol) traffic uses AES. Suffice it to say, there are many more examples.

Instructor AES Demonstration

In this activity your Professors will demonstrate how to encrypt and decrypt a file using AES (with CBC mode). Note an in depth understanding of the different modes used with AES are beyond the scope of this course, but it is worth noting that not all implementations of AES are equally secure.

Generate a 256-bit key	$ openssl enc -aes-256-cbc -md sha256 -pbkdf2 -iter 100000 -P -k MySecretWord salt=0C8E8E821AB80FAB key=AF1F7C30DCDF8B5691817EE5B1A3E11CB77B61CEF993772D73C2A55E2CABDCF6 iv =EE286E2CD7D56FE55874EC6E1BAA159C
Encrypt	$ openssl enc -aes-256-cbc -pass pass:MySecretWord -p -in WhatIWantToEncrypt.txt -out TheNameOfMyEncryptedOutput.txt salt=DF60C340D63467F1 key=D3325D264A3C61913A3D575CB8179675298D94929FE982A6FCAF872D8EFFCF25 iv =D59C03D3C4D0C42BD4983B06CA34B35B
Decrypt	$ openssl enc -d -aes-256-cbc -pass pass:MySecretWord -p -in TheNameOfMyEncryptedOutput.txt -out DecryptedFile.txt I Love SY110!!!

Student AES Activity

Although AES is usually embedded in other tools, we've provided you with a shell/command-line tool called aes that you can use as a stand-alone tool to encrypt and decrypt files and strings. You can use it to generate passwords (because coming up with random strings of 32 hex bits is tedious), to encrypt, and to decrypt. After running the commands think back to your Professor's demo - what is different about the encrypted output? Is this version of AES secure? What might be some potential issue(s) with your version of AES?

Generate a 128-bit key	$ aes -k adccbb42e647d10370992205ddc268e6
Encrypt	$ aes -e adccbb42e647d10370992205ddc268e6 "Who's afraid of the big bad wolf?" d31cfef5689d1cf37b725934c8d314f9e57a26bbbeb528c0364ab4edd0819b70829cc4f22add97df1a866a4ef176c2c4
Decrypt	$ aes -d adccbb42e647d10370992205ddc268e6 d31cfef5689d1cf37b725934c8d314f9e57a26bbbeb528c0364ab4edd0819b70829cc4f22add97df1a866a4ef176c2c4 Who's afraid of the big bad wolf?

Identify the key, plaintext and ciphertext.
The aes tool also operates on files. You can give the aes -h command for more information.

References

Schneier, Bruce. 1996. "Applied Cryptography : Protocols, Algorithms, and Source Code in C". Wiley

Singh, Simon. 1999. "The Code Book: The Science of Secrecy from ancient Egypt to Quantum Cryptograph". New York, Anchor Books

Dworkin, M. , Barker, E. , Nechvatal, J. , Foti, J. , Bassham, L. , Roback, E. and Dray, J. 2001. "Federal Inf. Process. Stds. (NIST FIPS)-197, National Institute of Standards and Technology". Gaithersburg, Maryland, NIST Pubs

Committee on National Security Systems. 2015. Committee on National Security Systems (CNSS) Glossary. Ft. Meade, MD: April 6, 2015.

Martinez, Michael. 2012. "UK Spies Unable to Crack Coded Message from WWII Carrier Pigeon" CNN, November 24, 2012.
https://www.cnn.com/2012/11/23/world/europe/uk-wwii-pigeon-mystery/index.html

National Security Agency. VENONA Washington: National Security Agency and Central Security Service.
https://www.nsa.gov/news-features/declassified-documents/venona/

U.S. Code. 2012. Title 44 - Public Printing and Documents Section 3542. Washington: Government Printing Office, January 3, 2012.

---