- cypherpunks-legacy - lists.cpunks.org

Toward Axiomatic Fenced DES (long!)
by ritter＠indial1.io.com 17 Dec '03

17 Dec '03

Ritter Software Engineering 2609 Choctaw Trail Austin, Texas 78745 (512) 892-0494, ritter(a)io.com Toward Axiomatic Fenced DES Terry Ritter May 26, 1994 Introduction This article continues the development of a block cipher which I have been calling "Fenced DES." This unique construct uses the U.S. Data Encryption Standard (DES) as a component in a strength- enhanced cipher. Even though DES is slow and is now becoming vulnerable to advancing attack technology, DES is also well-known and trusted, and industry would be grateful to continue to use it if only it were stronger. The time has come to replace ordinary DES. One alternative is the complete certification of a totally new cipher at tremendous cost in both treasure and time. Another alternative is "triple- DES," at three times the computation of ordinary DES. But if a strength-enhancing construction can be found which is sufficiently clear and elegant, we may hope for a "derivative certification," based only assumptions about the strength of DES itself. In this article I start the process of proving some things about the Fenced DES cipher. In particular, I prove that the resulting cipher is invertible and has the avalanche property, two admittedly modest characteristics, but ones we do associate with a good block cipher. I claim that the construct is certainly guaranteed to be no weaker than DES. I also argue--with some theoretical support-- that the construct should be expected to be much stronger, at least 120 bits. In other words, it should be "strong enough" for the next couple of decades. The system of definitions, proofs and arguments which takes up the major part of this article is by no means finished, and is known to be casual and inconsistent in places. (Some of these problems could be fixed by expanding the mathematical base, which I avoid for now.) In spite of this, I believe it to be an interesting approach, even if it is an approach to which others are probably far better suited than myself. Therefore, let us just agree to accept it for what it is, and see how close it gets to what we need. The definitions apply to this particular construction. Those generally familiar with combinatorics might start with section 7, "Block Mixing Transforms." Fenced DES Here is the current 4x Fenced DES construct: S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S ------------------------------mix------------------------------ --------------mix-------------- --------------mix-------------- ------DES------ ------DES------ ------DES------ ------DES------ --------------mix-------------- --------------mix-------------- ------------------------------mix------------------------------ S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S Each "S" represents a separately-shuffled and independent 8-bit substitution table (which also implies the presence of a keyed cryptographic RNG to shuffle the tables). We have 32 input substitutions and 32 output substitutions, for an overall block size of 256 bits. This is only 32 bytes, which should be much smaller than the typical message. Trailing 2x and 1x blocks would reduce data expansion to only that needed by DES itself. Each "---DES---" represents an ordinary 64-bit-block DES operation. Each "---mix---" represents the mixing of the covered data blocks using "block mixing transform" technology. There are two levels of mixing on each side of the DES operations: The innermost levels each have two mixings which combine two 64-bit blocks; the outermost levels each have just a single mixing which combines two 128-bit blocks, a substantial mixing operation. This entire construct requires about 4.8 times the computation to cipher 4 times the data. In contrast, triple-DES would of course need 12 times the computation to cipher 4 times the data. The Proofs 1. SETS ======= 1.1 DEFINITION: A SET is a collection of objects in which any object either is or is not a part of the set. A set S can be described by a list of the elements in the set, viz. S = { a1, a2, ..., an }. 1.2 DEFINITION: The SIZE OF SET S is the number of elements in S, and is denoted |S|. 2. CODES ======== 2.1 DEFINITION: A CODE is a string of symbols in which the symbol in each position is taken from some common set S. When S consists of numeric values, a code can be seen as a polynomial with coefficients in S. 2.2 DEFINITION: An N-POSITION code is a code which has n positions for symbols, and can be denoted by S**n. 2.3 DEFINITION: A BINARY code is a code in which the common set is the set {0,1}. 2.4 DEFINITION: An N-BIT binary code is a binary code with n positions and can be denoted by {0,1}**n or by S**n with S = {0,1}. 2.5 THEOREM: (Size of code.) There are |S|**n distinct code values in an n-position code. (Proof: Each position in a code string can be any possible symbol, there are |S| possible symbols and n positions in each code string, so there are |S|**n possible code values of length n.) 2.6 THEOREM: (No special positions.) Taken over all possible code values, each string position has exactly the same number of occurrences of each symbol. (Proof: Each position in a code string can be any possible symbol. For any particular combination of symbols in other positions, in the selected position each possible symbol occurs once. So for every possible combination of symbols in other positions, in the selected position each possible symbol occurs the same number of times.) 2.7 THEOREM: (Position difference counts.) The number of n-position code values which differ in exactly m positions is (n) m (m) * (|S|-1) . (n) (Proof: There are (m) combinations of m positions out of n possible positions, and in any particular combination of m positions each position can take on |S|-1 other symbols producing (|S|-1)**m other code values for each combination.) 2.8 EXAMPLE: The number of 8-bit binary codes which differ in m bits is: distance count 0 1 1 8 2 28 3 56 4 70 5 56 6 28 7 8 8 1 --- 256 = 2**8 (Comment: There are 256 8-bit binary code values, and 255 values which differ in at least one position from any particular code value.) 2.9 THEOREM: (Average distance and distribution.) The expected number of elements which differ between two n-position code values is n * (1 - 1/|S|), and the distribution is binomial. (Proof: Assume the number of code differences is the binomial (n) m n-m probability of a difference B(m;n,p) = (m) p q , where where p = 1 - 1/|S| and q = 1-p, times the total number of n code values (1/q) : (n) m (n) m n-m -n (m) * (|S|-1) = (m) p q q (n) m = (m) (p / (1-p)) which is correct, so the expected number of different elements is the binomial expectation np.) 2.10 EXAMPLE: The expected number of elements which differ between two 8-bit binary code values is: 8 * (1 - 0.5) = 4. 2.11 EXAMPLE: The probability of having two 8-bit binary code values which differ in exactly two elements is: (8) 2 6 (2) (0.5) (0.5) = 0.109 = 28 / 256. 2.12 EXAMPLE: The expected number of elements which differ between two 64-bit binary code values is: 64 * (1 - 0.5) = 32. 2.13 EXAMPLE: The probability of getting a 64-bit binary code value which differs in exactly m bits from some other value is: difference probability 16 0.000026 28 0.061 29 0.075 30 0.088 31 0.096 32 0.099 (Comment: The 9 difference values 28..36 account for about 74 percent of all possible difference counts, even though they are only about 14 percent of all 65 possibilities.) 3. DISCRETE FUNCTIONS ===================== 3.1 DEFINITION: A DISCRETE FUNCTION takes an input code value to an output code value for a finite number of input code values. 3.2 DEFINITION: A RANDOM discrete function allows each output code value to be selected independently for each possible input condition. 3.3 THEOREM: (Number of random functions.) There are 2**2n possible random functions with an n-bit binary input code and an n-bit binary output code. (Proof: An n-bit binary code can make 2**n possible selections, each of which can be 2**n possible values, and (2**n)*(2**n) = 2**2n.) 4. SUBSTITUTION =============== 4.1 DEFINITION: A SUBSTITUTION is a mapping from input values or positions to output values. (Comment: A SUBSTITUTION can be seen as an indexable vector of substitute values. A SUBSTITUTION can also be seen as a "codebook" with an entry for every possible input code, and storage for each corresponding output code. A SUBSTITUTION can also be seen as an "arbitrary" discrete function, since any possible discrete function can be described by using a separate output code for each possible input condition. A SUBSTITUTION can also be seen as the relation joining substitute values with the position of each value.) 4.2 DEFINITION: SIMPLE substitution is the operation of using a substitution table or codebook to "encode" a string of input values by replacing each value in the string with its associated substitute value. (Comment: If the substitution is invertible, we can use an inverse substitution to "decode" the resulting encoded values and recover the original values.) 4.3 THEOREM: (Unique substitute values.) An invertible substitution can contain any particular output code at most once. (Proof: Suppose not: Then two different values into a substitution will produce the same output value. But that output value can inverse-substitute to only one inverse value, making the other input value unreachable, which contradicts invertibility, so this is false.) 4.4 THEOREM: (Number of invertible substitutions.) There are (2**n)! possible invertible substitutions for an n-bit binary input code. (Proof: The first substitution element can be any one of 2**n elements, the second element can be any except the first element, or (2**n)-1 elements, the third can be any except the first and second, for (2**n)-2 elements, and so on.) 4.5 THEOREM: (Guaranteed change propagation.) A change of even one input bit to an invertible substitution is guaranteed to produce a change in at least one output bit from the substitution. (Proof: Each input bit can select between two different input code values, which will select two different output code values, since an invertible substitution contains no duplicate values. Since any two different codes must be different in at least one bit, any input bit-change will produce at least one output bit-change.) 4.6 DEFINITION: A COMPLETE substitution contains every value of an n-position code, for some n. 4.7 THEOREM: (Probable change propagation.) Any change whatsoever to the input value to a complete invertible substitution is likely to change about half the bits in the output value. (Proof: Changing the input value selects among all remaining output code values. If the output is considered to be binary bits, we expect about half those bits to change (2.9).) 4.8 DEFINITION: AVALANCHE is a statistical property of a discrete function in which any change whatsoever on the input is expected to produce a change in about half the bits in the output value. 4.9 THEOREM: (Avalanche is automatic.) Avalanche is an inherent property of complete invertible substitution. (Proof: See 4.5, 4.7, and 2.9.) 4.10 THEOREM: (No special input bits.) Each input bit to an invertible substitution has exactly the same power to produce the same expected change in output bits. (Proof: Consider any possible change to any possible input value: from all possible input values any particular bit-change will produce all possible input values. Thus, any possible bit-change must produce the same overall expectation.) 4.11 THEOREM: (No special output bits.) Each output bit from a complete invertible substitution has exactly the same change expectation as any other output bit. (Proof: See 2.6.) 4.12 THEOREM: (Not a random function.) An invertible substitution cannot be a random function. (Proof: Suppose a value is selected for placement somewhere in a substitution. Since an invertible substitution cannot allow another occurrence of that same value, other values cannot be selected independently.) 4.13 DEFINITION: In a KEYED substitution the substitute element values have been permuted or re-arranged as a function of some key value or function. 4.14 THEOREM: (Reconstruction requires information linking output values to input values.) An unknown invertible substitution cannot be resolved without simultaneous information about both the input value or position and the output value. (Proof: To the extent that a particular substitution can be said to have an identity, that identity is the relation between substitute values and their position. This relation is both necessary and sufficient to define the substitution.) 5. BIT MIXERS ============= 5.1 DEFINITION: A BIT-MIXER combines multiple input bits such that each output value is defined by each and every input bit. 5.2 THEOREM: An invertible substitution is a bit-mixer. (Proof: Each and every input bit can select between two different input code values. Any input value change into an invertible substitution must necessarily select a different output value. Thus, the output value, and every bit in the output value, inherently depends upon each and every bit of the input value.) 6. BLOCK CIPHERS ================ 6.1 DEFINITION: A CIPHER is a keyed invertible translation from a plaintext element to a ciphertext element. 6.2 THEOREM: A CIPHER is a keyed invertible substitution. (Proof: For "translation" read "substitution.") 6.3 DEFINITION: A BLOCK cipher is a cipher in which the size of the code element is prohibitively large to be exhaustively explored. 6.4 THEOREM: (Not a random function.) No static block cipher can be a random function. (Proof: A cipher must be an invertible function, and no invertible function can have elements which are independent.) 6.5 ASSERTION: (Just a large substitution.) There is no property of a block cipher which is not ideally modelled by a substitution table of appropriate size containing a key-selected permutation of the possible output values. (Invertibility argument: A permutation of the possible output values is just a re-arrangement of values, without duplication. As long as there are no duplicate output values, the substitution is invertible.) (Avalanche argument: Avalanche is an expected property of an invertible substitution (4.9).) 7. BLOCK MIXING TRANSFORMS ========================= 7.1 DEFINITION: A BLOCK MIXING TRANSFORM is a mapping from multiple input code values to the same number of output code values, in which: 1. (Invertible.) The mapping is invertible. (Every possible input will imply a different output, and every possible output will imply a different input.) 2. (Each Output a Function of All Inputs.) Every output code value is a function of all input code values. 3. (Changes Propagate to All Outputs.) Any change to any one of the input code values will change all of the output code values. 4. (Balance and Input Independence.) Stepping any input through all possible values (with the other inputs held fixed) will step every output through all possible values. 7.2 ASSERTION: (We have a finite field.) Mod-2 polynomials modulo some irreducible polynomial p generate a finite field. (Comment: Proofs can use algebra.) 7.3 THEOREM: (Example block mixing transform.) The equations X = 3A + 2B = A + 2(A + B) Y = 2A + 3B = B + 2(A + B) and the inverse A = X + 2(X + Y) B = Y + 2(X + Y) mod 2 and mod p, where p is some mod 2 irreducible polynomial, represent a block mixing transform. (Inverse Proof: assume true, thus A = A + 2(A + B) + 2(A + 2(A + B) + B + 2(A + B)) = A + 2(A + B) + 2(A + B) = A and B = B + 2(A + B) + 2(A + 2(A + B) + B + 2(A + B)) = B + 2(A + B) + 2(A + B) = B which are both correct, so the inverse does exist for any polynomials X and Y.) (Function Proof: the equations for output code X includes both input code values A and B, so X is a function of both input codes. Y reasons similarly.) (Change Propagation Proof: First consider one term of one output block equation: Suppose some change C is added to A: X = 3A + 2B (mod 2, mod p) X' = 3(A+C) + 2B X' = 3A + 3C + 2B dX = X' - X = 3C So, for any non-zero change, X has changed. Similar reasoning covers the other term, and the other equation.) (Balance Proof: Suppose not. Assuming A is fixed, then there must be two different values, B and B', which produce the same X: X = 3A + 2B = 3A + 2B' so X + 3A = 2B = 2B' which implies that B = B' a contradiction. Fixing B or working on the other block reason similarly.) 7.4 THEOREM: It is easy to manipulate both input blocks to a block mixing transform so as to fix one of the output blocks at a constant value. (Proof: Just inverse-transform the desired output blocks.) 7.5 ASSERTION: A block cipher can be used as a block mixing transform. (Method: Just divide the input block and output block into smaller "sub-blocks.") (Inverse Proof: A block cipher is invertible (6.1) and (6.3).) (Function Proof: To the extent that the block cipher can be considered an invertible substitution, each output bit is a function of each input bit (4.5), so each sub-block result is certainly a function of all sub-block input values.) (Change Propagation Argument: In a statistical sense, assuming substantial sub-blocks, each sub-block is extremely likely to change for any input change whatsoever (2.9).) (Balance Argument: In a statistical sense, over all possible inputs and all possible keys, any output value is equally likely, so any set of input changes is likely to produce a statistically-balanced result.) 8. 1X FENCED DES STRUCTURES ========================= 8.1 DEFINITION: A 1X INPUT-FENCED DES STRUCTURE is a 64-bit- wide construct consisting of eight keyed invertible byte- substitutions feeding a single DES ciphering: S S S S S S S S ------DES------ 8.2 THEOREM: Any data change whatsoever into a 1x input-fenced DES structure will produce a different result, and is expected to change about half of the output bits. (Proof: Every bit in the input block enters some small substitution which selects a keyed or arbitrary value from its set of output codes. Any input-change into an invertible substitution is is guaranteed to produce a change to at least one output bit (4.5). We model the DES ciphering as a large invertible substitution (6.5), and so expect that any change to the input will select a different output code value, which is likely to change about half of the output bits (4.7).) 8.3 DEFINITION: A 1X OUTPUT-FENCED DES STRUCTURE is a 64-bit-wide construct consisting of a single DES ciphering and eight keyed invertible byte-substitutions on the output: ------DES------ S S S S S S S S 8.4 THEOREM: Any data change whatsoever into a 1x output-fenced DES structure is expected to change about half of the output bits. (Proof: We model the DES ciphering as a large invertible substitution (6.5) and expect that any change to the input will change about half the bits in the output value (4.7). Since every possible DES result may occur, there are no special bits or bit subsets (2.6). Each of the output substitutions samples a bit subset in which about half of the bits are expected to change. Any change into an output substitution will select a different output code value, thus changing about half of the output bits (4.7) in every output substitution, and, thus, the overall output.) (Comment: One time in 255 there is no change to an output substitution, which is exactly what is required for an even output distribution. ) 8.5 DEFINITION: A 1X FENCED DES CIPHER is a 64-bit-wide construct consisting of eight keyed invertible byte-substitutions on the input, a single DES ciphering, and eight keyed invertible byte-substitutions on the output: S S S S S S S S ------DES------ S S S S S S S S 8.6 THEOREM: (Avalanche.) In 1x Fenced DES, any change of even a single bit in the large input block can be expected to change about half the bits in the large output block. (Proof: See 8.2 and 8.4.) 8.7 THEOREM: (Invertibility.) A 1x Fenced DES cipher is invertible. (Proof: From the construction of 1x Fenced DES, the small input substitutions are invertible, as are the small output substitutions. DES is assumed to be invertible. Since all elements in sequence from input to output are separately invertible, the sequential combination of these elements must also be invertible.) 9. 2X FENCED DES STRUCTURES ============================ 9.1 DEFINITION: A 2X INPUT-FENCED DES STRUCTURE is a 128-bit- wide construct consisting of 16 keyed invertible byte-substitutions feeding a block mixing transform, which feeds two DES cipherings: S S S S S S S S S S S S S S S S --------------mix-------------- ------DES------ ------DES------ 9.2 THEOREM: Any data change whatsoever into a 2x input-fenced DES structure will produce a different result, and is expected to change about half of the output bits. (Proof: Any change into an invertible substitution is guaranteed to produce a change to at least one output bit (4.5). Any change to either input block of a two-block block mixing transform is guaranteed to produce a change to both output blocks (7.1.3). We model the DES cipherings as large invertible substitutions (6.5) and so expect that any change to the input will select a different output code value, which is likely to change about half of the output bits (4.7).) 9.3 DEFINITION: A 2X OUTPUT-FENCED DES STRUCTURE is a 128-bit- wide construct consisting of two DES cipherings which feed a two- block block mixing transform, which feeds 16 keyed invertible byte- substitutions. ------DES------ ------DES------ --------------mix-------------- S S S S S S S S S S S S S S S S 9.4 THEOREM: Any data change whatsoever into a 2x output-fenced DES structure is expected to change about half of the output bits. (Proof: We model the DES cipherings as large invertible substitutions (6.5) and expect that any change to their inputs will select a different output value from all possible output values (4.5). Since any DES result is possible, any value is possible from both block mixing transform outputs (7.1.4), so we expect about half of the output bits to change (4.7). Since any block mixing result value is possible, there are no special bits (2.6), and each of the output substitutions samples a bit subset in which about half of the bits are expected to change. Any change into an output substitution will select a different output code value, thus changing about half of the output bits (4.7) in every output substitution, and, thus, the overall output.) 9.5 DEFINITION: A 2X FENCED DES STRUCTURE is a 128-bit-wide construct consisting of 16 keyed invertible byte-substitutions which feed a block mixing transform which feeds two DES cipherings which feed another two-block block mixing transform, which feeds another 16 keyed invertible byte-substitutions: S S S S S S S S S S S S S S S S --------------mix-------------- ------DES------ ------DES------ --------------mix-------------- S S S S S S S S S S S S S S S S 9.6 THEOREM: (Avalanche.) In a 2x Fenced DES cipher, any change of even a single bit in the large input block can be expected to change about half the bits in the large output block. (Proof: See 9.2 and 9.4.) 9.7 THEOREM: (Invertibility.) A 2x Fenced DES cipher is invertible. (Proof: From the construction of 2x Fenced DES, the small input substitutions are invertible, as are the small output substitutions. The block mixing transform is invertible (7.1.1). DES is assumed to be invertible. Since all elements in sequence from input to output are separately invertible, the sequential combination of these elements must also be invertible.) 10. 4X FENCED DES STRUCTURES ============================ 10.1 DEFINITION: A 4X FENCED DES CIPHER is a 256-bit-wide construct consisting of 32 keyed invertible byte-substitutions feeding a block mixing transform with two 128-bit blocks, which then feeds two block mixing transforms each with two 64-bit blocks, which feed four DES cipherings. The DES results feed two block mixing transforms each with two 64-bit blocks, which feed a block mixing transform with 128-bit blocks, which feeds 32 more keyed invertible byte-substitutions. S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S ------------------------------mix------------------------------ --------------mix-------------- --------------mix-------------- ------DES------ ------DES------ ------DES------ ------DES------ --------------mix-------------- --------------mix-------------- ------------------------------mix------------------------------ S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S 10.2 THEOREM: (Every input bit affects every DES ciphering.) In 4x Fenced DES, every bit in the large input block will affect at least one bit of the input to each of the DES cipherings. (Proof: Every bit in the large block enters some small substitution. Any input-change into a substitution is guaranteed to produce a change to at least one output bit (4.5). Any change into either side of the first-level block mixing transform is guaranteed to change both sides of the output (7.1.3), so some change is guaranteed to be present in the input of both next-level block mixing transforms. Again, any change anywhere on those inputs is guaranteed to be present in both sides of both outputs, which are the inputs to each DES ciphering.) 10.3 THEOREM: (Each output bit is affected by every DES ciphering.) In 4x Fenced DES, any data change whatsoever into any of the four DES cipherings is expected to change about half of the output bits. (Proof: We model the DES cipherings as large invertible substitutions (6.5) and expect that any change to their inputs will select a different output value from all possible output values (4.5). Since any DES result is possible, any value is possible on both outputs of the first-level output block mixing transform (7.1.4). Any possible block mixing transform result can be produced by some BMT input, so any possible value can occur as the input to the second-level output block mixing transform. With any possible BMT input, every output will occur, so there are no special bits (2.6), and each of the output substitutions samples a bit subset in which about half of the bits are expected to change. Any change into an output substitution will select a different output code value, thus changing about half of the output bits (4.7) in every substitution, and, thus, the overall output.) 10.4 THEOREM: (Avalanche.) In 4x Fenced DES, any change of even a single bit in the large input block can be expected to change about half the bits in the large output block. (Proof: See 10.2 and 10.3.) 10.5 THEOREM: (Invertibility.) 4x Fenced DES is invertible. (Proof: From the construction of 4x Fenced DES, the small input substitutions are invertible, as are the small output substitutions. The block mixing transform is invertible (7.3.1). DES is assumed to be invertible. Since all elements in sequence from input to output are separately invertible, the sequential combination of these elements must also be invertible.) 11. 4X FENCED DES STRENGTH CHARACTERISTICS ========================================== 11.1 ASSERTION: (DES cipherings cannot be separated.) In 4x Fenced DES, it is not possible to isolate and work on a single DES ciphering unless the small input substitutions have first been resolved. (Argument: In order to key-search a single DES ciphering, it is necessary to develop the input and output value for that particular ciphering. The large input and output blocks are known, but the values sent to the internal cipherings are hidden by the input and output substitutions.) 11.2 ASSERTION: (Input substitutions cannot be separated.) In 4x Fenced DES, it is not possible to isolate and work on any one small input substitution unless all four of the DES keys and at least one element in each of the 32 small output substitutions have first been resolved. (Argument: Even though their input values are known, resolving the content of the small input substitutions requires some information about their output values. Since these values flow through the internal DES cipherings, if DES is effective, these values cannot be known without the DES keys. Further, each of the DES keys is required, since all of the DES cipherings combined produce the known output. There can be no statistical effects which identify particular values from the input substitutions, because any change of any number of bits whatsoever affects the large output block similarly. There can be no statistical effects which isolate individual input substitutions because each input substitution has the same effect on the large output block. Any change whatsoever from any input substitution changes about half the bits in the output block, making statistical issues about the content of the substitutions completely irrelevant.) 11.3 ASSERTION: (Output substitutions cannot be separated.) In 4x Fenced DES, it is not possible to isolate and work on any one small output substitution unless all four of the DES keys and at least one element in each of the 32 small input substitutions have first been resolved. (Argument: Even though their output values are known, resolving the content of the small output substitutions requires some information about their input values. Since the input values flow from the internal DES cipherings, if DES is effective, these values cannot be known without the DES keys. Further, each of the DES keys is required, since each DES ciphering affects all of the output substitutions. There can be no statistical effects which identify particular input values to the output substitutions, because any change of any number of bits whatsoever affects the output from the substitution similarly. There can be no statistical effects which isolate individual output substitutions, because each of their input values come from the the output of the DES cipherings, and these values are "random like." So there can be no statistic to use for attack.) 12. FENCED DES EXPECTED STRENGTH ================================ 12.1 THEOREM: (Absolute minimum strength of 1x Fenced DES.) Assuming a known-plaintext attack, further assuming that all the input and output substitutions are known, if DES has a strength of 56 bits, the 1x Fenced DES construct has a keyspace of 56 bits. (Proof: All data flows through each layer; if the input and output substitutions are known, they do not confuse the data, but they also do not undo whatever confusion DES provides.) 12.2 ASSERTION: (Expected strength of the substitution layers in 1x Fenced DES.) Assuming a known-plaintext attack, and further assuming that the DES key is known, the 1x Fenced DES construct has a keyspace exceeding 64 bits. (Argument: The overall input is known, so the small input substitution _positions_ are all known; the uncertainty lies wholly in the _values_ at those positions. There are 256 possible values at the known position for each of eight input substitutions, for 256**8, or 2**64 possibilities. (A 63-bit expectation.) The uncertainty in the output substitution positions is the same, but the input and output substitutions are not independent: Since the DES key is known, defining the input substitutions implies what the output substitutions must be (or vise versa), so only one substitution level contributes to the keyspace. When working on the small input substitutions, the individual substitutions are independent: If even one of the input substitute values is wrong, we expect that half of the DES result bits will be wrong, which will imply wrong positions for most output substitutions. The process is similar if we choose to work on the output substitutions instead. A 64-bit keysearch is guaranteed to identify one element in each of the eight small input substitutions (for example). Then, assuming infinite known-plaintext, we just look for data blocks which are the same as the solved block in seven of the eight bytes. For each possible value of the eighth byte we can easily try each of the 254, 253,..., 2 remaining values (which will implicitly define many of the output substitutions) at almost no cost beyond holding and finding appropriate messages. With only a limited amount of known-plaintext there will be fewer if any messages which differ in just one byte, few if any quick byte searches, and many more-substantial searches until the input substitutions are filled in.) (Comment: DES with a known key is an example of a block mixing transform with absolutely no strength at all by itself, which nevertheless adds strength through bit mixing.) 12.3 ASSERTION: (Expected strength of 1x Fenced DES.) Assuming a known-plaintext attack, the 1x Fenced DES construct has a keyspace exceeding 120 bits. (Argument: When the DES key is known, the strength is 64 bits; the unknown DES key adds 56 bits more, for a total of 120 bits. (This is 2**64 times the complexity of DES.) It is not possible to separate the substitution layers from the cipher layer and so work on either independently, because the data flows through both. In addition, each DES operation is a function of every input bit (8.2) and each output bit is a function of every DES output (8.4), so individual DES operations cannot be isolated by particular input or output bits. A 120-bit keysearch will identify the DES key and one element in each of the eight small substitutions, and then we need to fill out the rest of each substitution as above.) 12.4 THEOREM: (Absolute minimum strength of 4x Fenced DES.) Assuming a known-plaintext attack, further assuming that all the input and output substitutions are known, if DES has a strength of 56 bits, the 4x Fenced DES construct has a keyspace exceeding 56 bits. (Proof: All data flows through each layer. The information content of the data is 256 bits; to recover that data, all four DES operations must be solved. Even if we assume that some aspect of the construction allows the DES operations to be solved separately, the resulting strength is still somewhat more than a single DES cipher.) 12.5 ASSERTION: (Expected strength of separated 4x Fenced DES.) Assuming a known-plaintext attack, and assuming that the internal ciphers _can_ be isolated and worked on separately, the 4x Fenced DES construct has an overall keyspace of not less than 120 bits. (Argument: The substitution and ciphering occur in series, consequently, at least one eight-byte substitution (input or output) and one DES ciphering must be solved simultaneously, even if the block mixing transform fails.) 12.6 ASSERTION: (Expected strength of 4x Fenced DES.) Assuming a known-plaintext attack, and assuming that the internal ciphers _cannot_ be isolated and worked on separately, the 4x Fenced DES construct has an overall keyspace exceeding 480 bits. (Argument: The small substitutions (input or output) jointly contribute 256 bits, and the four DES keys contribute 224 bits for a total of 480 bits. That is, searching a 480-bit keyspace will solve the system for a particular input (or output) block. This identifies the DES keys, but only solves 1/256th of each of 32 substitutions. Once the system is solved for a particular block, the 255 other entries in each of 32 substitutions must be filled in to completely solve the cipher.) Results It appears that Fenced DES can reasonably be proven to be an invertible block cipher which has the avalanche property (provided, of course, that DES has that property) with a strength at least that of DES itself. Reasonable-sounding arguments suggest that the internal ciphers cannot be separated and worked on independently, and that the resulting cipher has substantial strength. It would be nice to tighten this up; any and all suggestions are welcome. Appendix Some Fenced DES constructions: 1x Fenced DES S S S S S S S S ------DES------ S S S S S S S S 2x Fenced DES S S S S S S S S S S S S S S S S --------------mix-------------- ------DES------ ------DES------ --------------mix-------------- S S S S S S S S S S S S S S S S 4x Construct with 1x Strength S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S ------DES------ ------DES------ ------DES------ ------DES------ S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S Original 4x Fenced DES S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S --------------mix-------------- --------------mix-------------- ------------------------------mix------------------------------ ------DES------ ------DES------ ------DES------ ------DES------ ------------------------------mix------------------------------ --------------mix-------------- --------------mix-------------- S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S Current 4x Fenced DES S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S ------------------------------mix------------------------------ --------------mix-------------- --------------mix-------------- ------DES------ ------DES------ ------DES------ ------DES------ --------------mix-------------- --------------mix-------------- ------------------------------mix------------------------------ S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S 4x Fenced DES with Less Storage and Strength (A..H and S..Z represent 16 keyed byte-substitutions, each used four times.) A B C D E F G H A B C D E F G H A B C D E F G H A B C D E F G H ------------------------------mix------------------------------ --------------mix-------------- --------------mix-------------- ------DES------ ------DES------ ------DES------ ------DES------ --------------mix-------------- --------------mix-------------- ------------------------------mix------------------------------ S T U V W X Y Z S T U V W X Y Z S T U V W X Y Z S T U V W X Y Z --- Terry Ritter ritter(a)io.com

1 0

Digicash PR
by Dave Banisar 17 Dec '03

17 Dec '03

Date 5/26/94 Subject Digicash PR From Dave Banisar To Cypherpunks List Digicash PR Thought this might be of some interest. dave --------------------------------------------------------------- DIGICASH PRESS RELEASE World's first electronic cash payment over computer networks. ============================================================= FOR IMMEDIATE RELEASE (Release Date: May 27, 1994) ---------------------------------------------------------------------- Payment from any personal computer to any other workstation, over email or Internet, has been demonstrated for the first time, using electronic cash technology. "You can pay for access to a database, buy software or a newsletter by email, play a computer game over the net, receive $5 owed you by a friend, or just order a pizza. The possibilities are truly unlimited" according to David Chaum, Managing Director of DigiCash TM, who announced and demonstrated the product during his keynote address at the first conference on the World Wide Web, in Geneva this week. Electronic cash has the privacy of paper cash, while achieving the high security required for electronic network environments exclusively through innovations in public key cryptography. "It's the first software only solution. In the past we've pioneered such cash for chip cards and electronic wallets, always with a tamper-resistant chip for storing the value--now all you have to do is download the software and you're up and running" continues Dr. Chaum. The product works with Microsoft(R) Windows TM, Macintosh TM, and most UNIX TM platforms. It was shown integrated with Mosaic, the most popular software for people accessing databases, email, or other services on the Internet and World Wide Web. The graphic user interface allows intuitive "dragging and dropping" of icons representing stacks of coins, receipts, record books, etc. The company will be supplying the technology through other firms who will release the products, under various cooperation and trial programs. The user software, which allows both paying and receiving payment, will be distributed free of charge. The product was developed by DigiCash TM Corporation's wholly owned Dutch subsidiary, DigiCash TM BV. It is related to the firm's earlier released product for road pricing, which has been licensed to Amtech TM Corporation, of Dallas, Texas, worldwide leader in automatic road toll collection. This system allows privacy protected payments for road use at full highway speed from a smart card reader affixed to the inside of a vehicle. Also related is the approach of the EU supported CAFE project, of which Dr. Chaum is Chairman, which uses tamper-resistant chips inserted into electronic wallets. The underlying 'blind signature' technology was described in the article "Achieving Electronic Privacy," by David Chaum, Scientific American, August 1992. ---------------------------------------------------------------------- For more information contact: DigiCash bv info(a)digicash.nl Kruislaan 419 tel +31 20 665 2611 1098 VA Amsterdam fax +31 20 668 5486 The Netherlands ----------------------------------------------------------------------

1 0

Re: Factoring with a quantum computer (Citation)
by rjc＠gnu.ai.mit.edu 17 Dec '03

17 Dec '03

James A. Donald (jamesd(a)netcom.com) writes: > persuasion to get him to put up the pot. Alas, Michael was > not willing to let the pot for the bet go outside the > control of him or these dubious people. Eventually I > resorted to a vigorous attempt to shame him into putting up > the money. > > My unkind comments concerning Michael and his pals > eventually resulted in me being expelled from the > Extropians list, for flaming Michael and defaming the Exi > board. First let me explain something to people who don't know. The extropians list has a legal arbitration system to help keep down flames. We have rules against bringing verbal assaults into heated debates so that if you feel someone is insulting you, you may 'press charges'. If evidence is presented, the person usually gets a warning. 3 warnings and your posting privileges get revoked for a period between 24-72 hours to allow a 'cool down' period on the list. This was implemented out of neccessity because the list was averaging between 150 to 300 messages a day with most of those coming from only a handful of people. A common way of resolving a standoff debate on the Extropians list is to put your money where your mouth is -- a bet. This causes someone to get off their lazy ass and go look up the citation and present it to the list for judgement of the bet. Michael suggested having the bet held by the treasury of Extropy, Inc, the non-profit which runs the list. Extropy, Inc. has *never* been accused of financial impropriety with people's funds. They run an honest operation with far more altruism than libertarians should bear (e.g. the board members go into debt to maintain service to extropians even when revenues are low) James Donald insinuated that some board members were dishonest, *BUT*, he was not kicked off for this. Michael and one of the board members pressed charges under our flaming/insult rule and James had his posting suspended for some period (a few days, 72 hours I think) Usually, we rely on an honor code to enforce posting priveleges. We do not software block punished people from posting, but rely on their honor and fairness to commit themselves to arbitration. Donald didn't stop posting, so he had his priveleges turned off in software. He still wasn't "deleted' (kicked off from the list) The final act which led to his removal was that he circumvented the list security system by forging the headers of his message so as to appear to be Perry Metzger. This is a serious offense on the list software we run because each user has database information associated with their account, and our software is pay-for-use. Posting under someone else's account corrupts the list statistics, deducts list credits from their account, and could, depending on software limits set, use up their daily posting quota. For the act of forgery, James Donald was deleted and for no other reason. Extropy, Inc. has given Harry S. Hawk full autonomy in managing the list. The board can not kick off people just because they hate them, which the board didn't hate James Donald anyway. He started and esclated innuendo for no reason whatsoever. The legal system has been used rarely since and things are relatively calm now. If James Donald thinks he was kicked off because the list owners hated him, he is sadly mistaken. He should have honored the legal judgement and restrained himself from posting/flaming for the time limit set. Furthermore, he shouldn't have forged headers especially since it wastes my time when I have to go manually correct people's accounts. disclaimer: I hold no animosity towards James Donald, I hardly know him. I am merely stating what I recall as the historical record since I am the one who manages the software engineering side of the list. -Ray

2 1

Geek of the Week (fwd)
by snyderra＠dunx1.ocs.drexel.edu 17 Dec '03

17 Dec '03

OK. I do remember the earlier discussion about forwarding material to the list, but this is forwarding a pointer to data, which I hope is OK. :-) I get my talk radio files from ftp://sunsite.unc.edu/pub/talk-radio, although you may want to check the ITR FAQ for a closer location. (Th FAQ should be on rtfm.mit.edu) Bob >Date: Fri, 15 Jul 1994 04:03:15 -0400 >To: "Announcements" <announce(a)radio.com> >From: "Internet Multicasting Service" <rtfm(a)radio.com> >Org: Internet Multicasting Service >Subject: Geek of the Week >Status: RO > >The MIME-Version header has been deleted from this message to permit >interoperability with a larger number of mailers. > >------- =_aaaaaaaaaa0 >Content-Type: application/x-program-listing >Content-ID: <071594_geek_ITR.2(a)trystero.radio.com> > >Station: Internet Multicasting Service >Channel: Internet Talk Radio >Program: Geek of the Week >Content: Steve Crocker > >Carl Malamud interviews Steve Crocker, a newly elevated member of the >Internet Architecture Board and a leading contributor in efforts to >provide a security infrastructure for the Internet. Crocker discusses >PEM, Clipper, DSS, PKP, and other important security acronyms. > >Geek of the Week is made possible by the sponsors of Internet Multicasting >Service, including O'Reilly & Associates, Sun Microsystems, and Interop >Company. Additional support is provided by NASA, Cisco Systems, Harper >Collins, Persoft, Tadpole Technology, and WAIS Inc. Network connectivity >for the Internet Multicasting Service is provided by UUNET Technologies and >by MFS Datanet. > >Cassette tapes of Geek of the Week are available from O'Reilly & Associates. >Send electronic mail to audio(a)ora.com or point your WWW Viewer to the >Global Network Navigator (http://nearnet.gnn.com/gnn/gnn.html) > >ITR Program Files: > >Size Name Description >========== ====================== ======================= >14,771,098 071594_geek_01_ITR.au Steve Crocker > 071594_geek_ITR.readme (This File) > >To learn about the Internet Multicasting Service, send your electronic >mail to info(a)radio.com. > >------- =_aaaaaaaaaa0 >Content-Type: multipart/mixed; boundary="----- =_aaaaaaaaaa1" >Content-ID: <071594_geek_ITR.3(a)trystero.radio.com> > >------- =_aaaaaaaaaa1 >Content-Type: message/external-body; > access-type="anon-ftp"; > name="071594_geek_ITR.readme"; > site="$SITE"; directory="$DIRECTORY" > >Content-Type: text/plain >Content-ID: <071594_geek_ITR.4(a)trystero.radio.com> >Content-Description: Readme (This File) > >------- =_aaaaaaaaaa1 >Content-Type: message/external-body; > access-type="anon-ftp"; > name="071594_geek_01_ITR.au"; size="14771098"; > mode="image"; site="$SITE"; directory="$DIRECTORY" > >Content-Type: audio/basic >Content-ID: <071594_geek_ITR.5(a)trystero.radio.com> >Content-Description: Steve Crocker > >------- =_aaaaaaaaaa1-- > >------- =_aaaaaaaaaa0-- -- Bob Snyder N2KGO MIME, RIPEM mail accepted snyderra(a)dunx1.ocs.drexel.edu finger for RIPEM public key When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl.

1 0

Handling subscription requests
by tcmay＠netcom.com 17 Dec '03

17 Dec '03

Rishab asked earlier if there isn't some way that Majordomo could automatically filter the requests that go this list instead of to the Majordom agent. Pretty unlikely, for various reasons: - The requests would be poorly formed, such as "Can anyone tell me how to subscribe?" and I can't imagine anything short of a CPU-intensive natural language processor able to deduce the actions needed. Certainly I don't want to get added again, or be sent a message, every time "Pretty Good Autosubscriber" sees the word "subscribe" in one of my messages! (Yes, I can imagine an algorithm--"if not already a subscriber and mentions subscribe, then...") - In any case, this is very far from what Majordomo now does. In fact, Majordomo is very picky about the command syntax it expects to see. - And the CPUi-intensive filtering to look for the right magic words would be unwelcome. Especially if every message to cypherpunks(a)toad.com had to be examined! (Again, I can imagine way to reduce this, such as only looking closely at nonsubscriber messages. But not in Majordomo's current feature set.) So what to do? Frnakly, I don't think it's too big a problem. Only a couple of these hit the list per week, even after the list has gotten some publicity someplace like "Wired." Here's what I try to do, when I remember. When I see one of these requests I reply and attach this message: How to Subscribe to the Cypherpunks List This message is just an informal tip sheet on how to get on and off the Cypherpunks list, sent manually by me to people who ask how they can join the list. The Cypherpunks list is managed automatically by the "Majordomo" program, which is commonly used for mailing lists. Command syntax may be familiar to you from other lists. To subscribe: * Send a message to: majordomo(a)toad.com * No subject is needed, or is used * In the *body* section, include only the following: subscribe cypherpunks * This will subscribe you with the address from which you sent the message. If you wish to subscribe with a different address, for some odd reason, send a "help cypherpunks" message instead. * Unsubscribe by sending the message: unsubscribe cypherpunks * A list of current subscribers can be gotten by sending the message "who cypherpunks" to the same address. Be forewarned--your membership on the list will be known to others. (Hal Finney and others have talked about providing secondary mailing list, which can even be encrypted.) Comments: - Write the above information down somewhere. Do not send unsubscribe messages to the main list (cypherpunks(a)toad.com) And the address "cypherpunks-request(a)toad.com" probably will not work either. Use majordomo(a)toad.com. - The list is a high volume one. Fifty messages a day is common. If you can't handle this, unsubscribe. Or read your mail several times a day and make liberal use of the "delete" function. - The list was started in 1992 and has roughly 600 subscribers. - If you are new to the list, read for a while before posting. Be especially polite by not asking "dumb" questions like "Why is Clipper a bad idea?" and "Can anybody break this code?" (It is sometimes said there are no dumb questions. I disagree.) - You will also receive a longer welcome message after your subscription has been successfully processed. - The subscriber list has gotten corrupted several times, due to disk space problems. If you receive no traffic for several hours or more, do a "who cypherpunks" to see if this has happened again. Either resubscribe in the usual way, or wait for the list to (maybe) be restored. - If you find yourself getting two copies of every message, see if you are subscribed under two different mailing addresses. (The mail headers should tell you.) Then unsubscribe the address you don't want to use. This should answer the most obvious questions. Feel free to pass this message on to folks who ask about subscribing. --Tim May -- .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay(a)netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power: 2^859433 | Public Key: PGP and MailSafe available. "National borders are just speed bumps on the information superhighway."

2 1

Re: Anti-Clipper Article in "THe Computer Applications Journal"
by smb＠research.att.com 17 Dec '03

17 Dec '03

Might I suggest that this is not the right newsgroup for anti-Clipper articles? I've never seen *any* Cypherpunk defend it; what's the point? Preaching to the choir? Repeat doses of brainwashing? Citations are fine; they show what the outside world thinks. Technical aspects are fine; there's a lot to be learned about Skipjack and key escrow. But there's little point -- on this list -- to hearing yet again that Clipper is bad (unless, of course, someone starts defending it here). --Steve Bellovin

2 1

New Money design announced
by nym＠netcom.com 17 Dec '03

17 Dec '03

I think this came from a Fidonet channel. an interesting topic: how will this affect the value of US cash? i.e. will it affect the value of the dollar worldwide? often when countries are facing economic trouble they change their currency. **** Conf. : 0008 - FINANCIAL WASHINGTON (AP) -- Move over Ben Franklin, tell Andrew Jackson the news: The portraits on the nation's paper money likely will be enlarged and moved off-center as part of the first major makeover in 65 years. ``Our plan ... is a pre-emptive step to protect U.S. currency from high-tech counterfeiting,'' Treasury Secretary Lloyd Bentsen said in announcing the redesign Wednesday. His department plans to have a final design ready sometime in 1995 and begin circulating new bills about a year later, starting with the most popular target for counterfeiters, $100 notes. Nothing has been decided for certain, but Treasury officials gave the House Banking Committee a rundown Wednesday of what was likely. The enlarged portraits -- Franklin on the $100, Ulysses Grant on the $50, Jackson on the $20, Alexander Hamilton on the $10, Abraham Lincoln on the $5 and George Washington on the $1 -- will allow for more detailed engraving of what is the most recognizable feature on a bill. The $2 bill, with Thomas Jefferson, is not being redesigned. And, moving the portraits will make room for a watermark in the form of a smaller version of the portrait, visible only when a bill is held to the light. Other likely changes include: -- Color-shifting ink that may, for instance, appear green when viewed straight on and gold from an angle. -- Computer-designed ``interactive'' patterns that turn wavy when illicitly copied. -- Iridescent planchettes in bills' paper. These are colored discs only a few millimeters wide that reflect light. -- Micro-printing and machine-detectable threads or fibers in the paper. The last major change in U.S. currency came in 1929, when bills were reduced in size and given a uniform look. Congress added the words ``In God We Trust'' in 1957. In 1990, several small changes made it more difficult to counterfeit with modern color photocopiers. They included adding a microscopic line of type and a polyester thread visible only when a bill is held to a light. Most lawmakers applauded the latest modifications, saying they were long overdue. ``We must protect the dollar's standing as the world's foremost currency. Our financial future depends upon it,'' said the committee chairman, Rep. Henry B. Gonzalez, D-Texas. But others warned against too radical a redesign, saying it would send a message of instability at a time when the value of the dollar is being battered on world currency markets. Peter H. Daly, director of the Bureau of Engraving and Printing, said the bills' traditional look will be maintained as much as possible. The paper will feel the same and the size of notes won't change. And the same engraving style will be used for portraits, borders, numbers and the historic scenes on bills' back. Bentsen stressed that old money will continue as legal tender. ``The redesigned currency will be introduced over a period of years and no U.S. currency will be demonetized, devalued or recalled,'' he said. And U.S. Treasurer Mary Ellen Withrow promised a worldwide educational campaign to encourage public acceptance of the new design. About $357 billion of U.S. paper currency is in circulation, more than 60 percent of it abroad. In fact, in some countries with troubled economies it serves as the principal medium of exchange. According to the Secret Service, counterfeiting abroad now far outweighs domestic counterfeiting. Last year, $120 million in phony bills were seized overseas, compared with $44 million domestically, said Secret Service Deputy Director Guy P. Caputo. Republican Reps. Jim Leach of Iowa and Bill McCollum of Florida suggested the administration may be minimizing the severity of the problem. Leach said a Middle Eastern country, which he did not name, reportedly has developed the capacity to counterfeit large quantities of $100 notes. He was apparently referring to trade press reports that Iran was distributing counterfeit bills through Lebanon. But Bentsen stressed that the changes were being made in anticipation of future problems and not in response to any current counterfeiting crisis.

2 1

Re: Hashed hash (and Kent's games)
by Ben.Goren＠asu.edu 17 Dec '03

17 Dec '03

At 12:19 AM 7/17/94, Kent Borg wrote: >Ben.Goren(a)asu.edu foolishly says: >>I'm planning on implementing the "cryptographic protection of databases" > >And wonders about the hash being too fast to compute, that a >brute-force traversal of the database would be too easy. The idea is >then to hash a bunch of times to burn CPU cycles, but what if the hash >is a group, extra hashing could be reversed quickly. (Did I get that >right?) On the nose. >Well, as the LOUD proponent of making secret keys s-l-o-w-e-r to >decrypt, I have thought about this a bit, and have a suggestion: > >Hash once, then do a zillion encryptions of the hash with a non-group >cypher like DES. I'll probably do just that. First thought, subject to revision: hash the name, feed it to DES with the output of a deterministic RNG (need not be secure, but the slower the better--BBS? (not that BBS is incesure)) as the key; repeat as needed. Hmmm...perhaps I'll adapt an earlier idea of mine: split the hash into two parts, a and b, and compute (a^(1/b))-1, and use some or all bits after the leading zeros. >Another idea (something I have thought less about): send every legit >user of the database a custom version with the parts encrypted with >that user's public key--and do the trick mailing list companies use, >scatter some dummy info in the list. When a dummy (not just me) gets >a junk mailing, go beat up on the user who's copy had to have supplied >the junk [. . . .] Nice idea, but there's neither the available resources to do that, nor, I think, the desire to beat up on careless users. Berzerk suggests a 0.1 S/N ratio (and in an earlier note a couple useable algorithms for the multiple encryption process); that would not be practical for any decent sized database, and I might have 100K or so people to deal with. But I almost certainly will mix in at least some random padding. I imagine that the database will always be the same length, even as people are added and/or removed with time. And the records, of course, will be premuted randomly. >-kb, the Kent who doesn't want to be thought of as only a card player Then here's a suggestion for you: develop some other primitives, like rolling dice, and you could implement just about any other game you like. Monopoly would need (aside from licensing issues) the dice, two decks of special cards, and some ecash. (Surely MM used as Monopoly Money isn't subversive? After all, it's teaching our young 'uns to be good capitalists.) Scrabble would need a deck of cards, each of which contains only a letter, with many duplicates. Trivial Pursiut is just a huge deck of cards; they'd probably be index positions to the database of questions, so special editions are just a file switch away. These are among the most popular games in the US, and probalby abroad. Build your primitives right, and these games are as simple as specifing paramaters (how many sides to the dice, what info the cards contain, etc.). And maybe you could license the stuff, each and every independent game, to the current owners of the games that aren't PD. So how about becomming "kb, the Kent who digitized the American family evening"? Go for it! And drop me a line when you want beta testers (sometime Thursday?). >Kent Borg +1 (617) 776-6899 b& -- Ben.Goren(a)asu.edu, Arizona State University School of Music net.proselytizing (write for info): Protect your privacy; oppose Clipper. Voice concern over proposed Internet pricing schemes. Stamp out spamming. Finger ben(a)tux.music.asu.edu for PGP 2.3a public key.

2 2

PGP bug *NOT* yet fixed
by Ben.Goren＠asu.edu 17 Dec '03

17 Dec '03

Y'all remember that bug that Colin Plumb told us about in the true random number generation part of PGP? It's still there, in the version from net-dist.mit.edu, as of late yesterday evening. There is *no* mention of the bug anywhere, in any readme files, in the documentation, anything. This strikes me as irresponsible. I would expect PGP 2.6a to have been released the day of the announcement, with the bug fixed. If there's some reason why that couldn't be done, then at least there should be some sort of prominent notice detailing the change, and probably a diff file--or even a simple shell script--to apply the (very simple!) fix. The signature on the following file checks as follows: >File has signature. Public key is required to check signature. . >Good signature from user "Colin Plumb <colin(a)nyx.cs.du.edu>". >Signature made 1994/06/01 14:04 GMT That's a month and a half ago. The *only* copies of PGP 2.6 out there that are free of the bug are those that have been fixed by hand. That's probably not all that many of them. I'm going to bite the bullet and paste in the original message here. Feel free to flame me if this is unnecessary re/cross-posting, but I'm not aware of any place to get this aside from digging through archives, and.... b& -----BEGIN PGP PUBLIC KEY BLOCK----- Version: 2.5 mQCNAi3L864AAAEEAKRe8j9QUqL4PDQSsliTKQ0yTkdLL8BFBm7c03RC9Ol5PP9K j/RtnsdxFMTtW7wkMwTpY1jF23HR+x54LrOpi8ig6HEmiXVVWuNByRjSMgz8jvrn MM0/tIOCPAgNMxiANUWqretPEWCZE9sLbylkJrrOd54ZKyXBTw/D7AL7u4qxAAUR tCFDb2xpbiBQbHVtYiA8Y29saW5Abnl4LmNzLmR1LmVkdT6JAJUCBRAtyxCUZXmE uMepZt0BAeiyA/4tNXz6loqEwyMv65TMGtqxTlT5ocGNzyE8mkZXvbmoS0m7sdsd aVBvHfK8lrkQz/anrzAHJMBOaZ0V6T7aCLAK6GnjHoeanP8ZyhaXpc2e7EVut4Zi hCpmq45uiA/1diwLXhC8OoHwKqZDT+uNnJLLdlAzrJiOaELAzXXeOvtMXokAYAIF EC3L/BnKPaH9hlqn8wEBXWgCWMgIh8Lsww5pFHRFbAe2HehjGIiOmQ+ZcnL3pOhw tLdoGm6lqWZ4njDSTULxDpKUtbe4pWNv6Go13t9p+1GmTh+RrnGoq6rs3Mlg+IkA lQIFEC3L+zgPw+wC+7uKsQEBDZkEAJYkHK5n02GXLwEEgFKpxQvWLqI2xz33rPDa 0eT6+RYMDcr/1vzTqX7CwNpCuTaFTVNRbRznvwNTDcQXVsnyPg5yGdRIIMPnWuGf gSEP7vjm8zzvfdh5te4ag6jobCN1PVyqIIxIV5S8iPv632gm4vQboJiQ+4+53qoS WJ6BNDq9 =Wjfi -----END PGP PUBLIC KEY BLOCK----- -----BEGIN PGP SIGNED MESSAGE----- I have the unpleasant task of reporting a significant bug in PGP's random number generation (for making primes), and that it's my fault. It *is* a significant problem, although it is *not* end-of-the-world severity. That is, the code is not doing performing as intended, and the results aren't as random as intended. On the other hand, this does not appear to make any generated keys easier to break. Because it has to do with random-number generation, there are no interoperability issues raised. Please read on for details. Thanks to the many people who have submitted other bug reports and porting patches. A new release from MIT is forthcoming with more cleanups. * The Bug In pgp 2.6 (and 2.5), there is a file named "randpool.c", which accumulates entropy from keyboard timings. These random numbers are used in generating session keys, although the primary random number generator for session keys, based on IDEA, is unaffected. The main use of these random numbers is the much more sensitive task of generating RSA secret keys. In that file, a tiny helper function is xorbytes: static void xorbytes(byte *dest, byte const *src, unsigned len) { while (len--) *dest++ = *src++; } A character is missing. '^', to be precise. That "=" should be "^=". I wrote it, and I knew when I was writing it that it was critical code. Since you can't test a random-number generator (except for the most trivial of flaws), you have to walk through the code very carefully. I did, or thought I did, yet still managed to miss this. Oops is too mild. That code is not supposed to have ANY bugs. In other words, I screwed up. There's a lesson in there somewhere. I'll try to learn it. * The Effect The randpool.c code works by maintaining a pool (buffer) of random bits and adding in new "noise" from the environment each time a key is pressed. This "adding" is done by exclusive-oring it with successive bytes from the existing pool. When the pool is "full", a cryptographic stirring operation is performed to mix all the information in the pool together and get ready for new noise. The bytes in the pool at the end are intended to be uncorrelated with the noise bytes that will be added, so the XOR adding does not cause any sort of "cancellation" of information. This stirring is done with a key, which is taken from the pool at the end of each pass. With the bug in place, the noise bytes *replace* the bytes in the pool rather than being added to them. So the information that was in the pool is obliterated. The only trace that remains is what's stored in the key. This is at most the size of the key, 512 bits, rather than the size of the whole pool, 3072 bits. PGP tries to ensure that generated RSA keys are completely unpredictable by accumulating enough Shannon information to make the whole key. Thus, infinite computational power would not let you predict a generated secret RSA key. This bug subverts that. * Security Analysis What effect does this have on someone's chances of breaking an RSA secret key generated with PGP 2.6? Not much, as far as I can tell. But it requires more careful thought and that eats into the comfort margin that should be there. Just for comparison, the RSAREF library's random number generation routines are also based on MD5, but use 16 bytes of seed. Successive random bytes are taken by computing the MD5 hash of the 16-byte seed, using those 16 bytes, incrementing the seed by 1 (taken as a 128-bit number), and repeating. Taking the MD5 of a 16-byte value involves one pass of the MD5Transform function, with 16 of the 64 key bytes unknown, 48 bytes are known (fixed, in fact), and the input hash is known (fixed, in fact). Compared to this, PGP 2.6, even with the bug, is excellent. All 64 bytes of key to MD5Transform are dependent on all of the seed, the input hash varies widely, and the output is XORed with some difficult-to-predict data. The reason that you can get away with less than perfect random numbers (less Shannon information than the size of the generated key) is that you only have to make sure that the weakness does not make any attack easier than the best known attack without the weakness. As long as guessing is only useful to a brute-force attack, it remains far easier to factor. Paul Leyland estimated that the work to try all possible 128-bit IDEA keys is equivalent to factoring a 3100-bit RSA key. Now, recent work by Arjen Lenstra on the number field sieve (Paul Leyland was assuming the MPQS used in RSA-129) has raised this RSA key length somewhat. Thus, an argument can be made in favour of RSAREF's use of a 128-bit random number seed, since that's all that is necessary. PGP prefers to be a little bit more paranoid. Still, once you have 512 bits of uncertainty, trying all possibilities is more work than trying to break a 1024-bit RSA key by trial division. So let's see just how much entropy is in there. Each keystroke, the following data is added to the random pool: - - The cahracter typed, an int (2 or 4 bytes) - - the time_t result of time() (4 bytes) - - the clock_t result of clock() (4 bytes) - - On MS-DOS, 2 bytes of hardware timer 0 - - On Unix, 8 bytes of gettimeofday() and 20 bytes of times() results - - On VMS, 8 bytes of high-resolution timer. The total is 12 bytes on MS-DOS, 32 bytes on Unix (this may vary, but that's very common), and 20 bytes on VMS. The information content of the bytes is taken at a maximum of 8 bits, although it's actually closer to 15 bits on MS-DOS, and less (maybe as low as 1 or 2) on a Unix system with a fast typist and a slow (60 Hz) clock. VMS is in between. This means that the entropy density in the added bytes varies from 1/12 (or better) in MS-DOS to 1/256 on Unix. Thus, the content of a pool's worth (3072 bits) is 256 bits (or more) under MS-DOS and may be as low as 12 bits on some flavours of Unix. The random number accumulation operation adds bytes to the pool until it is either full or the desired number of bits have been accumulated. Then it stors the pool. For a maximum-sized key (1024 bits), it will take many passes through the pool to accumulate the entropy, but owing to the bug, each time the pool is overwritten with the most recently collected data. The only entropy that remains from the previous pass is in the 512-bit key buffer. This applies to every stirring pass until the last, after the last noise data has been added and new data is about to be withdrawn from the pool. This last pass is very likely to be incomplete; some of the data at the tail of the pool is probably not overwritten. This can carry over extra entropy from the previous pass. No more than is there (the 12 to 256 bit range observed before), and then you have to add an unknown fraction of that for data that has been added in the current pass, but the total will vary from 12 bits (an average of 18) to 256 bits (an average of 384). Plus the entropy preserved in the key buffer. So there is from just over 512 to an average of 896 bits of entropy in the pool. 1016 random bits are used to make the starting values for the two primes in a 1024-bit key. This is clearly not the perfect Shannon entropy PGP aims for. As long as the stirring operation is still considered cryptographically strong, this reduction in the possible range of generated keys is not useful to a factoring algorithm, so it doesn't make a factoring attack any easier, yet a factoring attack is still far easier than a guessing attack, so the easiest attack is no easier. So I don't think anything is more attackable. Still, it's NOT what was intended, and that's always bad. My apologies to users of PGP. - -- -Colin -----BEGIN PGP SIGNATURE----- Version: 2.5 iQCVAgUBLeyVSw/D7AL7u4qxAQEjCQP/YlzY5DWT4FrSErQ8W0TP9ibRqpck4gKL YOkUgiMQnvCE2XHEvP1VTfUANgU9O/P7lClJ1oaOXIEbt5GW45DAVPgSZk5PoJ10 TZ5Ly4wqDzMa8YLDu4I2l2Use5wwIIYl5IbGEdZiRlYdox7eWaGRLfOiA8CPVb9p yZ7PgFZU10Y= =Bj83 -----END PGP SIGNATURE----- -- Ben.Goren(a)asu.edu, Arizona State University School of Music net.proselytizing (write for info): Protect your privacy; oppose Clipper. Voice concern over proposed Internet pricing schemes. Stamp out spamming. Finger ben(a)tux.music.asu.edu for PGP 2.3a public key.

1 0

Sue D. Nym
by merriman＠metronet.com 17 Dec '03

17 Dec '03

I trust that everyone got the joke: Sue D. Nym = pseudonym Dave Merriman Wherever you go in Life - there you are!

1 0