# How to calculate leaked information from a check digit

Given a check digit calculated using mod 11, of an encrypted numeric sequence of 8 digits, how much information can be known about the plaintext?

More specifically, a single 3DES encrypted CBC block for which the check digit of the plaintext is known, would reduce by what factor the complexity in discovering the plaintext (and key)?

A second question is whether using the check digit hash as the IV is a good idea?

Example:

Given

encrypted = 0x672985cdd0484611


How much the information

checkdigit= 9


Will help in finding

plaintext = 12345678
key = 0x5e8667a439c68f5145dd2fcbecf02209  # md5(87654321)
iv = 0x45c48cce2e2d7fbd  # md5(9)[:8]


The motivation is to know if the check digit can be stored in plaintext alongside the encrypted data (always one block), and used as seed for the IV.

-

Assuming the mod 11 check digit is among 0123456789X, disclosing it reduces the number of possible plaintexts among 8-digit numbers by a factor of about 11 (from 100000000 to about 9090909; exactly how much depends very slightly on the value of the check digit), thus reveals about $\log_2(11)$ bits of information about the plaintext, that is just a little less than 3.46 bits.

The consequences vary depending on context. If the goal of an adversary is to rule out that a plaintext is a certain value, there are about 10 chances out of 11 that knowing the check digit allows the adversary to succeed.

In the hypothesis of "a single 3DES encrypted CBC block for which the check digit of the plaintext is known" because it is used to derive an IV using a deterministic method allowing to recover that check digit (as in the example where the IV is the MD5 hash of the check digit, truncated to 8 bytes), the worse problem might not be that the check digit is revealed by the IV. Another serious issue is that the same plaintext is always enciphered to the same ciphertext, which is foremost among what an IV is designed to prevent. If that's tolerable, we could just as well use 3DES in ECB mode on a single block, and live happier with a simpler system using no IV, and leaking less about the plaintext.

Knowing the check digit of the plaintext does not much help recovering the key. In the example, the key can best be found by enumerating the candidate keys (assumed to be the MD5 hash of a small string of decimal digits), and deciphering the ciphertext until the plaintext makes sense. The check digit still helps, in that it reduces the (already remote) odds of guessing the wrong key, by a factor of 11; however another ciphertext helps even more in this regard.

-
Very thorough, thanks. Your comment about ECB makes sense too: the plaintext will never repeat, so I guess we could do without CBC. –  lkraider Jun 22 '13 at 13:54

Knowing the check digit and the algorithm reduces the possible set of numbers from $10^8$ to under $10^6$. If there are other pieces of data available to the attacker (initials of the customer, ZIP code, etc.,) there could be enough information to correlate the customer with other sources of data without ever learning the account number. That may or may not be a concern for you.

The attack moves from a cipher text-only attack to a partially-known plaintext attack. It drastically reduces the pool of possible IV values, from $2^{64}$ to less than $2^{20}$, which might reduce the storage requirements for a meet in the middle attack on 3DES. It certainly does not improve your security. You'd definitely be better off using a secure random number for the IV.

-
I guess it is meant "reduces the possible set of numbers .. to under $10^7$", not "$10^6$". And perhaps "reduces the pool of possible IV values.. to $11$" rather than "less than $2^{20}$". –  fgrieu Jun 21 '13 at 5:15
@fgrieu, knowing the check digit is a specific value reduces it from $10^8$ to $10^7$ possibilities. Knowing the check digit algorithm lets me discard 10 out of every 11 possible remaining numbers. That's why it's < $10^6$. –  John Deters Jun 21 '13 at 12:26
Ah, I see what happens: you assume the check digit is part of the plaintext. I assume it is not, based on plaintext = 12345678 and md5(9) in the example which tends to show that the check digit (9) is not in the plaintext. –  fgrieu Jun 21 '13 at 14:19
Yes, that's likely an error in my assumption. In my experience, check digits are always incorporated into the numbers they are protecting - the last digit of credit card numbers, the last digits of UPC, EAN, and ISBN numbers, the last digit of a barcode, etc. They are always treated as a single series of digits to facilitate data entry. –  John Deters Jun 21 '13 at 19:13
@lkraider: 8 digits (e.g. 12345678) require 8 bytes with ASCII encoding (e.g. 0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38), but only 4 bytes with BCD encoding (̀̀e.g. 0x12,0x34,0x56,0x78). That can be reduced to 27 bits (obtained as $\lceil 8\cdot\log_2(10)\rceil$) by encoding as a number in binary (e.g. 0b000101111000110000101001110). –  fgrieu Jun 22 '13 at 14:12