Encryption Notes

Overview

• An encryption scheme is sometimes refered to a cipher
• "Having transformations which are very similar but characterized by keys means that if some particular encryption/decryption tranformation is revealed, then one does not have to redsign the entire scheme but simply charge the key" [1] (page 12)
  • When two parties wish to communicate securly using an encryption scheme, the only thing they keep secrete is the key pair.
• If the number of symbols of a given type is preserved in an encrypted text, cryptanalysis is easy
• Transposition spreads redundency across the ciper text (diffusion)
• Substitution adds confusion - obscuring the relationship between the key and cipher text.
• The size of the key space does not guarentee the security of the encryption scheme

Quotes

• "The level of information security sought in any particular situation should be commensurate with the value of the information and the loss, financial or otherwise, that might occur" [2]
• "Cryptography, over the ages, has been an art practised by many who have devised ad hoc techniques to meet some of the information secuirty requirements" [3] (page 6)
• "The objectives of information security cannot solely be achived through mathematical algorithms and protocols alone, but required procedural techniques and abidance of laws to achive the desired result" [4] (page 2)
• "One can gain additional security by keeping the class of encryption and decryption transformation secret but one should not base the security of the entire scheme on this approach. History has sown that maintaining the secrecy of the transormation is very difficult indeed." [5] (page 14)
• Codes
  • "A reasonably-designed code is generally more difficult to crack than a cipher, but of course suffers from the difficulty of preparing, distributing, and protecting codebooks." [6]
  • "Using a code requires printing and distributing a large number of codebooks, a process that is very vulnerable to thievery or treason" [7]

Uses of Encryption

Information Security

• Encryption is one means to achive information security

Objectives

Information has many objectives.

Privacy Data Integrity Entity Authentication (Identification) Message Authentication Signature Authorization

Validation Access Control Certification Timestamping Witnessing Receipt

Confirmation Ownership Anonymity Non-repudiation Revocation [8] (page 3)

• Cryptography isn't the only means of providing information security, but rather one set of techniques [9] (page 4)
• The digital age has changed information security dramatically. In the paper age, making thousands of indistinguishable copies copies of was much more difficult. In a digitial society, a means to ensure information security that is independent of the physical medium is required - security must rely on the digital information itself.[10] (page 3). Alteration and creation of digitial data is also easy.

Historical Uses

Pre 1900

• Spartans (5BC) - Scytale
• Julius Caesar

WWI

Room 40

• British effort in WWI to decrypt German transmissions
• Named for the room in the Admiralty building it started in

• Assisted by capture of several naval ciphers.
  • Russians recovered the body of a German signals officer after the wreck of the light crusier Magdenburg with cipher books
  • Deep sea dives performed by Shipwright E.C. Miller to recover code books from sunken U-Boats
  • Decrypted the Zimmermann Telegraph

References

• http://www.vectorsite.net/ttcode4.html

WWII

Ultra - Decryption of Axis radio messages

• Name used by the British for intelligence resulting from decryption of German communications
• Primarly dealt with Enigma machines
• Most traffic was military
• Several different Enigma varients, including commercial versions
• Naval Enigma used different key managment, making its traffic more difficult to break
• Fundamental breaks made in 1932 in Poland
• Naval Enigma machine captured
• Contributors included Alan Turing and MAx Newman

Cold War

Venona Project

• Long running secret collaboration between US and UK intelligence agencies to decrypt Soviet messages
• Out of hundreds of thousands of messages, it is claimed that under 3000 have been decrypted
• Esponiage (stealing pads, bugging rooms for keystroke analysis) contributed to decryption
• Revealed some spies in research and government (Julius and Ethel Rosenberg, Klaus Fuchs, Cambridge Five)
• Made possible because soviets resued some one-time pad material
• Not made public until 1995

References

1. http://www.brainyencyclopedia.com/encyclopedia/v/ve/venona_project.html
2. http://www.cypher.com.au/crypto_history.htm

Modern

• Signed Email
• Encrypted Passwords
• Online Banking
• E-Commerce
• ATMs

References

• Ultra at Free Dictionary
• Enigma *

Mathematics

• Intractable problems provide the fundamentals Cryptography systems
• Bijections are used as the tool for encrypting messages and the inverse transformations are used to decrypt [11] (page 8)
• A one-way function from X to Y is "easy" to compute for all x in X, but "hard" to find any x in X such that f(x) = y for essential all elements y in the range of f for X. [12] (page 8)
  • I didn't do a very good job transcribing that. (JSN)
  • I tend to think of rolling a large rock down a steep hill. (JSN)
• A trapdoor one-way function is a one-way function, that, given some extra information it becomes feasible to find for any given y an x such that f(x) = y.
  • Integer factorization
  • None one has yet definitvely proved the existence of such functions
  • The basis for public-key crptography

Encryption Techniques

One Time Pad

• The is the only perfectly secure encryption scheme. Brute force attacks on all other encryption schemes are theoretically possible.
• Developed in WWI, but use wasn't practical for most uses at the time
• "The key has to be provably random, just a string of gibberish. Such a key is known as an "incoherent" key, in contrast to a "coherent" key based on readable text." 1
• "The key can not be used to encrypt more than one message" 1
• " The key has to be provably random, just a string of gibberish. Such a key is known as an "incoherent" key, in contrast to a "coherent" key based on readable text." 1
• "If the key is at least as long as the message; the letters in the key are truly selected at random; and the key is never used again, then the encryptions of each letter in the message are completely random as well." 1
• "Since there's no fixed pattern in the ciphertext or the key, a key can be easily synthesized to produce every possible message that will fit into the number of plaintext letters" 1

Block Cipher

• Break the plain text into blocks of a fixed length

Substitution ciphers

• Replace symbols, or groups of symbols by other symbols or groups of symbols
• Distribution of the letter frequencies is preserved in the cipher-text (encrypted text)
• Homophobic substitution ciphers trade data expansion for a more uniform distribution of the symbols
• Polyalphabetic substituion cipers do not preserve symbol frequency (Vigenere Cipher)

Stream Cipher

• Block length ciphers with block length of 1
• Encryption transformation can be changed for each symbol
• Do not propagate errors
• Can be used for online encryption/decryption

Product Ciphers

• Combite multiple basic ciphers

Public Key Cryptography

• Encryption key is public knowledge
• Decryption key is keyt private by the receiver
• Public keys must be authenticated to ensure the data origin.

http://www.cs.washington.edu/homes/naeglej/images/public_key_encryption.jpg

Symmetric-key Encryption

• The same key is used for encryption and decryption
• Finding efficent ways to to exchange keys securely is a major challenge
• The decrypt key must be kept secret

http://www.cs.washington.edu/homes/naeglej/images/symmetric_key_communication.jpg

Hash Functions

• Used to simplify the computational requirements for digital signitures
• Can be used to detect modification (MDC) or authenticate messeages (MAC)

Encryption Implementations

DES - Data Encryption Standard

• Symmetric Block Cypher based on a 64-bit block.
• Developed by IBM in 1974
• Released as a federal standard in 1976
• Based on the Lucifer Algorithm
• 56-bit key length (reduced from 128 by NSA)
• Probably good enough for personal or commercial use
• Same algorithm and key are used for encryption and decryption

PGP - Pretty Good Privacy

• Developed by Philip Zimmermann
• Late 1980s
• RSA initally used to provide key management
• IDEA Algorithm provided data encryption layer
• Released onto the internet

Diffe-Hellman-Merkel Key Exchange

• Addresses the key-exchange problem
• Asymmetric key theory (public and private keys)

RSA

• Named after inventors (Ron Rivest, Adi Shamir and Leonard Adleman)
• Asymmetric cypher
• Used for public key cryptography
• Based on difficulty in factoring large numbers
• Public and private keys are functions of large (300-400 digit) prime numbers
• Recovering plaitext from public key requires factoring the product of the two primes

Attacks

• An adversary will often attempt to play the role of either the legitimate sender or receiver
• An unsecured channel is one where an adversary can reorder, delete, insert or read
• A secured change is one where an adversary can not reoder, delete, insert or read
• Attacks can be on the encryption schemes or the protocols

• Passive attack

http://www.cs.washington.edu/homes/naeglej/images/attack_1.jpg

• Active Attack (attacking public key encryption)

http://www.cs.washington.edu/homes/naeglej/images/attacking_public_key_encryption.jpg