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)
By Tim May, see README
HTML by Jonathan Rochkind