x/lib/ibe: Implementation of Fujisaki-Okamoto transformation for BB-IBE
THIS IS DAVID WU's CL.
I am simply uploading it as part of a multipart
patchset that fixes all the dependant code.
MultiPart: 1/2
Change-Id: I9c005af809ee5e338247b3a411d4ed053f427d2a
diff --git a/ibe/.api b/ibe/.api
index d2dd141..e561c43 100644
--- a/ibe/.api
+++ b/ibe/.api
@@ -1,5 +1,3 @@
-pkg ibe, const CiphertextSize ideal-int
-pkg ibe, const PlaintextSize ideal-int
pkg ibe, func MarshalParams(Params) ([]byte, error)
pkg ibe, func MarshalPrivateKey(PrivateKey) ([]byte, error)
pkg ibe, func SetupBB1() (Master, error)
@@ -8,7 +6,9 @@
pkg ibe, type Master interface { Extract, Params }
pkg ibe, type Master interface, Extract(string) (PrivateKey, error)
pkg ibe, type Master interface, Params() Params
-pkg ibe, type Params interface { Encrypt }
+pkg ibe, type Params interface { CiphertextOverhead, Encrypt }
+pkg ibe, type Params interface, CiphertextOverhead() int
pkg ibe, type Params interface, Encrypt(string, []byte, []byte) error
-pkg ibe, type PrivateKey interface { Decrypt }
+pkg ibe, type PrivateKey interface { Decrypt, Params }
pkg ibe, type PrivateKey interface, Decrypt([]byte, []byte) error
+pkg ibe, type PrivateKey interface, Params() Params
diff --git a/ibe/.godepcop b/ibe/.godepcop
index e1e57c2..adb8771 100644
--- a/ibe/.godepcop
+++ b/ibe/.godepcop
@@ -1,3 +1,6 @@
<godepcop>
<pkg allow="golang.org/x/crypto/bn256"/>
+ <pkg allow="golang.org/x/crypto/nacl/secretbox"/>
+ <pkg allow="golang.org/x/crypto/poly1305"/>
+ <pkg allow="golang.org/x/crypto/salsa20/salsa"/>
</godepcop>
diff --git a/ibe/bb1.go b/ibe/bb1.go
index 2f1351a..5e1c8d6 100644
--- a/ibe/bb1.go
+++ b/ibe/bb1.go
@@ -3,15 +3,22 @@
// license that can be found in the LICENSE file.
// This file defines an implementation of the IBE interfaces using the
-// Boneh-Boyen scheme. The paper defining this algorithm (see comments for
+// Boneh-Boyen scheme. The Fujisaki-Okamoto transformation is applied to
+// obtain CCA2-security. The paper defining this algorithm (see comments for
// SetupBB1) uses multiplicative groups while the bn256 package used in the
// implementation here defines an additive group. The comments follow the
// notation in the paper while the code uses the bn256 library. For example,
// g^i corresponds to G1.ScalarBaseMult(i).
+// The ciphertexts in the resulting CCA2-secure IBE scheme will consist of
+// two parts: an IBE encryption of a symmetric key (called the 'kem' - key
+// encapsulation mechanism) and a symmetric encryption of the payload
+// (called the 'dem' - data encapsulation mechanism).
+
package ibe
import (
+ "bytes"
"crypto/rand"
"crypto/sha256"
"errors"
@@ -19,6 +26,7 @@
"math/big"
"golang.org/x/crypto/bn256"
+ "golang.org/x/crypto/nacl/secretbox"
)
var errBadCiphertext = errors.New("invalid ciphertext")
@@ -27,6 +35,24 @@
marshaledG1Size = 2 * 32
marshaledG2Size = 4 * 32
marshaledGTSize = 12 * 32
+ nonceSize = 24
+ encKeySize = sha256.Size // size of encapsulated key = 32 bytes
+ kemSize = encKeySize + 2*marshaledG1Size // 160 bytes
+)
+
+// In the construction, we require several independent hash functions for
+// hashing the different quantities (in the security reduction, these
+// hash functions are modeled as random oracles). In the implementation,
+// we use SHA-256 as the underlying hash function, but concatenate a prefix
+// to differentiate the different hash functions. For example, we have
+// H1(x) = SHA256(00 || x), H2(x) = SHA256(01 || x), and so on. If we model
+// SHA256 as a random oracle, then H1, H2, ... are also independent random
+// oracles.
+var (
+ idPrefix = [1]byte{0x00}
+ kemPrefix = [1]byte{0x01}
+ demPrefix = [1]byte{0x02}
+ ibePrefix = [1]byte{0x03}
)
// Setup creates an ibe.Master based on the BB1 scheme described in "Efficient
@@ -34,6 +60,13 @@
// Xavier Boyen (http://crypto.stanford.edu/~dabo/papers/bbibe.pdf).
//
// Specifically, Section 4.3 of the paper is implemented.
+//
+// In addition, we apply the Fujisaki-Okamoto transformation to the BB-IBE
+// scheme (http://link.springer.com/chapter/10.1007%2F3-540-48405-1_34)
+// in order to obtain CCA2-security (in the random oracle model). The resulting
+// scheme is a CCA2-secure hybrid encryption scheme where BB-IBE is used to
+// encrypt a nonce used to derive a symmetric key, and NaCl/secretbox is used
+// to encrypt the data under the symmetric key.
func SetupBB1() (Master, error) {
var (
m = &bb1master{params: new(bb1params)}
@@ -91,7 +124,7 @@
g1Hat = &(m.params.g1Hat)
g0Hat = &(m.g0Hat)
hHat = &(m.params.hHat)
- i = id2bignum(id)
+ i = val2bignum(idPrefix, []byte(id))
)
// ret.d0 = g0Hat * (g1Hat^i * hHat)^r
d0.ScalarMult(g1Hat, i)
@@ -110,74 +143,168 @@
v *bn256.GT
}
-func (e *bb1params) Encrypt(id string, m, C []byte) error {
- if err := checkSizes(m, C); err != nil {
- return err
+// Helper method that checks that the ciphertext slice for a given message has
+// the correct size: len(C) = len(m) + CiphertextOverhead()
+func (e *bb1params) checkSizes(m, C []byte) error {
+ if msize, Csize := len(m), len(C); Csize != msize+e.CiphertextOverhead() {
+ return fmt.Errorf("provided plaintext and ciphertext are of sizes (%d, %d), ciphertext size should be %d", msize, Csize, e.CiphertextOverhead())
}
- s, err := random()
- if err != nil {
- return err
+ return nil
+}
+
+// Helper method that constructs the first two components of the BB-IBE
+// ciphertext. These components are re-computed during decryption to verify
+// proper generation of the ciphertext. This is the Fujisaki-Okamoto transformation.
+// The ciphertext C that is passed in must have size exactly
+// encKeySize + marshaledG1Size.
+func (e *bb1params) encapsulateKeyStart(sigma *[encKeySize]byte, s *big.Int, C []byte) error {
+ if len(C) != encKeySize+marshaledG1Size {
+ return fmt.Errorf("provided buffer has size %d, must be %d", len(C), encKeySize+marshaledG1Size)
}
var (
vs bn256.GT
tmpG1 bn256.G1
- // Ciphertext C = (A, B, C1)
- A = C[0:len(m)]
- B = C[len(m) : len(m)+marshaledG1Size]
- C1 = C[len(m)+marshaledG1Size:]
+ // Ciphertext C = (A, B, C1) - this method computes the first two components
+ A = C[0:encKeySize]
+ B = C[encKeySize : encKeySize+marshaledG1Size]
)
vs.ScalarMult(e.v, s)
- pad := sha256.Sum256(vs.Marshal())
- // A = m ⊕ H(v^s)
- for i := range m {
- A[i] = m[i] ^ pad[i]
+ pad := hashval(ibePrefix, vs.Marshal())
+ // A = sigma ⊕ H(v^s)
+ for i := range sigma {
+ A[i] = sigma[i] ^ pad[i]
}
// B = g^s
if err := marshalG1(B, tmpG1.ScalarBaseMult(s)); err != nil {
return err
}
+
+ return nil
+}
+
+// Compute the symmetric key used for data encapsulation (used to encrypt the payload
+// during Encrypt and for verification during Decrypt)
+func computeDemKey(sigma *[encKeySize]byte) *[encKeySize]byte {
+ return hashval(demPrefix, sigma[:])
+}
+
+// Computes the randomness used to encrypt the symmetric key. The randomness is given
+// by H(sigma || m).
+func computeKemRandomness(sigma *[encKeySize]byte, m []byte) *big.Int {
+ // Note: append(sigma[:], m) will allocate a new slice and copy the data
+ // since sigma is a fixed-size array (not a slice with larger capacity). However,
+ // if this changes in the future, this should be changed to ensure thread-safety.
+ return val2bignum(kemPrefix, append(sigma[:], m...))
+}
+
+func (e *bb1params) Encrypt(id string, m, C []byte) error {
+ if err := e.checkSizes(m, C); err != nil {
+ return err
+ }
+
+ // Choose a random nonce for the Fujisaki-Okamoto transform
+ var sigma [encKeySize]byte
+ if _, err := rand.Read(sigma[:]); err != nil {
+ return err
+ }
+
+ var (
+ s = computeKemRandomness(&sigma, m) // H_1(sigma, m)
+ symKey = computeDemKey(&sigma) // H_2(sigma)
+
+ tmpG1 bn256.G1
+ // Ciphertext C = (kem, dem)
+ kem = C[0:kemSize]
+ dem = C[kemSize:]
+ )
+
+ // kem = (A, B, C1). Invoke encasulateKeyStart to compute (A, B)
+ if err := e.encapsulateKeyStart(&sigma, s, kem[0:encKeySize+marshaledG1Size]); err != nil {
+ return err
+ }
+ C1 := kem[encKeySize+marshaledG1Size:]
+
// C1 = (g1^H(id) h)^s
- tmpG1.ScalarMult(&e.g1, id2bignum(id))
+ tmpG1.ScalarMult(&e.g1, val2bignum(idPrefix, []byte(id)))
tmpG1.Add(&tmpG1, &e.h)
tmpG1.ScalarMult(&tmpG1, s)
if err := marshalG1(C1, &tmpG1); err != nil {
return err
}
+
+ // Nonce for symmetric ecnryption can be all-zeroes string, because
+ // we only require one-time semantic security of the underlying symmetric
+ // scheme in the Fujisaki-Okamoto transformation.
+ var nonce [nonceSize]byte
+ if tmp := secretbox.Seal(dem[0:0], m, &nonce, symKey); &tmp[0] != &dem[0] {
+ return fmt.Errorf("output of Seal has unexpected length: expected %d, received %d", len(dem), len(tmp))
+ }
+
return nil
}
+func (e *bb1params) CiphertextOverhead() int {
+ return kemSize + secretbox.Overhead
+}
+
type bb1PrivateKey struct {
params *bb1params // public parameters
d0, d1 bn256.G2
}
func (k *bb1PrivateKey) Decrypt(C, m []byte) error {
- if err := checkSizes(m, C); err != nil {
+ if err := k.params.checkSizes(m, C); err != nil {
return err
}
var (
- A = C[0:len(m)]
+ A = C[0:encKeySize]
B, C1 bn256.G1
+ D = C[kemSize:]
)
- if _, ok := B.Unmarshal(C[len(m) : len(m)+marshaledG1Size]); !ok {
+ if _, ok := B.Unmarshal(C[encKeySize : encKeySize+marshaledG1Size]); !ok {
return errBadCiphertext
}
- if _, ok := C1.Unmarshal(C[len(m)+marshaledG1Size:]); !ok {
+ if _, ok := C1.Unmarshal(C[encKeySize+marshaledG1Size : encKeySize+2*marshaledG1Size]); !ok {
return errBadCiphertext
}
- // M = A ⊕ H(e(B, d0)/e(C1,d1))
+ // sigma = A ⊕ H(e(B, d0)/e(C1,d1))
var (
numerator = bn256.Pair(&B, &k.d0)
denominator = bn256.Pair(&C1, &k.d1)
- hash = sha256.Sum256(numerator.Add(numerator, denominator.Neg(denominator)).Marshal())
+ hash = hashval(ibePrefix, numerator.Add(numerator, denominator.Neg(denominator)).Marshal())
)
- for i := range m {
- m[i] = A[i] ^ hash[i]
+ var sigma [encKeySize]byte
+ for i := range sigma {
+ sigma[i] = A[i] ^ hash[i]
+ }
+
+ symKey := computeDemKey(&sigma)
+
+ var nonce [nonceSize]byte
+ if tmp, success := secretbox.Open(m[0:0], D, &nonce, symKey); !success || (&tmp[0] != &m[0]) {
+ return errBadCiphertext
+ }
+
+ // Check that consistent randomness was used to encrypt the symmetric key. It suffices
+ // to check that the first two components of the KEM portion matches, since given the
+ // message and the secret identity key, the first two components uniquely determine the third.
+
+ // First, derive the randomness used for the KEM.
+ s := computeKemRandomness(&sigma, m)
+
+ // Check the first two components
+ var kemChkBuf [encKeySize + marshaledG1Size]byte
+ k.params.encapsulateKeyStart(&sigma, s, kemChkBuf[:])
+
+ if !bytes.Equal(kemChkBuf[:], C[0:encKeySize+marshaledG1Size]) {
+ return errBadCiphertext
}
return nil
}
+func (k *bb1PrivateKey) Params() Params { return k.params }
+
// random returns a positive integer in the range [1, bn256.Order)
// (denoted by Zp in http://crypto.stanford.edu/~dabo/papers/bbibe.pdf).
//
@@ -197,9 +324,23 @@
}
}
-func id2bignum(id string) *big.Int {
- h := sha256.Sum256([]byte(id))
- k := new(big.Int).SetBytes(h[:])
+// Hash a particular message with the given prefix. Specifically, this computes
+// SHA256(prefix || data) where prefix is a fixed-length string.
+func hashval(prefix [1]byte, data []byte) *[sha256.Size]byte {
+ hasher := sha256.New()
+ hasher.Write(prefix[:])
+ hasher.Write(data)
+
+ var ret [sha256.Size]byte
+ copy(ret[:], hasher.Sum(nil))
+
+ return &ret
+}
+
+// Hashes a value SHA256(prefix || data) where prefix is a fixed-length
+// string. The hashed value is then converted to a value modulo the group order.
+func val2bignum(prefix [1]byte, data []byte) *big.Int {
+ k := new(big.Int).SetBytes(hashval(prefix, data)[:])
return k.Mod(k, bn256.Order)
}
@@ -212,10 +353,3 @@
copy(dst, src)
return nil
}
-
-func checkSizes(m, C []byte) error {
- if msize, Csize := len(m), len(C); msize != PlaintextSize || Csize != CiphertextSize {
- return fmt.Errorf("provided plaintext and ciphertext are of sizes (%d, %d), want (%d, %d)", msize, Csize, PlaintextSize, CiphertextSize)
- }
- return nil
-}
diff --git a/ibe/bb1_test.go b/ibe/bb1_test.go
index b6218c0..fd13fa7 100644
--- a/ibe/bb1_test.go
+++ b/ibe/bb1_test.go
@@ -11,6 +11,24 @@
"testing"
)
+func TestHashVal(t *testing.T) {
+ var (
+ prefix0 = [1]byte{0x00}
+ prefix1 = [1]byte{0x01}
+ msg0 = []byte("message 0")
+ msg1 = []byte("message 1")
+ )
+
+ // Hashes of distinct messages (with the same prefix) should be different
+ if bytes.Equal(hashval(prefix0, msg0)[:], hashval(prefix0, msg1)[:]) {
+ t.Errorf("Hashing two distinct values produced same output")
+ }
+ // Hashes of identical messages with different prefixes should be different
+ if bytes.Equal(hashval(prefix0, msg0)[:], hashval(prefix1, msg1)[:]) {
+ t.Errorf("Hashing two messages with different prefixes produced same output")
+ }
+}
+
func TestBB1Correctness(t *testing.T) {
master, err := SetupBB1()
if err != nil {
@@ -38,11 +56,10 @@
// Encrypt
m := []byte("AThirtyTwoBytePieceOfTextThisIs!")
- C := make([]byte, CiphertextSize)
- C2 := make([]byte, CiphertextSize)
- if msize := len(m); msize != PlaintextSize {
- t.Fatalf("Test string must be %d bytes, not %d", PlaintextSize, msize)
- }
+ overhead := master.Params().CiphertextOverhead()
+ C := make([]byte, len(m)+overhead)
+ C2 := make([]byte, len(m)+overhead)
+
if err := master.Params().Encrypt(alice, m, C); err != nil {
t.Fatal(err)
}
@@ -55,7 +72,7 @@
// Decrypt
decrypt := func(sk PrivateKey) ([]byte, error) {
- ret := make([]byte, PlaintextSize)
+ ret := make([]byte, len(C)-overhead)
if err := sk.Decrypt(C, ret); err != nil {
return nil, err
}
@@ -67,17 +84,52 @@
if decrypted, err := decrypt(aliceSK2); err != nil || !bytes.Equal(decrypted, m) {
t.Errorf("Got (%v, %v), want (%v, nil)", decrypted, err, m[:])
}
- if decrypted, _ := decrypt(bobSK); bytes.Equal(decrypted[:], m[:]) {
+ if _, err := decrypt(bobSK); err == nil {
t.Errorf("Decrypted message with a different PrivateKey")
}
}
-var (
- bb1 Master
- bb1SK PrivateKey
+// Applying the Fujisaki-Okamoto transformation to the BB1 IBE
+// scheme yields a CCA2-secure encryption scheme. Since CCA2-security
+// implies non-malleability, we verify that a tampered ciphertext
+// does not properly decrypt in this test case.
+func TestBB1NonMalleability(t *testing.T) {
+ master, err := SetupBB1()
+ if err != nil {
+ t.Fatal(err)
+ }
+ const alice = "alice"
+ aliceSK, err := master.Extract(alice)
+ if err != nil {
+ t.Fatal(err)
+ }
- benchmarkm = make([]byte, PlaintextSize)
- bb1C = make([]byte, CiphertextSize)
+ m := []byte("01234567899876543210123456789012")
+ overhead := master.Params().CiphertextOverhead()
+ C := make([]byte, len(m)+overhead)
+
+ if err := master.Params().Encrypt(alice, m, C); err != nil {
+ t.Fatal(err)
+ }
+
+ out := make([]byte, len(C)-overhead)
+ // Test that an untampered C can be decrypted successfully.
+ if err := aliceSK.Decrypt(C, out); err != nil || !bytes.Equal(out, m) {
+ t.Fatal(err)
+ }
+ // Test that a tampered C cannot be decrypted successfully.
+ C[0] = C[0] ^ byte(1)
+ if err := aliceSK.Decrypt(C, out); err == nil {
+ t.Fatalf("successfully decrypted a tampered ciphetext: %v", err)
+ }
+}
+
+var (
+ bb1 Master
+ bb1SK PrivateKey
+ benchmarkmlen = 64
+ benchmarkm = make([]byte, benchmarkmlen)
+ bb1C []byte
)
func TestBB1Marshaling(t *testing.T) {
@@ -91,11 +143,12 @@
t.Fatal(err)
}
m := []byte("01234567899876543210123456789012")
+ overhead := bb1P.CiphertextOverhead()
var (
- C1 = make([]byte, CiphertextSize)
- C2 = make([]byte, CiphertextSize)
- m1 = make([]byte, PlaintextSize)
- m2 = make([]byte, PlaintextSize)
+ C1 = make([]byte, len(m)+overhead)
+ C2 = make([]byte, len(m)+overhead)
+ m1 = make([]byte, len(m))
+ m2 = make([]byte, len(m))
)
// Encrypt with the original params, decrypt with the unmarshaled key.
if err := bb1P.Encrypt("alice", m, C1); err != nil {
@@ -158,6 +211,8 @@
if _, err := rand.Read(benchmarkm[:]); err != nil {
panic(err)
}
+ overhead := bb1.Params().CiphertextOverhead()
+ bb1C = make([]byte, benchmarkmlen+overhead)
if err := bb1.Params().Encrypt("alice", benchmarkm, bb1C); err != nil {
panic(err)
}
@@ -173,7 +228,7 @@
func BenchmarkEncryptBB(b *testing.B) {
p := bb1.Params()
- C := make([]byte, CiphertextSize)
+ C := make([]byte, benchmarkmlen+p.CiphertextOverhead())
for i := 0; i < b.N; i++ {
if err := p.Encrypt("alice", benchmarkm, C); err != nil {
b.Fatal(err)
@@ -182,7 +237,7 @@
}
func BenchmarkDecryptBB(b *testing.B) {
- m := make([]byte, PlaintextSize)
+ m := make([]byte, benchmarkmlen)
for i := 0; i < b.N; i++ {
if err := bb1SK.Decrypt(bb1C, m); err != nil {
b.Fatal(err)
diff --git a/ibe/ibe.go b/ibe/ibe.go
index 0d7c60e..4808b3c 100644
--- a/ibe/ibe.go
+++ b/ibe/ibe.go
@@ -32,11 +32,6 @@
// systems (at the time of this writing, only for the Boneh-Boyen scheme).
package ibe
-const (
- PlaintextSize = 32
- CiphertextSize = 160
-)
-
// Master is the interface used to extract private keys for arbitrary identities.
type Master interface {
Extract(id string) (PrivateKey, error)
@@ -48,16 +43,25 @@
type Params interface {
// Encrypt encrypts m into C for the identity id.
//
- // The slices m and C must of PlaintextSize and CiphertextSize respectively,
- // and must not overlap.
+ // The slice C must be of size len(m) + CiphertextOverhead(), and the two
+ // slices must not overlap.
Encrypt(id string, m, C []byte) error
+
+ // The additional space required to encrypt a message, that is,
+ // if a message has length m, the size of the ciphertext is
+ // m + CiphertextOverhead().
+ CiphertextOverhead() int
}
// PrivateKey is the interface used to decrypt encrypted messages.
type PrivateKey interface {
// Decrypt decrypts ciphertext C into m.
//
- // The slices m and C must of PlaintextSize and CiphertextSize respectively,
- // and must not overlap.
+ // The slice m must be of size len(C) - CiphertextOverhead(), and the two
+ // sices must not overlap.
Decrypt(C, m []byte) error
+
+ // Params returns the global system parameters of the Master that
+ // was used to extract this private key.
+ Params() Params
}
