[ Pobierz całość w formacie PDF ]
.If this is the case, we say thatthe opponent is in a position to mount a known-plaintext attack.At the time of World War II, the belligerents, not trusting their cryptosystems to resist known-plaintextattacks, imposed such signaling rules as "No message transmitted in cipher may ever be sent in clear."In fact a message sent in cipher could never be declassified without being paraphrased to reduce itscryptanalytic utility.This problem appears to have been solved for US government cryptosystems bythe 1960s, permitting formerly encrypted messages to be declassified on the basis of content alone.The sort of signaling rules formerly used by the military are entirely infeasible in a commercialenvironment.Fortunately, trust in modern electronic cryptosystems is sufficient that the availabilityof plaintext to an opponent makes no difference.In fact, we presume that the opponent can send anarbitrary number of text messages and will receive our cooperation in enciphering them ordeciphering them before beginning to attack the actual message of interest.This is called the chosen-plaintext assumption.15WorkfactorsTime is the essential element in measuring computation.The question is "How much will it cost meto get the answer when I need it?" It is a rule of thumb that computing power doubles every 18months;16 thus a personal computer purchased for $1000 today will have twice the computing powerof one purchased less than 2 years ago.17 These improvements in speed have profound implicationsfor cryptographic systems. The number of operations required to break a cryptographic system is called its workfactor.The formor complexity of the operations is not precisely stated.They might be encryptions, as they are whenthe analytic process is one of searching through the keys, or they might be something entirelydifferent.In a spirit of oversimplification, we will assume that operations are always entirelyparallelizable.If two processors can do a million operations in 5 seconds, then ten processors can dothe same number of operations in 1 second.For our purposes, this assumption is conservative in thesense that if it is false the problem merely becomes somewhat harder.If a system has a workfactor of 230, it can be broken by a billion operations.These may not beelementary computer instructions; they may be complex operations requiring hundreds of instructionseach.Even so, many desktop computers today can do a billion instructions in 5 seconds.If such acryptosystem requires several hundred instructions per encryption, it can be searched in under anhour.In short, breaking a system with a workfactor of 230 is trivial.A workfactor of 260 means that a million processors, each doing a million operations a second, cansolve the problem in a million seconds (between 11 and 12 days).It is clear that a system with aworkfactor of 260 can be broken today if the analytic operations are such that processors capable ofexecuting them are worth building or already available.If the operations are encryptions, theprocessors might be built from available encryption processors.On this path, systems with workfactors of 290 are the first that seem beyond reach for the foreseeablefuture.A billion processors in parallel can certainly be imagined.A billion operations a second, evenoperations as complex as DES encryptions, have been achieved (Eberle 1992).A billion seconds,however, is 30 years-long enough to count as secure for most applications.18Workfactors of 2120 seem beyond reach for the indefinite future.A trillionth of a second is less thanone gate delay in the fastest experimental technologies; a trillion processors operating in parallel isbeyond reach; and a trillion seconds is 30,000 years.Estimating the cost of searching through keys and validating the estimates by actually doing it havebecome sports in the cryptographic community.In the fall of 1995 a group of cryptographers met andprepared an estimate of search costs, concluding that 40-bit keys (the largest that could be readilyexported) could easily be searched and that keys at least 70 to 90 bits long were needed to providesecurity for commercial applications (Blaze et al.1996).The previous August, students at the EcôlePolytechnique in Paris had searched out a 40-bit key.The following January, students at MITrepeated the feat using an $83,000 graphics computer
[ Pobierz całość w formacie PDF ]
