packages feed

aos-signature (empty) → 0.1.0

raw patch · 6 files changed

+531/−0 lines, 6 filesdep +QuickCheckdep +aos-signaturedep +base

Dependencies added: QuickCheck, aos-signature, base, bytestring, cryptonite, memory, mtl, protolude, random, tasty, tasty-hunit, tasty-quickcheck

Files

+ LICENSE view
@@ -0,0 +1,30 @@+Copyright Adjoint Inc. (c) 2018++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Author name here nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ README.md view
@@ -0,0 +1,92 @@+<p align="center">+  <a href="http://www.adjoint.io"><img src="https://www.adjoint.io/assets/img/adjoint-logo@2x.png" width="250"/></a>+</p>++[![CircleCI](https://circleci.com/gh/adjoint-io/aos-signature.svg?style=svg&circle-token=ec783d4839d6a26e274796dd6e014399eac3918b)](https://circleci.com/gh/adjoint-io/aos-signature)++A ring signature, also know as a Spontaneous Anonymous Group (SAG) or 1-out-of-n signature, convinces a verifier that a message is signed by any member in a group of n independent signers without allowing the verifier to identify who the signer was.++Abe-Ohkubo-Suzuki Ring Signatures+=================================++In their paper, "1-out-of-n Signatures from a Variety of Keys"[1], Abe, Ohkubo and Suzuki (AOS) present a method to construct a 1-out-of-n signature scheme that allows mixture use of different flavours of keys at the same time.++### Linkable Spontaneous Anonymous Group (LSAG) Signature++Liu, et al.[2] add the property of linkability to ring signatures. Linkability means+that two signatures by the same signer can be identified as such, but the signer remains anonymous. It adds the feature of claimability, which allows a signer to claim responsibility by providing proof of having generated a given signature.++A LSAG signature scheme satisfies three properties:++- **Anonymity**: A signer cannot be distinguished from a pool of `t` commitments (public keys).+- **Spontaneity**: No group secret, group manager of secret sharing setup stage.+- **Linkability**: Two signatures by the same signer can be linked.++### A LSAG Signature Scheme over elliptic curves++It consists of two parts: signature generation and signature verification. Let L = {y<sub>0</sub>, ..., y<sub>t-1</sub>} be a list of `t` public keys. Let H:{0, 1}* -> Z<sub>n</sub> where `H` is a cryptographic hash function and `n` is the order of the elliptic curve over a finite field F<sub>q</sub>. For i ∈ {0, ..., t-1},+each user `i` has a distinct public key y<sub>i</sub> and a private key x<sub>i</sub>.++### Signature Generation++Let k ∈ {0, ..., t-1} be the position of the prover's public key in the list `L`+of public keys. Let x<sub>k</sub> be its private key. The LSAG signature of a message m ∈ {0,1}* is generated by the following steps:++1. Compute h = [H(L)] \* g, where `g` is the generator of the elliptic curve, and+y = [x<sub>k</sub>] \* h. Both computations are the product of a scalar and a point in the curve.++2. Select u ∈ Z<sub>n</sub> and compute the first challenge ch<sub>k+1</sub> = H(L, y, m, [u] \* g, [u] \* h)++3. For i in {k+1, ..., t-1, 0, ... k-1}, choose s<sub>i</sub> ∈ Z<sub>n</sub> and compute the remaining challenges: ch<sub>i+1</sub> = H(L, y, m, [s<sub>i</sub>] \* g + [ch<sub>i</sub>] \* y<sub>i</sub>, [s<sub>i</sub>] \* h + [ch<sub>i</sub>] \* y)++4. With the last ch<sub>k</sub> computed, calculate s<sub>k</sub> = (u - x<sub>k</sub> \* ch<sub>k</sub>) mod n++The signature is (ch<sub>0</sub>, [s<sub>0</sub>, ..., s<sub>t-1</sub>], y).++### Signature Verification++Given a message `m`, a signature of a message (ch<sub>0</sub>, [s<sub>0</sub>, ..., s<sub>t-1</sub>], y) and a list of public keys `L`, an honest verifier checks a signature as follows:++1. For i in {0, ..., t-1} compute ch<sub>i+1</sub> = H(L, y, m, [s<sub>i</sub>] \* g + [ch<sub>i</sub>] \* y<sub>i</sub>, [s<sub>i</sub>] \* h + [ch<sub>i</sub>] \* y), where h = [H(L)] \* g.++2. Check whether c<sub>0</sub> is equal to H(L, y, m, [s<sub>t-1</sub>] \* g + [ch<sub>t-1</sub>] \* y<sub>t-1</sub>, [s<sub>t-1</sub>] \* h + [ch<sub>t-1</sub>] \* y)++```haskell+testSignature+  :: ECC.Curve+  -> Int+  -> ByteString+  -> IO Bool+testSignature curve nParticipants msg = do+  -- Generate public and private keys+  (pubKey, privKey) <- ECC.generate curve+  -- Generate random foreign participants+  extPubKeys <- genNPubKeys curve nParticipants+  -- Position of the signer's key in the set of public keys+  k <- fromInteger <$> generateBetween 0 (toInteger $ length extPubKeys - 1)+  -- List of public keys+  let pubKeys = insert k pubKey extPubKeys+  -- Sign message with list of public keys and signer's key pair+  signature <- sign pubKeys (pubKey, privKey) msg+  -- Verify signature+  pure $ verify pubKeys signature msg+```++**References**:+1. M. Abe, M. Ohkubo, K. Suzuki. "1-out-of-n Signatures from a Variety of Keys", 2002+2. K. Liu, K. Wei, S. Wong. "Linkable Spontaneous Anonymous Group+Signature for Ad Hoc Groups", 2004+++**Notation**:++1. `[b] * P`: multiplication of a point P and a scalar b over an elliptic curve defined over a finite field modulo a prime number++License+-------++```+Copyright Adjoint Inc. (c) 2018++All rights reserved.+```
+ aos-signature.cabal view
@@ -0,0 +1,78 @@+-- This file has been generated from package.yaml by hpack version 0.28.2.+--+-- see: https://github.com/sol/hpack+--+-- hash: d214e3769ad5c9e277df99845fd5bef8e54ed9baaceb2483d09bfbbeb79d54da++name:           aos-signature+version:        0.1.0+synopsis:       An implementation of the AOS signatures+description:    An implementation of 1-out-of-n signatures from a variety of keys+category:       Cryptography+homepage:       https://github.com/adjoint-io/aos-signature#readme+bug-reports:    https://github.com/adjoint-io/aos-signature/issues+maintainer:     Adjoint Inc (info@adjoint.io)+license:        Apache+license-file:   LICENSE+build-type:     Simple+cabal-version:  >= 1.10+extra-source-files:+    README.md++source-repository head+  type: git+  location: https://github.com/adjoint-io/aos-signature++flag optimized+  description: Perform compiler optimizations+  manual: False+  default: False++flag static+  description: Emit statically-linked binary+  manual: False+  default: False++library+  exposed-modules:+      LSAG+  other-modules:+      Paths_aos_signature+  hs-source-dirs:+      src+  default-extensions: LambdaCase RecordWildCards OverloadedStrings NoImplicitPrelude FlexibleInstances+  ghc-options: -fwarn-tabs -fwarn-incomplete-patterns -fwarn-incomplete-record-updates -fwarn-redundant-constraints -fwarn-implicit-prelude -fwarn-overflowed-literals -fwarn-orphans -fwarn-identities -fwarn-dodgy-exports -fwarn-dodgy-imports -fwarn-duplicate-exports -fwarn-overlapping-patterns -fwarn-missing-fields -fwarn-missing-methods -fwarn-missing-signatures -fwarn-noncanonical-monad-instances -fwarn-unused-pattern-binds -fwarn-unused-type-patterns -fwarn-unrecognised-pragmas -fwarn-wrong-do-bind -fno-warn-name-shadowing -fno-warn-unused-binds -fno-warn-unused-matches -fno-warn-unused-do-bind+  build-depends:+      base >=4.7 && <5+    , bytestring+    , cryptonite+    , memory+    , mtl+    , protolude >=0.2+    , random+  default-language: Haskell2010++test-suite aos-signature-test+  type: exitcode-stdio-1.0+  main-is: Main.hs+  other-modules:+      TestLSAG+      Paths_aos_signature+  hs-source-dirs:+      test+  default-extensions: LambdaCase RecordWildCards OverloadedStrings NoImplicitPrelude FlexibleInstances+  ghc-options: -threaded -rtsopts -with-rtsopts=-N+  build-depends:+      QuickCheck+    , aos-signature+    , base >=4.7 && <5+    , bytestring+    , cryptonite+    , memory+    , mtl+    , protolude >=0.2+    , random+    , tasty+    , tasty-hunit+    , tasty-quickcheck+  default-language: Haskell2010
+ src/LSAG.hs view
@@ -0,0 +1,217 @@+-- | Implementation of Linkable Spontaneus Anonymous Group (LSAG) Signature over elliptic curve cryptography.+--+-- >>> (pubKey, privKey) <- ECC.generate curve -- Generate public and private keys+-- >>> extPubKeys <- genNPubKeys curve nParticipants -- Generate random foreign participants+-- >>> k <- fromInteger <$> generateBetween 0 (toInteger $ length extPubKeys - 1) -- Position of the signer's key in the public keys list (k)+-- >>> let pubKeys = insert k pubKey extPubKeys -- Insert signer's public key into the list of public keys+-- >>> signature <- sign pubKeys (pubKey, privKey) msg -- Sign message with list of public keys and signer's key pair+-- >>> verify pubKeys signature msg -- Verify signature+-- True++module LSAG+( sign+, verify+, genNPubKeys+) where++import           Control.Monad.State+import           Crypto.Hash+import           Crypto.Number.Serialize      (os2ip)+import           Crypto.Number.Generate       (generateBetween)+import qualified Crypto.PubKey.ECC.Generate   as ECC+import qualified Crypto.PubKey.ECC.Prim       as ECC+import qualified Crypto.PubKey.ECC.Types      as ECC+import qualified Crypto.PubKey.ECC.ECDSA      as ECDSA+import           Crypto.Random.Types          (MonadRandom)+import qualified Data.ByteArray               as BA+import qualified Data.ByteString              as BS+import           Data.Monoid+import           Data.List+import           Protolude                    hiding (hash, head)++-- | Generates a ring signature for a message given a specific set of+-- public keys and a signing key belonging to one of the public keys+-- in the set+--+-- It returns a signature (c0, ss, y) :+--+-- * c0: Initial value to reconstruct signature.+-- * ss: vector of randomly generated values with encrypted secret to+-- reconstruct signature {s0 ... sn-1}.+-- * y: Link for current signer.+sign+  :: MonadRandom m+  => [ECDSA.PublicKey]                    -- ^ List of public keys+  -> (ECDSA.PublicKey, ECDSA.PrivateKey)  -- ^ Signer's public and private keys+  -> ByteString                           -- ^ Message+  -> m (Integer, [Integer], ECC.Point)+sign pubKeys (pubKey, privKey) msg =+  case pubKey `elemIndex` pubKeys of+    Nothing -> panic "Signer's public key is not among public keys"+    Just k -> do+      -- Generate L random s values+      -- (sk + 1) : [sk + 2, ..., s0, 1, ..., sk - 1]+      (sK1:sK2ToPrevSK) <- replicateM (participants - 1) $ generateBetween 1 (n - 1)++      -- Pick u and compute challenge c = H(L, y, m, [u] * g, [u] * h)+      u <- generateBetween 1 (n - 1)+      -- Initial challenge at k + 1+      -- H(L, y, m, [u] * g, [u] * h)+      let chK1 = genChallenge curve pubKeys y msg (gu u) (hu u)++      -- Generate challenges+      -- [ck, ..., c1, c0, ... ck + 2, ck + 1]+      let reversedChKToChK1 = runChallenges k sK1 chK1 sK2ToPrevSK u y h+          chK = head reversedChKToChK1++      -- Compute s = u - x * c mod n+      let sK = (u - ECDSA.private_d privKey * chK) `mod` n++      -- Reverse reversedChKToChK1: [chK + 1, ck + 2, ..., 0, 1, ..., chK]+      -- Ordered challenges: [c0, c1, ..., cn-1]+      let orderedChallenges = orderChallenges k (reverse reversedChKToChK1)++      -- Ordered ss: [s0, s1, ..., sk, ..., sn-1]+      -- (sK : sK1 : sK2ToPrevSK): [sk, sk + 1, ..., sk - 1]+      let orderedSS = orderSS k (sK : sK1 : sK2ToPrevSK)+          ch0 = head orderedChallenges++      -- The signature is (ch0, (s0, ..., sn-1), y)+      pure (ch0, orderedSS, y)++  where+    curve = ECDSA.public_curve pubKey+    -- h = [Hash(L)] * g+    h = ECC.pointBaseMul curve (hashPubKeys curve pubKeys)+    -- y = [x] * h+    y = ECC.pointMul curve (ECDSA.private_d privKey) h+    n = ECC.ecc_n (ECC.common_curve curve)+    g = ECC.ecc_g (ECC.common_curve curve)+    gu u = ECC.pointMul curve u g+    hu u = ECC.pointMul curve u h+    participants = length pubKeys+    runChallenges k sK1 chK1 sK2ToPrevSK u y h = evalState+      (genChallenges pubKeys y msg sK2ToPrevSK)+      (initState k sK1 chK1)+    initState k sK1 chK1 =+      (((k + 1) `mod` participants, sK1, chK1), [chK1])+    orderChallenges k ch =+      drop (participants - (k + 1)) ch <>+      take (participants - (k + 1)) ch+    orderSS k sKToPrevSK =+      drop (participants - k) sKToPrevSK <>+      take (participants - k) sKToPrevSK++-- | Verify if a valid signature was made by any public key in the set of public keys L.+--+-- Return a boolean value indicating if signature is valid.+verify+  :: [ECDSA.PublicKey]                    -- ^ List of participants public keys+  -> (Integer, [Integer], ECC.Point)      -- ^ Signature+  -> ByteString                           -- ^ Message+  -> Bool+verify pubKeys (ch0, [], y) msg = panic "Invalid input"+verify pubKeys (ch0, [s], y) msg = panic "Invalid input"+verify pubKeys (ch0, s0:s1:s2ToEnd, y) msg = ch0 == ch0'+  where+    curve0 = ECDSA.public_curve $ head pubKeys+    -- h = [H(L)] * g+    h = ECC.pointBaseMul curve0 (hashPubKeys curve0 pubKeys)+    y0 = ECDSA.public_q $ head pubKeys+    -- z0' = [s0] * g + [ch0] * y0+    z0' = ECC.pointAdd curve0+      (ECC.pointMul curve0 s0 g)+      (ECC.pointMul curve0 ch0 y0)+    -- z0'' = [s0] * h + [c0] * y+    z0'' = ECC.pointAdd curve0+      (ECC.pointMul curve0 s0 h)+      (ECC.pointMul curve0 ch0 y)+    g = ECC.ecc_g (ECC.common_curve curve0)+    participants = length pubKeys++    -- initial challenge - ch1+    ch1 = genChallenge curve0 pubKeys y msg z0' z0''+    -- [ch0, chN-1 ..., ch2, ch1]+    challenges = evalState+      (genChallenges pubKeys y msg s2ToEnd)+      ((1 `mod` participants, s1, ch1), [ch1])+    ch0' = head challenges++genChallenges+  :: [ECDSA.PublicKey]  -- ^ List of public keys L+  -> ECC.Point          -- ^ y = h x [x]+  -> BS.ByteString      -- ^ message msg+  -> [Integer]          -- ^ random ss+  -> State ((Int, Integer, Integer), [Integer]) [Integer]+genChallenges pubKeys y msg ss = do+  ((prevK, prevS, prevCh), challenges) <- get+  let curve = ECDSA.public_curve $ pubKeys !! prevK+  let ch = challenge curve prevK prevS prevCh+  case ss of+    [] -> pure $ ch : challenges+    (s:ss) -> do+      put (((prevK + 1) `mod` participants, s, ch)+          , ch : challenges+          )+      genChallenges pubKeys y msg ss+  where+    g curve = ECC.ecc_g (ECC.common_curve curve)+    h curve = ECC.pointBaseMul curve (hashPubKeys curve pubKeys)+    gs curve prevK prevS prevCh =+      ECC.pointAdd curve+        (ECC.pointMul curve prevS (g curve))+        (ECC.pointMul curve prevCh (ECDSA.public_q $ pubKeys !! prevK))+    hs curve prevK prevS prevCh =+      ECC.pointAdd curve+        (ECC.pointMul curve prevS (h curve))+        (ECC.pointMul curve prevCh y)+    challenge curve prevK prevS prevCh =+      genChallenge curve pubKeys y msg+        (gs curve prevK prevS prevCh)+        (hs curve prevK prevS prevCh)+    participants = length pubKeys++-- | Generate challenge from a given message+--+-- @c = H(L, y, m, p1, p2)@+genChallenge+  :: ECC.Curve+  -> [ECDSA.PublicKey]  -- ^ List of public keys L+  -> ECC.Point          -- ^ y = [privKey] * h+  -> BS.ByteString      -- ^ message msg+  -> ECC.Point          -- ^ generator g+  -> ECC.Point          -- ^ h = [H(L)] * g+  -> Integer+genChallenge c pubKeys y msg g h =+  oracle c (pubKeys' <> y' <> msg <> g' <> h')+  where+    pubKeys' = pubKeysToBS pubKeys+    y' = pointToBS y+    g' = pointToBS g+    h' = pointToBS h++-- | Generate N different public keys. @L = {y1, ..., yn}@+genNPubKeys :: MonadRandom m => ECC.Curve -> Int -> m [ECDSA.PublicKey]+genNPubKeys curve n = replicateM n (fst <$> ECC.generate curve)++-- | Convert point to bytestring+pointToBS :: ECC.Point -> BS.ByteString+pointToBS ECC.PointO      = ""+pointToBS (ECC.Point x y) = show x <> show y++-- | Convert list of public keys to bytestring+pubKeysToBS :: [ECDSA.PublicKey] -> BS.ByteString+pubKeysToBS = foldMap (pointToBS . ECDSA.public_q)++-- | Hash list of public keys+hashPubKeys :: ECC.Curve -> [ECDSA.PublicKey] -> Integer+hashPubKeys c = oracle c . pubKeysToBS++-- | Unpredictable but deterministic random response+oracle :: ECC.Curve -> BS.ByteString -> Integer+oracle curve x = os2ip (sha256 x) `mod` n+  where+    n = ECC.ecc_n (ECC.common_curve curve)++sha256 :: BS.ByteString -> BS.ByteString+sha256 bs = BA.convert (hash bs :: Digest SHA3_256)
+ test/Main.hs view
@@ -0,0 +1,22 @@+module Main where++import           Protolude+import           Test.QuickCheck.Monadic+import           Test.Tasty+import           Test.Tasty.HUnit+import           Test.Tasty.QuickCheck+import           Crypto.Number.Generate     (generateBetween)+import qualified Crypto.PubKey.ECC.Prim as ECC+import qualified Crypto.PubKey.ECC.Types as ECC+import qualified Crypto.PubKey.ECC.Generate as ECC++import           LSAG+import           TestLSAG++main :: IO ()+main = defaultMain tests++tests :: TestTree+tests = testGroup "Tests"+  [ testLSAG+  ]
+ test/TestLSAG.hs view
@@ -0,0 +1,92 @@+module TestLSAG where++import           Protolude+import           Test.QuickCheck.Monadic+import           Test.Tasty+import           Test.Tasty.HUnit+import           Test.Tasty.QuickCheck+import           Crypto.Number.Generate     (generateBetween)+import qualified Crypto.PubKey.ECC.Prim     as ECC+import qualified Crypto.PubKey.ECC.Types    as ECC+import qualified Crypto.PubKey.ECC.Generate as ECC++import           LSAG++newtype Curve = Curve ECC.Curve deriving Show++secp256k1Curve :: ECC.Curve+secp256k1Curve = ECC.getCurveByName ECC.SEC_p256k1++instance Arbitrary Curve where+  arbitrary = elements+    [ Curve secp256k1Curve+    ]++genPoint :: ECC.Curve -> Gen ECC.Point+genPoint curve = ECC.generateQ curve <$> arbitrary++genPos :: Gen Integer+genPos = abs <$> arbitrary `suchThat` (> 0)++-- | Insert element at specified position+insert :: Int -> a -> [a] -> [a]+insert k e l = take k l <> [e] <> drop k l++testLSAG :: TestTree+testLSAG = testGroup "LSAG Signature"+  [ localOption (QuickCheckTests 10) $ testProperty+      "Verify signature on SEC curves"+      (forAll (choose (3, 20)) testSignature)+  , localOption (QuickCheckTests 50) $ testProperty+      "A verifier rejects invalid signatures"+      (forAll (choose (3, 15)) $ \nParticipants ->+      forAll genPos $ \challenge ->+      forAll (genPoint secp256k1Curve) $ \y ->+      testInvalidPubKeys nParticipants y challenge)+  ]++testSignature+  :: Int+  -> Curve+  -> Curve+  -> Curve+  -> Curve+  -> [Char]+  -> Property+testSignature+  nParticipants+  (Curve curve0)+  (Curve curve1)+  (Curve curve2)+  (Curve curve3)+  msg = monadicIO $ do+  -- Gen public and private keys+  (pubKey, privKey) <- liftIO $ ECC.generate curve0+  -- Gen random foreign participants+  extPubKeys1 <- liftIO $ genNPubKeys curve1 nParticipants+  extPubKeys2 <- liftIO $ genNPubKeys curve2 nParticipants+  extPubKeys3 <- liftIO $ genNPubKeys curve3 nParticipants+  let extPubKeys = extPubKeys1 <> extPubKeys2 <> extPubKeys3+  -- k: position of the signer's key in the public keys list+  k <- liftIO $ fromInteger <$> generateBetween 0 (toInteger $ length extPubKeys - 1)+  let pubKeys = insert k pubKey extPubKeys+  -- Sign message with list of public keys and signer's key pair+  signature <- liftIO $ sign pubKeys (pubKey, privKey) (show msg)+  -- Verify signature+  pure $ verify pubKeys signature (show msg)+++-- | A verifier rejects an invalid signature+testInvalidPubKeys+  :: Int+  -> ECC.Point+  -> Integer+  -> Curve+  -> [Char]+  -> Property+testInvalidPubKeys nParticipants y ch0 (Curve curve) msg = monadicIO $ do+  ss <- liftIO $ replicateM nParticipants $ generateBetween 1 n+  pubKeys <- liftIO $ genNPubKeys curve nParticipants+  pure $ not $ verify pubKeys (ch0, ss, y) (show msg)+  where+    n = ECC.ecc_n (ECC.common_curve curve)