netdev - RE: [PATCH 10/16] batman-adv: use CRC32C instead of CRC16 in TT code

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <AE90C24D6B3A694183C094C60CF0A2F6026B7386@saturn3.aculab.com>
Date:	Wed, 9 Oct 2013 17:19:44 +0100
From:	"David Laight" <David.Laight@...LAB.COM>
To:	"Antonio Quartulli" <antonio@...hcoding.com>
Cc:	<davem@...emloft.net>, <netdev@...r.kernel.org>,
	<b.a.t.m.a.n@...ts.open-mesh.org>,
	"Antonio Quartulli" <ordex@...istici.org>,
	"Marek Lindner" <lindner_marek@...oo.de>
Subject: RE: [PATCH 10/16] batman-adv: use CRC32C instead of CRC16 in TT code

> On Wed, Oct 09, 2013 at 04:49:53PM +0100, David Laight wrote:
> > > > Are you really generating CRC32 of a pile of ethernet MAC addresses
> > > > and the XORing the CRC together?
> > > > That gives the same answer as XORing together the MAC addresses and
> > > > then doing a CRC of the final value.
> > >
> > > I was not sure about this since the CRC32 is not a linear operation. However
> > > this routine is not on the fast path, so we can also live with this order.
> >
> > All CRC are linear.
> > Because '(a + b) mod c' is the same as '((a mod c) + (b mod c)) mod c'.
> >
> > The CRC of a buffer is the XOR of the CRCs generated for each '1' bit.
> > The CRC for each bit depends on how far it is from the end of the buffer.
> 
> In our tables we cannot make any assumption about the order of the entries: the
> node whom generated the table may store the entries in a different order from
> what we have got.
> This is why I did not implemented it as a simple CRC of the
> whole the GlobalTable/buffer but I CRC'd each MAC+VID on its own.
> 
...
> 
> Assuming what I said above (that we cannot make assumptions on the order of the
> entries), what is your suggestion?

I'm not sure what you are using this CRC for.
If you are trying to use it to check that the two tables match - so a
full update isn't needed then it just won't work.

If you take out 11:22:33:44:55:60 and 11:22:33:44:55:61 and
change 99:88:77:66:55:40 to 99:88:77:66:55:41 then the XOR of
the CRCs won't change.
For MAC addresses such changes aren't that unlikely.

	David