# Tag Info

18

In practice, CRC operations are often started with a nonzero state. Because of this, the actual equation is usually of the form: $$crc(a) \oplus crc(b) = crc( a \oplus b ) \oplus c$$ for some constant $c$ (which depends on the length of $a$, $b$). An alternative way of expressing this is, for three any equal-length bitstrings $a, b, c$, we have: $$crc(a)... 10 First of all, if your goal is to keep the garbled messages to "once every hundred years", well, you already don't meet that goal, even before the change. With an 8 bit CRC, a random change has a probability 1/256 of being accepted; hence if your wireless network has a transmission error at least once every three months (which, to me, sounds like an ... 10 Assuming the n-bit CRC of an unknown bit string b is known, one can constructively rebuild any consecutive n bits of b from the rest of the bit string (and the definition of the CRC). Indeed, in the case described, that speeds up password search considerably. One can compute the last 32 bits of the password (likely, 4 characters) from the beginning of the ... 7 You can have a look at the Wikipedia page on the mathematics of CRC. Among freely available resources, see also chapter 2 of the Handbook of Applied Cryptography. The two main ways to view a CRC-32 are: It is a linear operation in the vector space \mathbb{Z}_2^{32}. This means that the CRC(A \oplus B) = CRC(A) \oplus CRC(B) ("\oplus" is XOR). It is ... 7 If you have 62 chars you can transform 62 letters (10+26+26) in 6 bit number (approx). CRC is guaranteed to be unique mapping (Injective function) as long as input is shorter than output – you can have at most 10 letters, but not 11 since 62^{10} < 2^{64} < 62^{11}. It same goes whit most other hash functions. Lets say that you have hash function ... 6 This started as a comment to @Poncho's fine answer, and grew over the 600-char limit. Point is: a careful choice of the definition of V2 messages can keep some the existing capabilities of the original CRC to always detect some kinds of errors. Foremost, we are interested in short error bursts (where all bits in error are within a small number of ... 6 I guess that CRC is borrowed from the 32-bit Frame Check Sequence in the 1988 edition of CCITT V.42, section 8.1.1.6.2, available here, which gives a mathematical definition (note: remove the obviously spurious 1 after x^{30} in the English edition). I prefer this alternate definition with some of the math on polynomial replaced by equivalent ... 6 I have a different take on ralu's accepted answer and some of the comments thereafter. Consider two N-bit data sequences which we think of as polynomials$$D^{(1)}(x) = \sum_{i=1}^{N-1} D_i^{(1)}x^i ~~\text{and}~~D^{(2)}(x) = \sum_{i=1}^{N=1} D_i^{(2)}x^i where each $D_i^{(1)}$ and $D_i^{(2)}$ is $0$ or $1$. Let $M(x)$ of degree $64$ denote the CRC ...

5

I will assume that the question is "If we take the CRC-64 function, and consider inputs that consist only of the ASCII characters in the specified range, what's the longest inputs we can have without having a collision". The other answers assumed some mapping between the string and the CRC-64 function (and try to answer 'what sort of mapping would be best');...

5

I don't have that book, but I suspect that you are misreading it. It's always easy to find collisions with CRC, no matter what the divisor (more conventionally known as a polynomial) is. One easy way is to take the divisor and exclusive-or that bit pattern into an arbitrary place in the message (dividend); as in: 10011 : Divisor (polynomial) 10101011 ...

4

If we're talking about a malicious and intelligent attacker, you are mostly wrong, but not for the reasons you might expect. If we assume an intelligent attacker, then a CRC does not help; they can obviously modify a file, and either figure out how to update the CRC32, or how to make sure that the modifications do not change the CRC. On the other hand, if ...

3

My answer to how to recalculate a CRC32 on a large byte array and the comment which follows may explain it. The linearity comes from the fact that CRC is a remainder of dividing a high degree polynomial with binary coefficients (=data) by a fixed degree polynomial with binary coefficients (=crc polynomial). Adding of polynomials with binary ...

3

No, it is not safe to authenticate the BIOS in that way. CRC should be used as checksum only, i.e. to avoid random bit flips. For larger random changes you should use CRC32 at the minimum. If you want to protect against malicious change you need a cryptographically secure hash. the reason for this is that any attacker can create a malicious BIOS that ...

3

I recently posted an answer describing CRC computations on the math.stackexchange site. It discusses the basics of CRC-16 minus the bells and whistles mentioned in fgrieu's comment, but with minor modifications, applies to CRC-32 as well. Incidentally, CRC-32 uses a degree 32 polynomial, not a degree 33 polynomial as stated in Thomas Pomin's answer.

3

Well, 32 bits is somewhat short, so one could just try ciphertexts. However, there is a much better attack. Choose M0 arbitrarily, let P be the CBC padding for Headers || CRC || M0, and choose M1 so that CRC( M0 || P || M1 ) = CRC(M0). Submit M0 || P || M1 to be encrypted, truncate the ciphertext to the length of encryptions of M0, and then output the ...

3

Disclaimer: I have no first-hand knowledge of what hash (or MAC, or whatever method) DropBox uses for de-duplication; about if it is enough to know that (and its key, for a MAC) in order to download something from DropBox; and I see slightly diverging opinions about these points. If we consider the problem of finding a collision, the 160-bit hash defined by ...

3

Yes, it is very possible. And quite efficient, too. $\DeclareMathOperator{\crc}{crc}$CRC is linear, meaning $\crc(x \oplus y) = \crc(x) \oplus \crc(y)$. This property is fantastic for an attacker. Let your 100-byte message be called $m$. Now suppose you wish to change the value of the byte $a$ to $a'$. Compute $d = a \oplus a'$. Now, pad $d$ with zeroed ...

2

One problem not mentioned here is that CRC collisions are a certainty. If you were using a cryptographically secure hash, you would never encounter a false positive where both solutions were possible. In this scheme, every 256 messages would yield identical CRC values, and your different versions would be indistinguishable. You might be able to "stutter" ...

2

One fundamental property of CRCs is that if you exclusive-or in the bit representation of the polynomial (which, for standard CRC-32, would be 0x0104C11DB7) anywhere in the message, you don't modify the CRC. So, the obvious thing for you to try is to exclusive-or that value (and similar, for example, the bit-reversed version of above) and see if that ...

2

This is easiest to understand if we use polynomial arithmetic. The CRC of a message $m(x)$ is the remainder $r(x)$ of $m(x) x^k$ when divided by the CRC polynomial $f(x)$. Or more conveniently, the CRC is congruent to the message multiplied by $x^k$ modulo the CRC polynomial, $r(x) \equiv m(x) x^k \pmod{f(x)}$. If the message consists of a prefix $m_1$ and ...

1

No, in general using a CRC in this way is not secure. A CRC is not designed to be used against adversaries, it is used to detect random bit changes to the data it is protecting (as well as the CRC itself). A CRC of 16 bit will certainly not be as secure as an 8 byte MAC value, that was designed to protect against such attacks. Without additional measures a ...

1

For common CRC functions your function F exists as its inverse is essentially the way that CRCs of long streams of data are calculated without having to store significantly more than the value of the CRC. The existence of a unique inverse is a side-effect of some of the desirable guarantees provided by common CRC functions. In your terminology, given a ...

1

CRCs are based on irreducible polynomials, and the choice of polynomial is driven by the type of error to detect (e.g. CRC 32 for ethernet is "good" for single bits and double bits errors and a few more types of errors typical of noisy transmissions). As a general rules, all CRCs are good to detect single bits up to a certain volume of data (around 11 Kbit ...

1

I'll assume $n$ is a multiple of 4. One option is to compute the CRC16 of the bytes $d_{4j},d_{4j+1}$ ($0\le j<n/4$), giving 2 bytes appended as $d_{n},d_{n+1}$; and the CRC16 of the bytes $d_{4j+2},d_{4j+3}$, giving 2 bytes appended as $d_{n+2},d_{n+3}$. That reduces the work compared to the original solution, because each byte is processed once ...

1

A CRC or some other similar scheme is superior as they can be engineered such that single character changes or transpositions can be detected. A Bitcoin address uses a truncated hash function as a "checksum" but it is easily possible to have two valid addresses differing by one character 1ByteCoinAddressesMatch1kpCWNXmHKW 1ByteCoinAddressesMatch1kpCxNXmHKW ...

1

Neither CRC32 , nor MD5 are cryptographically secure. MD5 has known collision weaknesses and is therefore not to be considered cryptographically secure anymore. And CRC32 isn't even a hash… it's a “cyclic redundancy check” algorithm, which produces an “error-detecting code”. Cyclic redundancy checks are not and were never meant to be cryptographically secure....

1

CRCs are not cryptographically secure. If you need cryptographic security, replace the CRC with a message authentication code (MAC). If you don't need cryptographic security, then your question is off-topic for Crypto.SE and you should probably flag it to ask the moderators to migrate it to Computer Science.SE.

Only top voted, non community-wiki answers of a minimum length are eligible