********************************************************************* FTSC FIDONET TECHNICAL STANDARDS COMMITTEE ********************************************************************* Publication: FTS-1030 Revision: 1 Title: Binkp optional protocol extension CRC Checksum. Authors: Tobias Ernst (publisher of this protocol), Michiel Broek (documentation for FTSC). FTSC members and administrator. Date: 2014-09-21 --------------------------------------------------------------------- Contents -------- 1. Definitions 2. Binkp CRC Checksum Mode 2.1 Introduction 2.2 Protocol specification 2.3 Further thoughts 2.4 CRC-32 Algorithm 3. Compatibility issues A. References B. History --------------------------------------------------------------------- Status of this document ----------------------- This document is a FidoNet Technical Standard (FTS). This document specifies an optional FidoNet standard for the FidoNet community. This document is released to the public domain, and may be used, copied or modified for any purpose whatever. This document supersedes and replaces FSP-1020. FSP-1020 is preserved in the FTSC reference library as FRL-1022. The CRC algorithm described in this document can be used for file forwarding as explained in FSC-0028 and might be easier to understand. Note that FSC-0060 also describes CRC algorithms. Do not use it, the algorithm documented in FSC-0060 is in error. 1. Definitions -------------- The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [FTA-1006]. 2. Binkp CRC Checksum Mode -------------------------- 2.1 Introduction ---------------- Binkp originally was designed to work on top of a reliable transmission layer, i.E. a transmission layer that has its own checksums, like TCP. Therefore, the Binkp specification does not provide a way for controlling correct data transfer, because it is assumed that the underlying TCP transport layer does the necessary data integrity checks. However, I have seen TCP connections trashing data at random, and actually have suffered from mail loss because a file received by binkd was not identical with the file that the sender has transmitted. Therefore, this document specifies an extension to the Binkp protocol which allows data integrity checks by means of CRC32 checksums. It is intended as an *optional* feature in Binkp for those nodes that live in places with an unreliable TCP routing structure (like I seem to do), and it is fully backwards compatible. It is highly recommended to use this extension when receiving files using the optional NR mode (FTS-1028). It will ensure that any file received in two or more parts matches the file on the sending system before it is acknowledged, and deleted by the sending system. 2.2 Protocol specification -------------------------- During session handshake, a mailer that knows the CRC protocol extension MAY send an "M_NUL OPT CRC" message. This indicates that the mailer is able to process the CRC-extended "M_FILE" messages described below, nothing more. The other end which receives the OPT CRC message will switch to CRC-secure mode (probably only if CRC-secure mode has been allowed by the sysop for the particular other end). Note that even if this end previously has sent a M_NUL OPT CRC on its own, it is not forced to switch to CRC mode, it is just an option. In the following, the "sending end" is the Binkp mailer which is transmitting a file, and the "receiving end" is the mailer which is receiving it. Of course, in a Binkp session, both sides can become both sending and the receiving ends. When the sending end is in CRC-secure mode, it will send an extended M_FILE message with an additional fifth argument, specifying a CCITT CRC32 checksum for the file that is following. This means that the mailer has to calculate the checksum before transmitting the file. The checksum is pre-conditioned and postconditioned. This means that the initial CRC-value is 0xFFFFFFFF (preconditioning), and after the final value has been computed, all bits must be in- verted (postconditioning). The CRC polynomial to be used is: X^32+X^26+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0. The format of the fifth M_FILE argument is a sequence of up to eight hexadecimal digits in ASCII. The letters a-f may be converted to lower case. Leading zeros may be omitted, trailing digits must not be omitted. The receiving end, if it has sent an "M_NUL OPT CRC", MUST be able to process M_FILE messages with either four or five arguments. If it receives a M_FILE message with five arguments, it will treat the fifth argument as a checksum and, after receiving the file, will compare this checksum with the checksum it has computed from the data that has been received. If the checksums disagree, the receiving end has two options. It can either send a M_SKIP for this file. This will cause a non-destructive reject of the file, so that the session goes on, but the remote site will mark the file as not sent successfully and retransmit it in the next session. Or it can send a M_ERR, indicating a fatal failure, which will terminate the session, and also cause a non-destructive reject of this and all following files. It is suggested that on the first CRC failure, a M_SKIP is sent, but if the next file also has an error, indicating that the session is completely faulty, a M_ERR could be transmitted instead. 2.3 Further thoughts -------------------- There are some disadvantages of this way of implementing CRC: 1. The CRC checksum must be computed before the file transmission STARTS, instead of during the transmission. 2. The protocol will fail if errors don't occur spontaneous, but regularly with an error rate greater than 1 error per file. In this case, transmission will be impossible because all files will always be rejected. Why then implement it this way? It is the easiest way to implement CRC fully backwards compatible, and it is the way that requires the least amount of changes in the code of existing binkp mailers. Even given the mentioned disadvantages, the extension is good enough for detecting spontaneous transmission errors, so that sysops will not loose valuable data, and so that they can see that there is a problem in the network infrastructure and fix it. That is, this extension is intended as a safeguard against rare error conditions on a transport layer that still, basically, is reliable. This extension, however, is not suitable for transmission over a transport layer which is unreliable by definition, as a standard modem connection. But that was not the goal of binkp from the beginning. In the future, it might be worth considering an extension to the binkp protocol which goes further. For example, one CRC32 checksum could be transmitted at the end of each frame, and a mechanism for directly resending frames added. 2.4 CRC-32 Algorithm -------------------- The checksum algorithm that is used is CRC-32 following ITU-T's specifications. For further information refer to the literature list given below. The following pseudocode shows how to calculate such a checksum for a file of N bytes indexed from 0 to N-1 and stored in BUFFER. The XOR, AND and NOT logical operations are to be executed bit-wise. In C, for instance, XOR equals ^, AND equals &, and NOT equals ~. // CRC, I, J, K are unsigned integers of at least 32 bits. UNSIGNED LONG CRC, I, J, K // Preconditioning CRC = FFFFFFFF // Loop through all bytes in the file FOR J = 0 TO N-1 K = (CRC XOR BYTE#J) & 000000FF // (*) FOR I = 8 DOWNTO 1 IF K AND 1 <> 0 THEN K = (K SHR 1) XOR EDB88320 ELSE K = K SHR 1 ENDIF END FOR // (**) CRC = ((CRC SHR 8) AND 00FFFFFF) XOR K END FOR // Postconditioning: Flip all bits CRC = NOT CRC; Note that the initial value of K is limited to the range of 0 up to 255. (see line marked by '(*)'). Therefore it is a good idea to replace the inner loop with a lookup table routine, i.e. generate a lookup table with the results of the inner loop for the start values of 0 up to 255, and then replace the loop marked by '(*)' and '(**)' with something like: K = LOOKUPTABLE [ (CRC XOR BYTE#J) XOR 000000FF ] Author: Tobias Ernst 3. Compatibility issues ----------------------- The CRC option cannot be used together with some other options which also use extra parameters with the M_FILE messages. This currently includes the GZip and BZip2 file compression options. A. References ------------- [FTS-1026] Binkp/1.0 Protocol specification. [FTA-1006] Key words to indicate requirement levels, Fidonet Technical Standards Committee administrative. FTA-1006. [ITU-T V.42] International Telecommunications Union, Error-correcting Procedures for DCEs Using Asynchronous-to-Synchronous Conversion, ITU-T Recommendation V.42, 1994, Rev. 1. [ISO 3309] International Organization for Standardization, "Information Processing Systems--Data Communication High-Level Data Link Control Procedure--Frame Structure", ISO 3309, October 1984, 3rd Edition. B. History ---------- Rev.1, 2014-09-21: First release.