NYC Crypto Talk
For those in the NYC-area, Michael Anshel writes: I'm scheduled to speak to my colleagues in the Physics Dept at CCNY some of whom have co-taught with me Quantum Computing and Cryptography. The announcement is below. THE CITY COLLEGE OF THE CITY UNIVERSITY OF NEW YORK NEW YORK, NY 10031 DEPARTMENT OF PHYSICS J419 Telephone: 2l2-650-6832 SOLID STATE SEMINAR Date/Time: Wed. Nov.24,1999 12:15 pm Place: Room J418 Speaker: Prof. Michael Anshel Dept. of ComputerSciences,CCNY-CUNY Title: Cryptography for Physicists Abstract: Methods of constructing public key cryptosystems via combinatorial group theory. By all means let interested parties know. I very much appreciate your help Michael http://www-cs.engr.ccny.cuny.edu/~csmma/ PS: My co-workers are my daughter Iris Anshel and her husband (and my son-in-law) Dorian Goldfeld. cc: David Molnar, Bob Karash, Jean-Jacques Quisquater, Iris Anshel and Dorian Goldfeld - See Anshel's paper, "Constructing Public Key Cryptosystems Via Combinatorial Group Theory:" http://cryptome.org/pkc-cgt.htm
Re: DPA mapped to spectral analysis
"Marcus Leech" wrote on 1999-11-19 19:45 UTC: Has anyone considered experimenting with DPA (Differential Power Analysis), but using spectral data, instead of power consumption? Different operations will produce different EM spectra, and so the attack should work, given suitable selection of frequency range. This could potentially allow the bad guy to attack a card without having access to the card, using a suitably directional antenna, etc. We are working on experiments along such lines. The information carrying components of the power spectrum extend even for a 3.5 MHz clock microcontroller well into the VHF range, where meter-long cables become good antennas. (Note that normal spectrum analysers are useless for such studies, because they provide you only with the spectrum of the entire power line, and they do not show you the much weaker information- carrying components in it are are only of interest here.) We are pretty certain that the currents and path lengths on the chip itself are orders of magnitude too small to be picked up by any practical form of antenna (unless perhaps you are in a very well-shielded environment and use some esoteric helium-cooled lowest-noise antennas), even if long-time averaging is performed. However, this is not the case for currents on all the lines that leave the chip surface. Our experimental target is at the moment the PIC16F84 microcontroller. It is in many aspects fully comparable to a smartcard controller (it is in fact used in some smartcards), but assembler-level development kits for it are much more easily openly available then for other smartcard processors and we do not want to have to ask our students to sign manufacturer NDAs before they can join the project. The PIC has also more I/O ports than a normal smartcard CPU, which simplifies triggering the oscilloscope during measurements, and it has a reasonably simple architecture. We have been working with an 8-bit 200 MHz storage scope so far, which is more than sufficient for performing a number of attacks, but in order to fully characterize the spectral properties of the leaking information, we will now use a new 8-bit 2 GHz scope as well. Our interest in the EM aspects is not specific to smartcards. For smartcards, you can usually get easily galvanic access to the connectors, and for most attacks, direct microprobing of the chip surface is the easiest approach anyway. However, EM attacks on microcontrollers are a first step towards better understanding the CPU EM emissions of other more complex embedded security applications, eventually even workstation-class systems. That's where compromising emanations will really become interesting. Some related earlier publications are on http://www.cl.cam.ac.uk/Research/Security/tamper/ especially http://www.cl.cam.ac.uk/~mgk25/ih98-tempest.pdf http://www.cl.cam.ac.uk/~mgk25/sc99-tamper.pdf Markus -- Markus G. Kuhn, Computer Laboratory, University of Cambridge, UK Email: mkuhn at acm.org, WWW: http://www.cl.cam.ac.uk/~mgk25/
Re: DPA mapped to spectral analysis
At 4:04 PM -0800 11/19/99, Matt Crawford wrote: A while back someone on cypherpunks posted a program that would let you hear FSK modulation on a normal radio when the program was run, by modulating PCI traffic. Shoot, I remember the operators of the CDC 3150 at the local state college doing this around 1973 -- they set a radio on top of the console and ran a program that fiddled accumulator bits to play tunes. Matt We used to use an AM radio as a debugging aid with an IBM 1620 (20 microsecond cycle time) at Dartmouth Collage in 1962-1963. My wife reports a program called Mutran (sp?) she saw at Reed Collage which used a radio and the 1620 to play suitably encoded sheet music. - Bill Frantz | Internet Explorer, the | Periwinkle -- Consulting (408)356-8506 | hacker's path to your | 16345 Englewood Ave. [EMAIL PROTECTED] | hard disk. | Los Gatos, CA 95032, USA
Marked cash in Lucre
--- begin forwarded text Date: 21 Nov 1999 22:20:08 - To: [EMAIL PROTECTED] From: lcs Mixmaster Remailer [EMAIL PROTECTED] Subject: Marked cash in Lucre Sender: [EMAIL PROTECTED] Earlier this year there was discussion of David Wagner's blinding as a way of creating electronic cash that would not be covered by existing patents. See the archives at http://privacy.nb.ca/cryptography/archives/coderpunks/new/1999-03/ for the threads "Anonymous cash via blinded authentication" and "Getting around Chaum's patent". David Wagner's original posting is at http://www.deja.com/getdoc.xp?AN=145097228. This algorithm has been implemented by Ben Laurie in his Lucre package, info at http://anoncvs.aldigital.co.uk/lucre/. There have been rumors that Lucre might serve as the foundation for an actual field trial of electronic cash. The idea is that the bank "signs" a number by raising it to a secret exponent k, modulo a strong prime p. The bank can then recognize a signed pair y, y^k by raising the first one to the k power. The y values have some internal redundancy, like the right half is the hash of the left half. To blind, David Wagner suggested the bank also publish a generator g and a value g^k, similar to what is done in Diffie Hellman exchanges. The client then chooses a random blinding factor r and calculates y * g^r, which he sends to the bank. The bank raises this to the k power (a power unknown to the client), producing y^k * g^rk. The client is able to calculate g^rk by taking the published g^k value to the r power. (g^k)^r = g^kr = g^rk. He can therefore divide this out and be left with y^k, a properly "signed" value. This is what is implemented in Lucre. However, there is a flaw. During the discussion earlier this year, it was pointed out that Chaum had proposed a similar algorithm for another purpose, blind undeniable signatures. Instead of blinding by multiplying by g^r, he blinded by raising to a random power. Unblinding was then done by raising to the inverse power. This worked OK for Chaum, but in the Coderpunks discussion it was pointed out that it would allow the bank to "mark" the cash. It could misbehave during the transaction and raise the blinded y value to a power k' instead of k. This cannot be detected by the client since there is no public key to verify the "signature" against (which is why these are not technically signatures). Then when the coin is deposited after unblinding, the bank can recognize that it was the same coin which was marked with the special k' power. It was suggested at the time that David Wagner's blinding was immune to this marking attack. However recently it has been learned that this is not true; the bank can mark cash using Wagner blinding as well. The current Lucre implementation would be vulnerable. During withdrawal, the user submits y * g^r. The bank, to mark the cash, raises it to the k' power rather than the k power. The creates y^k' * g^rk'. The user unsuspectingly unblinds by calculating g^kr and dividing it, leaving y^k' * g^(r(k'-k)). This is what is later submitted to the bank, along with y. The bank, at this point, knows y, k, k', g, and the product above. It does not know r. It can calculate y^k' and divide to get g^(r(k'-k)). It can raise to the inverse power of (k'-k) to get g^r. Now it can multiply by y to get y * g^r. This is the same value which was submitted to be signed in the first place. By keeping a record of the values which were signed using the special k' exponent, the bank can look back and see which one this one is, thereby linking the deposit to the withdrawal, which is exactly what blinding is supposed to prevent. Hence the current Lucre implementation cannot be viewed as safe. It appears that there is a simple fix, but other people should look at it to be sure. The flaw in the existing implementation was not discovered for months, presumably because no one looked closely at it. The fix is simple but it would add confidence for more people to study it. The proposed fix is to combine the two forms of blinding, Wagner's and Chaum's. Choose two random blinding factors, r and s, and blind by calculating y^s * g^r. This is sent to the bank which returns (if it is not cheating) y^sk * g^rk. As in Wagner's blinding, the user can calculating g^rk and divide out, to leave y^sk. As in Chaum's blinding, the user can then raise to the 1/s power to leave y^k. Hence the blinding is easily removed. If the bank cheats by raising to the k' power, the user gets y^sk' * g^rk'. He divides by g^rk to get y^sk' * g^((k'-k)r). He then raises to the 1/s power to get y^k' * g^((k'-k)r/s). This is what he gives to the bank at deposit time, along with y. The bank can calculate and divide off y^k', and raise to the inverse (k'-k) power as before, leaving g^(r/s). However at this point it appears to be stopped. There seems to be no way to correlate this value to the y^s * g^r that it saw at blinding time. If it
