Dog race tracks often employ Automatic Betting Machines (ABMs),18 which are some
ID: 3822847 • Letter: D
Question
Dog race tracks often employ Automatic Betting Machines (ABMs),18
which are somewhat analogous to ATM machines. An ABM is a terminal
where Alice can place her own bets and scan her winning tickets.
An ABM does not accept or dispense cash. Instead, an ABM only accepts
and dispenses vouchers. A voucher can also be purchased from a
special voucher machine for cash, but a voucher can only be redeemed
for cash by a human teller.
A voucher includes 15 hexadecimal digits, which can be read by a human
or scanned by a machine—the machine reads a bar code on the
voucher. When a voucher is redeemed, the information is recorded in a
voucher database and a paper receipt is printed. For security reasons,
the (human) teller must submit the paper receipt which serves as the
physical record that the voucher was cashed.
A voucher is valid for one year from its date of issue. However, the
older that a voucher is, the more likely that it has been lost and will
never be redeemed. Since vouchers are printed on cheap paper, they
are often damaged to the point where they fail to scan, and they can
even be difficult for human tellers to process manually.
A list of all outstanding vouchers is kept in a database. Any human
teller can read the first 10 hex digits from this database for any outstanding
voucher. But, for security reasons, the last five hex digits are
not available to tellers.
If Ted, a teller, is asked to cash a valid voucher that doesn't scan, he
must manually enter its hex digits. Using the database, it's generally
easy for Ted to match the first 10 hex digits. However, the last five hex
digits must be determined from the voucher itself. Determining these
last five hex digits can be difficult, particularly if the voucher is in poor
condition.
To help overworked tellers, Carl, a clever programmer, added a wildcard
feature to the manual voucher entry program. Using this feature, Ted
(or any other teller) can enter any of the last five hex digits that are
readable and "*" for any unreadable digits. Carl's program will then
inform Ted whether an outstanding voucher exists that matches in the
digits that were entered, ignoring any position with a "*." Note that
this program does not give Ted the missing digits, but instead, it simply
returns a yes or no answer.
Suppose that Ted is given a voucher for which none of the last five hex
digits can be read.
a) Without the wildcard feature, how many guesses must Ted make,
on average, to recover the last five hex digits of this particular
voucher?
b) Using the wildcard feature, how many guesses, on average, must
Ted make to recover the last 5 hex digits of this voucher?
c) How could Dave, a dishonest teller, exploit the wildcard feature to
cheat the system?
d) What is the risk for Dave? That is, how might Dave get caught
under the current system?
e) Modify the current system so that it allows tellers to securely and
efficiently deal with vouchers that fail to scan automatically, but
also makes it impossible (or at least more difficult) for Dave to
cheat the system.
Explanation / Answer
a)Without the wildcard feature,
Each of the 5 places can have 16 possible values (from 0 to E). So there are total 16^5 = 1048576 combinations.
If we assume, all combinations are equally likely, then average number of guesses =
= 1048576 / 2
= 524288
This means that if we guess 524288 times, then it is likely that we guess the right combination.
b)With the wildcard feature,
Teller can guess the 11th digit by sending input as 11th digit * * * *. This means that he can send * for remaining 4 places and try to obtain all valid digits for 11th place. Once he got that he can choose any one of the valid digit and repeat same process for 12th,13th,14th and 15th digit.
For each digit, he has to guess 26 times. So total number of guesses = 26*5=130
If we assume, all guesses are equally likely, then average number of guesses =
= 130 / 2
= 65
c) Dave can cheat the system as following -
1.He reads any 10 digits from database (Assuming he shows the unreadable couple).
2.For remaining 5 digits, he can guess one by one. With wildcard feature program, Dave first send input as - guessed digit * * * * as 11 to 15th digits. Carl’s program will return yes or no. Dave stops guessing for 11th digits as soon as he gets yes reply from Carl’s program.
3.Now Dave sends input as 11th digit, guessed 11th digit, * * * to Carl’s program. This way he has to guess 26 times for each digit (worst case).
4.So in worst case, he needs to guess 26*5=130 times. On average, he needs to guess = 130/2 = 65 times.
5.So using carl’s program for around 65 times, Dave is able to cheat the system.
d)The current can detect such fraud by monitoring the usage of Carl’s program for a teller. The system can set some threshold, say 40 times, then the tellers which uses Carl’s program for more than 40 times should be enquired for authentication. (can ask for more details, when and how he purchased the tickets etc)
e) The current system can be improved to prevent (make almost impossible) such cheating cases, by adding following mechanism :
1.In ATMs machine, while dispensing the voucher, the voucher code, current timestamp and hash of user id can be kept in database. So for all vouchers dispensed, we have details of code, current timestamp and hash of user id in database.
2.Whenever teller redeems his voucher by scanning, then we delete the entry associated with the voucher from database.
3.If the voucher is not readable, then before displaying first 10 digits to teller, we first ask him, his user id, computes it’s hash and check the hash against hashes stored in databases. If there is no match, then this teller never been issued a voucher.
4.If there is match for hash, then allow the teller to select 10 digits and then allow using Carl’s program for last 5 digits. But before issuing him the money, the system should ask him the time when he got the voucher. The timestamp is checked against stored timestamp in database for this voucher. If there is mismatch, the teller is cheater.
Step 4 is necessary, because there may a case that the user is member, but never got any voucher and trying to cheat.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.