Cryptography

• Introduction

• Cryptosystems
− Substitution
− Transposition
− Symmetric
− Asymmetric

• Hash Functions

Seite 39 Prof. Dr. A. Lehmann | IT Security

Introduction
• Cryptography
− Encrypt/Decrypt messages
− In addition to confidentiality, this may include data integrity, non-
repudiation and authentication

• Cryptology = Cryptography + Cryptoanalysis (break cryptographic

techniques)

• Cryptography model

Encryption Key Decryption Key

Plaintext Encryption Ciphertext Ciphertext Decryption Plaintext

Method Method

Encryption Decryption

• Kerckhoffs‘ principle: Security should not depend on secrecy of the method

[Kapp]
Seite 40 Prof. Dr. A. Lehmann | IT Security
Steganography
• Steganography (hide secret message in non-secret message)

− Linguistical (Semagrams – messages hidden in images or writings)

Linguistical
Steganography

Semagrams Open Code

Jargon Code Concealment Cipher

Cue Null Cipher Grille Cipher

− Technical (e.g., invisible ink, miniaturization (microdots))

[Babi]
Seite 41 Prof. Dr. A. Lehmann | IT Security
Semagram Example

Where is the message hidden? [Kahn]

Seite 42 Prof. Dr. A. Lehmann | IT Security

Linguistical Steganography
• Open Code
− Message hidden in open transmitted harmless message, e.g. coughing in
quiz show (Who Wants to Be a Millionaire?)

− Cue: Term, phrase or sentence with previously agreed meaning, e.g.

HIGASHI NO KAZE AME in Japanese weather forecast – twice – means
war with USA

• Jargon
− Special languages or special signs, e.g. weed, Mary Jane, purple haze,
snow

• Concealment Cipher
− Null Cipher, e.g. a letter after each punctuation mark
− Grille Cipher, e.g. hidden message must be written with a mask

[Babi]
Seite 43 Prof. Dr. A. Lehmann | IT Security
Technical Steganography
• Methods to conceal a secret message, such as the use of invisible ink,
microdots, and shaved heads

• Steganography in images
− E.g. Least Significant Bits

• Code message in redundant Bits

R G B
0010 0111 1110 1001 1100 1000
0010 0111 1100 1000 1110 1001
1100 1001 0010 0111 1110 1001
Hidden Message 1000 0011

0010 0111 1110 1000 1100 1000

0010 0110 1100 1000 1110 1000
1100 1001 0010 0111 1110 1001

• Steganography leads to small changes within pictures

[Ecke]
Seite 44 Prof. Dr. A. Lehmann | IT Security
Modifications in Image
Histogram:

original steganography

Seite 45 Prof. Dr. A. Lehmann | IT Security

Encryption Methods

• Substitution Cipher
− Substitute symbol or group of symbols by other symbol or group of
symbols, order is preserved

• Transposition Cipher
− Retain symbols but change order

• Product Cipher
− Combination of the above

• Also a basis for modern cryptographic methods, applied to Bits and Bytes

[Kapp]
Seite 46 Prof. Dr. A. Lehmann | IT Security
Substitution Cipher
• Example: Caesar Cipher

• Shift letters in alphabet order modulo n

• E.g. n = 7

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
H I J K L M N O P Q R S T U V W X Y Z A B C D E F G

• Plaintext: KNOWLEDGE IS POWER

• Ciphertext: RUVDSLKNL PZ WVDLY

[Kapp]
Seite 47 Prof. Dr. A. Lehmann | IT Security
Transposition Cipher
• Example: Scytale Cipher

• Letters are reordered, original letters are preserved

• An early Greek transposition cipher a strip of paper was wound round a staff

B I R T H D A Y
2 5 6 7 4 3 1 8
K N O W L E D G
E I S P O W E R

• Plaintext: KNOWLEDGE IS POWER

• Ciphertext: DKELNOWG EEWOISPR

[Kapp]
Seite 48 Prof. Dr. A. Lehmann | IT Security
Crypto Analysis
• Key Space is crucial

• Brute Force Attacks: try all possible keys

• Statistical properties of cipher text

• In general:
− Ciphertext-Only-Attack

− Known-Plaintext-Attack

− Chosen-Plaintext-Attack

− Chosen-Ciphertext-Attack

[Kapp]
Seite 49 Prof. Dr. A. Lehmann | IT Security
Brute Force Attack
• If there are finitly many keys, try until one fits

• How long does it take?

• Suppose computer can test 1 million keys per second

Binary Key Size No. of Keys Time required to try
all
16 Bit 65535 ≈ 6.6 * 104 0.07 seconds
32 Bit 4294967296 ≈ 4.3 * 109 72 minutes
64 Bit ≈ 1.8 * 1019 805675 years
128 Bit ≈ 3.4 * 1038 1.4 * 1028 years
256 Bit ≈ 1.2 * 1077 5 * 1063 years
n Bit 2n 2n/(3.1536 * 1013)
years

[Kapp]
Seite 50 Prof. Dr. A. Lehmann | IT Security
Security of Encryption Schemes
• Encryption keys ought to be long. Is this sufficient?

• Example: monoalphabetic substitution (scrambling of letters)

• Number of different keys: 26! = [Link].[Link].000

• Scrambled text
rqjenjmanjvcqjcxwnmjhmxfwrwjujkjvjfrcqrcberlrxdbajlrb
cbfrcqrcbpxenawxaqjerwpqrburybmaryyrwpfrcqcqnfxambxor
wcnayxbrcrxwjwmwduurorljcrxwxwnmjharpqccqnanrwjujkjvj
urccunkujltkxhbjwmkujltpraubfruuknjkuncxsxrwqjwmbfrcq
urccunfqrcnkxhbjwmfqrcnpraubjbbrbcnabjwmkaxcqnabrqjen
jmanjvcxmjhrqjenjmanjvcqjcxwnmjhnenahejuunhbqjuuknngj
ucnmjwmnenahqruujwmvxdwcjrwbqjuuknvjmnuxfcqnaxdpqyujl
nbfruuknvjmnyujrwjwmcqnlaxxtnmyujlnbfruuknvjmnbcajrpq
cjwmcqnpuxahxocqnuxambqjuuknanenjunmjwmjuuounbqbqjuub
nnrccxpncqna
[Kapp]
Seite 51 Prof. Dr. A. Lehmann | IT Security
Statistical Analysis
Letter Relative
Frequency
in English
Language
A 8.167 %
B 1.492 %
C 2.782 %
D 4.253 %
E 12.702 %
F 2.228 %
G 2.015 %
H 6.094 %
I 6.966 %
J 0.153 %
K 0.772 %
L 4.025 %
M 2.406 %
N 6.749 %
O 7.507 %
P 1.929 %
rqjenjmanjvcqjcxwnmjhmxfwrwjujkjvjf
Q 0.095 % rcqrcberlrxdbajlrbcbfrcqrcbpxenawxa
R 5.987 % qjerwpqrburybmaryyrwpfrcqcqnfxambxo
S 6.327 % rwcnayxbrcrxwjwmwduurorljcrxwxwnmjh
T 9.056 % arpqccqnanrwjujkjvjurccunkujltkxhbj
wmkujltpraubfruuknjkuncxsxrwqjwmbfr
U 2.758 % cqurccunfqrcnkxhbjwmfqrcnpraubjbbrb
V 0.978 % cnabjwmkaxcqnabrqjenjmanjvcxmjhrqje
W 2.360 % njmanjvcqjcxwnmjhnenahejuunhbqjuukn n=9
X 0.150 % ngjucnmjwmnenahqruujwmvxdwcjrwbqjuu
knvjmnuxfcqnaxdpqyujlnbfruuknvjmnyu
Y 1.974 % jrwjwmcqnlaxxtnmyujlnbfruuknvjmnbca
Z 0.074 % jrpqcjwmcqnpuxahxocqnuxambqjuuknane
njunmjwmjuuounbqbqjuubnnrccxpncqna

Seite 52 Prof. Dr. A. Lehmann | IT Security

Security of Encryption Schemes
• Original text:
ihaveadreamthatonedaydowninalabamawithitsviciousracis
tswithitsgovernorhavinghislipsdrippingwiththewordsofi
nterpositionandnullificationonedayrightthereinalabama
littleblackboysandblackgirlswillbeabletojoinhandswith
littlewhiteboysandwhitegirlsassistersandbrothersihave
adreamtodayihaveadreamthatonedayeveryvalleyshallbeexa
ltedandeveryhillandmountainshallbemadelowtheroughplac
eswillbemadeplainandthecrookedplaceswillbemadestraigh
tandthegloryofthelordshallberevealedandallfleshshalls
eeittogether

• Blank characters? Missing punctuation marks?

i have a dream that one day down in alabama with its
vicious racists with its governor having his lips
dripping with the words of interposition and
nullification one day right there in alabama little
black boys and black girls will be able to join hands
with little white boys and white girls as sisters and …
Seite 53 Prof. Dr. A. Lehmann | IT Security
One-Time-Pad
• If used correctly, “unbreakable" encryption

• Key
− As long as the plaintext (minimum)
− Truly random
− Never reused

• XOR-conjunction of plaintext and key

• Limitations:
− Key management extremely expensive
+ Demand for random numbers is huge
+ Key exchange must be secure

[Ecke]
Seite 54 Prof. Dr. A. Lehmann | IT Security
Cryptographical Methods
• Symmetrical Method (Secret-Key)

• Asymmetrical Method (Public Key)

Message Encryption Decryption

Encryption Decryption
Sender Key (e) Key (d) Receiver

Symmetric: e=d secret! e.g. DES, AES

Asymmetric: e≠d e.g. RSA, ElGamal

public private

[Ecke]
Seite 55 Prof. Dr. A. Lehmann | IT Security
Symmetric Cipher Model
• Plaintext block of size m is translated into ciphertext block using the key of
size n Key (Size n)

Plaintext Encryption Ciphertext Ciphertext Decryption Plaintext

(Size m) Method (Size m) (Size m) Method (Size m)

Encryption Decryption
• DES (Data Encryption Standard):
− Block size 64 Bit
− Key size 56 Bit

• AES (Advanced Encryption Standard)

• Both can be implemented easily in hardware

[Ecke]
Seite 56 Prof. Dr. A. Lehmann | IT Security
Symmetric Encryption Schemes

Method DES 3-DES AES-128 AES-192 AES-256

Key Length 56 Bit 112 Bit 128 Bit 192 Bit 256 Bit
Block Size 64 Bit 64 Bit 128 Bit 128 Bit 128 Bit

[Ecke]
Seite 57 Prof. Dr. A. Lehmann | IT Security
Block Cipher
• Plaintext is split into blocks of fixed length

• Block by block encryption

• Same key for each block

Plaintext

Block 1 Block 2 Block n

Encryption Encryption Encryption

C1 C2 … Cn

Decryption Decryption Decryption

Block 1 Block 2 Block n

Plaintext
[Ecke]
Seite 58 Prof. Dr. A. Lehmann | IT Security
Block Cipher Modes
• ECB (Electronic Code Book)

• Block by block encryption

• Same plaintext blocks result in same ciphertext blocks

• Problems:
− Reload blocks
− Change order
− Remove block

[Ecke]
Seite 59 Prof. Dr. A. Lehmann | IT Security
Block Cipher Modes
• CBC (Cipher Block Chaining)

• Conjunction with previous ciphertext block

• Initial value is initialization vector (IV)

• Same plaintext blocks result in different ciphertext blocks

Plaintext Plaintext Plaintext

Cn C n+1 C n+2
Block Block Block

IV

Enc Enc Enc Dec Dec Dec

IV

Plaintext Plaintext Plaintext

Cn C n+1 C n +2
Block Block Block

[Ecke]
Seite 60 Prof. Dr. A. Lehmann | IT Security
Further Cipher Modes
• OFB (Output Feedback) and CFB (Cipher Feedback)

• Both use block cipher as stream cipher

• OFB generates keystream blocks, which are then XORed with the plaintext
blocks to get the ciphertext
Block Block Block
IV
Cipher Cipher Cipher

Encryption Plaintext Plaintext Plaintext

Ciphertext Ciphertext Ciphertext

Block Block Block

IV
Cipher Cipher Cipher

Decryption
Ciphertext Ciphertext Ciphertext

Plaintext Plaintext Plaintext

[Ecke]
Seite 61 Prof. Dr. A. Lehmann | IT Security
Further Cipher Modes
• CTR (Counter), e.g. AES

Encryption
Nonce Nonce Nonce
Block Block Block
+ + +
Cipher Cipher Cipher
Ctr Ctr+1 Ctr+n

…
Plaintext Plaintext Plaintext

Ciphertext Ciphertext Ciphertext

Decryption
Nonce Nonce Nonce
Block Block Block
+ + +
Cipher Cipher Cipher
Ctr Ctr+1 Ctr+n
…
Ciphertext Ciphertext Ciphertext

Plaintext Plaintext Plaintext

[Ecke]
Seite 62 Prof. Dr. A. Lehmann | IT Security
Asymmetric Encryption
• Key pair: private and public key

• Based on one-way function

Recipient’s Recipient’s
Public Key Private Key

Plaintext Encryption Ciphertext Ciphertext Decryption Plaintext

Method Method

Encryption Decryption
Sender Recipient

[Ecke]
Seite 63 Prof. Dr. A. Lehmann | IT Security
Public-Key Methods
• Public key encrypted messages can only be decrypted with the private key

• Knowledge of public key → no conclusion to private key

• Public key can be distributed, also via insecure channels

• Significantly longer keys than symmetrical encryption

• Based on mathematics Sender Recipient

− Diffie-Hellman (DH) – discrete logarithm
− ElGamal – elliptic curves
− RSA – product of primes

[Kapp]
Seite 64 Prof. Dr. A. Lehmann | IT Security
Example: RSA
• RSA, developed by Rivest, Shamir, Adleman

1. Choose two distinct prime numbers p and q

2. Compute n = p*q (Modulus)

3. Compute λ(n), where λ is Carmichael's totient

function.

4. Choose an integer e such that 1 < e < λ(n)

and gcd(e, λ(n)) = 1; that is, e and λ(n) are [Link]

coprime

5. Determine d as d = e−1 (mod λ(n)); that is, d is the modular multiplicative inverse of e
modulo λ(n)

[Reis]
Seite 65 Prof. Dr. A. Lehmann | IT Security
Comparison

Symmetric Asymmetric
Key exchange Secure channel is Public key
necessary
Key length Mostly 128 or 256 Bit Mostly 2048 – 8192 Bit
Performance Fast, easily implementable 100 – 1000 times slower
in hardware or software

[Reis]
Seite 66 Prof. Dr. A. Lehmann | IT Security
Hybrid Methods
• First, utilize public key method to transmit a session key for symmetrical
encryption

• Then use symmetric encryption

A B

[Kapp]
Seite 67 Prof. Dr. A. Lehmann | IT Security
Hash Functions
• One-way Hash, not injective → may have collision

• Proof of integrity

• Therefore, unique hash values for data

• If data changes, hash value also changes

− Problem is possible collision

• Use of hashed passwords, e.g. Unix

• Example: Software distribution

[Reis]
Seite 68 Prof. Dr. A. Lehmann | IT Security
Hash Functions
• Based on compression function

M1 M2 Mn + Padding

IV G G … G Hash Value

• Message m is split into Mi blocks of fixed length y

• Initialized with an initial vector

• Last block Mn may be filled to length y (Padding)

[Ecke]
Seite 69 Prof. Dr. A. Lehmann | IT Security
Example Hash Function
• Message Digest Algorithm 5 (MD5)

• Length is fixed (128 Bits), independent of input

• Only 2128 different hash values → many existing files with same hash value

• Two very similar inputs should not result in same hash value (collision
resistance)

[Reis]
Seite 70 Prof. Dr. A. Lehmann | IT Security
Message Authentication Code (MAC)
• Data integrity and authenticity of source of data

• Hash function with key (pre-shared)

Sender Receiver
Message Message

Message
MAC MAC MAC
Key Key
Algorithm Algorithm

MAC MAC =? MAC

• Problem: initial vector often is equal (e.g. MD5) → collisions

[Ecke]
Seite 71 Prof. Dr. A. Lehmann | IT Security
HMAC Method
• Uses key to vary initial vector

• Standardized by IETF RFC 2104

• Uses hash function H (compression function block size B) and a secret key K

• ipad = 0x36 (B times), opad = 0x5c (B times)

• Can be used with any one-way hash function

[Reis]
Seite 72 Prof. Dr. A. Lehmann | IT Security