Cyphernomicon Top
Cyphernomicon 5.4

Cryptology:
Crypto Basics


    5.4.1. "What is cryptology?"
           - we see crypto all around us...the keys in our pockets, the
              signatures on our driver's licenses and other cards, the
              photo IDs, the credit cards
           + cryptography or cryptology, the science of secret
              writing...but it's a lot more...consider I.D.  cards, locks
              on doors, combinations to safes, private
              information...secrecy is all around us
             - some say this is bad--the tension between "what have you
                got to hide?" and "none of your business"
           - some exotic stuff: digital money, voting systems, advanced
              software protocols
           - of importance to protecting privacy in a world of
              localizers (a la Bob and Cherie), credit cards, tags on
              cars, etc....the dossier society
           + general comments on cryptography
             - chain is only as strong as its weakest link
             - assume opponnent knows everything except the secret key
             -
           - Crypto is about economics
           + Codes and Ciphers
             + Simple Codes
               - Code Books
             + Simple Ciphers
               + Substitution Ciphers (A=C, B=D, etc.)
                 - Caesar Shift (blocks)
               + Keyword Ciphers
                 + Vigenère (with Caesar)
                   + Rotor Machines
                     - Hagelin
                     - Enigma
                     - Early Computers (Turing, Colossus)
             + Modern Ciphers
               + 20th Century
                 + Private Key
                   + One-Time Pads (long strings of random numbers,
                      shared by both parties)
                     + not breakable even in principle, e.g., a one-time
                        pad with random characters selected by a truly
                        random process (die tosses, radioactive decay,
                        certain types of noise, etc.)
                       - and ignoring the "breakable by break-ins"
                          approach of stealing the one-time pad, etc.
                          ("Black bag cryptography")
                     - Computer Media (Floppies)
                     + CD-ROMs and DATs
                       - "CD ROM is a terrible medium for the OTP key
                          stream.  First, you want exactly two copies of
                          the random stream.  CD ROM has an economic
                          advantage only for large runs. Second, you want
                          to destroy the part of the stream already used.
                          CD ROM has no erase facilities, outside of
                          physical destruction of the entire disk."
                          [Bryan G. Olson, sci.crypt, 1994-08-31]
                   + DES--Data Encryption Standard
                     - Developed from IBM's Lucifer, supported by NSA
                     - a standard since 1970s
                     + But is it "Weak"?
                       + DES-busting hardware and software studied
                         + By 1990, still cracked
                           - But NSA/NIST has ordered a change
                   + Key Distribution Problem
                     + Communicating with 100 other people means
                        distributing and  securing 100 keys
                       - and each of those 100 must keep their 100 keys
                          secure
                       - no possibility of widespread use
                 + Public Key
                   + 1970s: Diffie, Hellman, Merkle
                     + Two Keys: Private Key and Public Key
                       + Anybody can encrypt a message to Receiver with
                          Receiver's PUBLIC key, but only the Receiver's
                          PRIVATE key can decrypt the message
                         + Directories of public keys can be published
                            (solves the key distribution problem)
                           + Approaches
                             + One-Way Functions
                               - Knapsack (Merkle, Hellman)
                               + RSA (Rivest, Shamir, Adleman)
                                 - relies on difficulty of factoring
                                    large numbers (200 decimal digits)
                                 - believed to be "NP-hard"
                                 + patented and licensed to "carefully
                                    selected" customers
                                   - RSA, Fiat-Shamir, and other
                                      algorithms are not freely usable
                                   - search for alternatives continues
    5.4.2. "Why does anybody need crypto?"
           + Why the Need
             - electronic communications...cellular phones, fax
                machines, ordinary phone calls are all easily
                intercepted...by foreign governments, by the NSA, by
                rival drug dealers, by casual amateurs
             + transactions being traced....credit card receipts,
                personal checks, I.D. cards presented at time of
                purchase...allows cross-referencing, direct mail data
                bases, even government raids on people who buy greenhouse
                supplies!
               - in a sense, encryption and digital money allows a
                  return to cash
             - Why do honest people need encryption? Because not
                everyone is honest, and this applies to governments as
                well. Besides, some things are no one else's  business.
           - Why does anybody need locks on doors? Why aren't all
              diaries available for public reading?
           + Whit Diffie, one of the inventors of public key
              cryptography (and a Cypherpunk) points out that human
              interaction has largely been predicated on two important
              aspects:
             - that you are who you say you are
             - expectation of privacy in private communications
           - Privacy exists in various forms in various cultures. But
              even in police states, certain concepts of privacy are
              important.
           - Trust is not enough...one may have opponents who will
              violate trust if it seems justified
           + The current importance of crypto is even more striking
             + needed to protect privacy in cyberspace, networks, etc.
               - many more paths, links, interconnects
               - read Vinge's "True Names" for a vision
             + digital money...in a world of agents, knowbots, high
                connectivity
               - (can't be giving out your VISA number for all these
                  things)
             + developing battle between:
               - privacy advocates...those who want privacy
               - government agencies...FBI, DOJ, DEA, FINCEN, NSA
               + being fought with:
                 - attempts to restrict encryption (S.266, never passed)
                 - Digital Telephony Bill, $10K a day fine
                 - trial balloons to require key registration
                 - future actions
           + honest people need crypto because there are dishonest
              people
             - and there may be other needs for privacy
           - Phil Zimmerman's point about sending all mail, all letters,
              on postcards--"What have you got to hide?" indeed!
           - the expectation of privacy in out homes and in phone
              conversations
           + Whit Diffie's main points:
             + proving who you say you are...signatures, authentications
               - like "seals" of the past
             - protecting privacy
             - locks and keys on property and whatnot
           + the three elements that are central to our modern view of
              liberty and privacy (a la Diffie)
             - protecting things against theft
             - proving who we say we are
             - expecting privacy in our conversations and writings
    5.4.3. What's the history of cryptology?
    5.4.4. Major Classes of Crypto
           - (these sections will introduce the terms in context, though
              complete definitions will not be given)
           + Encryption
             - privacy of messages
             - using ciphers and codes to protect the secrecy of
                messages
             - DES is the most common symmetric cipher (same key for
                encryption and decryption)
             - RSA is the most common asymmetric cipher (different keys
                for encryption and decryption)
           + Signatures and Authentication
             - proving who you are
             - proving you signed a document (and not someone else)
             + Authentication
               + Seals
                 + Signatures (written)
                   + Digital Signatures (computer)
                     - Example: Numerical codes on lottery tickets
                     + Using Public Key Methods (see below)
                       - Digital Credentials (Super Smartcards)
                 - Tamper-responding Systems
               + Credentials
                 - ID Cards, Passports, etc.
               + Biometric Security
                 - Fingerprints, Retinal Scans, DNA, etc.
           + Untraceable Mail
             - untraceable sending and receiving of mail and messages
             - focus: defeating eavesdroppers and traffic analysis
             - DC protocol (dining cryptographers)
           + Cryptographic Voting
             - focus: ballot box anonymity
             - credentials for voting
             - issues of double voting, security, robustness, efficiency
           + Digital Cash
             - focus: privacy in transactions, purchases
             - unlinkable credentials
             - blinded notes
             - "digital coins" may not be possible
           + Crypto Anarchy
             - using the above to evade gov't., to bypass tax
                collection, etc.
             - a technological solution to the problem of too much
                government
           + Security
             + Locks
               - Key Locks
               + Combination Locks
                 - Cardkey Locks
             + Tamper-responding Systems (Seals)
               + Also known as "tamper-proof" (misleading)
                 - Food and Medicine Containers
                 - Vaults, Safes (Alarms)
                 + Weapons, Permissive Action Links
                   - Nuclear Weapons
                   - Arms Control
                 - Smartcards
                 - Currency, Checks
                 + Cryptographic Checksums on Software
                   - But where is it stored? (Can spoof the system by
                      replacing the whole package)
                 + Copy Protection
                   - Passwords
                   - Hardware Keys ("dongles")
                   - Call-in at run-time
             + Access Control
               - Passwords, Passphrases
               - Biometric Security, Handwritten Signatures
               - For: Computer Accounts, ATMs, Smartcards
    5.4.5. Hardware vs. Software
           - NSA says only hardware implementations can really be
              considered secure, and yet most Cypherpunks and ordinary
              crypto users favor the sofware approach
           - Hardware is less easily spoofable (replacement of modules)
           - Software can be changed more rapidly, to make use of newer
              features, faster modules, etc.
           - Different cultures, with ordinary users (many millions)
              knowing they are less likely to have their systems black-
              bag spoofed (midnight engineering) than are the relatively
              fewer and much more sensitive military sites.
    5.4.6. "What are 'tamper-resistant modules' and why are they
            important?"
           - These are the "tamper-proof boxes" of yore: display cases,
              vaults, museum cases
           - that give evidence of having been opened, tampered with,
              etc.
           + modern versions:
             - display cases
             - smart cards
             + chips
               - layers of epoxy, abrasive materials, fusible links,
                  etc.
               - (goal is to make reverse engineering much more
                  expensive)
             - nuclear weapon "permissive action links" (PALs)
    5.4.7. "What are "one way functions"?"
           - functions with no inverses
           - crypto needs functions that are seemingly one-way, but
              which actually have an inverse (though very hard to find,
              for example)
           - one-way function, like "bobbles" (Vinge's "Marooned in
              Realtime")
    5.4.8. When did modern cryptology start?
           + "What are some of the modern applications of cryptology?"
             + "Zero Knowledge Interactive Proof Systems" (ZKIPS)
               - since around 1985
               - "minimum disclosure proofs"
               + proving that you know something without actually
                  revealing that something
                 + practical example: password
                   + can prove you have the password without actually
                      typing it in to computer
                     - hence, eavesdroppers can't learn your password
                     - like "20 questions" but more sophisticated
                 - abstract example: Hamiltonian circuit of a graph
             + Digital Money
               + David Chaum: "RSA numbers ARE money"
                 - checks, cashiers checks, etc.
                 - can even know if attempt is made to cash same check
                    twice
                 + so far, no direct equivalent of paper currency or
                    coins
                   - but when combined with "reputation-based systems,"
                      there may be
             + Credentials
               + Proofs of some property that do not reveal more than
                  just that property
                 - age, license to drive, voting rights, etc.
                 - "digital envelopes"
               + Fiat-Shamir
                 - passports
             + Anonymous Voting
               - protection of privacy with electronic voting
               - politics, corporations, clubs, etc.
               - peer review of electronic journals
               - consumer opinions, polls
             + Digital Pseudonyms and Untraceable E-Mail
               + ability to adopt a digital pseudonym that is:
                 - unforgeable
                 - authenticatable
                 - untraceable
               - Vinge's "True Names" and Card's "Ender's Game"
               + Bulletin Boards, Samizdats, and Free Speech
                 + banned speech, technologies
                   - e.g., formula for RU-486 pill
                   - bootleg software, legally protected material
                 + floating opinions without fears for professional
                    position
                   - can even later "prove" the opinions were yours
               + "The Labyrinth"
                 - store-and-forward switching nodes
                 + each with tamper-responding modules that decrypt
                    incoming messages
                   + accumulate some number (latency)
                     + retransmit to next address
                       - and so on....
                 + relies on hardware and/or reputations
                   + Chaum claims it can be done solely in software
                     - "Dining Cryptographers"
    5.4.9. What is public key cryptography?
   5.4.10. Why is public key cryptography so important?
           + The chief advantage of public keys cryptosystems over
              conventional symmetric key (one key does both encryption
              and decryption) is one _connectivity_ to recipients: one
              can communicate securely with people without exchanging key
              material.
             - by looking up their public key in a directory
             - by setting up a channel using Diffie-Hellman key exchange
                (for example)
   5.4.11. "Does possession of a key mean possession of *identity*?"
           - If I get your key, am I you?
           - Certainly not outside the context of the cryptographic
              transaction. But within the context of a transaction, yes.
              Additional safeguards/speedbumps can be inserted (such as
              biometric credentials, additional passphrases, etc.), but
              these are essentially part of the "key," so the basic
              answer remains "yes." (There are periodically concerns
              raised about this, citing the dangers of having all
              identity tied to a single credential, or number, or key.
              Well, there are ways to handle this, such as by adopting
              protocols that limit one's exposure, that limits the amount
              of money that can be withdrawn, etc. Or people can adopt
              protocols that require additional security, time delays,
              countersigning, etc.)
           + This may be tested in court soon enough, but the answer for
              many contracts and crypto transactions will be that
              possession of key = possession of identity. Even a court
              test may mean little, for the types of transactions I
              expect to see.
             - That is, in anonymous systems, "who ya gonna sue?"
           - So, guard your key.
   5.4.12. What are digital signatures?
           + Uses of Digital Signatures
             - Electronic Contracts
             - Voting
             - Checks and other financial instruments (similar to
                contracts)
             - Date-stamped Transactions (augmenting Notary Publics)
   5.4.13. Identity, Passports, Fiat-Shamir
           - Murdoch, is-a-person, national ID cards, surveillance
              society
           + "Chess Grandmaster Problem" and other Frauds and Spoofs
             - of central importance to proofs of identity (a la Fiat-
                Shamir)
             - "terrorist" and "Mafia spoof" problems
   5.4.14. Where  else should I look?
   5.4.15. Crypto, Technical
           + Ciphers
             - traditional
             - one-time pads, Vernams ciphers, information-theoretically
                secure
             + "I Have a New Idea for a Cipher---Should I Discuss it
                Here?"
               - Please don't. Ciphers require careful analysis, and
                  should be in paper form (that is, presented in a
                  detailed paper, with the necessary references to show
                  that due diligence was done, the equations, tables,
                  etc. The Net is a poor substitute.
               - Also, breaking a randomly presented cipher is by no
                  means trivial, even if the cipher is eventually shown
                  to be weak. Most people don't have the inclination to
                  try to break a cipher unless there's some incentive,
                  such as fame or money involved.
               - And new ciphers are notoriously hard to design. Experts
                  are the best folks to do this. With all the stuff
                  waiting to be done (described here), working on a new
                  cipher is probably the least effective thing an amateur
                  can do. (If you are not an amateur, and have broken
                  other people's ciphers before, then you know who you
                  are, and these comments don't apply. But I'll guess
                  that fewer than a handful of folks on this list have
                  the necessary background to do cipher design.)
               - There are a vast number of ciphers and systems, nearly
                  all of no lasting significance. Untested, undocumented,
                  unused--and probably unworthy of any real attention.
                  Don't add to the noise.
             - What is DES and can it be broken?
             + ciphers
               - RC4, stream cipher
               + DolphinEncrypt
                 -
                 + "Last time Dolphin Encrypt reared its insecure head
                    in this forum,
                   - these same issues came up.  The cipher that DE uses
                      is not public and
                   - was not designed by a person of known
                      cryptographicc competence.  It
                   - should therefore be considered extremely weak.
                      <Eric Hughes, 4-16-94, Cypherpunks>
           + RSA
             - What is RSA?
             - Who owns or controls the RSA patents?
             - Can RSA be broken?
             - What alternatives to RSA exist?
           + One-Way Functions
             - like diodes, one-way streets
             - multiplying two large numbers together is
                easy....factoring the product is often very hard
             - (this is not enough for a usable cipher, as the recipient
                must be able to perform the reverse operation..it turns
                out that "trapdoors" can be found)
           - Digital Signatures
           + Digital Cash
             - What is digital cash?
             - How does digital cash differ from VISA and similar
                electronic systems?
             - Clearing vs. Doublespending Detection
           - Zero Knowledge
           - Mixes and Remailers
           - Dining Cryptographers
           + Steganography
             - invisible ink
             - microdots
             - images
             - sound files
           + Random Number Generators
             + von Neumann quote about living in a state of sin
               - also paraphrased (I've heard) to include _analog_
                  methods, presumably because the nonrepeating (form an
                  initial seed/start)  nature makes repeating experiments
                  impossible
             + Blum-Blum-Shub
               + How it Works
                 - "The Blum-Blum-Shub PRNG is really very simple.
                    There is source floating around on the crypto ftp
                    sites, but it is a set of scripts for the Unix bignum
                    calculator "bc", plus some shell scripts, so it is
                    not very portable.
                    
                    "To create a BBS RNG, choose two random primes p and
                    q which are congruent to 3 mod 4.  Then the RNG is
                    based on the iteration x = x*x mod n.  x is
                    initialized as a random seed.  (x should be a
                    quadratic residue, meaning that it is the square of
                    some number mod n, but that can be arranged by
                    iterating the RNG once before using its output.)"
                    [Hal Finney, 1994-05-14]
               - Look for blum-blum-shub-strong-randgen.shar and related
                  files in pub/crypt/other at ripem.msu.edu. (This site
                  is chock-full of good stuff. Of course, only Americans
                  are allowed to use these random number generators, and
                  even they face fines of $500,000 and imprisonment for
                  up to 5 years for inappopriate use of random numbers.)
               - source code at ripem ftp site
               - "If you don't need high-bandwidth randomness, there are
                  several good PRNG, but none of them run fast.  See the
                  chapter on PRNG's in "Cryptology and Computational
                  Number Theory"." [Eric Hughes, 1994-04-14]
             + "What about hardware random number generators?"
               + Chips are available
                 -
                 + "Hughes Aircraft also offers a true non-deterministic
                    chip (16 pin DIP).
                   - For more info contact me at kephart@sirena.hac.com"
                      <7 April 94, sci.crypt>
             + "Should RNG hardware be a Cypherpunks project?"
               - Probably not, but go right ahead. Half a dozen folks
                  have gotten all fired up about this, proposed a project-
                  -then let it drop.
             - can use repeated applications of a cryptographic has
                function to generate pretty damn good PRNs (the RSAREF
                library has hooks for this)
             + "I need a pretty good random number generator--what
                should I use?"
               - "While Blum-Blum-Shub is probably the cool way to go,
                  RSAREF uses repeated iterations of MD5 to generate its
                  pseudo-randoms, which can be reasonably secure and use
                  code you've probably already got hooks from perl
                  for.[BillStewart,1994-04-15]
             + Libraries
               - Scheme code: ftp://ftp.cs.indiana.edu/pub/scheme-
                  repository/scm/rand.scm
           + P and NP and all that jazz
             - complexity, factoring,
             + can quantum mechanics help?
               - probably not
           + Certification Authorities
             - heierarchy vs. distributed web of trust
             - in heierarchy, individual businesses may set themselves
                up as CAs, as CommerceNet is talking about doing
             + Or, scarily, the governments of the world may insist that
                they be "in the loop"
               - several ways to do this: legal system invocation, tax
                  laws, national security....I expect the legal system to
                  impinge on CAs and hence be the main way that CAs are
                  partnered with the government
               - I mention this to give people some chance to plan
                  alternatives, end-runs
             - This is one of the strongest reasons to support the
                decoupling of software from use (that is, to reject the
                particular model RSADSI is now using)
   5.4.16. Randomness
           - A confusing subject to many, but also a glorious subject
              (ripe with algorithms, with deep theory, and readily
              understandable results).
           + Bill Stewart had a funny comment in sci.crypt which also
              shows how hard it is to know if something's really random
              or not: "I can take a simple generator X[i] = DES( X[i-1],
              K ), which will produce nice random white noise, but you
              won't be able to see that it's non-random unless you rent
              time on NSA's DES-cracker." [B.S. 1994-09-06]
             - In fact, many seemingly random strings are actually
                "cryptoregular": they are regular, or nonrandom, as soon
                as one uses the right key. Obviously, most strings used
                in crypto are cryptoregular in that they _appear_ to be
                random, and pass various randomness measures, but are
                not.
           + "How can the randomness of a bit string be measured?"
             - It can roughly be estimated by entropy measures, how
                compressible it is (by various compression programs),
                etc.
             - It's important to realize that measures of randomness
                are, in a sense, "in the eye of the beholder"--there just
                is no proof that a string is random...there's always room
                for cleverness, if you will
             + Chaitin-Kolmogoroff complexity theory makes this clearer.
                To use someone else's words:
               - "Actually, it can't be done.  The consistent measure of
                  entropy for finite objects like a string or a (finite)
                  series of random numbers is the so-called ``program
                  length complexity''.  This is defined as the length of
                  the shortest program for some given universal Turing
                  machine
                  which computes the string.  It's consistent in the
                  sense that it has the familiar properties of
                  ``ordinary'' (Shannon) entropy.  Unfortunately, it's
                  uncomputable: there's no algorithm which, given an
                  arbitrary finite string S, computes the program-length
                  complexity of S.
                  
                  Program-length complexity is well-studied in the
                  literature.  A good introductory paper is ``A Theory of
                  Program Size Formally Identical to Information Theory''
                  by  G. J. Chaitin, _Journal of the ACM_, 22 (1975)
                  reprinted in Chaitin's book _Information Randomness &
                  Incompleteness_, World Scientific Publishing Co.,
                  1990." [John E. Kreznar, 1993-12-02]
           + "How can I generate reasonably random numbers?"
             - I say "reasonably" becuae of the point above: no number
                or sequence is provably "random." About the best that can
                be said is that a number of string is the reuslt of a
                process we call "random." If done algorithimically, and
                deterministically, we call this process "pseudo-random."
                (And  pseudorandom is usually more valuable than "really
                random" because we want to be able to generate the same
                sequence repeatedly, to repeat experiments, etc.)
   5.4.17. Other crypto and hash programs
           + MDC, a stream cipher
             - Peter Gutman, based on NIST Secure Hash Algorithm
             - uses longer keys than IDEA, DES
           - MD5
           - Blowfish
           - DolphinEncrypt
   5.4.18. RSA strength
           - casual grade, 384 bits, 100 MIPS-years (Paul Leyland, 3-31-
              94)
           - RSA-129, 425 bits, 4000 MIPS-years
           - 512 bits...20,000 MIPS-years
           - 1024 bits...
   5.4.19. Triple DES
           - "It involves three DES cycles, in encrypt-decrypt-encrypt
              order. THe keys used may be either K1/K2/K3 or K1/K2/K1.
              The latter is   sometimes caled "double-DES".  Combining
              two DES operations like this requires twice as much work to
              break as one DES, and a lot more storage. If you have the
              storage, it just adds one bit to the effective key size.  "
              [Colin Plumb, colin@nyx10.cs.du.edu, sci.crypt, 4-13-94]
   5.4.20. Tamper-resistant modules (TRMs) (or tamper-responding)
           + usually "tamper-indicating", a la seals
             - very tough to stop tampering, but relatively easy to see
                if seal has been breached (and then not restored
                faithfully)
             - possession of the "seal" is controlled...this is the
                historical equivalent to the "private key" in a digital
                signature system, with the technological difficulty of
                forging the seal being the protection
           + usually for crypto. keys and crypto. processing
             - nuclear test monitoring
             - smart cards
             - ATMs
           + one or more sensors to detect intrusion
             - vibration (carborundum particles)
             - pressure changes (a la museum display cases)
             - electrical
             - stressed-glass (Corning, Sandia)
           + test ban treaty verification requires this
             - fiber optic lines sealing a missile...
             - scratch patterns...
             - decals....
           + Epoxy resins
             - a la Intel in 1970s (8086)
             + Lawrence Livermore: "Connoisseur Project"
               - gov't agencies using this to protect against reverse
                  engineering, acquisition of keys, etc.
             + can't stop a determined effort, though
               - etches, solvents, plasma ashing, etc.
               - but can cause cost to be very high (esp. if resin
                  formula is varied frequently, so that "recipe" can't be
                  logged)
             + can use clear epoxy with "sparkles" in the epoxy and
                careful 2-position photography used to record pattern
               - perhaps with a transparent lid?
           + fiber optic seal (bundle of fibers, cut)
             - bundle of fibers is looped around device, then sealed and
                cut so that about half the fibers are cut; the pattern of
                lit and
                unlit fibers is a signature, and is extremely difficult
                to reproduce
           - nanotechnology may be used (someday)
   5.4.21. "What are smart cards?"
           - Useful for computer security, bank transfers (like ATM
              cards), etc.
           - may have local intelligence (this is the usual sense)
           - microprocessors, observor protocol (Chaum)
           + Smart cards and electronic funds transfer
             - Tamper-resistant modules
             + Security of manufacturing
               - some variant of  "cut-and-choose" inspection of
                  premises
             + Uses of smart cards
               - conventional credit card uses
               - bill payment
               - postage
               - bridge and road tolls
               - payments for items received electronically (not
                  necessarily anonymously)
  

Next Page: 5.5 Cryptology-Technical, Mathematical
Previous Page: 5.3 What this FAQ Section Will Not Cover

By Tim May, see README

HTML by Jonathan Rochkind