Cryptology
Diomidis Spinellis
Department of Management Science and Technology
Athens University of Economics and Business
Athens, Greece
dds@aueb.gr
Cryptology
- Cryptography:
-
Generalized methods to hide (encrypt) and authenticate information
- Cryptanalysis:
-
Generalized methods to expose and substitute information
Algorithm Uses and Properties
-
Algorithms reversibly converting data (plaintext) into unintelligible form (ciphertext).
- E(P) = C, and then D(C) = P
- Only knowledge of "secret" allows recovery.
- Kerckhoffs's doctrine (19th century):
not based on the secrecy of the algorithm.
- E(P, EK) = C, and then D(C, DK) = P
- Building blocks for services/protocols that provide other assurances such as
- confidentiality
- integrity
- authentication
- non-repudiation
Algorithm Types
Algorithm applications
- Confidentiality
- Block Ciphers: we encrypt several plaintext symbols at once in a block
- Stream Ciphers: the encryption rule depends on a plaintext symbol's position in the stream of plaintext symbols.
- Authenticity and non repudiation:
- Hash Functions
- Digital Signatures
Maintaining Confidentiality
- One time pad (OTP)
- length of key equal to message length
- c = m XOR k
- c XOR k = m
- perfect secrecy
- severe key distribution problems
- Shared secret key
- c = E(m,k).
- D(c,k) = m
- requires key distribution
- vulnerable to exhaustive key search
- Private / public key
- Key generator creates Ek, Dk
- c = E(m, Ek)
- D(c, Dk) = m
- Computationally expensive
Transposition Ciphers
- Re-arrange order of letters
- Write-in in a geometrical figure (square, scytale)
- Take-off in a specified order
- Key is the figure and the order
Example
1 2 3 4
T R A N
S P O T
I T I O
N X X X
Take-off as 2, 4, 3, 1: RPTXNTOXAOIXTSIN
Try RAYXPAIXYNSXCTLS
Transposition Cryptanalysis
- Recognize by noting relative frequencies
(same as in natural language)
- English: ... f m u c d h l r s n a I o t e
- Greek ... π λ μ ν σ ε κ σ ρ
τ ι ο α
- Use digraph and trigraph frequency distributions
Substitution Ciphers
- Shifted alphabets
- C = P + K mod 26
- Caesar Cipher (K=3)
- Key is the shift
- Cipher alphabet
- Key is the substitution alphabet
- Cryptanalysis: Single letter frequency analysis
Polyalphabetic Ciphers
Rotor Machines
- Each rotor maps 26 characters on the front face to 26 on the back face
- Simple substitution cipher
- After each encoding rotation changes the mapping
- Introduces polyalphabetic element with period 26
- The output of one rotor feeds the next
- Introduces function composition
- The key is the rotor wiring, placement, and initial position
- Used by the Germans during the WW2
- Cryptanalyzed by the British using electromechanical computers
The Playfair Cipher
Example:
A -> B
B -> I
O -> P
R -> U
T -> A
X -> V
L -> O
A -> I
N -> L
D -> G
I -> Y
N -> L
G -> H
X -> W
SP Networks
- To increase block size we need (prohibitively) larger tables
- As an example a function 16 -> 16 bits would
require a table of 220 bits (16 * 216).
- A substitution permutation network requires a lot less
storage
- Data has to pass through the network multiple times to add
diffusion and confusion to the plaintext
- Result is called a product cipher
Example: 4 bit S-box design with a single permutation
The Data Encryption Standard (DES)
- 64 bit input and output
- 56 bit key (marginal length; vulnerable to exhaustive key search)
- Standard for encryption of unclassified data since 1977
- 16 internal rounds
DES structure
The Advanced Encryption Standard (AES)
- Result of a public process
- Evaluation criteria:
- Security
- No licensing
- Computational efficiency
- Memory requirements
- Flexibility (key size, block size, time/memory tradeoffs)
- Hardware and software suitability
- Simplicity of design
- Acts on 128-bit blocks
- Key 128, 192 or 256 bits (for 10, 12, 14 rounds)
Operation Modes
Block ciphers can be operated in a number of different modes
- Electronic code book (ECB)
- Cipher block chaining (CBC)
- Output feedback mode (OFB)
Electronic Code Book (ECB)
- Each block is separately encoded
- Same blocks result in same ciphertext
- Can be used to locate known plaintext (e.g. blanks)
- Subject to cut and splice attacks
Cipher Block Chaining (CBC)
- Each plaintext block is XORed with the previous encrypted block
Cn = E(Pn XOR Cn - 1, K)
- Patterns in plaintext are concealed
- An error is only propagated one block
- Can do random access decryption
(one block look backwards required)
- Subject to some cut and splice attacks
- Last block can be used as a
message authentication code (MAC)
since it depends on all the message and the key
Output Feedback Mode (OFB)
- An initial vector is encoded N times
- The result of each encoding is used to XOR a message block
- Allow pre-computing of pseudorandom stream
- No error propagation problem as in CBC
- Allow in-time encrypt/decrypt due to bit-wise computation
- Subject to known-plaintext substitution attacks:
Knowing Pi allows you to recover Ki and
substitute Ci with Ci'
Hash Function Properties
Hash functions compress a n (abritrarily) large number of bits
into a small number of bits (e.g. 512).
Properties
- One way; can not be reversed
- Output does not reveal information on input
- Hard to find collisions (different messages with same hash)
Common Hash Functions
- Block cipher in CBC mode
- SHA1 (secure hash algorithm) 160-bit output
- MD5 (message digest) 128-bit output
- SHA256 SHA512 (secure hash algorithm) 256/512-bit output
Hash Function Applications
- Construct a message authentication code (MAC)
- Digital signature
- Make commitments, but reveal message later
- Timestamping
- Key updating: key is hashed at specific intervals resulting in new key
Asymmetric Ciphers
- Key is split into private and public part
- Public key can not be used to derive private key
- Encryption is performed using the public key
- Decryption is performed using the private key
- The two operations can be combined to establish secrecy and sender authenticity
- Can be used to implement a digital signature
- Underlying mathematical operations
- Factorization (factor a product of two primes)
- Discrete logarithm (calculate the integer nth root of a number)
- Elliptic curves
- Computationally expensive
- Typically used to establish common secret key
The Diffie-Hellman Protocol
- Can be used to establish common secret key over insecure channel
- Requires commutative encryption function E(E(M, Ka), Kb) = E(E(M, Kb), Ka)
- Procedure
- Alice chooses a key M
- Alice sends Bob E(M, Ka)
- Bob sends Alice E(E(M, Ka), Kb)
- ... which is E(E(M, Kb), Ka)
- Alice decrypts it into E(M, Kb) and sends it to Bob
- Bob decrypts it to M
- M can then be used as a shared secret key
Case Study: Public Key Cryptography
The following example is based on the
OpenSSL (http://www.openssl.org/) open-source cryptography
library and command-line tool.
#!/bin/sh
################
# Key generation
# Create Alice's key pair
openssl genrsa >alice.private
# Obtain Alice's public key
openssl rsa -pubout <alice.private >alice.public
# Create Bob's key pair
openssl genrsa >bob.private
# Obtain Bob's public key
openssl rsa -pubout <bob.private >bob.public
##########################################
# Alice sends a short confidential message
# Secret message Alice wants to send to Bob
echo "Alice loves you" >message.plain
# Alice encrypts the message using Bob's public key
openssl rsautl -encrypt -in message.plain -out message.encrypted -pubin -inkey bob.public
# Bob decrypts Alice's message using his private key
openssl rsautl -decrypt -in message.encrypted -out message.decrypted -inkey bob.private
##################################
# Bob sends a short signed message
# Message Bob wants to sign
echo "Will you marry me?" >message.plain
# Bob signs the message using his private key
openssl rsautl -sign -in message.plain -out message.signed -inkey bob.private
# Alice verifies Bob's message using his public key
openssl rsautl -verify -in message.signed -out message.verified -pubin -inkey bob.public
#####################################################
# Alice sends a large signed and confidential message
# Secret message Alice wants to send to Bob
cat >message.plain <<EOF
Marital AGREEMENT
THIS AGREEMENT, made this thirteen day of June, 2004 is between Bob
and Alice
1. PURPOSE. The parties expect to be married to death do them part,
and hear by enter into this agrement vouluntarily.
2. EFFECT OF AGREEMENT. The parties agree that if one or the other
commits infidelity during the duration of the marriage, that the person
guilty of said act shall in effect and wholey forsake all material
property, assets and rights to act as a parent of any children.
3. DEFINITON OF INFEDELITY. Infedelity is defined as follows: Any
socializing with the intent to establish a realtionship, and/or
physical contact with other person.
4. JOINT PROPERTY, ETC. This Agreement does not restrict, prohibit
or condition any conveyance or transfer by the parties, or either of
them alone, of the Separate Property of either party into tenancy in
common, joint tenancy, tenency by the entireties or any other form of
concurrent and/or undivided estate or ownership between the parties,
or the acquisition of any property in any such form of ownership by the
parties. The incidents and attributes of ownership and other rights
of the parties with respect to any property so conveyed, transferred
or acquired shall be determined under State law and shall not be
governed by or otherwise determined with reference to this Agreement.
5. SEPARATE PROPERTY. The parties agree that there is no seperate
property.
6. WAIVER OF RIGHTS. Except as otherwise provided in this Agreement,
each party hereby waives, releases and relinquishes any and all right,
title or interest whatsoever, whether arising by common law or present
or future statute of any jurisdiction or otherwise.
7. DISSOLUTION/SEPARATION/ANNULMENT. Except as otherwise provided in
this Agreement, each party specifically agrees that neither shall make
any claim for or be entitled to receive any money or property from
the other as alimony, spousal support, or maintenance in the event
of separation, annulment, dissolution or any other domestic relations
proceeding of any kind or nature, and each of the parties waives and
relinquishes any claim for alimony, spousal support or maintenance,
including, but not limited to, any claims for services rendered,
work performed, and labor expended by either of the parties during
any period of cohabitation prior to the marriage and during the entire
length of the marriage. The waiver of spousal support shall apply to
claims both pre and post-judgment.
8. RIGHT TO CONTEST. Nothing contained herein shall limit the right
of either party to contest any domestic relations suit between the
parties or to file a countersuit against the other party; However,
in any hearing on such suit, this Agreement shall be considered
a full and complete settlement of all property rights between the
parties. In such case, neither party shall maintain any claim or demand
whatsoever against the other for property, suit money, attorney fees
and costs which is either inconsistent with or not provided for in
this Agreement.
9. INTEGRATION. This Agreement sets forth the entire agreement between
the parties with regard to the subject matter hereof. All prior
agreements, covenants, representations, and warranties, expressed or
implied, oral or written, with respect to the subject matter hereof,
are contained herein. All prior or contemporaneous conversations,
negotiations, possible and alleged agreements, representations,
covenants, and warranties, with respect to the subject matter hereof,
are waived, merged, and superseded hereby. This is an integrated
agreement.
10. BINDING ON SUCCESSORS. Each and every provision hereof shall
inure to the benefit of and shall be binding upon the heirs, assigns,
personal representatives, and all successors in the interest of
the parties.
11. ACKNOWLEDGEMENTS. Each party acknowledges that he or she has
had an adequate opportunity to read and study this Agreement, to
consider it, to consult with attorneys individually selected by each
party, without any form of coercion, duress or pressure. Each party
acknowledges that he or she has examined the Agreement before signing
it, and has been advised by independent legal counsel concerning the
rights, liabilities and implications of this document.
12. STATE LAW. It is intended that this Agreement be valid and
enforceable within the provisions of the State Law, and that Case
Law that governs its interpretation. State law is considered to be
that of California, USA.
EOF
# Alice generates a short random key to be used for encrypting the message
openssl rand 16 -out key.plain
# Alice encrypts the message with the short random key
openssl des3 -e -kfile key.plain -in message.plain -out message.encrypted
# Alice creates a message digest of the message to sign
openssl dgst -binary message.plain >message.digest
# Alice signs the digest using her private key
openssl rsautl -sign -in message.digest -out digest.signed -inkey alice.private
# Alice encrypts the random key using Bob's public key
openssl rsautl -encrypt -in key.plain -out key.encrypted -pubin -inkey bob.public
# Alice sends Bob:
# - the encrypted message
# - the encrypted key
# - the signed message digest
# Bob decrypts Alice's encrypted key using his private key
openssl rsautl -decrypt -in key.encrypted -out key.decrypted -inkey bob.private
# Bob decrypts the message using the decrypted key
openssl des3 -d -kfile key.decrypted -in message.encrypted -out message.decrypted
# Bob verifies the digest Alice has signed using her public key
openssl rsautl -verify -in digest.signed -out message.digest1 -pubin -inkey alice.public
# Bob calculates again a message digest of the message
openssl dgst -binary message.plain >message.digest2
# Bob compares the two message digests to verify Alice signed the agreement
# he has examined
diff message.digest1 message.digest2
A Simple Public Key System
- Create a graph with a known perfect code
- We draw a set of dominating edges
- Add more edges around each edge
- Add more verices between the non-dominating edges
- The graph is our public key
- The exact dominating set the private key
- Determining whether the graph as a dominating set is NP-complete
- Simple example: fair coin tossing over the phone
- Alice sends map to Bob
- Bob guesses whether number of dominating edges is odd or even
- Alice reveals the solution
- Public key encryption and decryption
- To transmit a secret number
- Randomly distribute the number on all edges
- For each edge send the sum of all its immediate neighbours and itsself
- To decrypt
- Sum the values of the dominating set
Bibliography
- Ross Anderson.
Security Engineering: A Guide to Building Dependable Distributed Systems,
pages 73–113.
John Wiley & Sons, New York, 2001.
- Friedrich L. Bauer.
Decrypted Secrets: Methods and Maxims of Cryptology.
Springer Verlag, 1997.
- Tim Bell, Harold
Thimberly, Mike Fellows, Ian Witten, and Neil Koblitz.
Explaining cryptosystems to the general public.
In Louise Yngström and Simone Fisher-Hübner, editors, WISE 1:
First World Conference on Information Security Education, pages
221–233. IFIP TC11 WG 11.8, June 1999.
- Dorothy Elizabeth Robling
Denning.
Cryptography and Data Security.
Addison-Wesley, 1983.
- Dieter Gollmann.
Computer Security.
John Wiley & Sons, New York, 1999.
- David Kahn.
The
Codebreakers: The Story of Secret Writing.
Scribner, New York, 1996.
- Bruce Schneier.
Applied Cryptography.
Wiley, New York, second edition, 1996.