Sperimentazioni di Sicurezza, A.A. 2008-2009 Identity Based Cryptosystems Speaker: Luca Maria Aiello, PhD student Università degli Studi di Torino, Computer Science Department Corso Svizzera, 185 – 10149, Torino, Italy [email protected] 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 1 Introduzione o Panoramica su Identity Based Cryptosystems • Encryption • Signature • SignCryption • Key agreement o Idea di base • In un contesto a chiave pubblica, evitare directory e certificati • Un identificativo human readable sostituisce la chiave pubblica o Strumenti matematici • Teoria dei gruppi • Curve ellittiche • Pairing 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 2 Sommario 1. 2. 3. 4. 5. 6. 7. 6/4/2010 Concetti di base Shamir IBS Teoria dei gruppi, curve ellittiche e pairing Boneh e Franklin IBE Sakai Ohgishi Kasahara IBS Considerazioni ed estensioni Conclusioni Sperimentazioni di Sicurezza, A.A. 2009/2010 3 Sommario 1. 2. 3. 4. 5. 6. 7. 6/4/2010 Concetti di base Shamir IBS Teoria dei gruppi, curve ellittiche e pairing Boneh e Franklin IBE Sakai Ohgishi Kasahara IBS Considerazioni ed estensioni Conclusioni Sperimentazioni di Sicurezza, A.A. 2009/2010 4 Crittosistemi a chiave pubblica vs IBC o Nei PKC il legame tra una identità e una chiave è garantita dalla CA o Proprietà fondamentali di un IBC • La chiave pubblica di un utente risiede nel suo identificativo, ed è facilmente ricavabile da questo da qualsiasi altro utente • Non è necessario un repository di chiavi pubbliche • Le procedure di verifica di una firma o di cifratura di un messaggio richiedono soltanto rispettivamente l’identità del firmatario e del destinatario (oltre ad alcuni parametri globali di sistema) o Lo scopo è di risparmiare il costo della PKI per il legame ID-chiave o Purtroppo, gli IBC hanno anche alcune caratteristiche negative, che vedremo più avanti… 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 5 Cifratura – chiave pubblica Encryption msg m c k channel c m + k directory 6/4/2010 Decryption - k + - k k Key generation Sperimentazioni di Sicurezza, A.A. 2009/2010 msg seed 6 Cifratura – identity based Encryption msg c m id k channel Decryption m c + recipient’s identity msg - id k id k - Key generation 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 7 Firma digitale – chiave pubblica msg seed 6/4/2010 Signature generation m k k - m s channel m s Signature verification k valid/ invalid + + k k Key generation directory Sperimentazioni di Sicurezza, A.A. 2009/2010 8 Firma digitale – identity based msg Signature generation m id id m - s k k channel Signature verification m s id k valid/ invalid + sender’s identity - Key generation 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 9 Private Key Generator o La chiave privata viene generata a partire dall’ID dell’utente • In teoria, dato un ID qualunque, ciascun utente potrebbe calcolare la chiave privata corrispondente • Il crittosistema sarebbe così banalmente violato! o Necessità di una Trusted Third Party che generi chiavi private a partire dall’ID fornito e da una chiave segreta nota solo ad essa o Il Private Key Generator (PKG) ricopre questo ruolo in un IBC • Ovviamente è necessario un canale sicuro tra l’utente e il PKG per la trasmissione della chiave privata 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 10 IBE – IBS: schema generale o IBE ed IBS necessitano di 4 fasi fondamentali, le primi due comuni o Setup: il PKG inizializza alcuni parametri di sistema, che sono resi pubblici; durante questa fase viene anche selezionata la Master Key (MK), ossia la chiave segreta del PKG o Extract: dato l’ID di un utente e la MK, il PKG ricava una chiave privata KID IBS IBE o Encryption: un messaggio m viene cifrato a partire dall’identità del destinatario (ID) o Decryption: il messaggio cifrato viene decifrato usando la chiave privata KID 6/4/2010 o Signature generation: viene prodotta una firma σ da un messaggio m usando la chiave KID o Signature verification: ricevuti σ e m, si verifica se la firma è valida usando l’identificativo del firmatario (ID) Sperimentazioni di Sicurezza, A.A. 2009/2010 11 Sommario 1. 2. 3. 4. 5. 6. 7. 6/4/2010 Concetti di base Shamir IBS Teoria dei gruppi, curve ellittiche e pairing Boneh e Franklin IBE Sakai Ohgishi Kasahara IBS Considerazioni ed estensioni Conclusioni Sperimentazioni di Sicurezza, A.A. 2009/2010 12 Shamir IBS o L’idea di IBC è da attribuirsi ad Abi Shamir o In un articolo del 1984, “Identity-based cryptosystems and signature schemes”, introduce l’idea di utilizzare l’identificativo di un utente (e.g. l’indirizzo email) come chiave pubblica, al fine di evitare certificati e directory o Propone uno schema di IBS simile ad RSA o Auspica che un analogo schema di IBE possa essere costruito “At this stage we have concrete implementation proposals only for identity based signature scheme but we conjecture that identity-based cryptosystems exists as well and we encourage the reader to look for such systems” o Il primo schema di IBE sarà ideato 17 anni più tardi… 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 13 Shamir IBS: preliminari o Funzione totiente di Eulero φ(n) • è definita, per ogni intero positivo n, come il numero degli interi positivi minori o uguali ad n tali che sono coprimi con n. • Sia n=p∙q, p,q primi → φ(n) = (p-1)(q-1) o Teorema di Eulero • p,q primi, n=p∙q, 0<m<n • mwφ(n)+1 = m mod n, w arbitrario 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 Leonhard Euler 1707 - 1783 14 Shamir IBS: schema o Setup(): il PKG genera dei parametri di sistema • n prodotto di due primi p,q molto grandi • e numero grande, primo con φ(n) = (p-1)(q-1) • h funzione one-way o Extract(ID): • ID = (k)e mod n - ID è il digest della stringa identificativa o Signature generation(m, k): • t = re mod n, con r random • s = k∙rh(t,m) mod n • σ = <s,t> o Signature verification(m, σ, ID): • se =?= ID∙th(t,m) mod n 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 15 Shamir IBS: correttezza se = (k∙rh(t,m))e = ke∙reh(t,m) = ke∙th(t,m) = ID∙th(t,m) 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 (mod n) 16 Shamir IBS: sicurezza o k può essere calcolato facilmente dal PKG perché conosce p e q Dati: ID,e,n,p,q Incognite: k ID = ke mod n Vogliamo trovare un valore d t.c. ked = k mod n kwφ(n)+1 = k mod n (per il teorema di Eulero) e∙d = w∙φ(n)+1 → e∙d = 1 mod φ(n) → d = 1/e mod φ(n) φ(n) = (p-1)(q-1) k = IDd mod n o Chi non conosce la fattorizzazione di n non può ricavare facilmente k, quindi lo schema è sicuro assumendo la difficoltà dell’ Integer Factorization Problem (IFP) o Dalla firma non è possibile ricavare la chiave se si assume la difficoltà del Discrete Logartihm Problem (re mod n) 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 17 Sommario 1. 2. 3. 4. 5. 6. 7. 6/4/2010 Concetti di base Shamir IBS Teoria dei gruppi, curve ellittiche e pairing Boneh e Franklin IBE Sakai Ohgishi Kasahara IBS Considerazioni ed estensioni Conclusioni Sperimentazioni di Sicurezza, A.A. 2009/2010 18 Teoria dei gruppi: gruppo Gruppo {G,●} o Insieme di elementi g G affiancati dall’operatore binario ● o Assiomi di base: a, b G a b G • Chiusura • Associatività a (b c) (a b) c, a, b, c G e G | a e e a a, a G • Elemento identità • Elemento inverso a' | a a' a'a e, a G o Gruppo abeliano a b b a, a, b G • Commutatitività o Gruppo ciclico (→ abeliano) • Elemento generatore g G | a g k , k , a G • Tutti i gruppi ciclici finiti dello stesso ordine sono isomorfi • Es. Il gruppo {N,+} è un gruppo ciclico di ordine infinito generato da 1 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 19 Teoria dei gruppi: anello Anello {R,+,×} o È un gruppo abeliano rispetto all’operatore + o Proprietà rispetto all’operatore × • Chiusura a, b R ab R a(bc) (ab)c, a, b, c R • Associatività a(b c) ab ac, a, b, c R • Distributività o Ulteriori proprietà dell’operatore × ab ba, a, b R Anello commutativo • Commutatività i R | ai ia a, a R • Elemento identità Dominio a, b R ab 0 a 0 b 0 integrale • No divisore 0 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 20 Teoria dei gruppi: campo (1) Campo {F,+,×} o È un anello, con una proprietà addizionale per ×: a F {0}, a 1 F | aa 1 i • Elemento inverso o Un campo è un insieme cui si possono eseguire le 4 operazioni fondamentali (+,-,×,/) • L’insieme , con le 4 operazioni, è un esempio di campo o Se un campo F è finito il suo ordine deve essere pari a pn (|F| = pn) • p primo (caratteristica del campo), n intero positivo o I campi finiti sono detti campi di Galois (Évariste Galois: 1811-1832) • GF(p1), GF(p2), GF(p3), … per ogni p primo 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 21 Teoria dei gruppi: campo (2) o Campi “notevoli” • GF(p) = Fp = Zp = {0,1, …, p-1} residui modulo p, p numero primo • GF(2n) = F2n campi binari • • • Insieme di stringhe di bit di lunghezza n L’operatore + è lo XOR () tra bit L’operatore × è la moltiplicazione dei due polinomi binari che corrispondono ai due operandi. Il risultato deve essere ridotto calcolando il modulo rispetto al polinomio di grado più elevato esprimibile nel campo (implementazione con SHIFT e XOR) o I campi binari sono tra i più utilizzati in informatica perché le operazioni tra elementi sono eseguite più efficientemente da un calcolatore rispetto ad operazioni tra elementi di altri campi 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 22 Curve ellittiche: definizione o Una curva ellittica è definita tramite un’equazione del tipo: y 2 axy by x 3 cx 2 dx e o Oppure, più semplicemente: y 2 x 3 ax b o Una curva è definita su un gruppo G se i coefficienti e le variabili assumono valori in G o La definizione di tali curve sull’insieme dei numeri reali R risulta intuitiva e facilmente rappresentabile geometricamente 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 23 Curve ellittiche: addizione tra punti o I punti di una curva ellittica costituiscono una varietà abeliana • insieme degli zeri del polinomio in x e y che è anche un gruppo (e.g. {G,+}) o Calcolo di + su R • Errori di arrotondamento • Inefficienza o In applicazioni crittografiche si usano • Zp : curve prime • GF(2n) : curve binarie e.g. Nel caso di Zp, la formulazione della curva diventa: y 2 mod( p) x 3 ax b mod( p) 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 24 Curve ellittiche: moltiplicazione o Sia P un punto sulla curva o 2P = P + P o In generale • Q = nP = P + … + P (n volte) 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 25 Curve ellittiche: esempio su Zp o Esempio grafico dei punti di una curva ellittica su Z23 y 2 mod( 23) x 3 x mod( 23) o I punti sul piano sono le soluzioni dell’equazione in modulo 23 o L’applicazione dell’operatore + tra punti è definito in modo diverso rispetto a quello definito su R 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 26 Curve ellittiche: applicazioni o Elliptic Curve Cryptography (ECC) • La crittografia basata su curve ellittiche necessita di chiavi dalla lunghezza più limitata rispetto a tecniche crittografiche basate su campi finiti (160 vs 1024 bit) perché il problema dei logaritmi discreti (DLP) è di più difficile risoluzione nel contesto delle curve ellittiche • Per campi finiti esistono algoritmi di risoluzione ottimizzati • Per curve ellittiche è necessario usare algoritmi generici • Ovviamente, in entrambi i contesti, non si conosce un algoritmo che risolva DLP in tempo polinomiale o Pairing bilineari • Sono strutture matematiche che costituiscono il fondamento delle moderne tecniche di IBS e IBE 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 27 Pairing bilineari: definizione o Siano G1, G2, Gt gruppi ciclici dello stesso ordine o Una mappa bilineare è una funzione e : G1 G2 Gt o Un pairing bilineare è una particolare formulazione di una mappa bilineare (specifica scelta di G1, G2, Gt ) o Il termine deriva dal fatto che ad una coppia (pair) di elementi, ne viene associato un terzo o G1, G2, Gt sono ciclici e dello stesso ordine, quindi sono isomorfi 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 28 Pairing bilineari: proprietà o Un pairing è detto ammissibile se soddisfa le seguenti proprietà e(av, bu ) e(v, u ) ab , v G1 , u G2 , a, b • Bilinearità • Non-degenerazione e(v, u) 1, v G1 , u G2 • Computabilità se e è facilmente calcolabile o I pairing ammissibili sono gli unici usati nella specifica dei meccanismi di IBC o I gruppi usati nella definizione dei pairing sono, solitamente • Curve ellittiche • Curve supersingolari • Curve MNT • … 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 29 Pairing bilineari: storia o I pairing di Weil e Tate-Lichtenbaum sono i pairing più usati in ambito IBC o I pairing furono inizialmente usati per violare sistemi ECC • Menezes, Okamoto, and Vanstone 1993, MOV reduction • Frey, Ruck 1994, FR reduction o La prima applicazione “buona” fu il primo schema di IBE, di Boneh e Franklin (2001) Dan Boneh 6/4/2010 Mattew Franklin Sperimentazioni di Sicurezza, A.A. 2009/2010 30 Sommario 1. 2. 3. 4. 5. 6. 7. 6/4/2010 Concetti di base Shamir IBS Teoria dei gruppi, curve ellittiche e pairing Boneh e Franklin IBE Sakai Ohgishi Kasahara IBS Considerazioni ed estensioni Conclusioni Sperimentazioni di Sicurezza, A.A. 2009/2010 31 Boneh & Franklin IBE: preliminari o Nel seguito considereremo pairing del tipo G1 × G1 → G2 o Useremo un’operazione di hash map-to-point così definita • H : {0,1}* → G o Useremo anche una funzione hash inversa • H’ : G → {0,1}n o I dettagli implementativi di H,H’ saranno omessi 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 32 Boneh & Franklin IBE: setup, extract o Setup(): il PKG genera dei parametri di sistema • MK = s Zq • Ppub = sP, P punto in G1 • H1 : {0,1}* → G1 • H2 : G2 → {0,1}n • Parametri pubblici: <G1,G2,e,P,Ppub,H1,H2> • Parametri privati: <s> o Extract(ID): • QID = H1(ID) - public key • SID = sQID - secret key - 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 33 Boneh & Franklin IBE: encrypt/decrypt o Encrypt(m, ID): • QID = H1(ID) • r Zq • gID = e(QID, Ppub) • c = <rP, m H2(gIDr)> o Decrypt(c = <U,V>) • m = V H2(e(SID, U)) 6/4/2010 - G1 × {0,1}n - Sperimentazioni di Sicurezza, A.A. 2009/2010 34 Boneh & Franklin IBE: proprietà (1) o Correttezza • V H2(e(SID, U)) → m • e(SID, U) = e(sQID, rP) = e(QID, P)sr = e(QID, sP)r = e(QID, Ppub)r = gIDr • V = m H2(gIDr) • m H2(gIDr) H2(gIDr) = m 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 35 Boneh & Franklin IBE: proprietà (2) o Sicurezza: complicata da provare… • È stata provata nell’ambito del Random Oracle Model, un modello largamente accettato in crittografia ma delicato… • Si suppone che le funzioni H1 e H2 siano dei ROM • Sostituendo una funzione reale al ROM, alcuni algoritmi non garantiscono più le proprietà di sicurezza dimostrate nel ROM! • Schemi successivi di IBE sono stati provati nello Standard Model, che suppone l’uso di funzioni reali • Ad oggi, esistono molti schemi di IBE diversi, tutti basati su pairing 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 36 Sommario 1. 2. 3. 4. 5. 6. 7. 6/4/2010 Concetti di base Shamir IBS Teoria dei gruppi, curve ellittiche e pairing Boneh e Franklin IBE Sakai Ohgishi Kasahara IBS Considerazioni ed estensioni Conclusioni Sperimentazioni di Sicurezza, A.A. 2009/2010 37 SOK IBS: setup, extract o Setup(): • MK = s Zq • Ppub = sP, P punto in G1 • H1 : {0,1}* → G1 • Parametri pubblici: <G1,G2,e,P,Ppub,H1> • Parametri privati: <s> o Extract(ID): • QID = H1(ID) - public key • SID = sQID - secret key - 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 38 SOK IBS: sign/verify o Signature generation(m): • r Zq • S1 = SID + rH1 (m) • S2 = rP • σ = <S1, S2> - G1 × G1 o Signature verification(m,σ,ID) • QID = H1(ID) • e(QID,Ppub) e(H1(m),S2) =?= e(s1,P) 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 39 SOK IBS: proprietà o Omesse… 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 40 Sommario 1. 2. 3. 4. 5. 6. 7. 6/4/2010 Concetti di base Shamir IBS Teoria dei gruppi, curve ellittiche e pairing Boneh e Franklin IBE Sakai Ohgishi Kasahara IBS Considerazioni ed estensioni Conclusioni Sperimentazioni di Sicurezza, A.A. 2009/2010 41 Problemi degli IBC o Il primo problema concerne l’efficienza degli algoritmi di IBE/IBS • RSA è circa 10 volte più veloce nella generazione delle firme e addirittura 150 volte più veloce in fase di verifica • I test sono condotti su un Intel™ Quad-Core Xeon 2.5 GHz, 4GB di RAM e si riferiscono allo schema IBS di Hess (millisecondi) • Libreria C: http://crypto.stanford.edu/pbc/ RSA IBS Operation 6/4/2010 μ σ μ σ Generate 2.026 0.164 25.395 0.045 Verify 0.1 0.014 15.012 0.051 Sperimentazioni di Sicurezza, A.A. 2009/2010 42 Problemi degli IBC o Il problema più grave inerente agli IBC è quello del key escrow o Se il PKG viene attaccato e la sua chiave privata violata, l’attaccante può produrre firme valide a nome di un qualunque altro utente di cui conosca il nome (l’user ID) o Questo non accade in sistemi classici a chiave pubblica, dove se la chiave della CA è violata, l’attaccante può produrre certificati a nome della CA ma non può firmare per conto di altri o Il key escrow è il più grande ostacolo alla diffusione degli IBC 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 43 Contromisure possibili (1) o Contro il key escrow • Lo schema di IBS di Cheng, Zhang e Kim attenua il problema del key escrow, permettendo di tracciare eventuali truffe attuate dal PKG e da chi ne rubi la master key • Gestione gerarchica dei PKG. HIBC, Hierarchical ID-based Cryptosystem. • • 6/4/2010 Un root PKG distribuisce a diversi PKG secondari la responsabilità di gestire le richieste di generazione di chiavi per specifici sottodomini di utenza. Il root PKG genera le chiavi per i PKG di dominio. Per comunicare tra loro, due utenti devono conoscere soltanto i parametri dei rispettivi root PKG per comunicare. Il vantaggio di un’architettura gerarchica è, oltre che la distribuzione del carico, la proprietà di damage control: la violazione di un PKG di dominio non compromette i segreti dei PKG di più alto livello. Ovviamente si perde in parte il vantaggio di evitare una PKI complessa Sperimentazioni di Sicurezza, A.A. 2009/2010 44 Contromisure possibili (2) o Per migliorare l’efficienza • Firme aggregate e verifiche batch • • Firme aggregate: Dati n oggetti con altrettante firme distinte, tali firme possono essere aggregate in una sola (risparmio di spazio). È da notare comunque che le firme IBS sono più piccole rispetto alle firme RSA per pari livello di sicurezza. Verifiche batch: Date n firme di altrettanti oggetti distinti, un’unica procedura di verifica, in tempo sublineare in n, può essere effettuata • … 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 45 Sommario 1. 2. 3. 4. 5. 6. 7. 6/4/2010 Concetti di base Shamir IBS Teoria dei gruppi, curve ellittiche e pairing Boneh e Franklin IBE Sakai Ohgishi Kasahara IBS Considerazioni ed estensioni Conclusioni Sperimentazioni di Sicurezza, A.A. 2009/2010 46 Conclusioni Gli IBC hanno lo scopo fondere i concetti di chiave pubblica ed identità, che molto spesso sono “appaiati” Si evitano certificati Non è necessaria una PKI complessa (risparmio di denaro) Sono schemi molto sicuri e relativamente efficienti La proprietà inerente del key-escrow ne ostacola la diffusione I concetti matematici su cui si basano sono piuttosto complessi La ricerca nell’ambito degli IBC è molto attiva Si auspica che, nel prossimo futuro, i problemi di IBC siano risolti o mitigati 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 47 Contatti o È disponibile una vasta letteratura su IBC o Esistono alcuni survey introduttivi molto completi o La libreria C di Stanford è una delle poche librerie sui pairing disponibile • Ne esistono altre in Java, ma decisamente meno efficienti o Per qualunque informazione, richiesta di chiarimento o di materiale aggiuntivo, contattatemi [email protected] 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 48 Sperimentazioni di Sicurezza, A.A. 2008-2009 Identity based Cryptosystems Grazie per l’attenzione! Speaker: Luca Maria Aiello, PhD student Università degli Studi di Torino, Computer Science Department Corso Svizzera, 185 – 10149, Torino, Italy [email protected] 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 49 ©2009 by Luca Maria Aiello. Permission to make digital or hard copies of part or all of this material is currently granted without fee provided that copies are made only for personal or classroom use, are not distributed for profit or commercial advantage, and that new copies bear this notice and the full citation. 6/4/2010 Sperimentazioni di Sicurezza, A.A. 2009/2010 50