From dawagner@flagstaff.princeton.edu Mon Jul 10 09:01:18 EDT 1995 Article: 37151 of sci.crypt Path: cnn.Princeton.EDU!flagstaff.princeton.edu!dawagner From: dawagner@flagstaff.princeton.edu (David A. Wagner) Newsgroups: sci.crypt Subject: Re: Clipper wiretapping Date: 10 Jul 1995 12:55:57 GMT Organization: Princeton University Lines: 52 Message-ID: <3tr80t$2m3@cnn.Princeton.EDU> References: NNTP-Posting-Host: flagstaff.princeton.edu In article , John Kelsey wrote: > >Yes. That means it's better to steal the keys as they're created. > > It's even better to [...] just > design the whole Clipper package so that it leaks 40 bits of key in the > IV, if you know where to look. > If you suspected this was going on, it could probably be detected (assuming have you a Clipper chip, of course). Fix a key K, and repeatedly load it into the Clipper chip, asking for a random IV. Do this repeatedly until you see a repeated IV. The birthday paradox says this shouldn't happen until 2^32 trials, if the IVs are truly random -- but if they're leaking 2n key bits, you should see a collision after just 2^{32-n} trials. [If it won't tell you the IVs, you're still ok: fix two chosen plaintexts P,P', and record (CBC_K(P),CBC_K(P')) for each random IV. A repeated IV will be detectable when the corresponding ciphertexts match.] [You can load a requested key into the Clipper chip, right??] You could do a similar test to check whether the chip's random key generator has a honest-to-goodness full 2^80 keyspace: repeatedly ask it to generate a random key, and then record the key K you get. [If it won't tell you the key K, you can still run the test: fix two chosen plaintext blocks P,P', and record (ECB_K(P),ECB_K(P')). When a key is generated twice, you'll be able to detect it by a match in the corresponding ciphertexts.] If the true keyspace is 2n bits of key, then 2^n trials should suffice. Has anyone tried this? It seems (barely) feasible. But I don't see how to detect (for instance) trapdoor S-boxes... > > Michael Roe had a paper at the Cambridge algorithms workshop in which he > pointed out several interesting tests that could be done on Skipjack > with a device that would the user to freely load keys and see whole > encryptions. He had some suspiscions that the effective keyspace of > Skipjack might be smaller than 80 bits, based on an uncompleted test > meant to demonstrate effective keyspace. > Interesting -- I wonder what tests he suggested. Hopefully the proceedings will be available soon... ------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu