Re: Into the Fire

From: Bryan Olson (fakeaddress_at_nowhere.org)
Date: 07/31/03 

Date: Thu, 31 Jul 2003 13:54:37 GMT

Mark Wooding wrote:

> Bryan Olson wrote:
>
>
>>Eve happens to know the plaintext, and is able to block delivery of
>>Alice's message to Bob. This gives Eve 1000 bytes of the keystream.
>>She then makes up a 980-byte message, encrypts it with the first 980
>>known key byes, then computes the 10-byte MAC using the next 20 known
>>bytes. Eve sends her message to Bob, who decrypts it to the text Eve
>>chose, and finds that the MAC verifies.
>
>
> But that's not the way these MACs work. The two parties choose a
> /fixed/ and /secret/ hash function from an AXU family for an entire
> session,

There is exactly one message in the session.

> and then for each message, compute the message hash using the
> selected hash function and mask it with the next lump of pad.

Only the key is shared and secret. If Alice and Bob need to
choose a secret hash function uniformly from among 2^80
candidates, that takes 80 bits of key. Then masking an 80-bit
hash requires another 80 bits of key. Note that I have Alice
and Eve using 20 bytes of keystream to compute a 10-byte digest.

Don't confuse the internal workings of the MAC with how it's
used: it takes message and key, and returns a digest. If we
want n-bits of entropy in the MAC, and require that showing the
attacker a message and MAC provide no information on how to MAC
a different message, the function will require at least 2*n bits
of key. Internally, the function may use n bits to select from
a family of hashes and n bits to key the selected hash.

> Sorry: I thought you understood this.

My example problem is from an old post that explains the basic
theory of these functions:

     http://www.google.com/groups?selm=82ei0e%242f2%241%40nnrp1.deja.com

> If the hash selection is encoded in the
> message then the scheme leaks which hash function is being used and Eve
> can /choose/ an advantageous hash value for her forgery attempt, with
> the result that the scheme doesn't work.

There's no hash selection encoded in the message in my example.
Within the MAC, the hash is selected by key, as it must be,
since Bob and Alice have to use the same secret function. My
point is that the authentication keystream must be distinct from
the encipherment keystream. 

-- 
--Bryan

Relevant Pages

  • Re: a makeshift hash solution
    ... Tom Foolery wrote: ... But how would I use a public key system to protect ... > the hash that's in the file and compare to the hashes in the list. ... I've been using a MAC all along. ...
    (sci.crypt)
  • Re: HMAC issues
    ... hash the message once and then hash the result. ... MAC!= Hash. ... twofish and AES modules i have in VB use this code fiddling to unsign ... implementation in VB (apparently they work for counterpane), ...
    (sci.crypt)
  • Re: Can a program prove its own integrity?
    ... > program he would have to find a way to calculate the right MAC for every ... If the attacker has access to the box, the MAC can be bypassed, ... get and build a simple program that does a SHA-1 hash of a file. ... Modify the program to calculate a hash of itself. ...
    (sci.crypt)
  • Re: Hash of Hashes
    ... I am having some problems in printing the Hash of Hashes. ... The file has multiple MAC, PHY and Network Statistics in it and I am ...
    (comp.lang.perl.misc)
  • Re: Statistics Extraction
    ... into an hash of hashes and print them. ... The file has multiple MAC, PHY and Network Statistics in it and I am ...
    (comp.lang.perl.misc)