David Wagner wrote:
Ed Gerck wrote:
(A required property of MACs is providing a uniform distribution of values for a
change in any of the input bits, which makes the above sequence extremely
improbable)
Not so. This is not a required property for a MAC.
(Not all MACs must be PRFs.)
Ed Gerck wrote:
Wei Dai wrote:
No matter how good the MAC design is, it's internal collision probability
is bounded by the inverse of the size of its internal state space.
Actually, for any two (different) messages the internal collision probability
is bounded by the inverse of the SQUARE of
Adam Back [EMAIL PROTECTED] wrote:
See for example Rogaway's arguments about limited value of
defending against extension forgery attacks in XCBC:
[... quote snipped ...]
http://csrc.nist.gov/encryption/modes/workshop2/presentations/xcbc.pdf
This doesn't contain the paragraph that you quoted,
On Thu, Oct 24, 2002 at 02:08:11AM -0700, Sidney Markowitz wrote:
[...] XCBC should be inherently resistant to extension forgery
attacks. The attack requires that the MAC have the property that
MAC(x) == MAC(y) implies that MAC(x||z) == MAC(y||z). In the case of
XCBC, because of the padding
There seems to be a question about whether:
1. the internal collision probability of a hash function is bounded by the
inverse of the size of its internal state space, or
2. the internal collision probability of a hash function is bounded by the
inverse of the square root of size of its
There seems to be a question about whether:
1. the internal collision probability of a hash function is bounded by the
inverse of the size of its internal state space, or
2. the internal collision probability of a hash function is bounded by the
inverse of the square root of size of its
... pls read this message with the edits below...
missing ^ in exp and the word WITHOUT...still no coffee...
David Wagner wrote:
Ed Gerck wrote:
Wei Dai wrote:
No matter how good the MAC design is, it's internal collision probability
is bounded by the inverse of the size of its internal
The problem with this one-size fits all approach is that for most
applications given the key size of AES, the extension forgery is
impractical. It would be more flexible to specify RMAC as having an
optional salt, with the size determined by the implementer as
appropriate for their scenario.
So
On Mon, 21 Oct 2002, Aram Perez wrote:
[EMAIL PROTECTED] wrote:
While you are correct in the general case, I have worked on a system where
Alice could only generate MACs and Bob could only verify MACs. The hardware
was designed so that Alice could not verify MACs and Bob could not generate
On Tue, 22 Oct 2002, Ed Gerck wrote:
Short answer: Because the MAC tag is doubled in size.
Longer answer: The birthday paradox says that if the MAC tag has t bits,
only 2^(t/2) queries to the MAC oracle are likely needed in order to discover
two messages with the same tag, i.e., a
On Tue, Oct 22, 2002 at 11:09:41AM -0700, bear wrote:
Now Bob sends Alice 2^32 messages (and Alice's key-management
software totally doesn't notice that the key has been worn to
a nub and prompt her to revoke it). Reviewing his files, Bob
finds that he has a January 21 document and a
bear wrote:
On Tue, 22 Oct 2002, Ed Gerck wrote:
Short answer: Because the MAC tag is doubled in size.
Longer answer: The birthday paradox says that if the MAC tag has t bits,
only 2^(t/2) queries to the MAC oracle are likely needed in order to discover
two messages with the same
On Tue, 22 Oct 2002, Ed Gerck wrote:
Short answer: Because the MAC tag is doubled in size.
I know, but this is not my question.
Longer answer: The birthday paradox says that if the MAC tag has t bits,
only 2^(t/2) queries to the MAC oracle are likely needed in order to discover
two
Ed Gerck [EMAIL PROTECTED]
It does to (as you can read in the paper). BTW, the easily applies to the
case
WITHOUT salt
Well, to be really pedantic the paper never says that it is easy only that
it has a work factor of the square root of the number of possible MAC strings
without salt, and that
[EMAIL PROTECTED] wrote:
On Tue, 22 Oct 2002, Ed Gerck wrote:
Short answer: Because the MAC tag is doubled in size.
I know, but this is not my question.
;-) your question was Why is RMAC resistant to birthday attacks?
Longer answer: The birthday paradox says that if the MAC tag has
On Tue, Oct 22, 2002 at 12:31:47PM -0700, Ed Gerck wrote:
My earlier comment to bear applies here as well -- this attack can be avoided
if only a subset of the MAC tag is used
I can't seem to find your earlier comment. It probably hasn't gone through
the mailing list yet.
I don't see how
[EMAIL PROTECTED]
I want to understand the assumptions (threat models) behind the
work factor estimates. Does the above look right?
I just realized something about the salt in the RMAC algorithm, although it
may have been obvious to everyone else:
RMAC is equivalent to a HMAC hash-based MAC
Wei Dai wrote:
On Tue, Oct 22, 2002 at 12:31:47PM -0700, Ed Gerck wrote:
My earlier comment to bear applies here as well -- this attack can be avoided
if only a subset of the MAC tag is used
I can't seem to find your earlier comment. It probably hasn't gone through
the mailing list
But the salt doesn't increase the MAC length. It just frustrates
attempts to collect message+MAC pairs to find a collision. Think of
it like a salt on unix passwords. You can still brute force one
particular target in the same time, but the salt reduces your scope
for pre-computation.
There is
Sidney Markowitz wrote:
[EMAIL PROTECTED]
I want to understand the assumptions (threat models) behind the
work factor estimates. Does the above look right?
I just realized something about the salt in the RMAC algorithm, although it
may have been obvious to everyone else:
RMAC is
Ed Gerck [EMAIL PROTECTED] said:
No -- these are all independent things. One can build an RMAC wih SHA-1.
An RMAC does not have to use an HMAC scheme. One can also have an
HMAC hash-based MAC algorithm using a block cipher, that is not an RMAC.
Some quotes from the paper:
This paper defines
At 03:05 PM 10/22/2002 -0400, Wei Dai wrote:
Call the Jan 21 document x, and the Sept 30 document y. Now Bob knows
MAC_Alice(x | z) = MAC_Alice(y | z) for all z, because the internal states
of the MAC after processing x and y are the same and therefore will remain
equal given identical suffixes.
Sidney Markowitz wrote:
Ed Gerck [EMAIL PROTECTED] said:
That's is not the reason it was devised. The reason is to prevent a birthday
attack for 2^(t/2) tries on a MAC using a t-bit key. Needless to say, it also makes
harder to try a brute force attack.
RMAC was devised for the reason
Ed Gerck [EMAIL PROTECTED] wrote:
A minor nit, but sometimes looking into why
things were devised is helpful.
What I explained can be found in
http://csrc.nist.gov/encryption/modes/workshop2/report.pdf
Thank you, that was really helpful in seeing the motivation for the work that led to
the
The RMAC FIPS draft does not appear to explicitly state when RMAC is
useful. What is the scenario in which (presumably unlike some other keyed
MAC algorithms) RMAC is resistant to birthday attacks? More broadly for an
arbitrary keyed MAC (in a plausible application!) how does the birthday
attack
I think they are presuming there will be no encryption, so Eve can
verify collisions by observing the MAC values. Eve just records
messages and their MACs that Alice sends Bob. They are also presuming
exceedingly long lived MAC keys. (If you changed keys the collection
of messages would have to
26 matches
Mail list logo
