From: futplex@pseudonym.com (Futplex)
Date: Fri, 15 Dec 1995 11:01:57 +0800
To: cypherpunks@toad.com (Cypherpunks Mailing List)
Subject: Re: kocher's timing attack
In-Reply-To: <Pine.BSF.3.91.951214200818.22735C-100000@Aspen.Woc.Atinc.COM>
Message-ID: <199512150203.VAA00869@opine.cs.umass.edu>
MIME-Version: 1.0
Content-Type: text/plain


Jonathan M. Bresler writes:
[...on firewalls...]
> regarding kocher's timing attack paper:
>
> RSA attack.  only known ciphertext is needed.  dont know how many
> known ciphertexts are required (related to key size surely).  the
> paper's example is digital signature, rephrase that to Alice signs
> Bob's public key certifying that (you know the story).  After
> several large key signing parties hundreds of known ciphertexts
> could have been generated using Alice's key--each one a public key
> of someone else.  over several years it piles up.  the known
> ciphertexts can be tested/analyzed to yield Alice's secret key.

[...later on cypherpunks...]

> no, i am not sure.  but after reading the paper carefully that is 
> what i conclude.  on page 4 start of the 4th paragraph "The Chinese 
> Remainder Theorem RSA attack can also be adapted to use only known 
> ciphertext, and thus can be used to attack RSA digital signatures."
> 
> 	the key here is "known ciphertext": you have both the message and 
> its encrypted version.  When Alice signs Bob's public key, with her 
> private key of course, she is encrypting Bob's public key.  this allows 
> Charlie to use Alice's public key to decrypt the signature, recovering a 
> message that is identical to Bob's public key.  that's the proof that 
> Alice was the signer.
> 
> 	no, i am not sure.   anyone see holes in this?

You are overlooking the main point that this is a _timing_ attack. Unless
Bob gets to time Alice carefully when she signs his public key (or a message),
there is no basis for the attack. For certificate servers this may well be
an issue, but most individuals don't sign things online. Just beware of
people with extremely precise stopwatches at key signing parties ;>

-Futplex <futplex@pseudonym.com>