Minix' CRC implementation Hi, this is Johann N. Löfflmann, computer scientist from Munich, Germany. On March 1, 2008 I filed a bug on Minix's CRC implementation. The crc command was added to MINIX 1.3 on Sep 28, 1988 and the bug was undetected for more than 19 years and 5 months. That bug report was accepted as "[ minix Bugs Item #151] The update macro in Minix's crc implementation computes a wrong index for the table access (trackeritem-151)" The bug report contains important background information with respect to Minix's inherited CRC implementation - why it is wrong and explanations why the implementation will not be changed. The bug report was public, but unfortunately the URL called https://gforge.cs.vu.nl/gf/project/minix/tracker/?action=TrackerItemEdit&tracker_id=245&tracker_item_id=151 vanished from the web. Even the WaybackMachine seems to have stored only the overview of the tracker: https://web.archive.org/web/20170324193615/https://gforge.cs.vu.nl/gf/project/minix/tracker/ Fortunately I was able to grab the bug update notification email thread from my archived inbox and I have stored the mail thread in eml-format here for further/historic reference: https://jacksum.net/downloads/minix-bug-151.eml ... just in case someone scratches her/his head and asks why the Minix's CRC cannot be described by the "Rocksoft CRC model". Starting with Jacksum 3.0.0 (https://jacksum.net) supports the Minix' CRC implementation flavor: $ jacksum -a crc16_minix -q hex:48656C6C6F20576F726C640A 27710 12 and we know that after the fix, the return value will be 39386 (decimal), so $ jacksum -a unknown:16 -q hex:48656C6C6F20576F726C640A -E dec -e 39386 Trying 13 algorithms with a width of 16 bits that are supported by Jacksum 3.0.0 ... Trying 30 CRC algorithms with a width of 16 bits by testing against well known CRCs ... crc:16,1021,0000,false,false,0000 --> CRC-16/XMODEM => actually the crc16 on Minix should be the CRC-16/XMODEM, but in fact that never happend. $ jacksum -a crc:16,1021,0000,false,false,0000 -q hex:48656C6C6F20576F726C640A 39386 12 Since my provider doesn't allow to download .eml, you find the entire email in plain text below. On GNU/Linux you can call the following to extract the .eml from this text file: $ curl -s https://jacksum.net/downloads/minix-bug-151.txt 2>&1 | grep -A 200 ^== | grep -v == > minix-bug-151.eml $ jacksum -a sha3-256 -E hex minix-bug-151.eml 11000bcebb36ba17a4446f7cdc2a3db411b91be490362fbca728b09f98c41205 minix-bug-151.eml ========================================================================================================================================= X-Account-Key: account1 X-UIDL: 03f7cd8284e97007694663a303fc8b2b X-Mozilla-Status: 0001 X-Mozilla-Status2: 00000000 X-Mozilla-Keys: X-Envelope-From: X-Envelope-To: X-Delivery-Time: 1262609404 X-UID: 50580 Return-Path: X-RZG-CLASS-ID: mi Received: from gforge.cs.vu.nl ([130.37.20.36]) by mailin.webmailer.de (zeb mi58) (RZmta 22.6) with ESMTP id 6012b8m04CnD4C for ; Mon, 4 Jan 2010 13:50:04 +0100 (MET) Received: from root by gforge.cs.vu.nl with local (Exim 4.63) (envelope-from ) id 1NRmNo-0004hh-D6 for jonelo@jonelo.de; Mon, 04 Jan 2010 13:50:04 +0100 To: jonelo@jonelo.de From: "GForge" Reply-To: "GForge" Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 8bit" Subject: =?utf-8?B?WyBtaW5peCBCdWdzIEl0ZW0gIzE1MV0gVGhlIHVwZGF0ZSBtYWNybyBpbiBNaW5peCdzIGNyYyBpbXBsZW1lbnRhdGlvbiBjb21wdXRlcyBhIHdyb25nIGluZGV4IGZvciB0aGUgdGFibGUgYWNjZXNzICh0cmFja2VyaXRlbS0xNTEp?= X-Mailer: PHP/5.2.0-8+etch16 Message-Id: Date: Mon, 04 Jan 2010 13:50:04 +0100 Bugs item #151, was opened at 2008-03-01 15:24:14 Priority: 3 Submitted By: Johann Löfflmann (jonelo) >Assigned to: David van Moolenbroek (dcvmoole) Summary: The update macro in Minix's crc implementation computes a wrong index for the table access Product: N/A Version: N/A Component: N/A Resolution: Accepted As Bug Status: Closed Severity: N/A URL: Initial Comment: The update macro in Minix's crc implementation computes a wrong index for the table access. The table in crc.c is correct, it keeps values for a CRC with 16 bit width and the polinomial x^16 + x^12 + x^5 + 1 (0x1021). However the update macro is wrong in crc.c: #define updcrc(cp, crc) ( crctab[((crc >> 8) & 255)] ^ (crc << 8) ^ cp) In a table driven CRC model, each byte of an input stream has direct impact on the index of the table. This is not the case for the Minix crc implementation. The correct macro would be #define updcrc(cp, crc) ( crctab[((crc >> 8) & 255) ^ cp] ^ (crc << 8) ) Example: -------- # echo "Hello World" > hello.txt # hexdump hello.txt 00000000 48 65 6C 6C 6F 20 57 6F 72 6C 64 0A Hello World. sha1(hello.txt) = 648a6a6ffffdaa0badb23b8baf90b6168dd16b3a Before the fix: # crc test.txt 27710 12 hello.txt After the fix: # crc test.txt 39386 12 hello.txt --jonelo ---------------------------------------------------------------------- You can respond by visiting: https://gforge.cs.vu.nl/gf/project/minix/tracker/?action=TrackerItemEdit&tracker_id=245&tracker_item_id=151 Or by replying to this e-mail entering your response between the following markers: #+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+ (enter your response here) #+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+ ---------------------------------------------------------------------- Follow-Ups: ------------------------------------------------------- Date: 2008-03-01 15:28:42 By: Johann Löfflmann Comment: Correction (there was a filename typo in my first posting): Before the fix: # crc hello.txt 27710 12 hello.txt After the fix: # crc hello.txt 39386 12 hello.txt --jonelo ------------------------------------------------------- Date: 2008-03-08 14:03:48 By: Johann Löfflmann Comment: Fix verification with Jacksum (www.jonelo.de/java/jacksum). It is one of the free software tools on the web which is able to specify a CRC algorithm according to the "Rocksoft (tm) Model CRC Algorithm". Example: # jacksum -a crc:16,1021,0,false,false,0 -q hex:48656C6C6F20576F726C640A 39386 12 --jonelo ------------------------------------------------------- Date: 2009-06-13 18:10:02 By: David van Moolenbroek Comment: Thank you for submitting this bug report. Let me start by saying that you're absolutely right. I'm not yet sure what we're going to do with this - sometimes it is better to be consistent than to be right - but I'd just like to add what I found out about the origin of this bug so far. The comment in crc.c right above the updcrc() macro lists Stephen Satchell and Chuck Forsberg as copyright holders of the macro. The code in question is a literal copy of the "rzsz" ZMODEM implementation (which is also part of MINIX, in /usr/src/commands/zmodem), written by the same Chuck Forsberg. In fact, the ZMODEM protocol itself is Chuck Forsberg's work. ZMODEM was predated by XMODEM/CRC, which added a 16-bit CRC to the XMODEM protocol. The CRC chosen was CRC-CCITT. Apparently [1] introduced by John Mahr, this XMODEM extension was documented by John Byrns in "MODEM PROTOCOL OVERVIEW, CRC OPTION ADDENDUM" on Jan 13, 1985 [2]. This addendum contains an explanation and an example C implementation of the protocol, which works correctly. This addendum appears in the Oct 10, 1985 version of the "XMODEM/YMODEM PROTOCOL REFERENCE" document [3]. However, the June 18, 1988 version of the same XMODEM/YMODEM PROTOCOL REFERENCE document [4], while leaving the explanation text as is, replaces the calcrc() example with an updcrc() routine example, taken from the same "rzsz" code. The text also mentions that rzsz includes a table-driven version of the code. The updcrc() routine, just like the table-driven version with the udpcrc macro, does not compute CRC-CCITT correctly. ZMODEM became the de-facto standard and with that, Chuck Forsberg's flawed CRC implementation survived. Going by the text in the June 20, 1986 "Xmodem, CRC Xmodem, Wxmodem File Transfer Protocols" document [5], his code was based on ".. routine M4 in Steven Satchell's paper, 'Test of CRC Routines for CRC-CCITT', ..". This paper might provide more insight as to where things went wrong exactly, but as I cannot find a copy of it online anymore, perhaps we'll never know. Interestingly, the same 1986 "File Transfer Protocols" document credits the original, correct calcrc() reference implementation to Chuck Forsberg as well. In any case, one Johan Stevenson took the flawed table code and used it as basis for MINIX's crc. crc was added to MINIX 1.3 on Sep 28, 1988 [6]. Somehow it is fairly amusing that the one-line macro in question has an accompanying 11-line comment detailing usage, authorship and copyright, and yet fails at the one thing it needs to do properly. [1] http://en.wikipedia.org/wiki/XMODEM [2] http://aelinik.free.fr/crc.htm [3] http://www.textfiles.com/programming/ymodem.txt [4] http://www.techfest.com/hardware/modem/xymodem.htm [5] http://www.textfiles.com/programming/FORMATS/xmodem.pro [6] http://groups.google.com/group/comp.os.minix/msg/f62b322aef047f7e ------------------------------------------------------- Date: 2009-10-02 12:34:25 By: David van Moolenbroek Comment: Given that it is consistently wrong, we'll just leave it like this for now. If anybody ever finds a case where such wrong-but-valid crc(1) output is an actual issue, we can change it then. ______________________________________________________________________ You received this email because you requested to be notified when changes were made to this tracker. If you don't wish to be notified in the future, please login to https://gforge.cs.vu.nl/gf/account/?action=Login and click this link: https://gforge.cs.vu.nl/gf/?action=Monitor§ion=tracker&ref_id=245&redirect_to=%2Fgf%2Fproject%2Fminix%2Ftracker%2F¬ify=0