<commit_before># Flipping bits to arbitrary CRC values

<NAME><br/>
2020-10-10

## Abstract

This short paper describes a simple algorithm to select from several chosen
bits of a message to flip in order to obtain any desired cyclic redundancy
check (or CRC) value.

## Background

### CRC implementation

CRC is often implemented in software with a lookup table. The usually model is
given in [Rocksoft Model CRC Algorithm] [1]. There are several parameters to
the model:

1. The width of the polynomial.
1. The value of the polynomial.
1. The initial value for the register.
1. Whether each input byte is reflected before processing.
1. Whether the final register value should be reflected.
1. The value to XOR (exclusive-or) with the final register value.

Parameter 1, 2, and 4 determine the values in the lookup table.

Parameter 3 is akin to a xor-in value with the register initialized to zero.
This is similar to parameter 6, a xor-out parameter.

Parameter 5 is not interesting to our discussion here.

Under the lookup table method, an input byte is combined with the current
register value to lookup the corresponding pre-calculated value from the table.
This value is then used to update the register. The final register value might
be reversed before being XOR'd with the xor-out value.

Combining the xor-in value, the processing, and the xor-out value, [the CRC of
a message in terms of three components] [2] are shown below:

    CRC(m) = i ^ process(m) ^ o

where `i` is due to the xor-in value, `o` the xor-out.

The interesting aspect of the processing part is its linearity. That is, given
two messages `m_1` and `m_2` of the same length, `process(m_1 ^ m_2)` yields
the same value as `process(m_1) ^ process(m_2)`. This property is seen under
the [modulo arithmetic view of CRC functions] [3] (i.e.
`(a + b) mod m = ((a mod m) + (b mod m)) mod m`).

### Affinity

CRC is [affine with respect to the XOR operation] [4], i.e. given messages
`m_1`, `m_2`, and `m_3` of the same length:

    CRC(m_1) ^ CRC(m_2) ^ CRC(m_3) = CRC(m_1 ^ m_2 ^ m_3)

A sketch proof looks like this:

    CRC(m_1) = i ^ process(m_1) ^ o
    CRC(m_2) = i ^ process(m_2) ^ o<commit_msg>Fix Github-flavored markdown full reference links.<commit_after># Flipping bits to arbitrary CRC values

<NAME><br/>
2020-10-10

## Abstract

This short paper describes a simple algorithm to select from several chosen
bits of a message to flip in order to obtain any desired cyclic redundancy
check (or CRC) value.

## Background

### CRC implementation

CRC is often implemented in software with a lookup table. The usually model is
given in [Rocksoft Model CRC Algorithm][1]. There are several parameters to
the model:

1. The width of the polynomial.
1. The value of the polynomial.
1. The initial value for the register.
1. Whether each input byte is reflected before processing.
1. Whether the final register value should be reflected.
1. The value to XOR (exclusive-or) with the final register value.

Parameter 1, 2, and 4 determine the values in the lookup table.

Parameter 3 is akin to a xor-in value with the register initialized to zero.
This is similar to parameter 6, a xor-out parameter.

Parameter 5 is not interesting to our discussion here.

Under the lookup table method, an input byte is combined with the current
register value to lookup the corresponding pre-calculated value from the table.
This value is then used to update the register. The final register value might
be reversed before being XOR'd with the xor-out value.

Combining the xor-in value, the processing, and the xor-out value, [the CRC of
a message in terms of three components][2] are shown below:

    CRC(m) = i ^ process(m) ^ o

where `i` is due to the xor-in value, `o` the xor-out.

The interesting aspect of the processing part is its linearity. That is, given
two messages `m_1` and `m_2` of the same length, `process(m_1 ^ m_2)` yields
the same value as `process(m_1) ^ process(m_2)`. This property is seen under
the [modulo arithmetic view of CRC functions][3] (i.e.
`(a + b) mod m = ((a mod m) + (b mod m)) mod m`).

### Affinity

CRC is [affine with respect to the XOR operation][4], i.e. given messages
`m_1`, `m_2`, and `m_3` of the same length:

    CRC(m_1) ^ CRC(m_2) ^ CRC(m_3) = CRC(m_1 ^ m_2 ^ m_3)

A sketch proof looks like this:

    CRC(m_1) = i ^ process(m_1) ^ o
    CRC(m_2) = i ^ process(m_2) ^ o
{'fraction_non_alphanumeric': 0.0792169360346005, 'fraction_numerical': 0.01957659913498748, 'mean_word_length': 3.882222222222222, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2932615', 'n_tokens_mistral': 1374, 'n_tokens_neox': 1317, 'n_words': 696}