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