From: fc@all.net (Dr. Frederick B. Cohen)
Date: Thu, 14 Dec 1995 12:50:52 +0800
To: cypherpunks@toad.com
Subject: Re: Timing Cryptanalysis Attack
In-Reply-To: <199512112111.NAA02653@mage.qualcomm.com>
Message-ID: <9512120054.AA05216@all.net>
MIME-Version: 1.0
Content-Type: text


The timing of cryptosystems to get keys is a special case of covert
channels, and it is not correct to claim that trusted systems (ala the
TCSEC) fail to account for this.

The problem with covert channels (including timing channels such as the
one that gets key material) runs pretty deep.  For example, Shannon's
theory says that for any finite amount of noise, we can always send
information through such a channel at a bandwidth dictated by the signal
to noise ratio.  Furthermore, any time a computational resource with
known characteristics is shared in a way that depends on a secret in any
way, that secret is leaked through the covert channel associated with
the shared resource. 

So the difference between processing a one and a zero even in many forms
of multiplication can be used to determine characteristics of many secret
processes.

	Example: a valid password results in a different execution time
	than an invalid one -> enough statistics, and you can find the
	password.

	Example: a valid UID with an invalid password takes a different
	amount of time than a valid UID with the same password -> enough
	statistics and you can find valid UIDs.

	Example: a transaction worth $1,000 takes a different amount of
	processing time than a transaction for $2.95 -> enough statistics
	and you can figure out which messages are worth breaking.

	Example: usage characteristics change just before major stock
	changes occur -> enough statistics and you can predict when the
	share price will change dramatically.

If you are willing to spend enough effort charactierizing these things,
no system with information-dependent shared resources (e.g., the
Internet) can hold its secrets (a bit of poetic license there). 

-> See: Info-Sec Heaven at URL http://all.net/
Management Analytics - 216-686-0090 - PO Box 1480, Hudson, OH 44236