Crittografia Visuale

Seminario Sicurezza a.a. 2001/2002

Barbara Anconelli

La Crittografia Visuale Tecnica crittografica per

cifrare immagini Basata SOLO sul sistema visivo

umano Fornisce anche

meccanismi di autenticazione meccanismi di identificazione

Introduzione Scenario:

Insieme P di n partecipanti “dealer” D Segreto S (un’immagine)

Idea: dealer genera n share contenenti un’informazione parziale su S e le distribuisce agli n partecipanti. La sovrapposizione delle n share permetterà la ricostruzione dell’immagine S.

Esempio

Ciascuna share da sola non dà alcuna informazione sull’immagine di partenza!

Share 1

Share 2

Originale Ricostruita

Schema a soglia (k,n) Schema di condivisione di un segreto

a soglia (k,n) con k<=n Se k=n: schema con il numero di partecipanti=numero

di share indispensabili per ricostruire l’immagine Se k<n il segreto S può essere ricostruito

sovrapponendo solo k delle n share a disposizione n-k share sono prive di informazione

Struttura di accesso: definisce quali partecipanti sono in grado di recuperare l’immagine e quali no

Partecipanti autorizzati Partecipanti non autorizzati

Codifica di un pixel Ipotesi:

Immagini in bianco e nero Schema a soglia (2,2)

Soluzione 1: un pixel bianco dell'immagine originale

viene codificato con un pixel bianco in entrambe le share

un pixel nero dell'immagine originale viene codificato con un pixel bianco in una share ed uno nero nell'altra

Esempio soluzione 1

Codifica di un pixel Ogni share contiene troppa

informazione! Soluzione 2:

p è bianco: la coppia di sottopixel usata nella codifica è uguale per le due share

p è nero: la coppia di sottopixel utilizzata in una share è complementare a quella utilizzata nell'altra share

Esempio soluzione 2

Osservazioni Deformazione dell'immagine in larghezza Scelta della codifica per ogni pixel casuale Perdita di contrasto dell'immagine ricostruita

è ½ -> il bianco appare come “grigio” Sicurezza:

ogni coppia di sottopixel è costituita da un sottopixel bianco ed un sottopixel nero, indipendentemente dal colore del pixel originale

osservando una coppia di sottopixel in una share, NON è possibile risalire al colore del corrispondente pixel nell'immagine originale

Codifica di un pixel Soluzione 2: caso particolare del più

generico schema di crittografia visuale (VCS)

Soluzione 3: ogni pixel viene codificato da m sottopixel -> VCS (Visual Cryptography Scheme)

p è bianco: i sottopixel usati nella codifica sono uguali per le due share.

p è nero: i sottopixel utilizzata in una share sono complementari a quelli utilizzati nell'altra share.

Vediamo il caso m=4 m = espansione del pixel

Esempio soluzione 3Possibili codifiche di un pixel bianco :

Esempio soluzione 3Possibili codifiche di un pixel nero :

Osservazioni non ho distorsione ma l'immagine

ricostruita risulta quattro volte più grande Cercare di minimizzare m per ridurre lo spazio

per la memorizzazione perdita di contrasto dell'immagine

ricostruita è ½ -> il bianco appare come “grigio”

Sicurezza del VCS: stesse considerazioni del caso m=2 ma probabilità di risalire al colore del pixel ancora minore

Matrici di base Immagine originale = collezione di pixel

bianchi e neri Codifica:

Ogni pixel trattato separatamente Per rappresentare la codifica di un pixel:

matrice booleana S righe = share, colonne = sottopixel Si,j = 1 -> nero, Si,j = 0 -> bianco

Decodifica: Sovrapposizione equivale a OR booleano delle

righe

Esempio di matrici di baseSchema a soglia (2,2) con m=2

Matrici di base 2 matrici S0 e S1 (nxm)

Riga i di S0 (S1) rappresenta la codifica base di un pixel bianco (nero) per il partecipante i

Codifiche diverse di un pixel date dalla permutazione delle colonne di S0 e S1

Distribuzione delle share: riga 1 al partecipante 1 …

Immagine in toni di grigio Ipotesi:

Immagine segreta in toni di grigio Share e immagine ricostruita formate

sempre da pixel bianchi e neri Diverse tonalità di grigio ottenute in

base al numero di pixel neri sovrapposti

Esempio: schema (2,2) con m=4 e 3 toni di grigio (bianco, nero e grigio)

Esempio: 3 toni di grigio

Esempio immagine in toni di grigio

CVCS (Color Visual Cryptography Scheme)

Ipotesi Immagine segreta a colori Pixel delle share e dell’ immagine ricostruita

a colori Sovrapposizione dei colori:

composizione RGB c1=(r1, g1, b1), c2=(r2, g2, b2)

Legge:

255

2*1,

255

2*1,

255

2*1 bbggrrc

Esempio immagine a colori

Esempio

Share 1 Share 2

Cenni di Crittografia Visuale estesa

Creazione di share contenenti immagini significative, ma comunque diverse dall’originale.

Schema a soglia (2,3): la share c non porta informazione

Autenticazione ed Identificazione Visuale Scopi della crittografia:

Garantire la confidenzialità dei dati Fornire meccanismi di autenticazione

Autenticazione dei messaggi (autenticazione) Autenticazione di entità (identificazione) Autenticazione del tempo

Scenario: 2 utenti S (Sally) e H (Harry) vogliono

comunicare su un canale pubblico a cui ha accesso un nemico P (Paul) che ha la capacità di intercettare e manipolare i dati

Motivazioni dell’uso di una trasparenza

e’ molto meno costosa di un sistema elettronico ed e’ abbastanza piccola

e’ semplice da produrre e i sistemi che la usano non basano la loro sicurezza su dispositivi esterni

I processi di identificazione e autenticazione diventano molto semplici

L’utente non ha la necessita’ di memorizzare una password o di consultare un codebook

Modello per autenticazione Requisiti:

P non puo’ generare M’ e far credere ad H che provenga da S;

P non puo’ modificare M in M’ e far credere che M’ provenga da S;

Ipotesi: S, H non hanno risorse di calcolo: protocollo

basato solo sulle capacita’ naturali di H; S, H hanno una potenza di calcolo e capacita’ di

memorizzazione polinomiali in n (parametro di sicurezza del protocollo)

Modello Inizializzazione:

S genera una stringa random r S produce share T(r) e un’informazione ausiliaria A(r) S invia T(r) e A(r) ad H S invia ad H un’insieme di istruzioni (pubbliche) che

P non puo’ pero’ modificare Comunicazione:

S genera C(M,r) e lo trasmette lungo il canale pubblico

P intercetta C e lo puo’ modificare in C’ H riceve C e in base a T(r) e A(r) (seguendo I) decide

se accettarlo o no

Metodo dell’area nera e dell’area dell’informazione S prepara M contenente:

area nera area dell’informazione: contiene il messaggio

S genera due share s, t: t contiene le informazioni su quale sia l’area

nera e quale quella dell’informazione e viene inviata sul canale privato

s viene inviata ad H sul canale pubblico H riceve le share e le sovrappone come

da istruzioni di S

Esempio

Considerazioni Possibili modifiche di P:

Cambiare la posizione di sottopixel neri Cambiare il numero di sottopixel neri

P non conosce la posizione dell’area nera e attacchi dei tipi 1 e 2 porterebbero ad avere pixel bianchi nell’area nera -> H se ne accorge!

Estensione a k aree nere e di informazione per avere maggiore sicurezza

Bibliografia Web server per realizzare applicazioni pratiche di

crittografia visuale: http://www.dia.unisa.it/VISUAL/

“An Introduction to Visual Cryptography”, di Douglas R. Stinson

“Constructions and Properties of k out of n visual secret sharing Schemes”, di E.R. Verheul and H.C.A. van Tilborg

“Visual Authentication”, di M. Naor and Benny Pinkas

“Visual Cryptography” di M. Naor and A. Shamir