← Back to branch summary

~ubuntu-branches/ubuntu/precise/krb5/precise-updates

« back to all changes in this revision

Viewing changes to src/lib/crypto/krb/prng/yarrow/ASSUMPTIONS

  • Committer: Package Import Robot
  • Author(s): Sam Hartman
  • Date: 2011-12-01 19:34:41 UTC
  • mfrom: (28.1.14 sid)
  • Revision ID: package-import@ubuntu.com-20111201193441-9tipg3aru1jsidyv
Tags: 1.10+dfsg~alpha1-6
http://bugs.debian.org/650671
http://bugs.debian.org/650603
http://bugs.debian.org/650611
* Fix segfault with unknown hostnames in krb5_sname_to_principal,
  Closes: #650671
* Indicate that this library breaks libsmbclient versions that depend on
  krb5_locate_kdc, Closes: #650603, #650611

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/lib/crypto/krb/prng/yarrow/ASSUMPTIONS
1
 
Assumptions
2
 
===========
3
 
 
4
 
The Yarrow design, described in "Yarrow-160: Notes on the Design and
5
 
Analysis of the Yarrow Cryptographic Pseudonumber Generator" by John
6
 
Kelsey, Bruce Schneier and Niels Ferguson of Counterpane Systems
7
 
(available from http://www.counterpane.com/yarrow.html), left out some
8
 
implementation details and has some ambiguities in the protocol.  ZKS
9
 
has to made some assumptions and taken some decisions in its
10
 
implementation of Yarrow. In the text, `we' represents ZKS.
11
 
 
12
 
Here is the list of those assumptions: 
13
 
 
14
 
1) To simplify the code and speed up running time, we limit the number
15
 
of different sources to 20. This should be enough for most
16
 
applications. This can be changed by redefining YARROW_MAX_SOURCE in
17
 
yarrow.h.
18
 
 
19
 
2) The Yarrow paper (in section 5.3) state that Pt is either
20
 
implementation dependent or dynamically adjusted. We chose to fix the
21
 
slow pool's Pt to 100 and the fast pool's Pt to 10. This can be
22
 
changed by redefining YARROW_FAST_PT and YARROW_SLOW_PT in yarrow.c.
23
 
 
24
 
3) Initialization when there is no saved state is not discussed in the
25
 
Yarrow paper.  We have defined that CPRNG is becomes seeded after a
26
 
slow reseed.  During initialization, a slow reseed is triggered by
27
 
YARROW_K_OF_N_INIT_THRESH sources reaching the slow threshold
28
 
YARROW_SLOW_INIT_THRESH.  During initialization, fast reseeds are
29
 
triggered when a source reaches the fast threshold
30
 
YARROW_FAST_INIT_THRESH.  After reseed the behavior of the pools is
31
 
controlled by YARROW_K_OF_N_THRESH, YARROW_SLOW_THRESH and
32
 
YARROW_FAST_THRESH.  
33
 
 
34
 
Our default values for YARROW_K_OF_N_INIT_THRESH,
35
 
YARROW_SLOW_INIT_THRESH and YARROW_FAST_INIT_THRESH are the same as
36
 
YARROW_K_OF_N_THRESH, YARROW_SLOW_THRESH and YARROW_FAST_THRESH
37
 
respectively.  Note this means that a Yarrow_Poll call by itself can
38
 
never put us in an initialized state, as it only works on one pool,
39
 
and the default YARROW_K_OF_N_INIT_THRESH value is 2.
40
 
 
41
 
4) We define a function Yarrow_Poll which can gather entropy.  The
42
 
user must allocate a source_id, and call Yarrow_Poll manually.
43
 
Yarrow_Poll just adds samples from the machines state to the source
44
 
given as an argument.
45
 
 
46
 
5) Prior to initialization, Yarrow_Output will fail.
47
 
 
48
 
6) The actions to take on state load are not described in the yarrow
49
 
paper, all it says is that 2k bytes should be written (and by
50
 
implication read back in somehow).  We read in the 2k bytes, hash
51
 
them into the fast pool, and then do a forced fast reseed, and an
52
 
immediate state save.
53
 
 
54
 
7) In step 2 of the reseed process, we must hash the value i. The
55
 
representation of this integer will affect the hash value. In our
56
 
code, i is a 64-bit unsigned value. We update the hash context using
57
 
the 64 bit big endian representation of i.
58
 
 
59
 
8) Yarrow outputs random bits in blocks. If the calling function
60
 
requests less bits than available, then the unused bits are kept
61
 
in memory until the next call. In case of a reseed, we chose to 
62
 
discard those leftover bits.
63
 
 
64
 
9) The samples from one source must alternate between the two pools.
65
 
As a default, we initialize the first pool to send the sample too to
66
 
be the fast pool. This initialization is done only when a source is
67
 
added, not when we reseed from one.
68
 
 
69
 
10) The Yarrow paper states that the maximum number of outputs between
70
 
reseeding is limited to min(2^n,2^(k/3)*Pg), but does not explain
71
 
what is to happen when this limit is reached. It could be the case
72
 
that we reach the limit but there is not enough entropy in the pools 
73
 
to reseed. In our code, the Yarrow_Output_Block will do a forced
74
 
fast reseed. 
75
 
 
76
 
11) In the Yarrow paper, the limit on the number of outputs between
77
 
reseeding is expressed in number of outputs:
78
 
 
79
 
#oututs <= min(2^n, 2^(k/3).Pg)
80
 
 
81
 
but we redefine it in terms of gates by dividing the numbers by Pg,
82
 
the number of outputs per gate, and counting the number of gates
83
 
instead.  This makes an overflow a little less likely.
84
 
 
85
 
We don't use a bignum library, so in event of overflow, the limit in
86
 
number of gates before reseed (y->gates_limit) is reduced down to
87
 
2^64-1 (or 2^32-1 if 64 bit ints aren't available on the platform).
88
 
 
89
 
12) The Yarrow paper describes that the cipher block C should be 
90
 
incremented as part of the output function.  We treat the bytes
91
 
of C as a big endian number to do the increment.
92
 
 
93
 
13) Triple-DES key size.  The yarrow paper uses the letter k to
94
 
represent the keysize in bits.  Due to the parity bits, the size of k
95
 
is 192 bits.  However the effective key size is actually 168 bits, as
96
 
the value of k is used in security limits, k must be 168 bits.  The
97
 
paper uses k (eg set K to the next k output bits), so we have to do
98
 
the parity padding function, to copy bits 0-6 to 0-7, 7-13 to 8-15
99
 
etc.  The macro DES_Init performs the function of doing a DES key
100
 
schedule from a packed key (no parity bits), internally doing the
101
 
parity padding.  Other ciphers are simpler as there is no parity.