sfinx

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

scheme.md (12599B)


      1 # sfinx scheme spec
      2 
      3 This is the implementable specification. A compatible signer and verifier can be
      4 written from this document alone. For the intuition, read `idea.md`; for the
      5 command line and file formats, read `cli.md`.
      6 
      7 `sfinx` is a stateless, SPHINCS+-inspired hash-based signature. The tree is
      8 binary, stacked as `N` subtrees of height `b = 8`, with a Winternitz one-time
      9 key (WOTS) at each subtree leaf. Every key is derived from the seed and the path
     10 that reaches it, so the tree is never built or stored.
     11 
     12 ## Constants
     13 
     14 | name    |       value | meaning                                                                            |
     15 | :------ | ----------: | :--------------------------------------------------------------------------------- |
     16 | `L`     | 28/32/48/64 | hash output size in bytes, from `sfinx_hash` (SHA3-224/256/384/512). Default `32`. |
     17 | `len1`  |         `L` | message chains, one per byte of the signed value                                   |
     18 | `len2`  |           2 | checksum chains                                                                    |
     19 | `c`     |     `L + 2` | chains per WOTS key (`= len1 + len2`)                                              |
     20 | `w`     |         256 | chain length, `1 << 8`, so one digit is one byte                                   |
     21 | `b`     |           8 | subtree height in bits, so `1 << b = 256` leaves per subtree                       |
     22 | `N`     |          32 | path length in bytes, E4M4-representable. Default `32`.                            |
     23 | `layer` |      `1..N` | which WOTS key in the stack; layer-`k` is named by `E4M4(N)` and `k` path bytes    |
     24 
     25 - `H` is `SHA3-8*L`, so SHA3-224/256/384/512, and returns `L` bytes.
     26 - `SHAKE256(x)` is the XOF; the WOTS pre-image asks for `c * L = (L + 2) * L` bytes.
     27 - The seed is any byte string up to `SFINX_SEED_LEN_MAX` (64 MiB), not a fixed length.
     28 - `N` is bounded only by E4M4: any representable value up to `SFINX_PATH_LEN_MAX` (507904) is accepted.
     29 
     30 ## E4M4 length byte
     31 
     32 `N` and `L` each travel as one byte called E4M4: high nibble is the exponent
     33 `E`, low nibble is the mantissa `M`.
     34 
     35 - `E == 0`: value = `M`, so `0x00..0x0F` = 0..15.
     36 - `E >= 1`: value = `(16 + M) << (E - 1)`.
     37 - Rows: `0x00..0x0F` = 0..15, `0x10..0x1F` = 16..31, `0x20..0x2F` = 32..62, `0x30..0x3F` = 64..124, doubling each exponent step.
     38 - `N = 0` encodes as `0x00`, `N = 32` as `0x20`. `L` encodes as `0x1C` (28), `0x20` (32), `0x28` (48), `0x30` (64).
     39 
     40 ## Node position
     41 
     42 A node is named by a path prefix, not a mask. WOTS keys sit at byte-aligned
     43 depths, so their prefix is `E4M4(N)` plus a whole number of path bytes. Merkle
     44 internals can sit at any depth, so their position is `prefix` bytes plus a
     45 sub-byte remainder carried as `bitlen` (0..8) and `mask` (the partial byte, top
     46 `bitlen` bits kept and the rest zeroed). Nothing else is zero-padded, because
     47 SHA3 has no length extension, so `seed | prefix` cannot be confused with another
     48 prefix.
     49 
     50 ## Path
     51 
     52 - The signer draws `N` bytes from a CSPRNG. This is the randomizer and it is carried in the signature.
     53 - `path[0]` is the most significant byte (near the root), `path[N-1]` the least significant (near the message).
     54 - Each path byte navigates one subtree of height `b = 8`, most significant bit first: bit 7 is the decision nearest the subtree root, bit 0 the decision at the leaf.
     55 - A WOTS key is named by `E4M4(N)` and the truncated path that reaches it: a layer-`k` key uses `E4M4(N) | path[0..k-1]`.
     56 - `N` must be E4M4-representable, because `E4M4(N)` leads the signature.
     57 - The library never draws the path. `sfinx_tree_sign` takes `path` as an argument, and `sfinx_random_bytes` is a helper the caller uses.
     58 
     59 ## WOTS
     60 
     61 One WOTS key signs one `L`-byte value, derived from the seed, the path length
     62 and the truncated path that reaches it.
     63 
     64 Pre-image, `c * L = (L + 2) * L` bytes:
     65 
     66 ```
     67 stream = SHAKE256(seed | E4M4(N) | path[0..k-1])    for a layer-k key
     68 pre[i] = stream[i*L .. i*L + L-1]      for i in 0..c-1
     69 ```
     70 
     71 - `E4M4(N)` is at a fixed offset and the prefix length gives `k`, so the key is a bottom key iff `k = N` and interior otherwise.
     72 - `N = 0` is single mode: empty prefix, `stream = SHAKE256(seed)`.
     73 
     74 Digits, from the `L`-byte `value`:
     75 
     76 ```
     77 d[i]   = value[i]                      for i in 0..L-1
     78 d[L]   = (C >> 8) & 0xff               where C = sum(255 - value[i])
     79 d[L+1] = C & 0xff
     80 ```
     81 
     82 `C` max is `L * 255`, which fits in two bytes for every supported `L` (7,140 at
     83 `L = 28`, 16,320 at `L = 64`), so `len2 = 2`.
     84 
     85 Key id, once per WOTS key, over public data only so the verifier can recompute
     86 it:
     87 
     88 ```
     89 kid = H(E4M4(N) | path[0..k-1])[0 .. K-1]
     90 K   = min(L, rate - 1 - L - 2)           rate = 200 - 2L
     91 ```
     92 
     93 | hash     | rate | L  | K  | block |
     94 | -------- | ---- | -- | -- | ----- |
     95 | SHA3-224 |  144 | 28 | 28 |    58 |
     96 | SHA3-256 |  136 | 32 | 32 |    66 |
     97 | SHA3-384 |  104 | 48 | 48 |    98 |
     98 | SHA3-512 |   72 | 64 |  5 |    71 |
     99 
    100 `K` is cut so a chain step stays one permutation. SHA3-512 is the tight case:
    101 rate 72 leaves 5 bytes, so its key ids separate only 40 bits, and two keys
    102 colliding there share a chain pool again. Single mode has an empty suffix, so
    103 `kid = H("")`.
    104 
    105 Chain and keys:
    106 
    107 ```
    108 chain_i(x, j, 0) = x
    109 chain_i(x, j, n) = chain_i(H(x | kid | i | j), j+1, n-1)
    110 
    111 proof[i] = chain_i(pre[i], 0, d[i])              sign
    112 end[i]   = chain_i(pre[i], 0, w)                 pubkey build
    113 pubkey   = H(end[0] | end[1] | ... | end[c-1])
    114 ```
    115 
    116 Every step is bound to its key, its chain and its position: `i` is `0..c-1` and
    117 `j` is `0..w-1`, both one byte. Without that binding every published chain
    118 value across every key sits in one pool, and one precomputation targets all of
    119 them at once.
    120 
    121 Verify a proof against a value: recompute the digits from the value, then
    122 `end[i] = chain_i(proof[i], d[i], w - d[i])`, then the pubkey hash. An attacker
    123 can only hash forward, so raising any `d[i]` lowers `C`, which forces a
    124 checksum chain backward, which needs a preimage.
    125 
    126 ## Merkle subtree
    127 
    128 Each subtree is binary with height `b = 8`, so 256 leaves, each leaf a WOTS
    129 public key. The parent hash is keyed by the parent's position:
    130 
    131 ```
    132 parent = H(bitlen (1) | mask (1) | prefix (p) | left (L) | right (L))
    133 ```
    134 
    135 - For a node at depth `8k + d`, `prefix` is `E4M4(N) | path[0..k-1]`, so `p = k + 1`, and `bitlen` is `d`.
    136 - `bitlen` is 0..8, the number of sub-byte bits in the position. `mask` holds those bits in its top `bitlen` positions with the low `8 - bitlen` bits zeroed, so a prefix has one encoding.
    137 - `left` is the child reached by a 0 bit, `right` the child reached by a 1 bit.
    138 - Keying by position is what moves the tree from collision resistance to second-preimage resistance.
    139 - A leaf input is `c * L` bytes and a parent input `2 + p + 2L`, so the two coincide at `L*L + 2L` bytes, where `p = L*L - 2`. The verifier's walk is fixed by `N` and the subtree height, so a leaf is never read as a parent.
    140 
    141 ## Tree structure
    142 
    143 - `N` subtrees, `0` top to `N-1` bottom, and `N` WOTS keys at layers `1..N`.
    144 - `R_k` is the root of subtree `k`. `R_0` is the public key. `R_N := org`.
    145 - WOTS at layer `k` signs `R_k`, so `k = N` signs `org` and `1 <= k <= N-1` signs `R_k`.
    146 - `R_{k-1}` is the WOTS pubkey at layer `k` hashed up subtree `k-1` with its `b` neighbours. At `k = 1` that is the public key.
    147 - `N >= 1`: the public key is `R_0`, the top subtree root, with no WOTS above it, matching SPHINCS+. `R_0` depends on the seed, `L` and `N`: one public key per length.
    148 - `N = 0`: no subtrees and no path. The public key is the layer-0 WOTS pubkey over `SHAKE256(seed)`, and that key signs `org = H(message)`.
    149 
    150 ## org
    151 
    152 - `N >= 1`: `org = H(path | message)`, so the same message on a different path signs a different value.
    153 - `N = 0`: `org = H(message)`.
    154 
    155 ## Signature layout
    156 
    157 ```
    158 offset       field       size
    159 0            N           1 (E4M4)
    160 1            PATH        N
    161 1 + N        L           1 (E4M4)
    162 2 + N        DATA        see below
    163 ```
    164 
    165 - `N` is the path length, E4M4-encoded.
    166 - `PATH` is `N` bytes, `path[0]` first.
    167 - `L` is the hash size in bytes, E4M4-encoded, and must match the public key length.
    168 - `N = 0`: `DATA` is one WOTS proof, `c * L` bytes.
    169 - `N >= 1`: `DATA` is `N` rounds. Round `k` counts `N` down to `1` and holds the WOTS proof for layer `k` (`c * L` bytes), then the `b` neighbours of subtree `k-1` (`b * L` bytes), LSB (deepest) first.
    170 
    171 Sizes:
    172 
    173 - `size(0) = 2 + c * L = 2 + (L + 2) * L`
    174 - `size(N) = 2 + N + N * (c + b) * L = 2 + N + N * (L + 10) * L`
    175 - At `L = 32`: `size(0) = 1,090` and `size(N) = 2 + 1345 * N`.
    176 
    177 ## Signing
    178 
    179 1. Draw `path`, `N` random bytes.
    180 2. `org = H(path | message)` for `N >= 1`, else `H(message)`.
    181 3. Emit `E4M4(N)`, then `path`, then `E4M4(L)`.
    182 4. `N = 0`: emit the WOTS proof for layer 0 over `org`. Done.
    183 5. `N >= 1`: for `k = N` down to `1`: emit the WOTS proof for layer `k` over `R_k` (`R_N = org`), then the `b` neighbours of subtree `k-1` along the path, LSB first.
    184 
    185 ## Verifying
    186 
    187 1. Read `E4M4(N)` and decode `N`.
    188 2. Read the `N`-byte `path`, then read `E4M4(L)` and check it against the public key length.
    189 3. `N = 0`: read one WOTS proof, rebuild its pubkey over `H(message)`, compare to the public key.
    190 4. `N >= 1`: compute `org = H(path | message)`.
    191 5. Set `value = org`. For `k = N` down to `1`:
    192    - read a WOTS proof and rebuild its pubkey over `value`;
    193    - read `b` neighbours and hash the pubkey up subtree `k-1` to its root, LSB first;
    194    - if `k == 1`, that root is the public key, so compare and finish;
    195    - else set `value` to that root.
    196 
    197 ## Sizes and hash counts
    198 
    199 With `c = L + 2`, at the default `L = 32` (`c = 34`):
    200 
    201 - keygen `N = 0`: `c * w = 8,704` hashes.
    202 - keygen `N >= 1`: `(1 << b) * c * w = 2,228,224` hashes, because the top subtree needs its 256 WOTS pubkeys.
    203 - sign `N = 0`: `c * w = 8,704` hashes.
    204 - sign `N >= 1`: `N * (1 << b) * c * w`, which is `71,303,168` at `N = 32`.
    205 - verify `N >= 1`: about `N * c * w` chain hashes plus `N * b` parent hashes.
    206 
    207 ## Number formats
    208 
    209 - All multi-byte integers are MSB first (big-endian).
    210 - `E4M4(N)`, `E4M4(L)`, and the checksum are MSB first.
    211 - The Merkle neighbour list is a sequence, not a number, so it follows verification order: LSB (deepest) first, MSB (subtree root) last.
    212 - Path bytes run most significant (near the root, `path[0]`) to least significant (near the message, `path[N-1]`). Within a byte, the most significant bit is nearest the subtree root and the least significant bit is at the leaf.
    213 
    214 ## Pseudocode
    215 
    216 A sketch, not reference code.
    217 
    218 ```c
    219 // A key is named E4M4(N) | path[0..k-1] for a layer-k key.
    220 pre_image(seed, prefix) = SHAKE256(seed | prefix, c * L)   // c = L + 2
    221 
    222 // L message digits, then the 2 checksum digits.
    223 digits(value) = value[0..L-1] ++ be16(sum(255 - value[i]))
    224 
    225 // Keyed subtree parent: byte prefix plus the sub-byte remainder.
    226 // mask keeps the top bitlen bits of the byte, low bits zeroed.
    227 parent(bitlen, mask, prefix, left, right) =
    228     H(bitlen | mask | prefix | left | right)
    229 
    230 // WOTS
    231 chain(x, kid, i, from, steps):
    232     for j = from to from + steps - 1:
    233         x = H(x | kid | i | j)
    234     return x
    235 
    236 single_sign(seed, prefix, value):
    237     pre = pre_image(seed, prefix)
    238     kid = H(prefix)[0..K-1]
    239     d   = digits(value)
    240     return [ chain(pre[i], kid, i, 0, d[i]), for i in 0..c-1 ]
    241 
    242 single_pubkey(proof, kid, value):
    243     d    = digits(value)
    244     ends = [ chain(proof[i], kid, i, d[i], w - d[i]), for i in 0..c-1 ]
    245     return H(ends[0] | ... | ends[c-1])
    246 ```
    247 
    248 Signing, with `value` starting at `org` and climbing one subtree per round:
    249 
    250 ```c
    251 tree_sign(seed, message, N):
    252     path  = random(N bytes)
    253     value = (N == 0) ? H(message) : H(path | message)
    254 
    255     out = E4M4(N) | path | E4M4(L)
    256 
    257     if N == 0:
    258         out += single_sign(seed, "", value)
    259         return out
    260 
    261     for k = N down to 1:
    262         out   += single_sign(seed, E4M4(N) | path[0..k-1], value)
    263         out   += auth(subtree = k-1, path)               // 8 neighbours, LSB first
    264         value  = root(subtree = k-1, path)               // what the next round signs
    265 
    266     return out
    267 ```
    268 
    269 Verifying:
    270 
    271 ```c
    272 verify(pubkey, message, sig):
    273     N    = E4M4_decode(sig)
    274     path = read_path(N)
    275     L    = E4M4_decode(sig)
    276 
    277     if N == 0:
    278         return single_pubkey(read_proof(), H(""), H(message)) == pubkey
    279 
    280     value = H(path | message)
    281 
    282     for k = N down to 1:
    283         kid = H(E4M4(N) | path[0..k-1])[0..K-1]
    284         pub = single_pubkey(read_proof(), kid, value)  // proof for layer k
    285         if k == 1:
    286             return hash_up(pub, read_auth()) == pubkey   // root of subtree 0
    287         value = hash_up(pub, read_auth())            // root of subtree k-1
    288 
    289     return false
    290 ```