Re: kocher's timing attack

On Firewalls, "Jonathan M. Bresler" <jmb@FreeBSD.ORG> said:

JMB> regarding kocher's timing attack paper:

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

	Are you sure about this?  It would seem that the same principle
would then apply to signed messages as well, and I find it a bit hard to
believe that signing messages would make ones key pair vulnerable.

-- 
#include <disclaimer.h>				/* Sten Drescher */
To get my PGP public key, send me email with your public key and
	Subject: PGP key exchange
Key fingerprint =  90 5F 1D FD A6 7C 84 5E  A9 D3 90 16 B2 44 C4 F3

On 14 Dec 1995, Sten Drescher wrote:

> On Firewalls, "Jonathan M. Bresler" <jmb@FreeBSD.ORG> said:
> 
> JMB> regarding kocher's timing attack paper:
> 
> JMB> RSA attack.  only known ciphertext is needed.  dont know how many
> JMB> known ciphertexts are required (related to key size surely).  the
> JMB> paper's example is digital signature, rephrase that to Alice signs
> JMB> Bob's public key certifying that (you know the story).  After
> JMB> several large key signing parties hundreds of known ciphertexts
> JMB> could have been generated using Alice's key--each one a public key
> JMB> of someone else.  over several years it piles up.  the known
> JMB> ciphertexts can be tested/analyzed to yield Alice's secret key.
> JMB> ouch.  ;/
> 
> 	Are you sure about this?  It would seem that the same principle
> would then apply to signed messages as well, and I find it a bit hard to
> believe that signing messages would make ones key pair vulnerable.

	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?


Jonathan M. Bresler        FreeBSD Postmaster         jmb@FreeBSD.ORG
play go. ride bike. hack FreeBSD.--ah the good life 
i am moving to a new job.                 PLEASE USE: jmb@FreeBSD.ORG

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>

-----BEGIN PGP SIGNED MESSAGE-----

Hello cypherpunks@toad.com (Cypherpunks Mailing List)
  and futplex@pseudonym.com (Futplex)

Futplex writes:
... [in reply to others] ...
> You are overlooking the main point that this is a _timing_ attack. Unless
...
> Just beware of
> people with extremely precise stopwatches at key signing parties ;>

Hold on, you *never* sign directly at key signing parties!

Never take your key where:
  - it could be stolen
  - you suspect others may wish to influence your signing
  - somebody might spy your passphrase (hidden cameras in ceiling)

You take fingerprints, and sign when you get back home.


Re the timing subject, do you think it'd make a good party trick?

  * Think of a number between 20 and 30.
  * for 4-5 numbers a, "Multiply the orignal number by <a>"
  * the number you are thinking of is <number>

Now, anybody have statistics for mental arithmetic?

Jiri
- --
If you want an answer, please mail to <jirib@cs.monash.edu.au>.
On sweeney, I may delete without reading!
PGP 463A14D5 (but it's at home so it'll take a day or two)
PGP EF0607F9 (but it's at uni so don't rely on it too much)

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2i

iQCVAwUBMNOXuyxV6mvvBgf5AQFEtgP/Wf5I205BAuqiuSEwkslbGP0nwV8ylA0G
nnmS1FFJjFkkfICxEp+/C0iQqLcYpp1ytio+yyWmAE+nDEomcmnQb40ElGjYB/2m
btP6cT9ozfM8lXY6Tfn+G+kduZWfpKyngoMDSPzYSNAuizD5qyUodYJXyjfz4y0p
BoXBMwB9IUA=
=EpU4
-----END PGP SIGNATURE-----