Exam2-4393

Secret Key Cryptography

• Claude Shannon
  • proved in 1937 with his Master’s thesis that electrical switches could solve boolean algebra
  • This along with two additional paper were the foundation of information theory
  • Proposed Confusion and Diffusion system

Diffusion and Confusion

• Concerned with strong ciphers against statistical analysis
  • Strong cipher: knowledge of how the cipher is made should give no evidence of how to decode. The solution should give no hints to the key or plaintext
• Shannon proposed a “product cipher” - a block cipher consisting of a sequence of simple operations

  Diffusion

  • can be accomplished by repeatedly transposing the data, many bits in plaintext will contribute to each ciphertext letter.
    • Good diffusion is determined if a change in a single plaintext letter has on average ~0.5 letters change in the ciphertext

Confusion

relation between statistics of the ciphertext and the key. The more complex the higher the confusion.

• Can be achieved with a more complicated substitution algorithm.

Feistel Cipher

• 1971 IBM sold a Feistel Cipher called “Lucifer” with 16 rounds of 128 bit blocks and 128 bit keys
• Data is rounded and then XORed with the other half of the data. This makes it nearly impossible to get the plaintext without the key.
• The round function can be as complicated as you wish, making it more secure
• Decryption and encryption use the same algorithm just in reverse.

DES

• NIST in 1973 called for a national standard for encryption
• Systems such as IBM’s Lucifer were submitted for approval
• The 56-bit standard is used until 2001
  • UNIX used DES to hash passwords. Password is permutated, a subsequent 25 times before being stored in /etc/password
  • This 25 fold of encryption forces the attacker to crack the code for each implementation of this permutation algorithm.
• F Function - Half block (32 bits) - passed through the “E Box” to transform the half block into a 48 bit sequence - Subkey ( 48 bits ) - The half block and subkey are XORed, and split into 8 groups of 6 bits S1-8

  Note for Exam 2

  Said he may ask us on the exam to go through the F Function by hand Given some hexadecimal numbers, find the output Example can be seen on Wikipedia on how the algorithm works

Triple DES

• Notice that 56-bit of DES is too short as computers advance.
  • double was tried but it is vulnerable to meet in the middle attack

Meet in the middle Attack

• The attack tries many keys and denotes what the encrypted output is.
• using these points he can measure the difference between input and output to solve the algorithm

Block Ciphers

• unlike stream ciphers which only work in one dimension and direction we can use block ciphers on 2d arrays of numbers. This allows us to parrallelize the work of encryption
• Each block of encryption is entirely independent from the other blocks.
• If you want to ensure no duplication you can attach the output of one block into the input of another with an XOR gate to ensure NAND.
• s-bit Feedback Mode
  • Using some size s, we can continually encrypt text, then selecting the first s bits (perhaps 1 byte) that will be output
  • This output goes back into the loop to find the next byte of the encryption
  • if one block get corrupted, all the next blocks will be incorrect
• output feedback mode
  • does effect other blocks when one fails
• Counter Mode

Key Management

Why?

Secret key depends on the sender and receiver having a shared key that is kept secret

Key Types

• Major problem with how do we distribute and handle the master keys
  • attacks on key distribution typically easier
• Session Keys
  • generated dynamically, used, and then destroyed after the session
• Master Key
  • can be used to encrypt session keys
  • typically shared with key distribution center

Key Distribution Center

• In order for Alice and Bob to get a secure key that only they share. They can use a third party who will securely give them a key
• Alice and Bob request a session key, which is shared so they can set up their new secure encryption channel
• In order to create enough secure channels, the KDC needs to have N master keys, where N is the number of connected hosts
• Drawbacks
  • If the KDC is compromised, then the whole network is leaked. Single point failure
  • performance bottleneck
  • Alice needs to wait for bob to get a session token, which depending on the KDC they may not be willing to communicate with some clients

Needham-Schroeder Protocol

• A KDC Protocol which only has communication from the KDC to one host

1. Alice request to talk to bob
2. KDC sends a session key to Alice, with bob’s session key encrypted by KDC with bob’s master key to avoid Alice peeping
3. Alice sends this package to bob with the session key encryption
   1. Bob challenges

Public Key Cryptography

Problems with Secret Key

must exchange the secret key before communications a host needs N-1 secret keys to talk with everyone KDC is a single point of failure

Diffie-Hellman Key Agreement Protocol (DH)

Premise of Diffie-Hellman

Two hosts can setup a secret key across a public network without a KDC

• A = Alice, B = Bob, P = public prime number, g = public int < p (and other restrictions)
  1. A will randomly choose a number X and send a modified X’ = g^X mod p → B
  2. B does the same, choose a number Y and sends Y’ = g^Y mod p → A
  3. Now Both A and B have both X’ and Y’
  4. Using X’ and Y’ both A and B compute a common master key g^(XY) mod p

DH provides no form of authentication

Public Key Ciphers

• Use the public key to encrypt, and private key to decrypt.
  • These keys need to be related, but in a way that it is computationally difficult to deduce
• PKC Encryption
  • using a hard mathematical problme to define the relationship between the keys
  • Integer factorization, discrete logarithm on an elliptic curve
• anyone can encrypt a message with anyone’s public key, but only ones with the private key can decrypt

RSA

• patented public key cryptosystem
• key length is variable (typically 512)
• very similar to Diffie-Hellman using large integer multiplication to create the message

Public Key Management

• public org issue keys
  • Certificate Authority
  • after certification no communications with CA needed
• Public Key Certificates
  • Bob registers with CA and requests a public key
  • Bob can send his certificate to share his public key with others
  • anyone can verify the CA is authentic and not tampered
  • Certificate has owner’s name, public key, and digital signature of the CA

Message Authentication

• Messages are exchanges between hosts in a network environment
• Encryption prevents information disclosure (Confidentiality)
• A messages’ authenticity is its unaltered nature and came from claimed source.
• authentication prevents falsification and masquerading attacks

Damgard / Merkle

• Unix password hash function, where E = DES + permutation

MD5

• Input can be of any length
  • processed in 512 bit blocks
  • processing a block creates an intermediate 128 bit result

SHA - 1

• input size less than 2^64 bit
• uses 512 bit pages

MAC using Hash

• MAC needs to include secret key in the address
  • can append a secret value before hashing
  • use keyed hash function