data-dispersal 1.0.0.0 → 1.0.0.1
raw patch · 4 files changed
+94/−42 lines, 4 filesdep ~base
Dependency ranges changed: base
Files
- data-dispersal.cabal +40/−17
- src/Crypto/IDA.hs +33/−14
- src/Data/IDA/FiniteField.hs +17/−10
- src/Data/IDA/Internal.hs +4/−1
data-dispersal.cabal view
@@ -6,27 +6,23 @@ -- PVP summary: +-+------- breaking API changes -- | | +----- non-breaking API additions -- | | | +--- code changes with no API change-version: 1.0.0.0+version: 1.0.0.1 synopsis: Space-efficient and privacy-preserving data dispersal algorithms. description:- This library provides space-efficient (m,n)-information dispersal algorithms (IDAs). - .- Given a ByteString @bstr@ of length @D@, we encode @bstr@ as a list @fs@ of @n@ + Given a ByteString of length @D@, we encode the ByteString as a list of @n@ 'Fragment's, each containing a ByteString- of length @O(D/m)@. Then, each fragment in @fs@ could be stored on a separate - machine for fault-tolerance.- Even if up to @n-m@ of these machines crash, we can still reconstruct the original - ByteString out of the remaining m fragments.+ of length @O(D/m)@. Then, each fragment could be stored on a separate + machine to obtain fault-tolerance:+ Even if all but @m@ of these machines crash, we can still reconstruct the original + ByteString out of the remaining @m@ fragments.+ Note that the total space requirement of the @m@ fragments is @m * O(D/m)=O(D),@+ which is clearly space-optimal. The total space required for the n fragments is @O((n/m)*D)@.- Note that @m@ and @n@ are roughly in the same order, so the actual storage overhead - for getting good fault-tolerance increases only by a constant factor.- .- The module @Data.IDA@ contains the basic information dispersal algorithm. The module- @Crypto.IDA@ augments the dispersal scheme by combining it with secret sharing, i.e.,- the knowledge of up to @m-1@ fragments does not leak any information about- the original data. See "Crypto.IDA" for details.+ Note that @m@ and @n@ can be chosen to be of the same order, so the+ asymptotic storage overhead for getting good fault-tolerance increases only by+ a constant factor. . /GHCi Example:/ .@@ -36,9 +32,36 @@ > -- Now we could distributed the fragments on different sites to add some > -- fault-tolerance. > > let frags' = drop 5 $ take 10 fragments -- let's pretend that 10 machines crashed+ > -- Let's look at the 5 fragments that we have left:+ > > mapM_ (Prelude.putStrLn . show) frags'+ > (6,[273,771,899,737,285])+ > (7,[289,939,612,285,936])+ > (8,[424,781,1001,322,788])+ > (9,[143,657,790,157,423])+ > (10,[314,674,418,888,423])+ > -- Space-efficiency: Note that the length of each of the 5 fragments is 5 + > -- and our original message has length 24. > > decode frags' > "my really important data" .+ /Encrypted Fragments:/ + .+ The module @Data.IDA@ contains an information dispersal algorithm that produces + space-optimal fragments. However, the knowledge of 1 or more fragments might+ allow an adversary to deduce some information about the original data.+ The module @Crypto.IDA@ combines information dispersal with+ secret sharing: the knowledge of up to @m-1@ fragments does not leak any+ information about the original data. + .+ This could be useful in scenarios where we need to store data at untrusted+ storage sites: To this end, we store one encrypted fragment at each site.+ If at most @m-1@ of these untrusted sites collude, they will still+ be unable to obtain any information about the original data.+ The added security comes at the price of a slightly+ increased fragment size (by an additional constant 32 bytes) and an+ additional overhead in the running time of the encoding/decoding process.+ The algorithm is fully described in module "Crypto.IDA". + . /Fault-Tolerance:/ . Suppose that we have @N@ machines and encode our data as @2log(N)@ fragments @@ -50,7 +73,7 @@ @Pr[ at most n-m machines crash ] >= 1-0.5^(log(N)) = 1-N^(-1).@ . * What is the overhead in terms of space that we pay for this level of fault-tolerance?- We have n fragments, each of size D\/m, so the total space is @n * D\/ m = + We have n fragments, each of size @O(D\/m)@, so the total space is @O(n D\/ m) = 2D.@ In other words, we can guarantee that the data survives with high probability by increasing the required space by a constant factor.@@ -108,7 +131,7 @@ ,entropy >= 0.3.2 ,secret-sharing >= 1.0.0.0 - ghc-options: -Wall + ghc-options: -W test-suite Main type: exitcode-stdio-1.0
src/Crypto/IDA.hs view
@@ -18,10 +18,9 @@ -- -- 1. Any @m@ of the @n@ fragments are sufficient for reconstructing the original -- bytestring via 'decode', and--- 2. the knowledge of up to @m-1@ fragments does /not/ reveal any information+-- 2. the knowledge of up to @m-1@ fragments does /not/ leak any information -- about the original bytestring. ----- -- In more detail, suppose that we have some bytestring @b@ that we want to -- (securely) disperse and parameter @m@, @n@. -- Running 'encode' @m n b@ does the following: @@ -45,12 +44,13 @@ -- ----------------------------------------------------------------------------- {-# LANGUAGE DeriveDataTypeable, ScopedTypeVariables, DeriveGeneric #-}-module Crypto.IDA( EncryptedFragment(fragmentId,keyShare,aesIV,fragment)+module Crypto.IDA( EncryptedFragment(keyShare,aesIV,fragment) , encode+ , encodeWithIV , decode ) where-import Data.IDA.Internal( Fragment(..) )+import Data.IDA.Internal( Fragment(theContent)) import qualified Data.IDA.Internal as IDA import Crypto.SecretSharing( Share )@@ -67,13 +67,16 @@ import GHC.Generics data EncryptedFragment = EncryptedFragment- { fragmentId :: Int -- ^ the id of the encrypted fragment, ranging from 1 to n.- , keyShare :: Share -- ^ the list of (bytewise) shares of the AES key+ { keyShare :: Share -- ^ the list of (bytewise) shares of the AES key , aesIV :: B.ByteString -- ^ the initialization vector of the AES encryption , fragment :: Fragment -- ^ the encrypted fragment of the original data }- deriving(Typeable,Show,Eq,Generic)+ deriving(Typeable,Eq,Generic) ++instance Show EncryptedFragment where+ show f = show (keyShare f,theContent $ fragment f)+ instance Binary EncryptedFragment @@ -85,22 +88,38 @@ -- Generates @n@ fragments out -- of a given bytestring @b@. Each fragment has size @length b \/ m + O(1)@. -- At least m fragments are required for reconstruction.--- Preserves secrecy: Assuming that these fragments are distributed --- among different sites, the knowledge of less than m +-- Preserves secrecy: The knowledge of less than m -- fragments provides /no/ information about the original data whatsoever.-encode :: Int -- ^ m: number of fragments required for reconstruction+encode :: Int -- ^ m: number of fragments required for reconstruction -> Int -- ^ n: total number of fragments (@n ≥ m@)- -> Maybe ByteString -- ^ the initialization vector for the AES encryption -> ByteString -- ^ the information that we want to disperse -> IO [EncryptedFragment] -- ^ a list of n encrypted fragments.-encode m numFragments mIV msg = do+encode m n msg = encode' m n Nothing msg+++-- | Same as 'encode' but uses an initialization vector for the AES encryption.+encodeWithIV :: Int -- ^ m: number of fragments required for reconstruction+ -> Int -- ^ n: total number of fragments (@n ≥ m@)+ -> ByteString -- ^ the initialization vector for the AES encryption+ -> ByteString -- ^ the information that we want to disperse+ -> IO [EncryptedFragment] -- ^ a list of n encrypted fragments.+encodeWithIV m n iv msg = encode' m n (Just iv) msg+++encode' :: Int -- ^ m: number of fragments required for reconstruction+ -> Int -- ^ n: total number of fragments (@n ≥ m@)+ -> Maybe ByteString -- ^ the initialization vector for the AES encryption.+ -- If none is given, we create a random one.+ -> ByteString -- ^ the information that we want to disperse+ -> IO [EncryptedFragment] -- ^ a list of n encrypted fragments.+encode' m numFragments mIV msg = do key <- getEntropy aesKeyLength iv <- maybe (getEntropy aesIVLength) (return . BL.toStrict) mIV keyShareList <- PSS.encode m numFragments (BL.fromStrict key) let headers = zip keyShareList (replicate numFragments $ BL.fromStrict iv) let fs = IDA.encode m numFragments $ BL.toStrict $ crypt CTR key iv Encrypt msg- return [ EncryptedFragment i ks (BL.toStrict iv) f - | (i,(ks,iv),f) <- zip3 [1..] headers fs + return [ EncryptedFragment ks (BL.toStrict iv') f + | ((ks,iv'),f) <- zip headers fs ] -- | Reconstruct the original data from (at least) @m@ fragments.
src/Data/IDA/FiniteField.hs view
@@ -9,7 +9,7 @@ -- Stability : experimental -- Portability : portable -- --- Computations in a finite prime field+-- Linear algebra computations in a finite prime field. -- ----------------------------------------------------------------------------- @@ -21,7 +21,6 @@ import GHC.Generics import qualified Data.FiniteField.PrimeField as PF import Data.FiniteField.Base-import Data.IDA.Prime import qualified Data.Vector as V import Data.Vector(Vector)@@ -32,14 +31,16 @@ -- | Our finite prime field. All computations are performed in this field.-newtype FField = FField { number :: $(PF.primeField $ fromIntegral prime) }- deriving(Show,Read,Ord,Eq,Num,Fractional,Generic,Typeable,FiniteField)+newtype FField = FField { number :: $(PF.primeField $ fromIntegral 1021) }+ deriving(Read,Ord,Eq,Num,Fractional,Generic,Typeable,FiniteField) +instance Show FField where+ show = show . PF.toInteger . number+ instance Monoid FField where mempty = 0 mappend = (+) - instance Enum FField where toEnum = FField . fromIntegral fromEnum = fromEnum . PF.toInteger . number@@ -51,6 +52,11 @@ put f = put (PF.toInteger $ number f) +-- | The size of the finite field+prime :: Int+prime = fromInteger $ order (0 :: FField)++ -- | A matrix over the finite field. type FMatrix = Matrix FField @@ -62,10 +68,10 @@ -- | Solves a linear equality system @A x = b@ given by a lower triangular matrix via -- forward substitution. forwardSub :: Fractional a => Matrix a -> Vector a -> Vector a-forwardSub lower bV =- forwardSub' lower bV (V.empty)+forwardSub =+ forwardSub' (V.empty) where- forwardSub' lower bV xV + forwardSub' xV lower bV | nrows lower == 0 = xV | otherwise = let curRow = getRow 1 lower @@ -75,9 +81,10 @@ negSum = curRow `dotProduct` xV curX = (curB - negSum) / lm in- forwardSub' (submatrix 2 (nrows lower) 1 (ncols lower) lower) + forwardSub' (V.snoc xV curX)+ (submatrix 2 (nrows lower) 1 (ncols lower) lower) (V.tail bV) - (V.snoc xV curX)+ -- | Solves a linear equality system @A x = b@ given by an upper triangular matrix via
src/Data/IDA/Internal.hs view
@@ -38,7 +38,10 @@ , theContent :: ![FField] -- ^ the encoded content of the fragment , msgLength :: !Int -- ^ length of the original message }- deriving(Typeable,Show,Eq,Generic)+ deriving(Typeable,Eq,Generic)++instance Show Fragment where+ show f = show (fragmentId f,theContent f) instance Binary Fragment