Newsportal - Ruhr-Universität Bochum
A car key should open only the one car to which it belongs. In order to ensure that this is the case, cryptographic protocols run on the microprocessor integrated in the key.© Roberto Schirdewahn
Encryption is an integral element of many modern microdevices, for example the implantable defibrillator.© Roberto Schirdewahn
RFID tags are ubiquitous. They are deployed not only in ID cards, but are also used for labelling animals.© Roberto Schirdewahn
In search of economical encoding
A car key is an unremarkable item, and yet it contains complex mathematics: anyone who opens their vehicle remotely using a wireless key fob needs to be sure that it is impossible for criminals to intercept the signal and to replay the command for the car to open the door even without a key; this is why the communication between car and car key is encrypted with mathematical algorithms.
However, a car key is not a high-performance computer: with its cheap chip and its small battery, it is incapable of handling any complicated calculations. Consequently, it is a real stumper for IT experts such as Prof Dr Gregor Leander.
As professor for IT security, he specialises in so-called lightweight cryptography and develops economical encryption algorithms at RUB. They can be deployed in small, cheap sensors and chips with limited computing power and electricity supply – such as window frames, thermostat buttons or car keys. And yet, they are secure.
More often than not, the secure algorithms are complicated, while the simple ones are not secure.
“Finding a secure or a simple encryption algorithm is not a problem,” says the researcher. “But more often than not, the secure algorithms are complicated, while the simple ones are not secure. The challenge is to combine both: security and simplicity.” It sounds self-evident, but it is not: “In the industry, substandard algorithms are often deployed,” deplores Gregor Leander. He and his colleagues are striving to redress this problem.
Altering the message
Cryptography is all about altering a message in such a manner that the result is incomprehensible for outsiders, while insiders are able to translate it back. A computer represents each message as a sequence of the digits zero and one, the so-called bits. Cryptography aims at reconstructing a given sequence of zeros and ones following a specific algorithm.
The algorithm contains an encryption policy, namely a general guideline that is commonly known. It also incorporates a secret key, a specific addition to the policy which is different in each individual case and should not be disclosed. A clever combination of policy and key renders an encoding algorithm good and secure.
Block ciphers for encryption
Gregor Leander studies so-called symmetric encryption algorithms, where both the sender and the recipient have the key necessary for coding and decoding the message. “In practice, almost all data are encrypted using symmetric algorithms, because they are very fast,” says the IT scientist. “Other algorithms are only used for exchanging the key between the sender and the recipient.
As far as symmetric encryption algorithms are concerned, Gregor Leander focuses on so-called block ciphers, where the message is split and the encryption is performed in blocks. Each block has a predefined length. Encryptions based on such blocks are often carried out in several steps: one block consisting of the digits zero and one is altered several times in a row, following a specific policy and with the aid of the key.
This is easy to programme.
“This is easy to programme,” explains Leander. “Moreover, an algorithm performed in accordance with this pattern helps us identify the reason why it works – i.e. the reason why it is secure.”
As the encryption policy is commonly known, the attackers’ goal is to find out the key. In theory, this is only possible through tedious trial-and-error. This is because, as far as the computer is concerned, the code, too, has a predefined length and is likewise nothing but a sequence of the digits zero and one.
Deciphering by trial and erorr
If an attacker knows what the clear text is and how it was altered by the encryption algorithm, he has to prefix the encoding policy by every possible key, i.e. each possible sequence of zeros and ones of the same length as the key – until he identifies the key that changes the known clear text into the known secret text.
In order to prevent attackers from doing precisely that, the keys that are chosen in practice are so long that it would take an unimaginable period of time to find them by trying out all possible sequences of bits. However, a cipher can be cracked not only by trial-and-error, but also by skilful analysis. Here, attackers search for shortcuts, as it were, i.e. mathematical simplifications that enable them to find the secret cipher without testing all possibilities.
An example for such a mathematical shortcut is the so-called linear cryptanalysis. Attackers try to approximate the encryption algorithm through a linear, i.e. extremely simple, function.
The challenge we face is to invent algorithms that are difficult to break.
In addition to developing novel encryption algorithms, Gregor Leander’s research also aims at getting a better grasp of the factors that render symmetric encryption algorithms secure: “The challenge we face is to invent algorithms that are difficult to break,” says the researcher.
Gregor Leander and his colleagues have, for example, developed the encryption algorithm “Present”, which has been approved by the International Organization for Standardization, short ISO. The message that has to be encrypted is split into blocks with a length of 64 bits each, i.e. a sequence of 64 ones and zeros. Those 64 bits, in turn, are regarded in segments of four bits each.
In the first step, the four zeros and ones in each segment are changed following a specific formula. Subsequently, all 64 bits are shuffled. Then, the next stage begins, where the bits are again changed in blocks of four and then shuffled in the entire 64-bit block, and so on. It may sound easy, but the alteration to the blocks of four as well as the shuffling of the 64-bit blocks must meet specific requirements in order to render the algorithm secure.
Achieving maximal distortion in the message
Linear alterations should be avoided: that means they must not be too simple. Moreover, the shuffling has to be as random as possible to ensure that digits at the front swap places with digits at the end, rather than just digits that are next to each other. The aim is to achieve maximal distortion of a message after performing this simple operation several times in a row.
Gregor Leander works hand in hand with researchers and experts at the engineering departments. He considers such interdisciplinary collaboration extremely important. This is because in order to provide relevant mathematical solutions for affordable and energy-efficient applications, he has to understand what affordability and energy-efficiency mean in terms of hardware. Eventually, his algorithms may be deployed in numerous practical applications.
Efficient cryptography for small devices
Economical cryptography is not only used in car keys, but also in pacemakers: the latter can be remotely controlled, and here, too, communication has to be secure. Just like the car key, the pacemaker doesn’t have a powerful computer for encryption, and it only has a small battery.
In practice, unsecure algorithms are often used.
“Dick Cheney, the former Vice President of the USA, had allegedly the remote control function of his pacemaker deactivated for fear of an attack,” says Gregor Leander. The IT researcher himself is much more relaxed about these matters, even though he realises that there is a lot of catching on to do: “In practice, unsecure algorithms are often used.”
Lightweight cryptography is a crucial challenge in industry 4.0, where intelligent and interconnected systems are required for production and logistics. Radio frequency identification (RFIDs), for example, are used not just as anti-theft devices, but also for tracking packages and for labelling livestock and wildlife. They are integrated in passports and IDs, as well as in contactless public transport chipcards. The encryption algorithms developed by Gregor Leander may be utilised for all these purposes.
23 May 2016