Documentation
¶
Overview ¶
Package tesla implements a TESLA-inspired hash-chain key schedule for delayed disclosure of packet authentication keys.
Key Schedule Overview ¶
Keys form a backward hash chain: the executor generates a random secret seed k_L (the tail) and hashes it L times to obtain the public anchor k_0:
k_0 = H^L(k_L) (public anchor, published at setup)
k_i = H(k_{i+1}) (each key is the hash of the next one)
The executor uses key k_i during epoch i (1 ≤ i < L) and discloses it once the disclosure delay of d ≥ 2 epochs has elapsed, at the start of epoch i+d (see Disclosure). Because k_0 is public, epoch 0 has no signing key: nothing is tagged before epoch 1 starts. Because k_L is never disclosed, nothing is tagged from epoch L on either. A verifier who has buffered packets from epoch i can verify them once k_i is published by checking:
H^i(k_i) == k_0
Given a disclosed key k_τ, the key for an earlier epoch t (t ≤ τ) is reconstructed by hashing forward τ-t times:
k_t = H^(τ-t)(k_τ)
Per-Measurement Derivation ¶
Because a single executor may service multiple measurements concurrently, an additional per-measurement key ak is derived from the current chain key:
ak = HKDF-SHA256(secret=k_i, info=measurement_id, length=32)
Authentication Tag ¶
The authentication tag written into the IPv4 IPID field follows the versioned tag specification TagSpec (docs/tag-spec.md):
tag = SipHash-2-4(ak[0:16], canonical(packet)) mod 2^16
where canonical takes the first min(64, total length) bytes and zeroes the fields a router, NAT or checksum offload rewrites. The eBPF tagger (tagger.c) and the pure-Go fallback compute it identically; see HashInput and PacketTag.
Disclosure ¶
k_i is disclosed no earlier than the start of epoch i+d, where the disclosure delay d (Config.DisclosureDelay) is at least MinDisclosureDelay epochs. This is TESLA's safety condition: a verifier accepts k_i only for packets it received before k_i could have been disclosed, and it tries the packet's epoch t and its predecessor t-1 to absorb clock skew. With d = 1, k_{t-1} would be public during epoch t, so anyone who saw it could forge tags that verify for packets timestamped in epoch t. With d ≥ 2 the key of every candidate epoch is still secret while its packets are in flight; the margin (d-1)·I must exceed the verifier's clock tolerance plus the skew between the executor, the dispatcher and the capture host.
A key is also disclosed no earlier than the first heartbeat after every kernel tagger of the chain has moved off it. Each eBPF tagger registers with the schedule as an InstalledKeyHolder and reports the epoch whose key its map slot may still hold; DisclosedKey never names that epoch or a later one. The kernel taggers refresh their key at each epoch boundary, so in the ordinary case the taggers have moved off k_i long before epoch i+d, and a delayed or failed refresh delays disclosure instead of leaving a disclosed key installed. At the end of the chain k_{L-1} follows the same rules: it is disclosed from the start of epoch L-1+d, once every tagger has removed it at Expiry. The pure-Go tagger reads CurrentKey for every packet and holds no key.
Disclosure therefore lags the start of epoch i+d by up to one heartbeat interval, or longer while a refresh fails. A verifier waits for the key rather than treating a missing one as a failure.
Attribution ¶
Attribution reports whether packets tagged now can be attributed: not in epoch 0 or from Expiry, not while a holder's latest refresh failed, and not once an installed key has held disclosure back for longer than one epoch. The executor sends it in its capability report.
Index ¶
- Constants
- func ChainSeed(seed []byte, generation int64) ([]byte, error)
- func ComputeTag(ak, input []byte) (uint16, error)
- func DefaultDisclosureDelay(epochLength time.Duration) int64
- func DeriveAK(k []byte, measurementID []byte) ([]byte, error)
- func DeriveFromDisclosed(disclosedKey []byte, disclosedEpoch, targetEpoch int64) ([]byte, error)
- func HashInput(packet []byte) ([]byte, error)
- func PacketTag(ak, packet []byte) (uint16, error)
- func SipHash24(key, data []byte) uint64
- func VerifyChain(anchor, key []byte, t int64) bool
- func VerifyTag(chainKey []byte, epoch int64, measurementID, packet []byte, tag uint16) (bool, error)
- type Attribution
- type Config
- type InstalledKeyHolder
- type KeySchedule
- func (ks *KeySchedule) Anchor() []byte
- func (ks *KeySchedule) Attribution(now time.Time) Attribution
- func (ks *KeySchedule) ChainLength() int64
- func (ks *KeySchedule) ComputeTagForPacket(t time.Time, measurementID, packet []byte) (uint16, error)
- func (ks *KeySchedule) Config() Config
- func (ks *KeySchedule) CurrentKey(t time.Time) []byte
- func (ks *KeySchedule) DisclosedKey(t time.Time) (index int64, key []byte, ok bool)
- func (ks *KeySchedule) DisclosureDelay() int64
- func (ks *KeySchedule) EpochOf(t time.Time) int64
- func (ks *KeySchedule) Exhausted(t time.Time) bool
- func (ks *KeySchedule) Expiry() time.Time
- func (ks *KeySchedule) FinalDisclosure() time.Time
- func (ks *KeySchedule) KeyAtEpoch(epoch int64) ([]byte, error)
- func (ks *KeySchedule) MaxDisclosureHold() time.Duration
- func (ks *KeySchedule) RegisterInstalled(h InstalledKeyHolder)
- func (ks *KeySchedule) UnregisterInstalled(h InstalledKeyHolder)
- type RefreshReporter
- type UnsupportedError
Constants ¶
const ( // UnattributableEpochZero: k_0 is public, so nothing sent in epoch 0, or // before Epoch, is tagged with a secret key. UnattributableEpochZero = "epoch_zero" // UnattributableChainExhausted: from Expiry no key signs. UnattributableChainExhausted = "chain_exhausted" // UnattributableRefreshFailing: a kernel tagger's latest key refresh // failed, so its slot is empty or may still hold a previous epoch's key. UnattributableRefreshFailing = "refresh_failing" // UnattributableDisclosureHeld: an installed key has held disclosure back // for longer than MaxDisclosureHold, so the keys of new tags stay withheld. UnattributableDisclosureHeld = "disclosure_held" )
Reasons why packets tagged now cannot be attributed. They are the fixed vocabulary of the executor capability report.
const ( UnsupportedIPv6 = tagspec.UnsupportedIPv6 UnsupportedNotIPv4 = tagspec.UnsupportedNotIPv4 UnsupportedTooShort = tagspec.UnsupportedTooShort UnsupportedMalformed = tagspec.UnsupportedMalformed UnsupportedFragment = tagspec.UnsupportedFragment )
Reasons why a packet has no v1 tag. The tagger leaves such a packet unchanged, and a verifier reports it unsupported rather than unmatched.
const DefaultChainHorizon = 7 * 24 * time.Hour
DefaultChainHorizon is the uptime a default-sized chain covers. The default ChainLength is DefaultChainHorizon/EpochLength, so a longer epoch gives a shorter chain rather than a shorter usable lifetime.
const DefaultDisclosureWindow = 15 * time.Minute
DefaultDisclosureWindow is the wall-clock time a default disclosure delay covers: d defaults to the smallest number of epochs, and at least MinDisclosureDelay, whose length reaches it. Fifteen minutes is in the range TRACER uses (10 to 30 minutes), far beyond any verifier tolerance or disciplined clock skew, and still short enough that a result's tags become verifiable soon after the run. At the default epoch length of 10 seconds it is d = 90.
const DefaultEpochLength = 10 * time.Second
DefaultEpochLength is the epoch length I of a schedule that names none.
const MaxTagInput = tagspec.MaxInput
MaxTagInput is the most packet bytes the tag authenticates.
const MinDisclosureDelay = tagspec.MinDisclosureDelay
MinDisclosureDelay is the shortest disclosure delay d, in epochs, a schedule accepts. A verifier tries a packet's epoch t and t-1; with d = 1 the key of t-1 is already public during epoch t (see Disclosure).
const TagSpec = tagspec.ID
TagSpec identifies the packet-tag algorithm this build implements, defined in docs/tag-spec.md. Taggers and verifiers of one fleet use one version; results record it so evidence names the algorithm its tags follow.
Variables ¶
This section is empty.
Functions ¶
func ChainSeed ¶
ChainSeed derives the tail k_L of one chain from a configured seed:
k_L = HKDF-SHA256(secret=seed, info="debuglet tesla chain <generation>", length=32)
Each generation of the same seed yields a different chain, so a restart with an unchanged seed does not reuse keys an earlier chain disclosed.
func ComputeTag ¶
ComputeTag is the 16-bit tag of an already canonical input (tagspec.ComputeTag).
func DefaultDisclosureDelay ¶ added in v0.3.0
DefaultDisclosureDelay returns the disclosure delay, in epochs, of a schedule with the given epoch length that names none.
func DeriveAK ¶
DeriveAK computes the per-measurement authentication key:
ak = HKDF-SHA256(secret=k, info=measurementID, length=32)
measurementID is the ASCII of the run's canonical UUID (tagspec.DeriveAK).
func DeriveFromDisclosed ¶
DeriveFromDisclosed reconstructs the key at targetEpoch given a disclosed key at disclosedEpoch. Because the chain runs backward (k_i = H(k_{i+1})), a verifier can only derive keys at epochs ≤ disclosedEpoch by hashing the disclosed key forward (disclosedEpoch → targetEpoch, t ≤ disclosedEpoch):
k_t = H^(disclosedEpoch - t)(k_disclosedEpoch)
To reconstruct a later (newer) key you would need an even newer disclosed key, since the chain cannot be inverted.
func HashInput ¶ added in v0.3.0
HashInput returns the canonical tag input of an IPv4 packet (tagspec.HashInput).
func PacketTag ¶ added in v0.3.0
PacketTag is the v1 tag of an IPv4 packet under ak (tagspec.PacketTag).
func VerifyChain ¶
VerifyChain checks that H^t(k_t) == k_0 (the public anchor). A verifier calls this after reconstructing k_t to confirm its authenticity.
func VerifyTag ¶
func VerifyTag(chainKey []byte, epoch int64, measurementID, packet []byte, tag uint16) (bool, error)
VerifyTag checks whether tag is the v1 tag of an IPv4 packet at a given epoch, given the chain key of that epoch and the measurement ID. Choosing the candidate epochs is the caller's (docs/tag-spec.md). A packet v1 does not cover fails with an *UnsupportedError rather than a mismatch.
Types ¶
type Attribution ¶ added in v0.3.0
type Attribution struct {
Epoch int64
// Reason is empty when attribution is available, otherwise one of the
// Unattributable constants; the first that applies in their order wins.
Reason string
// InstalledEpoch is the oldest epoch a registered holder may still sign
// with; it is meaningful only when Installed.
InstalledEpoch int64
Installed bool
// LastInstall is the oldest last successful install among the holders
// that report one, and zero when none does.
LastInstall time.Time
// RefreshErr is the latest error of a failing holder, nil when none fails.
RefreshErr error
// HeldSince is when the installed key started holding disclosure back, the
// end of InstalledEpoch; zero when disclosure is not held.
HeldSince time.Time
}
Attribution is whether packets tagged at one instant can be attributed once their key is disclosed, with the kernel refresh state that decides it.
type Config ¶
type Config struct {
// Seed is the secret tail k_L of the hash chain. If nil, a random
// 32-byte seed is generated on the first call to NewKeySchedule.
// The seed is NEVER disclosed; it is only used internally to derive
// keys by hashing backwards toward k_0.
Seed []byte
// ChainLength L is the total number of epochs supported by this
// schedule. The keys k_0 … k_L are generated; k_0 is the public
// anchor and k_L is derived from the seed.
//
// If zero, it is derived from EpochLength so that the chain covers
// DefaultChainHorizon of uptime. Sizing this from a wall-clock horizon
// matters: k_L is never disclosed, so the last signing epoch is L-1 and
// from the start of epoch L (Expiry) the schedule has no signing key and
// nothing is tagged.
ChainLength int64
// EpochLength is the interval duration I of one epoch. Defaults to
// DefaultEpochLength.
EpochLength time.Duration
// DisclosureDelay d is the number of epochs after which a key is
// disclosed: k_i is disclosed once epoch i+d has started. Zero derives
// DefaultDisclosureDelay(EpochLength); otherwise it must be at least
// MinDisclosureDelay.
DisclosureDelay int64
// Epoch is the reference wall-clock time that anchors epoch 0.
// Defaults to the time NewKeySchedule is called.
Epoch time.Time
}
Config carries the tuneable parameters of the TESLA key schedule.
type InstalledKeyHolder ¶ added in v0.3.0
InstalledKeyHolder is a signing path that keeps a chain key outside the schedule, such as a kernel map slot. InstalledEpoch reports the epoch whose key the path may still sign with, and false once it holds no key.
type KeySchedule ¶
type KeySchedule struct {
// contains filtered or unexported fields
}
KeySchedule is a thread-safe TESLA hash-chain key schedule.
Keys are indexed by epoch number t where t ∈ [0, L]:
epoch t covers the time interval [Epoch + t*I, Epoch + (t+1)*I).
The chain direction is backward: k_0 is the public anchor and k_L is the private seed tail. Key k_t is used during epoch t and disclosed after the disclosure delay d has elapsed (i.e., once epoch t+d has started).
k_0 is public from setup, so it never signs: epoch 0, and any instant before Epoch, has no usable signing key. The first usable key is k_1 at Epoch+I and the last is k_{L-1}; from Expiry, the start of epoch L, no key signs.
The set of registered InstalledKeyHolders is the one mutable part; every other field is fixed at construction.
func NewKeySchedule ¶
func NewKeySchedule(cfg Config) (*KeySchedule, error)
NewKeySchedule creates a KeySchedule from cfg.
The chain direction is backward (k_i = H(k_{i+1})). The private seed k_L is stored internally and the public anchor k_0 = H^L(seed) is computed once.
If cfg.Seed is empty a cryptographically random 32-byte seed is generated. A seed that is not exactly 32 bytes long is folded through SHA-256 so that k_L is always one key wide. If cfg.EpochLength is zero it defaults to DefaultEpochLength. If cfg.DisclosureDelay is zero it defaults to DefaultDisclosureDelay; a delay below MinDisclosureDelay is refused. If cfg.ChainLength is zero it is derived from EpochLength (see DefaultChainHorizon).
func (*KeySchedule) Anchor ¶
func (ks *KeySchedule) Anchor() []byte
Anchor returns k_0, the public anchor that should be published at setup. Verifiers use it to check consistency: H^t(k_t) == k_0.
func (*KeySchedule) Attribution ¶ added in v0.3.0
func (ks *KeySchedule) Attribution(now time.Time) Attribution
Attribution reports the state at now. Without a registered holder only the epoch decides it, which is also the pure-Go tagger's case.
func (*KeySchedule) ChainLength ¶
func (ks *KeySchedule) ChainLength() int64
ChainLength returns L, the highest epoch this schedule can serve.
func (*KeySchedule) ComputeTagForPacket ¶
func (ks *KeySchedule) ComputeTagForPacket(t time.Time, measurementID, packet []byte) (uint16, error)
ComputeTagForPacket derives ak from the chain key at time t and returns the v1 tag of packet. It fails while no chain key is usable and with an *UnsupportedError for a packet v1 does not tag.
func (*KeySchedule) Config ¶
func (ks *KeySchedule) Config() Config
Config returns a copy of the schedule's configuration.
func (*KeySchedule) CurrentKey ¶
func (ks *KeySchedule) CurrentKey(t time.Time) []byte
CurrentKey returns the chain key k_t for the epoch that contains time t, or nil while no key is usable: epochOf maps epoch 0 and any instant before Epoch to 0, whose key is the public anchor (see KeySchedule), and every instant from the start of epoch L to L, whose key k_L is never disclosed. Every signing path reads the key here, so this is the one place the rule is decided.
func (*KeySchedule) DisclosedKey ¶
DisclosedKey returns the epoch index and key that should be disclosed at time t. The key for epoch τ is disclosed once the disclosure delay of d epochs has elapsed after τ: at the start of epoch τ+d, so at time t the disclosed epoch is epoch(t)−d.
Before epoch d has started (no key is disclosable yet), ok is false. The disclosed key stops at k_{L-1}, the last signing key, once epoch L−1+d has started, even though the chain was exhausted at epoch L; k_L is never disclosed.
A registered holder that may still sign with k_e caps the result at e-1, so a key is never disclosed while an installed copy of it can tag packets.
func (*KeySchedule) DisclosureDelay ¶ added in v0.3.0
func (ks *KeySchedule) DisclosureDelay() int64
DisclosureDelay returns d, the number of epochs after which a key is disclosed.
func (*KeySchedule) EpochOf ¶ added in v0.3.0
func (ks *KeySchedule) EpochOf(t time.Time) int64
EpochOf returns the epoch that contains t: 0 before Epoch, and at most L.
func (*KeySchedule) Exhausted ¶
func (ks *KeySchedule) Exhausted(t time.Time) bool
Exhausted reports whether time t falls at or past the end of the chain, the start of epoch L. k_L is never disclosed, so an exhausted schedule has no signing key and CurrentKey returns nil from then on.
func (*KeySchedule) Expiry ¶
func (ks *KeySchedule) Expiry() time.Time
Expiry returns the wall-clock time at which the chain runs out.
func (*KeySchedule) FinalDisclosure ¶ added in v0.3.0
func (ks *KeySchedule) FinalDisclosure() time.Time
FinalDisclosure returns when the last signing key k_{L-1} becomes disclosable: the start of epoch L-1+d, d-1 epochs after Expiry. Keys live only in this schedule, so a restart before then starts a new chain and the keys of the old chain's last undisclosed epochs are never published; the packets they tagged cannot be verified.
func (*KeySchedule) KeyAtEpoch ¶
func (ks *KeySchedule) KeyAtEpoch(epoch int64) ([]byte, error)
KeyAtEpoch returns the chain key for the given epoch index.
func (*KeySchedule) MaxDisclosureHold ¶ added in v0.3.0
func (ks *KeySchedule) MaxDisclosureHold() time.Duration
MaxDisclosureHold bounds how long an installed key may hold disclosure back before attribution is reported unavailable. One epoch covers the boundary refresh and its first retry at EpochLength/2; the hold at every boundary until the refresh lands is ordinary and stays well inside it.
func (*KeySchedule) RegisterInstalled ¶ added in v0.3.0
func (ks *KeySchedule) RegisterInstalled(h InstalledKeyHolder)
RegisterInstalled adds h to the holders that cap DisclosedKey. A holder registers before it installs its first key.
func (*KeySchedule) UnregisterInstalled ¶ added in v0.3.0
func (ks *KeySchedule) UnregisterInstalled(h InstalledKeyHolder)
UnregisterInstalled removes h once it can no longer sign with any key.
type RefreshReporter ¶ added in v0.3.0
RefreshReporter is an InstalledKeyHolder that also reports its refresh: the time of its last successful key install, zero before one, and the error of its latest attempt, nil after a success.
type UnsupportedError ¶ added in v0.3.0
type UnsupportedError = tagspec.UnsupportedError
UnsupportedError is returned for a packet the specification assigns no tag.
Source Files