Sixième journée à Hyberabad - début d'ICISS2008

Historique

Paris -> Hyderabad : premières galères
Première journée à Hyberabad - tristes constats
Deuxième journée à Hyberabad - la vie de touriste

Troisième journée à Hyberabad - shopping & farnienté

Osman Sagar Lake - dernières déceptions
Cinquième journée à Hyberabad - shopping & les derniers problèmes
Sixième journée à Hyberabad - début d'ICISS2008

Sixième journée à Hyberabad - début d'ICISS2008

Et c'est parti pour la première journée de la conférence ; quand j'aurais mis ça au propre, je remettrai à jour l'article pour les prises de notes ... mais je le poste déjà à cause de la partie "Fin des problèmes ? " :)

Matin

NB people: 40

Secure Multiparty Computation

Outline

- Definitional issues
- taxonomy of SMC research
- landmark results in SMC
- Outlook and future directions

A) Definitional issues

General Objectives:
to overlay a specified secure distributed system S over the real (insecure) network N
-> connect back boxes (nodes) with secure channel communication

what is security? what is secure computation?
- integrity, authentication
mathmematical proof -> mathematical specification
full implemenation of perfect security is impossible
-> only partial security ; requiered assumptions

- Definition of basic examples
Example A)sender S, Receiver R
-> insecure channel ; intermediate nodes
-> overlay a virtual secure channel between S & R

Example B) broadcast channel
-> simulating broadcast with mutliple unicast
-> not fully secure if active faults (K-holes)

Example C) privacy preserving Statistics
-> virtual secure nodes (SN) that compute the means
-> protocal : ForAll Pi, send Xi to SN; SN: send the mean
=> spec: easy ; implementaion: ...

General SMC: So Far

given (S,N) ;: compute
prtocol qhi that emulates N ov S runing phi

SMC: Models & def
network: inter-processes communication (Directed Graph) Timing: (a)syncrhonous nrets
prtocol: tyring machines; synch. systems
complexity aspects
 -synchronous
- communication & robustness: bound by a upper limit

Model (control)
system failures:
- advesary
- corruption ; K < N intenal nodes (upp_limit(K)=N)
- uncertainity in the set of currupted nodes
=> probabilties
runtime: adverary my choose a malicious node

Secuity:
- strengh in the sim. of S on N
e.g.: P: S over N is secure if for every adversary A corrupting N, there existe B corrupting S such as the output distribution ensembles (which includes the view of B) are similar.

General SMC: Thus Far
Given the following:
- An ideal system S influenced by B than run prtocol qhi
- A real network N influenced by A   
-> Compute the protocol phi

B) taxonomy of SMC research

Tax. Adversary Models
- Computational Power
probabilistic polynomial-time bounder, unbounded
- Corruption-type
passive, fail-stop, byzantine
- Corruption Capacity
Threshold: percentage of nodes that can be corrupted <- bound
Non-Threshold
- Mobility (?)
Static
Adaptive
Mobile

Security Model
- Prefect Security
perfect simulation
- Computational Securtiy
S&N: computationally indistinguishable
- Statitical Security
S&N: statiscally close


Summary of Various Models
- Network Model: IPC/timing
- Protocol Model: Basic pstulates/Assumptions (Deterministic, randomized, ...) ; Composability (standalone, sequentially composable, concurrently ...)
- Adversary Model: Computational Power, Corruption Type, Corruption Capacity, Mobility
- Security Model: Perfect, Unconditional, Statistical, Computational
- Inquiry/Objective: def, possiblity, feasibility, optimality

Challenges in Example A: secure channel

Shannon Pessimism
Pessimism 1: a physical secure chanel is necessary for secure communication

invariant: adversary knows all that the receiver R knows
if R knows  (a finite amount of) secrets the adv does not kno
Pessimism 2: even in the presence of a secure chanel, the overall secure transmission capacity is essentially same as the capacity of the secure channel
=> key length must be same as channel stream length

Alleviating pessimism 1: cryptographic solution
shannon: hold if the message is to be kept secure forever ; but most of the time, not forever but for a given time is required
=> one-way fonctions
=> Diffie Hellman Key Exchange

Alleviating pessimism 2: cryptographic solution
pseduorandom generators (PRG): expand any key to long keys
=> PRG need one-way functions
=> we need one-way functions

C) landmark results in SMC

distributed algorithm solution
distribution helps in improving security
perfect security: sometimes possible

key ingredient: secret sharing

perfect secure communication
[Doleve et al. Protocol]
    split, send using diff. channels --- collect, unsplit
    probability that the attackers cannot get all the shares

t-Secret sharing
[Shamir protocol, 1979]
    t-degree polynomial p() ;  secret =p(0) ; share p(1), p(2) ... p(n), n >= t

Quantum solution
quantum mechanics : measures modifie the state of the system
-> detectable anomalies in case of eavsdropping

so far:
- passive adversary model;
- byzantine adversary model

Challenges in example B

broadcast 1 out of 3: impossibility
broadcast 1 out of 4: req. n>3t, t=number byzantine
So far:complete sync net ; threashold unbounded

2t+1 connectivity is necessary (and suifficient if n>3t)
(non-threshold)
> even a single fail-stop is not tolerable!

athenticated  byznatine agreement (ABA)
- computationnalu bounded adv. model
- digital signautres
- fault tolerance: t < n

ABA protocol for 1 out of 3
composability of ABA : if n < 3t+1, no ABA protocol can be composed
- combining secure protocol => not always secure
- modularity of Secure Software design is markedly different

Simulating channels is not all!

SMC: requiered simulating the entire system S -> simulate secure processors!

- simulating secure nodes
the data in each memory register of  the secure virtual sever
=> secret shared and store accros several nodes
CPU instructions: Network protocols .. but slower!

- secure addition protocol: make ADD without sharing xi on the network
passive adv. case: send rn=xi - sum(ri, i=0..n-1) ; sum all rn received and send it as y ; sum all y => sum xi
fail-stop adv. case: t-secret share
req: n>2t
byzantinve adv. case: req: n>3t ; t-veriafbly secet shares
    probability correctness if n>2t

- secure mutliplication protocol
cryptographic solution: uses oblivious transfer
non-crypto: uses secure degree reduction

D) Outlook and future directions

Generality vs efficiency
compiler like: not adapted to a specific solution
veriafiability vs workability
few CPU instruct: verifiable ... bu usable in reality?

Après Midi

Symbolic verification of cryptographic protocols: theoretical issues

Protocols and theire analysis

The environment
- Model: Asaveri (ie Alice :d), Bhairavy (Bob), sahana (the trusted server) & Intruder
- Security assumption 1: total eavesdropping
- Security assumption 2: the intruder control the public channel
- Encryption is supposed perfect

Protocols
- examples of several incorrect protocols
- Security assumption 3: the intruder may be a legitimate user

Several Conclusion
- freshness is important
- proving correctness is hard

Dolev-Yao Model

- symboles analysis model
- malicious active attacker
- secrecy problem:
 search for an attacker such that
- honest agents respect the protocol
- attacker messages is made from what it knows
- attackers can derive the secret


based on a proof model
notion of non nominal proof
notion of normalization rules
-> the attacker is bounded
using XOR ... more compicated

active attacker: can add proofs in the system
unboundness -> undecidability

Conclusion

Symbolic analysis & verification: thriving research
theorticial issues but tools from logiic & automata theory are promising

Fin des problèmes ?

Eh oui, c'est avec une petite lueur qui brille dans mes yeux que j'écris cette partie de l'article. Il semblerait que les problèmes vont se régler today (ie officiellement demain :d)

L'aéroport

Alors, là, je dirai aucun commentaire, car il faut rester content :d
Mais voici quand meme le timeframe de cette fin d'après-midi
- 16h30, la conférence finie en avance. Chouette, je cours pour prendre l'auto-rickshaw et arriver avant 17h30 : pour appelle l'aéroport. Car en effet, ils ont pas appellés today (j'avais précisé ça à l'hotel) et ne sont pas venus
- 16h50 : téléphone occupé
- 17h10 : téléphone occupé ; j'essaye un autre numéro trouvé sur le site de KLM, même problème
...
j'essaye le portable sur la fiche de constatation : ne marche pas sur le téléphone de l'hotel  ... j'essaye sur mon portable, oui !!! Bon, je raccroche de suite et j'appelle avec un cellphone indien !
"ok, I call you back at the hotel number" (euh, j'ai déjà entendu ça :)
- 17h50 .. rien ; je rappelle "the guy didn't call you? ok, I give you his number".
- 18h00, j'appelle "I'm on the way"
- 18h15, il rappelle car il ne trouve pas l'hotel ...
Comment est-ce possible ? Moi qui ne suis pas d'hyderabad, ni indien, je le trouve !!!!
- 18h30, le gars prend ma valise et ok pour ramener la nouvelle vendredi au plus tard !!

Ouf :) Un problème théoriquement réglé

La conférence

bon, je n'ai pas trouvé le transaction ID cet après-midi alors que je suis sur de leur avoir envoyé... je rechecke ce soir au calme, et le trouve en tant qu'envoyé :( :( Bon, il me prenne pour un idiot, eux aussi ???
Je leur ait FW et noté sur mon Iphone. On verra demain mais cela doit être okay !

J'adore quand cela devient okay :) :)

Par contre, je me demande vraiment si ces gens (ICISS2008 et KLM hyderabad) sont vraiment compétents :(