Cryptography: Difference between revisions

Revision as of 10:23, 13 June 2003

Revision as of 20:23, 14 June 2003

Line 7:

Cryptography has four main goals, though they are nearly always concealed beneath a blanket of marketing speak in commercial products. Examining any proposed crypto system with these in mind, and ignoring the marketing blather, will be a very useful exercise in the real world. They are:

# message ''confidentiality:'' Only the authorised recipient should be able to extract the contents of the message from its encrypted form. In addition, it should not be possible to obtain information about the message contents (such as a statistical distribution of certain characters) as this makes cryptanalysis easier.

# message ''integrity:'' The recipient should be able to determine if the message has been altered during transmission.

Line 19:

:1) a computer program on a local system,

:2) a computer program on a 'nearby' system which 'provides security services' for users on other nearby systems,

:3) or -- what most people assume is "obviously" meant -- a human being using some computer system. Even in this case, the human doesn't not actually encrypt or sign or decrypt or authenticate anything. At most, when all is right in the world, the user instructs a computer program to encrypt or sign or ... This buffering of human action from actions which are thought to have 'been done by a human' is a source of problems in crypto system design and implementation. Such problems are generally quite subtle and correspondingly obscure. Often, even to practicing cryptographers.

:3) or -- what most people assume is "obviously" meant -- a human being using some computer system.

When confusion on these points is present (at the design stage, during implementation, or by a user), unintended failures in reaching each of the stated goals can occur quite easily, often without notice to any human involved, and even given perfect algorithms, superb and provably secure system design, and error free implementation. Such failures are most often due to extra-cryptographic issues; each such failure demonstrates that good algorithms and good protocols alone do not provide 'security'. Instead, careful thought is required regarding the entire system design -- and too often, this is absent in practice with real-world crypto systems.

Although cryptography has a long and complex history, it wasn't until the [[19th century]] that it developed anything more than ad hoc approaches to either [[cryptanalysis]] (eg, [[Charles Babbage]]'s Crimean War era work on mathematical cryptanalysis of polyalphabetic cyphers, repeated publicly rather later by the Prussian Kasiski) or encryption (eg, [[Auguste Kerckhoffs]]' writings in the later 19th century). An increasingly mathematically theoretical trend accelerated up to [[World War II]] (notably in [[William F. Friedman]]'s application of statistical techniques to cryptography and in [[Marian Rejewski]]'s initial break into the German Army's version of the [[Enigma]] system);. bothBoth cryptography and cryptanalysis have become far more mathematical since WWII. Even then, it has taken widely available computers, and the [[Internet]], to bring effective cryptography into common use by anyone other than national governments or similarly sized enterprises.

== Classical Cryptography ==

Line 29:

The earliest known use of cryptography is found in non-standard [[hieroglyphics]] on monuments from Egypt's Old Kingdom (ca 4000 years ago). These are not thought to be serious attempts at secret communications, however, but rather attempts at mystery, intrigue, or even amusement for literate onlookers. Each of which has been, intermittently, still another use of cryptography, or of something that looks (impressively if misleadingly) like it. Later, [[Hebrew]] scholars made use of simple [[substitution ciphers]] (such as the [[Atbash cipher]]) beginning perhaps around 500 to 600 BCE. Cryptography has a long tradition in religious writing likely to offend the dominant culture or political authorities. Perhaps the most famous is the 'Number of the Beast' from the book of Revelations in the Christian New Testament. 666 is almost certainly a cryptographic (ie, coded) way of concealing a dangerous reference; most scholars believe it's a way of referring to Rome (and so to Roman policies of persecution) that would be understood by the initiated (who 'had the codebook') and yet be safe (or less dangerous) if it came to the attention of those authorities. At least for orthodox Christian writing, the need for such concealment ended with Constantine's conversion.

The classical Greeks are said to have known of cyphers (eg, the [[scytale]] transposition cypher said to have been used by the Spartan military). Herodutus tells us of secret messages physically concealed beneath wax on wooden tablets or as a tattoo on a slave's head concealed by regrown hair. The Romans certainly did (eg, the [[Caesar cipher]] and its variations). There is mention of a book about Roman military cryptography (especially Julius Caesar's); it has been, unfortunately, lost. Cryptography became (secretly) important still later as a consequence of political competition and religous analysis. For instance, in Europe during and after the Renaissance, citizens of the various Italian states, most specifically including the Papacy, were responsible for substantial improvements in cryptographic practice (eg, polyalphabetic cyphers by [[Leon Alberti]]). And in the Arab world, textual analysis of the Koran led to the invention of the letter frequency counting technique for breaking monoalphabetic substitution cyphers around 1000 CE.

Both cryptography, [[cryptanalysis]], and secret agent betrayal featured in the [[Babington plot]] during the reign of Queen [[Elizabeth I]]. And an encrypted message from the time of the Man in the Iron Mask (decrypted around 1900 by [[Étienne Bazeries]]) has shed some, regrettably non-definitive, light on the identity of that legendary, and unfortunate, prisoner. Cryptography, and its misuse, was involved in the plotting which led to the execution of [[Mata Hari]] and even more reprehensibly in the travesty which led to [[Dreyfus affair|Dreyfus' conviction]] and imprisonment, both in the early [[20th century]]. Fortunately, cryptographers were also involved in setting Dreyfus free; Mata Hari, in contrast, was shot.

Mathematical cryptography leapt ahead (mostly secretly) ahead after [[World War I]]. Marian Rejewski, in [[Poland]], attacked and 'broke' the early German Army Enigma system (an electromechanical rotor cypher machine) using purely mathematical techniques in ([[1932]] and up to '39). His work was extended by [[Alan Turing]], Gordon Welchman, and others at [[Bletchley Park]] beginning in [[1939]], leading to sustained breaks into several other of the Enigma variants and their assorted networks. [[US Navy]] cryptographers (with help from the British and the Dutch after 1940) broke into several [[Japanese Navy]] crypto systems. The break into one of them famously led to the US victory in the [[Battle of Midway]]. A US Army group, the [[SIS]], managed to break the highest security Japanese diplomatic cypher system (aan electromechanical 'stepping switch' machine called [[Purple code|Purple]] by the Americans) before WWII began. The Americans referred to the intelligence resulting from cryptanalysis, perhaps especially that from the Purple machine, as '[[Magic]]'. The British eventually settled on '[[Ultra]]' for intelligence resulting from cryptanalysis, particularly that from message traffic enciphered by the various Enigmas. An earlier British term had been 'Boniface'.

=== World War II Cryptography ===

Line 39:

By [[World War II]] mechanical and electromechanical cryptographic machines were in wide use, although where these were impractical manual systems were still used. Great advances were made in both practical and mathematical cryptography in this period, all in secrecy. Some information about this period has begun to be declassified in recent years as the official 50-year (British) secrecy period has come to an end, and as the relevant US have slowly opened.

The Germans made heavy use (in several variants) of an electromechanical rotor system known as [[Enigma]], the Japanese Foreign Office used the independently developed electrical stepping switch based system called Purple by the US, and also used several similar machines for attaches in some Japanese embassies. One of these was called the 'M-machine' by the US, another was referred to as 'Red'. All were broken, to one degree or another by the Allies. Other cypher machines used in WWII included the British Type X and the American SIGABA; both were electromechanical rotor designs similar in spirit to the Enigma. Neither is known to have been broken by anyone.

=== Modern Cryptography ===

Line 45:

The era of modern cryptographic theory started with [[Claude Shannon]], arguably the father of mathematical cryptography. In [[1949]] he published the paper [http://www3.edgenet.net/dcowley/docs.html Communication Theory of Secrecy Systems] in the Bell System Technical Journal and a little later the book, Mathematical Theory of Communication, with Warren Weaver. These, in addition to his other works on [[information theory|information and communication theory]] established a strong theoretical basis for cryptography.

[[1976]] saw two major public (ie, non-secret!) advances. First was the [[DES]] (Data Encryption Standard) developed by [[IBM]], with 'advice' and modification by the [[NSA]]submitted, at the invitation of the National Bureau of Standards (now NIST), by [[IBM]] in an effort to develop secure electronic communication facilities for businesses such as banks. DESIt was lateradopted, after 'advice' and modification by the [[NSA]]. DES was published as a [[FIPS]] (Federal Information Processing Standard) in [[1977]] (currently at FIPS 46-3), and has been made effectively obsolete by the adoption of the Advanced Encryption Standard, also a NIST project, as FIPS 197. DES was the first cipher algorithm accessible to the public 'blessed' by a national crypto agency such as NSA. The release of the specifications of the DES algorithm by NBS (now NIST) stimulated an explosion of public and academic interest in cryptography. DES and more secure variants of it (such as [[3DES]], see FIPS 46-3) are still used today, although DES was officially supplanted by [[AES]] (Advanced Encryption Standard) in [[2001]] when NIST announced the selection of Rinjdael, by two Belgian cryptographers. It remains in wide use nonetheless, having been incorporated into many national and organizational standards. However, it has been broken (by the [[Electronic Frontier Foundation]], a cyber civil rights group -- the story is in ''Cracking DES'', published by O'Reilly and Associates).

Secondly, and even more importantly, was the publication of the paper [http://citeseer.nj.nec.com/340126.html New Directions in Cryptography] by [[Whitfield Diffie]] and [[Martin Hellman]]. This paper introduced a radically new method of distributing cryptographic keys, known as asymmetric key cryptography. This essentially solved one of the fundamental problems of cryptography, key distribution.

Prior to this, all useful modern encryption algorithms had been [[symmetric key algorithm]]s, in which the same [[cryptographic key]] must beis used with the underlying algorithm by both the sender and the recipient. All of the electromechanical machines used in WWII were of this logical class, as were the Caesar and Atbash cyphers and essentially all crypto systems throughout history;. theThe 'key' for a code is, of course, the codebook, which must be distributed and kept secret. Of necessity, a key in suchany asuch system had to be exchanged between the communicating parties in some secure way prior to any use of the system -- the term usually used is 'via a secure channel') such as a trustworthy courier with a briefcase handcuffed to a wrist or face-to-face contact -- prior to any use of the system. This requirement rapidly becomes unmanageable when the number of participants increases beyond some small number, or when (really) secure channels aren't available for key exchange. In particular, a separate key is required for each communicating pair if other parties are not to be able to decrypt their messages. A system of this kind is also known as a [[private key]], secret key, or conventional key cryptosystem.

In contrast, in [[asymmetric key algorithm|asymmetric key]] cryptography, there is a pair of mathematically related keys for the algorithm, one of which is used for encryption and the other for decryption. Some of these algorithms have the additional property that one of the keys may be made public since the other cannot be (by any currently known method) deduced from the 'public' key. The other key in these systems is kept secret and is usually called the 'private' key. An algorithm of this kind is known as a [[public key / private key algorithm]], although the term [[asymmetric key cryptography]] is preferred by those who wish to avoid the ambiguity of using that term for all such algorithms and to stress that there are two distinct keys with different secrecy requirements.

As a result, only one key pair is now needed per recipient (regardless of number of senders) as possession of a public key (by anyone whatsoever) does not compromise the 'security' of the algorithm so long as the corresponding private key is not known to any attacker (effectively this means not known to anyone except the sender). Note, however, that it has NOT been proven, for any of the good public/private asymmetric key algorithms, that a private key cannot be deduced from a public key (or vice versa). Informed observers believe it to be currently impossible (and perhaps forever impossible) for the 'good' algorithms, however;. and noNo workable deduction techniques have been publicly shown for any of them. Some asymmetric key algorithms have quite thoroughly broken, just as many symmetric key algorithms have; there is no special magic attached to using two keys.

Nevertheless, some of the well respected, and widely used, public key / private key algorithms can be broken by one or another cryptanalytic attack and so, like most encryption algorithms, the protocols within which they are used must be chosen and implemented carefully. _All_ of them can be broken if the key length used is short enough to permit practical brute force key search; indeed this is true of all encryption algorithms using keys, regardless of class.

Line 59:

This is an example of the fundamental problem for those who wish to keep their communications secure; they must choose a crypto system (algorithms + protocols + operation) that resists all attack from any attacker. There being no way to know who those attackers might be, nor what resources they might be able to deploy, nor what advances in cryptanalysis (or its associated mathematics) might in future occur, users may ONLY do the best they know how, and then hope. In practice, for well designed / implemented / used crypto systems, this is believed to be enough, possibly even for all(?) future attackers. Distinguishing between well designed / implemented / used crypto systems and crypto trash is another, quite difficult, problem for those who are not themselves expert cryptographers. It is even quite difficult for those who are.

Both asymmetric key cryptography and the best known of the public key / private key algorithms (ie, what is usually called the RSA algorithm) seem to have been developed by a UK intelligence agency before the public announcement in '76. [[GCHQ]] has released documents claiming that they had developed public key cryptography before the publication of Diffie and Hellman's paper. Various classified papers were written during the [[1960s]] and [[1970s]] which eventually led to schemes essentially identical to [[RSA]] encryption and to [[Diffie-Hellman]] key exchange in [[1973]] and [[1974]]. Some of these have now been published, and the inventors (James Ellis, Clifford Cocks, and Malcolm Williamson) have made public (some of) their work.

==Some algorithms of various kinds==

Line 107:

== Further Reading ==

* General note on cryptographic references: There is a great amount of myth and misunderstanding in wide circulation about topics cryptographic. Some is grossly wrong, some is 'merely' subtley misleading. There is also a very great selection of poorly done, non-secure crytographic software on the market (purchaseware, shareware, freeware, xyzware). Readers and buyers should exercise substantially more than the usual caution lest they lose one, two, or all of the reasons they have bothered with cryptography at all (see the article above for the goals of cryptography use). At the time this sentence was written, each of the following references is reliable -- mostly. Consider that none covers up_to_date secret cryptography (at minimum, publishing schedules do not permit it) and so much may be missing. All of this may produce considerable distortions in your understanding of the current state of the art in cryptography, but try these references first if you wish to minimize those distortions.

* [http://www.murky.org/cryptography/index.shtml The Beginner's Guide to Cryptography] - This website gives ana (quite) elementary overview of some basic areas of cryptography.

* [[Niels Ferguson|Ferguson, Niels]], [[Bruce Schneier|Schneier, Bruce]] - ''Practical Cryptography'', Wiley, 2003, ISBN 0471223573. Up to date cryptography reference. Describes how to implement a particular crypto system using cryptographic protocols. This is an in depth consideration of one cryptographic problem including paths not taken. Not otherwise available in a single source. A follow-up to 'Applied Cryptography' (see below)

* [[Bruce Schneier|Schneier, Bruce]] - ''Applied Cryptography'', 2 ed, Wiley, ISBN 0471117099. The best single volume available covering modern cryptographic practice. Not overly mathematical and so accessible -- mostly -- to the non-technical.

* [[Bruce Schneier|Schneier, Bruce]] - ''Secrets and Lies'', Wiley, ISBN 0471253111, a discussion of the context within which cryptography and cryptosystems work. Meta-cryptography, if you will. Required reading for would be cryptographers, and nearly so for all cryptography users.

* Ross Anderson -- ''Security Engineering'', advanced coverage of computer security issues, including cryptography, by one of its foremost practicioners, and most likely its best writer.

* Bamford, James - ''The Puzzle Palace : A Report on America's Most Secret Agency'' ISBN 0140067485, and the more recent "Body of Secrets". The best of a quite small group of books about NSA. Most are inadequate, and untrustworthy, for various reasons.