SECRET THE POSSIBILITY OF SECURE DIGITAL Hepun Nu SECRET SECRET E E S G NU 3DDE THE PESSIEILITY DF SECURE NUHHEECRET DIGITAL J H Ellie Summary This report ccnsiders the problem cf achieving secure cf digital infermeticn in the circumstances where there is nc informaticn initially possessed in by the tee legitimate communicators Which is not also tc the interceptor It demen- by means cf mcdel having the required prepar- ties that theoretical seluticn exists but nes not establish that system can be devise Ease refers Date cf fer issue January SECRET SECRET INPRUDUCTIDH 0F NON-SEGRET A HODEL PGSSIBILITY DF In PRACTICAL HDDEL 101E ATTAEHEIJ Drawing No 352mm SECRET PAGE 15 SECRET Introduction 1 It is generally regarded as self-evident that in order to present an interceptor from understanding a message which is intelligible to the authorised recipient it is necessary to have some initial information known to the sender and to the recipient but kept secret from the interceptor This information can take many forms such as the method of encipherment itself the construction of a cipher machine a key setting or a one-time tape All these methods require that there is a route by which this secret information can be sent without fear of interception only then can the cipher test he sent safely in a non- secret manner and large quantities of cipher text of high security thus tend to need the parallel transmission of smaller but still substantial quantities of secret information 2 This report demonstrates that this secret information is not theoretically necessary and that in principle secure messages can he sent even though the method of encipherment and all transmissions between the authorised communicators are known to the interceptor This is what is meant by non-secret It must be emphasised however that this demonstration has only the status of an existence theorem It shows only that such a system is theoretically possible and not that a practical form exists The demonstration consists of showing that a particular but unfortunately as yet highly impractical system has the desired properties This is followed by an heuristic discussion nhich attempts to establish the necessary properties of a system and indicate the likely form of a practical solution 5 he the title indicates we are concerned here with digital trans mission Analogue systems have essentially different properties and possibilities with regard to nonesecret encipherment and they will be diacussed only as one illustrative example in the following section SECRET SECRET Possibility of Hen Eecrct In what follows the originator of the message will he referred to es the sender the authorised recipient as the recipient and the unauthorised interceptor as the interceptor 5- It seems apparent that the recipient oust he in a special position with respect to the interceptor to enable him to understand the message and as they are both essence to knew the cipher test equally this would seem to imply that the recipient has some knowledge denied to the interceptorll also that this knowledge must he shared with the sender otherwise how could it he put to use ht first sight the idea that the recipient night he in the necessary special position Just because he was the authorised recipient seems impossible- Hewerer consider the following 5 An ingenious scheme intended for the eneipherment of speech over short metallic connections was proposed hp Bell Telephone Laboratories Ref 1 in which the recipient adds noise to the line over which he receives the signal If this noise is sufficiently large compared with the message it can effectively disguise it The recipient however can subtract the noise from the signal he receives and so obtain the original message This method has obvious disadvantages and limitations which are irrelevant to this discussionI but it has an important property if the interoeptor were provided with a receiver identical with that of the recipient and connected to the same point on the line then the two terminals would be identical for all practical purposes and could be interchanged without altering the situation Nevertheless the interceptor would not he able to read the message as he would not know the noise which had to be subtracted from the line signal Thus this system fulfils the condition which was discussed above that the recipient is able to decipher the message because he is the authorised recipient and not because of any SECRET SECRET special physical position or prior secret knowledge Clearly should the interceptor try to usurp this authority by adding his own noise to the line all that he will succeed in doing will be to block the message from the genuine recipientll revealing his own presence without acquiring any information Because such a system exists we know that the required property is not an impossibility and we can now try to devise a useful system which possesses it In the added noise scheme the receiver has information not known to the interceptor namely the exact form of the noise which has been added but this has been generated by the recipient and is not known to the sender or anyone else The reason that the recipient is able to use this knowledge is that he takes an active part in the encipherment process and his special position is due to this fact In the nature of things the interceptor cannot take an active part in any communication system without actually posing as the recipient and also ensuring that the recipient is not himself participating S The above system is essentially analogue and the questi GT whether or not it can he developed into a useful technique is outside the scope of this paper The problem with which we are now concerned is that of trying to find a digital system which is non-secret It is implied by the ferae ine discussion that it is necessary for the recipient to take an active part in the eneipherment process and as the only connection we can assume between the sender and the recipient is the ability to pass digital information this participation by the recipient must consist of sending digits to the sender We shall now describe a theoretical model of a systEm which has these properties SECRET 5' Theer tieal edel 9 First we shall gensralise the idea of a cipher machine Essentially a cipher maehine er ether eneipherment precess can be regarded as a device Which takes an input key tent setting etc and Pr dunEE an eutput frem it If there is en randen element in the machine then the eutput is defined by the input- Thus we can regard eur manhins as leehrup table containing ene value cf eutput fer each possible input value Here an 1'input value means a eenplete set ef data necessary te define the value of the eutput it may be in the fenm ef a setting and serial tent er ef any ether fern OftenI hut net necessarilyII the eutput defines the input he the input may eensist ef data sf mere than ene type we can eensider the maehine as a ene-dimenaienal er multidimensienal table as is neat convenient Fer instanee if a mashine uses bits ef message and hits cf key te ehtain 10 hits ef cipher text this could equally well be regarded as a table with 220D pessible input values er as a tee- dimensienal table with tee sets ef inputs each of E1UG different possibilities Clearly here is ne essential difference in these ten views whieh eerreapend merely te envisaging the table arranged as a square 5 5 B column 1D In regarding cipher machines as leek-up tables there isI ef ceurse ne suggesticn that they sheuld have a physical Perm ef this kind The table is merely a general methed of defining the eperatien ef a mashine nitheut having to eensider its internal wnrhing and it is see nhieh can he applied te any machine er system clearly a table can he fermed for any given machine by enumeratien and eenversely a maehine eeuld in principle be censtrueted tn repreduee the results ef any given table Indeed the table itself if actually repreduced weuld eenstitute a cipher machine Thus if a table can he sheen tn he pessihle with certain preperties then a machine with these preperties is pessihle 11 Per brevity we shall call ene-dimensienal tables linear I and twe- dimenaienal tables rectangular er square if the sides are equal SECRET SECRET The output value of a machine whose inputs have values 1 y will be written H x y s The terms output and 1 input will be used to include output value and input value where it is felt that no confusion will arise 12 We can not describe the proposed system and a block diagram is shown in Figure 1 The sender has a message which he wishes to transmit Securelf t0 the recipient The recipient generates a random key which he enciphers by means of the machine H1 forming the enciphered hey a The sender uses and ME to eneipher to form the eneiphered message 2 Finally the recipient uses and to decipher and so obtain p 13 The following properties are clearly essential It must be impossible for the interceptor to obtain from a without knowing even though he knows I AlsoI since a knowledge of would enable him to decipher a he must be unable to obtain from x Finally 3 must have the property of being able to decipher c To obtain these properties we specify the loch up tables corresponding to H1 H2 and in the following Let have different possible values and here different possible values for simplicity take them to he the integers 1 to and 1 to respectively Let have the same range of values as k and have the same range as p H1 can be defined as a linear look-up table of entries whose contents are the numbers 1 to in a random order where random implies that the output is sufficiently uncorrelated with the input so that the position of a particular entry in the table cannot be found in a simpler way than by searching through the tablet H2 corresponds to an by rectangular table in which the entries for a fixed value of consists of the numbers 1 to in random order and where the columns for the various values of are suitable uncorrelated with one another- SECRET SECRET is an by table in which each entry is the value of corresponding to the values of and which locate it In other words the column of H3 is obtained from the column of H2 hy making the entry in the h column the address of the number in the H2 column This is sheen in Figure 2 1a It is evident that this process gives the recipient the message Now consider the position of the interceptor he has the values of and and the details of H2 This means that he has ensugh information to define p for he has only to search column of IE to find the entry in order to establish 9 However this column has entries inrandom order snd so he would need to make a search cf these values since we have defined random to imply just this is thus the work faster in this form of attack and as is 2100 far a 100 hit message shout 2G letters this factor can easily be made adequately large Similarly the work factor in obtaining from is n which can also he made large It is clear from the random nature of the tables that there is as simpler attach thus we have shown that the system can be guaranteed to have a work factor which is the smaller of and n both of which can easily be made amply large This is in spite of the feet that details of all machines are known to the interceptor who may be supposed to have copies of them and that no pricr secret information is held in common hy the sender and the recipient Thus the system satisfies our requirements 15 This may seem a specious argument on the grounds that the effort of makingj say Ei trials is regarded as prohibitive for the interceptor Ihile the making of a device containing 220G entries is accepted for the authorised communicator However there is no suggestion that this is a proof that auch a system can he made I certainly not that a practical machine would be constructed in the form of a look-up table The SECRET SECRET argument is that the operation of a machine is defined by its equivalent look-up table and that if a system eith a look-up table defined in a certain non-contradictory way has certain properties than there is a hope that a real system can be devised having these properties All that has been proved is that a theoretical system having such properties exists and clearly there is an enormous number of Functions which would satisfy such a system PossibilitI_of a Practical Mode 16 To help us assess the probability of being able to devise a practical model we shall examine two questions seu1s a practioal model be similar to the theoretical one and secondly Gan machines having the essential properties of H1 H2 and can be devised To answer the first question let us return to the basic problemll which is that we have a situation in which the sender and the recipient have some form of cipher machine whose details are known to the inter who also has full knowledge of all traffic which passes between them but where the sender needs to send a message to the recipient without the interceptor being able to read it It is clear that the recipient must introduce some random element into his transmissions otherwise they would be entirely predictable and serve no useful purpose The sender map or may not produce some random contribution but there is no indication of the need for this The interchange could cansist Of a continuous dialogue or simply a block of data sent by the recipient and replied to by the sender 13 Some properties of the system can be deduced en exhaustion attack is always possible SECRET SECRET 19 Since the message must be uniquely decipherableII only one message can correspond to the signals transmitted Therefore any message including any random element which may be included in the sender's process which when combined with the recipient's signals gives the sender's signals must be the correct one Hence an exhaustion attack by trying all possible messages will always succeed In this case Messages includes any random element although the random element need not of course I be deoipherable In what follows the word message 111 Blwaf thie meaning as a random element could always be added to the message and although the fact that the random element does not need to be deciphcrable could be of importance in a practical case it does not effect arguments of the present paper Therefore we shall neglect the possibility of the sender using a random element EU In a similar way an exhaustion attack is always possible with the random element used by the recipient which we shall call the key From this it clearly follows that The maximum possible work factor of the system is the smaller of the number of different possible messages and the number of different possible keys 21 These facts establish that it is important that the message and keys are each used in large blocks to obtain security and it does not seem practicable to perform the interchange between sender and recipient in dialogue of less than block length as the initial exchanges would depend on less message and key and would thus provide a weakness This latter point is clearly not strictly true but as the encipherment must be based essentially on long blocks the dialogue idea will not be further considered It is also impossible to improve the security by making the message of the form of a random number such as a key-setting This is unfortunate as one very profitable use for such a system would be remote key setting However the work factors obtainable from moderate SECRET w- SECRET of message can he very large It is also evident that stylised messages must he padded with random material since complete cribs can be readily tested 22 In operating this system both sender and recipient will produce cipher test using either message or key in conjunction with data which has been received from the other and is thus known to the interceptor Clearly it is essential that the interceptor cannot work backwards and find the message or key and so in this sense we have The enoipherment must he irreversible 25 These results indicate that a system will be essentially of the form where the sender has a message of a standard length which is long enough to defeat an exhaustion attack say upwards of 190 bits and the recipient generates a similar length of random key The recipient enciphers the key by some process and sends the result which we will call enciphered key to the sender who uses it in turn to enoipher the message to form an enoiphered message which he transmits to the recipient Finally the recipient must use his original key to decipher the message This is the system illustrated in Figure l and thus we imply an affinmative answer to the first question of Paragraph 16 it To answer the second question let us look rather more closely at the general properties of cipher machines 25 In the case of a linear machine there is one output for each input and if these outputs are all different from one another then the input is defined by the output and we will say that in this case the machine is defined The less correlation there is between input and output the better the will he Intuitively one would say that ideally the output should depend on the input in a random manner but SECRET SECRET as the input-output relationship is firedll and any relationship is possible in a random choice we will say that the machine is random if the input cannot be correlated with the output in any way which is simpler than by enumeration We shall not attempt to define simple There will he degrees of randomness which will depend on the ingenuity of the cipher maohine construction in a practical case in the same way that the stream of key from a good key generator is apparently random although produced according to a relatively simple law also in practice it will be necessary for the output to he produced from the input by some means other than enumeration We shall therefore replace the concept of randomness by that of Irreversibility a linear machine will be regarded as perfectly irreversible if no way of obtaining the input from a given output could he found which is simpler than enumeration and satisfactorily irreversible if no way can be found which has a work factor smaller than that which is regarded as acceptable It follows that a random machine is also irreversible a machine which is both irreversible and defined we shall call ideal 26 We may extend these definitions to include higher dimensions as follows - a machine is irreversible with respect to an input if for any given set of values of the other inputs there exists no way of deriving the input value from a given output value which is simpler than by enumeration of the values of the input a machine is defined with respect to a given input if for any fixed set of values of the other inputs there is a different value of the output for each different value of the input A machine is ideal with respect to an input if it is both irreversible and defined with respect to that input SECRET SECRET If when the output of a certain linear machine is used as the input of another linear machine the output of the second Machine is always the same as the input to the first we shall say that the second machine is the inverse of the first Clearly if the inputs and outputs have the same range or vulnes the first machine is also the inverse of the second a pair of rectangular machines each of which has a fixed value applied to one input could be inverse in this way M2 and Hi It is clear that for any defined machine there exists a possible inverse although the inverse of an ideal machine would have to he produced by enumeration 23 we can now say that H1 is an ideal linear machine that H2 is a rectangular machine ideal with respect to the input and that is a rectangular machine which is the inverse of H2when is fed with l and H2 with a H1 k 29 There is no problem in devising an ideal linear machine Any good key generator with the settings regarded as the input and the key as output is a good enough approximation to this Similarly there is no problem in making an ideal hut When we add the requirement of the existence of a practical we meet difficulties there appears to he a contradiction in the requirement for H2 to be ideal and to have an inverse This would be a genuine impossibility for a linear machine for our definition of irreversibility requires that there shall be no way of obtaining the input from a given output which is simpler than enumeration a suitable work factor would by definition preclude enumeration and so the existence of an inverse machine would establish that the first was reversible In the case of a rectangular machine however it is possible for it to be irreversible with respect to one input and yet still have a machine which is its inverse for that input under certain conditions This is hocause it is irreversible given the output and the other input not for a fixed value of the other input Thus in the case of H2 it could be reversible with respect to for each fixed SECRET it SECRET value of x in the sense that fer every value of there exists a linear machine which is the inverse cf H2 for that particular 1 input hut if the search fer the particular Machine cerreepending te a given input invelves enumeration ccmparable tc that ef enumerating then H2 is still irreversible with respect to p In ether nerds a multidimeneicnal machine can he irreversible with respect to an input even thcugh the linear machines farmed frem it by fixing the values cf the ether inputs are reversible in Receiving this apparent centrasictien has demenstrated the real prehlem cf designing H2 which is that cf preducing a rectangular machine which is ideal with respect te but where the linear machines formed by fixing the 3 input are reversible 31 Tue pessihle methods of selving this preblem seem plausible The first is te make H2 seme cf reflex precess a linear irreversible machine in such a way that the inverse precess invelves the input tc this machine I but where the encipherment can he dens using help the eutput in ether nerds the input is never used directly in the encipherment precessII only via the machine The machine could then beecme Hi and the required preperties cf 2 fallen A selutien of this weuld he very useful as it would enable any cenvenient type cf key- generator te he used fer H1 Hewever such a seluticn may preve te he essentially impossible The ether appreaeh is to find a precess in which finding the inverse depends en hnneing the value of an inverse funeticn cf same value used in the process The funetien in questicn then hecemes H1 This wculd depend en special preperties at particular functions 32 Attempts to find selutiens in this way have as far been unsuccessful but have seemed tantalisingly near to success at times as that one feels that a selutien prehahlp ees exist There is certainly no apparent reasen te believe it impessihle SECR ET 11 SECRET Bunclusicns 35 In assessing the implicaticns cf the shave arguments it is necessary tc distinguish carefully between fact and cpinicnI i e between that which has actually been prayed and that which seems likely It is particularly difficult tc dc this in this case because we haye established semething which to meet pecpleII seems inherently ur tacit assumptions and inferences have therefcre tc he watched with particular care it that has been sheen rigorously is that a digital system in which an secret is shared by the sender and recipient is thecretiw cally plausible at this the cf the assumpticn that the sender and the recipient must share secret infernaticn fer any secure communica tinn tc be possible is the majcr step and this is achieved by ccneidera tien cf the system in which the recipient adds ncise tn the line The cf the digital system adds little definite tc cur since it dces net shew that it can he dens only that it is thecretically pcssihle in the digital case there are some indirect advantages which may be attained ccnsideraticn cf the digital system It seems likely that many pecple scald assume in the absence cf evidence that the properties cf the enelcgue system were dependent entirely en the physical ccnditiens prevailing in it and se wculd ccnsider a study cf a system using digital transmissicn Herth- while Hcrecyer it is pcssible that the heuristic discussion centained in the prericus sectien may indicate the necessary cf practical fulfilment 1 altheugh assumptions made an this basis should he scrutinised carefully as the arguments are by no means rigereus 55 Anether petential a tnntage to be obtained the theereticsl system is that it cculd preside a ccunternexample cf a tentative hype- thesis The practical realisaticn cf a nun-secret digital scheme depends SECRET t SECRET ef eeuree on there net being meme heeie theerem whieh ferhide it hug ptetuleted theerem hieh furbede the theoretical existence ef the eyetem praenntad leuld thue be untenable and net eerth pursuing Thin me he mere then et firet likely ee the only apparent die- ldmtege of the eyetem it the enormous end eoet end if eeunter theereme are to he limited te this eepeet then the ultimate is raised substantially eheve that which would preveil if any eert ef theeretieel limitetien were 35 A eeneideretien whieh eneeuregee belief in the exietenee ef a practical eelutien ie that the number of different functions whieh eetie y the eenditiene fer the leek-up tehlee ef H1 end ie eleerly and enly the eet capable If practical generatien is needed Thin in net te any of eeuree that eelutien ef the prehlem et all imminent Even if there ie an fundamentel diffieulty we knew that the gap between ehewing eemething te he which we have net yet dune enly thet it may he end eetuellr doing it he immenee It me he that the heat Hey te eentinue thie etudy ie te prepertiee fer the functiehe H1 H2 end eueh ee fer example er permutetien end nee that een be preved ee eeneeqpenee Thin may nerve te eerrew the whet field ef funetiene whith exiete et end mekee rendem imprectieehle In any it 13 that thin r p rt will stimulate prefieient in these matters to find preetieel eelutien The petentiel e ventegee ere tee eh'l'inu te need epeeifieetien Finel repert en prejeet 3 5 Bell Telephehe Liberateryy eteher 19% p 25 SECRET GRGUF In Ui- - DIGITAL SECRET 3539 SYSTEM HESEAGE 2 EHEIPHEHEP HEESABE M3 DECIPHEHED MESSAGE EGMMUHICATIDHS SEEUHITY I mum DATE IISSUE ENDM-ENT PAH TICULAFLS RR ame 'v-l 5 1 DIP-H 33- cm E51 APPLE DATE 11 MI SECRET SENDEH i RECIPIENT FIGTh SENDEFI RECIPIENT FIG 3