Re: [Cfrg] matching AES security

On Wed, Jul 30, 2014 at 4:08 PM, Blumenthal, Uri - 0558 - MITLL
<uri@ll.mit.edu> wrote:
>>>Please explain what typical device will use at least one new key every
>>> minute?
>>
>>Er, well, smartphone apps might well poll/get pushed to that
>>frequently, altogether, with a new key per-poll/push.  Sure, the
>>protocol involved might not generate a new key per-event, but if the
>>protocol is TLS, then it will.
>
> Maybe... A good argument to avoid TLS. :-)
>
>>DJB's point is that we should permit "odd" match-ups like AES-256 and
>>Curve25519 _because_ AES-128 is weak in plausible scenarios.
>                                           ^^^^^^^^^ :-)
>
> There already are such "odd" match-ups, and I guess the trend is here to
> stay.
>
> But to do it because of attackers "getting _all_ of your 2^50 keys with
> 2^128 easy (sic!) computations"? (I guess you could convince about half of
> the existing atoms in the Universe to do one computation for you, and
> maybe store the result. But lookups would have to be extra! :).

This is what rainbow tables are for. Let's suppose f:S->S, |S|=n. To
find preimages of k points p_1, ... p_k,
I do the following: pick s points q_1, .. q_s, store (q_i,f^r(q_i)) in
a table, and compute f^j(p_t) for each j and t,
checking if I get f^r(q_i) for some q_i. If I do, I calculate the
intermediate iterates of q_i, one of which is likely p_t.

The storage is s, while the number of points is sr, and I win with
probability about srjk/n, doing sr+jk work.
There is a higher-order collision term, but it's negligible.

This isn't new: rainbow tables were used to reverse password hashes in the 90's.

Sincerely,
Watson Ladd

>
>>I'm having a hard time objecting to that!
>
> :-)
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin