Crypto

2.5.1. "Why is crypto so important?" + 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 - Although there is no explicit "right of privacy" enumerated in the U.S. Constitution, the assumption that an individual is to be secure in his papers, home, etc., absent a valid warrant, is central. (There has never been a ruling or law that persons have to speak in a language that is understandable by eavesdroppers, wiretappers, etc., nor has there ever been a rule banning private use of encrption. I mention this to remind readers of the long history of crypto freedom.) - "Information, technology and control of both _is_ power. *Anonymous* telecommunications has the potential to be the greatest equalizer in history. Bringing this power to as many as possible will forever change the discourse of power in this country (and the world)." [Matthew J Miszewski, ACT NOW!, 1993-03-06] 2.5.2. "Who uses cryptography?" - Everybody, in one form or another. 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. Lock combinations, door keys, PIN numbers, etc. All are part of crypto (although most might call this "security" and not a very mathematical thing, as cryptography is usually thought to be). - Whitticism: "those who regularly conspire to participate in the political process are already encrypting." [Whit Diffie] 2.5.3. "Who needs crypto? What have they got to hide?" + honest people need crypto because there are dishonest people - and there may be other needs for privacy - There are many reasons why people need privacy, the ability to keep some things secret. Financial, personal, psychological, social, and many other reasons. - Privacy in their papers, in their diaries, in their pesonal lives. In their financial choices, their investments, etc. (The IRS and tax authorities in other countries claim to have a right to see private records, and so far the courts have backed them up. I disagree.) - people encrypt for the same reason they close and lock their doors - Privacy in its most basic forms 2.5.4. "I'm new to crypto--where should I start?" - books...Schneier - soda - sci.crypt - talk.politics.crypto - FAQs other than this one 2.5.5. "Do I need to study cryptography and number theory to make a contribution?" - Absolutely not! Most cryptographers and mathematicians are so busy doing their thing that they little time or interest for political and entrepreneurial activities. Specialization is for insects and researchers, as someone's .sig says. - Many areas are ripe for contribution. Modularization of functions means people can concentrate in other areas, just as writers don't have to learn how to set type, or cut quill pens, or mix inks. - Nonspecialists should treat most established ciphers as "black boxes" that work as advertised. (I'm not saying they do, just that analysis of them is best left to experts...a little skepticism may not hurt, though). 2.5.6. "How does public key cryptography work, simply put?" - Plenty of articles and textbooks describe this, in ever- increasing detail (they start out with the basics, then get to the juicy stuff). + I did find a simple explanation, with "toy numbers," from Matthew Ghio: - "You pick two prime numbers; for example 5 and 7. Multiply them together, equals 35. Now you calculate the product of one less than each number, plus one. (5-1)(7- 1)+1=21. There is a mathematical relationship that says that x = x^21 mod 35 for any x from 0 to 34. Now you factor 21, yeilds 3 and 7. "You pick one of those numbers to be your private key and the other one is your public key. So you have: Public key: 3 Private key: 7 "Someone encrypts a message for you by taking plaintext message m to make ciphertext message c: c=m^3 mod 35 "You decrypt c and find m using your private key: m=c^7 mod 35 "If the numbers are several hundred digits long (as in PGP), it is nearly impossible to guess the secret key." [Matthew Ghio, alt.anonymous, 1994-09-03] - (There's a math error here...exercise left for the student.) 2.5.7. "I'm a newcomer to this stuff...how should I get started?" - Start by reading some of the material cited. Don't worry too much about understanding it all. - Follow the list. - Find an area that interests you and concentrate on that. There is no reason why privacy advocates need to understand Diffie-Hellman key exchange in detail! + More Information + Books - Schneier - Brassard + Journals, etc - Proceedings - Journal of Cryptology - Cryptologia - Newsgroups - ftp sites 2.5.8. "Who are Alice and Bob?" 2.5.9. "What is security through obscurity"? - adding layers of confusion, indirection - rarely is strong in a an infromation-theoretic or cryptographic sense - and may have "shortcuts" (like a knot that looks complex but which falls open if approached the right way) - encryption algorithms often hidden, sites hidden - Make no mistake about it, these approaches are often used. And they can add a little to the overall security (using file encyption programs like FolderBolt on top of PGP is an example)... 2.5.10. "Has DES been broken? And what about RSA?" - DES: Brute-force search of the keyspace in chosen-plaintext attacks is feeasible in around 2^47 keys, according to Biham and Shamir. This is about 2^9 times easier than the "raw" keyspace. Michael Wiener has estimated that a macine of special chips could crack DES this way for a few thousand dollars per key. The NSA may have such machines. - In any case, DES was not expected to last this long by many (and, in fact, the NSA and NIST proposed a phaseout some years back, the "CCEP" (Commercial COMSEC Endorsement Program), but it never caught on and seems forgotten today. Clipper and EES seem to have grabbed the spotlight. - IDEA, from Europe, is supposed to be much better. - As for RSA, this is unlikely. Factoring is not yet proven to be NP-co 2.5.11. "Can the NSA Break Foo?" - DES, RSA, IDEA, etc. - Can the government break our ciphers? 2.5.12. "Can brute-force methods break crypto systems?" - depends on the system, the keyspace, the ancillary information avialable, etc. - processing power generally has been doubling every 12-18 months (Moore's Law), so.... - Skipjack is 80 bits, which is probably safe from brute force attack for 2^24 = 1.68e7 times as long as DES is. With Wiener's estimate of 3.5 hours to break DES, this implies 6700 years using today's hardware. Assuming an optimistic doubling of hardware power per year (for the same cost), it will take 24 years before the hardware costs of a brute force attack on Skipjack come down to what it now costs to attack DES. Assuming no other weaknesses in Skipjack. - And note that intelligence agencies are able to spend much more than what Wiener calculated (recall Norm Hardy's description of Harvest) 2.5.13. "Did the NSA know about public key ideas before Diffie and Hellman?" + much debate, and some sly and possibly misleading innuendo - Simmons claimed he learned of PK in Gardner's column, and he certainly should've been in a position to know (weapons, Sandia) - + Inman has claimed 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) 2.5.14. "Did the NSA know about public-key approaches before Diffie and Hellman?" - comes up a lot, with some in the NSA trying to slyly suggest that _of course_ they knew about it... - Simmons, etc. - Bellovin comments (are good) 2.5.15. "Can NSA crack RSA?" - Probably not. - Certainly not by "searching the keyspace," an idea that pops up every few months . It can't be done. 1024-bit keys implies roughly 512-bit primes, or 153-decimal digit primes. There are more than 10^150 of them! And only about 10^73 particles in the entire universe. - Has the factoring problem been solved? Probably not. And it probably won't be, in the sense that factoring is probably in NP (though this has not been proved) and P is probably not NP (also unproved, but very strongly suspected). While there will be advances in factoring, it is extremely unlikely (in the religious sense) that factoring a 300- digit number will suddenly become "easy." - Does the RSA leak information so as to make it easier to crack than it is to factor the modulus? Suspected by some, but basically unknown. I would bet against it. But more iffy than the point above. + "How strong is strong crypto?" - Basically, stronger than any of the hokey "codes" so beloved of thriller writers and movie producers. Modern ciphers are not crackable by "telling the computer to run through all the combinations" (more precisely, the number of combinations greatly exceeds the number of atoms in the universe). 2.5.16. "Won't more powerful computers make ciphers breakable?" + The effects of increasing computer power confer even *greater* advantage to the cipher user than to the cipher breaker. (Longer key lengths in RSA, for example, require polynomially more time to use, but exponentially more time to break, roughly speaking.) Stunningly, it is likely that we are close to being able to use key lengths which cannot be broken with all the computer power that will ever exist in the universe. + Analogous to impenetrable force fields protecting the data, with more energy required to "punch through" than exists in the universe - Vernor Vinge's "bobbles," in "The Peace War." - Here I am assuming that no short cuts to factoring exist...this is unproven, but suspected. (No major shortcuts, i.e., factoring is not "easy.") + A modulus of thousands of decimal digits may require more total "energy" to factor, using foreseeable approaches, than is available - reversible computation may help, but I suspect not much - Shor's quantum-mechanical approach is completely untested...and may not scale well (e.g., it may be marginally possible to get the measurement precision to use this method for, say, 100-digit numbers, but utterly impossible to get it for 120-digit numbers, let alone 1000-digit numbers) 2.5.17. "Will strong crypto help racists?" - Yes, this is a consequence of having secure virtual communities. Free speech tends to work that way! - The Aryan Nation can use crypto to collect and disseminate information, even into "controlled" nations like Germany that ban groups like Aryan Nation. - Of course, "on the Internet no one knows you're a dog," so overt racism based on superficial external characteristics is correspondingly harder to pull off. - But strong crypto will enable and empower groups who have different beliefs than the local majority, and will allow them to bypass regional laws. 2.5.18. Working on new ciphers--why it's not a Cypherpunks priority (as I see it) - It's an issue of allocation of resources. ("All crypto is economics." E. Hughes) Much work has gone into cipher design, and the world seems to have several stable, robust ciphers to choose from. Any additional work by crypto amateurs--which most of us are, relative to professional mathematicians and cipher designers--is unlikely to move things forward significantly. Yes, it could happen...but it's not likely. + Whereas there are areas where professional cryptologists have done very little: - PGP (note that PRZ did *not* take time out to try to invent his own ciphers, at least not for Version 2.0)...he concentrated on where his efforts would have the best payoff - implementation of remailers - issues involving shells and other tools for crypto use - digital cash - related issues, such as reputations, language design, game theory, etc. - These are the areas of "low-hanging fruit," the areas where the greatest bang for the buck lies, to mix some metaphors (grapeshot?). 2.5.19. "Are there any unbreakable ciphers?" - One time pads are of course information-theoretically secure, i.e., unbreakable by computer power. + For conventional ciphers, including public key ciphers, some ciphers may not be breakable in _our_ universe, in any amount of time. The logic goes as follows: - Our universe presumably has some finite number of particles (currently estimated to be 10^73 particles). This leads to the "even if every particle were a Cray Y- MP it would take..." sorts of thought experiments. But I am considering _energy_ here. Ignoring reversible computation for the moment, computations dissipate energy (some disagree with this point). There is some uppper limit on how many basic computations could ever be done with the amount of free energy in the universe. (A rough calculation could be done by calculating the energy output of stars, stuff falling into black holes, etc., and then assuming about kT per logical operation. This should be accurate to within a few orders of magnitude.) I haven't done this calculation, and won't here, but the result would likely be something along the lines of X joules of energy that could be harnessed for computation, resulting in Y basic primitive computational steps. I can then find a modulus of 3000 digits or 5000 digits, or whatever, that takes *more* than this number of steps to factor. Therefore, unbreakable in our universe. - Caveats: 1. Maybe there are really shortcuts to factoring. Certainly improvements in factoring methods will continue. (But of course these improvements are not things that convert factoring into a less than exponential-in-length problem...that is, factoring appears to remain "hard.") 2. Maybe reversible computations (a la Landauer, Bennett, et. al.) actually work. Maybe this means a "factoring machine" can be built which takes a fixed, or very slowly growing, amount of energy. In this case, "forever" means Lefty is probably right. 3. Maybe the quantum-mechanical idea of Peter Shor is possible. (I doubt it, for various reasons.) 2.5.20. "How safe is RSA?" "How safe is PGP?" "I heard that PGP has bugs?" - This cloud of questions is surely the most common sort that appears in sci.crypt. It sometimes gets no answers, sometimes gets a rude answer, and only occasionally does it lead to a fruiful discussion. - The simple anwer: These ciphers appear to be safe, to have no obvious flaws. - More details can be found in various question elsewhere in this FAQ and in the various FAQs and references others have published. 2.5.21. "How long does encryption have to be good for?" - This obviously depends on what you're encrypting. Some things need only be safe for short periods of time, e.g., a few years or even less. Other things may come back to haunt you--or get you thrown in prison--many years later. I can imagine secrets that have to be kept for many decades, even centuries (for example, one may fear one's descendents will pay the price for a secret revealed). - It is useful to think _now_ about the computer power likely to be available in the year 2050, when many of you reading this will still be around. (I'm _not_ arguing that parallelism, etc., will cause RSA to fall, only that some key lengths (e.g., 512-bit) may fall by then. Better be safe and use 1024 bits or even more. Increased computer power makes longer keys feasible, too.).

Next Page: 2.6 PGP

Previous Page: 2.4 Organizational

By Tim May, see README

HTML by Jonathan Rochkind