"Clay Turner" <physics@bellsouth.net> wrote in message
news:aAktd.38809$Dm2.10619@bignews1.bellsouth.net...
>
> Karl, Bryan et. al.,
>
> The guys at Stanford, were able to break the RSA code via a timing attack
> over a network within two hours. And that is for a case of using 1000
digit
> numbers.
>

Their attack used a timing difference of 10^7 cpu cycles over a local area
network.  Professor Bernstein's attack uses a timing difference of 1 cpu
cycle.

karl m

"Karl Malbrain" <karl_m@acm.org> wrote in message
news:1102269765.683817.172220@f14g2000cwb.googlegroups.com...
>
> Bryan Olson wrote:
> > Bryan Olson wrote:
> >
> >  >
> >  > Tim Wescott wrote:
> >  >  > [...] This means that if the
> >  >  > variance in your network turn-around time is v, and if the
> difference
> >  >  > between message times is t_d, you need to collect somewhere on
> the
> > order
> >  >  > of N = v / t_d^2 of each type of message if you want to discern
> a
> >  >  > difference.
> >  >
> >  > I think you mean  N = (v / t_d)^2.
> >
> > Oops, my mistake.  The variance is already in seconds^2.
>
> On a wide area network I estimate the variance is going to run 10^12.
> With a DS3 connection of 45mbs that's about 50 years to gather enough
> trial encryptions.
>
> karl m
>

Karl, Bryan et. al.,

The guys at Stanford, were able to break the RSA code via a timing attack
over a network within two hours. And that is for a case of using 1000 digit
numbers.

Clay S. Turner

"karl malbrain" <karl_m@acm.org> wrote in message
news:31jqstF396i8vU1@individual.net...
>
> "Clay Turner" <physics@bellsouth.net> wrote in message
> news:KCKsd.104218$IQ.17698@bignews6.bellsouth.net...
>
> > Hello Randy,
> >
> > The RSA algo has a similar vunerability and the standard work around was
> to
> > make the encryption/decryption process a constant time one.
>
> Do you have any details on this? A web url, for example?
>
> Thanks, karl m
>

Google for "Quisquater" and "RSA". This professor from Belgium has published
a lot about timing attacks.

Wim

"Clay Turner" <physics@bellsouth.net> wrote in message
news:vH3td.36626$Dm2.1889@bignews1.bellsouth.net...
>
> "karl malbrain" <karl_m@acm.org> wrote in message
> news:31jqstF396i8vU1@individual.net...
> >
> > "Clay Turner" <physics@bellsouth.net> wrote in message
> > news:KCKsd.104218$IQ.17698@bignews6.bellsouth.net...
> >
> > > Hello Randy,
> > >
> > > The RSA algo has a similar vunerability and the standard work around
was
> > to
> > > make the encryption/decryption process a constant time one.
> >
> > Do you have any details on this? A web url, for example?
> >
> > Thanks, karl m
>
> Hello Karl,
>
> I think you will find the following paper more than useful.
>
> http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf

Yes, thanks.  I'd been stuck in section 5 and hadn't read section 6 yet.
karl m

"karl malbrain" <karl_m@acm.org> wrote in message
news:31jqstF396i8vU1@individual.net...
>
> "Clay Turner" <physics@bellsouth.net> wrote in message
> news:KCKsd.104218$IQ.17698@bignews6.bellsouth.net...
>
> > Hello Randy,
> >
> > The RSA algo has a similar vunerability and the standard work around was
> to
> > make the encryption/decryption process a constant time one.
>
> Do you have any details on this? A web url, for example?
>
> Thanks, karl m

Hello Karl,

I think you will find the following paper more than useful.

http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf

Clay S. Turner

"Clay Turner" <physics@bellsouth.net> wrote in message
news:KCKsd.104218$IQ.17698@bignews6.bellsouth.net...

> Hello Randy,
>
> The RSA algo has a similar vunerability and the standard work around was
to
> make the encryption/decryption process a constant time one.

Do you have any details on this? A web url, for example?

Thanks, karl m

"Bryan Olson" <fakeaddress@nowhere.org> wrote in message
news:biYsd.29447$zx1.4950@newssvr13.news.prodigy.com...
> Karl Malbrain wrote:
>  > Over a wide area network the variance is likely 10^12.
>
> Standing by itself and with no unit, that's not meaningful.  Tim
> had it right (sorry about my previous confusion):

The unit is cpu cycles squared, estimated.

>      The key parameters in this case are the deterministic difference in
>      turn-around time due to message content and the variance in turn-
>      around time from the network.
>
> We can compress this to a single parameter: the signal to noise ratio.
> The signal is the expected time difference caused by the key/message
> values, and the noise is the standard deviation in the network turn-
> around time.  Both are in seconds, so the ratio is a unit-less constant.

Professor Bernstein's attack on the Athlon accumulates a 1 cpu-cycle timing
difference between trial encryptions -- estimated at a 1 cpu-cycle squared
variance.

> In this case, working with noise/signal is a little more convenient
> than signal/noise.  We expect the signal to become larger than the noise
> when the number of messages exceeds the square of the single-message
> noise/signal.

>  > With a message
>  > length of 1K bits and a DS3 transfer rate of 45 mbs, that's 45K
>  > encryptions/second which makes for 50+ years.
>  > Do you know the optical circuit data rate?  karl m
>
> Those numbers don't really tell us anything.  If the standard deviation
> in the time is 1000 times as large than the key-dependent effect, then
> we expect to need on the order of a million messages.

Right.

My point was that over a DS3 line with a timing variance of 10^12 there's
not much worry of a remote wide-area-network timing attack.  karl m

Karl Malbrain wrote:
 > Over a wide area network the variance is likely 10^12.

Standing by itself and with no unit, that's not meaningful.  Tim
had it right (sorry about my previous confusion):

     The key parameters in this case are the deterministic difference in
     turn-around time due to message content and the variance in turn-
     around time from the network.

We can compress this to a single parameter: the signal to noise ratio.
The signal is the expected time difference caused by the key/message
values, and the noise is the standard deviation in the network turn-
around time.  Both are in seconds, so the ratio is a unit-less constant.

In this case, working with noise/signal is a little more convenient
than signal/noise.  We expect the signal to become larger than the noise
when the number of messages exceeds the square of the single-message
noise/signal.

 > With a message
 > length of 1K bits and a DS3 transfer rate of 45 mbs, that's 45K
 > encryptions/second which makes for 50+ years.
 > Do you know the optical circuit data rate?  karl m

Those numbers don't really tell us anything.  If the standard deviation
in the time is 1000 times as large than the key-dependent effect, then
we expect to need on the order of a million messages.


-- 
--Bryan

"Randy Yates" <yates@ieee.org> wrote in message
news:653hpr4e.fsf@ieee.org...
> Tim Wescott <tim@wescottnospamdesign.com> writes:
> > [...]
> > I suspect that N may be quite large, and the attack could easily be
> > defeated by wrapping your cryptographic algorithm by a process that
> > schedules the outgoing message so the reply always takes the same
> > amount of time to be sent, no matter how long the actual cryptography
> > took.
>
> Damn, Tim! Why spoil a perfectly good theoretical discussion with
> a practical suggestion like that?
> -- 


Hello Randy,

The RSA algo has a similar vunerability and the standard work around was to
make the encryption/decryption process a constant time one.

Clay

Bryan Olson wrote:
> Bryan Olson wrote:
>
>  >
>  > Tim Wescott wrote:
>  >  > [...] This means that if the
>  >  > variance in your network turn-around time is v, and if the
difference
>  >  > between message times is t_d, you need to collect somewhere on
the
> order
>  >  > of N = v / t_d^2 of each type of message if you want to discern
a
>  >  > difference.
>  >
>  > I think you mean  N = (v / t_d)^2.
>
> Oops, my mistake.  The variance is already in seconds^2.

On a wide area network I estimate the variance is going to run 10^12.
With a DS3 connection of 45mbs that's about 50 years to gather enough
trial encryptions.

karl m