From jimbell@pacifier.com Tue Dec 26 23:36:19 1995 Xref: elastic sci.crypt:6252 talk.politics.crypto:2407 Path: elastic!exorcist!lethe!abyss!news2.compulink.com!news.compulink.com!news1.toronto.fonorola.net!news1.toronto.istar.net!news.toronto.istar.net!torn!howland.reston.ans.net!newsfeed.internetmci.com!uwm.edu!homer.alpha.net!pacifier!news From: jimbell@pacifier.com (jimbell) Newsgroups: talk.politics.crypto,alt.security.pgp,sci.crypt,alt.privacy,alt.privacy.anon-server,alt.privacy.clipper Subject: Spread-Spectrum computer clock? Date: Sun, 24 Dec 1995 07:59:22 GMT Organization: Pacifier BBS, Vancouver, Wa. ((360) 693-0325) Lines: 145 Message-ID: <4bj19t$hcl@news.pacifier.com> NNTP-Posting-Host: ip93.van3.pacifier.com X-Newsreader: Forte Free Agent 1.0.82 Recently there has been a substantial amount of discussion concerning the use of accurate timing in an attempt to uncover encryption keys, by carefully noting the length of time that a decryption takes in a computer of a known cpu speed. I have noticed that most of the discussion focussed on the delay time of the overall operation done over a network, for example a LAN or perhaps the Internet, but it has been recognized that imprecision due to indeterminate network timings make such a tactic problematic at least. However, being a ham and occasionally listening to the various odd noises produced by a computer when you tune a VHF or UHF ham radio to a harmonic of the clock speed, it ccurred to me that the delay times WITHIN a particular encryption/decryption would be far more easily measured with local RF snooping. I would imagine that if you can determine even a fraction of a bit of key from a network "ping," you could do a lot better "listening" to the execution of a program within a few hundred feet with an ordinary radio receiver and a sophisiticated analysis program. Okay, I admit, this is certainly not a new idea. The military's TEMPEST program is to build electronic equipment which is so "quiet" that it is impossible (or, at least, arbitrarily difficult) to capture useful information by inadvertent radio transmission. Obviously, that is out of the league (not to mention the budget) of the vast majority of the users of personal computers. Nevertheless, it seems to me that if we as a community of computer users are interested in security, we should not merely focus on the mathematics and algorithms used and their reliability, but also secondary methods to break the systems involved. True, most of us are not sufficiently interesting "targets" to justify this kind of attack, but machines such as encrypted remailers are sufficiently "high value" that protecting them would be worth a little extra effort I'm not under any illusion that we can hope to make them "snoop-proof", but a little effort should substantial raise the difficulty level.. More than a year ago, it occurred to me that it might be worth it to build a CPU clock replacement module that took the place of the main CPU crystal oscillator, and replaced it with a oscillator module whose frequency was (very long period!) pseudorandomly varied, possibly with a resolution of 16-bit and over a range of perhaps 1%., with the frequency varying every few tens or hundreds of microseconds. The result, I presume, is that every operation synchronized to the microprocessor clock would vary in time and would be hard to "tune" with a normal radio receiver. It seems to me that this would make the resulting computer harder to "bug" using standard equipment. If this were do-able and were in fact done, it would probably be worth it to "tailor" the spectrum of variation in clock speed so that these variations do not tend to average out over "long" times, for example a few hundred milliseconds or even tens of seconds. This would at least help to disguise the decryption-time information that is commonly discussed. A complicating factor is the fact that modern motherboards often generate their microprocessor clocks using PLL synthesis from a master clock, probably the 14.318 MHz clock. On the one hand, that might make the process easier; only one clock to vary. On the other, it is at least conceivable that there are some devices in any given computer which depend on a precisely constant clock speed, and would not tolerate such variation. This was probably more true in the early days of the IBM PC; today you usually see separate crystals on any cards that need truly specific frequencies. (Hey, I didn't say this was a perfect solution, merely one that would raise the barrier a bit...) Other potential tactics. (Some of which are already happening; if anybody out there is more informed about such techniques, please tell me) 0. Copper-screen cages. Okay, maybe this appears to be a bit too obvious, but it really isn't too involved: A few years ago, I happened onto a roll of honest-to-goodness copper screen; sort of line window screen but made of pure copper. Sewn/soldered into a bag, it would make an excellent cover. (openings required for floppies and CDROMS, as well as cables are obviously a complication, but... 1. Use CPUs with Internal caches as well as external caches, both to reduce the amount of electronic noise transmitted to antenna-length wires outside the microprocessors, as well as make external memory accesses less predictable and less frequent. Fortunately, I suppose, the natural transition to 486's, DX2's and DX4/4s) and Pentiums has make this happen without any anti-snooping motivaition. 2. Eventually, CRT's will be replaced with some sort of matrix-type displays that emit far less useable information and will be easier to shield. 3. Filtering of every wire that comes out of the computer's case, primarily using a combination of ferrite beads and decoupling capacitors. This would be especially true of the telephone line, which would be accessible from outside a house or office. Also, use of multiple powerline filters/surge protectors in series. 4. I'd pay particular attention to the keyboard interface and its associated microcontroller: Years ago, I speculated that if a VFO (voltage to frequency converter) was placed on the data line between the keyboard and the computer, it would transmit the identity of every key pressed. (This would obviously include passwords, too) (Does the keyboard hardware of the typical PC allow echobacks, whcih would allow the CPU to fill the CPU/Keyboard channel with apparently meaningless random garbage, thwarting RF overhearing of this data?!?) And I wouldn't be surprised if the NSA has built replacement keyboard controllers to be used to surreptiously replace on garden-variety keyboards, controllers which deliberately "broadcast" such information in an even easier-to-discern pattern. Even a short access to such a keyboard and it might be telling your secrets. Even if a black-bag job wasn't possible, If it were possible to tune to its normal keyboard microprocessor operation rate, and given a known keyboard scan pattern a particular pressed key could be identified. Given how cheap keyboards are these days, a slightly paranoid person might buy one from a trustworthy source and glue the case shut to prevent tampering, and replace it monthly with cast-offs. 5. While this isn't my area of expertise, it occurs to me that softrware should be written to complete operations in an identical time frame, no matter the input data. While this has already been hashed over on the nets, the "solution" that is typically discussed involves adding a null loop at the end of the real operation, and contining only after the "wall clock" shows enough time has passed. This isn't an adequate solution, I think, if local RFmonitoring of the computer can be done. (It will know when the actual result ended) A better (and, sadly, more inefficient) method would involve executing BOTH branches of conditional jump, and only using the data generated from the desired half at the very end.. Another possibility might be (for certain large mathematical algorithms) is to split up the functions and to execute them in a "random" order, with enough "dummy" operations inserted to further disguise the facts. For example, if you're multiplying two 1024-bit values to get a 2048-bit result, program this to be done in a pseudrandom order and intersperse any operations with pseudorandom operations to disguise it. (A pseudorandom interrupt generator might help, here.) 6. Think like an NSA hack. If I were such a sneaky bastard, I'd try to figure out a way to module a visible LED on the computer's case with data, or modulate the video display's brightness to signal slow-speed data.. Well, that's just a few thoughts. There's a lot more material out there that ought to be discussed. Admittedly, these subjects can appear to be a bit more than a little paranoid, but without such discussion we're almost certain to be at risk. From dhenson@1eagle1.com Tue Feb 13 07:49:20 1996 Xref: elastic sci.crypt:6923 talk.politics.crypto:3628 Path: elastic!exorcist!lethe!geac!onramp.ca!grumpy.insinc.net!news.sprintlink.net!news.itsnet.com!usenet From: Don Henson Newsgroups: talk.politics.crypto,sci.crypt Subject: Phil's Free! Let's Keep Up the Pressure Date: 12 Feb 1996 15:01:24 GMT Organization: West El Paso Information Network Lines: 32 Message-ID: <4fnko4$cdg@itchy.itsnet.com> NNTP-Posting-Host: ep202.itsnet.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 1.1 (Windows; U; 16bit) Phil Zimmerman, author of Pretty Good Privacy (PGP), has been notified that he will not be prosecuted under the ITAR for allowing PGP to be exported. His problems are over, at least for now. However, the ITAR is still being used to 'convince' software companies to produce software without effective encryption functions. Let's keep up the pressure. One way to do that is to wear the Munition T-shirt which contains the code (human and machine readable) for an implementation of the RSA algorithm and which loudly proclaims that this t-shirt is a munition. Get your t- shirt today. If you don't know about the Munition T-shirt, just send email to wepinsto@colossus.net with a subject of 'TSHIRT STORY' and you will receive full details via return email. For more information on how to own this classic example of civil disobedience, just send email to wepinsto@colossus.net with the subject of 'SHIRT'. (You don't have to be a US/Canadian citizen to request the info.) Or, if you have WWW access, just point your Web browser to: http://colossus.net/wepinsto/wsft_f/wspp_f/wsppts.html You can read about the t-shirt, see pictures of the t-shirt, and order it online using a personal check (yes, you can do that on line). -- Don Henson, Managing Director (PGP Key ID = 0X03002DC9) West El Paso Information Network (WEPIN) email: wepinsto@colossus.net Check out The WEPIN Store at URL: http://colossus.net/wepinsto/wshome.html From elastic!lethe!abyss!news2.compulink.com!news3.idirect.com!n2tor.istar!tor.istar!east.istar!ott.istar!istar.net!van.istar!west.istar!n1van.istar!van-bc!unixg.ubc.ca!news.bc.net!info.ucla.edu!nnrp.info.ucla.edu!ihnp4.ucsd.edu!munnari.OZ.AU!comp.vuw.ac.nz!auckland.ac.nz!news Thu Jul 25 07:34:08 1996 Xref: elastic sci.crypt.research:278 Path: elastic!lethe!abyss!news2.compulink.com!news3.idirect.com!n2tor.istar!tor.istar!east.istar!ott.istar!istar.net!van.istar!west.istar!n1van.istar!van-bc!unixg.ubc.ca!news.bc.net!info.ucla.edu!nnrp.info.ucla.edu!ihnp4.ucsd.edu!munnari.OZ.AU!comp.vuw.ac.nz!auckland.ac.nz!news From: Matt Blaze Newsgroups: sci.crypt.research Subject: NSA response to key length paper Date: 20 Jul 1996 06:12:46 GMT Organization: AT&T Lines: 127 Sender: crypt-submission@cs.aukuni.ac.nz (sci.crypt.research co-moderator) Approved: crypt-submission@cs.aukuni.ac.nz Message-ID: <4sptcu$miq@net.auckland.ac.nz> Reply-To: Matt Blaze NNTP-Posting-Host: kiwi.cs.auckland.ac.nz X-Newsreader: NN version 6.5.0 #4 (NOV) July 18, 1996 There is currently being circulated, to members of Congress and possibly elsewhere, a four page document entitled ``Brute-Force Cryptanalytic Attacks'' that calls into question some of the conclusions of the ``Minimum Key Lengths for Symmetric Ciphers'' white paper [1]. The document bears no author or organization attribution, but we are told that it originated from NSA. The NSA document argues that ``physical realities'' make parallel key search much more expensive and time consuming than our white paper estimated. However, the NSA document appears to have been written from the perspective of general parallel processing or cryptanalysis rather than exhaustive key search per se. It ignores several elementary principles of parallel processing that apply specifically to exhaustive key search machines of the type that our white paper considered. In particular, NSA argues that interconnections, heat dissipation, input/output bandwidth, and interprocessor communication make it difficult to ``scale up'' a key search machine by dividing the task among a large number of small components. While these factors do limit the scalability of more general purpose multiprocessor computers (such as those made by Cray), they do not apply at all to specialized exhaustive key search machines. The NSA argument ignores the most fundamental feature of brute-force key search: the processors performing the search have no need to communicate with other components of the system while they perform their share of the search, and therefore the system has no need for any of the global interconnections that limit scaling. Indeed, there is no reason that all the components of a parallel search machine must be located even within the same city, let alone the same computer housing. We note that one of our co-authors (Eric Thompson, of Access Data, Inc.) designs and builds medium-scale FPGA-based key search machines with exactly this loosely-coupled structure, and regularly uses them to recover keys for clients that include the FBI. The NSA document also calls into question our cost estimates for ASIC components, suggesting that ASIC chips of this type cost NSA approximately $1000.00 each. However, our $10.00 per chip estimate is based on an actual price quote from a commercial chip fabrication vendor for a moderate-size order for an exhaustive search ASIC designed in 1993 by Michael Wiener [2]. Perhaps NSA could reduce its own costs by changing vendors. Finally, the NSA report offers estimates of the time required to perform exhaustive search using a Cray model T3D supercomputer. This is a curious choice, for as our report notes, general-purpose supercomputers of this type make poor (and uneconomical) key search engines. However, even the artificially low performance results for this machine should give little comfort to the users of 56 bit keys. According to NSA, 56 bit keys can be searched on such a machine in less than 453 days. ``Moore's law'' predicts that it will not be long before relatively inexpensive general-purpose computers offer similar computational capability. /s/ Matt Blaze Whitfield Diffie References: [1] Blaze, M., Diffie, W., Rivest, R., Schneier, B., Shimomura, T., Thompson, E., and Wiener, M. ``Minimum Key Lengths for Symmetric Key Ciphers for Commercial Security.'' January 1996. Available from ftp://ftp.research.att.com/dist/mab/keylength.txt [2] Wiener, M. ``Exhaustive DES Key Search.'' Presented at Crypto-93, Santa Barbara, CA. August 1993. ========================================================================= [Transcription of document circulated to various members of congress and others in June, 1996, apparently by NSA] BRUTE-FORCE CRYPTANALYTIC ATTACKS Two published theoretical estimates of cost versus time to perform brute-force hardware attacks on selected cryptography key lengths differ between themselves and differ significantly from what we find when we buy or build computers to carry out such attacks. The differences lie in assumptions made in the theoretical estimates, which are not fully spelled out by the authors, and in scaling up hypothesized small machines to ever larger ones without accounting for physical realities. The factors not accounted for are: o R&D costs for the first machine, typically on the order of $10 million. o As more and more chips are added to a machine, two effects occur: o Interconnections increase and increase running time; o Heat from the chips eventually limit [sic] the size of a machine. o Memory costs are not included. o When get [sic] to the very fast processing speed estimates, machines can become Input/Output bound; so [sic] it cannot achieve the estimated speed. o Assuming every algorithm can be tested in same amount of time and key length is the only difference. Table 1 are [sic] the average time estimates made for a given cost done by Michael Wiener of Bell Norther Research in 1995. These are published in Bruce Schneier's Applied Cryptography book. Note that these are average times, one-half of the total exhaust time. Table 2 are [sic] the estimates for total exhaust times using Field Programmmable Gate Arrays (FPGA) and Application Specific ICs (ASICs) done for the Business Software Alliance by Blaze, Diffie, Rivest, Schneier, Shimomura, Thompson, and Wiener in 1996. In addition to the above factors not accounted for they have assumed ASICs cost as low as $10. We find ASICs more typically cost $1000 and their capabilities can vary considerably depending upon the specific task. Table 3 are out estimates based on our experience with a Cray T3D supercomputer with 1024 nodes. This machine costs $30 million. [Tables 1, 2, and 3 not transcribed here.] From elastic!lethe!geac!onramp.ca!news2.insinc.net!news.sprintlink.net!news-pen-14.sprintlink.net!newsfeed.internetmci.com!in2.uu.net!news.iadfw.net!usenet Mon Aug 5 19:17:02 1996 Xref: elastic sci.crypt:10419 talk.politics.crypto:5050 Path: elastic!lethe!geac!onramp.ca!news2.insinc.net!news.sprintlink.net!news-pen-14.sprintlink.net!newsfeed.internetmci.com!in2.uu.net!news.iadfw.net!usenet From: rmashlan@r2m.com (Robert Mashlan) Newsgroups: sci.crypt,alt.security.pgp,talk.politics.crypto Subject: Goodbye Encryption???? Date: Tue, 30 Jul 1996 09:01:52 GMT Organization: R2M Software Company Lines: 22 Message-ID: <31fdcd6c.1263840@library.airnews.net> NNTP-Posting-Host: sea2.seasurf.com X-Newsreader: Forte Agent .99e/32.227 I just read a news brief on Time's Pathfinder called "World Leaders to Adopt Anti-Terrorism Steps" The URL is http://pathfinder.com/welcome/latest/RB/1996Jul30/24.html Some excerpts from this article: "PARIS (Reuter) - The world's major powers will debate in Paris Tuesday how far they can go in waging a global war on terrorism without confronting each other in a trade war or violating civil rights." "The proposals include such seemingly obvious measures as pooling intelligence, sharing know-how and easing extradition, as well as moves to dry up the supply of funds and weapons to bombers and ways to prevent guerrillas exploiting the Internet." "-- better control of the public Internet, with legislation to ban private encryption of content on the worldwide computer network and ban incitement to and instruction in terrorism " From elastic!lethe!gts!torfree!tor-nn1.netcom.ca!news Mon Nov 4 08:20:57 1996 Xref: elastic sci.crypt:11294 Path: elastic!lethe!gts!torfree!tor-nn1.netcom.ca!news From: seward@netcom.ca(Vaughn Herbert Seward) Newsgroups: sci.crypt Subject: 512-bit RSA broken? (was: Re: Crypted Austian letter bomb warning) Date: 23 Oct 1996 03:58:15 GMT Organization: Netcom Canada Lines: 37 Message-ID: <54k54n$cdv@tor-nn1-hb0.netcom.ca> References: <325B503F.4557@siemens.at> NNTP-Posting-Host: edm-ab3-32.netcom.ca X-NETCOM-Date: Tue Oct 22 11:58:15 PM EDT 1996 I found the following in comp.security.pgp.discuss, being motivated to expand my coverage of the PGP-related newsgroups, and noticed this post, which appears to be of interest on this group: In <325B503F.4557@siemens.at> Kurt Siegl writes: > >Hi, > >Does anyone knows details about the coding of the Austrian letter >bomb warning? > >From what I know it was crypted with a 512 bit RSA(PGP) key. >Is that true? > >The US NSA was able to decode the letter within one week, by exploiting >the mathematic model, in other words brute force factorisation. > >The Austrian security agency cheated a little and where able to >decode it even earlier by knowing the witing style and guessing >the letter content. Verification of the correctness of a PGP code >is trivial as we all know. But guessing a 5 pages letter in a few days >is still an awsome good job. > >As conclusion, if my asumtions are right and it was a 512bit PGP >code which can be brute force cracked by NSA within a week, >we cannot consider 512 bit keys as secure anymore. > >So I will have to increase my PGP key to at least 1024 now :( > >Kurt > >-- >Kurt Siegl / SIEMENS PSE KB HAG / Softwarepark / A-4232 Hagenberg >Email: kurt.siegl@siemens.at Tel: (+43)7236/3720-27