AES timing attacks

"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

"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

"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: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
>

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

Wim

"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

"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