Subject: 答复: RE: RE: about security level evaluation of draft-zhou-6man-mhash-cga-00

From: [email-masked]
Date: Mon, 9 Apr 2012 13:29:49 +0800

Hi，Huitema，

Regards~~~

-Sujing Zhou

Christian Huitema <[email-masked]> 写于 2012-03-29 08:23:38:

> Sujin,
> 
> Your statement  “after attacker has cracked a CGA address, then it 
> is in the same stand as the defender” is incorrect. The attacker 

Thank your for pointing out one of my omission that failing to recall the 
same value "modifier" is used in both HASH1 and HASH2. 

> will not need 65536 additional trials; he will need to find a 
> matching CGA address 65536 times, and each trial is just as complex 
> as finding a matching CGA address. The defender on the other hand 
> can pick any CGA address he wants, so he has to perform just 65536 
trials.

You may have a misundertand about my words.
By "cracked a CGA address", I mean the attacker has obtained another pair 
of public key and private key of his own, and has managed to 
find a suitable "modifer " so that the computated CGA address equals the 
CGA address under attack.
Yes, I　did not recall that the same modifier value is to be used in the 
computation of HASH2, so there is little manipulation space for the 
attacker to try a new modifier.

But I don't agree with you in  "each trial is just as complex as finding a 
matching CGA address."
suppose we define a new hash algorithm:
H'(modifier,public key, extension fields, subnet-prefix,collision count)
=HASH2(modifier,0,public key,extension 
fields)||HASH1(modifer,subnet-prefix,collision-count, public key, 
extension fields)
Is this new hash algorithm much much more secure than any one of its 
components?
If it is ,then we have found a good design method of hash algorithm.

As pointed out  by Tim Polk(?) when introducing SHA-3 progress at SAAG 
meeting this time, it is better to be algorithm agile before it is too 
late, 
too much replace cost will be required.

So, I suggest the earlier the problem resolved, the better. 

> -- Christian Huitema

> 
> 
> 
> From: [email-masked] [mailto:[email-masked]] 
> Sent: Wednesday, March 28, 2012 4:46 AM
> To: Christian Huitema
> Cc: [email-masked]; Jari Arkko
> Subject: 答复: RE: about security level evaluation of draft-
> zhou-6man-mhash-cga-00
> 
> 
> Regards~~~
> 
> -Sujing Zhou 
> 
> Christian Huitema <[email-masked]> 写于 2012-03-27 23:00:09:
> 
> > > Well, I think it is quite a simple trade-off. Increasing Sec 
> > increases computational effort on both sides by equal amount. 
> > Increasing the length of 
> > > the hash increases computational effort only on the attacker side.
> > As a result, the hash bits are relatively valuable.
> > 
> > Jari, the effect of sec is different on both sides. The effort is 
> > not increased "by equal amount" but rather "in the same proportion."
> > Suppose that an attacker could crack the 59 bit hash in a day with 
> > sec=0. Adding sec = 1 means that the attacker will have to try 65536
> > times as many keys. The time to crack becomes 65536 hours, i.e. 
> > about 7 years. The defender will have to try 65536 instead of one to
> > get the right sec, taking only  a fraction of a second. 
> 
> after attacker has cracked a CGA address, then it is in the same 
> stand as the defender. 
> defender, as well as attacker, has to try one by one to get the 
> right sec, i.e., to get a matching length of zeros, 
> how come attacker need extra 65536 hours but defender only needs a 
> fraction of a second? 
> 
> > > 1) Status quo: RFC 4982 eats three bits for Sec, leaving 59 bits 
> > of hash length after accommodating for u and g bits as well. The 
> > good with this is 
> > > that it leaves maximum size for hash. The bad is that it is less 
> > flexible for adding many new hash algorithms.
> > 
> > I kind of like the status quo.
> > 
> > > 2) The proposed new approach: Eat a total of six bits, for Sec and
> > the hash algorithm identifier. 56 bits remain. The good is that this
> > gives more 
> > > flexibility to allocate hash algorithms, including the ability to 
> > independently choose Sec and the algorithm. The bad is that the 
> hash size is 
> > > decreased.
> > 
> > Decreased a lot. On the other hand, if we do gain the flexibility to
> > define new algorithms, then we can define a mandatory-to-implement 
> > algorithm that incorporates the equivalent of the "sec" strengthening.
> 
> the security of a hash algo can be roughly estimated by length of its 
output,
> from birthday attack, that is about 2^(59/2) or 2^(56/2)(theorical 
> estimate), or less, 
> can you give a more precise of value of "a lot"? 
> I don't see flexibility in defining mandatory-to-implementing hash alg 
> 
> > -- Christian Huitema
> > 
> > 
> > 
> >

---

From: Christian Huitema <[email-masked]>
Date: Mon, 9 Apr 2012 06:12:42 +0000

> But I don't agree with you in  "each trial is just as complex as finding a matching CGA address."

It is just as complex -- unless of course someone cracks the hash algorithm. Absent a published crack, we have to assume that the best method for the attacker is an exhaustive search of salt values.

Of course, we have no guarantee that the hash algorithm will not be cracked at some point in the future, and algorithm agility is indeed a desirable property.

-- Christian Huitema