store

package module
Version: v0.0.0-...-43d270f Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jun 12, 2019 License: BSD-3-Clause Imports: 12 Imported by: 0

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.

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

Examples

Constants

View Source
const DictKeyBytes = C.HMAC_KEY_BYTES

Length of the HMAC key. HMAC_KEY_BYTES is defined in c/const.h.

View Source
const ErrorIdx = Error("index out of range")

Returned by pub.GetShare() in case x or y is not in the table index.

View Source
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.

View Source
const ItemNotFound = Error("item not found")

Returned by Get() and priv.GetOutput() if the input was not found in the map.

Length of the store key.

View Source
const MaxOutputBytes = MaxRowBytes - TagBytes - 1

The maximum length of the outputs. 1 byte of each row is allocated for padding the output string.

View Source
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.

View Source
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.

View Source
const SealKeyBytes = 16

Length of key for sealing the outputs. (AEAD is AES128-GCM.)

View Source
const TagBytes = 2

Number of row bytes allocated for the tag.

Variables

This section is empty.

Functions

func DeriveKeyFromPassword

func DeriveKeyFromPassword(password, salt []byte) []byte

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

func NewDict(K []byte, M map[string]string) (*PubDict, *PrivDict, error)

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

func NewStore(K []byte, M map[string]string) (pub *PubStore, priv *PrivStore, err error)

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 Error

type Error string

func (Error) Error

func (err Error) Error() string

type PrivDict

type PrivDict struct {
	// contains filtered or unexported fields
}

The private state required for evaluation queries.

func NewPrivDict

func NewPrivDict(K []byte, params *pb.Params) (*PrivDict, error)

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

func (priv *PrivDict) Get(pub *PubDict, input string) (string, error)

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

func (priv *PrivDict) GetIdx(input string) (int, int, error)

GetIdx computes the two indices of the table associated with input and returns them.

func (*PrivDict) GetOutput

func (priv *PrivDict) GetOutput(input string, pubShare []byte) (string, error)

GetOutput computes the output associated with the input and the table rows.

func (*PrivDict) GetParams

func (priv *PrivDict) GetParams() *pb.Params

GetParams returns the public parameters of the data structure.

type PrivStore

type PrivStore struct {
	// contains filtered or unexported fields
}

Stores the private context used to query the map.

func NewPrivStore

func NewPrivStore(K []byte, params *pb.Params) (priv *PrivStore, err error)

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) Get

func (priv *PrivStore) Get(pub *PubStore, input string) (string, error)

Get looks up input in the public store and returns the result.

func (*PrivStore) GetIdx

func (priv *PrivStore) GetIdx(input string) (int, int, error)

GetIdx computes the index corresponding to the input.

func (*PrivStore) GetOutput

func (priv *PrivStore) GetOutput(input string, pubShare []byte) (string, error)

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.

func (*PrivStore) GetParams

func (priv *PrivStore) GetParams() *pb.Params

GetParams returns the public parameters of the store.

type PubDict

type PubDict struct {
	// contains filtered or unexported fields
}

The public representation of the map.

func NewPubDictFromProto

func NewPubDictFromProto(table *pb.Dict) *PubDict

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.

func (*PubDict) GetProto

func (pub *PubDict) GetProto() *pb.Dict

GetProto returns a *pb.Dict representation of the dictionary.

func (*PubDict) GetShare

func (pub *PubDict) GetShare(x, y int) ([]byte, error)

GetShare returns the bitwise-XOR of the x-th and y-th rows of the table.

func (*PubDict) String

func (pub *PubDict) String() string

String returns a string representation of the table.

type PubStore

type PubStore struct {
	// contains filtered or unexported fields
}

Stores the public representation of the map.

func NewPubStoreFromProto

func NewPubStoreFromProto(table *pb.Store) (pub *PubStore)

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

func (pub *PubStore) GetProto() *pb.Store

GetProto creates a protobuf representation of the public store.

This is a compact representation suitable for transmission.

func (*PubStore) GetShare

func (pub *PubStore) GetShare(x, y int) ([]byte, error)

GetShare computes the pubShare corresponding to the index (x, y).

The payload is comprised of the public share of the dictionary table and the sealed output corresponding to the share. This function returns ItemNotFound if there is no such sealed output.

func (*PubStore) String

func (pub *PubStore) String() string

String returns a string representing the public storage.

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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL