sfinx

sphincs+ inspired signing utility
git clone git://git.finwo.net/app/sfinx
Log | Files | Refs | README | LICENSE

idea.md (8228B)


      1 # sfinx, the idea
      2 
      3 `sfinx` is a stateless, SPHINCS+-inspired hash-based signature. Think of it as a
      4 tree you never build. The public key is a hash, and below it sit subtrees whose
      5 leaves are one-time signature keys. Nothing is stored: every key is derived from
      6 the seed plus the path that reaches it, so the whole keyspace is a function
      7 rather than a pile of bytes on disk.
      8 
      9 This document is the intuition and the vocabulary. The precise formulas are in
     10 `scheme.md`.
     11 
     12 ## Glossary
     13 
     14 - `L`: hash output size in bytes, one of `28`, `32`, `48`, `64` (SHA3-224, SHA3-256, SHA3-384, SHA3-512). Every example uses `32`.
     15 - `H`: the hash function, `SHA3-8*L`.
     16 - `seed`: the secret, any byte string up to 64 MiB. Random bytes are recommended, a passphrase is allowed.
     17 - `w`: Winternitz chain length (256, so one chain digit is one byte).
     18 - `len1`: message chains (`= L`).
     19 - `len2`: checksum chains (`= 2`).
     20 - `c`: chains per WOTS (`= len1 + len2 = L + 2`).
     21 - `b`: bits per subtree (8, one path byte, so 256 leaves).
     22 - `N`: path length in bytes, E4M4-representable. `N` subtrees and `N` WOTS keys for `N >= 1`.
     23 - `bitlen`, `mask`: the sub-byte part of a node's position. `bitlen` is the bit count (0..8), `mask` one byte holding those bits in its top `bitlen` positions with the low `8 - bitlen` bits zeroed.
     24 - `layer`: which WOTS key in the stack, `1..N`. A layer-`k` key is named by `E4M4(N)` and the first `k` path bytes.
     25 - `org`: what the bottom WOTS signs, `= H(path | message)`, so the same message on a different path signs a different value. With no path, `org = H(message)`.
     26 - `E4M4`: the log-ish length byte, 4-bit exponent then 4-bit mantissa. Exponent `0` is the mantissa (0..15); for exponent `E >= 1` the value is `(16 + mantissa) << (E-1)`, so `0x10` is 16, `0x20` is 32, `0x30` is 64, and each exponent step doubles.
     27 
     28 ## The shape
     29 
     30 The tree is binary, stacked as `N` subtrees of height `b = 8`.
     31 
     32 - Each subtree has 256 leaves, and each leaf is a WOTS public key.
     33 - Each subtree root is only a hash of its children.
     34 - The WOTS at layer `k` signs the root of the subtree below it.
     35 - The bottom WOTS has no subtree below it, so it signs `org = H(path | message)`.
     36 - The public key is the top subtree root, with nothing above it.
     37 - The path length is part of every key derivation, so each depth has its own public key.
     38 
     39 `N = 0` collapses the whole thing: no subtrees, no path, and the public key is a
     40 single WOTS key over `org = H(message)`.
     41 
     42 ## The path
     43 
     44 The signer picks a random path of `N` bytes. It is the randomizer, so it never
     45 derives from the message, and signing the same message twice lands on different
     46 keys.
     47 
     48 - `path[0]` is the most significant byte (near the root), `path[N-1]` the least significant (near the message).
     49 - One path byte selects a leaf in one subtree, most significant bit first.
     50 - A one-time key is named `E4M4(N) | path[0..k-1]` for a layer-`k` key. No mask, because the path is already split into bytes and SHA3 resists length extension.
     51 - `N` must be E4M4-representable, because the signature carries it as an E4M4 byte.
     52 
     53 ## WOTS
     54 
     55 Each key is a Winternitz one-time signature over an `L`-byte value.
     56 
     57 - Pre-image: `SHAKE256(seed | E4M4(N) | path[0..k-1])` for a layer-`k` key, `c * L` bytes, split into `c = L + 2` chains of `L` bytes.
     58 - A step is `H(x | kid | i | j)`, where `kid = H(E4M4(N) | path[0..k-1])` truncated, `i` is the chain and `j` the position.
     59 - Chain `i` signs digit `i` by stepping its pre-image `digit[i]` times.
     60 - The first `L` digits are the signed value. The last `len2 = 2` digits are the checksum `C = sum(255 - digit[i])`.
     61 - The pubkey is `H(chain_end[0] | ... | chain_end[c-1])`, where a chain end is the pre-image stepped `w = 256` times.
     62 
     63 Binding the key, chain and position into every step keeps published chain
     64 values apart. A plain `H(x)` chain puts every value from every key in one pool,
     65 where a single precomputation targets all of them at once. The `kid` is public,
     66 so a verifier recomputes it; it is truncated to keep a step inside one Keccak
     67 block, which at SHA3-512 leaves only 5 bytes.
     68 
     69 The checksum is what stops a chain from being reversed. Increasing any digit
     70 decreases `C`, and an attacker can only hash forward, so a checksum chain would
     71 have to run backward, which needs a preimage. `len2 = 2` because `L * 255` fits
     72 in two base-256 bytes for every supported `L` (7,140 at `L = 28`, 16,320 at
     73 `L = 64`).
     74 
     75 ## The Merkle tree
     76 
     77 Each subtree is a plain binary hash tree, but the hash is keyed by position:
     78 
     79 ```
     80 H(bitlen | mask | prefix | left | right)
     81 ```
     82 
     83 `prefix` is `E4M4(N)` plus the byte-aligned path prefix above the node. `bitlen`
     84 (0..8) and `mask` carry the sub-byte remainder, so a node at depth `8k + d` is
     85 named by `k` path bytes plus `d` bits. `mask` keeps the top `bitlen` bits and
     86 zeroes the rest, so `0xff` and `0xfc` are the same prefix at `bitlen = 4`. The
     87 prefix itself is never padded. No node hash can be replayed at another depth or
     88 in another subtree, so the tree rests on second-preimage resistance instead of
     89 collision resistance. An `L`-byte hash is not silently cut in half.
     90 
     91 ## Signing
     92 
     93 - Output `E4M4(N)`, the random path, then `E4M4(L)`, then the proof data.
     94 - `N = 0`: no path, just the single WOTS proof for `org = H(message)`.
     95 - `N >= 1`: walk bottom up. At each subtree, output the WOTS proof for the path key, then the `b = 8` Merkle neighbours in verification order: LSB (deepest) first, up to MSB (subtree root) last.
     96 
     97 ## Verifying
     98 
     99 Verification walks from the bottom up.
    100 
    101 - Read `N`, then the path, then `L`, and check `L` against the public key length.
    102 - Recompute `org = H(path | message)`.
    103 - Advance each of the `c` proof values to `w = 256`, hash the chain ends into the WOTS pubkey, and check the checksum digits.
    104 - Hash up the `b = 8` Merkle neighbours to this subtree root, one level at a time, LSB first.
    105 - Repeat with the next WOTS up, each one signing the subtree root below it.
    106 - The last subtree root is the public key.
    107 
    108 When `N = 0` there is nothing to climb, so the WOTS pubkey over `org = H(message)`
    109 is compared to the public key directly.
    110 
    111 ## Wire order
    112 
    113 - Numbers are MSB first, matching human notation: `E4M4(N)`, `E4M4(L)`, the path bytes (most significant, near the root, first), the `bitlen` and `mask` bytes, and the checksum (high byte first).
    114 - The Merkle neighbour list is a sequence, not a number, so it follows the verification algorithm: LSB (deepest) first, MSB (top) last.
    115 
    116 ## How many times can a seed sign?
    117 
    118 A key is named `E4M4(N) | path[0..k-1]`, which fixes what it signs: the subtree
    119 root beneath it when `k < N`, `org` when `k = N`. Two signatures share a key
    120 only at the same `N` and the same prefix.
    121 
    122 The limit is therefore a path collision: same `N`, same path, different message.
    123 The bottom key is named by the full path, so at the default `N = 32` the
    124 collision space is 256 bits.
    125 
    126 - Random path, what the library does: the birthday bound gives a 50 percent chance of one collision at about `2^128` signatures.
    127 - Tracked paths, where the caller never repeats one: the limit is the path space, `2^256`. The library tracks nothing, so the caller builds this.
    128 - Single-key mode (`N = 0`): one key signs `H(message)` every time, so two messages break it.
    129 
    130 ## No state
    131 
    132 A signature is a proof that you can produce the path to a given root, not a
    133 record that you did.
    134 
    135 ## Cost and parallelism
    136 
    137 - `size(0) = 2 + c * L`, `size(N) = 2 + N + N*(c*L) + N*(b*L) = 2 + N + N*(L + 10)*L` for `N >= 1`.
    138 - `keygen(N)`: `c * w` hashes for `N = 0`, `2^b * c * w` hashes for `N >= 1`.
    139 - `sign(N)`: `c * w` hashes for `N = 0`, `N * 2^b * c * w` hashes for `N >= 1`.
    140 
    141 | N  | WOTS | subtrees | size     | keygen | sign hashes |
    142 |---:|-----:|---------:|---------:|-------:|------------:|
    143 |  0 |    1 |        0 |  1,090 B |   8.7k |        8.7k |
    144 |  1 |    1 |        1 |  1,347 B |   2.2M |        2.2M |
    145 | 16 |   16 |       16 | 21,522 B |   2.2M |       35.7M |
    146 | 32 |   32 |       32 | 43,042 B |   2.2M |       71.3M |
    147 
    148 Hash chains are independent, so the library runs the 256-leaf subtree build on
    149 a worker pool when compiled with pthread support, and sequentially when it is
    150 not. The switch is compile-time only, and the output is identical either way, so
    151 it is invisible in the signature.