(:title Domande di Crittografia:)

 :: Esercizi di Crittografia ::

Esercizi svolti by Licia

Funzioni MAC

Funzioni HASH

APPELLO DEL 14/09/2010

http://ananke.crema.unimi.it/Crittografia/Appello-100914.pdf

CHIESTO AL PROF.

2. a) Si consideri la seguente funzione hash che fa uso di un robusto algoritmo di cifratura simmetrica Ek(m). Per un messaggio arbitrario m=(m1,….,mn), l’hash d è calcolato come d=Em1(IV) XOR Emn(IV), dove indica lo XOR i IV è un valore fissato.

i) Discutere le proprietà di sicurezza della funzione indicata. In particolare la one-wayness (sugg. Si consideri un messaggio con n=1) e la collision resistance (sugg. Si consideri un messaggio con n=3 dove m2=m3).

Proprietà di One-wayness: se n=1 si ha un solo blocco, cioè M = m1, quindi l’hash d = Em1(IV) e da questa funzione non si è in grado di risalire al messaggio in chiaro perché m1 è la chiave e quindi l’unico modo sarebbe rompere il cifrario e risalire alla chiave (cioè il blocco).

Proprietà di collsion resistance: se n=3 e m2=m3 l’hash è il seguente:

Poichè i blocchi m2 ed m3 sono uguali, per la proprietà dello XOR si eliminano e rimane solo la cifratura con chiave il blocco 1

Quindi un messaggio M formato da 3 blocchi è come se corrispondesse ad un solo blocco, e di conseguenza è possibile calcolare un M’ formato da un solo blocco tale da poter trovare una collisione:

i)

	H1(x) = H0(H0(x1)||H0(x2))

iii) Se assumiamo che la funzione H0 sia collision resistance e per assurdo assumiamo che H1 non lo sia, per non soddisfare la proprietà di collision resistance dovremmo avere un input x’ che genera uno stesso output y’, ma, per avere uno stesso output, anche gli argomenti della funzione H1 non devono essere collision resistance, e ciò non corrisponde perché noi abbiamo detto inizialmente che H0 era collision resistance; di conseguenza abbiamo dimostrato che, se H0 è collision resistance, lo è anche H1.

APPELLO DEL 20/01/2011

http://ananke.crema.unimi.it/Crittografia/Appello-110215.pdf

CHIESTO AL PROF.

a) Si consideri la seguente funzione hash che opera su messaggi M lunghi 2m bit: H0:{0,1}2m -> {0,1}m e si costruisca la funzione hash H1:{0,1}4m -> {0,1}m tale che se x è una stringa di bit x € {0,1}4m con x = (x1||x2) e x1, x2 € {0,1}2m allora

                     H1(x) = H0(H0(x1)||H0(x2))

i. Se m = 4 e H0 è la funzione che somma in modulo le coppie di bit successive, calcolare l’output di H1 se x = 0110 1100 0001 1000

ii. Si discutano le proprietà di sicurezza della funzione H1

iii. Si provi in generale che se H0 è collision resistant, lo è anche H1

http://ananke.crema.unimi.it/Crittografia/Appello-050621.pdf

      |   1        se     w0(M) < w1(M)

h(M) = | 0 se w0(M) > w1(M)

      |   m1       se     w0(M) = w1(M) (dove M=m1m2m3…..)'''

   	 |   1    se     w0(M) < w1(M)

   	    |   1    se     w0(M) < w1(M)

   	               |   1    se     w0(M) < w1(M)

''' | 1 se w0(M) < w1(M)

      |   m1   se     w0(M) = w1(M) (dove M=m1m2m3…..)'''

''' | 1 se w0(M) < w1(M)

          |   m1   se     w0(M) = w1(M) (dove M=m1m2m3…..)'''

b) Si consideri la seguente funzione hash h(M) definita per messaggi M {0,1}*. Sia W0(M) (risp, w1(M)) il numero di 0 (risp, di 1) presenti nel messaggio M. La funzione h(M) restituisce: ''' | 1 se w0(M) < w1(M) h(M) = | 0 se w0(M) > w1(M)

        |   m1   se     w0(M) = w1(M) (dove M=m1m2m3…..)'''

i) Si calcoli il digest dei seguenti messaggi M1 = {00011}, M2 = {100101}, M3 = {00111}, M4 = {0101010101}.

APPELLO DEL 21/06/2005

FATTO IN AULA '''b) Si consideri la seguente funzione hash h(M) definita per messaggi M {0,1}*. Sia W0(M) (risp, w1(M)) il numero di 0 (risp, di 1) presenti nel messaggio M. La funzione h(M) restituisce:

h(M) = | 0 se w0(M) > w1(M)

i) Si calcoli il digest dei seguenti messaggi M1 = {00011}, M2 = {100101}, M3 = {00111}, M4 = {0101010101}.'''

ii) Si discutano le proprietà di sicurezza della funzione h(M) precedentemente descritta

monodirezionalità: è soddisfatta perché dal valore dell’hash non è possibile risalire al messaggio sicurezza debole: non soddisfatta perché si può trovare un altro messaggio M che genera uno stesso hash sicurezza forte: non soddisfatta perché si può trovare una coppia di messaggi M e M’ che generano lo stesso hash

1. Esercizi svolti by Licia

Esercizi svolti di Licia

1. Esercizi svolti di Licia

Esercizi svolti di Licia?

Torna alla pagina di Crittografia

funzioni MAC

Dei seguenti esercizi posso garantirne la correttezza solo per quelli fatti in aula e per quelli corretti dal prof...

APPELLO DEL 21/06/2005

FATTO IN AULA b) Si consideri la seguente funzione hash h(M) definita per messaggi M {0,1}*. Sia W0(M) (risp, w1(M)) il numero di 0 (risp, di 1) presenti nel messaggio M. La funzione h(M) restituisce:

	|   1    se     w0(M) < w1(M)

h(M) = | 0 se w0(M) > w1(M)

        |   m1   se     w0(M) = w1(M) (dove M=m1m2m3…..)

i) Si calcoli il digest dei seguenti messaggi M1 = {00011}, M2 = {100101}, M3 = {00111}, M4 = {0101010101}.

W0 indica gli zeri, mentre w1 indica gli uni. Se guardiamo i bit di ogni singolo messaggio, per es. M1 vediamo che M1 ha 3 zeri e 2 uni, quindi gli zeri sono maggiori degli uni, di conseguenza ci troviamo nel secondo caso: h(M1) = 0, idem per gli altri messaggi. Per M2 invece possiamo vedere che gli uni e gli zeri sono uguali, quindi siamo nel caso 3: h(M2) = m1, cioè è uguale al primo bit del messaggio M2 che è 1 (h(M) = 1), ecc….

ii) Si discutano le proprietà di sicurezza della funzione h(M) precedentemente descritta monodirezionalità: è soddisfatta perché dal valore dell’hash non è possibile risalire al messaggio sicurezza debole: non soddisfatta perché si può trovare un altro messaggio M che genera uno stesso hash sicurezza forte: non soddisfatta perché si può trovare una coppia di messaggi M e M’ che generano lo stesso hash

APPELLO DEL 16/04/2009

Si consideri la seguente funzione MAC M(a,b) = ax+b mod 3 che ha come chiave una coppia di valori a e b e si applica ai messaggi x, con a, b, x € Z3. a) Si costruisca la matrice di autenticazione che calcola tutti i valori considerando per ogni riga le possibili coppie di valori della chiave e come colonne i possibili messaggi input x. Le celle della matrice avranno il valore del MAC. Esempio: Chiave

	0	1	2

(0,0) 0 0 0

Se a,b,x € Z3, allora possono assumere valori 0, 1, 2; quindi la matrice di autenticazione sarà:

Chiave MAC(x) Calcolo Funzione MAC (a,b) (ax+b mod 3)

	0	1	2	   X = 0	    X = 1	    X = 2

(0,0) 0 0 0 0*0 + 0 mod 3 0*1 + 0 mod 3 0*2 + 0 mod 3 (0,1) 1 1 1 0*0 + 1 mod 3 0*1 + 1 mod 3 0*2 + 1 mod 3 (1,0) 0 1 2 1*0 + 0 mod 3 1*1 + 0 mod 3 1*2 + 0 mod 3 (1,1) 1 2 0 1*0 + 1 mod 3 1*1 + 1 mod 3 1*2 + 1 mod 3 (0,2) 2 2 2 0*0 + 2 mod 3 0*1 + 2 mod 3 0*2 + 2 mod 3 (2,0) 0 2 1 2*0 + 0 mod 3 2*1 + 0 mod 3 2*2 + 0 mod 3 (2,2) 2 1 0 2*0 + 2 mod 3 2*1 + 2 mod 3 2*2 + 2 mod 3 (1,2) 2 0 0 1*0 + 2 mod 3 1*1 + 2 mod 3 1*2 + 2 mod 3 (2,1) 1 0 2 2*0 + 1 mod 3 2*1 + 1 mod 3 2*2 + 1 mod 3

b) Si consideri un attacco di selective forgery. Si spieghi in cosa consiste l’attacco e rispetto alla matrice costituita si discuta la sicurezza del MAC proposto. L’attacco selective forgery prevede che: dato un messaggio M l’attaccante cerca di determinare y tale che y = MAC(M,K); cioè l’avversario sarà in grado di calcolare, per alcuni messaggi, il MAC corretto anche senza conoscere la chiave. Considerando il MAC proposto l’attaccante sarà in grado di calcolare il MAC con una certa facilità poiché è una semplice funzione lineare in Z3.

funzioni HASH

APPELLO DEL 20/01/2011

CHIESTO AL PROF. a) Si consideri la seguente funzione hash che opera su messaggi M lunghi 2m bit: H0:{0,1}2m -> {0,1}m e si costruisca la funzione hash H1:{0,1}4m -> {0,1}m tale che se x è una stringa di bit x € {0,1}4m con x = (x1||x2) e x1, x2 € {0,1}2m allora

                     H1(x) = H0(H0(x1)||H0(x2))

ii. Se m = 4 e H0 è la funzione che somma in modulo le coppie di bit successive, calcolare l’output di H1 se x = 0110 1100 0001 1000 iii. Si discutano le proprietà di sicurezza della funzione H1 iv. Si provi in generale che se H0 è collision resistant, lo è anche H1

Riassunto dati:

• x1 e x2 €{0,1}2m così che la loro concatenazione da ({0,1}2m || {0,1}2m) ={0,1}4m , che corrisponde infatti alla x che € a {0,1}4m
• x = 0110 1100 0001 1000, quindi x1 = 0110 1100 mentre x2 = 0001 1000
• H0 è la funzione che somma in modulo le coppie di bit successive: cioè si considerano le coppie di bit della x (di x1 e x2) e si sommano in modulo:

	es. 01 = 1, 00 = 0, 11 = 0, 10 = 1 

Quindi se proviamo a sostituire tali valori nella funzione hash H1: i) H1(x) = H0(H0(x1)||H0(x2))

	      = H0(H0(0110 1100)||H0(0001 1000))
	      = H0[(1100)|| (0110)]
	      = 0011

ii) - La proprietà One-wayness è soddisfatta perché dall’output H1 = 0011 non sono in grado di risalire all’input dato dai due valori x1 e x2 - La proprietà di sicurezza debole alle collisioni non è soddisfatta perché posso generare un altro input che mi dia lo stesso valore di ouput; questo è possibile perché se inserisco per es. un input formato dalla seguenza 1001 al posto di 0110 mi darà lo stesso output per come è costruita la funzione hash H0 - La proprietà di sicurezza forte alle collisioni non è soddisfatta perché, come detto per la sicurezza debole, posso trovare una coppia di input che mi dia lo stesso output, sfruttando la costruzione della funzione di hash H0

iii) Se assumiamo che la funzione H0 sia collision resistance e per assurdo assumiamo che H1 non lo sia, per non soddisfare la proprietà di collision resistance dovremmo avere un input x’ che genera uno stesso output y’, ma, per avere uno stesso output, gli argomenti della funzione H1 devono essere uguali, e ciò non corrisponde perché noi abbiamo detto inizialmente che H0 era collision resistance; di conseguenza abbiamo dimostrato che, se H0 è collision resistance, lo è anche H1.

APPELLO DEL 14/09/2010

2. FUNZIONI HASH a) Si consideri la seguente funzione hash che fa uso di un robusto algoritmo di cifratura simmetrica Ek(m). Per un messaggio arbitrario m=(m1,….,mn), l’hash d è calcolato come d=Em1(IV) XOR Emn(IV), dove indica lo XOR i IV è un valore fissato.

i) Discutere le proprietà di sicurezza della funzione indicata. In particolare la one-wayness (sugg. Si consideri un messaggio con n=1) e la collision resistance (sugg. Si consideri un messaggio con n=3 dove m2=m3).

Proprietà di One-wayness: se n=1 si ha un solo blocco, cioè M = m1, quindi l’hash d = Em1(IV) e da questa funzione non si è in grado di risalire al messaggio in chiaro perché m1 è la chiave e quindi l’unico modo sarebbe rompere il cifrario e risalire alla chiave (cioè il blocco).

Proprietà di collsion resistance: se n=3 e m2=m3 l’hash è il seguente: d=Em1(IV) XOR Em2(IV) XOR Em3(IV) = Em1(IV)

un messaggio M formato da 3 blocchi è come se corrispondesse ad un solo blocco, quindi è possibile calcolare un M’ formato da un solo blocco tale da poter trovare una collisione: M = m1m2m3 -> h(M) = Em1(IV) M’ = m1 -> h(M’) = Em2(IV) Quindi questa proprietà non è soddisfatta

• Schema (è Feistel-confermato dalle slide)

(:title Domande e Esercizi di Crittografia:)

• Playfair: come si usa, che vantaggi ha, attacchi a Playfair

• Possibili attacchi in base alla conoscenza dell'avversario

• Diffie Hellman (di solito con esercizio annesso)

• HMAC

• b = lunghezza in BYTE della password (0 - 255)

• Utilizzo delle funzioni hash: firma digitale, integrità, certificazione del tempo

• Equivalente alla firma normale
• Caratteristiche
  • facile da generare
  • facile da verificare
  • impossibile da falsificare

• certification path (stessa CA; CA differenti)

Torna alla pagina di Crittografia

• (n,n)

Torna alla pagina di Crittografia

(:title Domande di Crittografia:)

 :: Domande di Crittografia ::

Teoria teorica

• algoritmo di cifratura incondizionatamente sicuro (One Time Pad) e computazionalmente sicuro

Crittografia classica

• Playfair: come si usa, che vantaggi ha
• Vigenere: come si usa
  • Kasiski
  • Indice di Coincidenza (IC)
  • Indice Mutuo di Coincidenza (IMC)
• Playfair
• Cifrario Affine
• Hill
• Autokey

Crittografia simmetrica

• cifratura ideale: blocco di n bit => 2ⁿ valori => 2ⁿ mappaggi
• confusione e diffusione
• caratteristiche dei cifrari simmetrici moderni
• rete di Feistel
• DES
  • descrizione
  • prova del funzionamento
  • sicurezza
  • Modalità: ECB, CBC, CFB, OFB, COUNTER
  • Double DES
    • Meet in the middle
  • Triple DES
    • Meet in the middle
• AES
  • Blocco: 128, 192, 256 bit
  • Round: 10, 12, 14
  • Crittografia e Decrittografia (non è Feistel)
• Blowfish
  • Blocco: 64 bit
  • chiave: 32 - 448 bit
  • Schema (non è Feistel)
• RC5 w/r/b
  • w = lunghezza della word (16, 32, 64)
  • r = numero di round (0 - 255)
  • b = lunghezza in BYTE della password
• RC4

Crittografia asimmetrica

• RSA
  • Teoremi di Fermat ed Eulero
  • Ottimizzazioni: left-to-right, right-to-left
  • Sicurezza
    • Sicurezza della chiave
    • Sicurezza della cifratura: Chosen Ciphertext, Common Modulus, Low Exponent
    • Sicurezza dell'implementazione: power, timing
    • Malleabilità
• El Gamal
  • Come stabilire se un g è generatore di Z_p^*

Hash, MAC

• Funzioni hash: proprietà (one-way, weak collision resistance e strong collision resistance)
• Paradosso del compleanno
• MD4
• MD5
• SHA-1
• MAC: caratteristiche e applicazioni
  • Sicurezza
    • Total Break = recupero la chiave
    • Selective Forgery = dato M, trovarne il MAC senza chiave
    • Existential Forgery = trovare una coppia M, y tale che y è MAC(M, k)

Firme digitali e certificati

• DSS: parametri, utilizzo
• Differenza tra firma RSA e DSS usati con lo stesso messaggio in due occasioni
• Certificati digitali
  • scopo
  • CA
  • caratteristiche
  • certification path (stessa CA, CA differenti)

Secret Sharing

• Diffie Hellman
  • Man in the middle
• (k,n)
• (n,n)