The BSD checksum algorithm was a commonly used, legacy
checksum
A checksum is a small-sized block of data derived from another block of digital data for the purpose of detecting errors that may have been introduced during its transmission or storage. By themselves, checksums are often used to verify dat ...
algorithm. It has been implemented in old
BSD
The Berkeley Software Distribution (BSD), also known as Berkeley Unix or BSD Unix, is a discontinued Unix operating system developed and distributed by the Computer Systems Research Group (CSRG) at the University of California, Berkeley, beginni ...
and is also available through the
sum command line utility.
This algorithm is useless from a security perspective, and is weaker than the
CRC-32 cksum for error detection.
[ — manual pages from ]GNU
GNU ( ) is an extensive collection of free software (394 packages ), which can be used as an operating system or can be used in parts with other operating systems. The use of the completed GNU tools led to the family of operating systems popu ...
coreutils
The GNU Core Utilities or coreutils is a collection of GNU software that implements many standard, Unix-based shell commands. The utilities generally provide POSIX compliant interface when the environment variable is set, but otherwise offers ...
Computation of the BSD checksum
Below is the relevant part of the
GNU
GNU ( ) is an extensive collection of free software (394 packages ), which can be used as an operating system or can be used in parts with other operating systems. The use of the completed GNU tools led to the family of operating systems popu ...
sum source code (
GPL licensed). It computes a 16-bit checksum by adding up all bytes (8-bit words) of the input data stream. In order to avoid many of the weaknesses of simply adding the data, the checksum accumulator is circular rotated to the right by one bit at each step before the new char is added.
int bsdChecksumFromFile(FILE *fp) /* The file handle for input data */
Description of the algorithm
As mentioned above, this algorithm computes a checksum by segmenting the data and adding it to an accumulator that is circular right shifted between each summation. To keep the accumulator within return value bounds, bit-masking with 1's is done.
Example: Calculating a 4-bit checksum using 4-bit sized segments (
big-endian
'' Jonathan_Swift.html" ;"title="Gulliver's Travels'' by Jonathan Swift">Gulliver's Travels'' by Jonathan Swift, the novel from which the term was coined
In computing, endianness is the order in which bytes within a word (data type), word of d ...
)
Input: 101110001110 -> three segments: 1011, 1000, 1110.
''Iteration 1:''
segment: 1011 checksum: 0000 bitmask: 1111
a) Apply circular shift to the checksum:
0000 -> 0000
b) Add checksum and segment together, apply bitmask onto the obtained result:
0000 + 1011 = 1011 -> 1011 & 1111 = 1011
''Iteration 2:''
segment: 1000 checksum: 1011 bitmask: 1111
a) Apply circular shift to the checksum:
1011 -> 1101
b) Add checksum and segment together, apply bitmask onto the obtained result:
1101 + 1000 = 10101 -> 10101 & 1111 = 0101
''Iteration 3:''
segment: 1110 checksum: 0101 bitmask: 1111
a) Apply circular shift to the checksum:
0101 -> 1010
b) Add checksum and segment together, apply bitmask onto the obtained result:
1010 + 1110 = 11000 -> 11000 & 1111 = 1000
''Final checksum:'' 1000
References
{{Reflist
Sources
official FreeBSD sum source codeGNU sum source code
Checksum algorithms