This section covers methods of distributing keys in ways that, without using public-key cryptography, reduce, without eliminating, the need to transport keys securely. In practice, of course, a layer of public-key cryptography could be used as an additional safeguard for the secure transmission of keys for these methods.
A set of cipher machines could each be given exactly half of the keys in a large set.
As long as no cipher machine is made that has exactly the opposite set of keys as another machine, any two cipher machines would be able to communicate.
Thus, for example, since there are 70 ways to choose four items from a group of eight, 35 cipher machines each of which was issued a different combination of four of eight possible keys could each share at least one key with each of the other cipher machines, if the 35 combinations used were the complements of the 35 combinations not used.
At least three cipher machines would need to be broken into to get the complete set of keys, but that means this protocol is not particularly resistant to collusion.
Note also that the set of keys shared between a pair of machines is not guaranteed to be unique, so some messages may be readable with the keys other machines have. In practice, this technique would also rely on the machines having tamper-proof hardware, not only to protect the keys, but to restrict their use to decoding appropriately-addressed messages.
This kind of technique is most applicable to the military environment. One way to facilitate this kind of restriction, and yet also have robust error-recovery, would be to use a stream cipher with a simple XOR combiner for the actual message, but to send the IV, together with addressee identification, enciphered in a mode involving propagation, with a heavy error-correction layer after encryption. In this way, a deciphering machine would only obtain the correct IV from a message intended for it; even without an internal checksum, matters could be arranged so that the keystream produced from a wrong IV would give no clue as to what the correct keystream would be.
For example:
Let a message be sent from machine:
01001110
to machine
11100100
and thus, the message is enciphered using the keys indicated by the AND of the two key vectors,
01000100
and the user of the machine whose key vector is:
11000110
seeks to surreptiously read the message. So he changes the unencrypted header to read:
From 01101100 to 11000110
instead of
From 01001110 to 11100100
If one enciphers an IV as follows:
then, assuming the keys remain protected by the tamper-proof hardware of the cipher machine, the decrypted IV will bear no relation to the intended IV if the machine is given wrong "from" and "to" bytes, or even if only the "to" byte is changed in the unencrypted header.
Of course, for some stream ciphers, using the same key but a different IV will result in different points in the same output sequence being generated, with a slight possibility of overlap. So appropriate choice of the stream cipher mode is also needed; for example, instead of counter (CTR) or output-feedback (OFB) modes, a combined counter and output-feedback mode where the output of a block cipher is then XORed with a counter before being fed back would be appropriate as a keystream generator.
A technique used in smartcards to allow them to work with limited computational resources inadequate for the use of public-key methods is known as the use of diversified keys.
Each smartcard might be issued a large number of pairs of blocks of the form:
( value(user,n), E( value(user,n), K(n) ) )
that is, each pair consists of one random block of data, and the encipherment of that block using one of a set of keys.
Each machine used to carry out transactions with a smartcard might be issued a subset of the keys.
Then, the protocol between the smartcard and the terminal could proceed as follows:
Since both can now use this common but secret value as an encryption key, the two devices can now authenticate themselves to each other.
The total number of keys in the system needs to be large enough, and the fraction given to each terminal small enough (but the number each terminal has large enough) that it is difficult for a number of colluding terminals to obtain enough keys to make smartcards that can fool other terminals.
The scheme can be made more elaborate by issuing the smartcards keys corresponding to block pairs held by the terminals as well. Because of the difference in resources, in this case each smartcard would be issued a very small fraction of a pool of possible keys that could be larger in size.
If a trusted authority is available, it is possible to use methods based on the principles examined above to allow members of a group to communicate with each other in pairs with a convenience similar to that afforded by public-key cryptography. Initially, each member must receive keys from the trusted authority over a secure channel.
One particular method for this proposed by Leighton and Micali somewhat resembles the way in which the Diffie-Hellman cipher operates.
With diversified keys, someone knowing A and E(A,K) can, revealing only A, communicate with someone who knows K.
Thus, one can have a group of K values, where members of one group of users have a complete set of ( A, E(A,K) ) pairs for all the different values of K, and the members of the other group have one or more of the possible K values.
In Leighton-Micali, a somewhat different approach is taken. For each of several key pools, let the keys have identities noted by small letters (a, b, c) and the keys themselves be noted by capital letters (A, B, C).
Thus, a and b are public, and in addition, for every pair of keys in each key pool, the value E(a,B) xor E(b,A) is public.
The user issued A can calculate E(b,A) and then use it to obtain E(a,B). The user issued B can calculate E(a,B) directly.
Multiple key pools are needed to avoid having to calculate an E(a,B) xor E(b,A) for every possible pair of users. Leighton and Micali also proposed having multiple trusted authorities, so that messages would not be readable by a single authority acting alone.
Various forms of the Leighton-Micali protocol are noted in the literature; one involves a table with pairs of entries of the form:
E( H(a,b), A ) E( H(a,b), B ) xor E( H(a,b), A ) xor E( b, B )
and with the use of H(a,b) as the shared secret key.
Another form involves a table with groups of three entries in the form:
E(a,B) xor E(b,A) E(E(a,B),A') E(E(b,A),B')
where A' and B' are additional secret keys known to A and B respectively, and used for authentication, to allow the users to verify that the E(a,B) xor E(b,A) entries in the table have not been tampered with. Although encryption is shown for ease of understanding, a keyed hash function is actually what was proposed for this form.
Flaws have been found in some forms of the Leighton-Micali scheme, particularly by Yuliang Zheng, who described them in a paper presented at Eurocrypt '98.
The basic idea of the original scheme, though, that the user A, knowing A and knowing b, c, d... z who could obtain E(a,B), E(a,C), E(a,D)... E(a,Z) from the table, and who could compute E(b,A), E(c,A), E(d,A)... E(z,A) would still be completely unable to derive E(m,N) for any two users M and N neither of whom is A, and therefore would not be able to read any communications not sent by or intended for him is sound.
Instead, the problems come in when one considers situations where there are a large number of users, so that the keys have to be split into key pools. In that case, if every possible combination of one key from each pool were assigned to some user, even two colluding users could read the communications of a large number of other users. Preventing this by using only a fraction of the possible key combinations is possible, but leads to a larger number of keys, which would be impractical for a large number of users. Tamper-proof hardware, of course, would eliminate the need to prevent this in that way. Note that this problem is not unique to Leighton-Micali, but is applicable to key-distribution schemes involving diversified keys or related techniques in general.
The paper by Yuliang Zheng, in addition to raising the objection above, noted a serious flaw in one variant of the Leighton-Micali scheme, in which a user was identified by a sequence of numbers N1, N2, N3... and was given as a secret key the sequence K1 hashed N1 times, K2 hashed N2 times, K3 hashed N3 times, and so on. The session key between two users would simply be composed of K1 hashed the greater of the first user's N1 and the second user's N1 times and so on.
With tamper-proof hardware available, Yuliang Zheng proposed as a simple alternative using H(X,a,b) as the session key between users A and B, where X is a secret value, and there is an ordering of the identities a, b such that a consistent convention of putting one user's identity first is possible. He noted that the identities must be prefix-free, so that H(X,a,b) cannot be equal to H(X,c,d) where simple concatenation of the inputs is used to form the input to the hash function, but that condition is met trivially if all the identities are the same length, as would tend to be the usual case (and would thus tend to be implicitly assumed, which, of course, can be dangerous).
It would seem to me that one could safely drop the requirement of an ordering by using H(X,a,b) xor H(X,b,a).
Note, too, that if one defines a multiple-argument hash
HM(x,y,z)
as
H(3|H(x)|H(y)|H(z)|x|y|z)
where the vertical bar represents concatenation, one has a definition for a multi-argument hash-function which avoids problems of the string of arguments being identical to the concatenation of a different string of arguments. The 3 at the beginning, of course, represents the number of arguments, and it is intended for the definition to be generalized.
Note that the multi-argument hash is noted as HM and not as H, so as to make it unambiguous that HM(x) = H(1|H(x)|x) to avoid the possibility of constructing single-argument inputs that produce collisions.
Also, it is required to deal with the field giving the number of arguments; three common alternatives for doing what is required are:
The first and second alternatives have the disadvantage of imposing a finite limit (although in the second case, one that is enormously large) on the numbers represented, the third involves a continuing inefficiency throughout the whole representation of the number of excluding at least the value of the terminating symbol from the possible digits used.
For such purposes as Gödel-numbering, if not for any practical purpose, it may be noted that these disadvantages may be avoided by combining the two approaches.
First, the number of levels may be encoded in decimal digits (or even base-15 digits) terminated with 1111.
If the number of levels is 0, then the number being represented itself is given in the next byte, as a pure binary value.
If the number of levels is 1, then the next byte gives the number of bytes in the number itself, which follows.
If the number of levels is 2, then the next byte gives the number of bytes in the next field, which then gives the number of bytes in the number itself.
And so on and so forth, with only the first field, which indicates the number of levels, not being in pure binary form.