Cryptography
Block Cipher – Breaks the plaintext into blocks and encrypts each with the same algorithm
Cipher – Cryptographic transformation operates on the characters or bites
Ciphertext or Cryptogram – unintelligible message
Clustering – plaintext message generates identical ciphertext using the same algorithm but different keys
Codes – A cryptographic transformation that operates at the word or phrase level
Cryptanalysis – act of obtaining plaintext or key from ciphertext. It is used to obtain valuable information and to pass on altered or fake messages in order to deceive the original intended recipient.
Cryptographic Algorithm – Step-by-step procedure used to encipher plaintext and decipher ciphertext
Cryptography – Art and Science of hiding the meaning of communication
Cryptology – encompasses cryptography and cryptanalysis
Cryptosystem – set of transformations from message space to ciphertext space; A strong cryptosystem has a large keyspace (entire keyspace to choose the values from) . It has a reasonably large unicity distance. A system that provides encryption and decryption.
Strength of cryptosystem: An algorithm with no flaws, a large key, using all possible values within a key space and protecting the actual key are important elements of encryption. If one is weak it affects the whole process.
Cryptoperiod: period for which the same is used.
Decipher - to undo cipherment process
Encipher – to make a message unintelligible to all except recipient
End-to-end encryption – Encrypted information that is send from sender to receiver. End-to-end encryption: refers to the protection of data from the originating host all the way to the final destination host with no unprotected transmission points. In a complex environment, end to end encryption is provided at the presentation or application layer.
Encryption (Encipher) is the transformation of data into a form that is as close to impossible as possible to read with out the appropriate knowledge (a key). Its purpose is to ensure privacy by keeping information hidden from anyone for whom it is not intended, even those who have access to the encrypted data.
Decryption (Decipher) is the reverse of encryption; it is the transformation of encrypted data back into an intelligible form.
Exclusive Or
Boolean Operation
Indicated by XOR
Indicated by symbol
Easily implemented in hardware
0+0=0, 0+1=1, 1+1=0, 1+1=0
Input A / Input B / Output T0 / 0 / 0
0 / 1 / 1
1 / 0 / 1
1 / 1 / 0
XOR operated on the bit level
XOR the plain text (byte level) with the keystream source
Can be reversed by simple XOR of output plus keystream.
A XOR B = T
T XOR B = A
Key – cryptovariable
Information or sequence that controls enciphering and deciphering of message
Plaintext – a message in clear text
Steganogrophy
Secret communication of a message where communication is hidden
Example – least significant bit of each pixel in an image file contains bit of a message.
Hiding the existence of the message.
A digital watermark would be used to detect copying of digital images
Work Function (Factor)
Difficulty in recovering plain text from ciphertext as a factor if time and cost
Systems security is directly proportional to the work function
Work function should be commensurate with the value of the data
Security of cryptosystem should depend ONLY on the secrecy of keys and not on algorithm
History of Cryptography
Traced back to the Egyptians in 3000B.C.
Scytale
used by Spartans in 400B.C. – wrap message around wooden dowel
diameter and length are the keys to the cipher.
Caesar cipher
Monoalphabetic substitution – only used one alphabet
Specifically - Involved shifting the alphabet three letters
Known as C3 (Caesar shift 3 places)
Cipher Disks
Two concentric disks with letters on the edge
Can be used to match up letters
Arabs invented cryptanalysis
Arab philosopher al-Kindi wrote Manuscript on Deciphering Cryptographic Messages
Thomas Jefferson - disks
1790 developed device with 26 disks that could be rotated individually
Message would assembled by lining up the disks to the alignment bar
Then the bar was rotated a given angle and the resulting letters were the cipher text
The angle of rotation of the alignment bar was the key
Disks used extensively during the civil war
UNIX – ROT13 shift the alphabet 13 places
Hagelin Machine
Developed in 1920 by Boris Hagelin – Stockholm Sweden
Known as the M-209 in the US
1920’a Herbert O. Yardley was in charge of U.S. MI-8 (a.k.a. the Black Chamber)
Cracked codes of a number of Nations
Gave U.S edge in Japanese negotiations in 1921-1922
U.S. State Department shut down MI-8
Upset, Yardley published book The American Black Chamber 1931
Japanese got new codes
Yardley is father of American Cryptology
William Frederick Frederick published the Index of coincidence and its applications in cryptography. He is referred to as the “father of modern cryptography”.
Japanese Purple Machine
After Yardley William Friedman resumed cryptanalysis for U.S. Army
Broke the new Japanese cipher.
U.S. Navy broke the Purple Machine naval codes during World War II
German Enigma Machine
Polyalphabetic substitution cipher - using mechanical rotors
Developed in 1919 by Dutchman Arthur Scherbius obtained US Patent for Berlin firm
Polish cryptanalyst broke the three-ring system with card file of all 6 x 17,576 possible rotor positions
1938 German went to six rings
In 1938 Poles and French developed the “Bombe” there own Enigma machine
British took over in 1940 and by 1943 British and US had high speed “bombe”
Disks have 26 contacts on each side, to communicate with each neighboring disk one of them makes contact with the other disk
Also rotates the disks after encryption of each letter
Rotates next highest rotor like a “gas pump” – polyalphabetic
Other rotor machines – German Enigma, Japanese Red, Japanese Purple and American SIGABA “Big Machine”
Vigenere Polyalphabetic Cipher
Caesar is a subset of the Vigenere Polyalphabetic Cipher
Vigenere used 26 alphabets
Each letter of the message corresponds to a different alphabet
Subject to guessing the period, when the alphabet changes
Modulo returns the remainder over the modulo value
C=(M+b) mod N
Where
C = Cipher Text
M= Message
B = fixed integer
N = size of alphabet
Caesar monoalphabetic can be attacked by using frequency analysis.
Polyalphabetic cipher is accomplished through the use of multiple substitution: counters frequency analysis but can be attacked by discovery of periods.
Transposition – Permutation
Columnar Transposition – write the message vertically and read horizontally
Can be attacked through frequency analysis however hides the statistical properties of letter pairs such as IS and TOO.
Book or Running Key Cipher
Using text from a book as the key and performing modulo26 addition on it.
Would use specific line and page number
Codes - Deal with words and phrases and represent them with other numbers or letter
Identify types of Encryption systems
Types of Cipher / Characteristcs / ProblemsClassical substitution ciphers / Replaces bits, characters, or blocks of characters with different bits, characters, or blocks.
Transposition (permutation) ciphers / The letters of the plaintext are permuted. / Frequency analysis
But it hides the statistical properties of letter pairs and triples such as IS and TOO.
Monoalphabetic or simple substitution ciphers / Only one alphabet was used, which are monoalphabetic substitution / Frequency analysis
Polyalphabetic Ciphers / Does not replace the original text with different text but moves the original text around. Is accomplished through use of multiple substitution ciphers / Counters Frequency analysis however, attacked by discovery of periods.
Running key ciphers / Using text from a book as the key and performing modulo26 addition on it.
Would use specific line and page number
Does not require electronic algorithm and bit alterations / -
Concealment / The true letters of plaintext are hidden/disguised in a sentence say every third word in a sentence.
Does not require electronic algorithm and bit alterations / -
Digital System
Codes / Deal with words and phrases and represent them with other numbers or letter
Steganography / Hiding the existence of the message.
A digital watermark would be used to detect copying of digital images
Machines
End-to-end encryption / Encrypted information that is send from sender to receiver
Protection of data from the originating host all the way to the final destination host with no unprotected transmission points.
In a complex environment, end to end encryption is provided at the presentation or application layer.
Start to finish; more flexibility; higher granularity becos each application different key; hop computer does not need to have key for decryption. / Headers, addresses, routing and trailer information are not encrypted hence attackers can learn more about capture packet
Destination to have same encryption mechanism to properly decrypt the message.
Link-to-link encryption : / Each entity has key in common with two neighboring nodes.
Node 1 –Encrypts with key A
Node 2 – Decrypts with key A and encrypts with key B
Node 3 – Decrypts with Key B and encrypts with Key C
The term refers to the use of encryption to protect a single segment between two physically contiguous nodes. It is usually a hardware device operating at layer 2. Such devices are used by financial firms to protect automatic teller machines transactions. Another common form of link-to-link encryption in the secure telephone unit (STU) used by the military.
Provides data flow security since everything is encrypted.
Users need not do anything; works at lowest layer – physical layer / Key distribution and key management is more complex because each hop computer must receive a key and when the keys change each must be updated.
Messages are decrypted at each hop thus there are more points of vulnerability.
Both End to End and link should be used to strengthen the process:
The data is encrypted with the End to End and entire packet ie header and encrypted data packet is encrypted with link – great
One-Time pad / Vernam Cipher.
Unbreakable and each pad is used
exactly once.
Truly non-repeating set of random bits that are combined bitwise XOR with message to produce cipher text. Encryption with key K ith components k1, k2,…kn, the encipherment uses each component of k to encrypt message M with components m1, m2,…mn.
The Key is the same length as the Message; Random key
Key only used once and never again
Key must be completely random
Two identical key pads one with sender and another with receiver
Unbreakable by exhaustive search
Relies on physical security of the pad
Used
Invented 1917 by the US Army Signal Corps and AT&T / More overhead
Distribution of pad, or key can be challenging
Perfect synchronization of timing for usage.
Cipher
Long as message hence infeasible to use in all application. Not very practical
Clipper Chip / Clipper Chip – implemented in tamper proof hardware
Skipjack algorithm / Only 80 bit hence weak and not opened for testing or any proof of trying out.
16 bit checksum can be defeated
CC id tagged and identified every communication session.
Double/Triple DES / -refer above-
Public Key / -refer above-
RSA / -refer above-
Elliptic curve / -refer above-
PGP / -refer below-
El Gamal / -refer above-
Diffie-Hellman / -refer above-
Escrowed encryption / US government clipper chip;
Allowing law enforcement to obtain the keys to view peoples encrypted data
Escrow the key in two pieces with two trusted escrow agents
Court order to get both pieces
Clipper Chip – implemented in tamper proof hardware
80 bit family key and 80 bit unit key ( which is to be secret and this encrypts the session key). Session key is used to encrypt the message.
Based on Skipjack algorithm
Key exchange through Diffie-Hellman
Key Escrow / Uses public key cryptography
Fair Cryptosystems – Sylvio Micali, MIT
Private key is split and distributed
Can verify each portion of the key without joining.
Public key is also split and sent along / Criminal encryption use exists.
Encryption is not regulatable outside the US.
Key recovery is expensive for both government and software companies.
Escrow has not been thoroughly tested.
Mandatory escrow can be circumvented. There is no way to "scan" the Internet to detect use of non-escrowed encryption.
Escrow involves humans.
The government would hold the key to everyone's personal data. Under current proposed legislation, keys would be released by a court subpoena, not a judicial order.
Types of Encryption
Secret Key Cryptography – Symmetric Key
Sender and receiver both know the key
Encrypt and decrypt with the same key
Secret key should be changed frequently
Requires secure distribution of keys – by alternate channel; Out of band method is used to exchange the key.
Ideally only used once
Secret Key Cryptosystem does have both public and private information
Large keys like >128 bit are very hard to break
Very fast
Key needs to be secret.
Sender requires different key for each receiver
Time stamps can be associated to the key so valid only during time window (counters replay)
Symmetric key do no Authentication or repudiation
Best known is DES developed by IBM in 1970’s for commercial use
Key Management: only for symmetric wide distribution of keys. Can be manual, or through link or end to end encryption and last choice is through KDC.
Algorithm need not be secret though we need strong algorithm. Used in : low cost chip implementations which are widely available and incorporated into a number of products, because algorithm need not be secure.
The encryption scheme is computationally secure if the cipher text meets one or both criteria such as cost of breaking the cipher exceeds the value of the encrypted information and time required is more than the useful life of the data.
Public
Algorithm for enciphering plaintext
Possibly some plaintext and cipher text
Possibly encipherment of chosen plaintext
Private
The KEY
One cryptographic transformation out of many possible transformations
Fiestal : Dr. Horst Feistel led a research project at the IBM Watson Research Lab in the 1960's which developed the Lucifer cipher. This later inspired the US DES (below) and other product ciphers, creating a family labeled ``Feistel ciphers''.
- Higher block size it is safe but reduced speed; tradeoff 64
- key size – higher the better ; trade off 128
- number of rounds : higher the better typical is 16
- subkey generation algorithm and round key function : more complex the better.
Speed is a concern if the encryption is embedded in applications which precludes the hardware hence slower; also, ease of analysis is good but DES is not done that way.
Public Key Cryptography
Employee private and public key
Public made available to anyone wanting to encrypt a message
Private key is used to decrypt
Public Key cannot decrypt the message it encrypted
Ideally private key cannot be derived from the public key
The other can decrypt a message encrypted by one of the keys
Private key is kept private
1,000 to 10,000 times slower than secret key encryption
Hybrids use public key to encrypt the symmetric key
Important algorithms Diffie-Helllman RSA, El Gamal, Knapsack, Elliptic Curve
Whitfield Diffie and Martin Hellman published ``New Directions in Cryptography'', introducing the idea of public key cryptography.
Key management: only transcription and storage.
Very slow, better key distribution, scalability and provide confidentiality, authentication and non-repudiation.
In order to be useful should have a trap door, a secret mechanism that enables you to accomplish the reverse function in a ONE WAY HASH FUNCTION.
A mathematical function that is easier to compute in one direction (forward direction) than in the opposite direction (inverse direction)
Forward direction could take seconds, inverse months
‘Trap-door one way function’ is a one way function for which the inverse direction is easy given a piece of information (the trap door)
Public Key Cryptography is based on ‘trap-door one way functions’
Public key: gives info about the function
Private key: gives info about the trap door
Whoever knows the trap door (private key) can compute function easily in both directions
Under Public Key Cryptography, there are two formats:
Open message ( if authentication is more important)
- Sender encodes message with own private key
- Receiver decodes with sender's public key
Secure message format ( if confidentiality is more important)
- Sender encodes in the receiver’s public key.
- Receiver decodes with own private key
Secure & signed message
- Sender encodes message with own private key
- Sender re-encodes message with receiver's public key
- Receiver decodes message with own private key
- Receiver decodes message with sender's public key
Hybrid systems
Using Symmetric and Asymmetric known as public key cryptography: symmetric for bulk data encryption and asymmetric for protecting encryption keys and key distribution.
- Asymmetric algorithm performs encryption and decryption by using public and private keys
- Symmetric algorithm performs encryption and decryption by using a secret key.
- A secret key is used to encrypt the actual message
- Public and private keys are used to encrypt the secret key
- A secret key is synonymous to a symmetric key
- An asymmetric key refers to a public or private key
Symmetric
Algorithm / Developer / Provides / Key Size (bits) / CharacteristicsDES
64 bit block size / IBM under US government
contract (devised in 1972
as a derivative of Lucifer
algorithm by
Horst Feistal at IBM.
Modified by NSA to come
up with US DES / Confidentiality.
It can be used in many applications including during data transmission and file security. Implemented in electronic devices including VLSI, RAM, PROM, EEPROM and ROM / 56 bits / Defacto industry standard.
64 bit block size. It begins with a 64-bit key and
strips off 8 parity (1 odd in each byte) bits.
8 bit parity can be used for error detection
16 rounds of transposition and substitution