Understanding the benefits and pitfalls of modern cryptography

First it was finance. Money has gone from being represented by precious metals to promissory notes to numbers stored in a database. Each step demanded an improvement in methods to stop forgery. For today's electronic funds, the key technology is cryptography. Being able to transfer those funds raised an important problem: how to transmit securely the keys needed to decrypt the information contained in those transfers. The keys would have to pass across untrusted networks – making it relatively easy for an eavesdropper to pick up supposedly secret keys needed to decrypt the data. In 1976, Whit?eld Diffie and Martin Hellman proposed and demonstrated a technique that, effectively, made such secure communications possible and which now underpin transactions on the internet. They developed the idea of public keys – keys that can be sent in the open to allow two parties to talk securely without risk of eavesdropping. Symmetric, or private key, encryption remains in widespread use as it is, for keyholders, often more computationally efficient than public key systems. And the rise of public key systems has not stopped the development of new private key systems. For example, the Advanced Encryption Standard (AES) was developed to provide a higher level of security than the Data Encryption Standard (DES) used by the US government. However, public key systems are often used to transmit private keys between users so they can initiate communications using a private key system. Public key cryptography is not just useful for communications, it can be used to sign documents and even software to confirm that the contents had not been tampered with. This is an aspect of cryptography that is now becoming increasingly important to manufacturers of embedded systems faced with the problems of having their hardware cloned, copied or hacked. Concern over design security, so far, has largely been concentrated within a few markets, such as digital tv. Set top box decoders are designed so they can only show tv programmes for which the user has the right credentials – stored on a smartcard or a similar ic embedded in the unit. Hardware can also be designed to stop counterfeit products from being used inside a computer – although today this is more commonly used to prevent consumers from using third party ink cartridges in their printers. The rise of the Smart Grid provides another angle of attack for fraudsters as internet connected utility equipment will make it possible for homes to record energy generation – and thus qualify for refunds from their energy suppliers – as well as consumption. Utilities will need to use public key encryption to both qualify remote meters and securely transmit the usage data. Effective public key cryptography relies on the ability to generate a key that can be made public from a secret private key in such a way that doing the inverse – calculating the private key from the public version – is computationally incredibly time consuming. Although many techniques have been proposed as potential starting points for public key cryptography, just two problems underpin public key cryptography in use today. One is integer factorisation used in the system developed by Ronald Rivest, Adi Shamir and Leonard Adleman who went on to form RSA Security. This system is potentially vulnerable to quantum computing (New Electronics, 13 December 2011) but remains hard to crack with conventional hardware, even using racks of fpgas configured purely for the task. The other mathematical problem used in cryptography is that of discrete logarithms – an approach used in a number of proposed encryption systems from the Diffie-Hellman system to AES. It underpins elliptic curve cryptography – a technique now being adopted by government agencies after many years of research and checks for potential weaknesses. RSA is conceptually simple, but tough to crack, although its implementation does depend on an understanding of a number of mathematical theorems. The other systems require an understanding of their operation that are tougher for non mathematicians to deal with. However, there are commonalities between both popular branches of digital cryptography. Conventional number systems have infinite fields: there is no limit to the number of real or rational numbers in nature. Modern cryptographic systems use limited or finite fields. One useful form technique is the Galois field used in AES. In this type of field, for any prime integer p and any normal integer n, there is a field with p^n elements in it. A number of steps in AES use a 2^8 Galois field, where only 256 values are allowed – all mathematical operations that can be performed on the field result in one of these values. Cryptographically useful fields are also cyclic – the mathematical operations use modulo arithmetic and are sometimes redefined to preserve aspects of regular mathematics such as commutativity. This is not necessary in RSA, as it is based on conventional number theory. However, things are quite different in a Galois field. Both addition and subtraction are performed using the same exclusive-OR (XOR) operation – the two operations are equivalent in this type of field. Multiplication is somewhat more complicated, involving a series of shifts and XOR. As with regular arithmetic, exponentiation involves repeated multiplications. To be able to send out public keys, the number system needs to have some predictable behaviour. In the case of RSA, the key lies in the mathematics of prime numbers. A number will break down into prime factors in only one way. So, any number is defined and reconstructed by its prime factors. RSA uses another property: the concept of relatively prime, or coprime, numbers. These are numbers that have no common factor other than 1. For example, 3 and 7 are coprime. If you have two coprime numbers and multiply them together, it is straightforward to calculate Euler's totient function of that number – the number of primes smaller than this value – simply by subtracting one from both of the primes and multiplying them together. These relationships make it possible for two systems at either end of a connection to generate two keys – which are again prime numbers – as well as the modulus that the encrypting system will use. Data is encrypted using the public key by raising each piece of data in the stream to its power and then performing a modulo operation on it. Thanks to the known properties of the primes, the private key generated at the other end has a relationship to the public key such that performing the same operation, but using instead this private key, reveals the source data. The modulo arithmetic makes it much tougher for an attacker to derive the private key from the public key because there are a large number of possible private key values that could have been used. The key is to find them. Such modulo processing is often termed clockface arithmetic: you don't know how many times around the clock a number has gone without access to the private key. The smaller the key, the easier the factoring process becomes. But RSA uses very large key values: 1024bit are at the low end and 15360bit keys are used in some systems. Such long keys also mean you can encrypt more bytes of data at once, which improves their security. And theorems such as Fermat's Little Theorem make it far easier to work out whether a large number is prime than it is to factor a number produced by two large primes. A similar mixture of predictability and intractability is used in the discrete logarithm systems. The key in the Galois field is the generator: these are values in the field that can be used to create all the field's other possible values through exponentiation. In the AES field, exponentiating a value 255 times will recreate the original value and the cycle can start again. A corresponding logarithm chart can be created to show how many times a given number needs to be exponentiated to reach another value within the Galois field. The trick for the attacker is to determine how many times around the clock the message has been, which demands that you have access to the discrete logarithm. However, the public key represents only the exponent used. When it comes to implementation, there are obvious mismatches between general purpose computer architectures and encryption algorithms. Exponentiating by a 1024bit value potentially takes up a lot of space and cycles, even when implemented on a 32bit processor with a hardware multiplier. And performance is not helped by the final modulo reduction: equivalent to very long division. Yet these types of operation are commonly performed on low end 8bit processors sitting inside smartcards. Peter Montgomery of Software Development Corporation came up with the basis for one of the most widely used shortcuts in use today. Like the RSA algorithm itself, the Montgomery reduction takes advantage of the numerical properties of coprimes to simplify the arithmetic. The algorithm picks a modulus that is coprime to the processor's native wordlength – this greatly simplifies the operations, turning multiplications into a series of adds and squaring operation, which become just simple shifts on binary computers. Exponentiation takes more work as it involves repeating these steps many times, but the individual steps themselves are simple and can take advantage of circuits such as carry-save adders to improve the performance of pipelined implementations. The final conversion to the correct modulus takes a few additions, multiplications and simple integer divides. The basic Montgomery reduction is highly vulnerable to side channel attacks (New Electronics, 28 June 2011) that can reveal the key simply by observing electrical activity. The key can be recovered by monitoring the difference in power consumptions of the sequences of adds and shifts. Protecting against this demands that extra circuitry be used to cover up this activity or the hardware processes random values at frequent intervals to upset the attacker's analysis. An alternative used for decryption in embedded systems is the Chinese remainder theorem, which splits the key into two prime factors that are used to produce a pair of exponents and a conversion coefficient. As the split exponents are much smaller, the modular exponentiation for each is quicker. So, the algorithm is converted into a larger number of quick and, important for smartcards at least, less memory intensive operations. The Chinese remainder theorem has its own weakness to side channel attacks. In this case, fault injection can be used to expose one of the prime factors used to generate the private key needed for decryption. The attack was demonstrated in 2001. Although the acceleration techniques developed for RSA work well enough on standard processors, smartcards use dedicated accelerators to speed up operation through the many steps. They also tend to include additional hardware, such as address scramblers, to make it harder for an attacker to simply probe memory addresses in the search for keys and important intermediate values. The discrete logarithm algorithms make life harder for the software writer because, if they are implemented on general purpose hardware, they require a lot of conditional statements to test whether bits are positive or not. Because of the large number of possible branches and differences in execution time, naïve implementations in software are vulnerable to timing oriented side-channel attacks. However, it is relatively straightforward to precompute tables and then use repeated access to those to encrypt and decrypt data at high speed. Table lookups can be used to reduce the risk of exposing data through attacks that try to work out if the crypto algorithm takes varying amounts of time to process different values. However, these operations are extremely cheap to put into custom hardware that can perform the necessary bit tests as part of the pipeline. A number of digital signal processors support Galois arithmetic because the same mechanisms are used in Reed-Solomon error correcting decoders – common in communications hardware and disk drives. The more advanced elliptic curve algorithms introduce demand for other hardware optimisations. For example, shorter keys put less emphasis on exponentiation but demand higher throughput for functions such as modular inversion that are relatively straightforward but expensive to implement in software. The lack of standardisation on elliptic curve cryptography makes it difficult for silicon vendors to bake hardware support into their processors. So it's no surprise that the fpga has become the favoured platform for advanced cryptography based on finite fields and elliptic curves as they readily allow new 'instructions' to be downloaded and executed much more quickly than if implemented as software libraries on even a high end dsp. However, this has focused attention on the security of the fpga itself in terms of how the algorithms are themselves protected from eavesdropping on the programming stream used – in the case of sram based parts – to load the logic configuration and from power related sidechannel attacks. Because glitching is a large source of lost energy in fpgas – and glitching is very much circuit dependent – designers need to take more care at hiding the energy differences between high and low computational cost operations to avoid giving away details of algorithms and keys. Cryptography remains a game of cat and mouse between developers and an army of people committed to breaking the codes: whether through the use of abstract mathematics to probe weak points in an algorithm or taking advantage of leaky electronic circuit to find a far more useful shortcut to someone else's secrets.