Tag Info

Hot answers tagged

9

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 ...


8

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 ...


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 ...


5

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 ...


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 ...


5

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 ...


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 ...


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 ...


2

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.


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

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 ...


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

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" ...


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