I have a customer with an existing ticketing system that generates tickets for events like theaters, movies, football and so on.

The information in each ticket is encoded in a 16 decimal digit numeric string. The information contains fixed positions for event date, event identifier, seat row, seat number and so on. This system has a numeric barcode on each ticket with room for 20 decimal digits. (https://en.wikipedia.org/wiki/Interleaved_2_of_5)

The main problem is that it is too easy for adversaries to generate false tickets with valid barcodes.

My customer now wants to encrypt the information in the barcode to make it more difficult to generate false tickets.

The requirements are as follows:

  • The plaintext is a 16 decimal digit (0-9) string.
  • The ciphertext is a 20 decimal digit (0-9) string.
  • Consecutive ticket numbers might differ only in a single digit position in the cleartext, the ciphertext for consecutive tickets must still be completely different.
  • It should be impossible to calculate the encryption key even if you have access to many valid tickets.
  • The encryption key is the same for all tickets for a certain event.
  • It must be difficult for an adversary to generate a valid ticket number, especially for a specific event.
  • Barcode readers used for validating tickets should work completely offline - it is not possible to have a complete database of valid ticket numbers available to the barcode readers.
  • Note that the 20-digit encrypted barcode after decryption must contain the full 16-digit plaintext. This means that we only have room for a 4-digit hash.

What kind of encryption and authentication should we use in this case? As I see it, the main problem is that the space in the barcode is very limited, so we can not use a real HMAC.

Any suggestions?

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Ella Rose Feb 15 at 15:58

Given that we can add only 4 digits (13.3 bits) of redundancy, there is no way to use asymmetric cryptography. We'll have to use a secret key in the verification terminals.

This is an application for Format Preserving Encryption. It can act like a block cipher, except we can decide the block width, and deal with decimal rather than binary or hexadecimal digits. Methods for FPE are given in NIST SP 800-38G. The previous link leads to references with other methods.

Take the 16-digit plaintext, append four zeroes, yielding 20 digits. Encipher that using FPE, yielding 20 digits, put that on the ticket.

On reading a ticket, check that it is 20 digits, decipher per FPE (yielding 20 digits), and consider the result valid when it ends with four zeroes; remove these.

  • 1
    $\begingroup$ Great answer! It is true that we do not have to calculate a true MAC. Because of the encryption adding four zeroes is secure enough! $\endgroup$ – Stefan Gustafsson Feb 15 at 16:18
  • $\begingroup$ @Stefan Gustafsson: Yes. Also, the encryption effectively increases the resistance to random forgery to the max when not all 10-digit values are valid, which is most likely the case. $\endgroup$ – fgrieu Feb 15 at 16:20
  • $\begingroup$ Do we use fixed tweak or random? If fixed, not recommended, then some information on the series of the ticket will be already the same and this will reduce a random attack. If the tweak is not fixed then where do we store, in the barcode? $\endgroup$ – kelalaka Feb 15 at 17:13
  • $\begingroup$ @Kelalaka: A tweak could be the identifier of the event (like a combination of date and location). Changing the tweak creates a new scrambling of the numbers, without the hassle of changing the key. The tweak needs not be secret or unpredictable, as long as the key and devices using the key are not available to adversaries. $\endgroup$ – fgrieu Feb 15 at 18:05
  • $\begingroup$ Stefan commented in my answer barcode reader knows what event, date, and section. But if we use day and location etc. that is fixed for all tickets of the section of the event. $\endgroup$ – kelalaka Feb 15 at 18:16

For this type of ticketing, you don't need encryption. Your system only needs to make sure that the tag on the ticket is correct. You can choose a random key $k$ ,128-bit or higher. then

$$\text{tag} = \operatorname{HMAC-SHA256}(k,\text{date}\mathbin\|\ldots \mathbin\| \text{row}\mathbin\| \text{seat}\mathbin)$$

It is mentioned in this answer HMAC-SHA256 it is secure against key recovery and forgery. Now truncate the output tag as you need. In your case, there is a special case that the tag size is 4-digit. So with 1/10000 probability, a random tag will be accepted. If this is not an acceptable probability, you need to change your barcode system.

  • $\begingroup$ Yes, I understand this, unfortunately I have a specific requirement for encryption. My third requirement is that even if the plaintext only changes in one position, the entire ciphertext must change. So, as far as I see it, encryption is a must. $\endgroup$ – Stefan Gustafsson Feb 15 at 11:21
  • $\begingroup$ The tag changes, too. If not, it will be easy to forge. The SHA-256 is a cryptographic hash function that has avalanche criteria. Besides, in block ciphers, one needs to have the same size input and output. $\endgroup$ – kelalaka Feb 15 at 11:24
  • $\begingroup$ In this case I would suggest encrypting as well, with some kind of format preserving encryption. While the MAC still can be guessed with the same probability, the adversary now simultaneously has to produce a ciphertext that would result in a valid plaintext. $\endgroup$ – Natanael Feb 15 at 11:31
  • 1
    $\begingroup$ A random attacker doesn't need to consider the encryption, a random guess will have still 1/10000 probability to success. The 4-digit causes this. $\endgroup$ – kelalaka Feb 15 at 11:33
  • 1
    $\begingroup$ @kelalaka If the 16 digits are unencrypted, there is a 1/10000 chance to guess a valid ticket number by guessing the 4 digits. If they are encrypted, there is a much higher chance to guess a "valid" ticket number where the "plain text" is already invalid (e.g. if the decrypted "plain text" has the scheme "date|row|seat" and contains an invalid seat number). $\endgroup$ – Martin Rosenau Feb 15 at 17:21

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.