seed derivation math

gistfile1.txt

Given the series of (i(n),f(n)), where subsequent checks happen whether a
predicate with chance f(n) is true after i(n) iterations. A seed that
satisfies f(n), but not any f(k) with k<n is said to be of strength n. We
want the following two properties:
* (a) constructing a seed of a given strength n takes on average A*B^n
      iterations.
* (b) assuming an attacker has an oracle that tells all valid seeds of a
      given (known) strength n, it takes as many iterations to construct
      all derived keys as there are elements in the seedspace.

N(n) = A*B^n
P(n) = mult(1-f(k), k=0..n-1)
C(n) = P(n)*f(n)
H(n) = sum(i(k)*C(k), k=0..n-1) 
I(n) = H(n) + i(n)*P(n)

iterations for a valid strength-n (given the seed): i(n)-1
fraction of seedspace that produces strength-n seeds: C(n)
-> equation for (b): (i(n)-1)*C(n) = 1

iterations per strength-n attempt: I(n)
iterations for finding a strength-n seed: I(n)/C(n)
-> equation for (a): I(n)/C(n) = N(n)

(i(n)-1)*C(n) = 1
I(n)/C(n) = N(n)
->
(i(n)-1)*I(n) = N(n)
(i(n)-1)*(H(n) + i(n)*P(n)) = N(n)
->
i(n) = sqrt(((P(n) - H(n))*i(n) + H(n) + N(n))/P(n))
f(n) = (H(n) + i(n)*P(n)) / (N(n)*P(n))

Solution for A=65536, B=2:
 n |  i(n) | 2^32*f(n) | I(n)/C(n) (~ N(n) = 65536*2^n)
---+-------+-----------+-----------
 0 |   257 | 0x1010000 |      65536
 1 |   363 |  0xB60183 |     131072
 2 |   513 |  0x80C1A2 |     262144
 3 |   726 |  0x5B2143 |     524288
 4 |  1028 |  0x4080DF |    1048576
 5 |  1454 |  0x2D9892 |    2097152
 6 |  2058 |  0x204059 |    4194305
 7 |  2911 |  0x16CC35 |    8388608
 8 |  4118 |  0x101E1E |   16777223
 9 |  5826 |   0xB6591 |   33554438
10 |  8241 |   0x80ECA |   67108804
11 | 11656 |   0x5B265 |  134217811
12 | 16487 |   0x40733 |  268435297
13 | 23319 |   0x2D922 |  536869575
14 | 32980 |   0x20389 | 1073740391
15 | 46644 |   0x16C86 | 2147493766
16 | 65968 |   0x101C0 | 4294982504