1

We will have a symmetric key arriving in three component parts. Once all parts arrive, the key custodians will get together for a ceremony where each enters their part of the key into a secured system. This system will XOR the parts together to combine them into a final key that will be injected into the receiving system. The secret-combining system verifies that each custodian has correctly entered his or her part of the key by having each custodian enter a checksum for their key part; these checksums were generated at the time when the key was split. To avoid entering a corrupt key, if there are any errors in the data entry the process must be terminated and restarted.

My question is if there are standard checksum algorithms used for validating key entry into a multipart key exchange system? Or is this something each crypto vendor typically comes up with on their own?

John Deters
  • 33,650
  • 3
  • 57
  • 110
  • There are standards or at least customs https://crypto.stackexchange.com/questions/11879/kcv-and-compatibility-with-block-cipher-modes-of-operation https://crypto.stackexchange.com/questions/1930/sending-kcv-key-check-value-with-cipher-text https://crypto.stackexchange.com/questions/37379/calculating-3des-key-check-value-kcv https://crypto.stackexchange.com/questions/55484/will-two-keks-provide-the-same-kcv https://crypto.stackexchange.com/questions/55768/discrepancy-between-3des-in-openssl-and-pydes but that doesn't mean you must follow them. – dave_thompson_085 May 25 '18 at 03:08
  • @dave_thompson_085 These are designed to protect from transmission errors. For example a single character ASCII error may go undetected due to changing two bits (for parity checks). – forest May 25 '18 at 03:10
  • @forest: and a human typing in the wrong value for a key share is a form of transmission error – dave_thompson_085 May 25 '18 at 20:35
  • Indeed. I just meant that a human typing in the wrong value will have a different error profile than a transistor not flipping when it should. The KCV for the ASCII key "abcdefg" for DES will be equally valid for "bacdefg", but it would detect "a`cdefg" (a more likely machine error). – forest May 26 '18 at 01:39

1 Answers1

3

There is no standard algorithm for key verification*, but there are standard checksums.

Assuming verification is done to detect simple mistakes when retrieving or submitting the key, any reliable checksum algorithm such as CRC32 will work. In fact, it can be made transparent to the key-holder by including the checksum in the key itself. This can be done easily for any key K by creating K' = K || H(K), where H is a hash or checksum. Any error in the key itself or the checksum would result in the key being discarded. The keys being input could optionally have their checksum stripped after verification. This mirrors historical techniques where encryption keys for algorithms such as DES included parity bits in the standard to ensure every 8-bit chunk is odd-parity.

You have a few options for the checksum itself. Parity bits are the easiest to implement, but are designed to detect transmission errors where only a single bit is expected to change. A human-created mistake that changes "a" to "b" will result in two changed bits and a parity bit would not detect the change. Checksums are similar, but more complicated. They calculate a sum of the weighted multiplication of each component part of the input. CRCs on the other hand are designed for efficient error detection under nearly all circumstances. They can be guaranteed free of collisions for up to a certain number of errors. They have a configurable overhead.

Which one you use is up to you. CRCs are the most effective, since performance is not an issue (you won't be verifying millions of keys per second). A commonly used standard is CRC32c. It has a 32-bit output and has a well-chosen polynomial. If you only expect single-bit errors, parity checks will be a simpler option with less overhead (only one extra bit for each chunk of data).

* As pointed out in a comment, there are standards for verifying keys called Key Check Values, or KCVs, for example ANSI X9.24-1:2009 KCV. However, these are designed to detect electronic transmission errors, not human errors.


To answer your questions directly...

My question is if there are standard checksum algorithms used for validating key entry into a multipart key exchange system?

There is no standard for validating key entry, but there are checksums that have been standardized for error detection which you can safely use in your scheme. However, there is a standard for secret sharing (multipart key input) which is not your simple K' = K0 ⊕ K1 ⊕ K2. The algorithm is called Shamir's Secret Sharing and provides configurable parameters for the number of correct keys required to calculate the secret, the amount of redundancy against incorrect keys, etc.

In order to reduce the impact of incorrect input, you can use an error correcting code. These expand the size of the key material slightly, but ensure that the original value can always be derived even if it has up to a certain number of errors. The larger the error correcting code (and associated overhead), the more errors it can correct. This allows you not just to detect a mistake, but to correct it at the same time.

Or is this something each crypto vendor typically comes up with on their own?

Most vendors come up with things on their own due to a severe case of NIH syndrome, not because there are no standard primitives to work with or best practices to adhere to. The answer also depends on the specific organization. Various US intelligence agencies tend to use (or used) fill devices which often used parity bits for key integrity. The answer here is that they do typically come up with their own, sometimes flawed, scheme. This does not mean it is necessary to do so.

forest
  • 64,616
  • 20
  • 206
  • 257
  • ANSI X9 Key Check Values were the thing I was looking for. Thanks! – John Deters Jun 04 '18 at 20:48
  • @JohnDeters While not a _standard_ per se, you could also look at the [BIP39](https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki) mnemonic system. – forest Jan 25 '19 at 07:37