If the attacker doesn't know the algorithm, then implementing a brute force attack is impossible since the attacker can't compute the output even if he knows the key. Systems like this were the historical norm until very recently.
This is still a reasonable strategy in some situations, especially where there is a limit on the complexity of the encryption hardware (perhaps for cost or power consumption reasons) and/or insufficient key storage mechanism.
Good examples of this situation would be RFID tags which cannot consume very much current nor cost more than the value they protect, perhaps a single trip on a subway.
Nonetheless, such systems are being used less and less in favor of systems constructed from widely studied open algorithms. This has been made possible by advances in semiconductor technology that permit logic gates to cost less and consume less power at the same time.
It's very hard to maintain the secrecy around algorithms:
* The German WW2 Enigma machine was secret only until one was captured by the Allies and its weaknesses were uncovered by clever mathematicians
* The encryption algorithm originally encrypting European GSM cell phone conversations was protected by a non-disclosure agreement (NDA) until a university accidentally disclosed it without getting a signature on an NDA. It was promptly broken and the attack published.
* The encryption algorithm in the Mifare chips was teased out of the logic on the chip by another university team that legitimately purchased devices that implemented the algorithm. They studied the logic under a microscope to find out how it worked.
Better hardware design strategies that include countermeasures for historical and anticipated security attack methodologies can increase the useful life of systems with secret algorithms further into the future.
On Hash Algorithms
Cryptographic hash algorithms are designed to convert or compress a variable length message into a fixed-length string called a digest. If the digest uniquely identifies the message then the digest can be used as a stand-in for the message, shortening the computation time for various operations. While many algorithms can be used for simple hashing functions, a cryptographic hash algorithm has a few important properties:
1. It should be very difficult to find two messages for which the digest is the same. If two such messages do exist, this is said to be a collision.
2. Given a particular digest value, it should be very difficult to create a message that would produce that digest.
3. It should be relatively easy to create the digest from the message.
Digests can be used to verify the integrity of the message by performing some cryptographic operation using both a secret key and the message digest, the output of which can be used for message validation. If the recipient of this validity code has the knowledge of the secret key, he or she can be confident that the message sent along with the code was not modified while in transit.
When used in this way, such a validity code is usually called a message authentication code (MAC). Usually we say that attached to a message is a MAC, which was generated using both the message and a secret key.
The MAC algorithm is considered to be strong if it is very difficult for the attacker to create message/MAC pairs without knowledge of the secret. As well, it should be impossible for the attacker to change the message in a way that the same MAC would match it. Hash algorithms are often used to implement MAC algorithms.
The SHA-1 and MD5 hash algorithms have been widely used for cryptographic purposes. However, recent mathematical analysis has shown that there may be weaknesses in these algorithms. As a result, they have been replaced in the suite of algorithms recommended for use by the US Government with the SHA-2 family. The best known of the algorithms in the SHA-2 family is SHA-256.
The typical attack on hash algorithms is to find a collision ” two messages that hash to the same digest. The reason for this is twofold:
1. If the hash algorithm is being used as part of a message authentication or signature scheme, then the attacker can create one message that the sender authenticates but substitute the other message which the recipient will believe to be authentic. This would have significant benefits for the attacker ” if the attacker could change the shipping address on an order, for instance, he could receive the goods without paying for them.
2. Due to the Birthday Paradox this kind of attack takes far less attempts than is obvious. If the digest has n bits, then only 2n/2 random messages need to be hashed in order to find a collision. This is the same as cutting the number of bits in half!
As a result, cryptographers have put a great deal of effort into finding ways to create two messages that collide. For SHA-1, while the expected strength against attacks would be to require 280 attempts, the current state of the art attacks require only 263 attempts, potentially within range of a brute force attack.
The Birthday Paradox requires that the attacker randomly select pairs of messages. This seems to limit its usefulness, but an example with an email message shows why it's very powerful. We can't see space characters at the end of a line in a simple text email, but there may be a variable number at the end of each line.
If the message is relatively long it's easy to see how a huge number of messages can be generated each of which appears identical but all of which are actually unique. A similar concept can be used with an image attachment ” two images may appear to our eyes to be identical but may in fact be very different at the bit level.
The brute force birthday attack does not work on most authentication devices, however, for a few specific reasons:
1. The usual implementation of the birthday attack is to compute digests of 2n/2 versions of the original message all of which appear to be the same and 2n/2 versions of a beneficially fraudulent message and compare all of the digests in the first set with all the digests in the second set. Since in authentication chips all the bits of the original message are known to the verifier (the message is short and of a fixed format), the first set can't be created which forces the second set to be 2n in length.
2. Incorporating a unique nonce into the message prevents pre-computing digests of a large array of messages that might be compared to those recorded during each of many authentication operations. This is because each 'correct' message contains a shared element (the nonce) that is different from all previous 'correct' messages. Care must be taken to ensure that nonces are not reused, however.
Some attacks to find collisions are made easier by being able to vary the length of the message – the fixed length message property of authentication chips can inhibit these. This property also inhibits “length-extension” attacks, in which an attacker can 'extend' an unknown message with a known value and create the proper digest for the new extended message. Combining a hash algorithm with the HMAC construction also prevents length extension attacks.
Is The Latest and Greatest Algorithm Sufficient?
Attacks on the algorithm itself can be prevented by using the latest and greatest algorithm. But this is not enough.
While authorized systems interact with these security chips according to the datasheets, the attacker has access to a whole range options well outside the normal operating range, up to and including removing the package from around the chip and analyzing the very components within the chip.
Since the purpose of these algorithms is to prevent the security chip from having to reveal its stored secret key in the clear the algorithm must be combined with a whole range of additional protections to ensure that the secret cannot be obtained by means other than a cryptographic attack, including the following:
* Physical protection against attacks. Equipment to probe internal nodes of operating chips is widely available, so authentication chips should include active shields to cover internal nodes, use the latest processing technology to reduce the size of the internal nodes and incorporate multiple layers of internal interconnects, preferably more than 3 layers. All these make microprobing more difficult
* Secure cryptographic protocols. Most algorithms have known weaknesses if used in an improper way so the way in which the chip uses the algorithm must facilitate its secure use. Since an attacker can usually record every bit going back and forth between the chip and an authentic system the protocol must provide anti-replay protection.
* Environmental extremes like fast clock rates or supply voltages that violate the datasheet can often cause a chip to malfunction. In some cases this malfunction can permit the secrets to be read from the chip. State of the art secure designs prevent this from happening by controlling the environment or detecting extremes and shutting the chip down.
* Improper command or IO usage. Many programmers are familiar with stack or memory overflow attacks against some systems which occur when some function is presented with extraordinarily large inputs or passed an illegal value. Well designed security chip are specially constructed to carefully analyze every input and reject all but those which are acceptable.
* Information leakage. Beyond the expected IO channel there are other ways in which information may pass from the chip to the attacker. Perhaps the timing of an operation indicates something about the internal secret.
An attacker can measure the current flow into the chip over time to see if there is an unusually large or small current flow for one condition or the other. Sometimes there may be some sort of electromagnetic emission that can be measured. While no chip can provide perfect protection against every kind of known or unknown leakage, security chip designers are familiar with these attacks and can provide a significant level of protection.
There are broad reputation, safety, liability and profit reasons to incorporate hardware authentication in all new designs. High quality authentication solutions are available to protect a wide range of things from cloning, fraudulent modification, secret disclosure or other types of misuse.
The elements being protected can include software/firmware modules, media files, all medical consumables and medical records, electronic consumables such as batteries and printer toner cartridges, other retail consumables such as filters, wireless or network transmissions, just to name a few.
So long as the device or host device contains some sort of microprocessor or host computer, modern authentication chips can be used to bring a level of security to the design that was never before achievable. The availability of proven cryptographic algorithms simplifies the implementation so the design doesn't have to be a crypto expert.
When selecting an authentication solution for products the designer needs to find the right balance between cost, security, and speed for his/her application. In addition, the designer should consider the lifetime of the product in the market to ensure that the authentication mechanism will still be secure at the end of the useful product life.
For applications that don't require lots of memory storage, different cryptographic protection for different sections of the chip memory and don't require multiple algorithms on the same chip, cryptographic authentication ICs can offer the highest level of security at prices that make them appropriate in most mass markets.
While Moore's law dictates that the counterfeiter will have access to progressively cheaper and faster computations horse power with which to build the clone device or crack the keys, it also means that high security chips with progressively greater security and lower cost are also available to the legitimate OEM. In the case of key size, bigger is always better.
To read Part 1, go to “Is a 256 Bit crypto-key big enough to secure your application?”
Kerry Maletsky is Crypto Products Business Unit Director at www.atmel.com.