Cryptographic PostageIndiciaJ. D. Tygar and Bennet Yee and Nevin HeintzeJanuary 1996CMU-CS-96-113School of Computer ScienceCarnegie Mellon UniversityPittsburgh, PA 15213This research was partially supported by the US Postal Service.The views and conclusions contained in this document are those of the authors and should not be interpreted asrepresenting the official policies, either expressed or implied, of the U.S. Government.Carnegie Mellon University Computer Science technical reports CMU-CS-96-113Keywords: cryptography, franking, electronic currency, mail, postage, stamps, electronicstamps, secure coprocessors, signaturesAbstractWe apply cryptographic techniques to the problem of fraud in metered mail. We describe a mailsystem that combines off-the-shelf barcode technology, tamper-proof devices, and cryptography ina fully-integrated secure franking system. This system provides protection against:1. Tampering with postage meters to fraudulently obtain extra postage;2. Forging and copying of stamps;3. Unauthorized use of postage meters; and4. Stolen postage meters.We provide detailed justificationfor our design, and discuss important tradeoffs involving scanningstrategies, encryption technology and 2-D barcode technology. The US Postal Service’ recentInformationBasedIndiciaProgram(IBIP)[15]announcement adopted the principaldesignfeaturesof our model.1 MotivationThe US Postal Service1handles over 165 billion pieces of mail each year through almost 40,000autonomous post office facilities. Much of this mail is metered, which means that the mail doesnot have an ordinary stamp attached to it. Instead, a postage meter prints a special mark (called apostal indicia) on the mail. Fraud is a serious problem for the US Postal Service:The US Postal Service recently calculated that meter fraud cheats the agency out of substan-tially more than $100 million each year [4].There are over 82,000 postage meters in the US that are currently reported as lost or stolen[14].The US Postal Service is prosecuting two cases in New York and Boston; each involvesmore than $4 million dollars in postage meter fraud [10].To address these problems, we propose a new system for printing postage indicia with crypto-graphicinformation. This system allowsa PCorworkstation withalaser printeranda tamper-proofdevice to produce unforgeable postage indicia. This paper describes that design.The design of cryptographic postage indicia is an interesting exercise in security engineering.The US Postal Service’s recent InformationBased Indicia Program (IBIP) [15] adopts the principaldesign features of our model.2 Postal FraudToday’s postage meters and indicia are not very secure. They are vulnerable to at least four kindsof fraud:The postage meter may be tampered with so that it generates free postage;The indicia imprint produced by a postage meter may be forged or copied, using a rubberstamp, a color photocopier, or a color laser printer.A valid postage meter may be used by an unauthorized person; andA postage meter may be stolen.A number of these issues can be addressed by cryptography. Thanks to recent developmentsin digital barcoding, we can now use off-the-shelf technology to replace old-fashioned stamps bymachine readable indicia. These indicia can be printed by laser printers or similar devices, underthe control of a workstation, a PC, or a dedicated postage device. Moreover, we can includecryptographically signed information in the indicia to prove the authenticity of the indicia. Byincluding information such as the mailing date and the zip code of the sender and receiver, we canalso guard against forged or copied indicia. Pastor [7] gave a rough outline of how such a systemcould work.1This paper addresses mail in the United States, but the basic design can be generalized to mail in other countries.Unfortunately, Pastor’s system and similar proprietary proposals are vulnerable to additionaltypes of attack:Cryptographic techniques are vulnerable to misuse, leading to systems that can be success-fully attacked by an adversary.Postage meter credit may still be tampered with, even if cryptographic techniques are used.A postage meter may be opened and examined by adversaries looking for cryptographickeys, thus allowing the adversary to build new bogus postage meters.Even more problematic, Pastor’s proposal relies on an implicit assumption that a master listcontaining all examined indicia is maintained. This would require a large, distributed database ona highly available network connecting post office facilities. With nearly 40,000 postal facilitiesand a yearly volume of 165 billion pieces of mail, such an integrated, real-time, distributed,highly-available database would be unrealistic at present without dramatically increasing the costof postage.This paper describes a complete postal franking system addressing these concerns. This systemis most suitable for a PC or workstation printing out cryptographic indicia on a standard laserprinter. A slightly less secure design also allows postal meters to print out cryptographic indicia.Central to our design is the use of tamper-proof computing devices, such as those in the specifiedin the US FIPS 140-1 standard [13]. Using this technology, we can produce secure, unforgeablepostal indicia.3 Traditional IndiciaHere we review the structure of traditionalindicia and define necessary properties forcryptographicindicia.Today’s postage meters are portable devices containing a print mechanism and a postageaccounting mechanism, enclosed in a sealed case. Each postage meter is initialized with a postagecredit by a post office; as each letter is stamped, the postage value is deducted from the machine’scredit. Meters are periodically returned to the post office so that additional postage credit may betransferred to them. Although postage meter cases are not tamper-resistant or tamper-proof, theyare supposed to be tamper-evident. Meters are subject to periodic inspection by postal authorities.Unfortunately, the tamper-evident mechanisms frequently fail. Further problems are created bystolen or missing meters, which cannot be inspected but may be in use. Finally, postal employeesoften fail to recognize signs of tampering.Traditional postage meters maintain three important registers:ascending register The monetary total value of all indicia ever produced by this meter.descending register The remaining credit available in the meter.piece-count