1994-06-02 - LEAF forgery

Header Data

From: perry@imsi.com (Perry E. Metzger)
To: cypherpunks@toad.com
Message Hash: acf473e9236a2dc5e6c6e3e331084ddd3176f06e3fe61e307f6fe6a09571ebbc
Message ID: <9406021826.AA16847@webster.imsi.com>
Reply To: N/A
UTC Datetime: 1994-06-02 18:27:11 UTC
Raw Date: Thu, 2 Jun 94 11:27:11 PDT

Raw message

From: perry@imsi.com (Perry E. Metzger)
Date: Thu, 2 Jun 94 11:27:11 PDT
To: cypherpunks@toad.com
Subject: LEAF forgery
Message-ID: <9406021826.AA16847@webster.imsi.com>
MIME-Version: 1.0
Content-Type: text/plain

Matt gave me permission to explain the technical details of the paper.

This is the hack. Its idiotically simple.

According to the paper, because of the nature of the communications
involved, the Capstone chip is forced to accept as valid any LEAF with
the right 16 bit checksum. Note that the LEAF contains only the the
chip's ID, the key encrypted in the chip's "secret never to be
divulged except by escrow" key, and this checksum, all encrypted with
the family key.  Since the other chip lacks the "supersecret" key,
it can't check that the session key matches the encrypted session key.
It relies on the checksum for everything. That checksum is a silly 16
bits long.

Thus, you just have to try about 2^15 random LEAFs and you can get one
that works. You can even precompute them if you wish. Its that simple.
Then all you do is send the rogue LEAF instead of a legitimate one. 

Matt Blaze should be commended for finding such a big hole. As with
most such ideas, its obvious in retrospect but took some good thought
to come up with in the first place.

Let me say also that the NSA should feel highly embarassed. They
fucked up big time. My terror of them from a few days ago when we
heard the Russian Coup intercept story has lessened. Even if they are
years ahead of us, they are still human.


PS There are also a bunch of neat techniques out there for the "lets
say that you don't care about interoperating" case, but they are
naturally less general.