Cryptography and System Security Michael Pramateftakis Room Z940 Tel: (089-289)23622 E-Mail: [email protected]

Cryptography and System Security


Michael PramateftakisRoom Z940

Tel: (089-289)23622E-Mail: [email protected]

Slide 2Cryptography and System Security

Organisatorisches• Vorlesung: Do., 12:30-14:00, N1170• Übung: Do., 14:00-14:45, N1170• Skript und Folien auf Englisch• Vorlesung, Diskussion und Prüfung auf Deutsch.

Hinweis: Ab 3.5.2004 neue Vorlesung (WA)

“Applied IT-Security”

Mo. 14:00-15:30, Hörsaal 0999, Vorl. auf Englischin Zusammenarbeit mit der Fraunhofer Gesellschaft (Dr. Stephan Spitz)


Lecture Overview

1. Motivation

2. Security Services and Mechanisms

3. Cryptographic Mechanisms

4. Discrete Algebra

5. Cryptographic Algorithms

6. Cryptographic Protocols

7. Security and the Internet

8. Smartcards and Security Applications


1. Motivation

Why cryptography?


Exemplary Scenario

Internet

CompanyNetwork

Other companies

Bank

Internet usersBrowsing, Orders…

Money, Payments

Business offers, contacts

Payment

Attacker


Further catchwords

• Hackers, Crackers, Script kiddies etc.

• Denial of Service

• Address spoofing

• Connection hijacking

• Firewall, NAT, Intrusion detection

• Spam

• E-mail faking

etc., etc., …


2. Security Services and Mechanisms

Cryptography’s most basic terms and definitions


Basic terms

• Security Services

• Security Mechanisms

• Cryptographic algorithms


Security Services

• Security services describe what a user requires from a security system:– Confidentiality (or Nondisclosure of Information)

– Authentication– Verifiability and Nonrepudiation– Anonymity– Access Control

Security services remedy threats.


Security Mechanisms and Algorithms

• Security Mechanisms:The technical and procedural means used to implement security services.(e.g. encryption provides confidentiality.)

• Algorithms:Concrete implementations of security mechanisms.(e.g. DES implements encryption)


Relations• Services, mechanisms and algorithms are

related to one another.• The relation is formally defined in the OSI

security architecture.• Security systems are designed and

parameterized based on these relations.

Services, Mechanisms and Algorithms are very basic and important terms!Distinguish between them correctly!


3. Cryptographic Mechanisms

Mechanism Details


Symmetric Encryption

f f-1c

k k

m m

Encryptionc= f(k,m)

Decryptionm= f-1(k,c)

Secure Environment Secure Environment

m: Plaintext messagec: Cipherk: Keyf: Encryption Functionf-1: Decryption Function (Inverse of f)

• Symmetric = Same key for encryption and decryption.• Key is secret, secure environment needed at sender and receiver.


Symmetric Encryption

Different kinds of symmetric encryption schemes:

• Characterwise with a key.<Output char.> = f (k,<Input char.>)

• Blockwise with a key.<Output block> = f (k,<Input block>)

• Symbolwise/bitwise with sequence of keysk: k1,k2,k3,…

• Blockwise with block chaining.


Perfect SecurityPrerequisites for perfect security:• Unlimited key length.• Truly random key sequence.• One-time pad.• |K| >= |C| >= |M|

Every message can be mapped to every cipher with a different key!

Thus, for a given cipher, every possible message is equiprobable, since a proper key can always be constructed! An attacker cannot make any assumptions about the message.


Perfect Security

M C

c1

c2

c3

c4

c5

m3

|M|=|C|=|K|Keys equiprobable

Messages equiprobable

k1

k5


Asymmetric Encryption

f fc

e d

m m

Public Encryptionc= fe(m)

Decryptionm= fd(c)

Secure Environment

m: Plaintext messagec: Ciphere: Encryption Keyd: Decryption Keyf: Asymmetric Function

• Asymmetric = Different keys for encryption and decryption.• Only decryption key is secret, secure environment needed only at receiver side.


Asymmetric Encryption

• Sender encrypts with receiver’s public key.

• Receiver decrypts with his own private key.

Thus, everybody can send encrypted messages to the receiver without needing to exchange a secret.


Digital Signature

• Creator of message signs with own private key.

• Everybody can verify the signature with the creator’s public key.

• The correspondence of the creator’s person to the respective public key must be reliably known.

• Signed messages are not encrypted.


4. Discrete Algebra

Basics of modulo-arithmetics


Discrete Algebra

Chapter Overview:

• Definition of modulo-n arithmetics

• Groups, Rings and Fields, Galois field

• Multiplicative-inverse elements in mod n

• Powers in mod n, related theorems

• Chinese remainder theorem

• Discrete logarithms


GroupsAn algebra on a finite or infinite set of elements

satisfying the following axioms:

1. The sum of 2 arbitrary elements a+b is defined and is an element of this set.

2. The sum is associative: (a+b)+c=a+(b+c)3. A null-element 0 exists, such that for any

element a holds a+0=a4. Every element a has an additive-inverse

element a-1 such that a+a-1=0

is called a Group. Addition and subtraction are defined for groups.


RingsIf all preceding axioms hold, plus:

5. The sum is commutative: a+b=b+a

6. The product of 2 arbitrary elements a·b is defined and is an element of this set.

7. The product is associative: (a·b)·c=a·(b·c)

8. The distributive law holds: a·(b+c)=a·b+a·c

we have a Ring. Multiplication is defined for a ring along addition and subtraction.


FieldsIf all preceding axioms hold, plus:

9. The product is commutative: a·b=b·a

10. There is an one-element 1, such that a·1=a holds for every element a

11. Every element a≠0 has a multiplicative inverse element a-1, such that a·a-1=1

we have a Field. Division is defined for a field along multiplication, addition and subtraction.


Arithmetics mod n• For arithmetics modulo-n axioms 1 to 10

are valid.• For arithmetics modulo-p, where p is a

prime number, axioms 1 to 11 are valid.

We’ll show that every element a[0,n-1] can be replaced by any element of the same remainder class Ra. When the axioms are proven, the calculus rules of algebra apply.


Multiplicative-inverse elements

• In modulo-n arithmetics, an element a≠0 with hcd(n,a)=1 has a multiplicative inverse element a-1.

• One way to find it would be a search of 1·a,2·a,3·a,… which is not practical for large modules.

• Another way is through the fact thathcd(n,a)=1=·n+·a

The above mod n yields 1=·a mod n and thus a-1=


Euler’s -function

The -function for a natural number n is defined as:

The quantity of numbers less than n, that are relatively prime to n

(n)=| {z[1,n-1] where hcd(n,z)=1} |

Since for a prime number p all numbers z<p are relatively prime to it:

(p)=p-1


Euler’s -function

In the case where n=p·q, p≠q prime:

(p·q)=(p-1)·(q-1)

because:

(p·q)=[p·q-1]-(p-1)-(q-1)=

(p·q)=(p-1)·(q-1)

Multiples of q Multiples of p

All possible numbers


Euler’s theorem

a(n)≡1 (mod n) for a|hcd(n,a)=1

This is formula (4.4.2) since (p)=p-1. The relation is also called

“Small theorem of Fermat”

ap-1≡1 (mod p), for a[1,p-1]


RSA Generalization(RSA: Rivest, Shamir, Adleman, inventors of the RSA algorithm)

Take Euler’s theorem, exponentiate with iN and multiply with a:

• a(n)≡1 (mod n)

• (a(n))i≡1i ai·(n)≡1 (mod n)

• ai·(n)+1≡a

valid for a[0,n-1] with n=p or n=p·q, p≠q


5. Cryptographic Algorithms

Symmetric and asymmetric encryption algorithms


Chapter Overview

• DES– DES-based MAC– DES-based cryptohash-function

• AES

• IDEA

• Block operation modes

• RSA

• El Gamal methods

• Certificates


DES

DES history:

• Developed by IBM

• Published in 1974

• ‘National Bureau of Standards’, today NIST, recognizes DES as a standard in 1977

• ‘American National Standards Institute’ recognizes DES as standard (ANSI X3.92) in 1981


DESDES attributes:• Symmetric algorithm• Block cipher: Message blocks of 64 bits.

Encryption to cipher blocks of 64 bits.• Key of 64 bits. Significant key length is 56 bits,

with 8 parity bits. |K|=256

DESKey k

64(56) bits

64 bits mi

64 bits ci

DES-1

64 bits mi

64 bits ci

Encryption Decryption


AES Encryption round

Data block di-1: 128 bits/16 bytes

Transformationsbased on byte-operations

- Substitution-Permutation

- Intermix

Data block di: 128 bits/16 bytes

AES key: 128/192/256 bits

Round keyderivation from AES key

10/12/14 depending onkey size

• No transformation box in initial round• No intermix for last round


AES Encryption roundTransformations:• Substitution

– Each byte is replaced by its multiplicative inverse value.

– Bytes are used to represent polynomials of grade less than 8, due to modular reduction with an irreducible polynomial of grade 8.

– Bytes are interpreted as elements of a finite field. Addition and multiplication are defined, but are not the same with the ones used for numbers.

• Permutation– Interchange of byte positions.

• Intermix– Matrix multiplication of bytes in the internal ‘State’.


AES Encryption round

Key derivation: With keylength 128 bits, each round requires 128 bits.

The key is split into 4 words of 4 bytes each.

w0 w1 w2 w3 w4 w5 w6 w7

AES key=key for round 0

Key for round 1

KT

…

wi=wi-1 XOR wi-4

When i mod 4=0, keytransformation (KT) isapplied.

KT involves byte shifts,substitutions and theaddition of a ‘roundconstant’, powers of 2in the GF(28).


Block operation modes

Electronic Codebook (ECB)

ci=BA(mi), mi=BA-1(ci)

BAk

m1

c1

BAk

m2

c2

BA-1k

c1

m1

BA-1k

c2

m2

Time

Sender: Encryption Receiver: Decryption

…

…

…

…


Block operation modesProperties of ECB• Every block is independent of other blocks.• Same plaintext is encrypted to same ciphertext.• Error propagation: If an error occurs in a cipher

block, only the respective plaintext block is affected.

• Synchronization: If the receiver cannot synchronize block boundaries, decryption is impossible.



Cipher Block Chaining (CBC)

ci=BA(mici-1), mi=BA-1(ci)ci-1, c0=IV

BAk

m1

c1

IV

BAk

m1

c1

Sender: Encryption

c1

BA-1k

m1

IV

c2

BA-1k

m2

Receiver: Decryption

…

… …

…


Block operation modesProperties of CBC• The initialization vector IV must be specified. It must not

be secret.• A cipher block depends on IV and all plaintext blocks

before it. Identical plaintexts are encrypted to different ciphertexts.

• The sequence of the blocks is significant. If the sequence changes, the cipher changes.

• Identical plaintext sequences are encrypted to identical cipher sequences, so different IVs should be used.

• Error propagation: If an error occurs in a cipher block, this and the next plaintext block cannot be decrypted.

• Synchronization: If synchronization is regained at this cipher block, the next plaintext block and all following ones can be decrypted.



Cipher Feedback (CFB)

ci=BA(ci-1)mi, mi=BA(ci-1)ci, c0=IV

ci-1

BAk

ci

mi

ci-1

BAk

mi

ci


Similar properties to CBC. Messages shorter than blocksize possible.



Output Feedback (OFB)

zi=BA(zi-1), ci=zimi, mi=zici, z0=IV

zi-1

BAk

ci

mi zi-1

BAk

mi

ci


Shorter messages than blocksize possible


Block operation modesOFB properties• State sequence zi does not depend on the

plaintext.• Corresponds to encryption with

pseudonoise, with a random number generator with nonlinear feedback.

• Error propagation: none.• Synchronization: If block boundary

synchronization is lost, the system must be resynchronized.


RSACreating an RSA key pair:

We will work in arithmetics modulo n, with:

n=p·q, p≠q prime

(n)=(p-1)·(q-1)

We select one of the keys randomly, e.g. e, with the following restrictions:

1<e<(n) and hcd(e,(n))=1

The other key is the multiplicative inverse of e modulo (n):

e·d≡1 mod (n)


RSA• A’s public key is thus: eA,n• A’s secret key is: dA

The prime factors of n cannot be found out. (Difficult task of factorization)

Euler’s theorem (ai·(n)+1) mod n=a yields with e·d≡1 mod (n):

(me·d) mod n=m for 0≤m<n

as i·(n)+1≡1 mod (n) as well.so, you encrypt a message by raising to one key

(here e) and decrypt by raising to the other (here d), modulo n.


RSA

Thus, the following formulas apply:

Encryption: c=(me) mod n

Decryption: (cd) mod n=(me)d mod n=m

Signature: s=(md) mod n

Verification: (se) mod n=(md)e mod n=m

The operations are computationally intensive. (e.g. 1000 times slower than IDEA)


RSA

Applications of RSA:

• Digital signature on message hash-values.

• Transmission of symmetric session keys in hybrid cryptography systems.

Due to high complexity, RSA is not useful for bulk data encryption.


Chinese Remainder Theorem

The Chinese remainder theorem calculates a number x mod n=p·q, when the remainders of x modulo p and modulo q are known.

Known: (x mod p) and (x mod q)

Result: (x mod n) with n=p·q


Chinese Remainder Theorem

The hcd of two natural numbers p and q with no common factors can be written as:

hcd(p,q)=1=·p+·q

where and can be calculated with the extended Euclidean algorithm.

With a=x mod p and b=x mod q known, we can deduce x=(b··p+a··q) mod n=p·q

See proof in script, p.38.


Chinese Remainder TheoremAuxiliary theorem:

When forming a remainder modulo p, no change is induced by forming the remainder modulo n=p·q. Thus:

y mod (p·q) ≡ y (mod p)

y mod (p·q) ≡ y (mod q)

Uniqueness:

The number x calculated by the chinese remainder theorem is unique in the interval [0, n-1]


El GamalAsymmetric methods for:• Digital Signature• Key exchangebased on discrete logarithms.

Key setup:• Publicly known prime number p and base g,

gGF(p)• Each participant selects private key d randomly

and calculates public key with e=gd mod p• Use of long modules is advised (>512 bits), so

that no discrete logarithms can be calculated.


El GamalDigital SignatureSigner:• Select for each signature a random number

r[1,p-1], hcd(p-1,r)=1• Calculate r -1 mod (p-1) with the extended

euclidean algorithm.• Calculate the message identification number

=gr mod p• Calculate the signature element s for the given

message from: d·+r·s≡m (mod p-1)

by solving to: s=((m-d·)·r -1) mod (p-1)• The signed message is (m, , s).


El Gamal

Verifier:

• Obtain signed message and public key of signer.

• Verify that gm≡e·s (mod p)

We’ll see why an attacker can’t forge a signature in the excercises.


El GamalKey exchangeModule p and base g are publicly known. Key pair

calculated as before (e=gd mod p).Sender:• Obtain receiver’s public key e• Select a random number a and calculate

=ga mod p• Calculate the secret session key k=ea mod p• Encrypt a message m with an arbitrary

symmetric method and k: c=f(k,m)• Transmit (,c) to receiver


El GamalReceiver:• Calculate the session key out of with the

private key d: k=(d) mod p• Decrypt the message: m=f-1(k,c)

Note that:• System corresponds to hybrid cryptography.• The receiver is not sure about the origin of ,

even though he is the only one who can find k out of it. An additional digital signature would ensure the origin of the message (,c).


6. Cryptographic Protocols


Chapter Overview

• Password methods

• Challenge-Response

• Diffie-Hellman

• Fiat-Shamir

• Authentication with digital signature and symmetric keys

• Needham-Shroeder and Kerberos protocols


Challenge-Response

A symmetric key k exists between A and B. A will prove that he has the key without transmitting it.

A B

Choose random rChallenge = r

Encrypt r withsecret key k Response = fk(r) Check if r = fk

-1(resp.)


Challenge-Response• The random number r may be used only once. It is a

‘nonce’.• Party B is sure that party A posesses the key after the

protocol is completed.• Party B is sure that A’s response is current, since the

nonce was not known before. This protects against replay attacks.

• Party A cannot be sure about the origin of the challenge.• The method can also work with a publicly known one-

way function, with the key involved: response=f(k,r)• The method can also work with asymmetric keys. The

response dA(r) can be verified with A’s public key.


Diffie-HellmanMethod for creation and exchange of a secret key over an

open channel. Based on discrete logarithms.

A prime number p and a base g are publicly known.

A B

Choose random number bCalculate =gb mod p

Choose random number aCalculate =ga mod p

Calculatek=b mod p=gab mod p

Calculatek=a mod p=gab mod p


Diffie-Hellman• After the protocol run, both parties can

create the same session key.• An attacker cannot calculate the same key

out of and , due to discrete logarithms.• Authenticity is not guaranteed by the

protocol. No party knows the identity of the other.

• a and b can be seen as private keys, and as public ones. El Gamal key exchange is similar to this protocol.


Fiat-Shamir

• Authentication protocol based on rounds.

• Authenticity is proven with a probability that increases with the number of rounds.

• Security is based on discrete square roots. The module consists of two primes p≠q, so calculation of the roots is only possible when the primes are known.

• A Trusted Third Party (Key-bank) is involved, that creates the user secrets.


Fiat-ShamirRole of the Key-bank

– Chooses the module n=p·q, p≠q, p and q prime. n is public, p and q are secret.

– For every subscriber, a random number z is chosen and an ID-mark is created with v=h(ID,z). v is the public information used for authentifying the subscriber.

– A secret s for the subscriber is calculated from s2·v≡1 (mod n). The keybank is the only instance who can do this, since it knows p and q.

– Each subscriber is given his own secret s and the corresponding information n, ID, z, v is made public.


Fiat-Shamir

Authentication round: A authenticates himself to B

A(knows sA)

B(knows vA)

Chooses random r,hcd(r,n)=1 and

calculates x=r2 mod n xchooses random bit bb

Calculates ydepending on b:

b=1: y=r·s mod nb=0: y=r mod n y Verifies for

b=1: y2 ≡ x/v mod nb=0: y2 ≡ x mod n


Fiat-Shamir

• An attacker (who doesn’t know s) has a chance of 50% to successfully complete an authentication round. In order to succeed, he must guess what b will be chosen by B (Proof in your script).

• With n rounds, the attacker’s success probability is pf=2-n

• Even though many rounds are needed, only very simple operations are involved in each round.


Authentication with digital signatures

We will consider:– One-way, one-pass authentication– One-way, two-pass authentication– Mutual two-pass authentication– Mutual three-pass authentication


One-way, one-pass authentication

A B

(tA, IDA, IDB)sigA

• Simplest case. A authentifies himself to B with a digital signature.• tA is a timestamp that shows B that the signature is current. Sequence numbers may also be used.• B can retrieve an appropriate certificate for A based on IDA.• The presence of IDB prevents any interceptors from using the same message with another party D.• The digital signature is calculated over all fields of the message.


One-way, two-pass authentication

A B

• B wants to check A’s identity. B starts the protocol.• The random number rB is chosen by B and signed by A. This is similar to the challenge-response method.• Timestamps are not needed, due to the fact that rB is current.• The random number rA protects against reusing an old rB.

(rB, IDB, IDA)

(rA, IDA, rB, IDB)sigA


Mutual two-pass authentication

A B

(tA, IDA, IDB)sigA

(tB, IDA, IDB)sigB

Authentication using timestamps


Mutual three-pass authentication

A B

(rB, IDB, IDA)

(rA, IDA, rB, IDB)sigA

(rA, IDA, IDB)sigB

Authentication with challenge-response


8. Chipcards


Chapter Overview

• Kinds of chipcards and applications

• Architecture and functionality of chipcards– Card architecture– Data transfer– Smartcard operating system– Security of chipcards

• Exemplary Chipcard Applications– GSM security functions


Kinds of Chipcards• Distinguished by functionality:

– Memory cards• Memory chip without protection of stored data.• Intelligent variant features access control logic• Application specific: Telephone cards, Insurance cards etc.

– Processor cards• Contain a microcontroller (CPU, memory, I/O)• Also called Smartcards• May contain cryptographic coprocessors• Smartcard operating systems exist• Very flexible

• Distinguished by data transfer methods:– Chipcards with contacts– Chipcards without contacts


Chipcard applications• Most important properties:

– Secure storage of secret data– Ability to perform cryptographic operations

• Real applications:– Telecom: Public card phone, GSM SIM– Banking: EC-card, Credit cards (EMV)– Health care: Insurance cards– Security: Access control, digital signature– Service: Pay-TV


Chipcard format

6,25 mm

85,6 mm

54 mm

16,4 mm


Chipcard pinout

C1

C2

C3

C4

C5

C6

C7

C8

C1: Power Supply (Vcc)C2: Reset input (RST)C3: Clock input (CLK)C4: n/cC5: Ground (GND)C6: Programming voltage (not used)C7: Data I/OC8: n/c


Card chip architecture

CPU RAM I/O

ROM EEPROM

Address-/Databus

C7

C1

C2

C3

C5

Vcc

RST

CLK

GND

To/From reader


Chipcard layer model

(Layer 7) Application

(Layer 2) Data Link

(Layer 1) Physical

e.g. ISO/IEC 7816-4, GSM, …

e.g. ISO/IEC 7816-3 T1

ISO/IEC 7816-3

Host and Card Reader Chipcard


Data transfer

Address1 byte

Control1 byte

Length1 byte

Data0..254 bytes

Checksum1..2 bytes

Layer 2 PDU (T1 protocol)

CLA INS P1 P2 Lc Data Le

Message Structure (Layer 7)

Command-PDU

Data SW1 SW2Response-PDU


Chipcard File system Hierarchy

MF

EF

DF

EF

DF

DF

DF

MF

EF

DF

Master File (root)

Elementary File (data)

Dedicated File (directory)


Chipcard File Structures

Linear Fixed Cyclic

Linear VariableTransparent


Chipcard commands• File Management

– Select File– Read/Write Record

• Authentication– Verify PIN– Get Challenge– Internal/External/Mutual Authentication

• Cryptography– Encrypt, Sign, MAC

• Counter Operations– Increase/Decrease


Security of Chipcards• Hardware Protection

– Address and data busses not accessible– Bus lines are scrambled many times– Same power consumption for all commands– Special coating against chemical attacks

• Data transfer protection– Encryption, MAC, Sequence counters

• Authentication between card and terminal– Internal, External, Mutual challenge-response

• Access Control– File access rights for every file imposed by OS

• Card holder authentication– PINs protected by fault presentation counters

Documents

Cryptography and System Security Michael Pramateftakis Room Z940 Tel: (089-289)23622 E-Mail: [email protected]