0
$\begingroup$

As an initial disclaimer, I know virtually nothing about coding theory. I apologize in advice for incorrect or inappropriate terminology.

The problem space I'm exploring is ensuring the integrity of bulk data being transported "trans-continentally" across multiple R&E networks. The messages can be up to many gigabytes in size. I suspect that there is a very low incidence (< every 10^12 bytes transmitted) of byte swapping that can occur in transit that the 16bit 1's compliment checksum used by our data format, TCP, & IPv4 headers is insensitive to. The CRC schemes used by the various layer 2 segments in the path should be sensitive to byte swapping but I A) lack the knowledge to estimate the probability of corruption happening that could bypass both a CRC scheme and a 16 bit 1's compliment, B) can't rule out that the issue isn't occurring "in between" layer 2 segments, and C) still need an end-to-end mechanism to detect this type of event so I feel that trying to answer #A isn't necessarily helpful.

The current solution has been to independently transmit a md5 digest (on the same network path). However, it's occurred to me that the separate md5 digest is also vulnerable the byte swapping issue while in transit. In practice, it's generally possible to re-transmit either the message or the digest but I would like to consider the case when this isn't possible. This has lead me to the question: What is the most robust method of distinguishing between corruption in the digest and the message?

  • Is there a hash algorithm that produces a digest with inherent ECC properties?

  • In "practice", are there examples of ECCs being calculated to protect digests?

  • Is it reasonable to use two independent hash functions to produce digests of the same message?

    • If so, how does one go about selecting multiple hash functions that are likely to have different [in]sensitivities?
  • Should I be considering using a form of ECC over the entire message instead of independent digests?

    • If so, is there an ECC algorithm that both decodes faster than polynominal time and is independent of the original message such that it can be used without requiring an ECC decode on every read?

I realize this is a bit of a novel. Many thanks in advance to anyone willing to answer any of these questions.

$\endgroup$
  • $\begingroup$ You may want to look into Parchive, which was created for a similar use case. A cryptographic hash function like MD5 isn't equipped to tell you where the error is, just whether or not there is one. $\endgroup$ – Snowball Feb 27 '14 at 0:21
  • $\begingroup$ I'm aware of Parchive and thought it was completely dead (last CVS commit was 8 years ago). Googling turns up discussion of a par3 but I'm unable to locate a code repository, so I'm assuming it's still dead. In any event, my question(s) are specifically algorithmic as my application involves operating on data in memory and/or in a streaming fashion and archiving data for what is is essentially an infinite time period (at least on the human scale). $\endgroup$ – Joshua Hoblitt Feb 27 '14 at 1:52
2
$\begingroup$

I'm not sure that this question really belongs here, because it's more about the engineering side of CS than about the mathematical side, but:

  • Is there a hash algorithm that produces a digest with inherent ECC properties?

Unlikely. Generic hash algorithms are typically designed either to detect a certain class of error or (in the case of cryptographic ones) such that a change of 1 bit in the input will change approximately 50% of the bits in the output. ECC belongs in a higher layer.

  • Is it reasonable to use two independent hash functions to produce digests of the same message?

It's not unreasonable, but you're already doing that, so I'm not sure why you ask the question.

  • If so, how does one go about selecting multiple hash functions that are likely to have different [in]sensitivities?

Pick two which have different design goals, e.g. a CRC and something from the SHA family. Or pick two cryptographic hashes from different families, such as SHA-2 and SHA-3.

  • Should I be considering using a form of ECC over the entire message instead of independent digests?

I assume that the bottleneck is the network rather than the CPU time spent hashing and verifying, if you're experiencing error rates of about 1 in $10^{12}$ it seems like a tremendous waste to add more overhead than 1 in $10^6$ bytes. That points at using something like your current approach of error detection with retransmission.

I understand your concern that it might be the hash which is corrupted rather than the block of data hashed. One possible response is: what are the odds? If you send a 128b = 16B hash for every 16MB of data, the odds are 1 in $10^6$ that it was the hash which was corrupt rather than the block.

On the other hand, you could possibly take a hash tree approach. For every block you send a hash; for every $n$ hashes you send a hash of the hashes. Tune the block size and the value of $n$ as desired.

$\endgroup$
  • $\begingroup$ I agree that this question is not a great fit for the mathematics stack but I couldn't find a better location for questions on applied math. $\endgroup$ – Joshua Hoblitt Mar 17 '14 at 20:56
  • $\begingroup$ This response was great - Thank you! I need to do some reading up on Merkle trees to see if that's a viable approach for us. $\endgroup$ – Joshua Hoblitt Mar 17 '14 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.