README
¶
Oblivous Go maps
This package provides secure storage of map[string]string objects. The
contents of the structure cannot be deduced from its public representation, and
querying it requires knowledge of a secret key. It is suitable for client/server
protocols where the service is trusted only to provide storage. In addition to
providing confidentiality, it allows the client to verify the integrity of the
server's responses.
An overview and installation instructions follow; the package documentation is indexed on GoDoc.
DISCLAIMER: This
code is related to a research paper, which will be up on ePrint at some point.
FUTURE WORK:
Currently this package only provides immutable storage of maps, meaning once
you've created a data store, you can't change its contents. However, with some
modifications it should be possible to insert, remove, and update input/output
pairs securely. I'll be working on this next.
The store package
The main package provides two data structures: Store and Dict. The
former offers confidentiality and integrity for map[string]string objects
with arbitrary-length inputs and outputs. Its security follows from the
combination of authenticated encryption with associated data
(AEAD) and the latter
structure, which offers only confidentiality and is only suitable for maps
who's outputs are of length at most 60.
Store.
The client possesses a secret key K and data M (of type map[string]string).
It executes:
pub, priv, err := store.NewStore(K, M)
and transmits pub, the public representation of M, to the server.
To compute M[input], the client executes:
x, y, err := priv.GetIdx(input)
and sends x and y (both of type int) to the server. The pair (x,y) is
called the index and is used by the server to compute its share of the
output. The server computes:
pubShare, err := pub.GetShare(x, y)
and sends pubShare (of type []byte) to the client. Finally, the client
executes:
output, err := priv.GetOutput(input, pubShare)
This combines pubShare with a private share computed from input and K.
The result is output = M[input]. Note that the server is not entrusted with
the key; its only job is to look up the index requested by the client. The
underlying data structure is designed so that no information about input or
output is leaked to any party not in possession of the secret key.
For convenience, this package also provides an interface for querying pub
directly:
output, err := priv.Get(pub, input)
Dict. This light-weight structure is the core of Store. The Go package is an interface for the underlying C implementation. It can be used in exactly the same way as Store, but is only suitable for short (60 byte) outputs. See the package documentation for an explanation of this limitation. To construct it, the client executes:
pub, priv, err := store.NewDict(K, M)
The remaining functions are as above.
The store/pb package
File pb/store.proto specifies a bare-bones remote procedure
call for the client and server
roles in the protocol above.
The StoreProvider service.
The user computes pub from its map M and key K and provisions the
service provider (out-of-band) with pub. The request consists of the user
and (x,y), and the response consists of the pubShare computed from x, y,
and pub.
This simple RPC provides no authentication of the user, so any anyone can get
the entire public store of any user. This is not a problem, however, as long
as the adversary doesn't know (or can't guess) K. But if K is derived from a
password, for example, then the contents of pub are susceptible to dictionary
attacks.
For documentation of this package, check out the GoDoc index.
Installation
First, you'll need Go. To get the latest version on Ubuntu, do
$ sudo add-apt-repository ppa:longsleep/golang-backports
$ sudo apt update
$ sudo apt install golang-go
On Mac, download the pkg and install it. Next, add the
following lines to the end of.bashrc on Ubuntu or .bash_profile on Mac:
export GOPATH="$HOME/go"
export PATH="$PATH:$GOPATH/bin"
In a new terminal, make the directory $HOME/go, go to the directory and type:
go get github.com/cjpatton/store
This downloads this repository and puts it in
go/src/github.com/cjpatton/store.
Next, the core data structures are implemented in C. (Navigate to
go/src/github.com/cjpatton/store/c/.) The Makefile compiles a shared object
for which the Go code has bindings. They depend on OpenSSL (SHA512 and
HMAC-SHA512), so you'll need to install this library in advance. On Ubuntu:
$ sudo apt-get install libssl-dev
On Mac via Homebrew:
$ brew install openssl
(Homebrew puts the includes in /usr/local/opt/openssl/include, which is a
non-standard location. Makefile passes this directory to the compioler via
-I, so this shouldn't be a problem.) To build the C code and run tests do:
$ make && make test
Note that, since the data strucutres are probabilistic, the tests will produce warnings from time to time. (This is OK as long as it doesn't produce a lot of warnings.) To install, do
$ sudo make install && sudo ldconfig
This builds a file called libstructsec.so and moves it to /usr/local/lib and
copies the header files to /usr/local/include/structsec.
Now you should be able to build the package. To run tests, do
$ go test github.com/cjpatton/store
Running the toy application
hadee/server/hadee_server.go implements the RPC service and serves a single
user. It takes as input the user name and a file containing the public store.
To run it, first generate a sample store by doing:
$ cd hadee/gen && go install && hadee_gen
It will prompt you for a "master password" used to derive a key, which is used
to generate the structure. This writes a file store.pub to the current
directory. (The map it represents is hard-coded in the Go code.) To run the
server, do:
$ cd hadee/server && go install && hadee_server cjpatton store.pub
This opens a TCP socket on localhost:50051 and begins serving requests. To run the client, do:
$ cd hadee/client && go install && hadee_client cjpatton
SECURITY WARNING:
Do NOT use this for anything real. As is, the protocol is susceptible to
dictionary attacks on the master password.
Modifying store.proto
You only need to do this if you want to modify the protocol buffers or RPC.
This project uses protcool buffers and remote procedure calls. To build you'll
first need the lastest version of protoc. Go to protobuf
documentation
for instructions. To build store.pb.go, go to
$HOME/go/src/github.com/cjpatton/store/pb and run
$ protoc -I . store.proto --go_out=plugins=grpc:.
Note that you only need to do this if you modify store.proto.
Copyright notice
This software is distributed under the terms of the 3-Clause BSD License; see
LICENSE in the root project directory for details.
Documentation
¶
Overview ¶
Package store provides secure storage of map[string]string objects. It combines an AEAD ("authenticated encryption with associated data") scheme and a data structure for representing functions called a Bloomier filter. It is suited client/server protocols in which the server is trusted only to provide storage. The client possesses a secret key K and data M (of type map[string]string). It executes:
pub, priv, err := store.NewStore(K, M)
and transmits pub, the public representation of M, to the server. To compute M[input], the client executes:
x, y, err := priv.GetIdx(input)
and sends x and y to the server. These are integers corresponding to rows in a table encoded by pub. The server executes:
pubShare, err := pub.GetShare(x, y)
and sends pubShare (of type []byte) to the client. (This is the XOR of the two rows requested by the client.) Finally, the client executes:
output, err := priv.GetOutput(input, pubShare)
This combines pubShare with the private share computed from input and the key. The result is M[input]. Note that the server is not entrusted with the key; its only job is to look up the rows of the table requested by the client. The data structure is designed so that no information about input or output (except for the length of the output) is leaked to any party not in possession of the client's secret key.
At the core of data structure is a Bloomier filter, a variant of a technique of Charles and Chellapilla for representing functions. (See "Bloomier Filters: A second look", appearing at ESA 2008.) It is implemented in C, but this package provides Go bindings. You can use it similarly to Store:
pub, priv, err := store.NewDict(K, M) x, y, err := priv.GetIdx(input) pubShare, err := pub.GetShare(x, y) output, err := priv.GetOutput(input, pubShare)
However, the length of the outputs is limited to 60 bytes, a limitation we now explain. The idea of Dict is that each input is mapped to two rows of a table so that, when these rows are added together (i.e., their bitwise-XOR is computed), the result is equal to the output. The look up is performed using hash functions. The table has L rows and each row is 64 bytes in length. Roughly speaking, the query is evaluated as follows:
x := H1(input) // An integer in range [1..L] y := H2(input) // An integer in range [1..L] pad := H3(input) // A string of length 64 bytes output := Table[x] ^ Tabley[y] ^ pad
(Note that the above is pseudocode; the functions H1, H2, and H3 are not provided.) In our setting, the hash functions are implemented using HMAC-SHA512, which is a keyed, pseudorandom function. The output of HMAC-SHA512 is 64 bytes in length.
If some query is not in the table, then the result of the query should indicate as much. This is accomplished by appending a tag to the output. After adding up the pad and table rows, we check if the last few bytes are 0; if so, then the input/output pair is in the map; otherwise the input/output pair is not in the map. 4 bytes of each row are allocated for the tag and padding of the output; hence, each output must be at most 60 bytes long. Note that this makes the data structure probabilistic, since there is a small chance that, when the query is evaluated, the tag bytes will all equal 0, even though the input is not correct.
NOTE: Dict does not on its own provide integrity protection, as Store does. It's meant to be extremely light weight, and in fact is a core component of Store.
NOTE: The underlying data structure is implemented in C. The source can be found in github.com/cjpatton/store/c; refer to github.com/cjpatton/store/README.md for installation instructions.
Index ¶
- Constants
- func DeriveKeyFromPassword(password, salt []byte) []byte
- func GenerateDictKey() []byte
- func GenerateKey() []byte
- func NewDict(K []byte, M map[string]string) (*PubDict, *PrivDict, error)
- func NewStore(K []byte, M map[string]string) (pub *PubStore, priv *PrivStore, err error)
- type Error
- type PrivDict
- type PrivStore
- type PubDict
- type PubStore
Examples ¶
Constants ¶
const DictKeyBytes = C.HMAC_KEY_BYTES
Length of the HMAC key. HMAC_KEY_BYTES is defined in c/const.h.
const ErrorIdx = Error("index out of range")
Returned by pub.GetShare() in case x or y is not in the table index.
const ErrorMapTooLarge = Error("input map is too large")
Returned by NewStore() in case the number of elements in the input exceeds the number of unique counters.
const ItemNotFound = Error("item not found")
Returned by Get() and priv.GetOutput() if the input was not found in the map.
const KeyBytes = DictKeyBytes + SealKeyBytes
Length of the store key.
const MaxOutputBytes = MaxRowBytes - TagBytes - 1
The maximum length of the outputs. 1 byte of each row is allocated for padding the output string.
const MaxRowBytes = C.HASH_BYTES
The maximum length of the row. In general, the length of the row depends on the length of the longest output in the map. HASH_BYTES is defined in c/const.h.
const SaltBytes = 8
Number of bytes to use for the salt, a random string used to construct the table. It is prepended to the input of each HMAC call.
const SealKeyBytes = 16
Length of key for sealing the outputs. (AEAD is AES128-GCM.)
const TagBytes = 2
Number of row bytes allocated for the tag.
Variables ¶
This section is empty.
Functions ¶
func DeriveKeyFromPassword ¶
DeriveKeyFromPassword derives a key from a password and (optional) salt and returns it.
If salt == nil, then no salt is used. Note that the salt is not the same as pb.Params.Salt. pb.Params.Salt is generated by NewDict(), which in turn depends on the key.
Example ¶
password := []byte("A really secure password")
salt := []byte("Optional salt, useful in many applications")
K := DeriveKeyFromPassword(password, salt)
fmt.Println(len(K))
Output: 32
func GenerateDictKey ¶
func GenerateDictKey() []byte
GenerateKey generates a fresh, random key and returns it.
func GenerateKey ¶
func GenerateKey() []byte
GenerateKey generates a fresh, random key and returns it.
Example ¶
K := GenerateKey() fmt.Println(len(K))
Output: 32
func NewDict ¶
New generates a new structure (pub, priv) for the map M and key K.
You must call pub.Free() and priv.Free() before these variables go out of scope. These structures contain C types that were allocated on the heap and must be freed before losing a reference to them.
func NewStore ¶
NewStore creates a new store for key K and map M.
You must call pub.Free() and priv.Free() before these variables go out of scope. This is necessary because these structures contain memory allocated from the heap in C.
Example ¶
K := GenerateKey()
M := map[string]string{"Out": "of this world!"}
pub, priv, err := NewStore(K, M)
if err != nil {
fmt.Println("NewStore() error:", err)
return
}
defer pub.Free()
defer priv.Free()
x, y, err := priv.GetIdx("Out")
if err != nil {
fmt.Println("priv.GetIdx() error:", err)
return
}
pubShare, err := pub.GetShare(x, y)
if err != nil {
fmt.Println("pub.GetShare() error:", err)
return
}
out, err := priv.GetOutput("Out", pubShare)
if err != nil {
fmt.Println("priv.GetOutput() error:", err)
return
}
fmt.Println(out)
Output: of this world!
Types ¶
type PrivDict ¶
type PrivDict struct {
// contains filtered or unexported fields
}
The private state required for evaluation queries.
func NewPrivDict ¶
NewPrivDict creates a new *PrivDict from a key and parameters.
You must destroy this with priv.Free().
func (*PrivDict) Free ¶
func (priv *PrivDict) Free()
Free deallocates moemory associated with the C implementation of the underlying data structure.
func (*PrivDict) Get ¶
Get queries input on the structure (pub, priv). The result is M[input] = output, where M is the map represented by (pub, priv).
func (*PrivDict) GetIdx ¶
GetIdx computes the two indices of the table associated with input and returns them.
type PrivStore ¶
type PrivStore struct {
// contains filtered or unexported fields
}
Stores the private context used to query the map.
func NewPrivStore ¶
NewPrivStore creates a new private store context from a key and parameters.
You must call priv.Free() before priv goes out of scope.
Example ¶
K := GenerateKey()
M := map[string]string{"Out": "of this world!"}
pub, priv, err := NewStore(K, M)
if err != nil {
fmt.Println("NewStore() error:", err)
return
}
defer pub.Free()
defer priv.Free()
privFromKeyAndPrivParams, err := NewPrivStore(K, priv.GetParams())
if err != nil {
fmt.Println("NewPrivStore() error:", err)
}
defer privFromKeyAndPrivParams.Free()
privFromKeyAndPubParams, err := NewPrivStore(K, pub.GetProto().GetDict().GetParams())
if err != nil {
fmt.Println("NewPrivStore() error:", err)
}
defer privFromKeyAndPubParams.Free()
Output:
func (*PrivStore) Free ¶
func (priv *PrivStore) Free()
Free releases memory allocated to the private context's internal representation.
func (*PrivStore) GetOutput ¶
GetOutput computes the final output from input and the public share.
The nonce is the constructed from combining the table public share with the private share and concatenating the result to the salt. The associated data is the input. Returns ItemNotFound if unsealing the output fails.
type PubDict ¶
type PubDict struct {
// contains filtered or unexported fields
}
The public representation of the map.
func NewPubDictFromProto ¶
NewPubDictFromProto creates a new *PubDict from a *pb.Dict.
You must destroy with pub.Free().
func (*PubDict) Free ¶
func (pub *PubDict) Free()
Free deallocates memory associated with the underlying C implementation of the data structure.
type PubStore ¶
type PubStore struct {
// contains filtered or unexported fields
}
Stores the public representation of the map.
func NewPubStoreFromProto ¶
NewPubStoreFromProto creates a public store from its protobuf representation.
You must call pub.Free() before pub goes out of scope.
func (*PubStore) Free ¶
func (pub *PubStore) Free()
Free releases memory allocated to the public store's internal representation.
func (*PubStore) GetProto ¶
GetProto creates a protobuf representation of the public store.
This is a compact representation suitable for transmission.
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
hadee
|
|
|
client
hadee_client is a toy client that makes RPC requests to hadee_server.
|
hadee_client is a toy client that makes RPC requests to hadee_server. |
|
gen
hadee_gen generates a sample store from a password.
|
hadee_gen generates a sample store from a password. |
|
server
hadee_serv is a toy server implementing the StoreProvider RPC specified in store.proto.
|
hadee_serv is a toy server implementing the StoreProvider RPC specified in store.proto. |
|
Package pb is a generated protocol buffer package.
|
Package pb is a generated protocol buffer package. |