ET1206/Lectures

From FUKTwiki

Contents 1 2007-11-05 1.1 3.1 Kryptering 1.1.1 Kerckhoffs' principle 1.2 3.2 Autentisering, verifiering 1.3 3.3 Public key encryption (publika nycklar) 1.4 3.4 Digitala signaturer 2 2007-11-06 2.1 Publika nycklar 2.2 3.5 PKI, Public Key Infrastructure 2.3 3.6 Attacker 2.3.1 1 Ciphertext only 2.3.2 2 Known plain text 2.3.3 3 Chosen plain text 2.3.4 4 Chosen Ciphertext 2.3.5 Collision attacks 2.4 4 Blockkryptering 2.5 4.3 The Ideal block cipher 2.6 4.5 Real block ciphers 2.6.1 DES 3 2007-11-07 3.1 4 3.2 AES 3.2.1 Lineraritet 3.2.2 Subbytes 3.2.3 Shiftrows 3.2.4 Mix Columns 3.2.5 Add Round Key 3.2.6 Fördel mot DES 3.3 Serpent 3.4 Twofish 3.5 Attacker 3.5.1 XSL - equation solving attacks 3.5.2 Which block cipher should I use? 3.5.3 Vilken nyckelstorlek ska jag använda? 4 2007-11-12 4.1 5 Block Cipher Modes 4.2 Kollisionsrisk för två Ci block 4.3 5.1 Padding 4.3.1 Schema 4.3.2 Schema 2 4.4 5.2 ECB – Electronic Code Book 4.4.1 XOR 4.5 5.3 CBC – Cipher Block Chaining 4.5.1 1 Fix IV eller C0 4.5.2 2 Counter IV 4.5.3 3 Random IV 5 2007-11-13 5.1 CBC – Cipher Block Chaining (forts.) 5.1.1 Nonce generated IV 5.2 Stream Ciphers 5.2.1 OFB – Output Feedback Mode 5.2.2 CTR – Counter Mode 6 2007-11-14 6.1 CTR – Counter Mode (forts.) 6.2 OFB 6.2.1 Exempel 6.3 5.8 Läckor 6.3.1 Risk för kollision 6.4 6 Hashfunktioner (kryptografiska hash functions) 6.5 6.1 Säkerhet med hashfunktioner 6.5.1 Praktiska hashfunktioner 6.5.1.1 Fördelar med iterativa hashfunktioner 6.5.1.2 MD5 6.5.1.3 SHA-1 7 2007-11-19 7.1 6 Hashfunktioner 7.1.1 Iterativa hashfunktioner 7.2 6.3 Svagheter hos hashfunktioner 7.2.1 Length extensions 7.3 6.3.2 Partial message collision 7.3.1 Fix av svagheterna 7.4 7 Message Authentication Codes (MAC) 7.5 7.4 CBC-MAC 7.6 7.5 HMAC (Hash MAC) 7.7 7.6 UMAC 8 2007-11-20 8.1 8 The Secure Channel 8.1.1 Trafikanalys 8.2 8.2 Ordningen på kryptering och verifiering 8.2.1 Kryptering först 8.2.2 Autentifiering (verifiering) först 8.3 8.3 Hur sätter vi upp en säker kanal? 8.4 8.3.1 Meddelandenumrering 8.4.1 Authentication (verifieringen) 8.4.2 Krypteringen 9 2007-11-21 9.1 10 Generera slumptal 9.2 10.1.2 Pseudorandom data (PRNG) 9.3 10.3 Fortuna 9.4 10.4 Generatorn ska vara en CTR mode 9.5 10.4.1 Initialisering 9.6 10.4.2 Reseed 9.7 10.4.3 Generate Blocks 9.8 10.5 Accumulator 9.9 10.5.2 Pool 10 2007-11-26 10.1 11 Primtal 10.2 11.3 Moduloräkning med primtal 10.2.1 Addition och Subtraktion 10.2.2 Finita fält 10.3 GCD (Största gemensamma delare ) 11 2007-11-27 11.1 12.1 11.2 Grupper och undergrupper 11.3 Diffie och Hellman 11.4 12.2 11.4.1 Alice 11.4.2 Bob 12 2007-12-03 13 2007-12-04 13.1 Diffie-Hellman 13.1.1 Alice 13.1.2 Bob 13.2 12.3 Man in the middle 13.3 12.4 Fallgropar 13.4 12.5 Safe Primes 13.4.1 Problem med den fulla gruppen 13.4.2 Algoritm för att använda ett säkert primtal (p,q,g) 14 2007-12-10 14.1 13 RSA 14.1.1 Diffie-Hellman 14.1.2 RSA 14.2 13.2 CRT – The Chinese Remainder Theorem 14.3 13.2.1 Garner’s Formula 14.3.1 Exempel 15 2007-12-11 15.1 RSA 15.1.1 Tentauppgift kan vara 15.1.1.1 Svar: 15.1.2 Signera ett meddelande 15.2 13.6 15.3 13.4.3 Hemliga nycklar 15.3.1 1 15.3.2 2 15.4 Uppgift 16 2007-12-17 16.1 14 Inledning till kryptografiska protokoll 16.1.1 A. Roller 16.1.2 B. Förtroende 16.2 14.5 16.2.1 C. Meddelande, steg 16.2.2 Transportlagret 16.2.3 Protokoll och meddelandeidentifiering 16.3 14.5 Meddelandekryptering 16.3.1 Felhantering 16.4 15 Key negotiation protocols 16.5 15.2 DH + added authentication 16.5.1 Problem 16.6 Verifiering: Hur ska vi välja m? 16.6.1 Alice 16.6.2 Bob 16.6.3 Alice 16.6.4 Problem 17 2007-12-18 17.1 17 The Clock 17.2 18 Key Servers 17.3 18.2 Kerberos 17.4 18.3 Secure Connection 17.5 19 Public Key Infrastructure (PKI) 17.6 19.2 Universell PKI 17.7 19.3 Multilevelcertificat 17.8 19.4 Bäst före-datum

[edit] 2007-11-05

[edit] 3.1 Kryptering

• ke = hemlig nyckel
• m = meddelande
• c = krypterad text
• m → (ke,m) → c
• c = E (ke,m) ⇒ c send
• E = krypterings funktioner (algoritmer)
• Rx ← In = c
• m = D (ke, c)
• D = dekrypterings funktion
• resultat m.

Exempel: "sjörövarspråket" m = Ronneby ke = o krypteringsfunktionen = E = ett ke skall införas efter varje konsonant och konsonanten före varje ke skall repeteras efter varje ke.

c = rorononnoneboby

skicka c

dekrypteringsfunktin = D = för varje hittat ke, kolla om det är en konsonant före och efter varje ke. om de är lika, tag bort första + ke

resultat = m = D("o", "roronnoneboby") = Ronneby

[edit] Kerckhoffs' principle

The security of the encryption scheme depends on the secrecy of ke, not on how public the information of how E or D works.

Fortfarande möjligt

• att byta hela meddelandet
• ta bort meddelandet
• ändra ordningen

[edit] 3.2 Autentisering, verifiering

• ka = Authentication key
• Tx ← m = medelande
• a = MAC = message authentication code
• a = MAC = h(ka,m)

Send: a,m

Rx ← In a,m

beräkna a

a = h(ka,m)

Resultat: Mottagit a och beräknat a.

[edit] 3.3 Public key encryption (publika nycklar)

Problem: Hur ska vi dela med oss nycklarna på ett säkert sätt?

2-persons	byt nycklar, snigelpost
3	3 byten
4	6 byten
1000	byten

Lösning: använd publika nycklar

• Bob generates 2 nycklar
• Hemlig nyckel k_sbob
• Publik nyckel k_pbob

k_pbob publiceras av Bob

Alice ska skicka till meddelande till Bob.

• Hämta publika nyckeln k_pbob
• Kryptera meddelandet C = E(k_pbob,m)

Bob får meddelandet

• Använder sin hemliga nyckel k_sbob
• Dekryptera meddelandet m = D(k_sbob,c)

---

• 
• k_pbob kan inte i praktiken räknas fram från k_pbob
• Enklare för större grupper att kommunicera säkert

[edit] 3.4 Digitala signaturer

Alice genererar två nycklar. k_palice k_salice

Alice genererar sedan en signatur.

• Genom att använda hemliga nyckeln k_salice

S = σ(k_salice,m)

Alice skickar S, m (och sin publika nyckel k_palice))

Bob tar emot S, m

• Använder publika nyckeln k_palice
• Verifierar signaturen S = v(k_palice,m)
• Jämför beräknad signatur med mottagen

[edit] 2007-11-06

kryptering, hemlig nyckel

k_e C = E(k_e,m)

[edit] Publika nycklar

k_pbob,k_sbob

C = E(k_pbob,m)

m = D(k_sbob,c)

[edit] 3.5 PKI, Public Key Infrastructure

Problem: hur vet vi att k_pbob verkligen tillhör Bob?

Lösning: CA = Certified[sic] Authority

CA använder en digital signatur för att säkerställa att verkligen k_pbob tillhör Bob.

Certifikat

[edit] 3.6 Attacker

[edit] 1 Ciphertext only

Attackera den krypterade texten

[edit] 2 Known plain text

Attackera och försök komma åt nyckeln

Exempel: Du kommer åt både c, m
någon skickar ett mail där du är en av mottagarna.

[edit] 3 Chosen plain text

Attackera och försök få nyckeln.

Exempel: Jag skickar meddelande till Alice som forwardar krypterat.

[edit] 4 Chosen Ciphertext

?

[edit] Collision attacks

• Birthday attack

23 personer P(två har samma födelsedag) > 0,5

365 dagar på ett år ⇒

Attacker som grundar sig på att kopior på nycklar och meddelande uppkommer fortare än man tror.

[edit] 4 Blockkryptering

Block cipher: krypteringsfunktion för en fix blockstorlek, t.ex. 128 bitar.

• Blockstorlek av originaltext och krypterad text lika stora.
• Storleken av nyckeln är oftast 128 eller 256 bitar

• C = E(K,p)
• P = D(K,c)
• E(K,p) = E_k(p) krypteringsfunktion publik

If P > 128, use block cipher mode (kapitel 5).

E_k(p)

P	c
00	11
01	00
10	01
11	10

D_k(c)

c	p
00	01
01	10
10	11
11	00

• En tabell för varje nyckel

Block length = 2^{(block size)} = 2² = 4rows

Verkligheten:

Attacker: för att få bra resultat använd chosen plain text

E_k(p)

P	c1	c2
00	11	00
01	00	11
10	01	01
11	10	10

[edit] 4.3 The Ideal block cipher

För varje ny nyckel: slumpmässig look-up-tabell

[edit] 4.5 Real block ciphers

• Hitta ej på er egen algoritm

Egenskaper:

• Använd XOR för att addera på nyckeln
• Använd S-box för att lägga till non-linearity
• Vänd och vrid på bitarna för att skapa oordning (mål: En liten ändring i klartexten ska göra stor ändring i kryptotexten)
• Kör algoritmen flera "rounds"

[edit] DES

Data Encryption Standard (1970-talet)

(Gammal, obsolete)

Nyckelstorlek = 56 bitar

Blockstorlek = 64 bitar

64 bitar, 32L och 32H.

Runda 0:

• L₀ = 32L
• R₀ = 32R

Runda 1:

• 
• L₁ = R₀

Funktion F

1. Expandera R från 32 → 48 bitar
2. XOR med nyckeln k_i som är 48 bitar och olika för varje rounds.
3. The S-box: 8 st
4. Blanda de 32 bitarna
5. Klart för en runda till

Denna struktur kallas Feistel construction

Nycklar så väljs k_j (48 bitar) ut på ett speciellt sätt från originalnyckeln på 56 bitar.

[edit] 2007-11-07

[edit] 4

Blockstorlek 128 in ⇒ 128 bitar ut

00	01
01	11
10	00
11	10

2¹²⁸

DES (Data encryption Standard)

key 56

Blocks = 64

3DES

key 128

Nackdelar:

• Fortfarande blockstorlek 64
• Långsam
• Vad händer om k = 0 (alla bitar 0)?

Fördel:

• Använder samma hårdvara för kryptering som dekryptering

[edit] AES

NIST (National Institute of Standards and Technology)

AES (Advanced Encryption Standard)

krav:

• Blockstorlek 128 bitar
• Nyckelstorlek: 128, 192 eller 256

15 förslag ⇒ 5 finalister

2001 ⇒ Rijndael

Rijndael var det möjligt att variera blockstorleken [128], 192, 256

{{subst:AES}}

[edit] Lineraritet

[edit] Subbytes

8 bitar → Sbox → 8 bitar

Alla S-boxar är identiska

[edit] Shiftrows

Byter "bytes" i samma rad plats genom att skifta 1-3 positioner beroende på rad

[edit] Mix Columns

Varje kolumn i blocket multipliceras med en förutbestämd matris så att varje "byte" får ett nytt värde.

[edit] Add Round Key

Xor med data och nyckel (permutation av originalnyckeln; olika varje runda).

AES	rounds
128	9
192	12
256	14

[edit] Fördel mot DES

• Större nyckel
• Större blockstorlek
• AES är mindre komplex än 3DES

[edit] Serpent

Alternativ till AES

Säkrare än AES ⇒ mer komplex

[edit] Twofish

Mellanting mellan AES och Serpent

Snabbt att kryptera, långsamt att byta nyckel och i början med ny nyckel

[edit] Attacker

[edit] XSL - equation solving attacks

Exempel: AES 128 blir 8000 ekvationer med 16000 variabler

[edit] Which block cipher should I use?

1. AES
   Standard
2. Serpent
   Mycket säker men långsam
3. Twofish
   Är säker och snabb

[edit] Vilken nyckelstorlek ska jag använda?

Minst betydelse
⋮
128 bitar	Bra nog, men se upp med collision attacks
⋮
256 bitar	AES 256 är mycket långsammare än AES 128
⋮
Mest betydelse

Rule: For a security level of n bits, every cryptographic value should be at least 2n bits long.

[edit] 2007-11-12

[edit] 5 Block Cipher Modes

Det är problem om två krypterade block C_i är lika.

C_i = E(K,P_i)

C_k = E(K,P_k)

C_i = C_k ⇒ P_i = P_k, vilket blir mycket lättare att knäcka.

[edit] Kollisionsrisk för två C_i block

[128 bitar] ↔ [128 bitar]

Sannolikheten att dessa två block är lika är .

Om vi skickar M block över kanalen, vad är sannolikheten att två av dessa är lika?

meddelandet är längre än 1 block (oftast 128 bitar – 16 ”byte”).

[edit] 5.1 Padding

Bara addera nollor på slutet är ingen bra idé. Det är svårt att veta hur många som ska tas bort vid dekrypteringen.

Vi behöver något padding-schema.

P = plaintext

l(P) = längden av meddelandet

b = blockstorleken i ”bytes”

[edit] Schema

"Meddelande" + bin(128) + bin(0)+ upp till b ”bytes”.

Exempel:

"AB" ⇒ (om b = 4) ⇒ "AB", bin(128), 0

Detta fungerar inte där ”byten” 128 kan förekomma.

[edit] Schema 2

Beräkna hur många padding-”bytes” som behövs för att få ett fullt block.

Lägg till meddelandet med n ”bytes” av värde bin(n).

Exempel: ”AB” → ”AB” + bin(2) + bin(2)

[edit] 5.2 ECB – Electronic Code Book

(Ska ej användas.)

C_i = E(K,P_i) för

Om två P_i är lika ⇒ två P_i lika.

Inte bra för en attack.

[edit] 5.3 CBC – Cipher Block Chaining

Löser problemet med att om två C_i = C_k ⇒ P_i = P_k

Problem? Hur hittar vi C₀ = Initialization Vector, IV?

[edit] 1 Fix IV eller C₀

Om flera meddelanden har samma start:

P₁ kommer vara samma ⇒ C₁ kommer att vara samma.

Inte bra ur en attacksynpunkt.

[edit] 2 Counter IV

IV = 0 för första meddelandet, IV = 1 för andra, o.s.v.

Om skillnaderna är små i meddelandet är det risk att XOR inte ger så stora skillnader.

[edit] 3 Random IV

Slumpmässig C₀, mottagaren måste också veta samma C₀.

C₀ = random block value

Dekryptering:

Nackdel:

• Slumpgenerator behövs
• Vår krypterade text förlängs med ett block

[edit] 2007-11-13

[edit] CBC – Cipher Block Chaining (forts.)

[edit] Nonce generated IV

Number used only once

Så att C₀ får bara användas en gång med varje nyckel K.

(Varje meddelande har oftast redan ett löpnummer.)

1. Konstruera ett nonce (128 bitar)
2. Kryptera E(k,nonce) = C₀
3. Kryptera hela meddelandet genom att använda CBC
4. Dekryptera meddelandet och kontrollera nonce

Exempel:

p = "HEJ"

blockstorlek två ”bytes”

CBC

C₀ = random = 0000111100001111

k = 0101010101010101

P₁ = (ASCII(H) = 72, ASCII(E) = 69)

P₂ = (ASCII(J) = 74, padding)

ASCII	Dec	Bin
H	72	01001000
E	69	01000101
J	74	01001010

Padding = 128

P₁ = 0100100001000101

P₂ = 0100101010000000

= E(K,0100011101001010) = 0001001000011111

= E(K,0101100010011111) = 0000110111001010

Dekryptering:

= D(k,0001110100010000) = 0100100001000101

= D(k,0001111111010101) = 0100101010000000

[edit] Stream Ciphers

Vi använder inte blockkrypteringen på meddelandet P₁, utan vi använder blockkrypteringen för att skapa en pseudorandom sekvens av bitar som vi sedan kör XOR på meddelandet

[edit] OFB – Output Feedback Mode

K₀ = IV

IV skapas enligt ovan

k_i = E(K,k_{i − 1}) för

IV genereras och skickas.

Fördelar: kryptering samma som dekryptering

Behöver ingen padding. ”Bra för små meddelanden”, står det i boken.

Nackdel: Om man använder samma IV (K₀) så kommer två meddelanden att kodas med samma ström.

Två meddelanden p och p' kodas med samma ström k_i ⇒ två krypton C och C'

Attackeraren gör följande:

[edit] CTR – Counter Mode

för

Där Nonce är unik för varje meddelande

i är blocknummer i meddelandet

Typiskt:

48 bitar	meddelandenummer
16 bitar	nonce
64 bitar	för räknaren i

[edit] 2007-11-14

[edit] CTR – Counter Mode (forts.)

[edit] OFB

K₀ = IV

K_i = E(K,k_{i − 1})

[edit] Exempel

Blockstorlek 8 bitar, K = 3, nonce = 7, i = 0

i		ki	ki binärt
i=0		10	00001010
i=1		4	00000100
i=2		9	00001001

P = "HEJ" = ASCII(H), ASCII(E), ASCII(J) = 0x48, 0x45, 0x4A

P₀ = 01001000

P₁ = 01000101

P₂ = 01001010

C₁ = 01000001

C₂ = 01000011

Vi ska använda CBC eller CTR

	CBC	CTR
Padding	Ja	nej
Hastighet	Snabb	Snabbare, ty parallel processing
Implementering	både E och D	bara E
Robust	läcker information om första blocket	läcka information om hela meddelandet
Nonce	Behövs, ev. random	Behövs

[edit] 5.8 Läckor

ECB (Electronic Code Book)

Om

CBC (Cipher Block Chaining)

Om

CTR

Om P_i = P_j blir inte C_i = C_j

Däremot så om så är ⇒ väldigt lite information som läcks.

[edit] Risk för kollision

M block skickas, varje block har längden n bitar.

Detta om M = 2^{n / 2}. Om n = 128 så får vi kollision om M = 2⁶⁴

[edit] 6 Hashfunktioner (kryptografiska hash functions)

Används för authentication (verifiering) digitala signaturer

Godtycklig mängd → hash → begränsad mängd, t.ex. 512 bitar

Istället för att signera m direkt så signerar man m' = h(m) där h är hashfunktionen.

[edit] 6.1 Säkerhet med hashfunktioner

• En-vägs funktion, inte möjligt att skapa m från m'
• Kollision:

Kollisionsresistenta funktioner = Även om kollisioner finns så inträffar de aldrig.

Ideal hashfunktion = slumpmässig mappning från alla möjliga insignaler till en begränsad mängd utsignaler.

hashfunktioner ⇒ ingen nyckel behövs

[edit] Praktiska hashfunktioner

Iterativa hashfunktioner som MD5 och SHA-familjen.

• Dela upp meddelandet i block, k stycken (plus ev. padding).
• Varje block processas för sig

Start: H₀

H_i = h'(H_{i − 1},m_i) där m = meddelandeblock i och H_k är slutgiltiga resultatet.

[edit] Fördelar med iterativa hashfunktioner

• Enklare att implementera
• Kan börja köra innan hela m mottagits

[edit] MD5

• 128 bitars output
• Meddelandet delas upp i block om 512 bitar
• Sista blocket innehåller meddelandets längd och padding

h' rekursiv den körs 4 rundor där varje runda innehåller additioner, booleansk algebra och blandning (permutering)

Nackdel: h' har kollisioner ⇒ H har kollisioner.

[edit] SHA-1

• 160 bitars output
• 2-3 gånger långsammare än MD5
• Blockstorleken är 128 bitar

SHA-256, SHA-384, SHA-512: Storleken på output för dessa varianter är 256, 384 respektive 512.

[edit] 2007-11-19

[edit] 6 Hashfunktioner

"Hash" = hacka sönder, röra om

m:h(m) = H

[edit] Iterativa hashfunktioner

Kan pipe-line:as.

m delas upp i block om n bitar, t.ex. 512.

H₀

H_i = h'(H_{i − 1},m_i)

H = H_k där

[edit] 6.3 Svagheter hos hashfunktioner

[edit] Length extensions

Första meddelandet m innehåller k block (och ev. delblock).

Andra meddelandet m' innehåller k + 1 block och de första k blocken är lika som i meddelande m.

m
A	B	C
m'
A	B	C	p

Första meddelandet: H = h(m)

Andra meddelandet: H för de första k blocken = h(m), H för alla block

MAC

[edit] 6.3.2 Partial message collision

Meddelande m

Verifiering av meddelandet (MAC)

k = nyckel

Attacker

Brute force to find k

Om en iterativ hashfunktion används för att räkna ut H då kan vi göra en bättre attack.

Leta efter två meddelande m och m' som ger en "kollision", d.v.s. som har samma H.

2^{n / 2} försök behövs, vilket är mycket enklare är att finna k.

[edit] Fix av svagheterna

kör hashfunktionen två gånger

Löser svagheterna

• Långsamt
• Behöver buffra hela meddelandet

En bättre fix

Bibehålla hastigheten (tidskomplexiteten)

H = h(m)

vi använder bara n / 2 bitar för att bibehålla hastigheten.

kallas h_d t.ex. SHA_d-256.

[edit] 7 Message Authentication Codes (MAC)

Kryptering hindrar Eva från att läsa meddelande, men inte att manipulera dem.

Authenticering hindrar att Eva kan manipulera med meddelanden, men inte att läsa dem.

Alice

a = MAC(k,m)

a,m skickas

Bob

a' = MAC(k,m) jämför a och a'.

[edit] 7.4 CBC-MAC

Kombinera Block cipher mode och MAC.

1. Kryptera meddelandet m genom att använda CBC
2. Kasta bort alla krypterade block C_i utom det sista C_k = a

Meddelande

H₀ = IV

a = MAC = H_k

[edit] 7.5 HMAC (Hash MAC)

Ej ideal hashfunktion ⇒ Hashsäkerhet = n / 2 bitar

”Bra” MAC: om h är bra.

[edit] 7.6 UMAC

Samma som HMAC fast snabbare.

T.ex. UMAC-STD-30, UMAC-MMX-30

Horton principle: Man ska ska authenticera vad som menas, inte vad som sägs.

T.ex. verifiera inte bara på IP-paket-nivå, då vet vi ju inte hur mailprogrammet tolkar data.

[edit] 2007-11-20

[edit] 8 The Secure Channel

• K är bara känd av Alice och Bob.
• Varje gång man sätter upp en ny kanal genereras ett nytt värde från nyckeln K för att Eva inte ska kunna använda meddelande från äldre sektioner.
• Key negotiation protocol

[edit] Trafikanalys

Alice ↔ Bob

• Storlek på m
• Tidpunkt
• Vem skickar meddelande till vem

[edit] 8.2 Ordningen på kryptering och verifiering

[edit] Kryptering först

Kryptering först för sändaren, verifiering först för mottagaren.

• ”Teoretiska resultat visar att kryptering först är bäst.”
• Mer effektivt vid fejkade meddelanden.

[edit] Autentifiering (verifiering) först

• MAC krypteras också. Det viktigaste är att skydda MAC.
• Authenticate what is being meant (klartexten), not what is being said (krypterade texten).

Recommended: Verifiera först, kryptera sedan.

[edit] 8.3 Hur sätter vi upp en säker kanal?

• Meddelandenumreringen – nonce
• Verifiering
• Kryptering

[edit] 8.3.1 Meddelandenumrering

• Källa för att finna IV
• Säkerställa att Bob får meddelandena i rätt ordning

• Unika
• Monotont växande

Använd 32 bitar ⇒ max antal meddelanden 2³² − 1, därefter byt nyckel.

m är index; meddelandenummer.

[edit] Authentication (verifieringen)

Använd HMAC – SHA-256

Insignal p_m meddelande och x_m är extra verifieringsdata (protokoll, typ av meddelande).

MAC code = a_m

l(.) = längden av en sträng i ”bytes”

[edit] Krypteringen

AES (Advanced Encryption Standard) in CTR mode with nonce.

Blockstorlek 128 bitar (16 ”bytes”).

Maxstorlek på varje meddelande bytes ⇒ blockräknare på 32 bitar med index i.

[edit] 2007-11-21

[edit] 10 Generera slumptal

Mättal för slumpmässighet ”entropy”

Exempel: 32 bitars tal ⇒ entropy = 32 bitar

Om 31 bitar + en bit paritet ⇒ entropy = 31 bitar

[edit] 10.1.2 Pseudorandom data (PRNG)

p(x) ↑
     │
     │
   1 ├──┐
     │░░│
     │░░│
     └──┴──→
    0   1  x

Slumptal framräknade med en matematisk algoritm från ett startvärde (seed) är slumpmässiga från en statistisk synvinkel, dock inte från en kryptografisk synvinkel.

[edit] 10.3 Fortuna

1. Ett riktigt slumptal för att beräkna startvärdet (seed)
2. Använd startvärdet för att beräkna en riktig pseudorandom sekvens av valfri längd.
3. Ibland byt startvärde och starta generera igen.

[edit] 10.4 Generatorn ska vara en CTR mode

k_i = E(K,i)

E ska implementeras av t.ex. AES-algoritmen.

Blockstorlek 256 bitar och räknaren i ska vara 128 bitar.

Glöm inte bort att ta bort den gamla nyckeln.

Om vi genererar 2¹²⁸ block med slumpdata så är två block lika ⇒ Begränsa antal block till högst 2¹⁶ i varje anrop.

[edit] 10.4.1 Initialisering

K = 0 C = counter = 0

[edit] 10.4.2 Reseed

När en viss tid eller viss mängd data överförts.

K = newK

Nytt K kan beräknas med en hash t.ex. SHA-256.

C = C + 1

[edit] 10.4.3 Generate Blocks

Genom att använda CTR

r = E(K,c) (c = counter)

Generera två extra block av r som används som ny nyckel.

[edit] 10.5 Accumulator

Används som insignal till ”reseed”.

Man lägger ihop data från olika källor.

[edit] 10.5.2 Pool

Mängd av händelser som används som input till Ackumulatorn, t.ex. zenerdiodbrus, muspekare.

Viktigt

1. Lita aldrig på algoritmer i operativsystemet som genererar slumptal.
2. Använd så många händelser som möjligt för att bygga upp ”original”-slumptalet.

[edit] 2007-11-26

[edit] 11 Primtal

Används för generering av publika nycklar

Delbarhet a | b ⇒ a är en delare till b ⇒ Vi kan dela b med a utan att få en rest.

Exempel: 7 | 35 Ja, det är en delare

Primtal: a | 11

Primtal: Om det bara finns två delare: primtalet själv och 1.

Eratosthenes’ såll

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

Stryk 1

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

Stryk varannat tal efter två:

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

Stryk var tredje tal efter tre:

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

Stryk var femte tal efter fem:

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

Vi kan sluta vid 5, eftersom det är det största tal vars kvadrat är mindre än det högsta tal som ska undersökas.

Lemma 1: a | b och

Bevis: Om a | b så måste det finnas ett heltal s så att .

Om b | c så måste det finnas ett heltal t så att .

⇒

Lemma 2: Låt n vara ett positivt heltal > 1 Låt d vara den minsta delaren till n > 1; då är d ett primtal.

Teorem: Det finns oändligt många primtal.

OBS! Det finns ingen exakt formel för att räkna ut primtal i ett visst intervall.

Goldbach’s conjecture: Varje jämt heltal > 2 är en summa av två primtal.

[edit] 11.3 Moduloräkning med primtal

Exempel: 25mod 7 = 4

Att finna (amod b) hitta heltalen q och r så att a = qb + r då är (amod b) = r

[edit] Addition och Subtraktion

(a + b)mod p

(a + b) är större än p: då blir resultatet a + b − p

Exempel: Om p = 7

5 + 3 − 7 = 1

[edit] Finita fält

Är ett antal heltal modulo ett primtal. Kallas (mod p)-fält eller bara (mod p)

Exempel: Grupp 0,1,2,3,4 och p = 5

Alla resultat kommer att vara i området oberoende av operation.

finit fält modulo p

Grupp: Ett antal heltal samt en operation:

Exempel: och addition blir en grupp.

Exempel: En grupp: { 0, 1, 2, 3, 4, 5, 6, 7 } modulo 8

Detta är inte ett finit fält eftersom 8 inte är ett primtal.

En undergrupp { 0, 2, 4, 6 }

---

, multiplikativ grupp

{ 0, 1, 2, 3, 4, 5, 6 }

A subgroup: { 1, 2, 4 }

Exempel:

[edit] GCD (Största gemensamma delare )

GDC av (a,b) alltså det största k som uppfyller k | a och k | b

(a,b) = (21,30)

så länge som

30mod 21 = 9

(a₁,b₁) = (9,21)

21mod 9 = 3

(a₂,b₂) = (3,9)

9mod 3 = 0

(a₃,b₃) = (0,3)

Exempel:

(23,35) = (a₀,b₀)

[edit] 2007-11-27

[edit] 12.1

[edit] Grupper och undergrupper

{ 0, 1, 2, 3, 4, 5, 6, 7 } (mod 8) är en additiv grupp, men ej ett finit fält eftersom 8 ej är ett primtal.

{ 0, 2, 4, 6 } (mod 8) är också en giltig additiv grupp eftersom man bara kan få någon medlem i gruppen när man adderar medlemmar i gruppen.

Noll får inte vara med i multiplikativa grupper.

{1,6}

[edit] Diffie och Hellman

1976

10 användare behöver byta nycklar.

Diffie och Hellman ⇒ Kryptering ≠ Dekryptering

p ska vara ett stortprimtal någonstans i området 2000-4000 bitar.

Finit grupp tillsammans med multiplikation modulo p.

Skapa en serie:

g ska vara ett element i gruppen.

Det är en oändlig serie men en finit grupp.

Exempel:

g = 2

Serien:

Antag att värdena börjar repeteras vid gⁱ = g^j

i < j

Dividera båda sidor med gⁱ ⇒ 1 = g^{i − j} Vi kan finna ett värde q = j − i som ger g^qmod p = 1

Minsta möjliga q = ordningen av g ⇒

Nästa tal i ordningen är då g^q = 1

Exemplet ovan

g = 2 genererar serien {1,2,4} ordning q = 3

Det är alltid möjligt att hitta en generator g som kan generera hela gruppen

Den generator g som genererar hela gruppen kallas ett primitivt element.

Andra värden på g kommer att generera undergrupper vars storlek är intressant ur en attacksynvinkel.

Välj g som ska vara ett primitivt element (som kan generera hela gruppen).

Välj h som är ett godtyckligt element i gruppen.

⇒ h = g^x där x ännu inte är valt.

Element som genereras med hjälp av h:

Ordningen av h: det minsta q för vilket h^q = 1

Om xq = 0(mod p − 1)

Detta händer.

⇒ q är en faktor i p − 1

g = primitivt element = 3

Serien

Välj = en subgrupp av ordning 3

Ordningen av subgrupperna är en faktor av (p − 1)

[edit] 12.2

Exempel

Välj ett primtal: p = 7

Välj ett primitivt element g = 3

p och g är publika.

{1,2,3,4,5,6}

Typisk tentafråga

[edit] Alice

Exempel x = 4

x är hemlig.

Beräkna g^x = 3⁴mod 7 = 4

g^x är publik

K = (g^y)^xmod 7 = 2⁴mod 7 = 2

[edit] Bob

Exempel y = 2

y är hemlig.

Beräkna g^y = 3²mod 7 = 2

g^y är publik

K = (g^x)^y = 4²mod 7 = 2

2 är den gemensamma nyckeln som används vid kommunikationen.

Är det möjligt att beräkna g^xy från g, p, g^x och g^y?

Diffie-Hellman-problemet inte möjligt att lösa om p är ett primtal och om g är ett primitivt element.

Anfallaren känner till p, g och ser g^x och g^y; känner ej till x och y.

[edit] 2007-12-03

(Cancelled due to illness.)

[edit] 2007-12-04

[edit] Diffie-Hellman

Välj p = 7, välj g = 3

[edit] Alice

Väljer x

Publicerar g^x.

k = (g^y)^x

[edit] Bob

Väljer y

Publicerar g^y

k = (g^x)^y

[edit] 12.3 Man in the middle

[edit] 12.4 Fallgropar

Fallgrop A

g = 1 ej bra ty k är alltid = 1

Lösning: kolla om g^x = 1 eller g^y = 1

Fallgrop B

Generator primitivt element, g har en liten subgrupp ⇒ få möjliga nycklar

Lösning: Kolla så att p = primtal och g = primitivt element eller ger tillräckligt stor subgrupp

OBS. Storleken på subgrupperna är delare till p − 1 så se till att undvika primtal med små delare.

[edit] 12.5 Safe Primes

2q + 1 där q också är ett primtal.

Subgrupper som är möjliga

• Storlek 1: Enkel att testa
• Storlek 2: Nummer 1 och p − 1
• Storlek q Välj denna
• Storlek 2q (fulla gruppen)

[edit] Problem med den fulla gruppen

Exakt hälften av alla tal i en full grupp är ”squares” (mod p)

Exempel:

”squares” = {1,4,9,16,25,36,}(mod 7) = {1,4,2,2,4,1}

Non-squares = {3,5,6}

Om en generator g = ”square” ⇒ g är inte ett primitivt element.

p = 2q + 1

Om g^x är genererat från en non-square-generator så kan Eve använda sig av Legendre symbol-funktion för att bestämma om x är jämn eller udda.

Lösning: använd g som är ”squares” (mod p) d.v.s. en subgrupp av storlek q

[edit] Algoritm för att använda ett säkert primtal (p,q,g)

1. Välj p och q så att både p och q är primtal. p = 2q + 1
2. Välj g som är en ”square” så att g^x tillhör halva mängden. Hur? Välj α ska uppfylla g = α²(mod p)
3. Kolla så att och

Exempel: q = 5

α = 2

g = 2² = 4mod 11 = 4

så OK

så OK

g^x ger samma möjliga nycklar som (g^x)^y

g^x (ordning q = 5) = {1,4,5,9,3}

När man tar emot ett g^x se till att g^x kommer från en subgrupp med ordning q

och (g^x)^qmod p = 1

Exempel: p = 11 q = 5 g = 4

x = 1 ⇒ g^x = 4

(g^x)^qmod p = (4⁵)mod 11 = 1024mod 11 = 1 ⇒ OK

Om g^x = 8

8⁵mod 11 = 32768mod 11 = 10 ⇒ inte OK g^x

Säkra primtal har en nackdel att de är beräkningskrävande ⇒ mindre subgrupper.

Hur:

1. Hitta ett primtal q minst 256 bitar
2. Hitta ett mycket större primtal p = Nq + 1 (om N är primtal är p garanterat primtal)
3. Hitta lämpligt g, välj g = α^N kolla så att och g^q = 1

[edit] 2007-12-10

[edit] 13 RSA

• Mest kända och använda publika nyckel-krypteringsalgoritmer.
• Både kryptering och digitala signaturer
• Bygger på svårigheten att faktorisera stora primtalsprodukter

[edit] Diffie-Hellman

p och q givna

Lätt att beräkna g^xmod p om man vet x, mycket svårt i motsatt riktning.

[edit] RSA

Givet n och e - (publika)

- (inte modulo)

p och q - (stora primtal, minst tusen bitar)

Kryptering: m^emod n

[edit] 13.2 CRT – The Chinese Remainder Theorem

Diffie-Hellman: Beräkningar modulo ett primtal p

RSA: Beräkningar modulo en primtalsprodukt

Teoremet: (a,b) = (xmod p,xmod q)

Är a och b kända samt p och q så kan x bestämmas.

[edit] 13.2.1 Garner’s Formula

Hur ska vi använda CRT?

Kan användas för att spara beräkningskraft när vi räknar (mod n).

Addition (x + y)mod n kan representeras av (x + y)mod p,(x + y)mod q = (xmod p + ymod p),(xmod q + ymod q)

p primtal: x^{p − 1} = 1(mod p)

x^t = 1mod n

⇒ x^t = 1(mod q) och x^t = 1(mod p) eftersom

p − 1 ska vara en delare till till t och q − 1 ska vara en delare till t.

t = minsta gemensamma multipeln till (p − 1,q − 1)

p och q stora och olika primtal.

m^e(mod n)

Definiera två exponenter e och d

Välj en publik exponent e = till ett litet och udda tal.

d ska beräknas = inversen till emod t ⇒

Kryptering c = m^emod n

Dekryptering m = c^dmod n

= m(mod n)

m^t = 1(mod n)

m^t = 1mod p m^t = 1mod q

om

[edit] Exempel

Dekryptering och kryptering med RSA

p = 17 q = 19

Beräkna (publik)

lcm = Least Common Multiple

Beräkna (hemlig)

e = 5 (publik)

⇒ d = 29 (hemlig)

m = 201

c = m^emod n = 201⁵mod 323 = 328080401001mod 323 = 216

Dekryptering:

c^d = 216²⁹mod 323 = 50021738714629030177311081962496059484833406150976385567830453518336mod 323 = 201

[edit] 2007-12-11

[edit] RSA

Kryptering c = m^emod n

Dekryptering m = c^dmod n = c^{1 / e}mod n

Börja välj p och q

n är publik.

t = minsta gemensamma multipeln av p − 1 och q − 1.

Välj e. Litet udda tal < t

e ska inte ha gemensam faktor med t då vi inte hittar ett d.

Beräkna d från

Fermats lilla sats

x^{p − 1} = 1(mod p) om p är ett primtal

[edit] Tentauppgift kan vara

Ta fram RSA-parametrarna om p = 47 och q = 59

[edit] Svar:

e ska inte ha gemensam faktor med t

e = 3

Kolla att

Beräkna d:

⇒ ⇒ d = 445

c = m^emod n

m = c^dmod n = c^{1 / e}mod n

(m^emod n)^{1 / e}mod n

Om m^e < n då gäller (m^e)^{1 / e}mod n = m

En viktig fallgrop är detta ⇒ undvik små m

[edit] Signera ett meddelande

s = m^{1 / e}mod n = m^dmod n

Skicka m,s

Jämför och mottaget s.

⇒ Använd två värde på e, ett för signaturen och ett för krypteringen.

Storleken på n ska vara från 2048 till 4096 bitar, samma som för Diffie-Hellman.

Kryptering: I praktiten används inte RSA för att kryptera meddelanden eftersom m < n därför används RSA för att kryptera nycklar.

[edit] 13.6

1. Välj slumpmässig nyckel K + eventuell padding
2. Kryptera K med RSA
3. Använd ett block cipher mode för att kryptera meddelandet
4. Skicka RSA-krypterad nyckel K och krypterat meddelande. , istället för att

[edit] 13.4.3 Hemliga nycklar

Om man känner till en av de hemliga nycklarna (p,q,t,d) och de publika, då är det enkelt att knäcka RSA.

Två fallgropar vid signering

[edit] 1

Använd inte samma e vid kryptering och signering s = m^{1 / e}mod n

[edit] 2

Alice skickar två meddelanden som hon signerar (m₁,s₁) (m₂,s₂)

Eve konstruerar ett meddelande som uppfyller

signera genom att

[edit] Uppgift

Ta fram RSA-parametrar om p = 11 och q = 89 välj e större än 3 och kryptera m = 68

[edit] 2007-12-17

[edit] 14 Inledning till kryptografiska protokoll

• Utbyte meddelande
  • T.ex. Diffie-Hellman

[edit] A. Roller

Kom ihåg att alla kan anta olika roller, t.ex. man in the middle, DH

[edit] B. Förtroende

Inte svart-vitt

lita på någon att hantera t.ex. 10000kr.

kryptotillämpningar

minimera mängden förtroende.

1. Antal människor vi behöver lita på
2. Hur mycket förtroende vi behöver ge dessa människor

[edit] 14.5

[edit] C. Meddelande, steg

Specifikationerna av ett protokoll

• inte för detaljerad
• inte för enkel
• dela protokollet i flera steg

[edit] Transportlagret

• Ett givet antal bitar skall från punkt A till B. T.ex. TCP
  • Ingen säker kanal, ur ett kryptoperspektiv

[edit] Protokoll och meddelandeidentifiering

• Protokollinformation
  • Vilken version
  • Vilket protokoll
• Meddelandenumrering

[edit] 14.5 Meddelandekryptering

Konvertera från datasymboler till bitsekvenser och kryptera.

[edit] Felhantering

• Hantera fel varsamt
• T.ex. pinkoder om 4 siffror
  • 

[edit] 15 Key negotiation protocols

• Använde nyckelutbytnadsprotokollet för att sätta upp en "session key", K
  • "Session key" tenderar att vara beräkningskrävande
• Använd k för en säker och effektiv kanal

Varför använda en "session key" om vi redan har en säker nyckel?

• Om vi förlorar en ”session key” så är ändå t.ex. gårdagens information säker.

[edit] 15.2 DH + added authentication

Alice vet [p,q,g]

Väljer x från

g^x beräknas och skickas

Bob vet [p,q,g]

Väljer y

Beräknar g^y och k = (g^x)^y

Skickar tillbaka g^y

Alice kan nu beräkna k = (g^y)^x

och beräkna

Alice skickar a och m

Bob kollar a' och jämför a = a'

Bob skickar b och m

Alice kollar b = b'

[edit] Problem

• Samma nyckel används vid kryptering och verifiering ⇒ verifieringen ger oss inget nytt
• Inte bra att ha givna (p,q,g)
• 4 meddelande behövs, för många går att göra på 3

[edit] Verifiering: Hur ska vi välja m?

m ska vara all information som är skickad upp till nu.

Skriver Auth då menas all information som är sänt genom t.ex. en hashfunktion.

[edit] Alice

Väljer (p,q,g)

Välj x ⇒ g^x

Auth_A och g^x skickas.

[edit] Bob

Får reda på (p,q,g)

Välj y ⇒ g^y

Beräknar Auth'_A, jämför med mottagna Auth_A

Beräknar

Auth_B och g^y skickas

[edit] Alice

Beräknar Auth'_B och jämför med mottagna Auth_B

[edit] Problem

Problem vid verifiering och p,q,g kan vara felaktigt valda

1. Alice skickar slumptal + minsta p,Auth
2. Bob väljer parametrar, beräknar g^x + Auth
3. Alice beräknar g^y och Auth

Alice	↔	Bob
Väljer minsta storleken på p = s		Väjer p,q,g
Väljer slumptal (Nonce) på 256 bitar = Na	S,Na →	väljer x ⇒ gx
	← p,q,g,gx,AuthA	Beräknar AuthA(s,Na,p,q,g,gx)
Kolla (p,q,g)
välj y = gy
Beräkna Auth'A och jämför.
Beräkna AuthB och k (30 bitar)	gy,AuthB→	Kolla AuthB, beräkna k

Ytterligare förbättring för att få k till 256 bitar ⇒

[edit] 2007-12-18

[edit] 17 The Clock

• Begränsar varaktigheten av ett dokument
• nonce
• använd klockan för att inte förväxla gamla meddelanden som nya

[edit] 18 Key Servers

Organisation som man litar på som handhar publika nycklar eller delar ut en säker nyckel samt vet vem som är vem.

• Alla användare sätter upp en publik nyckel hos "key server".

Alice, k_A och Bob, k_B

[edit] 18.2 Kerberos

Alice vill kommunicera med Bob.

"key server" har då k_A och k_B

k_AB = session key

Alice	Request “Bob” →	Key Server
	← EKA(KAB)
	← EKA(EKB(KAB))
	EKB(KAB) →	Bob

• Verkar enkelt ⇒ komplicerat protokoll
• Servern måste hålla reda på alla använda k_AB, session keys

[edit] 18.3 Secure Connection

Förenklad version

Förutsätter att det finns en säker kanal mellan key server och Alice samt mellan key server och Bob.

Alice vill kommunicera med Bob

key server och Alice har nyckel k_A

1. Alice använder ett nyckelförhandlingsprotokoll för att förhandla en session key
2. Alice använder nu för att kommunicera med key server
3. Bob gör som punkt 1 och för
4. Bob kommunicerar med key server med nyckel
5. All kommunikation via nyckelservern

[edit] 19 Public Key Infrastructure (PKI)

CA - Central Authority

CA har en egen privat och publik nyckel. Den publika publiceras. (RSA används, oftast).

"Gå med i PKI"

1. Alice genererar sin publika/private nyckel.
2. Alice skickar sin publika nyckel (P_kA) till CA
3. CA utfärdar ett Certifikat som säger att P_kA
4. CA publicerar P_kA på sin officiella lista
5. Bob samma förfarande

kommunicera Alice ↔ Bob

1. Alice skickar sin publika nyckel P_kA till Bob
2. Bob kollar med CA om P_kA är samma
3. Bob skickar…
4. Alice kollar…

[edit] 19.2 Universell PKI

• Omöjlig

[edit] 19.3 Multilevelcertificat

Säkerhetskedja – Bankvärlden

T.ex. Mastercard ← Firstcard →

[edit] 19.4 Bäst före-datum

• Använd inte samma nyckel en längre tid
• Behöver också certifikat bytas