Skip to main content

5. Cryptology

THE CYPHERNOMICON: Cypherpunks FAQ and More, Version 0.666,

1994-09-10, Copyright Timothy C. May. All rights reserved. See the detailed disclaimer. Use short sections under "fair use" provisions, with appropriate credit, but don't put your name on my words.

5.2. SUMMARY: Cryptology

5.2.1. Main Points

  • gaps still exist here...I treated this as fairly low priority, given the wealth of material on cryptography

5.2.2. Connections to Other Sections

  • detailed crypto knowledge is not needed to understand many of the implications, but it helps to know the basics (it heads off many of the most wrong-headed interpretations)
  • in particular, everyone should learn enough to at least vaguely understand how "blinding" works

5.2.3. Where to Find Additional Information

  • a dozen or so major books
    • Schneier, "Applied Cryptography"--is practically "required reading"
    • Denning
    • Brassard
    • Simmons
    • Welsh, Dominic
    • Salomaa
    • "CRYPTO" Proceedings
    • Other books I can take or leave
  • many ftp sites, detailed in various places in this doc
  • sci.crypt, alt.privacy.pgp, etc.
  • sci.crypt.research is a new group, and is moderated, so it should have some high-quality, technical posts
    • FAQs on sci.crypt, from RSA, etc.
  • Dave Banisar of EPIC (Electronic Privacy Information Center) reports: "...we have several hundred files on encryption available via ftp/wais/gopher/WWW from cpsr.org /cpsr/privacy/crypto." [D.B., sci.crypt, 1994-06-30]

5.2.4. Miscellaneous Comments

  • details of algorithms would fill several books...and do
  • hence, will not cover crypto in depth here (the main focus of this doc is the implications of crypto, the Cypherpunkian aspects, the things not covered in crypto textbooks)
  • beware of getting lost in the minutiae, in the details of specific algorithms...try to keep in the mind the important aspects of any system

5.3. What this FAQ Section Will Not Cover

5.3.1. Why a section on crypto when so many other sources exist?

  • A good question. I'll be keeping this section brief, as many textbooks can afford to do a much better job here than I can.
  • not just for those who read number theory books with one hand

5.3.2. NOTE: This section may remain disorganized, at least as compared to some of the later sections. Many excellent sources on crypto exist, including readily available FAQs (sci.crypt, RSADSI FAQ) and books. Schneier's books is especially recommended, and should be on every Cypherpunk's bookshelf.

5.4. 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
  • VigenDre (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 blackbag 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)

5.5. Cryptology-Technical, Mathematical

5.5.1. Historical Cryptography

  • Enigma machines
    • cracked by English at Bletchley Park
    • a secret until mid-1970s
  • U.K. sold hundreds of seized E. machines to embassies, governments, even corporations, in late 1940s, early 1950s - could then crack what was being said by allies
    • Hagelin, Boris (?)
      • U.S. paid him to install trapdoors, says Kahn
  • his company, Crypto A.G., was probably an NSA front company - Sweden, then U.S., then Sweden, then Zug
    • rotor systems cracked

5.5.2. Public-key Systems--HISTORY

  • Inman has admitted that NSA had a P-K concept in 1966
  • fits with Dominik's point about sealed cryptosystem boxes with no way to load new keys
  • and consistent with NSA having essentially sole access to nation's top mathematicians (until Diffies and Hellmans foreswore government funding, as a result of the antiPentagon feelings of the 70s)
    • Merkle's "puzzle" ideas, circa mid-70s
    • Diffie and Hellman
    • Rivest, Shamir, and Adleman

5.5.3. RSA and Alternatives to RSA

  • RSA and other P-K patents are strangling development and dissemination of crypto systems
  • perhaps out of marketing stupidity, perhaps with the help of the government (which has an interest in keeping a monopoly on secure encryption)
    • One-way functions and "deposit-only envelopes"
      • one-way functions
  • deposit-only envelopes: allow additions to envelopes and only addressee can open
  • hash functions are easy to implement one-way functions (with no need for an inverse)

5.5.4. Digital Signatures

  • Uses of Digital Signatures
    • Electronic Contracts
    • Voting
  • Checks and other financial instruments (similar to contracts)
    • Date-stamped Transactions (augmenting Notary Publics)
    • Undeniable digital signatures
  • Unforgeable signatures, even with unlimited computational power, can be achieved if the population is limited (a finite set of agents)
  • using an untraceable sending protocol, such as "the Dining Cryptographers Problem" of Chaum

5.5.5. Randomness and incompressibility

  • best definition we have is due to Chaitin and Kolmogoroff: a string or any structure is "random" if it has no shorter description of itself than itself.
  • (Now even specific instances of "randomly generated strings" sometimes will be compressible--but not very often. Cf. the works of Chaitin and others for more on these sorts of points.)

5.5.6. Steganography: Methods for Hiding the Mere Existence of Encrypted Data

  • in contrast to the oft-cited point (made by crypto purists) that one must assume the opponent has full access to the cryptotext, some fragments of decrypted plaintext, and to the algorithm itself, i.e., assume the worst
    • a condition I think is practically absurd and unrealistic
  • assumes infinite intercept power (same assumption of infinite computer power would make all systems besides one-time pads breakable)
  • in reality, hiding the existence and form of an encrypted message is important
  • this will be all the more so as legal challenges to crypto are mounted...the proposed ban on encrypted telecom (with $10K per day fine), various governmental regulations, etc.
  • RICO and other broad brush ploys may make people very careful about revealing that they are even using encryption (regardless of how secure the keys are)
  • steganography, the science of hiding the existence of encrypted information
    • secret inks
    • microdots
    • thwarting traffic analysis
    • LSB method
    • Packing data into audio tapes (LSB of DAT)
  • LSB of DAT: a 2GB audio DAT will allow more than 100 megabytes in the LSBs
  • less if algorithms are used to shape the spectrum to make it look even more like noise
  • but can also use the higher bits, too (since a real- world recording will have noise reaching up to perhaps the 3rd or 4th bit)
  • will manufacturers investigate "dithering" circuits? (a la fat zero?)
  • but the race will still be on
  • Digital video will offer even more storage space (larger tapes)
    • DVI, etc.
    • HDTV by late 1990s
  • Messages can be put into GIFF, TIFF image files (or even noisy faxes)
  • using the LSB method, with a 1024 x 1024 grey scale image holding 64KB in the LSB plane alone
  • with error correction, noise shaping, etc., still at least 50KB
  • scenario: already being used to transmit message through international fax and image transmissions
    • The Old "Two Plaintexts" Ploy
  • one decoding produces "Having a nice time. Wish you were here."
  • other decoding, of the same raw bits, produces "The last submarine left this morning."
    • any legal order to produce the key generates the first message
  • authorities can never prove-save for torture or an informant-that another message exists
  • unless there are somehow signs that the encrypted message is somehow "inefficiently encrypted, suggesting the use of a dual plaintext pair method" (or somesuch spookspeak)
  • again, certain purist argue that such issues (which are related to the old "How do you know when to stop?" question) are misleading, that one must assume the opponent has nearly complete access to everything except the actual key, that any scheme to combine multiple systems is no better than what is gotten as a result of the combination itself
    • and just the overall bandwidth of data...
    • Several programs exist:
      • Stego
      • etc. (described elsewhere)

5.5.7. The Essential Impossibility of Breaking Modern Ciphers and Codes

  • this is an important change from the past (and from various thriller novels that have big computers cracking codes)
    • granted, "unbreakable" is a misleading term
    • recall the comment that NSA has not really broken any Soviet systems in many years
  • except for the cases, a la the Walker case, where plaintext versions are gotten, i.e., where human screwups occurred
  • the image in so many novels of massive computers breaking codes is absurd: modern ciphers will not be broken (but the primitive ciphers used by so many Third World nations and their embassies will continue to be child's play, even for high school science fair projects...could be a good idea for a small scene, about a BCC student who has his project pulled)
    • But could novel computational methods crack these public key ciphers?
      • some speculative candidates
  • holographic computers, where large numbers are factored-or at least the possibilities are somehown narrowed-by using arrays that (somehow) represent the numbers to be factored
  • perhaps with diffraction, channeling, etc.
  • neural networks and evolutionary systems (genetic algorithms)
  • the idea is that somehow the massive computations can be converted into something that is inherently parallel (like a crystal)
  • hyperspeculatively: finding the oracle for these problems using nonconventional methods such as ESP and lucid dreaming - some groups feel this is worthwhile

5.5.8. Anonymous Transfers

  • Chaum's digital mixes
  • "Dining Cryptographers"
  • can do it with exchanged diskettes, at a simple level
    • wherein each person can add new material
    • Alice to Bob to Carol...Alice and Carol can conspire to determine what Bob had added, but a sufficient "mixing" of bits and pieces is possible such that only if everybody conspires can one of the participants be caught
      • perhaps the card-shuffling results?
  • may become common inside compute systems...
  • by this vague idea I mean that various new OS protocols may call for various new mechanisms for exchanging information

5.5.9. Miscellaneous Abstract Ideas

  • can first order logic predicates be proven in zero knowledge?
    • Riemannn hypothesis
    • P = NP?
      • would the universe change?
  • Smale has shown that if the squares have real numbers in them, as opposed to natural numbers (integers), then P = NP; perhaps this isn't surprising, as a real implies sort of a recursive descent, with each square having unlimited computer power
    • oracles
  • speculatively, a character asks if Tarot cards, etc., could be used (in addition to the normal idea that such devices help psychologically)
  • "a cascade of changes coming in from hundreds of decimal places out"
    • Quantum cryptography
  • bits can be exchanged-albeit at fairly low efficiencies-over a channel
  • with detection of taps, via the change of polarizations + Stephen Wiesner wrote a 1970 paper, half a decade before the P-K work, which outlined this-not published until much later
  • speculate that the NSA knew about this and quashed the publication
  • But could novel computational methods crack these public key ciphers?
    • some speculative candidates
  • holographic computers, where large numbers are factored-or at least the possibilities are somehown narrowed-by using arrays that (somehow) represent the numbers to be factored
  • perhaps with diffraction, channeling, etc.
  • neural networks and evolutionary systems (genetic algorithms)
  • the idea is that somehow the massive computations can be converted into something that is inherently parallel (like a crystal)
  • hyperspeculatively: finding the oracle for these problems using nonconventional methods such as ESP and lucid dreaming - some groups feel this is worthwhile
    • links to knot theory
    • "cut and choose" protocols (= zero knowledge)
    • can a "digital coin" be made?
  • this is formally similar to the idea of an active agent that is unforgeable, in the sense that the agent or coin is "standalone"
  • bits can always be duplicated (unless tied to hardware, as with TRMs), so must look elsewhere
  • could tie the bits to a specific location, so that duplication would be obvious or useless
  • the idea is vaguely that an agent could be placed in some location...duplications would be both detectable and irrelevant (same bits, same behavior, unmodifiable because of digital signature)
  • coding theory and cryptography at the "Discrete Mathematics"
    • http://www.win.tue.nl/win/math/dw/index.html

5.5.10. 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.6. Crypto Programs and Products

5.6.1. PGP, of course

  • it's own section, needless to say

5.6.2. "What about hardware chips for encryption?"

  • Speed can be gotten, for sure, but at the expense of limiting the market dramatically. Good for military uses, not so good for civilian uses (especially as most civilians don't have a need for high speeds, all other things being equal).

5.6.3. Carl Ellison's "tran" and mixing various ciphers in chains - "tran.shar is available at ftp.std.com:/pub/cme

  • des | tran | des | tran | des
  • to make the job of the attacker much harder, and to make differential cryptanalyis harder
  • "it's in response to Eli's paper that I advocated prngxor, as in: des | prngxor | tran | des | tran | des with the DES instances in ECB mode (in acknowledgement of Eli's attack). The prngxor destroys any patterns from the input, which was the purpose of CBC, without using the feedback path which Eli exploited."[ Carl Ellison, 1994-0715]

5.6.4. The Blum-Blum-Shub RNG

  • about the strongest algorithmic RNG we know of, albeit slow (if they can predict the next bit of BBS, they can break RSA, so...
  • ripem.msu.edu:/pub/crypt/other/blum-blum-shub-strong- randgen.shar

5.6.5. the Blowfish cipher

  • BLOWFISH.ZIP, written by Bruce Schneier,1994. subject of an article in Dr. Dobb's Journal:
  • ftp.dsi.unimi.it:/pub/security/crypt/code/schneier- blowfish.c.gz

5.7.1. "What is "blinding"?"

  • This is a basic primitive operation of most digital cash systems. Any good textbook on crypto should explain it, and cover the math needed to unerstand it in detail. Several people have explained it (many times) on the list; here's a short explanation by Karl Barrus:
  • "Conceptually, when you blind a message, nobody else can read it. A property about blinding is that under the right circumstances if another party digitally signs a blinded message, the unblinded message will contain a valid digital signature. "So if Alice blinds the message "I owe Alice $1000" so that it reads (say) "a;dfafq)(*&" or whatever, and Bob agrees to sign this message, later Alice can unblind the message Bob signed to retrieve the original. And Bob's digital signature will appear on the original, although he didn't sign the original directly. "Mathematically, blinding a message means multiplying it by a number (think of the message as being a number). Unblinding is simply dividing the original blinding factor out." [Karl Barrus, 1993-08-24]
  • And another explanation by Hal Finney, which came up in the context of how to delink pharmacy prescriptions from personal identity (fears of medial dossiers(:
  • "Chaum's "blinded credential" system is intended to solve exactly this kind of problem, but it requires an extensive infrastructure. There has to be an agency where you physically identify yourself. It doesn't have to know anything about you other than some physical ID like fingerprints. You and it cooperate to create pseudonyms of various classes, for example, a "go to the doctor" pseudonym, and a "go to the pharmacy" pseudonym. These pseudonyms have a certain mathematical relationship which allows you to re-blind credentials written to one pseudonym to apply to any other. But the agency uses your physical ID to make sure you only get one pseudonym of each kind...So, when the doctor gives you a prescription, that is a credential applied to your "go to the doctor" pseudonym. (You can of course also reveal your real name to the doctor if you want.) Then you show it at the pharmacy using your "go to the pharmacy" pseudonym. The credential can only be shown on this one pseudonym at the pharamacy, but it is unlinkable to the one you got at the doctor's. " [Hal Finney, 1994-09-07]

5.7.2. "Crypto protocols are often confusing. Is there a coherent theory of these things?"

  • Yes, crypto protocols are often expressed as scenarios, as word problems, as "Alice and Bob and Eve" sorts of complicated interaction protocols. Not exactly game theory, not exactly logic, and not exactly anything else in particular...its own area.
    • Expert systems, proof-of-correctness calculi, etc.
  • spoofing, eavesdropping, motivations, reputations, trust models
    • In my opinion, much more work is needed here.
  • Graphs, agents, objects, capabilities, goals, intentions, logic
  • evolutionary game theory, cooperation, defection, tit-for- tat, ecologies, economies
  • mostly ignored, to date, by crypto community

5.7.3. The holder of a key is the person, basically

  • that's the bottom line
  • those that worry about this are free to adopt stronger, more elaborate systems (multi-part, passphrases, biometric security, limits on account access, etc.)
  • whoever has a house key is essentially able to gain access (not saying this is the legal situation, but the practical one)

5.7.4. Strong crypto is helped by huge increases in processor power, networks

  • Encryption always wins out over cryptanalysis...gap grows greater with time
    • "the bits win"
  • Networks can hide more bits...gigabits flowing across borders, stego, etc.
  • faster networks mean more "degrees of freedom," more avenues to hide bits in, exponentially increasing efforts to eavesdrop and track
  • (However, these additional degrees of freedome can mean greater chances for slipping up and leaving clues that allow correlation. Complexity can be a problem.)
  • "pulling the plug" hurts too much...shuts down world economy to stop illegal bits ("naughty bits"?)
  • one of the main goals is to reach the "point of no return," beyond which pulling the plug hurts too much
  • this is not to say they won't still pull the plug, damage be damned

5.7.5. "What is the "Diffie-Hellman" protocol and why is it important?"

  • What it is
  • Diffie-Hellman, first described in 1976, allows key exchange over insecure channels.
  • Steve Bellovin was one of several people to explaine D-H to the list (every few months someone does!). I'm including his explanation, despite its length, to help readers who are not cryptologists get some flavor of the type of math involved. The thing to notice is the use of exponentiations and modular arithmetic (the "clock arithmetic" of our "new math" childhoods, except with really, really big numbers!). The difficulty of inverting the exponention (the discrete log problem) is what makes this a cryptographically interesting approach.
  • "The basic idea is simple. Pick a large number p (probably a prime), and a base b that is a generator of the group of integers modulo p. Now, it turns out that given a known p, b, and (bAx) mod p, it's extremely hard to find out x. That's known as the discrete log problem. "Here's how to use it. Let two parties, X and Y, pick random numbers x and y, 1 < x,y < p. They each calculate (bAx) mod p and (bAy) mod p and transmit them to each other. Now, X knows x and (bAy) mod p, so s/he can calculate (Ьлу)лх mod p = (bA(xy)) mod p. Y can do the same calculation. Now they both know (bA(xy)) mod p. But eavesdroppers know only (bAx) mod p and (bAy) mod p, and can't use those quantities to recover the shared secret. Typically, of course, X and Y will use that shared secret as a key to a conventional cryptosystem. "The biggest problem with the algorithm, as outlined above, is that there is no authentication. An attacker can sit in the middle and speak that protocol to each legitimate party. "One last point -- you can treat x as a secret key, and publish (bAX) mod p as a public key. Proof is left as an exercise for the reader." [Steve Bellovin, 1993-07-17]
    • Why it's important
    • Using it
  • Matt Ghio has made available Phil Karn's program for generating numbers useful for D-H: - ftp cs.cmu.edu: /afs/andrew.cmu.edu/usr12/mg5n/public/Karn.DH.generator + Variants and Comments
    • Station to Station protocol
      • "The STS protocol is a regular D-H followed by a (delicately designed) exchange of signatures on the key exchange parameters. The signatures in the second exchange that they can't be separated from the original parameters...STS is a well-thought out protocol, with many subtleties already arranged for. For the issue at hand, though, which is Ethernet sniffing, it's authentication aspects are not required now, even though they certainly will be in the near future." [Eric Hughes, 1994-02-06]

5.7.6. groups, multiple encryption, IDEA, DES, difficulties in analyzing

5.7.7. "Why and how is "randomness" tested?"

  • Randomness is a core concept in cryptography. Ciphers often fail when things are not as random as designers thought they would be.
  • Entropy, randomness, predictablility. Can never actually prove a data set is random, though one can be fairly confident (cf. Kolmogorov-Chaitin complexity theory).
  • Still, tricks can make a random-looking text block look regular...this is what decryption does; such files are said to be cryptoregular.
  • As to how much testing is needed, this depends on the use, and on the degree of confidence needed. It may take millions of test samples, or even more, to establish randomness in set of data. For example:
  • "The standard tests for 'randomness' utilized in govt systems requires 1Х10Л6 samples. Most of the tests are standard probability stuff and some are classified. " [Wray Kephart, sci.crypt, 1994-08-07]
    • never assume something is really random just becuase it looks random! (Dynamic Markov compressors can find nonrandomness quickly.)

5.7.8. "Is it possible to tell if a file is encrypted?"

  • Not in general. Undecideability and all that. (Can't tell in general if a virus exists in code, Adleman showed, and can't tell in general if a file is encrypted, compressed, etc. Goes to issues of what we mean by encrypted or compressed.)
  • Sometimes we can have some pretty clear signals:
    • headers are attached
    • other characteristic signs
    • entropy per character
  • But files encrypted with strong methods typically look random; in fact, randomness is closely related to encyption.
  • regularity: all symbols represented equally, in all bases (that is, in doubles, triples, and all n-tuples)
  • "cryptoregular" is the term: file looks random (regular) until proper key is applied, then the randomness vaDCharles Bennett, "Physics of Computation Workshop," 1993]
    • "entropy" near the maximum (e.g., near 6 or 7 bits per character, whereas ordinary English has roughly 1.5-2 bits per character of entropy)

5.7.9. "Why not use CD-ROMs for one-time pads?"

  • The key distribution problem, and general headaches. Theft or compromise of the keying material is of course the greatest threat.
  • And one-time pads, being symmetric ciphers, give up the incredible advantages of public key methods.
  • "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]
  • If you have to have a one-time pad, a DAT makes more sense; cheap, can erase the bits already used, doesn't require pressing of a CD, etc. (One company claims to be selling CD- ROMs as one-time pads to customers...the security problems here should be obvious to all.)

5.8. The Nature of Cryptology

5.8.1. "What are the truly basic, core, primitive ideas of cryptology, crypto protocols, crypto anarchy, digital cash, and the things we deal with here?"

  • I don't just mean things like the mechanics of encryption, but more basic conceptual ideas.

5.8.2. Crypto is about the creation and linking of private spaces...

5.8.3. The "Core" Ideas of Cryptology and What we Deal With

  • Physics has mass, energy, force, momentum, angular momentum, gravitation, friction, the Uncertainty Principle, Complementarity, Least Action, and a hundred other such concepts and prinicples, some more basic than others. Ditto for any other field.
  • It seems to many of us that crypto is part of a larger study of core ideas involving: identity, proof, complexity, randomness, reputations, cut-and-choose protocols, zero knowledge, etc. In other words, the buzzwords.
  • But which of these are "core" concepts, from which others are derived?
  • Why, for example, do the "cut-and-choose" protocols work so well, so fairly? (That they do has been evident for a long time, and they literally are instances of Solomonic wisdom. Game theory has explanations in terms of payoff matrices, Nash equilibria, etc. It seems likely to me that the concepts of crypto will be recast in terms of a smaller set of basic ideas taken from these disparate fields of economics, game theory, formal systems, and ecology. Just my hunch.)
  • statements, assertions, belief, proof
    • "I am Tim"
  • possession of a key to a lock is usually treated as proof of...
  • not always, but that's the default assumption, that someone who unlocks a door is one of the proper people..access privileges, etc.

5.8.4. We don't seem to know the "deep theory" about why certain protocols "work." For example, why is "cut-and-choose," where Alice cuts and Bob chooses (as in fairly dividing a pie), such a fair system? Game theory has a lot to do with it. Payoff matrices, etc.

  • But many protocols have not been fully studied. We know they work, but I think we don't know fully why they work. (Maybe I'm wrong here, but I've seen few papers looking at these issues in detail.)
  • Economics is certainly crucial, and tends to get overlooked in analysis of crypto protocols...the various "Crypto Conference Proceedings" papers typically ignore economic factors (except in the area of measuring the strength of a system in terms of computational cost to break).
  • "All crypto is economics."
  • We learn what works, and what doesn't. My hunch is that complex crypto systems will have emergent behaviors that are discovered only after deployment, or good simulation (hence my interest in "protocol ecologies").

5.8.5. "Is it possible to create ciphers that are unbreakable in any amount of time with any amount of computer power?"

  • Information-theoretically secure vs. computationally-secure
  • 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")
  • not breakable in "reasonable" amounts of time with computers
  • Of course, a one-time pad (Vernam cipher) is theoretically unbreakable without the key. It is "information- theoretically secure."
  • RSA and similar public key algorithms are said to be only "computationally-secure," to some level of security dependent on modulus lenght, computer resources and time available, etc. Thus, given enough time and enough computer power, these ciphers are breakable.
  • However, they may be practically impossible to break, given the amount of energy in the universe.Not to split universes here, but it is interesting to consider that some ciphers may not be breakable in our universe, in any amount of time. Our universe presumably has some finite number of particles (currently estimated to be 10л73 particles). This leads to the "even if every particle were a Cray Y-MP it would take..." sorts of thought experiments. But I am considering energy here. Ignoring reversible computation for the moment, computations dissipate energy (some disagree with this point). There is some uppper limit on how many basic computations could ever be done with the amount of free energy in the universe. (A rough calculation could be done by calculating the energy output of stars, stuff falling into black holes, etc., and then assuming about kT per logical operation. This should be accurate to within a few orders of magnitude.) I haven't done this calculation, and won't today, but the result would likely be something along the lines of X joules of energy that could be harnessed for computation, resulting in Y basic primitive computational steps. I can then find a modulus of 3000 digits or 5000 digits, or whatever,that takes more than this number of steps to factor. Caveats:
  1. Maybe there are really shortcuts to factoring. Certainly improvements in factoring methods will continue. (But of course these improvements are not things that convert factoring into a less than exponential-in-length problem...that is, factoring appears to remain "hard.")
  2. Maybe reversible computations (a la Landauer, Bennett, et. al.) actually work. Maybe this means a "factoring machine" can be built which takes a fixed, or very slowly growing, amount of energy.
  3. Maybe the quantum-mechanical idea of Shore is possible. (I doubt it, for various reasons.) I continue to find it useful to think of very large numbers as creating "force fields" or "bobbles" (a la Vinge) around data. A 5000-decimal-digit modulus is as close to being unbreakable as anything we'll see in this universe.

5.9. Practical Crypto

5.9.1. again, this stuff is covered in many of the FAQs on PGP and on security that are floating around...

5.9.2. "How long should crypto be valid for?"

  • That is, how long should a file remain uncrackable, or a digital signature remain unforgeable?
    • probabalistic, of course, with varying confidence levels
    • depends on breakthroughs, in math and in computer power
  • Some messages may only need to be valid for a few days or weeks. Others, for decades. Certain contracts may need to be unforgeable for many decades. And given advances in computer power, what appears to be a strong key today may fail utterly by 2020 or 2040. (I'm of course not suggesting that a 300- or 500-digit RSA modulus will be practical by then.)
  • many people only need security for a matter of months or so, while others may need it (or think they need it) for decades or even for generations
  • they may fear retaliation against their heirs, for example, if certain communications were ever made public
  • "If you are signing the contract digitally, for instance, you would want to be sure that no one could forge your signature to change the terms after the fact -- a few months isn't enough for such purposes, only something that will last for fifteen or twenty years is okay." [Perry Metzger, 1994-07-06]

5.9.3. "What about commercial encryption programs for protecting files?"

  • ViaCrypt, PGP 2.7
  • Various commercial programs have existed for years (I got "Sentinel" back in 1987-8...long since discontinued). Check reviews in the leading magazines.
    • Kent Marsh, FolderBolt for Macs and Windows
      • "The best Mac security program...is CryptoMactic by Kent Marsh Ltd. It uses triple-DES in CBC mode, hashes an arbitrary-length password into a key, and has a whole lot of Mac-interface features. (The Windows equivalent is FolderBolt for Windows, by the way.)" [Bruce Schneier, sci.crypt, 1994-07-19]

5.9.4. "What are some practical steps to take to improve security?"

  • Do you, like most of us, leave backup diskettes laying around?
  • Do you use multiple-pass erasures of disks? If not, the bits may be recovered.
    • (Either of these can compromise all encrypted material you have, all with nothing more than a search warrant of your premises.)

5.9.5. Picking (and remembering) passwords

  • Many of the issues here also apply to choosing remailers, etc. Things are often trickier than they seem. The "structure" of these spaces is tricky. For example, it may seem really sneaky (and "high entropy" to permute some words in a popular song and use that as a pass phrase...but this is obviously worth only a few bits of extra entropy. Specifically, the attacker will like take the thousand or so most popular songs, thousand or so most popular names, slogans, speeches, etc., and then run many permutations on each of them.
    • bits of entropy
    • lots of flaws, weaknesses, hidden factors
    • avoid simple words, etc.
    • hard to get 100 or more bits of real entropy
  • As Eli Brandt puts it, "Obscurity is no substitute for strong random numbers." [E.B., 1994-07-03]
  • Cryptanalysis is a matter of deduction, of forming and refining hypotheses. For example, the site "bitbucket@ee.und.ac.za" is advertised on the Net as a place to send "NSA food" to...mail sent to it gets discarded. So , a great place to send cover traffic to, no? No, as the NSA will mark this site for what it is and its usefulness is blown. (Unless its usefulness is actually something else, in which case the recursive descent has begun.)
  • Bohdan Tashchuk suggests [1994-07-04] using telephone-like numbers, mixed in with words, to better fit with human memorization habits; he notes that 30 or more bits of entropy are routinely memorized this way.

5.9.6. "How can I remember long passwords or passphrases?"

  • Lots of security articles have tips on picking hard-to- guess (high entropy) passwords and passphrases.
    • Just do it.
  • People can learn to memorize long sequences. I'm not good at this, but others apparently are. Still, it seems dangerous, in terms of forgetting. (And writing down a passphrase may be vastly more risky than a shorter but more easily memorized passphrase is. I think theft of keys and keystroke capturing on compromised machines are much more important practical weaknesses.)
  • The first letters of long phrases that have meaning only to the owner.
  • e.g., "When I was ten I ate the whole thing."---> "wiwtiatwt" (Purists will quibble that prepositional phrases like "when i was" have lower entropy. True, but better than "Joshua.")
    • Visual systems
  • Another approach to getting enough entropy in passwords/phrases is a "visual key" where one mouses from position to position in a visual environment. That is, one is presented with a scene containg some number of nodes, perhaps representing familiar objects from one's own home, and a path is chosen. The advantage is that most people can remember fairly complicated (read: high entropy) "stories." Each object triggers a memory of the next object to visit. (Example: door to kitchen to blender to refrigerator to ... ) This is the visual memory system said to be favored by Greek epic poets. This also gets around the keyboard-monitoring trick (but not necessarily the CRT-reading trick, of course). It might be an interesting hack to offer this as a front end for PGP. Even a simple grid of characters which could be moused on could be an assist in using long passphrases.

5.10. DES

5.10.1. on the design of DES

  • Biham and Shamir showed how "differential cryptanalyis" could make the attack easier than brute-force search of the 2Л56 keyspace. Wiener did a thought experiment design of a "DES buster" machine (who ya gonna call?) that could break a DES key in a matter of days. (Similar to the Diffie and Hellman analysis of the mid-70s, updated to current technology.)
  • The IBM designers knew about differential cryptanalyis, it is now clear, and took steps to optimize DES. After Shamir and Biham published, Don Coppersmith acknowledged this. He's written a review paper:
  • Coppersmith, D., "The Data Encryption Standard (DES) and its strength against attacks." IBM Journal of Research and Development. 38(3): 243-250. (May 1994)

5.11. Breaking Ciphers

5.11.1. This is not a main Cypherpunks concern, for a variety of reasons (lots of work, special expertise, big machines, not a core area, ciphers always win in the long run). Breaking ciphers is something to consider, hence this brief section.

5.11.2. "What are the possible consequences of weaknesses in crypto systems?"

  • maybe reading messages
  • maybe forging messages
  • maybe faking timestamped documents
  • maybe draining a bank account in seconds
  • maybe winning in a crypto gambling system
  • maybe matters of life and death

5.11.3. "What are the weakest places in ciphers, practically speaking?"

  • Key management, without a doubt. People leave their keys lying around , write down their passphrases. etc.

5.11.4. Birthday attacks

5.11.5. For example, at Crypto '94 it was reported in a rump session

(by Michael Wiener with Paul van Oorschot) that a machine to break the MD5 ciphers could be built for about $10 M (in 1994 dollars, of course) and could break MD5 in about 20 days. (This follows the 1993 paper on a similar machine to break DES.)

  • Hal Finney did some calculations and reported to us:
  • "I mentioned a few days ago that one of the "rump session" papers at the crypto conference claimed that a machine could be built which would find MD5 collisions for $10M in about 20 days...The net result is that we have taken virtually no more time (the 2Л64 creations of MD5 will dominate) and virtually no space (compared to 2Л64 stored values) and we get the effect of a birthday attack. This is another cautionary data point about the risks of relying on space costs for security rather than time costs." [Hal Finney, 1994-09-09]

5.11.6. pkzip reported broken

  • "I finally found time to take a closer look at the encryption algorithm by Roger Schlafly that is used in PKZIP and have developed a practical known plaintext attack that can find the entire 96-bit internal state." [Paul Carl Kocher, comp.risks, 1994-09-04]

5.11.7. Gaming attacks, where loopholes in a system are exploited

  • contests that are defeated by automated attacks
  • the entire legal system can be viewed this way, with competing teams of lawyers looking for legal attacks (and the more complex the legal code, the more attacks can be mounted)
  • ecologies, where weaknesses are exploited ruthlessly, forcing most species into extinction
  • economies, ditto, except must faster
  • the hazards for crypto schemes are clear
  • And there are important links to the issue of overly formal systems, or systems in which ordinary "discretion" and "choice" is overridden by rules from outside
    • as with rules telling employers in great detail when and how they can discharge employees (cf. the discussion of "reasonable rules made mandatory," elsewhere)
    • such rules get exploited by employees, who follow the "letter of the law" but are performing in a way unacceptable to the employer
    • related to "locality of reference" points, in that problem should be resolved locally, not with intervention from afar.
    • things will never be perfect, from the perspetive of all parties, but meddling from outside makes things into a game, the whole point of this section
    • Implications for digital money: overly complex legal systems, without the local advantages of true cash (settled locally)
  • may need to inject some supra-legal enforcement mechanisms into the system, to make it converge
  • offshore credit databases, beyond reach of U.S. and other laws
  • physical violence (one reason people don't "play games" with Mafia, Triads, etc., is that they know the implications)
  • it's not unethical, as I see it, for contracts in which the parties understand that a possible or even likely consequence of their failure to perform is death

5.11.8. Diffie-Hellman key exchange vulnerabilities

  • "man-in-the-midle" attack
  • phone systems use voice readback of LCD indicated number
  • as computer power increases, even this may be insufficient

5.11.9. Reverse engineering of ciphers

  • A5 code used in GSM phones was reverse engineered from a hardware description
  • Graham Toal reports (1994-07-12) that GCHQ blocked a public lectures on this

5.12. Loose Ends

5.12.1. "Chess Grandmaster Problem" and other Frauds and Spoofs

  • of central importance to proofs of identity (a la Fiat- Shamir)
    • "terrorist" and "Mafia spoof" problems
No Comments
Back to top