~ehmry/nim_sphincs

ref: adb3c7562b087a342e562bbb0d4347c63101b4f9 nim_sphincs/src/sphincs/private/sphincsinstantiate.nim -rw-r--r-- 13.0 KiB
adb3c756Emery Hemingway Give credit for SHA3 library 3 years ago
                                                                                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
#
# WOTS + One-Time Signatures
#

proc chain(input: Nbytes, i, s: int; pk: PK; adrs: Address): Nbytes =
  ## Compute an iteration of F on a n-byte input using
  ## a WOTS+ hash address and a public seed.
  var adrs = adrs
  assert((i+s) <= (w-1))
  result = input
  for j in i..<min(i+s, w):
    adrs.setHashAddress(j)
    result = F(pk, adrs, result)

proc wots_SKgen(sk: SK; adrs: Address): Nbytes =
  var adrs = adrs
  adrs.setHashAddress(0)
  PRF(sk, adrs)

proc wots_PKgen(sk: Sk; pk: PK; adrs: Address): array[wotsLen, Nbytes] =
  ## Generate a WOTS+ public key.
  var adrs = adrs
  for i in 0..<wotsLen:
    adrs.setChainAddress(i)
    let sk = wots_SKgen(sk, adrs)
    result[i] = chain(sk, 0, w - 1, pk, adrs)

proc wots_checksum(lengths: openArray[int]): array[wotsLen2, int] =
  var csum = 0

  for i in 0..<wotsLen1:
    csum = csum + w - 1 - lengths[i]
    # compute checksum

  csum = csum shl (8 - ((wotsLen2 * lg(w) ) mod 8))
    # convert csum to base w

  const len2Bytes = (int)ceil( float( wotsLen2 * lg(w) ) / 8)
  var b: array[len2Bytes, byte]
  csum.toByte(b)
  base_w(result, b, w)

proc wots_sign(M: Nbytes; sk: SK; pk: PK; adrs: Address): array[wotsLen, Nbytes] =
  ## Generate a WOTS+ signature on message M.
  var
    adrs = adrs
    lengths: array[wotsLen1, int]
  base_w(lengths, M, w)
    # convert message to base w

  for i in 0..<wotsLen1:
    adrs.setChainAddress(i)
    let prf = PRF(sk, adrs)
    result[i] = chain(prf, 0, lengths[i], pk, adrs)

  let csum = lengths.wots_checksum
  for i in wotsLen1..<wotsLen:
    adrs.setChainAddress(i)
    let prf = PRF(sk, adrs)
    result[i] = chain(prf, 0, csum[i-wotsLen1], pk, adrs)

proc wots_pkFromSig(sig: array[wotsLen,Nbytes]; M: Nbytes; pk: PK; adrs: var Address): array[wotsLen, Nbytes] =
  ## Compute a WOTS+ public key from a message and its signature.
  var lengths: array[wotsLen1, int]
  base_w(lengths, M, w)
    # convert message to base w

  for i in 0..<wotsLen1:
    adrs.setChainAddress(i)
    result[i] = chain(sig[i], lengths[i], w - 1 - lengths[i], pk, adrs)

  let csum = lengths.wots_checksum
  for i in wotsLen1..<wotsLen:
    adrs.setChainAddress(i)
    result[i] = chain(sig[i], csum[i-wotsLen1], w - 1 - csum[i-wotsLen1], pk, adrs)

#
# The SPHINCS + Hypertree
#

type GenLeafProc = proc(sk: SK; pk: PK; idx: int; adrs: Address): Nbytes

proc isOdd(x: int): bool {.inline.} = bool(x and 1)

type
  TreeNode = tuple[node: Nbytes; height: int]

proc treeHash(root: var Nbytes; authPath: var openArray[Nbytes];
              stack: var openArray[TreeNode];
              sk: SK; pk: PK, leafIdx, idxOffset: int;
              genLeaf: GenLeafProc; adrs: Address) =
  ## For a given leaf index, computes the authentication path and
  ## the resulting root node using Merkle's TreeHash algorithm.
  var
    treeAdrs = adrs
    offset, idx, treeIdx: int

  for idx in 0..<(1 shl (stack.len-1)):
    stack[offset].node = genLeaf(sk, pk, idx+idxOffset, treeAdrs)
      # Add the next leaf node to the stack
    stack[offset].height = 0
    inc offset
    if (leafIdx xor 0x1) == idx:
      # if this is a node we need it for the auth path
      authPath[0] = stack[offset-1].node
    while (1 < offset) and (stack[offset-1].height == stack[offset-2].height):
      # while the top-most nodes are of equal height...
      treeIdx = idx shr (stack[offset-1].height+1)
        # compute index of the new node, in the new layer

      treeAdrs.setTreeHeight(stack[offset-1].height + 1)
      treeAdrs.setTreeIndex(treeIdx + (idxOffset shr (stack[offset-1].height + 1)))
        # set the address of the node we're creating
      stack[offset-2].node = H(pk, treeAdrs, stack[offset-2].node, stack[offset-1].node)
        # hash the top-most nodes from the stack together
      dec offset
      inc stack[offset-1].height
        # note that the top-most node is now one layer higher
      if ((leafIdx shr stack[offset-1].height) xor 0x1) == treeIdx:
        # if this is a node we need for the auth path...
        authPath[stack[offset - 1].height] = stack[offset-1].node
  root = stack[0].node

proc wotsGenLeaf(sk: SK; pk: PK; adrsIdx: int; treeAdrs: Address): Nbytes =
  ## Computes the leaf at a given address. First generates the WOTS
  ## key pair, then computes leaf by hashing horizontally.
  var
    wotsAdrs = initAdrs(WOTS_HASH)
    wotsPkAdrs = initAdrs(WOTS_PK)
  wotsAdrs.copySubTree(treeAdrs)
  wotsAdrs.setKeyPairAddress(adrsIdx)
  wotsPkAdrs.copyKeyPair(wotsAdrs)
  let wotsPk = wots_PKgen(sk, pk, wotsAdrs)
  T_len(pk, wotsPkAdrs, wotsPk)

proc xmss_PKgen(sk: SK; pk: PK; adrs: Address): Nbytes =
  ## Generate an XMSS public key.
  # 4.1.4. XMSS Public Key Generation
  const height = h div d
  var auth: array[height, Nbytes]
    # not used, but `treeHash` computes both a root and authPath
  var treeStack: array[height+1, TreeNode]
  treeHash(result, auth, treeStack, sk, pk, 0, 0, wotsGenLeaf, adrs)

type XmssSignature = object {.packed.}
  # 4.1.5. XMSS Signature
  sig: array[wotsLen, Nbytes]
  auth: array[h div d, Nbytes]

# HT: The Hypertee (sic)

proc ht_PKgen(sk: SK; pk: PK): Nbytes =
  ## Generate an HT public key.
  var adrs = initAdrs(TREE)
  adrs.setLayerAddress(d-1)
  xmss_PKgen(sk, pk, adrs)

type HtSignature = array[d, XmssSignature]

#
# FORS: Forest Of Random Subsets
#

proc computeRoot(leaf: Nbytes; leafIdx, idxOffset: int;
                 authPath: openArray[Nbytes],
                 height: int;
                 pk: PK; adrs: Address): Nbytes =
  var
    nodes: (Nbytes, Nbytes)
    adrs = adrs
    leafIdx = leafIdx
    idxOffset = idxOffset

  if leafIdx.isOdd:
    # If leafIdx is odd, current path element is a right child
    # and authPath has to go left. 
    nodes[1] = leaf
    nodes[0] = authPath[0]
  else:
    # Otherwise it is the other way around.
    nodes[0] = leaf
    nodes[1] = authPath[0]

  for i in 0..(height-2):
    leafIdx = leafIdx shr 1
    idxOffset = idxOffset shr 1
    adrs.setTreeHeight(i+1)
    adrs.setTreeIndex(leafIdx+idxOffset)
    if leafIdx.isOdd:
      nodes[1] = H(pk, adrs, nodes[0], nodes[1])
      nodes[0] = authPath[i+1]
    else:
      nodes[0] = H(pk, adrs, nodes[0], nodes[1])
      nodes[1] = authPath[i+1]
  leafIdx = leafIdx shr 1
  idxOffset = idxOffset shr 1
  adrs.setTreeHeight(height)
  adrs.setTreeIndex(leafIdx+idxOffset)
  H(pk, adrs, nodes[0], nodes[1])
    # the last iteration is exceptional; we do not copy an authPath node

const
  forsHeight = a
  forsTrees = k
  forsMsgBytes = (forsHeight*forsTrees+7) div 8

proc fors_SKgen(sk: SK; adrs: Address): Nbytes =
  ## Compute a FORS private key value
  # 5.2. FORS Private Key
  PRF(sk, adrs)

proc messageIndices(msg: openArray[byte]): array[forsTrees, int] =
  #assert(msg.len > forsHeight*forsTrees div 8)
  var offset: int
  for i in 0..<forsTrees:
    for _ in 1..forsHeight:
      result[i] =  (result[i] shl 1) xor ((msg[offset shr 3].int shr (offset and 0x7)) and 0x1)
      inc offset

type ForsSignature = array[k, tuple[
  key: Nbytes,
  auth: array[a, Nbytes]]]

proc fors_SKtoLeaf(pk: PK, adrs: var Address; sk: Nbytes): Nbytes =
  F(pk, adrs, sk)

proc forsGenLeaf(sk: SK; pk: PK; addrIdx: int; adrs: Address): Nbytes =
  ## Procedure for generating leaves of FORS tree.
  var forsLeafAdrs = adrs
  forsLeafAdrs.setType(FORS_TREE)
  forsLeafAdrs.setTreeIndex(addrIdx)
  forsLeafAdrs.setKeyPairAddress(adrs.getKeyPairAddress)
  result = fors_SKtoLeaf(pk, forsLeafAdrs, fors_SKgen(sk, forsLeafAdrs))

proc forsSign(sig: var ForsSignature; public: var Nbytes; msg: openArray[byte]; sk: SK; pk: PK; adrs: Address) =
  ## Generate a FORS signature and public key on n-byte string M.
  let indices = messageIndices msg
  var
    roots: array[forsTrees, Nbytes]
    forsTreeAdrs = adrs
    forsPkAdrs = adrs
  forsTreeAdrs.setType(FORS_TREE)
  forsTreeAdrs.setKeyPairAddress(adrs.getKeyPairAddress)
  forsPkAdrs.setType(FORS_ROOTS)
  forsPkAdrs.setKeyPairAddress(adrs.getKeyPairAddress)

  for i in 0..<k:
    let idxOff = i * (1 shl forsHeight)
    forsTreeAdrs.setTreeHeight(0)
    forsTreeAdrs.setTreeIndex(indices[i] + idxOff)
    sig[i].key = fors_SKgen(sk, forsTreeAdrs)
    var treeStack: array[forsHeight+1, TreeNode]
    treeHash(roots[i], sig[i].auth, treeStack, sk, pk, indices[i], idxOff, forsGenLeaf, forsTreeAdrs)

  public = T_k(pk, forsPkAdrs, roots)
    # Hash horizontally across all tree roots to derive the public key.

proc fors_pkFromSig(sig: ForsSignature; msg: openArray[byte]; pk: PK; adrs: var Address): Nbytes =
  ## Compute a FORS public key from a FORS signature
  let indices = messageIndices msg
  var
    roots: array[forsTrees, Nbytes]
    forsTreeAdrs = adrs
    forsPkAdrs = adrs

  forsTreeAdrs.setType(FORS_TREE)
  forsTreeAdrs.setKeyPairAddress(adrs.getKeyPairAddress)

  forsPkAdrs.setType(FORS_ROOTS)
  forsPkAdrs.setKeyPairAddress(adrs.getKeyPairAddress)

  for i in 0..<forsTrees:
    let idxOff = i * (1 shl forsHeight)
    forsTreeAdrs.setTreeHeight(0)
    forsTreeAdrs.setTreeIndex(indices[i] + idxOff)

    let leaf = fors_SKtoLeaf(pk, forsTreeAdrs, sig[i].key)
      # derive the leaf from the included secret key part

    roots[i] = computeRoot(leaf, indices[i], idxOff, sig[i].auth, a, pk, forsTreeAdrs)
      # derive the corresponding root node of this tree

  T_k(pk, forsPkAdrs, roots)
    # Hash horizontally across all tree roots to derive the public key.

const
  spxTreeHeight = h div d
  signatureSize* = n + k*(n+a*n) + d*(wotsLen*n+(h div d)*n)
    ## Size of SPHINCS⁺ signture minus the message. The message
    ## is appended during signing so it should be no longer than a
    ## hash digest.

type
  SpxSignature = object {.packed.}
    R: Nbytes
    FORS: ForsSignature
    HT: HtSignature

  RandomBytes* = proc(buf: pointer; size: int)
    ## Procedure type for collecting entropy during
    ## key generation and signing. Please supply
    ## a procedure that writes `size` random bytes to `buf`.

{.pop.} # allow runtime checks

proc sign*(pair: KeyPair; M: string|openArray[byte]; optRand: Nbytes): string {.noSideEffect.} =
  ## Generate a SPHINCS⁺ signature.
  ## The signature will be deterministic unless `optRand` is randomized.
  let msgOff = sizeof(SpxSignature)
  result = newString(msgOff+M.len)

  let sig = cast[ptr SpxSignature](result[0].addr)
  sig.R = PRFmsg(pair.sk, optRand, M)
    # generate randomizer

  let (md, mTree, mLeaf) = Hmsg(sig.R, pair.pk, M)
  var
    root: Nbytes
    treeAdrs = initAdrs(TREE)
    wotsAdrs = initAdrs(WOTS_HASH)

  wotsAdrs.setTreeAddress(mTree)
  wotsAdrs.setKeyPairAddress(mLeaf)
  forsSign(sig.FORS, root, md, pair.sk, pair.pk, wotsAdrs)
    # FORS sign
  block:
    var
      idxTree = mTree
      idxLeaf = mLeaf
    for i in 0..<d:
      treeAdrs.setLayerAddress(i)
      treeAdrs.setTreeAddress(idxTree)
      wotsAdrs.copySubtree(treeAdrs)
      wotsAdrs.setKeypairAddress(idxLeaf)

      sig.HT[i].sig = wots_sign(root, pair.sk, pair.pk, wotsAdrs)
      var treeStack: array[spxTreeHeight+1, TreeNode]
      treeHash(root, sig.HT[i].auth, treeStack, pair.sk, pair.pk,
        idxLeaf, 0, wotsGenLeaf, treeAdrs)

      idxLeaf = (int32)idxTree and ((1 shl spxTreeHeight) - 1)
      idxTree = idxTree shr spxTreeHeight
        # update the indices for the next layer
  for i in 0..M.len:
    result[msgOff+i] = (char)M[i]
    # append signature with message

proc sign*(pair: KeyPair; M: string|openArray[byte]; rand: RandomBytes): string {.noSideEffect.} =
  ## Generate a SPHINCS⁺ signature. The passed `rand` procedure is used to
  ## create non-deterministic signatures which are generally recommended.
  var optRand: Nbytes
  rand(optRand.addr, n)
  pair.sign(M, optRand)

proc verify(pk: PK; sigStr: var string): (bool, string) {.noSideEffect.} =
  assert(sigStr.len > sizeof(SpxSignature))
  let
    sig = cast[ptr SpxSignature](sigStr[0].addr)
    M = sigStr[sizeof(SpxSignature)..sigStr.high]
  var
    root, leaf: Nbytes
    wotsAdrs = initAdrs(WOTS_HASH)
    treeAdrs = initAdrs(TREE)
    wotsPkAdrs = initAdrs(WOTS_PK)
    (md, idxTree, idxLeaf) = Hmsg(sig.R, pk, M)

  wotsAdrs.setTreeAddress(idxTree)
  wotsAdrs.setKeyPairAddress(idxLeaf)

  root = fors_pkFromSig(sig.FORS, md, pk, wotsAdrs)

  for i in 0..<d:
    # for each subtree
    treeAdrs.setLayerAddress(i)
    treeAdrs.setTreeAddress(idxTree)

    wotsAdrs.copySubtree(treeAdrs)
    wotsAdrs.setKeypairAddress(idxLeaf)
    wotsPkAdrs.copyKeyPair(wotsAdrs)

    let wotsPk = wots_pkFromSig(sig.HT[i].sig, root, pk, wotsAdrs)
    leaf = T_len(pk, wotsPkAdrs, wotsPk)
    root = computeRoot(leaf, idxLeaf, 0, sig.HT[i].auth, h div d, pk, treeAdrs)

    idxLeaf = (int32)idxTree and ((1 shl spxTreeHeight) - 1)
    idxTree = idxTree shr spxTreeHeight
      # update the indices for the next layer

  if root == pk.root:
    (true, M)
  else:
    (false, "")

proc verify*(pk: PK; sig: string): (bool, string) {.noSideEffect.} =
  ## Verify a SPHINCS⁺ signature.
  ## The signed message is assumed to be stored at the
  ## end of the signature string.
  var sig = sig
  pk.verify sig

proc generateKeypair*(seedProc: RandomBytes): KeyPair {.noSideEffect.} =
  ## Generate a SPHINCS⁺ key pair.
  seedProc(result.addr, n*3)
    # Randomize the seeds and PRF
  result.pk.root = ht_PKgen(result.sk, result.pk)
    # Compute root node of top-most subtree