Proactive Secret SharingOr:How to Cope With Perpetual LeakageWhat is Secret SharingWhy Do We Need Proactive Sharing?System AssumptionsRemoving an Adversary from a ServerDefinitionsCryptographic ToolsCryptographic ToolsWith VSS there is more information to attack?!?Periodic Share RenewalBasic Share Renewal ProtocolBasic Share Renewal Protocol(2)Share Renewal Protocol in the Presence of Active AttackersShare Renewal Protocol in the Presence of Active Attackers(2)Resolving AccusationsResolving Accusations(2)Share Recovery SchemeDetecting CorruptionBasic Share Recovery ProtocolShare RecoveryTotal Protocol for Proactive Secret SharingApplicationsSummaryProactive Secret SharingOr:How to Cope With Perpetual LeakagePaper by Amir HerzbergStanislaw JareckiHugo KrawczykMoti YungPresentation byDavid ZageWhat is Secret Sharing• Basic Idea ((2, 2)-threshold scheme):– Two friends find a map to buried treasure!!– Who do we trust?– Neither, each gets a “share” of the map• Based on threshold cryptographyWhy Do We Need Proactive Sharing?• Secret sharing is a fundamental tool for protecting sensitive data.• How do we protect the data from gradual server break-ins?– Renew data – Not good for long lived data– Renew the Secret – Good!• Attacker must compromise k+1 servers in a time period instead of the entire life of the system.System Assumptions• System– (k+1, n)-threshold scheme– Secure encryption and signatures exist– Synchronized, secure broadcasts over a common medium– Data is actually destroyed when erased• Mobile Adversary– Byzantine corruption can occur at any time– Adversary can corrupt no more than k out of n servers, where k < n/2– Adversary is connect to the communication medium but cannot interfere with communicationRemoving an Adversary from a Server• Adversaries are removable through reboot procedures• Honest servers always detect and remove misbehaving servers• DOS attacks on the communication medium not taken into account (further papers address this using asynchronous systems)Definitions• Semantically Secure– Security is measured in terms of entropy and change– The scheme is semantically secure if for any function k computable on the secret, the difference in the probability of learning information between rounds is negligible.• Robust– Scheme guarantees the correct reconstruction of the secret at any time• Tolerates up to k Byzantine faultsCryptographic Tools• Shamir’s Secret Sharing– Dealer chooses a function f of degree k over a finite field where f(0) = secret– Dealer calculates vi= f(i) and secretly sends vito the server i.– The secret can now be reconstructed with k+1 vipieces and polynomial interpolationCryptographic Tools• Verifiable Secret Sharing– g is an element of a the finite field the equation k was chosen from– Values gfiare broadcast to every server before the secret share is broadcast– When a server receives a secret share it checks:– If the equation holds, the share is a valid share.kiiikiffffxggggg )...()())((2210=With VSS there is more information to attack?!?• Information can be learned from each of the gx• What can be done:– Use a different scheme where extra information is already released• ElGamal Signatures– Place the secret X in an “envelope”• Encode the secret in a longer bit string sPeriodic Share Renewal• Each server has a pair of public and private keys used for secure communication.– Assumption: Attacker cannot modify the keys• System initialization– The secret is encoded using Shamir’s secret sharing and securely distributed to all servers– Time periods for renewal are set arbitrarily by system administratorBasic Share Renewal Protocol• Each server Pi picks k random numbers from the finite field and creates a polynomial of degree k• For all other servers Pj, Pi secretly sends out to Pj• Pi computes the new share by:• Pi updates its share and erases all other datakikiiizzzzδδδδ+++= ...)(2211)( jiδ)...(21)1()1(niiititixxδδδ++++←−−Basic Share Renewal Protocol(2)• Solves share renewal in the face of a passive adversary• If all of the servers follow the protocol, then the share renewal protocol is correct, robust and is secret– Each new round produces a valid set of secret shares– Any k+1 servers can re-create the secret at any time– With k or less shares, no information is learnedShare Renewal Protocol in the Presence of Active Attackers• Each server Pi picks k random numbers from the finite field and creates a polynomial of degree kEach Pi also computes for each k• Pi computes and broadcasts the set of ε’s and δ signed with Pi’s signaturekikiiizzzzδδδδ+++= ...)(2211)( jiδimgimδε=Share Renewal Protocol in the Presence of Active Attackers(2)• Pi computes the new share by:• and checks the validity by computing:• If the messages are correct, Pi broadcasts an accept message• If not Pi broadcasts an accusation against the misbehaving server(s))...(21)1()1(niiititixxδδδ++++←−−kiiijkjjijg )...()()(221)(εεεδ=Resolving Accusations• If faulty server is recognized– Do not use the polynomial broadcast by the server– Reset the server to “expel” the adversary• Three types of possible faults:– Incorrect message format– Zero or greater than One correct message from a server¾ Verifiability equations do not match•3rdtype of fault requires extra effort to handleResolving Accusations(2)• If Pi accuses Pj of cheating, Pj must “defend” itself– If Pj sent a correct , then it exposes this value and all servers can check with the ε values already published during the protocol.• If Pj defends itself, then Pi marked as the fault server, else Pj is marked.• The share renewal equation becomes:)(ijδ∑∉−−+←iBjjititixxδ)1()1(Share Recovery Scheme• Severs must make sure other servers have not had their keys compromised. Otherwise an adversary could cause the secret to be lost by destroying n-k keys.• Without recovery, we loose security• For practical schemes:– During reboot, a server will loose it share and need recoveryDetecting Corruption• During initialization, each server stores a the set offor all the servers current shares.• During the secret share update, this set of exponents is also updated in a similar fashion.• If during the update phase, the value of the new x received and the one calculated do not match,
View Full Document
Unlocking...