Subject: CRC32C magic value -> shouldn't it be 0

From: Luben Tuikov <[email-masked]>
Date: Wed, 21 Nov 2001 15:28:23 -0800 (PST)

Hello there,

I've been implementing CRC32C for several days now and I was NEVER
able to get the results of the test cases of iSCSI draft v8.

I got to a point where I worked out the math myself and the results I
get are consistent.

I have two implementations, one simple shifting and another with table
lookup. They both yield the same results.

The problem is that any legal transformations, reorderings, etc, as
specified by the link, TCP, Ethernet, etc. protocols are transparent to
the sender and the receiver. E.g. data sent is the same data received
(assuming there was no noise or data corruption -- i.e. illegal
transformations).

If this is observed then I get ``magic'' value of 0 rather than
0x1c2d19ed. Here is my reasoning:

In the context of pp. 150-151 of iSCSI draft v8:

M(x) has been built MSB(lsb), i.e. the coefficient to x^(n-1), a_(n-1)
is the LS bit of the MS Byte, ... so on to a_0 which is the MS bit of
the LS byte.

Let M'(x) = x^32*M(x).

Then R(x) is computed as usual and then R(x) = ~R(x) as per the draft,
i.e. complement the coefficeints to yield r_31, ..., r_0, which are
appended in that order to the message. Call this message M''(x).

Now M''(x) looks like this:
  M''(x) = a_(n+31)*x^(n+31) + ... + r_31*x^31 + ... + r_0.

Now, this M''(x) is sent verbatim, and then received verbatim on the
other end of the wire -- as mentioned above -- assuming there was no
noise (all other link, Ethernet, etc. transformations are transparent
to us).

Now that the message has been received:
Then R(x) is computed as usual and then R(x) = ~R(x) (note the
algorithm symmetricity). At this point I get 0 and not 0x1c2d19ed. The
reason being is that M''(x) has a remainder ~0, since the remainder was
complemented before attaching it to M'(x) to form M''(x). But since we
always complement, we get R(x) = ~~R(x) (once before sending and once
after receiving) so the remainder is 0 as it should be.

Any comments, pointers, etc. would be greatly appreciated.

-l

=====
--

__________________________________________________
Do You Yahoo!?
Yahoo! GeoCities - quick and easy web site hosting, just $8.95/month.
http://geocities.yahoo.com/ps/info1

---

From: Luben Tuikov <[email-masked]>
Date: Thu, 22 Nov 2001 00:02:57 -0800 (PST)

(Cont'd from my previous message which is attached at the end.)

Furthermore I can XOR any value to R(x), recall that in
aritmetic modulo 2 XOR is both addition and subtraction,
to get that SAME value on the other end when ``unscrambling''
the message. (This result is detailed here below.)

This means that, just before sending the message over, M''(x),
I can XOR _any_ 32 bit unsigned value to the last 32 bits of M''(x),
in order to get that SAME value at the receiver's end...

So, I XOR-ed 0x1c2d19ed _just before sending over the wire_ just to get
that same value over at the receiver's end after CRC checking.

Reason being: M''(x) has no remainder* when divided by G(x) modulo 2,
so M''(x) + A(x), where A(x) is a polynomial of degree 31 or less
(that's important), will yield a remainder A when divided by G(x) which
has degree 32 (A(x) not divisible by G(x) modulo 2, since A(x) < G(x)
in context arithmetic modulo 2).

* Actually it has, 32 1's, since we had to complement R(x) before
appending it to M'(x) (as per the draft), but for sake of simplicity
lets ignore this for now.

All this means that if I receive a message from your implementations,
and XOR 0x1c2d19ed just after I get it from the wire, and then do CRC
checking I will get remainder 0. So why XOR it in the first place?

Please also note that complementing R(x) gives no apparent edge as it
is complemented again by the symmetricity of the algorithm.

Please comment on this matter.

-l

=====
--