Subject: Re: [81attendees] What is it at the bottom of restaurant receipts?

From: "Worley, Dale R (Dale)" <[email-masked]>
Date: Tue, 9 Aug 2011 13:20:08 -0400

Comparing a few receipts, I've so far discovered:

There are always 12 dingbats in the row.

There are never duplicates on a single receipt.  This suggests that the dingbats are not a direct transcription of information, but rather statistically random.

One can easily stack 5 receipts (60 dingbats) and see no duplicates.  This suggests (via the birthday paradox) that there are more than 60^2 = 3600 dingbats that are commonly used.

My current guess is that there are 4096 dingbats representing 12 bits each, and the line represents 12 * 12 = 144 bits that are either a hash or a digital signature of the data in the hash.  The dingbats are probably to be visually compared by a human with a similar display that is computed by a government device from the data on the receipt.

Curiously, on one receipt I have, the dingbat row consists of a sequence of 6 dingbats repeated twice, which seems to me to be very unlikely.

Dale

---

From: Ben Campbell <[email-masked]>
Date: Tue, 9 Aug 2011 12:31:24 -0500

I asked a couple of waiters about them, and they had no idea what the dingbats were for. That tells me that they don't use them for anything. They use the barcodes for everything. That makes me wonder if the dingbats were put there for restaurants that didn't invest in the bar-code system, as some sort of alternative verification. Or maybe they're only used by auditors. Or in expense reimbursement. 

On Aug 9, 2011, at 12:20 PM, Worley, Dale R (Dale) wrote:

> _______________________________________________
> 81attendees mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/81attendees

---

From: "John R. Levine" <[email-masked]>
Date: 9 Aug 2011 13:35:05 -0400

> I asked a couple of waiters about them, and they had no idea what the dingbats were for. That tells me that they don't use them for anything. They use the barcodes for everything. That makes me won…

I like the hash for audit theory.  It makes it harder to fake a receipt, 
which otherwise would be pretty easy if you're sending in scans of 
receipts, just load up gimp and cut and paste a few digits to adjust the 
amount.

Regards,
John Levine, [email-masked], Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. http://jl.ly

---

From: Paul Coverdale <[email-masked]>
Date: Tue, 9 Aug 2011 13:58:27 -0400

Just to add a bit more to the mystery, I had exactly the same lunch on 3
days. On each of the 3 receipts the row of 12 dingbats is completely
different, not even a repeat of any character.

Google doesn't help much. I did a search for "Quebec City" and "dingbats",
but it just came back with a listing of all the members of the National
Assembly... (that's a Canadian joke, by the way).

...Paul

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]]
>On Behalf Of Worley, Dale R (Dale)
>Sent: Tuesday, August 09, 2011 1:20 PM
>To: [email-masked]
>Subject: Re: [81attendees] What is it at the bottom of restaurant
>receipts?
>
>There are never duplicates on a single receipt.  This suggests that the
>dingbats are not a direct transcription of information, but rather
>statistically random.
>
>One can easily stack 5 receipts (60 dingbats) and see no duplicates.
>This suggests (via the birthday paradox) that there are more than 60^2 =
>3600 dingbats that are commonly used.
>
>My current guess is that there are 4096 dingbats representing 12 bits
>each, and the line represents 12 * 12 = 144 bits that are either a hash
>or a digital signature of the data in the hash.  The dingbats are
>probably to be visually compared by a human with a similar display that
>is computed by a government device from the data on the receipt.
>
>Curiously, on one receipt I have, the dingbat row consists of a sequence
>of 6 dingbats repeated twice, which seems to me to be very unlikely.
>
>Dale

---

From: Tobias Gondrom <[email-masked]>
Date: Tue, 09 Aug 2011 19:14:32 +0100

Ok guys, let's shed some light on this:
Found this out when I was in Quebec. It's to prevent tax evasion.
See info here: http://ladditionsvp.com/
and here in English:
http://www.revenuquebec.ca/en/centre-information/actualite/2011/2011-06-23.aspx

Kind regards and all the best, Tobias

---

From: Andrew Thurber <[email-masked]>
Date: Tue, 9 Aug 2011 14:15:09 -0400

This appears to be mandated by the new Revenu Quebec SRM system required at all restaurants to eliminate "Zapper" style tax fraud, with the receipts encoding a digital signature and fingerprint using the bar code and character string.

The SRM literature I found specifically does NOT describe the generation, encoding or purpose of the fields in the footer, though it carefully describes all other aspects of the receipts.

I don't know the algorithm or how Revenu Quebec would use the data.

Andrew

On Aug 9, 2011, at 1:58 PM, Paul Coverdale wrote:

...Paul

---

From: Tobias Gondrom <[email-masked]>
Date: Tue, 09 Aug 2011 19:07:19 +0100

Ok guys. To shed some light on this: Found this out when I was in 
Quebec. It is to prevent tax evasion.

See the information here http://ladditionsvp.com/
and here in English: 
http://www.revenuquebec.ca/en/centre-information/actualite/2011/2011-06-23.aspx

Kind regards, Tobias

---

From: "Worley, Dale R (Dale)" <[email-masked]>
Date: Tue, 9 Aug 2011 14:46:57 -0400

> From: Tobias Gondrom [[email-masked]]
> 

And somewhere on Revenue Quebec's web site I found an image with
annotations about the various parts of the receipt that are generated
by the SRM.  But nothing explaining the dingbats.

(I notice that Revenue Quebec isn't bothered by publishing tax
information in English!)

Dale

---

From: Ted Lemon <[email-masked]>
Date: Tue, 9 Aug 2011 14:52:19 -0400

> by the SRM.  But nothing explaining the dingbats.

Quite possibly it is just a binary buffer dump, possibly due to a bug in the cash register software, or was put in for debugging.

---

From: "John R. Levine" <[email-masked]>
Date: 9 Aug 2011 15:09:48 -0400

> Quite possibly it is just a binary buffer dump, possibly due to a bug in the cash register software, or was put in for debugging.

Considering that it appears in exactly the same place on every resto 
receipt I got in Quebec, from many different restos, that would be a heck 
of a bug.

Regards,

---

From: Richard Barnes <[email-masked]>
Date: Tue, 9 Aug 2011 15:11:48 -0400

Not addressing the dingbats, but as far as the barcodes:

The barcodes are apparently in the ISO-standard PDF417 format:
<http://en.wikipedia.org/wiki/PDF417>

It appears you get meaningful data if you do the following:
1. Decode PDF417 as text
2. Base64-decode

Using that technique, I was able to match several fields from
different receipts:
-- MEV ID number (binary)
-- Transaction number ("FACTURE#"/"ADDITION#") (ASCII)
-- Table number (ASCII)
-- Server name (ASCII)
-- TPS amount (binary)
-- TVQ amount (binary)
-- Total amount (binary)

In all of the three cases I looked at, the first intelligible field
(the MEV ID) appears at position 0x40 in the binary.  This would be
consistent with the overall code having the form (digest, data), if
the digest were 512 bits long, say SHA512.  Chopping of the first 0x40
octets and hashing the remainder with SHA-512 did not give the right
hash values.   But then again, you wouldn't expect that if the hash
were an HMAC instead of just a digest; it would make a lot of sense
for the machine to compute the HMAC with a secret key that the tax
department knows.

FWIW,
--Richard

On Tue, Aug 9, 2011 at 1:35 PM, John R. Levine <[email-masked]> wrote:
>> I asked a couple of waiters about them, and they had no idea what the
>> dingbats were for. That tells me that they don't use them for anything. They
>> use the barcodes for everything. That makes me wonder if the dingbats were
>> put there for restaurants that didn't invest in the bar-code system, as some
>> sort of alternative verification. Or maybe they're only used by auditors. Or
>> in expense reimbursement.
>
> which otherwise would be pretty easy if you're sending in scans of receipts,
> just load up gimp and cut and paste a few digits to adjust the amount.
>
> Regards,

---

From: "Bill Ver Steeg (versteb)" <[email-masked]>
Date: Tue, 9 Aug 2011 14:28:41 -0500

The tax guy's worst nightmare - a bunch of techies in town for a conference trying to reverse engineer his enforcement tools. 

bvs

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Richard Barnes
Sent: Tuesday, August 09, 2011 3:12 PM
To: John R. Levine
Cc: [email-masked]
Subject: Re: [81attendees] What is it at the bottom of restaurant receipts?

FWIW,
--Richard

---

From: "Worley, Dale R (Dale)" <[email-masked]>
Date: Tue, 9 Aug 2011 15:47:37 -0400

________________________________________
From: [email-masked] [[email-masked]] On Behalf Of Richard Barnes [[email-masked]]

But then again, you wouldn't expect that if the hash
were an HMAC instead of just a digest; it would make a lot of sense
for the machine to compute the HMAC with a secret key that the tax
department knows.
_______________________________________________

I believe I read on some explanatory page that the SRM-generated
data was "digitally signed", which would suggest an HMAC generated
with a secret key.

Dale

---

From: Richard Barnes <[email-masked]>
Date: Tue, 9 Aug 2011 15:53:49 -0400

Anyone got one of these machines that we could take apart to try to
get at the key?  Just to verify our findings, of course. <evil grin>

---

From: "Worley, Dale R (Dale)" <[email-masked]>
Date: Fri, 19 Aug 2011 23:48:41 -0400

I went through the math, and it looks like there are 256 symbols in
the set of dingbats.

I did a maximum-likelihood calculation, or rather, a Bayesian analysis
assuming that all alphabet sizes that are powers of 2 are a-priori
equally likely, then looking at a "large" set of dingbats, seeing
the pattern of duplications among them, and computing a-posteriori
probabilities of the alphabet size.  (This assumes that the dingbats
are statistically random.)

I had to reconstruct the formula for "If you have N symbols, and draw
from them randomly n times, allowing duplicates, the resulting
multiset will be a partition of n.  Given that partition, what is the
probability of that partition resulting, as a function of N?"

Throwing away some factors which are independent of N, which don't
affect the Bayes Rule calculation, the resulting probability is a
function only of N, n, and the number of parts in the partition, k:
P = descendingfactorial(N, k)/N**n.

Taking 5 slips that were perfectly readable, there were 60 symbols,
which included 3 triplets, one duplicate, and 49 unique symbols:

60 = 3 + 3 + 3 + 2 + (49)*1

Plugging this into the formula gives:

         n         ln(p)
        64   -61.867
       128   -46.607
       256   -44.610
       512   -46.457
      1024   -49.890
      2048   -54.051
      4096   -58.562
      8192   -63.245
     16384   -68.013

So it looks like there are 256 symbols, and they carry 8 bits of
information each, which isn't surprising.

Checking the Unicode charts, almost all of the symbols are on the page
U+22xx, "Mathematical symbols".  I haven't tracked down the rest, some
of which are seriously obscure, but some seem to be sans-serif Hebrew.
I am guessing that the symbols not in U+22xx are to replace some
symbols on that page that are too much like others.

So the dingbats contain 96 bits.

I still favor the idea that they are some sort of keyed hash of the
data in the barcode, but I can't figure out how it would be used
operationally, since a Revenue Quebec bar-code reader could easily
read a keyed hash and verify the signature.  It has to be compared by
eye with another display in the same format.

And then there's a receipt whose 12 symbols are two repetitions of a
sequence of 6 symbols.  This is so incredibly unlikely that there must
be something wrong with it.

Dale