Secret Sharing Schemes and Equivalency in Network Security
Delve into the world of secret sharing schemes and their importance in network security. Explore the concept of encoding and decoding, the mathematical basis behind different schemes, and the operational equivalency among various methods like hyperplane geometry, polynomial interpolation, bitwise XOR, information dispersal, and erasure codes. Uncover the efficiency, security, and practical applications of maintaining secrets through these innovative schemes.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
DIMACS Workshop on Coding Theoretic Methods for Network Security 9:15 - 10:15 AM, April 1st, 2015 Based on How to Maintain a Secret by Greg Dhuse and Jason Resch Jason Resch Cleversafe Research
Outline Secret Sharing Schemes Rebuilding Lost Data Risks and Costs Why it s Necessary A new way to Rebuild Implementation Details Efficiency and Security Other Applications
Secret Sharing Schemes Secret Sharing Schemes Convert secret information (the secret) into n shares where each is given to one of n shareholders The secret may be recovered from any t of the shares, where 1 t n Importantly: no information can be gleaned (practically or in some cases theoretically) from fewer than t shares Provides excellent confidentiality and availability: Secret remains confidential despite (t 1) exposures Secret remains available despite (n t) erasures
Comparison of Schemes Name Mathematical Basis Space Time Security O(n t l) O(n t l) Blakley Hyperplane Geometry Informational O(n t l) O(n l) Shamir Polynomial Interpolation Informational O(n l) O(n l) XOR Bitwise Exclusive-or Informational O((n / t) l) O(n l) SSMS Information Dispersal Computational O((n / t) l) O((n - t) l) AONT-RS Erasure Codes Computational
Equivalency of the Schemes The aforementioned secret sharing schemes were first described in terms of very different math: Hyperplane geometry, polynomial interpolation, bit- wise xor, information dispersal, and erasure codes Yet, all of these schemes are operationally equivalent: Each is a system of linear equations in a finite field Encoding and decoding work identically, the only difference is how the linear equations are formed
Encoding and Decoding In each of these schemes: Encoding is performed using a system of n equations to derive a set of n solutions (each solution being a share) Decoding uses at least t solutions to solve for the unknowns (the variables) used in the equations This is significant because the same math that enables efficient and secure rebuilding applies to all schemes
Shamir as a Linear SSS Define a random (t 1) degree polynomial f(x) Encode the secret s as one of the coefficients, for example as the y-intercept: f(x) = r1x4 + r2x3 + r3x2 + r4x1 + sx0 Pick n distinct values of (x > 0) to evaluate f(x): share1 = f(1), share2= f(2), , sharen = f(n) The polynomial can be solved with any t solutions: Use polynomial interpolation to solve the equation, and then recover the coefficients (including the secret)
Shamir as a Linear SSS 5 coefficients 9 solutions of f(x) 9 5 encoding matrix V 10 11 12 13 14 s10 + r411 + r312 + r213 + r114 s 20 21 22 23 24 s20 + r421 + r322 + r223 + r124 r4 30 31 32 33 34 s30 + r431 + r332 + r233 + r134 r3 = 40 41 42 43 44 s40 + r441 + r342 + r243 + r144 r2 50 51 52 53 54 s50 + r451 + r352 + r253 + r154 r1 60 61 62 63 64 s60 + r461 + r362 + r263 + r164 70 71 72 73 74 s70 + r471 + r372 + r273 + r174 80 81 82 83 84 s80 + r481 + r382 + r283 + r184 90 91 92 93 94 s90 + r491 + r392 + r293 + r194
Blakley as a Linear SSS Define a choose a point p in t-dimensional space Select p such that it encodes the secret, e.g. as one of the t coordinates that specifies p Generate n hyperplanes of dimensionality (t 1) that intersect point p, the n hyperplanes are the shares To find a random hyperplane intersecting p having coordinates = (s, x2, x3, x4, x5), generate t random coefficients (a1, a2, a3, a4, a5), the plane equation is: y = a1s + a2x2 + a3x3 + a4x4 + a5x5 sharei = yi and the coefficients (ai,1, ai,2, ai,3, ai,4, ai,5)
Blakley as a Linear SSS 5 coordinates 9 solutions (y1 yn) 9 5 encoding matrix V sa1,1 + x2a1,2 + x3a1,3+ x4a1,4 + x5a1,5 a1,1 a1,2 a1,3 a1,4 a1,5 s a2,1 a2,2 a2,3 a2,4 a2,5 x2 sa2,1 + x2a2,2 + x3a2,3+ x4a2,4 + x5a2,5 x3 a3,1 a3,2 a3,3 a3,4 a3,5 = sa3,1 + x2a3,2 + x3a3,3+ x4a3,4 + x5a3,5 x4 a4,1 a4,2 a4,3 a4,4 a4,5 sa4,1 + x2a4,2 + x3a4,3+ x4a4,4 + x5a4,5 x5 a5,1 a5,2 a5,3 a5,4 a5,5 sa5,1 + x2a5,2 + x3a5,3+ x4a5,4 + x5a5,5 a6,1 a6,2 a6,3 a6,4 a6,5 sa6,1 + x2a6,2 + x3a6,3+ x4a6,4 + x5a6,5 a7,1 a7,2 a7,3 a7,4 a7,5 sa7,1 + x2a7,2 + x3a7,3+ x4a7,4 + x5a7,5 a8,1 a8,2 a8,3 a8,4 a8,5 sa8,1+ x2a8,2 + x3a8,3+ x4a8,4+ x5a8,5 a9,1 a9,2 a9,3 a9,4 a9,5 sa9,1 + x2a9,2 + x3a9,3+ x4a9,4 + x5a9,5
XOR as a Linear SSS Choose (t 1) random bit strings of length equal to s The first (t 1) shares are these random bit strings The final share is the bitwise exclusive-or of all the random bit strings together with the secret Achieves Shannon perfect secrecy Analogous to a one-time-pad with (t 1) keys To decode, xor all of the shares together
XOR as a Linear SSS 5 bit strings 5 shares 5 5 encoding matrix V 1 0 0 0 0 r1 r1 0 1 0 0 0 r2 r2 0 0 1 0 0 r3 r3 = 0 0 0 1 0 r4 r4 1 1 1 1 1 s r1 + r2 + r3 + r4 + s
XOR as a Linear SSS 5 bit strings 9 shares 9 5 encoding matrix V 1 0 0 0 0 r1 r1 0 1 0 0 0 r2 r2 r3 0 0 1 0 0 r3 = r4 0 0 0 1 0 r4 s 1 1 1 1 1 r1 + r2 + r3 + r4 + s 20 21 22 23 24 s20 + r421 + r322 + r223 + r124 30 31 32 33 34 s30 + r431 + r332 + r233 + r134 40 41 42 43 44 s40 + r441 + r342 + r243 + r144 50 51 52 53 54 s50 + r451 + r352 + r253 + r154
SSMS as a Linear SSS Secret Sharing Made Short (SSMS) combines Rabin s Information Dispersal, Encryption, and Shamir s SSS First encrypt the secret with a random key Second, disperse the encrypted data with the IDA Third, encode the key using Shamir s SSS Shareholders get an IDA fragment and a Shamir share Unlike Shamir, Blakley, and XOR, SSMS is conditionally secure: Security depends on the security of the cipher, and the limited computational resources of adversaries
Rabin IDA as a Linear SSS 5 data elements 9 fragments 9 5 encoding matrix V 10 11 12 13 14 d110 + d211 + d312 + d413 + d514 d1 20 21 22 23 24 d120 + d221 + d322 + d423 + d524 d2 30 31 32 33 34 d130 + d231 + d332 + d433 + d534 d3 = 40 41 42 43 44 d140 + d241 + d342 + d443 + d544 d4 50 51 52 53 54 d150 + d251 + d352 + d453 + d554 d5 60 61 62 63 64 d160 + d261 + d362 + d463 + d564 70 71 72 73 74 d170 + d271 + d372 + d473 + d574 80 81 82 83 84 d180 + d281 + d382 + d483 + d584 90 91 92 93 94 d190 + d291 + d392 + d493 + d594
AONT-RS as a Linear SSS All-or-Nothing Transform Reed Solomon (AONT-RS) combines Rivest s AONT with Reed-Solomon coding First encode secret with AONT Second, encode redundancy with Reed-Solomon Third, split the AONT package and redundancy Shareholders get a fraction equal to (1 / t) of secret Unlike Shamir, Blakley, and XOR, but like SSMS, AONT-RS is conditionally secure: Security depends on the security of the cipher, and the limited computational resources of adversaries
AONT-RS as a Linear SSS 5 data elements 9 fragments 9 5 encoding matrix V 1 0 0 0 0 d1 d1 0 1 0 0 0 d2 d2 d3 0 0 1 0 0 d3 = d4 0 0 0 1 0 d4 d5 0 0 0 0 1 d5 10 11 12 13 14 d110 + d211 + d312 + d413 + d514 20 21 22 23 24 d120 + d221 + d322 + d423 + d524 30 31 32 33 34 d130 + d231 + d332 + d433 + d534 40 41 42 43 44 d140 + d241 + d342 + d443 + d544
Decoding in a Linear SSS 5 inputs 9 outputs 9 5 encoding matrix V =
Decoding in a Linear SSS 5 inputs 9 outputs 9 5 encoding matrix V =
Decoding in a Linear SSS 5 inputs 9 outputs 9 5 encoding matrix V =
Decoding in a Linear SSS 5 inputs 9 outputs 9 5 encoding matrix V =
Decoding in a Linear SSS 5 inputs 9 outputs 9 5 encoding matrix V =
Decoding in a Linear SSS 5 inputs 5 outputs 5 5 encoding matrix V =
Decoding in a Linear SSS decoding matrix V-1 encoding matrix V inputs decoding matrix V-1 outputs =
Decoding in a Linear SSS inputs decoding matrix V-1 outputs t t identity matrix 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 = 0 0 0 1 0 0 0 0 0 1
Decoding in a Linear SSS inputs decoding matrix V-1 outputs =
Rebuilding Lost Data No storage system is perfect Whatever storage media a shareholder uses for their share of the secret, it s subject to a non-zero failure rate The inverse of a failure rate is the mean time to failure Once more than (n t) shareholders have lost their shares, the secret is rendered irrecoverable But before this point in time, we may rebuild the lost share to recover full availability and reliability The most straight-forward way to do this is to recover the secret from t shares, then re-encode the lost share
Risks of Rebuilding Data Any time the secret is recovered it is vulnerable to interception, and accidental or malicious disclosure No shareholder is necessarily trusted with knowledge of the secret, nor knowledge of other shareholders shares To securely rebuild under the straight-forward approach, an entity trusted with knowledge of the secret must be involved in every rebuild operation But what if this entity is not available?
Cost of Rebuilding Lost Data Rebuilding is expensive, not only in terms of computation, but most importantly, in terms of necessary IO: Reads, Seeks, Network Transfers To rebuild a single share corresponding to 1 TB of secret information in a t=5, n=9 secret sharing scheme: SSMS and AONT-RS must read and transfer 1 TB of data Shamir and XOR must read and transfer 5 TB of data Blakley must read and transfer 25 TB of data! Since the shares are on 9 independent storage devices, this rebuild cost must be paid at a rate 9 times greater than the failure rate of the underlying storage media
Necessity of Rebuilding As costly and risky as rebuilding is, it is necessary to achieve any degree of reliability for the secret Assume MTTF of a disk is 20 years (5% AFR): For a t=5, n=9 Secret Sharing Scheme with shares stored on these drives, and no rebuilding, Mean Time to Irrecoverable loss of Secret: Time to (n t + 1) disk failures = (20 years / 9) + (20 years / 8) + (20 years / 7) + (20 years / 6) + (20 years / 5) = 14.91 years This is a 6.7% annual failure rate Less reliable than storing secret on just a single disk!
Power of Rebuilding If we assume the same drives, the same t=5, n=9 Secret Sharing Scheme, but add rebuilding Assume a 48 hour time window to rebuild lost shares: Mean time to Irrecoverable Loss of Secret would be: 5.63 trillion years Chance of losing secret over 100 years: Less than 1 chance in 50 billion!
Rebuilding Conclusions It s costly, dangerous, but nonetheless necessary A rebuild method that did not require shareholders to disclose their shares, or for the secret to be recovered every time a disk failed would be ideal The above sounds like a pipe dream, but the math tells us that this is indeed possible, and in fact, that it can be more efficient than conventional rebuilding!
Partial Rebuilding Partial rebuilding splits the rebuild operation into two separate mathematical stages: The first stage generates partial rebuild results The second stage combines the partial results The share is recovered without ever reconstructing the secret The combination can occur in different ways to decrease network overhead and increase performance The partial results can also be masked in such a way that no one learns anything they didn t already know
Traditional Rebuilding decoding matrix V-1 outputs inputs =
Traditional Rebuilding inputs rebuilt output 1 5 encoding vector V =
Full Rebuild Process decoding matrix V-1 outputs rebuilt output 1 5 encoding vector V =
Decomposed Rebuild Process decoding matrix V-1 outputs inputs =
Decomposed Rebuild Process decoding matrix V-1 output partially decoded result =
Decomposed Rebuild Process decoding matrix V-1 output partially decoded result =
Decomposed Rebuild Process decoding matrix V-1 output partially decoded result =
Decomposed Rebuild Process decoding matrix V-1 output partially decoded result =
Decomposed Rebuild Process decoding matrix V-1 output partially decoded result =
Combination Phase partially decoded results inputs + + + + =
Why it Works decoding matrix V-1 outputs decoding matrix V-1 = + + + +
Partial Decoding and Encoding decoding matrix V-1 outputs rebuilt output 1 5 encoding vector V =
Partial Decoding and Encoding decoding matrix V-1 output partially rebuilt output 1 5 encoding vector V a =
Partial Decoding and Encoding decoding matrix V-1 output partially rebuilt output 1 5 encoding vector V b =
Partial Decoding and Encoding decoding matrix V-1 output partially rebuilt output 1 5 encoding vector V c =
Partial Decoding and Encoding decoding matrix V-1 output partially rebuilt output 1 5 encoding vector V d =
Partial Decoding and Encoding decoding matrix V-1 output partially rebuilt output 1 5 encoding vector V e =
