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