Encryption Notes

From CSEP590TU
Revision as of 23:22, 19 November 2004 by Sbhuang (talk | contribs) (Views and issues on government-access keys)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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]
  • "A soldier engaged in combat doesn't always feel the need to do things "by the book" even when there are very good reasons to do so, and generals on the front line felt that they had other things to worry about. One codemaker suggested that the best way to address the problem was to publicly hang a few offenders, but he lacked the authority to do so." [8]
  • " if they didn't have time to properly encrypt a message, they shouldn't bother trying, sending the message unencrypted, or "in the clear". A partially or badly encrypted message could undermine a cipher or code system, sometimes completely, which made an unencrypted message far preferable." [9]
  • "The basic communication infrastructure of our society is becoming less secure, even as we use it for increasingly vital purposes. Cryptographic techniques more and more frequently will become the only viable approach to assuring the privacy and safety of sensitive information as these trends continue." risks98
  • "True information security requires operator security as well as high quality cryptographic design and implementation, and absolute information security is probably impossible." [10]

Uses of Encryption

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 [11] (page 3)


  • Cryptography isn't the only means of providing information security, but rather one set of techniques [12] (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.[13] (page 3). Alteration and creation of digitial data is also easy.

Historical Uses

Pre 1900

  • Spartans (5BC) - Scytale
  • Julius Caesar

WWI

Zimmermann Telegram (1917/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

WWII

Shoot down of Admiral Yamaoto (Aril 13, 1943)

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

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 [14] (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. [15] (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

Policy

Government Acts

The Computer Security Act of 1987

In 1987, the U.S. Congress, led by Rep. Jack Brooks, enacted a law reaffirming that the National Institute for Standards and Technology (NIST), a division of the Department of Commerce, was responsible for the security of unclassified, non-military government computer systems. Under the law, the role of the National Security Agency (NSA) was limited to providing technical assistance in the civilian security realm. Congress rightly felt that it was inappropriate for a military intelligence agency to have control over the dissemination of unclassified information.

Since the enactment of the Computer Security Act, the NSA has sought to undercut NIST's authority. In 1989, NSA signed a Memorandum of Understanding (MOU) which purported to transfer back to NSA the authority given to NIST. The MOU created a NIST/NSA technical working group that developed the controversial Clipper Chip and Digital Signature Standard. The NSA has also worked in other ways to weaken the mandate of the CSA. In 1994, President Clinton issued Presidential Decision Directive (PDD) 29. This directive created the Security Policy Board, which has recommended that all computer security functions for the government be merged under NSA control.


The Clipper Chip

The Clipper Chip is a cryptographic device purportedly intended to protect private communications while at the same time permitting government agents to obtain the "keys" upon presentation of what has been vaguely characterized as "legal authorization." The "keys" are held by two government "escrow agents" and would enable the government to access the encrypted private communication. While Clipper would be used to encrypt voice transmissions, a similar chip known as Capstone would be used to encrypt data. The underlying cryptographic algorithm, known as Skipjack, was developed by the National Security Agency (NSA). The NSA has classified the Skipjack algorithm on national security grounds, thus precluding independent evaluation of the system's strength.

Government Fact Sheet on The Clipper Chip Microcircuit

Digital Signature Standard

The Digital Signature Standard (DSS) is a cryptographic standard promulgated by the National Institute of Standards and Technology (NIST) in 1994. It has been adopted as the federal standard for authenticating electronic documents, much as a written signature verifies the authenticity of a paper document. The DSS was the first cryptographic standard developed under the regime established by the Computer Security Act, which was intended to limit the role of the National Security Agency (NSA) in the development of civilian standards. Documents obtained by EPIC under the Freedom of Information Act have demonstrated that the DSS development process was, in fact, dominated by NSA.

Paper on the negative results of DSS


Public Opinion

Princeton Survey Research Associates did a poll for Newsweek magazine back in 2001. The poll asked: "Would you favor reducing encryption of communications to make it easier for the FBI and CIA to monitor the activities of suspected terrorists -- even if it might infringe on people's privacy and affect business practices?" Fifty-four percent of those polled answered "yes," and 72 percent said anti-encryption laws would be "somewhat" or "very" helpful in thwarting similar terrorist attacks.


Views and issues on government-access keys

Members of the law enforcement and intelligence communities continue to express concern about widespread use of unescrowed cryptography. At the same time, these communities have expressed increasing alarm over the vulnerability of "critical infrastructure." But there is a significant risk that widespread insertion of government-access key recovery systems into the information infrastructure will exacerbate, not alleviate, the potential for crime and information terrorism. Increasing the number of people with authorized access to the critical infrastructure and to business data will increase the likelihood of attack, whether through technical means, by exploitation of mistakes or through corruption. Furthermore, key recovery requirements, to the extent that they make encryption cumbersome or expensive, can have the effect of discouraging or delaying the deployment of cryptography in increasingly vulnerable computing and communications networks.


Key access schemes are considered by law enforcement agencies as a possible solution to cope with issues like encrypted messages. However these schemes and associated TTPs raise a number of critical questions that would need to be carefully addressed before introducing them. The ongoing discussion of different legislative initiatives in the US is an illustrative example of the implied controversy. The most critical points are vulnerability, privacy, costs and effectiveness:

1)Inevitably, any key access scheme introduces additional ways to break into a cryptographic system. More people will know about "secret keys" and "system designs" leading to higher risks of insider abuse and the TTPs itself can become target for attacks. These new vulnerabilities are complex and need to be understood as substantial liability and privacy questions are implied.

2)The costs associated with key access schemes can be very high. Until now, questions on costs and who would bear them have not been addressed by policy makers. Important cost factors would be the specific requirements put on TTPs, e.g. response time to deliver keys, storage time for session keys, authenticate requesting government agency, secure transfer of recovered keys, internal security safeguards, etc. Furthermore, substantial and unknown costs would occur through the need for scaleability of key access schemes, i.e. making it work in a multi-million user environment. Up to now, such systems have at best been developed for small scale use. The costs to make them work on an economy of even global wide scale need to be looked at carefully.

3)Key access schemes can be easily circumvented - even if, hypothetically speaking, everyone would be forced to pass through these systems.

Key Escrow/Key Recovery