Secure MAC using Block Cipher?
John E. Hadstate
didn't return anything useful.
Let's say I have a highly constrained system where I have
managed to implement AES, but I can't get room for any other
primitive (like SHA-256). Is it possible to construct a
secure 256-bit MAC using only a 128-bit Block Cipher? If
so, what is the preferred method for doing this? References
to citeseer or google threads are fine.
Thanks,
-jeh
Tom St Denis
A simple [but slow] way is to use AES to make a 3-round feistel and use
that Feistel in CBC-MAC [e.g. like OMAC] mode. It's gonna be really
slow but provided the three AES keys are independent should be
practically secure...Though I think you'd need more than just three
rounds to get adaptive input indistinguishability.
Tom
Gregory G Rose
John E. Hadstate <jh11...@hotmail.com> wrote:
>Let's say I have a highly constrained system where I have
>managed to implement AES, but I can't get room for any other
>primitive (like SHA-256). Is it possible to construct a
>secure 256-bit MAC using only a 128-bit Block Cipher? If
I don't understand why one would want to.
The purpose of a MAC function is entirely
different to the purpose of a hash function. The
MAC just has to withstand second-preimage attacks
(and of course key recovery attacks). What's more,
the only way the adversary can get information
about valid MACs is to involve the user's
computers (either sender or receiver); he can't go
offline and do lots of parallel computations. So
the tag length for a MAC can, in practice, be
smaller than a corresponding key length. Given
that, why would anyone ever need a 256-bit tag
when the cipher is only 128-bit secure. 128 bits,
or maybe even 96, 80, or even 64 in a
bandwidth-constrained environment, might be
perfectly ample tag lengths.
Greg.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au
David Wagner
>Let's say I have a highly constrained system where I have
>managed to implement AES, but I can't get room for any other
>primitive (like SHA-256). Is it possible to construct a
>secure 256-bit MAC using only a 128-bit Block Cipher?
Can you explain what you mean by a 256-bit MAC? Does "256-bit"
refer to the desired security level? Are you talking about security
against 2^256 steps of computation? Against 2^256 chosen plaintexts?
Are you using AES with a 256-bit key?
Are you sure you really need 256-bit security, anyway? If your
reasoning is something like "this data must remain secure for 50
years", it is hard to be confident that any existing cryptosystem
will be adequate, no matter how long its key or block size.
Paul Rubin
> Can you explain what you mean by a 256-bit MAC? Does "256-bit"
> refer to the desired security level? Are you talking about security
> against 2^256 steps of computation? Against 2^256 chosen plaintexts?
> Are you using AES with a 256-bit key?
I'd say it starts with a 256-bit MAC length, giving 2^128 resistance
against birthday collisions.
David Wagner
Birthday collisions are not relevant to MACs.
A MAC with 128-bit output can provide 2^128 resistance against
birthday collisions.
Roughly speaking, birthday attacks apply mainly to unkeyed hashes,
not to keyed functions like a MAC (assuming the keyed function is
well-designed).
Paul Rubin
> Roughly speaking, birthday attacks apply mainly to unkeyed hashes,
> not to keyed functions like a MAC (assuming the keyed function is
> well-designed).
Sometimes people use MAC's as keyed hashes. Maybe that's a misuse in
that it's not being truly used as an authentication code. Anyway, in
that usage, a birthday collision is when the same MAC labels two
different messages.
David Wagner
>Sometimes people use MAC's as keyed hashes.
What do you mean by "keyed hash"? Do you mean "pseudorandom function"?
(I dislike the word "keyed hash", since it is so unclear what it is
supposed to mean. I don't mean to jump on you; just a personal pet peeve.)
>Anyway, in
>that usage, a birthday collision is when the same MAC labels two
>different messages.
But you can only find birthday collisions if you know the key ==> birthday
attacks are not a problem (unless you are using the function in a very
weird way, I guess).
Paul Rubin
> >Sometimes people use MAC's as keyed hashes.
> What do you mean by "keyed hash"? Do you mean "pseudorandom function"?
Yes.
> >Anyway, in that usage, a birthday collision is when the same MAC
> >labels two different messages.
>
> But you can only find birthday collisions if you know the key ==> birthday
> attacks are not a problem (unless you are using the function in a very
> weird way, I guess).
Let's say you have a database of poems indexed by the contents of the
first line. You don't want to store the database in the clear because
then attackers could see what poems you have. You can't index with an
unkeyed hash of the first line because the attackers could then run
their own list of first lines through the hash and see which ones are
in your database. You can't use a PRP because the lines are of
varying lengths. The answer is to use a PRF. But you want to be sure
that any two distinct first lines map to different "hashes", i.e. that
the PRF output is long enough to make birthday collisions unlikely.
David Wagner
>The answer is to use a PRF. But you want to be sure
>that any two distinct first lines map to different "hashes", i.e. that
>the PRF output is long enough to make birthday collisions unlikely.
Ok. But for this application, 128-bit outputs should be fine, as I
doubt you have a database containing 2^64 poems.
In general, the size of your database is something you control, whereas
the number of hash operations the adversary can perform is something you
don't. Usually the former number is much smaller than the latter number.
Maybe that's part of the reason why birthday attacks are such a big deal
on unkeyed hash functions, yet seem usually to be no big deal for PRFs.
John E. Hadstate
"John E. Hadstate" <jh11...@hotmail.com> wrote in message
news:yFD1e.93799$%Y4.5...@bignews6.bellsouth.net...
(1) Apparently, one can make a secure 256-bit MAC by
encrypting a 256-bit hash using two AES encryptions.
(2) The problem then becomes, "how can I construct a
cryptographic 256-bit hash using only AES?" The official
answer seems to be modified Davies-Meyer in tandem or
abreast configurations, or MDC-2, or MDC-4. Aaaargh! I
smell a wet dog.
(3) Tom's solution of building a 256-bit cipher using a
3-round Feistal structure and AES as the round function, and
then forming a MAC-CBC seems like an attractive alternative
to (1)+(2) (for performance reasons), especially if a hash
is not needed.
(4) Paul's example of protecting database indices was a good
one, although I would think that in the environment of a
database server, one would not be so constrained as to only
have the AES primitive available.
Sorry guys. It was just another dumb question from someone
who should have done more homework before posting. I should
have read the book first.
David Wagner
>(1) Apparently, one can make a secure 256-bit MAC by
>encrypting a 256-bit hash using two AES encryptions.
You still haven't defined what you mean by a "256-bit MAC", and in
particular, what security level you need.
If you mean that you don't care what the security level is, so long as
the MAC output is 256 bits long, then just run AES-CBC-MAC and append
128 zero bits to it.
If you mean that you are expecting security against attackers who can do
2^256 work, then the above doesn't cut it. I can see a trivial attack
that breaks it with 2^128 offline work and 1 chosen plaintext.
I suspect you'll need to be a little clearer about your requirements
before we can help you. I don't think it makes sense to look for
constructions until one can articulate the security goals such a scheme
must achieve.
John E. Hadstate
"David Wagner" <d...@taverner.cs.berkeley.edu> wrote in
message news:d27sgl$2n5q$1...@agate.berkeley.edu...
>
> I suspect you'll need to be a little clearer about your
requirements
> before we can help you. I don't think it makes sense to
look for
> constructions until one can articulate the security goals
such a scheme
> must achieve.
Sorry to disappoint you. Thanks for your comments.