lamport.go

// Package lamport implements lamport signatures.
//
// The lamport scheme is a one-time signature scheme, so each key
// is intended to be used only once. Using a key twice will destroy
// the scheme's security.
//
// Any hash function can be used with the scheme, but keep
// in mind that the lamport scheme's security reduces to the
// security of the hash function.
package lamport

import (
	"crypto"
	"fmt"
	"io"
)

// PrivateKey is the lamport private key.
type PrivateKey struct {
	PublicKey // public key part

	LBlocks []byte // left blocks of the private key
	RBlocks []byte // right blocks of the private key
}

// Public returns the public key corresponding to key.
func (key *PrivateKey) Public() crypto.PublicKey {
	return &key.PublicKey
}

// Sign signs digest with key. opts are ignored, and just
// used to implement crypto.Signer.
func (key *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
	return Sign(key, digest)
}

// PublicKey is the lamport public key.
type PublicKey struct {
	Hash crypto.Hash // the hash function used for the key

	LBlocksP []byte // left blocks of the public key
	RBlocksP []byte // right blocks of the public key
}

// GenerateKey generates a lamport key-pair.
//
// It is suggested to use the crypto/rand reader.
// A classic lamport key would be generated using crypto.SHA256.
//
// Will panic if the hash function is not linked into the binary.
func GenerateKey(random io.Reader, h crypto.Hash) (*PrivateKey, error) {
	// panic immediately if hash not linked
	hash := h.New()
	hashSize := hash.Size()

	keySize := 16 * hashSize * hashSize
	keyBytes := make([]byte, keySize)

	n, err := random.Read(keyBytes)
	if err != nil {
		return nil, fmt.Errorf("lamport: %s", err)
	}
	if n != keySize {
		return nil, fmt.Errorf("lamport: not enough entropy")
	}

	blocksSize := keySize / 2
	LBlocks := keyBytes[:blocksSize]
	RBlocks := keyBytes[blocksSize:]

	LBlocksP := make([]byte, 0, blocksSize)
	RBlocksP := make([]byte, 0, blocksSize)

	for off := 0; off < blocksSize; off += hashSize {
		hash.Write(LBlocks[off : off+hashSize]) // nolint, error always nil
		LBlocksP = append(LBlocksP, hash.Sum(nil)...)
		hash.Reset()

		hash.Write(RBlocks[off : off+hashSize]) // nolint, error always nil
		RBlocksP = append(RBlocksP, hash.Sum(nil)...)
		hash.Reset()
	}

	pk := PublicKey{
		Hash:     h,
		LBlocksP: LBlocksP,
		RBlocksP: RBlocksP,
	}
	k := &PrivateKey{
		PublicKey: pk,

		LBlocks: LBlocks,
		RBlocks: RBlocks,
	}

	return k, nil
}

var ones = []byte{0x80, 0x40, 0x20, 0x10, 0x8, 0x4, 0x2, 0x1}

// Sign generates a lamport signature over hashed.
//
// Will panic if hash function not linked to binary.
// It is expected that "hashed" was generated by priv.Hash,
// but it's only necessary that it be the same length as the
// hash size.
func Sign(priv *PrivateKey, hashed []byte) ([]byte, error) {
	// panic immediately if hash not linked
	hash := priv.Hash.New()
	hashSize := hash.Size()

	if hashSize != len(hashed) {
		return nil, fmt.Errorf("lamport: hash length mismatch")
	}

	sigSize := 8 * hashSize * hashSize
	sig := make([]byte, 0, sigSize)

	off := 0
	for _, b := range hashed {
		for _, o := range ones {
			if b&o == 0 {
				sig = append(sig, priv.LBlocks[off:off+hashSize]...)
			} else {
				sig = append(sig, priv.RBlocks[off:off+hashSize]...)
			}

			off += hashSize
		}
	}

	return sig, nil
}

// Verify verifies a lamport signature sig, over hashed.
//
// Will panic if hash function not linked to binary.
// It is expected that "hashed" was generated by pub.Hash,
// but it's only necessary that it be the same length as the
// hash size.
func Verify(pub *PublicKey, hashed []byte, sig []byte) error {
	// panic immediately if hash not linked
	hash := pub.Hash.New()

	hashSize := hash.Size()
	if hashSize != len(hashed) {
		return fmt.Errorf("lamport: hash length mismatch")
	}

	sigSize := 8 * hashSize * hashSize
	if sigSize != len(sig) {
		return fmt.Errorf("lamport: bad signature")
	}

	off := 0
	for _, b := range hashed {
		for _, o := range ones {
			hash.Write(sig[off : off+hashSize]) // nolint, error always nil

			var same bool
			if b&o == 0 {
				same = bytesSame(pub.LBlocksP[off:off+hashSize], hash.Sum(nil))
			} else {
				same = bytesSame(pub.RBlocksP[off:off+hashSize], hash.Sum(nil))
			}

			if !same {
				return fmt.Errorf("lamport: bad signature")
			}

			hash.Reset()
			off += hashSize
		}
	}

	return nil
}

// assumes same size
func bytesSame(a, b []byte) bool {
	for i := range a {
		if a[i] != b[i] {
			return false
		}
	}

	return true
}