redactionschemes

README

Golang Library for Redactable Signatures

⚠️WARNING⚠️ THIS LIBRARY HAS NOT BEEN VERIFIED AT ALL AND IS PROBABLY NOT SAFE TO USE!!!

This library includes 3 verifiable redaction schemes:

• A naive scheme
• A Merkle tree-based scheme by Johnson et al.
• An RSA-based scheme by Johnson et al.

Currently, all schemes use SHA256 for hashing, and the Merkle and Naive scheme use ECDSA for signing.

Partitioning

To keep the signatures small and the sign/verify/redact operations efficient, the input data is stored in partitions of data. We provide a helper struct PartitionedData with many helper functions to handle this.

TODO

• Make hash function modular.
• Probably replace PartitionedData with something more sensible?
• Merkle tree-based scheme very convoluted logic

Short Description of Each Scheme

Naive Scheme

NaiveSignature simply uses the underlying ECDSA key to sign each partition individually. To prohibit the reuse of each partition (reordering attack), we append an ID on each hash, as well as its position. We hard coded the hash of the data as ID. For a message m of length n, the signature is:

Sig(H(n || ID)) || Sig(H(ID || 0 || m_0)) || ... || Sig(H(ID || n || m_n))

Merkle Tree-based Scheme

JohnsonMerkleSignature is based on Johnson et al. and uses a Merkle tree-based structure to sign the data. The signature benefits from consecutive redactions, as neighboring redacted nodes in the Merkle tree will be merged. Thus the signature is largest, if the redaction is sparse.

RSA-based Scheme

JohnsonRSASignature is based on Johnson et al. and uses the RSA accumulator technique to achieve a constant sized signature. This currently use a hash function which maps to the primes, I don't know if this is safe or even sane... Due to the repeated exponentiations, this scheme can get really slow!

Documentation

Index

• func ArgDiffArray(arr_1 *PartitionedData, arr_2 *PartitionedData) (map[int]bool, error)
• func Base64ImageToByteArray(image_base64encoded string) ([]byte, error)
• func BoolArrayToImage(inputMatrix [][]bool, bounds image.Rectangle) image.Image
• func CommaSeperatedIndicesArray(s string) ([]int, error)
• func CommaSeperatedIndicesToBoolMatrix(s string, m, n int) ([][]bool, error)
• func CommaSeperatedIndicesToMismatchesMap(s string) (map[int]bool, error)
• func G(InputBytes []byte) []byte
• func GetEulerPhi(priv *rsa.PrivateKey) *big.Int
• func H(InputBytes []byte) []byte
• type JohnsonMerkleSignature
  • func SignJohnsonSignature(data *PartitionedData, priv_key *ecdsa.PrivateKey) JohnsonMerkleSignature
  • func UnmarshalJohnsonMerkleSignature(sig_string string) (JohnsonMerkleSignature, error)
  • func (sig JohnsonMerkleSignature) Marshal() (string, error)
  • func (orig_signature JohnsonMerkleSignature) Redact(old_data *PartitionedData, redacted_chunks map[int]bool) (JohnsonMerkleSignature, error)
  • func (sig JohnsonMerkleSignature) Verify(data *PartitionedData) error
• type JohnsonRSASignature
  • func SignJohnsonRSA(random io.Reader, x *PartitionedData, priv *rsa.PrivateKey, phi *big.Int) JohnsonRSASignature
  • func UnmarshalJohnsonRSASignature(input string) (JohnsonRSASignature, error)
  • func (sig JohnsonRSASignature) Marshal() (string, error)
  • func (sig JohnsonRSASignature) Redact(RemovedIndices []int, x *PartitionedData) (PartitionedData, JohnsonRSASignature)
  • func (sig JohnsonRSASignature) Verify(x *PartitionedData) bool
• type NaiveSignature
  • func SignNaivSignature(data *PartitionedData, priv_key *ecdsa.PrivateKey) (NaiveSignature, error)
  • func UnmarshalNaiveSignature(sig_string string) (NaiveSignature, error)
  • func (sig NaiveSignature) Marshal() (string, error)
  • func (sig NaiveSignature) Verify(data *PartitionedData) error
• type PartitionedData
  • func ImageToPartitionedData(img image.Image, chunksX int, chunksY int) (PartitionedData, error)
  • func PadChunkArrayToTwoPow(input *PartitionedData) (int, PartitionedData)
  • func StringToPartitionedData(s string) PartitionedData
  • func UnmarshalPartitionedData(s string) (*PartitionedData, error)
  • func (c PartitionedData) GetRedactedIndicesArray() []int
  • func (c PartitionedData) GetRedactedIndicesArrayImage(chunkX, chunkY int) []int
  • func (c PartitionedData) Hash() []byte
  • func (c PartitionedData) Marshal() (string, error)
  • func (c PartitionedData) Redact(mismatches map[int]bool) (*PartitionedData, error)
  • func (c PartitionedData) ToByteArray() []byte
  • func (c PartitionedData) ToDataURL(chunksX int, chunksY int) (string, error)
  • func (c PartitionedData) ToDataURLs() []string
  • func (c PartitionedData) ToHTMLString() string
  • func (c PartitionedData) ToImage(chunksX int, chunksY int) (image.Image, error)

Functions

func ArgDiffArray

func ArgDiffArray(arr_1 *PartitionedData, arr_2 *PartitionedData) (map[int]bool, error)

ArgDiffArray returns the indexes where arr_1 and arr_2 mismatch. arr_1 and arr_2 have to be of the same size.

func Base64ImageToByteArray

func Base64ImageToByteArray(image_base64encoded string) ([]byte, error)

func BoolArrayToImage

func BoolArrayToImage(inputMatrix [][]bool, bounds image.Rectangle) image.Image

func CommaSeperatedIndicesArray

func CommaSeperatedIndicesArray(s string) ([]int, error)

func CommaSeperatedIndicesToBoolMatrix

func CommaSeperatedIndicesToBoolMatrix(s string, m, n int) ([][]bool, error)

func CommaSeperatedIndicesToMismatchesMap

func CommaSeperatedIndicesToMismatchesMap(s string) (map[int]bool, error)

func G

func G(InputBytes []byte) []byte

Length-doubling pseudorandom generator

func GetEulerPhi

func GetEulerPhi(priv *rsa.PrivateKey) *big.Int

func H

func H(InputBytes []byte) []byte

Cryptographic hash function (just sha256)

Types

type JohnsonMerkleSignature

type JohnsonMerkleSignature struct {
	BaseSignature []byte
	PublicKey     ecdsa.PublicKey
	Key           []byte                      // This is only visible before the redaction
	RedactedKeys  map[string]redactedProperty // And this afterwards, these are the conodes keys
	RedactedHash  map[string]redactedProperty // and these the hashes of the parents of the redacted nodes
}

func SignJohnsonSignature

func SignJohnsonSignature(data *PartitionedData, priv_key *ecdsa.PrivateKey) JohnsonMerkleSignature

SignJohnsonSignature uses the priv_key to sign data redactably. Key size for each node is currently 128 bit, key is randomly generated

func UnmarshalJohnsonMerkleSignature

func UnmarshalJohnsonMerkleSignature(sig_string string) (JohnsonMerkleSignature, error)

func (JohnsonMerkleSignature) Marshal

func (sig JohnsonMerkleSignature) Marshal() (string, error)

func (JohnsonMerkleSignature) Redact

func (orig_signature JohnsonMerkleSignature) Redact(old_data *PartitionedData, redacted_chunks map[int]bool) (JohnsonMerkleSignature, error)

RedactJohnsonSignature redacts an existing signature based on the new_data. When redacting, k_epsilon is not publicsed, as with it we could just calculate all the hashes and possibly get access to the redacted data by bruteforcing or similar. Instead, we just publicise the co-nodes keys, as well as the parent node of the redacted leaf

func (JohnsonMerkleSignature) Verify

func (sig JohnsonMerkleSignature) Verify(data *PartitionedData) error

VerifyJohnsonSignature verifies if a given signature matches the supplied data This rebuilds the tree by regenerating the co-node-trees, as well as using the supplied hashes to retrieve the root node hash

type JohnsonRSASignature

type JohnsonRSASignature struct {
	DocumentKey   []byte
	BaseSignature big.Int
	Generator     big.Int
	PublicKey     rsa.PublicKey
}

func SignJohnsonRSA

func SignJohnsonRSA(random io.Reader, x *PartitionedData, priv *rsa.PrivateKey, phi *big.Int) JohnsonRSASignature

Signs the input data according to the paper

func UnmarshalJohnsonRSASignature

func UnmarshalJohnsonRSASignature(input string) (JohnsonRSASignature, error)

func (JohnsonRSASignature) Marshal

func (sig JohnsonRSASignature) Marshal() (string, error)

func (JohnsonRSASignature) Redact

func (sig JohnsonRSASignature) Redact(RemovedIndices []int, x *PartitionedData) (PartitionedData, JohnsonRSASignature)

Redacts an existing signature by mutliplying it with the removed hashes

func (JohnsonRSASignature) Verify

func (sig JohnsonRSASignature) Verify(x *PartitionedData) bool

Verifies a signature according to the paper

type NaiveSignature

type NaiveSignature struct {
	Identifier    []byte
	Length        int
	BaseSignature []byte
	Signatures    [][]byte
	PublicKey     ecdsa.PublicKey
}

func SignNaivSignature

func SignNaivSignature(data *PartitionedData, priv_key *ecdsa.PrivateKey) (NaiveSignature, error)

func UnmarshalNaiveSignature

func UnmarshalNaiveSignature(sig_string string) (NaiveSignature, error)

func (NaiveSignature) Marshal

func (sig NaiveSignature) Marshal() (string, error)

func (NaiveSignature) Verify

func (sig NaiveSignature) Verify(data *PartitionedData) error

type PartitionedData

type PartitionedData [][]byte

func ImageToPartitionedData

func ImageToPartitionedData(img image.Image, chunksX int, chunksY int) (PartitionedData, error)

ImagetoPartitionedData converts a html-base64 encoded image into a chunk array with chunksX * chunksY resolution.

func PadChunkArrayToTwoPow

func PadChunkArrayToTwoPow(input *PartitionedData) (int, PartitionedData)

PadByteArrayToTwoPow pads a byte array two a length of power of two. This is not actually needed, but makes generating and working with the tree way easier

func StringToPartitionedData

func StringToPartitionedData(s string) PartitionedData

StringToPartitionedData converts a string s to a chunk array word-wise

func UnmarshalPartitionedData

func UnmarshalPartitionedData(s string) (*PartitionedData, error)

func (PartitionedData) GetRedactedIndicesArray

func (c PartitionedData) GetRedactedIndicesArray() []int

func (PartitionedData) GetRedactedIndicesArrayImage

func (c PartitionedData) GetRedactedIndicesArrayImage(chunkX, chunkY int) []int

func (PartitionedData) Hash

func (c PartitionedData) Hash() []byte

func (PartitionedData) Marshal

func (c PartitionedData) Marshal() (string, error)

func (PartitionedData) Redact

func (c PartitionedData) Redact(mismatches map[int]bool) (*PartitionedData, error)

func (PartitionedData) ToByteArray

func (c PartitionedData) ToByteArray() []byte

func (PartitionedData) ToDataURL

func (c PartitionedData) ToDataURL(chunksX int, chunksY int) (string, error)

func (PartitionedData) ToDataURLs

func (c PartitionedData) ToDataURLs() []string

ToDataURLs will decode each image chunk, as we need reproducability at the end The client has to stitch together the image if this is used

func (PartitionedData) ToHTMLString

func (c PartitionedData) ToHTMLString() string

func (PartitionedData) ToImage

func (c PartitionedData) ToImage(chunksX int, chunksY int) (image.Image, error)