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 (b^x) 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
(b^x) mod p
and
(b^y) mod p
and transmit them to each other. Now, X knows x and
(b^y) mod p, so s/he can calculate (b^y)^x mod p =
(b^(xy)) mod p. Y can do the same calculation. Now
they both know (b^(xy)) mod p. But eavesdroppers know
only (b^x) mod p and (b^y) 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
(b^X) 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 1X10^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.)
By Tim May, see README
HTML by Jonathan Rochkind