Symmetric Versus Asymmetric Ciphers
Keep communication confidential and hidden from unintended recipients
Transform words, letters, bits into gibberish
Intended recipient must be able to transform the gibberish back to its original form
Eavesdropper can only get gibberish
Two types: Symmetric (secret key) ciphers and Asymmetric (public key) ciphers
Until the mid-1970s, the only way to send data confidentially
Have sender and recipient share some secret information for gibberish transformation
E.g. replace message with letter 13 places ahead in alphabet. A -> N, B -> O, Z -> M. The recipient transform back using N->A, O->B, etc.
The shared secret information (how the transformation to and from gibberish) is called a "key"
Transformation to gibberish is called encryption
Transformation back to the original text is called decryption
The original message is called plaintext, is encrypted to gibberish called ciphertext
The entrie confidentially mechanism (the encryption, decryption algo) is called cipher
Symmetric cipher: When the encryption key and the decryption key are idential OR one key is very easily derived from the other (the shifting character examples)
Data Encryption Standard (DES) is a 128 bit symmetric cipher
Fast: Tens of megabytes per second or more
But,
Need secret key exchange: sender and recipient needs to share secret key prior to transmission of the message
Scalability issues: in a community of 1000 users, a user needs 999 secret keys for others, and 1 for him/herself. So, the whole community needs close to half a million of "unique" secret keys.
n users may require up to n*n/2 unique secret keys
Unknown Entities communication is difficult: how does a user make sure the out-of-band secret key exchange is safe?
Some of the above problems could be solved by using a central server architecture with KDC (Key Distribution Center) which the centeral server is an introducer for entities that do not previously know each other
Significant signle point of failure and single point of attack
PK Cryptography is invented by Whitfield Diffie and Martin Hellman in mid-1970s
Asymmetric Ciphers: Key for encryption and the key for decryption were related but conspicuously different
Concept based on vector-matrix and inversion of matrix to generate keys
Known as the "trapdoor functions with high computational complexity"
Classic paper in 1976 from Diffie-Hellman broke the way to ever-increasing pace of PKI research
Key pair: the keys are different that knowing one does not allow derivation or computation of the other
Public key is made available (telephone book, directories, open database)
Private key is kept privately (securely)
The keys in the key pair in PK cipher are different, but related. The relationship is mathematical and may reply on information known only to the creator of the key pair (e.g. factorization of a large integer, inverson of matrix, etc)
In theory, the private key can always be derived, but the amount of time, memory, or computing power necessary to do so in practice must be prohibitively high
Security between strangers
Idea: use public key to encrypt and corresponding private key to decrypt
But,
Sender must trust the public key repository for download. In other words, the phone in the phone book must be correct
Sender must find a way to trust the information. Public repository may be untrusted, but the information it returns should be independently verified for correctness.
Public repositories cannot be trusted to return correct information, thus, the info itself must be independently verifiable. Need the use of public-key certificate.
Bring the KDC by means of reading hte data suffices to compromise the entire system
With public repository, the attracker must be able to explicitly manipulate the contained data in a totally undetectable way. (Much much harder ... )
Encryption
PK cryptography is generally slower, so a two-step process for encryption is used
1. The data is encrypted using a randomly generated symmetric key (sometimes called section key)
2. The symmetric key is encrypted using the public key of the intended recipient of the data.
(Sender then sends the data to the recipient)
When the recipient receives the encrypted data, a corresponding two-step process takes place
1. The recipient obtains the symmetric key by decrypting the symmetric key using its private key
2. The symmetric key is then used to decrypt the actual data
Digital Signature
Analogous to hand-written signature
Entity "sign" the data, any number of entities can read the signature and verify its accuracy
Secure since it is virutally almost impossible to create sender's signature on some data
Think of as private-key operation on data (where the resulting value is the signature)
private key holder is the only one can sign
public-key operation is used to check the result corresponds to the original data
Data to be signed may be of any arbitrary size (e.g. cn or 10M file)
However, private-key operation takes a fixed-size input and computes a fixed-size output
So, cryptographic hash function is used. This type of functions has the property that maps an input of arbitrary size to a fixed-size ouput (which will be used by private-key operation).
Generally, two different hash inputs do not produce the same hash output
Signing operation:
1. Signer hashes the data to a fixed-size value
2. Signer subjects this value to a private-key operation
Verification:
1. Verifier hashes the data to a fized-size value
2. The verifier then examines this value, the transmitted signature, the signing entity's public key (if the signature matches the key and the hash value, the signature verifies; otherwise, verification fails).
Data Integrity
Digitial signatures provide:
1. Data origin authentication (evidence as to who originated the data), AND
2. Data integrity (evidence that the data has not been altered in any way)
Since hashing diff data will not produce the same result. Any change (alteration) to the data will lead to a different hash value.
Key Establishment
Key exchange (aka Key establishment) could be done with PK cryptography
A protocol that use public and private key pairs to generate a share secret symmetric key between two unknown entities
Two ways of doing Key Establishment
1. One way key transfer: sender generates the symmetric key and sends it to the other entity. (Use public key to encrypt and private key to decrypt the key)
2. Joint key agreement: both entitie jointly contribute to the generation of the symmetric key. (E.g. Diffie-Hellman key establishment protocol)
Other services are in the works, XKMS, SAML, etc.
RSA (Ron Rivest, Adi Shamir, Len Adleman in 1978), one of the earliest and most versatile of the public-key algorithms.
DSA (Digital Signature Algorithm) is a Federal Information Processing Standard (FIPS) publication of the National Institute of Standards and Technology (NIST) of the US Department of Commerce. DSA is designed exclusively for signing, verification and use for data integrity.
DH: Whitefield Diffie and Martin Hellman. Simple and eleganant key establishment algo.
ECDSA and ECDH. The DSA and DH algorithms can be computed over the group of points defined by the solution to an equaton for an elliptic curve over a finite field defined. (Almost no one uses this today)
SHA-1: Secure Hash Algorithm is designed specifically for use with the DSA but can be used with RSA or other public-key signature algo as well. Its design principles are similar to those used in the MD2, MD4, and MD5 hash functions proposed by Ron Rivest.
Copyright 1996-2003 OpenLoop Computing. All rights reserved.