[Boneh-crypto-course] Are we keeping up?

Jason Orendorff jason.orendorff at gmail.com
Tue Apr 10 09:53:26 CDT 2012


On Tue, Apr 10, 2012 at 2:17 AM, Jim Blandy <jimb at red-bean.com> wrote:
> I just finished the week three problem set; it took me two tries. I
> was completely unable to figure out the last one, but guessed my way
> through it, and read the explanation carefully.

After tons of dicking around with algebra I finally figured out the
hand-wavy argument he was after with that question. I hate that kind
of argument. I don't see why I should have a lot of confidence in it.

I lost .16 of a point on one of the questions where it asked, suppose
(S, V) is a secure MAC, then how about this?
  S'(m) = (S(m), S(m))
I said it wasn't secure, because if S is randomized, so that you get
two different answers, then whenever you get (t, t') you know that (t,
t) and (t', t') and (t', t) are also valid tags, which technically
counts as a forgery.

I get into trouble overthinking things sometimes...

> I've been translating stuff into Haskell, which works nicely:
>
> The adversary in a MAC advantage computation gets to take a series of
> turns, offering as many queries as it likes, and prior results can
> influence future results. So I modeled that as an algebraic type that
> has a continuation of sorts in there:

Yeah, this was nice.

>> (I've been surprised to hear that again and again, the systems with
>> really strong security properties are not used in practice, apparently
>> for performance reasons. Provably secure ciphers are not used; instead
>> we use AES which we think is probably secure. We don't want secure
>> systems: we want secure-enough systems.)
>
> The only such thing I've seen so far is the compression function:

I guess the particular thing I had in mind was Blum Blum Shub:
  https://en.wikipedia.org/wiki/Blum_Blum_Shub
which is a provably "secure-if-integer-factorization-is-hard" PRG.

I haven't been taking good enough notes to keep track of any other
cases, but it's been a theme (that and "I can't tell you how many
products make this common mistake").

-j



More information about the Boneh-crypto-course mailing list