[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: MAC speeds
Steven M. Bellovin writes:
> Also bear in mind that proofs often make assumptions about ideal
> encryption functions, ideal hash functions, etc.
You seem to be confusing two different parts of the literature.
There are many papers proving the security of various secret-key
constructions against various attacks, under the assumption that the
participants share a long uniform random secret string. Trivial example:
the Mauborgne cipher, also known as the one-time pad.
We think that long secrets can be safely generated from short secrets.
The same systems appear to be secure when the long string is replaced by
Rijndael_k(0) Rijndael_k(1) Rijndael_k(2) ... for a uniform random
128-bit key k. If there's no fast algorithm with a noticeable chance of
distinguishing the Rijndael output from a uniform random string of the
same length---i.e., if Rijndael is unpredictable---then there's no fast
algorithm to break these secret-key constructions; and conversely.
Of course, we don't know how to prove that Rijndael is unpredictable.
But we think it is, and if we find that we're wrong then we'll start
using a different function. The unpredictability assumption is not some
artificial restriction in the proofs; it describes exactly what we need
to guarantee security.
In contrast, the ``ideal hash function'' papers put restrictions on the
attacker. The Rabin-Williams signature system, for example, is provably
secure _against generic attacks_ if factoring is difficult; here a
``generic attack'' uses a hash function as an oracle, and ``secure''
means that the average probability of success over all functions is
small. This is comforting, but it doesn't imply that the system is
secure against real attacks; maybe the hash function we use interacts
badly with the rest of the system.
---Dan
References: