[Boneh-crypto-course] Are we keeping up?
jimb at red-bean.com
Tue Apr 10 02:17:16 CDT 2012
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.
So, I've watched up through 6.6. I haven't tried any of the
programming assignments yet. I'd love to be able to pick up the pace a
bit so I'd have time for that. What degree of effort is involved in
them? It's hard to imagine a programming assignment that doesn't take
quite a bit longer than the quizzes.
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:
data (Bits x, Bits t) => AdvantageMACAdversary x t =
Query ([x], (t -> AdvantageMACAdversary x t)) |
Guess ([x], t)
advantageMAC :: (Bits x, Bits t) => AdvantageMACAdversary x t -> MAC k
[x] t -> Double
advantageMAC a (s, v) = pr (\u ->
let k = chooseChallengerKey u
game (Query (m, next)) used | not (elem m used) =
(next (s k m)) (m : used)
game (Guess (m, t)) _ = v k m t
in game a )
-- cascadeExtensionAttacker f fpad is an adversary that can break nmac
-- cascade after making only one query.
cascadeExtensionAttacker :: (Bits k, Bits x) => (k -> x -> k) ->
AdvantageMACAdversary x k
cascadeExtensionAttacker f = Query (,
\t -> Guess ([1729, 42], f t 42))
The type checker doesn't produce very legible error messages, but it's
caught many, many typos.
> (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:
provable p u v = \accum x -> (u^accum * v^x) `mod` p
Is that what you have in mind? You don't mean one-time pads, do you?
More information about the Boneh-crypto-course