Cryptography and Authentication: Principles and Techniques
Cryptography and Authentication: Core Concepts
Confidentiality: Can you keep a secret? Integrity: Did you get the same message I sent you? Identification/Authentication: Who are you? Can you prove it? Authorization & Access Control: What are you allowed to do? Availability: Are you there when needed?
Symmetric Key Cryptography (SKC)
Secure Key Cryptography: Vigenere Cipher: P XOR k = C, C XOR k = P. The first byte of the plaintext is XOR’ed with the first character of k, the second byte with the second character, and so on. If all the characters of k have been used, the next byte of the plaintext is XOR’ed with the first character of k again. Applications: secure storage in insecure media, message transmission over insecure channels, authentication. Can be used with public key cryptography by encrypting k through PKC and then using SKC and k for message transmissions. PKC can be used for the same things as SKC including digital signatures (encrypt a message with your private key which can only come from you); signatures used for authentication, integrity checking. Given k and m, SKC is just c=f(m,k) —-> m=f-1(c,k). To break SKC, have to test all values of k (if 56 bits, that’s 256 possibilities to check). k should be changed every session (session key).
Data Encryption Standard (DES) and Advanced Encryption Standard (AES)
DES maps a 64-bit block (m) to a 64-bit block (c) using a 56-bit k. The key is 8 characters (64 bits) with 8 bits being parity bits. DES works at the bit level (0s and 1s) and are represented in hex (4 bits per hex digit). The message must be broken down into 64-bit chunks or padded to be 64 bits. The key is 56 bits (appears as 16 hex digits but each 8th bit is ignored as parity). AES maps a 128-bit block (m) into a 64-bit block (c) using a 128, 192, or 256 bit key (k).
DES Structure
First m is permuted (1st bit goes to 58th bit, 2nd bit goes to 25th bit, etc.). The final permutation is the inverse of the first permutation. That is, applying P then P-1 yields m. Each round generates a new key from k by creating a 48-bit key through splitting k in half, flipping left with right, rotating bits on each half, and merging (while dropping bits) the left and right side to a new 48-bit key. Then we take the permuted 64-bit mi, the 48-bit ki and run through a DES round generating a new 64-bit mi+1. The round works by splitting mi in half, moving the right half to the left side, mangling the old right side with ki and XORing it with the old left side to make the new right side, then merging them to have mi+1 (Li+1= Ri,Ri+1= Li XOR f(Ri, Ki)). This is done 16 times to get m16. The inverse of the initial permutation is applied to m16 to get c. To decrypt c, we reverse DES. We apply the initial permutation to undo the final, do each of the 16 steps in reverse, and then do the final permutation to undo the initial permutation to get m. In each step, they can be reversed by doing Li = Ri+1 XOR f(Li+1,ki), Ri = Li+1.
Handling Large Messages
When messages are too big, the easy solution is to just do DES in 64-bit blocks of the original message. This is called Electronic Code Book (ECB). Problems: some chunks can be identical which is a clue for bad guys, message order can be modified and not be noticed (or a message can be deleted). Could use Cipher block chaining (CBC) instead. Makes it such that if mi=mj then ci != cj and changing the ciphertext does not induce predictable plaintext changes at the receiver. Process:
This is more efficient than ECB. The random IV forces identical messages to encrypt differently. Changing ci causes mi and mi+1 to be scrambled.
Other Modes of Operation
- Output Feedback Mode (OFB): Encryption is done by XORing the message with a one-time pad. OFB is a stream cipher (can encrypt one byte at a time). The receiver gets the IV so it can generate the one-time pad as well, XORing with the ciphertext generates m. OFB is very efficient. If ci is modified only mi is scrambled. A message can arrive in arbitrarily sized chunks, and be encrypted/decrypted immediately (streamed) as opposed to CBC in which a 64-bit block needs to arrive in order to be encrypted/decrypted.
- Cipher Feedback Mode (CFB): Similar to OFB only instead of a one-time pad the previous message is used to encrypt the next message. If ci is modified, mi and mi+1 is scrambled.
- Counter Mode (CTR): Similar to OFB, a one-time pad is generated in advance, but instead CTR increments the IV and encrypts the results to get successive blocks of the one-time pad. Same efficiency as OFB. You can decrypt starting at any point (like CBC, as opposed to OFB and CFB).
Multiple Encryption DES (EDE)
The idea is that 56-bits isn’t much so let’s increase security. Use EDE (encrypt-decrypt-encrypt) or 3DES. Two keys are used. Each block goes through DES encryption with k1, DES decryption with k2, and DES encryption with k1 again. Decryption is the same but reverse (D(k1) -> E(k2) -> D(k1). Using 3 DES steps as opposed to 2 is more secure. 3 is considered secure enough for now. 3 keys is not more secure than 2 keys. Breaking EDE is equivalent to breaking DES with a 112-bit key.
How to integrate with CBC? This can be done “on the inside” or “on the outside”. On the inside refers to encrypting the message with CBC using k1, decrypting the message with CBC using k2, encrypting the message with CBC using k1. On the outside (the standard implementation) refers to doing CBC once after the EDE block has been completed. When bits are changed in ci, on the outside only garbles mi and mi+1, while on the inside garbles mi through the end of the message. “on the inside” is more secure and could be pipelined. On the outside is better for apps requiring self re-synchronization.
Message Digests and Hash Functions
Hash functions map messages of arbitrarily long size to fixed-size messages (MD5 are 128-bit, SHA-1 are 160-bits). They should be easy to compute, but one-way (not computationally feasible to get x from h(x)). Because hash maps are many-to-one, there are collisions. Weak collision resistance means that given x1 and H(x1), it is computationally infeasible to find x2 such that x2!=x1 and H(x2) = H(x1). Strong collision resistance means it is computationally infeasible to find any two messages x1 and x2 such that x2 != x1 and H(x1) = H(x2). Applications – storing password digests (store hash of the password), testing message integrity (verifies the message is the same as what was sent), Improving digital signature efficiency (easier to sign the digest than sign the message), authentication, generating one-time pads for OFB or mixing pads and ciphertext like CFB.
MD5 and SHA-1 are main algorithms. MD5 takes 4 passes over each block of data and SHA-1 takes 5. Collisions can be found by math in MD5 but only through brute-force for SHA-1. They do not rely on a secret key (k). MAC (Message Authentication Code) incorporates k. Can be done by concatenating k to m and getting the MD5 or by using HMAC (prepend the key to the data and digest it, then prepend the key to the result and digest it).
Factors, Prime Numbers, and Modular Arithmetic
Two integers p and q are relatively prime if they have no common factors other than 1 (e.g., 26 and 51 or 5 and 7). Let Zn={0,1,…,n-1}. Let Zn* be a subset of Zn relatively prime with n (e.g., Z10*={1,3,7,9}, Z5*={1,2,3,4}). The totient function (phi(n)) is the size of Zn* (e.g., phi(10)=4, phi(5)=4). If p is prime then phi(p)=p-1. If n=pq then phi(n) = (p-1)(q-1) (e.g., n=3*5=15, phi(15)=2*4=8). If n is a positive integer and m is relatively prime to n, then (m^phi(n))-1 mod n = 0. Two integers p and q are multiplicative inverses when doing modulo n, if (pq)-1 mod n = 0 (e.g., 77 and 5 mod 96).
Public Key Cryptography (PKC)
Keys are not shared; instead, each individual has a public (e) and private key (d).
Can do everything SKC can do and more (generate digital signatures, establish secret keys for SKC) but slower by an order of magnitude. RSA is the main algorithm. Each user chooses two large prime numbers
p and q (around 256-bits and kept secret). Let n = pq and phi(n) = (p-1)(q-1). Pick e to be relatively prime to phi(n). Find d, the multiplicative inverse of e mod phi(n). That is, (de)-1 mod phi(n) = 0. For example: p=7, q=17, n=119, phi(n)=96, e=5, d=77. The list of prime numbers can be prepared offline. An alternate (and preferable) strategy is to choose e first and then select p and q such that (p-1)(q-1) is relatively prime to e. Popular e numbers are 3 and 216+1 (is prime). One strategy for finding p and q from e is: p=e*k+2 and q=e*h+2 where k and h are random numbers. RSA has problems with small message sizes (m3 < n).
Diffie-Hellman is another PKC algorithm. It is a public key distribution and not meant for exchanging arbitrary messages.
The problem DH tries to solve is making sure that Alice is who she says she is when trying to establish a
secret k over an insecure channel. DH is susceptible to the man-in-the-middle attack (see figure). The solution is to use authenticated DH where Ta and Tb are known. There is also the Digital Signature Standard (DSS). Digital signatures are messages that can only be encrypted by A but can be verified by everyone else. The idea is that party A produces a digital signature by encoding a fixed-length hash of the message using her private key and sends it together with the message. RSA’s solution is to the left. The problem here is that this is costly to compute (order of minutes) and DSS makes the operations only modulo 160-bit numbers and the exponent smaller than 256 bits without compromising security (order of seconds).
Authentication Techniques
Authentication is about verifying that someone is who they claim to be. This can be human authentication (e.g., Alice is using a public workstation to log on to a school account) or machine authentication (e.g., a print spooler is authenticating a printer). Humans can’t remember complex passwords or perform complex algorithms so they use clear-text small passwords. Machines can use complex passwords or operations. There are three main authentication techniques: what you know (passwords), what you have (physical keys/licenses/credit cards, etc.), what you are (biometrics, etc.). Bad guys will try to see the password in the transmission or read the password file on the computer or get the hash and try to break it, etc. The idea is to keep transmissions of passwords from being overheard, limit the number of guesses, and make passwords hard to guess. There are still the ability for hackers to get the password file and guess it offline. Salts help with this. A salt is a 12-bit number 0-4095, is based on the time of day, stored as 2 characters in the file, and is regenerated every time the password changes. The system stores both the salt and a hash of the combination of the salt and the password.
Security Handshake Pitfalls
Trivially authenticating (by providing a simple “I’m Alice” key and Bob matches the key against its own version for Alice’s key) only works over secure channels. There is the idea of Reflection attacks which is where Alice and Bob do exactly the same thing. This allows an intruder to repeat the message to the server and XOR the original with the encrypted message to determine k. This can be prevented by having the initiator answer a test first, or using different keys or challenges. One-way Authentication is where only one side of the communication is being challenged (whether by encrypting/hashing a random number or a timestamp to prove one’s identity), and mutual is where both are challenged. After authentication is done, the communications need to be encrypted to ensure privacy (SKC with a per-session key) and signed to ensure integrity (PKC).
