NetNews Usenet Archive 1992 #23/NN_1992_23.iso/spool/sci/crypt/3756

Text File | 1992-10-13 | 25.8 KB | 532 lines

Newsgroups: sci.crypt
Path: sparky!uunet!newsgate.watson.ibm.com!yktnews!admin!wo0z!lwloen
From: [e-mail] (Larry Loen)
Subject: temporary, independent FAQ file
Sender: [e-mail]
Message-ID: <[e-mail]>
Date: Tue, 13 Oct 1992 18:31:31 GMT
Reply-To: [e-mail]
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
Nntp-Posting-Host: wo0z.rchland.ibm.com
Organization: IBM Rochester
Keywords: FAQ cryptography
Lines: 517

"temporary, independent" sci.crypt Frequently Asked Questions

I understand a group is putting together a fine FAQ for this
topic.  However, in my brief tenure on Internet, there seems to
be a consistent cry for some form of FAQ.  After a discussion with
a former member of the FAQ group, I've decided to post this.

This is an attempt to answer many basic questions in hope of
providing a lot of the benefit of a FAQ without the burden of
being a complete answer to all relevant questions.  There is no
desire or attempt to replace the other group's work; this is more
of a stopgap.

I would cheerfully encourage the FAQ group to replace this with
an appropriate subset of their own effort.

Note:  References to a "Megabarfoocorp" are intended to be
fictional.

Q1:  What is cryptography?  How, basically, does it work?
  What are the basic terms used to describe cryptography?

  Cryptography is the art and science of hiding data in plain sight.
  It is also the art and science of stealing data hidden in plain sight.
  There are at least three players.  The first is the one who has
  the original data, which is presumed to have high value to
  others.  This data is presumed to reside in a safe place that
  no one but the originator and his/her friends can see.  (If the
  originator cannot physically secure the original data,
  cryptography is a waste of time).  Now, for cryptography to be
  necessary, the data must, for some reason, have to be
  transmitted over some public means such as a telephone line, a
  letter through the mail; any means that cannot be physically
  secured by the owner to a legitmate receiver of the data.  The
  receiver is the second party.

  Cryptography is any transformation of the data into a form it is hoped
  that cannot be recovered in a timely manner by an unknown party,
  which is called here 'the opponent'.  The transformation is not
  some physical means, such as hiding the data on microfilm or
  some such; it is some mathematical transformation of the
  original data that the receiver on the other end knows how to
  undo.

  The process of scrambling (transforming) the data is called
  'encryption'.  Unscrambling is called decryption.  An
  encryption system has two basic parts.  1) A general
  transformation process called the encryption algorithm.  2) A
  customization of that algorithm called a cipher key.  The
  sender and the receiver must find a secure means to exchange
  the cipher key.  That is, the same public means used to send
  the encrypted data cannot be used.  This may be a difficult
  problem, and has a variety of solutions, but will be assumed
  solved for now.  Once the key is successfully exchanged, the
  two parties can separately implement the encryption algorithm
  and its inverse, the decryption algorithm.

  At this point, the data can be transmitted in its encrypted form
  using the agreed-to key to customize the general algorithm to a
  particular version that transforms the data.  Since the
  encrypted data is sent over some insecure medium, it is assumed
  that an opponent (the third party) may intercept the data,
  possibly without being detected, and analyze the encrypted
  text, also called cipher text.

  In theory, any encryption system can be defeated, given enough
  time.  The amount of time it takes cannot always be predicted.
  This is because the opponent can supply extra information
  that might reduce the computation time a great deal.  For one
  thing, the sender and receiver may make a very poor choice of
  cipher key.  With computers, it is possible to try what at
  first seems like an outlandish number of keys very quickly.  If
  the opponent decides to do this and the key falls in the
  range attempted, even the strongest encryption algorithm will
  not protect the data.

  All methods the opponent dreams up have one thing in common.
  It is an attempt to recover the original data without advance
  knowledge of the particular cipher key.  There are a wide
  variety of means available and some will be described later on.
  The name for any of these methods is called 'cryptanalysis' and
  the person who does the penetration is called the cryptanalyst.

  To test a newly-created system, the designer of the system will
  pose as the cryptanalyst as well as finding others with skill
  to also pose as a cryptanalyst of the new system.  In other
  words, the designer will pose as the opponent of his/her own
  system in order to probe for weakness.

  In diagram form (the boxes indicated physically secure areas)--

  -------------|                   --------------
    Sender     |                   | Receiver
   "x"         |                   |  cipher key
    cipher key |------->  y  ----->|
   y=Encrypt(  |          |        | x=Decrypt(y,key)
      x,key)   |          |        |
  -------------|          |        |-------------
                          V
                  Opponent
                     z = Cryptanalysis(y,Encrypt Algorithm,
                             general knowledge of x, guesses about
                             secret key, statistical analysis of y)

           The opponent uses Cryptanalysis of message y until
           the value z is either equal to x or z is "enough" like
           x to accomplish the illicit purpose.  The sender and
           receiver win whenever recovery of z takes too much time.

Q2:  I have invented this wonderful, fast-running encryption
  algorithm.  How do I find out if it is as great as I think it
  is?

  It is one thousand times easier to invent an encryption
  algorithm than it is to discover if it is worthwhile.
  Cryptanalysis is hard to do, but has also frequently succeeded.
  It is often very hard for a designer, especially one who is
  unfamiliar with cryptanalysis, to put oneself in the
  cryptanalyst's shoes and dream up cryptanalysis that will
  defeat the newly invented system.  Many practical illicit
  decryptions astonish the newcomer; they seem like cheating, but
  they do work.

  Therefore, the first requirement for designing a successful
  new algorithm is to get skill in 'cracking' algorithms.  A
  good algorithm is much harder to invent than it seems.  Many
  people wish to shortcut this, but there really is no other
  way; even if you've a natural talent for crypto, it must be
  developed.  So, before posting a new wonder-algorithm, take
  the time to do a little study, first.

  It is easy to get superficial reassurance that a
  poor encryption algorithm seems good.  Most people reading
  this file have probably attempted the kinds of cryptograms one
  finds in newspapers and puzzle books (usually simply called
  'cryptograms').  That encryption algorithm is simple -- one
  replaces each letter of the alphabet with exactly one other
  letter of the alphabet.  Thus, the word "the" might encrypt to
  "xyh" and the word "these" might become "xyhqh".  This little
  fragment also reveals why most people can 'break' this cipher,
  even with little knowledge of cryptanalysis.  "xy" is a good
  candiate to be the common dipthong "th" and "the" is the most
  common word in the language.  Analysis of this kind will solve
  most newspaper-type cryptograms; only the severe shortness of
  most puzzle texts make it at all difficult.  A simple
  substitution cipher puzzle made from this FAQ file would be
  very easy indeed.  Yet, even for puzzle cryptograms,
  there are twenty-six factorial possible cipher keys,
  an immense number.  A full ASCII simple substitution cipher,
  with perhaps 96 total displayable characters has
  about 96 factorial keys.  Yet, an ASCII file so encrypted is not
  even three times harder than the newspaper cryptograms.

  The problem here is the same as for better systems; the
  opponent may be able to bring some added information (in the
  case of simple substitution, general knowledge of the English
  language) which enables the vast majority of cipher keys to be
  eliminated via cryptanalysis and thus never even be
  tried.  Claims that "my encryption system is safe because it
  has trillions of keys so the opponent cannot try them all" are
  extremely suspect and not made by those with experience.  It
  is a necessary condition for safety, but it is not sufficient.

  It is vital for a designer to have experience with
  crytanalysis.  Beginners are amazed how often they re-invent
  something that seems good, but is a trivial variation of an
  encryption algorithm which was broken decades ago.  Likewise,
  even if the system has never been seen before, it may none the
  less be vulnerable to some "attack" that is straightforward to
  those experienced with "cracking" algorithms.

Q3:  What is an "attack"?

  An attack is a particular form of cryptanalysis.  There are
  generic types of attacks, and some very specific attacks.  In
  the end, cryptography is a war of specifics.  The opponent
  will either invent a very clever and unique attack or will
  customize a general attack to suit the needs at hand.  Some
  attacks might even exploit the properties of a particular
  message or settle for a partial illicit decryption.

  However, in sci.crypt, there is a great deal of discussion
  about attacks, both general and specific, and an assumption
  that the reader can fill in missing details at times.  Since
  those who post here usually have other things to do, to-the-bit
  details are often omitted.

Q4:  Hmm.  In spite of questions 2 and 3, I still think I
  have a pretty good system.  But, it seems pretty hard
  to know if it can really defeat an expert.  Still, I know
  it will work if I can keep my method secret, right?

  Good luck.  There are documented cases aplenty where an
  encryption system was deduced based entirely on clever analysis
  of the encrypted text alone.  Any 'attack' on just the
  encrypted text (also called the ciphertext) is called a
  "ciphertext only attack", though such an attack usually
  assumes the encryption system is known.

  Any serious use of an encryption system would mean disclosing
  it to too many people to ensure secrecy, even if one were very
  confident that the encryption was too strong to be defeated by
  a ciphertext only attack.  By long experience, designers of
  practical encryption algorithms assume that the opponent
  discovers all the details of the algorithm; only the particular
  key can be assumed to be kept secret.  This also applies, by
  the way, to any form of cipher key translator.  Often, the
  internal form of a cipher key is some particular binary number.
  This is awkward to input, so there are a variety of ways of
  getting more "human understandable" input and transforming that
  input to the internal key.  Such a mechanism must also be
  assumed to be known.

  This is not to say the designer is _obligated_ to publish the
  algorithm (though this is done for any widely used system), but
  that the prudent designer must _assume_ someone else will
  learn it anyway, by hook or by crook.  Relying on secrecy of
  encryption method has failed repeatedly.

Q5:  What are the principal cryptanalytic attacks?

  The first is "cipher text only".  This is recovering the text
  or the key by analysis of the text (using statistical means,
  for instance) and by knowing broad details such as whether it
  is the text of someone's speech, a PC-DOS EXE file, whether text
  is in English or French.  For non-puzzle examples, such broad
  information is almost always reliably known.  People have some
  idea of what they wish to steal.  The weakest systems fall to
  this form of attack.

  The next attack is "known plaintext".  If one works with a
  newspaper cryptogram, one may have little idea of what is in
  the text.  However, if one was illicitly trying to decrypt the
  source code of Megabarfoocorp's C++ compiler, one would be much
  better off.  There would be lots of things one could
  confidently expect, such as long strings of the space
  character, strings like "if (" and "if(" and the like.

  There would even be whole phrases like "Copyright 1990,
  Megabarfoocorp International" or some such.  With imagination,
  surprisingly long strings can be predicted.  It might be easy
  to eliminate the wrong ones and therefore keep the correct
  ones.  For instance, in the "Copyright" string above, there are
  a lot of variations of what is capitalized, how much
  punctuation, where the date of copyright is placed, but the
  total number of variations is small enough to be a practical
  attack.

  Moreover, it is sometimes possible to know in a general way
  where the known text is; and even sometimes possible to have a
  very good idea where the text is.  Suppose, for example, an
  opponent studied books published by Megabarfoocorp.  The books'
  examples would show where the copyright notice was published,
  its format, etc.  It would very likely be the same format in
  the product as in the 'toy' examples in the book.  If it was
  near the front of the module, or had some predicatable
  "signature" in the ciphertext, independent of the cipher key,
  one might well be able to place it very exactly.  A wide
  variety of systems can be broken if enough known plaintext can
  be successfully placed.

  The next attack is "chosen plaintext".  In some situations, it
  is possible for the opponent to pose as the legitimate user
  of the encryption system.  This is especially true in "public
  key" systems (described later).  In this case, the opponent
  can present fairly arbitrary unencrypted data of his/her
  choosing, cause it to be encrypted, and study the results.
  Very few systems ever invented pass this test, but it should be
  seriously considered for any significant use, even if all that
  is ever contemplated is ordinary file encryption where it does
  not seem like a reasonable possibility.  Why?  Because it may
  be possible to take a very large file, with lots of data in it,
  and approximate, well enough, a chosen plaintext attack with a
  known plaintext attack.

  There are other, more elaborate attack strategies.  One worth
  mentioning for telecommunications applications is the "replay"
  attack.  Suppose one has an Automatic Teller Machine (ATM)
  which uses a simple substitution cipher.  Since one assumes the
  telephone line to the ATM can be tapped (why encrypt if it
  cannot?), one can also assume the opponent can _inject_ false
  ciphertext.  Thus, without even being aware of the actual
  system, an opponent may be able to simply replay old ciphertext
  and get the cash drawer to deduct $50 from your account.

  Another general form of attack often not considered by
  newcomers is comparing multiple messages using the same key.
  It is impractical to use a different key for each cipher
  text (with one important exception called the 'one time
  pad').  Therefore, an opponent will have several different
  things encrypted in the same key and may be able to exploit
  this fact.  All transpositions algorithms (those which merely
  scramble the order of the bytes) are vulnerable to this
  attack.  More sophisticated systems are also vulnerable to this
  attack in some cases as well.

  This is a vast area and one of the things that is difficult,
  even for experienced designers, is anticipation of all possible
  attacks.  Moreover, there is no obligation on the attacker's
  part to be less mathematically sophisticated than the designer.
  A system that survives the attacks the designer invents may
  fall easily to a mathematical approach the designer of the
  system is unfamiliar with.

Q6:  What does make a system 'good'?

  What makes a system 'good' relies on many details specific to
  a given situation.  Only after a lot of ingenuious attacks are
  tried can a system be released for use.  There never can be any
  absolute guarantees.  All that can be said is that it defeated
  the best experts available.  The opponent may be smarter.

  However, there are some agreed-to minimums that a good system
  must have to even be worth serious analysis --

  1)  It must be suitable for computer use.  Ordinary byte streams
   (as arbitrary as possible) would be the input "plain"
   text and byte streams would be the output "cipher" text.
   There should be few cases where some kinds of input text produces poor
   results and these, if they exist, should be easily known,
   described, and avoided.

  2)  To be cost-competitive, it must produce about the same number of
   output cipher bytes as input plain bytes.  Relaxing this restriction
   is not as helpful as one might think; the best historical systems
   meet this restriction, so a new system must meet it also.

  3)  Output bytes should have a complex relationship between the key,
   the plain text being encrypted, and possibly some amount of
   text previously encrypted.  "Simple", general methods, such
   as creation/construction of minterm sums and matrix inversions should
   not produce the cipher key or an equivalent, usable illicit
   decryption method.

  4)  Trying all keys must not be practical.  Trying a cleverly ordered
   subset of the keys must not work.  This is hard to achieve; it means
   that the failure of a particular key X to illicitly decrypt must
   not also allow an opponent to conclude that some large class of keys
   "similar" to X need not be tried.

   All keys must be equally strong; any exceptions must be well
   known, few in number, and easily avoided.

  5)  Assume all details about the encryption algorithm are known.
   Relying on a secret method has failed repeatedly.  It is prudent to
   assume only the variable part of the system, called the cipher key,
   that is selected by the customer, is unknown.

  6)  Classical attacks must be tried in great variety and ingenuity.
   Details of this are beyond the scope of this file.  For a summary
   of the principal attacks, see Question 5, "What are the principal
   cryptanalytic attacks?".  It is easy to do this particular step
   incompletely.  Remember, there may be little effective limit to the
   resources or the brainpower of one's opponent.  The data may be
   very valuable and it make take only a couple of days rental of the
   right kind of consultant and a supercomputer to get the job done.

  7) Performance must be competitive with existing solutions.  A
   practical problem is that every moment spent encrypting is regarded as
   "overhead".  Therefore, the method must not be uncompetitive
   with existing algorithms regarded as secure.

  Inventing one's own system is an interesting pastime and quite
  educational.  However, any hope of really securing data requires, at
  the very minimum, mastery of illicit decipherment.  It is very easy
  to scramble data and please oneself.  This is not the same as keeping
  it actually secure.

Q7:  What are the legal restrictions on cryptography?

  You'd have to ask a lawyer.  Most governments consider cryptography a
  sensitive topic for one reason or another.  There are a variety
  of restrictions possible.

  Most governments don't give their reasons publically, so one
  may not know why there are restrictions, just that there are
  restrictions to follow.

  One can expect to find laws about sending encrypted data over national
  borders and may often expect to find laws about the import and export of
  encryption systems.

  Since sending data over Internet, Bitnet, Usenet, Fidonet, etc. may cross
  national borders (even if the originator does not realize it), a basic
  familiarity with these laws is recommended before sending out encryption
  systems or encrypted data.

Q8:  What is a public key system?

  A public key system is an encryption method with a unique
  property -- encryption and decryption use different keys and
  one of those keys can be published freely.

  Being able to pass around the 'decrypt' key part of one's
  encryption algorithm allows some very interesting things to
  happen.  For one thing, messages can be exchanged by people who
  had not planned on doing so in advance.  One merely encrypts in
  one's private key, decrypts using the receiver's public key and
  passes on the result to the receiver.  The receiver encrypts in
  his/her own private key, then decrypts using the sender's public
  key, recovering the message.

Q9:  What is key distribution?

  Key distribution is the practical problem of exchanging keys
  between the parties that wish to set up an encryption system
  between the two of them.  Especially in a network environment,
  passing keys one can trust back and forth, can be difficult.
  How can one be sure a cipher key was not sent by an impostor?
  Unless the keys are exchanged in a secret, secure place,
  face-to-face, getting keys securely exchanged and with
  knowledge of the fact that the key was sent authentically can
  be difficult.  Yet, any practical system must permit reasonably
  convenient but very secure exchange of cipher keys.

  Once a few special keys are securely exchanged, it may be
  possible to send new cipher keys in encrypted form between the
  sender and receiver that have a known lifetime.  That is, the
  cipher key is sent in a special message using a special key
  used only for exchanging keys.  In telecommunications
  environments, this allows frequent change of keys between the
  parties 'safely' over the same insecure medium used to send the
  cipher text.  While this idea is at the heart of much
  commercial use of cryptography, it is not easily accomplished
  and less easily summarized.

Q10:  What is the 'one time pad'?

  The 'one time pad' is an encryption method that is known to be
  absolutely, proveably secure.  How it works is as follows --
  1.  Generate a huge number of bits using a naturally random
  process.  2.  Both sides exchange this data, which is as much
  data as they are going to exchange later on.  3.  Exclusive OR the
  original text, bit by bit, with the 'one time pad' data, never
  reusing the 'one time pad' data.  4.  Have elaborate rules to
  keep the two sides in synch so that the data can be recovered
  reliably by the receiver.  (Both sides must know where they are
  in terms of how much 'one time pad' has been consumed).

  Note that only genuine, naturally random processes will do.  There
  must be no relationship between any prior bit of the 'one time pad'
  and a future bit of the key.  "Random number generators", in
  particular, may not substitute and still be a 'one time pad'.  The
  reason it works is precisely because there is no relationship between
  any bits of the key stream.  All cipher keys are equally probable.
  All original data messages are equally probable.  There is no 'hat'
  to hang analysis upon.  Even if one can inject as much text into
  a one time pad as one wishes, recovering the key stream tells nothing
  about the next message.

  Unfortunately, one time pads are very ungainly, so they are not
  typically used.  The requirement to have a genuinely random process,
  with the right kind of statistical probability, is not easy to
  to set up.  The ability to exchange vast amounts of data,
  securely, in advance, is not easy to achieve in environments
  when encryption is needed in the first place.

  There are a variety of cipher systems which generate "pseudo
  one time pad" streams of cipher key, but all have the same
  theoretical vulnerability; any algorithmic process introduces
  relationships between some old key bit(s) and the new key bit
  and so permits cryptanalysis.  "Random number generators" are
  frequently dreamed up by newcomers as a "pseudo one time pad",
  but they are notoriously vulnerable to analysis, all
  independent of whether the pseudo-random stream satisfies
  randomness tests or not.

Q11:  What is the NSA (National Security Agency)?

  The NSA has several tasks.  The most relavent here is that it employs
  the United States' government's cryptographers.  Most nations have some
  department that handles cryptography for it, but the US' NSA tends to
  draw the most attention.  It is considered equal to or superior to any
  such department in the world.  It keeps an extremely low public profile,
  and has a "large", but secret budget.  Because of these and other factors,
  there will be many posts speculating about the activities and motives of
  the NSA.

Q12:  What is the American Cryptogram Association?

  American Cryptogram Association Information, Sept 1992

  The American Cryptogram Association is an international group
  of individuals who study cryptography together and publish
  puzzle ciphers to challenge each other and get a practical
  experience in solving ciphers.  It is a nonprofit group.

  The American Cryptogram Association (ACA) publishes the
  bi-monthly magazine "The Cryptogram", which contains
  a wide variety of simple substitution ciphers ("cryptograms")
  in English and other languages as well as cryptograms
  using cipher systems of historical interest (such as Playfair).

  The level of difficulty varies from easy to difficult.  Except
  for "foreign language" cryptograms, all text is in English.

  The magazine also features "how to" articles at the hobbyist level
  and other features of interest to members.  A "Computer Supplement"
  is also available which features articles on computerizing various
  phases of cryptogram solving; the level of the articles varies from
  simple programming examples to automatic algorithmic solutions of
  various cipher systems.  The supplement is available as a separate
  subscription, and is published when material permits; usually two
  or three times per year.

  Where to write for subscription or other information --

  ACA Treasurer
  18789 West Hickory St
  Mundelein IL 60060




--
   Larry W. Loen        |  My Opinions are decidedly my own, so please
                        |  do not attribute them to my employer