Cryptography

General Issues: (problem, terminology, public vs. private key)

by Mike Mellott

The Problem:
If a user is able to bypass the protection mechanism of a system or tap a physical channel, some other means must be in place to prevent uncontrolled intruder access to confidential information.

The Solution: Cryptography
Cryptography is a technique that provides added protection to the system in the event of such unauthorized information disclosures. Cryptography allows a piece of information to be converted into a cryptic form before being stored in a computer system or being transmitted over a physical channel. It can also be used for establishing the authenticity of a user to another user or entity.

Model of a Cryptographic System

Legend
M - Plaintext message.
Ke - Encryption key.
Block E - Performs encryption with key Ke.
C - Ciphertext C=Eke(M)
Kd - Decryption Key
Block D - Performs decryption with key Kd (i.e. M=Dkd(C))
Block CA - Performs crytoanalyst function
SI - Side information known about the process.

Potential Threats

The types of threats is dependent on the type of side information (SI) available. Increase in SI implies an increase in the potential threat. The following defines the three basic types of threats.
Forms of attack:
Cipher-text Only: Cipher-text is obtained through the tapping of an insecure channel. The intruder then uses probability characteristics or context of the cipher-text to break the cipher.
Known-plaintext: Both the ciphertext and a considerable amount of the corresponding known plaintext are known to the intruder. The intruder then simply compares the input to the output of the encrytion device in attempt to break the cipher.
Chosen-plaintext: The intruder can obtain the ciphertext corresponding to plaintext of his choice. The intruder then simply inputs to the encrytion device his chosen text and obtains the output in attempt to break the cipher.

Systems that can withstand these forms of attack are secure. A system that is secure to a Chosen-plaintext attack is also resistant to the previous two forms of attack, but a system that is resistant to known-plaintext may not be resistant to a chosen-plaintext attack.

Forms of Cryptosystems

Private Key:
A single key is used for both encryption and decryption and it is kept secret.
Key distribution problem - a secure channel is needed to transmit the key before secure communication can take place over an unsecure channel. One of the more common sources of private keys is the Data Encryption Standard (DES) libraries.
Public Key:
The encryption procedure (key) is public while the decryption procedure (key) is private.
Requirements:
  1. For every message M, D(E(M)) = M
  2. E and D can be efficiently applied to M
  3. It is impractical to derive D from E.

Data Encryption Standard (DES)

DES was developed by IBM and is the official standard for use by the U.S. federal government. The following are the two basic operations used in DES:
Permutation
The bits of a word are permuted.. This provides diffusion by spreading the correlation and dependencies among the bits of a word.
Substitution
An m-bit input is replaced by an n-bit output. This process provides confusion. This is performed in three steps:
  1. m-bit input is converted to decimal form.
  2. The decimal output is permuted giving another decimal number.
  3. This decimal output is converted into n-bit output.
The DES Process
DES uses a block cipher technique that encrypts 64-bit data blocks with a 56-bit key (we'll call key). These data blocks go through a three step process:
  1. Plaintext undergoes initial permutation (the 64-bit data block is permutated).
  2. The permuted block undergoes complex transformation. This transformation uses the a key and involves 16 iterations. These iterations each use the key derived from the key and the iteration number.
  3. The final step is to inverse permute output of step two in the same fashion as in step one.

Glossary

Intruder: A user not authorized to access information.
Plaintext: An intelligible message that is to be converted into an unintelligible (i.e., encrypted) form.
Ciphertext: A message in encrypted form.
Encryption: The process of converting plaintext to ciphertext.
Decryption: The process of converting ciphertext to plaintext.
Key: A parameter used in the encryption/decryption process.

Reference

1. Singhal, Mukesh, and Niranjan G. Shivaratri, Advanced Concepts in Operating Systems, pp. 404-412.

Go Back to the Operating Systems page.

Last updated 30 April 1995

e-mail:

mmellott@csgrad.cs.vt.edu