Cyphernomicon Top
Cyphernomicon 5.5

Cryptology:
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 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