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)
Next Page: 5.6 Crypto Programs and Products
Previous Page: 5.4 Crypto Basics
By Tim May, see README
HTML by Jonathan Rochkind