Development of products using the latest technology costs a lot of money. The greater the development cost, the greater the temptation to clone the product. Counterfeit goods comprise between 1% and 5% of worldwide trade, and it is growing at an alarming rate.
Since the cloner doesn't have a reputation to protect, quality and performance often suffer. The cloner can make a greater profit and offer the product at a lower cost by bypassing the development process and cutting corners on product safety and reliability. The result can be annoying if an ink cartridge fails. It can be expensive if a counterfeit battery damages the end-product. It can be life-threatening if a medical consumable is below standard..
Another issue is microprocessor firmware. Hackers are constantly figuring out ways to defeat product features intended to product the end-user from unauthorized firmware downloads.
While opening up a mobile phone to additional service providers may seem attractive, it puts the phone at risk of getting malware that could compromise the end-users personal information or damage the phone itself.
The harm done to the end-user by counterfeit products or software can damage the reputation of the OEM, increasing product liability, maintenance and warranty costs, and decreased sales in the future..
How To Authenticate Something
OEMs have always tried to protect their products and guarantee their authenticity in a variety of ways. There are many procedures that are in common use to authenticate items:
By Source: If we trust the seller and we believe in the reputation of the shipper, then we might use this as a method of authentication. It is easy to see potential issues:
* Truly secure shipping, such as an armored truck, with 100% control over the item at every instant of the process, is quite expensive and rarely used. While uncommon, various kinds of substitutions can take place without even the shipper knowing.
* Even a reputable seller may not have complete control over their own supply chain ” they may have been tricked in some way to offer counterfeit products under their own good name.
* We assume that some sellers, such as a sidewalk vendor selling $100 baseball jersey for $15, sell counterfeit goods. Yet the street vendor hasn't manufactured the items – what other sales channels is the counterfeit manufacturer using?
Physical Attributes: For items that have a unique physical shape, such as computer batteries, printer toner cartridges or even vacuum cleaner bags, we often just assume that if the label 'looks' authentic, carries the right logos and the product 'works', that it is authentic.
* It's hard to disbelieve our eyes ” if the computer works, the printer prints or the vacuum cleaner cleans ” that often serves to convince us, even though we know that cloned versions are available and printing counterfeit labels is cheap.
* We may not ever find out the truth ” how many people actually count the number of pages their replacement toner cartridge actually printed, or can tell what size particles are being passed right through that vacuum cleaner bag?
By Holograms: This is common for clothing and many other retail items. The tags look good and appear to be hard to reproduce using equipment we are familiar with. But enter “hologram printing” on any search engine and you can find many companies willing to print these for you.
* A related confidence builder is a metalized label with a serial number embossed in it. But these are no more difficult to duplicate than a hologram.
By Passwords : We are familiar with these to log into our computers or access accounts/information on a web site. But they are also often used internally in a controller-based system to validate a separate chip, board, consumable or network device. Or they may be used to control 'special' access to the system for configuration, maintenance, etc. Shared secret encryption keys are a close cousin of passwords, with the same advantages and disadvantages:
* There is usually no place to safely store the expected password on the receiving system, so if an attacker has access to that system he/she can extract that value from the EEPROM, FLASH or other nonvolatile chip.
* Usually, it's easy for an attacker to find a way to 'watch' the system when it's in use and discover the password as it is being passed from one system element or another. Or the attacker might record the entire session and just replay it at a later date to repeat the benefit the first user obtained.
* A somewhat more complex version of this kind of security is to include a public key signature of the serial number in a consumable. The host device can validate the signature without having to store any secrets. But since both the serial number and signature are typically stored in an unsecure device, they can easily be read and copied into the clone device.
By Smart Card: Some satellite, cable or other media providers use a smart card to authenticate a user to the network. The user plugs the card into the set top box in order to make the media available. These are often very secure but they are not perfect for all applications:
* They may be physically impractical if the device is too small, is used in a wet or dirty environment or if the end use (many consumer items) mandates no parts to lose.
* Smart cards can cost $5 per unit, way too much for an end-product priced under $100.
* The total system cost is even higher since a physical reader slot and connector has to be supplied, in addition to the cost of the electronics to support the ISO 7816 interface and the cost of the card itself.Low-cost, Crypto Authentication to the Rescue
Hardware authentication devices have been available for some time, but only recently have they been able to combine proven & robust cryptography with low cost and ease of use in the typical microprocessor-based application.
Virtually all security devices contain some sort of secret along with a cryptographic processing element. Generally, the secret can never be read from the chip, rather the secret is combined with input data using a protocol that proves the knowledge of the secret without revealing it.
Cryptographic chips with wired or wireless interfaces are available with increasingly impressive capabilities that can make the counterfeiter's task very difficult indeed.
Wired devices may be soldered down on a board with other system components, or may be attached to a consumable and connected to the system via contacts. Wireless RFID chips don't require contacts and are optimal when the environment is challenging.
Usually, these authentication chips incorporate a serial number and offer several advantages over any other kind of serial number storage:
* The number can be changed, since it is programmed into the silicon by the chip manufacturer.
* The serial number can be cryptographically connected to secret keys on the chip which cannot be read or copied. The attacker needs both the serial number and the secret key to build a counterfeit device.
* The chip can provide a way to combine a dynamic, random challenge from the host with the serial number ” a much better solution than the static signature mechanism discussed above which is susceptible to copying.
Cryptographic authentication ICs incorporate security features developed for more complex cryptographic memory and RF security chips, but at a much lower cost than other authentication chips.
These chips use the SHA-256 hash algorithm to avoid any known algorithm weaknesses. In addition, they incorporate a full active metal shield over the entire internal circuitry ” if an attacker cuts or shorts any wire in the shield, the chip stops functioning. Added to this are internal clock and voltage generation, fully encrypted memories, tamper detection and fully secure production test methods.
Modern processing technology allows the chips in this family to be incorporated in a SOT23 package which is less than 2mm x 3mm ” tiny enough to be incorporated in the most space constrained portable systems, incorporated inside battery packs or fit on existing PC boards without even increasing their size.
These chips can have a 48 bit serial number which is guaranteed to be unique, along with the appropriate cryptographic protocol to validate that the number is not a simple copy on a counterfeit product.
A single wire interface simplifies the mechanical connection to the device while reducing the number of GPIO or UART resources required on the host microcontroller. An automatic sleep mode reduces the standby current to less than 100nA when the crypto operations are completed. And the straightforward challenge-response mechanism of these devices, along with the use of an algorithm that is widely supported by commercial and open source software libraries simplifies the programming requirements. Figure4-CryptoAuthSetup
Two important characteristics of every cryptographic chip are the size of the key and the strength of the algorithm. It's pretty easy to imagine that bigger keys are better ” but just how big is big?
And while it's tempting to think that the newest secret algorithm is the best, “security through obscurity” is generally considered to be very risky. Crypto experts much prefer algorithms that are well publicized and have been analyzed by lots of smart people over years. The following sections discuss these concepts in more detail.
Is a 256 bit key big enough?
As computational ability rapidly increases, more concern is being placed on the key size in cryptographic devices. Individuals commonly have a quad processor 4GHz computer on their desks, so trying billions of possibilities to crack a secret key is pretty easy.
These attacks are usually called “offline” attacks since the attacker doesn't use the host or client system to try each possibility. Instead he uses external computers to mimic the computation of the authentication chip to guess the stored secret, trying to generate a sequence of bits which matches that which was recorded once on the authentic system.
In the simplest example, a “brute force” attack, the attacker gets a complete or partial clear text message and the corresponding version of the message encrypted with the key he wants to crack. He then successively tries each possible key until he finds the one that creates the correct encrypted message.
If there are n bits in the key, then after 2n-1 attempts the attacker has a 50% chance of finding the right key and after 2n attempts he has tried all possible keys and is guaranteed to have found the key.
The only protection against such a brute force attack is to choose an algorithm that uses a key so big that it will simply take too long to try a very large percentage of the possibilities. Keys that were big enough 10 years ago are not be big enough any more because of the exponential growth in computing power. Here are some well publicized successful brute force exploits:
An array of 64 Virtex-5 FPGAs from Xilinx can successfully find a 48-bit key in less than an hour. (See www.usenix.org The Mifare cryptographic memory chip used widely around to protect electronic purse contents uses 48-bit keys.
The official encryption standard adopted by the United States in 1976, Data Encryption Standard (DES) uses a larger 56-bit key. Several machines have been built that can find a key through brute force in less than a week.
Although no successful brute force attacks have been reported for commercial chips using algorithms with key sizes greater than 56 bits, it is expected that algorithms with larger key sizes will eventually become vulnerable with increasing computational ability. As of the writing of this article, the US Government is recommending Advanced Encryption Standard (AES) with a 128 bit key for government encryption purposes.
Setting aside any mathematical weaknesses in AES (if they exist), this means that the government believes that attacks against a key space this large will be impractical for some years to come. However, with computing power doubling every 18 months or two years, 128-bit keys will eventually become “crackable” using brute force attacks.
As a result some system designers look for even larger keys to ensure that a system they design today will still be secure during its entire life ” even after much larger and faster computers are available to hackers. A key size of 256 bits is so big that all cryptographers agree it is immune from exhaustive attacks. Just how big is 2256?
Here are some estimates of big numbers:
220 Number of grains of sand on the earth
222 Number of stars in the universe
279 Avogadro's number. The number of carbon atoms in 12 grams of coal.
296 Number of atoms in a cubic meter of water
2190 Number of atoms in the sun
2255 Number of attempts to find the key in this chip
But what about very well funded entities such as the US National Security Agency (NSA)? Could they build a machine to crack a 256 bit key? Assume they could build a theoretical nanocomputer that executes 1013 instructions per second (approximate rate of atomic vibrations) in a space of a cube with a side that is 5.43nm across (This is the approximate size of a silicon lattice10 atoms wide, or a crystal containing 1000 silicon atoms).
Assume that it could calculate an attempt in 10 cycles. Such a computer the size of the earth would take more than 1013 years (roughly 58 times the estimated age of the earth) to attack a 256 bit algorithm via brute force.
Is a 256 Bit Key TOO Big?
There are a few downsides to larger keys ” they increase the complexity of low cost authentication chips in a number of ways:
More internal memory storage to retain keys and temporary values. Usually the largest blocks on most such chips are the memory arrays. Doubling the size of the keys typically doubles the total amount of nonvolatile and volatile data memory which could therefore increase the chip cost. However as the line widths in chips shrink, the core size of the memory cells becomes a smaller and smaller percentage of the total chip area reducing this cost penalty proportionally.
More logic gates and hence larger, more costly chips. It's generally reasonable to assume that doubling the size of the key will double the size of the logic to implement the block. Alternatively the same logic size could be used at a penalty of perhaps 2-4x the computation time, depending on the algorithms in question. Implementing the chip in a newer technology with smaller transistors can offset this disadvantage.
More transmission time. Typically both the challenge and the response are the same size as the key (if not, then the shortest of the three can be attacked more easily than the other). So doubling the key size will double the transmission time for the transaction. But since authentication is done infrequently (perhaps on power up only), this penalty matters less in the overall scheme.
Cryptographic professionals (and hackers) are a creative bunch. Even though the time scales in the previous section seem daunting, new attack procedures could be found that might simplify the task by a factor of 2, or 2,000 or 2,000,000. Increasing the search space with a larger key helps to ensure that even with these advances, it will remain extraordinarily difficult to guess a 256 bit key anytime soon.
Next in Part 2: Why not just keep the hash algorithm secret?
Kerry Maletsky is Crypto Products Business Unit Director at www.atmel.com.