LW cryptography: ciphers for RFID systems
One of the fastest growing trends in computerized small devices is RFID systems. RFID is an automatic object identification method in which data stored in so-called RFID tags are read or written via radio signals.
Any RFID system consists of a reader and an RFID tag (sometimes the term RFID tag is also used).
Most RFID tags consist of two parts: an integrated circuit for storing and processing information and an antenna for receiving and transmitting a signal.
By type of power source, RFID tags are divided into the following categories:
')
• passive
• active
• semi-passive
Passive RFID tags do not have an embedded power source. The electric current induced in the antenna by the electromagnetic signal from the reader provides sufficient power for the functioning of the silicon chip placed in the label and the transmission of the response signal.
Active RFID tags have their own power source and do not depend on the reader’s energy, as a result, they are readable in the far distance, are large and can be equipped with additional electronics. However, such tags are most expensive, and battery life is limited.
Semi-passive RFID tags, also called semi-active, are very similar to passive tags, but are equipped with a battery that provides power to the chip.
Currently, RFID technologies are used in a wide variety of fields: from agriculture to transport.
According to the general director of the state-owned corporation Rosnano, Russia will probably switch to chips for bank cards with interactive RFID radio communications, with the help of which in the next few years, a retail revolution should take place in the world.
In confirmation of this, one can cite the fact that the State Corporation Rosnano and the IT company Sistematika create an enterprise for the development of RFID tags. Investment in the project will amount to 690 million rubles, the company's revenue by 2015 should reach 800 million rubles.
Based on the above, we can conclude that these technologies will soon become ubiquitous.
However, do not forget about security issues. This issue is especially acute when applying RFID-technologies in the military or financial spheres. Due to tight pricing constraints, the protection system must not only be reliable and productive, but also cheap to implement.
To achieve this allows the use of LW-cryptography. This section of cryptography aims to develop algorithms for use in devices that are not capable of providing most of the existing ciphers with sufficient resources to function.
As passive RFID-tags are most widely used, the algorithms applicable specifically to them are further considered.
The basis of any LW-cryptosystem used in RFID-tags are symmetric algorithms. Their use is primarily due to a higher speed compared to asymmetric ciphers, which is critical in the devices in question.
Every developer of algorithms in the field of LW-cryptography is forced to seek a balance between reliability, performance and price. For example, for block ciphers, the key size determines the reliability / cost ratio, the number of encryption rounds determines reliability / performance, and the hardware design features determine performance / price. As a rule, any two of the three design goals can be easily achieved, while meeting all three requirements is an extremely difficult task. For example, it is possible to provide an acceptable ratio between reliability and performance, however, to implement such an algorithm, a large area will be required in the diagram, which leads to an increase in cost. On the other hand, you can create a reliable and cheap system, but with limited performance.
Obviously, this problem has three solutions:
1. Use proven standard algorithms.
2. Modification of known algorithms in order to improve performance and reduce logical complexity.
3. Development of new algorithms.
The problem with the first approach is that most modern ciphers were originally designed for use in software, without regard to hardware applications. Of course, this approach is justified, because, firstly, most of the algorithms are used on computers, and secondly, due to the cheapness of modern processors, the creation of high-performance, low-cost hardware implementations does not pose a problem. However, for RFID systems, these assumptions do not work, which means that the use of standard cryptographic algorithms in them is impossible.
The second approach is to modify the cipher with a rich history of research, which was originally designed for use in hardware. The indisputable advantage of this solution is that a lot of research has already been devoted to the reliability of the cipher under consideration and, therefore, the work to eliminate the weaknesses of the algorithm being created is simplified. However, one should not forget that careless modification of the system can lead to serious undesirable consequences. Therefore, when changing some elements of the algorithm, it is necessary to carefully evaluate the likelihood of additional weaknesses.
Most of the solutions in the field of LW-cryptography is based on the third approach. It is clear that the creation of a new cipher without certain flaws in persistence is a rather difficult task, however, the existing algorithms show good results and, perhaps, will find their use in the future in cryptosystems that ensure the security of RFID devices.
There are both block and stream LW-algorithms. At the moment, only three described stream LW cipher are known, having relatively acceptable characteristics. These are the MICKEY, Trivium and GRAIN algorithms. However, these codes are not applicable in passive RFID systems due to the individual characteristics of each of them. For example, Trivium requires an area on the chip that is more than one and a half times the allowable (3488GE * with a limit of 2000GE). The current version of the GRAIN cipher can be successfully attacked on the associated keys. As for MICKEY, the developers tested its resistance to only certain attacks, but this is not enough to ensure confidence in its reliability.
Thus, we can conclude that at the moment among stream ciphers there is no algorithm that meets the basic requirements of RFID systems.
In the block cipher section, the situation is somewhat better. Let us consider in more detail some block LW-algorithms.
First of all, it is worth noting the DESL cipher. It was developed based on the DES (Data Encryption Standart) algorithm described in the early 70s of the last century. The choice of this cipher as the basis for a new cryptosystem is not accidental. The advantage of DES over other known algorithms is, first of all, that it was originally designed for use in hardware devices. Also, due to the fact that this cipher has a more than thirty-year history of research, it can be assumed that its main vulnerabilities have been found and fixed.
To optimize the use of DES in RFID systems, a modification was carried out. First of all, IP and IP -1 permutations were excluded, which do not affect the durability, but occupy a place in the diagram. Then, the eight original S-boxes were replaced with one, repeated eight times. The authors proved that this change does not affect the resistance of the algorithm to basic attacks, such as linear and differential cryptanalysis. The resulting cipher was called DESL. Its main disadvantage is the small key size - 56 bits. Although it takes months to run a cluster of several dozen computers to open it completely, this task can be solved on a supercomputer in just three days. Therefore, such an algorithm should be applied only where short-term protection is required, or where the importance of the protected data is relatively small. The implementation of the algorithm requires 1848GE, which is an acceptable requirement for an LW cipher.
The next block LW algorithm that meets all the requirements of RFID systems is PRESENT.
Unlike DESL, this cipher uses an 80-bit key, which significantly increases its reliability. The developers conducted a study of the vulnerability of this algorithm to linear and differential analysis, algebraic attack, and some other types of attacks. The PRESENT durability shown is an excellent result for a cipher created from scratch. At the moment, not a single successful attack on the full-round version of the algorithm is known.
There are various PRESENT implementations. The smallest one requires only 1000GE, which is one of the best results for LW ciphers.
In addition to ensuring the security of the transmitted data in RFID-systems, some modifications of PRESENT have found application in other resource-dependent devices. For example, H-PRESENT-128 is the most compact of the known hash functions. In addition, it is possible to use the algorithm as a pseudo-random number generator for the crypto-GPS scheme.
Also among the LW-ciphers, you can select the family of algorithms KATAN and KTANTAN.
Each of the families consists of three ciphers, differing in the number of encryption rounds: 32, 48 or 64. All ciphers have an 80-bit key. The difference between KTANTAN and KATAN is that the former require less resources due to the fact that the encryption key is “sewn” into the device and cannot be changed. In the description of ciphers, developers have shown resistance to such attacks as differential and linear analyzes, an attack on related keys and an algebraic attack.
The hardware implementations of KTANTAN representatives show the best results in this field of cryptography. For example, the KTANTAN48 algorithm can be implemented using a total of 588GE, which is almost half the size of the most compact implementation of PRESENT.
However, despite all the advantages of the block ciphers described above, and for them there are certain threats that do not allow using them everywhere. As already mentioned, the DESL algorithm uses a relatively short key, which makes its use in devices whose security must be provided at a high level impossible. The PRESENT and KTANTAN algorithms, despite the many studies conducted over the past few years, can carry critical vulnerabilities that will nullify all current advantages.
There are many more block LW-algorithms. However, they have certain disadvantages. For example, MIBS and TWIS show good results, both in terms of speed and efficiency, but not enough research has been done, which, as in the case of flow algorithms, does not allow us to judge their reliability with due confidence. Other ciphers, such as HIGHT or mCrypton, require too much space on the chip for hardware implementation.
Thus, summarizing all the above, we can conclude that the task of creating both a stream and block encryption algorithm for passive RFID tags is still relevant and needs to be addressed.
Any RFID system consists of a reader and an RFID tag (sometimes the term RFID tag is also used).
Most RFID tags consist of two parts: an integrated circuit for storing and processing information and an antenna for receiving and transmitting a signal.
By type of power source, RFID tags are divided into the following categories:
')
• passive
• active
• semi-passive
Passive RFID tags do not have an embedded power source. The electric current induced in the antenna by the electromagnetic signal from the reader provides sufficient power for the functioning of the silicon chip placed in the label and the transmission of the response signal.
Active RFID tags have their own power source and do not depend on the reader’s energy, as a result, they are readable in the far distance, are large and can be equipped with additional electronics. However, such tags are most expensive, and battery life is limited.
Semi-passive RFID tags, also called semi-active, are very similar to passive tags, but are equipped with a battery that provides power to the chip.
Currently, RFID technologies are used in a wide variety of fields: from agriculture to transport.
According to the general director of the state-owned corporation Rosnano, Russia will probably switch to chips for bank cards with interactive RFID radio communications, with the help of which in the next few years, a retail revolution should take place in the world.
In confirmation of this, one can cite the fact that the State Corporation Rosnano and the IT company Sistematika create an enterprise for the development of RFID tags. Investment in the project will amount to 690 million rubles, the company's revenue by 2015 should reach 800 million rubles.
Based on the above, we can conclude that these technologies will soon become ubiquitous.
However, do not forget about security issues. This issue is especially acute when applying RFID-technologies in the military or financial spheres. Due to tight pricing constraints, the protection system must not only be reliable and productive, but also cheap to implement.
To achieve this allows the use of LW-cryptography. This section of cryptography aims to develop algorithms for use in devices that are not capable of providing most of the existing ciphers with sufficient resources to function.
As passive RFID-tags are most widely used, the algorithms applicable specifically to them are further considered.
The basis of any LW-cryptosystem used in RFID-tags are symmetric algorithms. Their use is primarily due to a higher speed compared to asymmetric ciphers, which is critical in the devices in question.
Every developer of algorithms in the field of LW-cryptography is forced to seek a balance between reliability, performance and price. For example, for block ciphers, the key size determines the reliability / cost ratio, the number of encryption rounds determines reliability / performance, and the hardware design features determine performance / price. As a rule, any two of the three design goals can be easily achieved, while meeting all three requirements is an extremely difficult task. For example, it is possible to provide an acceptable ratio between reliability and performance, however, to implement such an algorithm, a large area will be required in the diagram, which leads to an increase in cost. On the other hand, you can create a reliable and cheap system, but with limited performance.
Obviously, this problem has three solutions:
1. Use proven standard algorithms.
2. Modification of known algorithms in order to improve performance and reduce logical complexity.
3. Development of new algorithms.
The problem with the first approach is that most modern ciphers were originally designed for use in software, without regard to hardware applications. Of course, this approach is justified, because, firstly, most of the algorithms are used on computers, and secondly, due to the cheapness of modern processors, the creation of high-performance, low-cost hardware implementations does not pose a problem. However, for RFID systems, these assumptions do not work, which means that the use of standard cryptographic algorithms in them is impossible.
The second approach is to modify the cipher with a rich history of research, which was originally designed for use in hardware. The indisputable advantage of this solution is that a lot of research has already been devoted to the reliability of the cipher under consideration and, therefore, the work to eliminate the weaknesses of the algorithm being created is simplified. However, one should not forget that careless modification of the system can lead to serious undesirable consequences. Therefore, when changing some elements of the algorithm, it is necessary to carefully evaluate the likelihood of additional weaknesses.
Most of the solutions in the field of LW-cryptography is based on the third approach. It is clear that the creation of a new cipher without certain flaws in persistence is a rather difficult task, however, the existing algorithms show good results and, perhaps, will find their use in the future in cryptosystems that ensure the security of RFID devices.
There are both block and stream LW-algorithms. At the moment, only three described stream LW cipher are known, having relatively acceptable characteristics. These are the MICKEY, Trivium and GRAIN algorithms. However, these codes are not applicable in passive RFID systems due to the individual characteristics of each of them. For example, Trivium requires an area on the chip that is more than one and a half times the allowable (3488GE * with a limit of 2000GE). The current version of the GRAIN cipher can be successfully attacked on the associated keys. As for MICKEY, the developers tested its resistance to only certain attacks, but this is not enough to ensure confidence in its reliability.
Thus, we can conclude that at the moment among stream ciphers there is no algorithm that meets the basic requirements of RFID systems.
In the block cipher section, the situation is somewhat better. Let us consider in more detail some block LW-algorithms.
First of all, it is worth noting the DESL cipher. It was developed based on the DES (Data Encryption Standart) algorithm described in the early 70s of the last century. The choice of this cipher as the basis for a new cryptosystem is not accidental. The advantage of DES over other known algorithms is, first of all, that it was originally designed for use in hardware devices. Also, due to the fact that this cipher has a more than thirty-year history of research, it can be assumed that its main vulnerabilities have been found and fixed.
To optimize the use of DES in RFID systems, a modification was carried out. First of all, IP and IP -1 permutations were excluded, which do not affect the durability, but occupy a place in the diagram. Then, the eight original S-boxes were replaced with one, repeated eight times. The authors proved that this change does not affect the resistance of the algorithm to basic attacks, such as linear and differential cryptanalysis. The resulting cipher was called DESL. Its main disadvantage is the small key size - 56 bits. Although it takes months to run a cluster of several dozen computers to open it completely, this task can be solved on a supercomputer in just three days. Therefore, such an algorithm should be applied only where short-term protection is required, or where the importance of the protected data is relatively small. The implementation of the algorithm requires 1848GE, which is an acceptable requirement for an LW cipher.
The next block LW algorithm that meets all the requirements of RFID systems is PRESENT.
Unlike DESL, this cipher uses an 80-bit key, which significantly increases its reliability. The developers conducted a study of the vulnerability of this algorithm to linear and differential analysis, algebraic attack, and some other types of attacks. The PRESENT durability shown is an excellent result for a cipher created from scratch. At the moment, not a single successful attack on the full-round version of the algorithm is known.
There are various PRESENT implementations. The smallest one requires only 1000GE, which is one of the best results for LW ciphers.
In addition to ensuring the security of the transmitted data in RFID-systems, some modifications of PRESENT have found application in other resource-dependent devices. For example, H-PRESENT-128 is the most compact of the known hash functions. In addition, it is possible to use the algorithm as a pseudo-random number generator for the crypto-GPS scheme.
Also among the LW-ciphers, you can select the family of algorithms KATAN and KTANTAN.
Each of the families consists of three ciphers, differing in the number of encryption rounds: 32, 48 or 64. All ciphers have an 80-bit key. The difference between KTANTAN and KATAN is that the former require less resources due to the fact that the encryption key is “sewn” into the device and cannot be changed. In the description of ciphers, developers have shown resistance to such attacks as differential and linear analyzes, an attack on related keys and an algebraic attack.
The hardware implementations of KTANTAN representatives show the best results in this field of cryptography. For example, the KTANTAN48 algorithm can be implemented using a total of 588GE, which is almost half the size of the most compact implementation of PRESENT.
However, despite all the advantages of the block ciphers described above, and for them there are certain threats that do not allow using them everywhere. As already mentioned, the DESL algorithm uses a relatively short key, which makes its use in devices whose security must be provided at a high level impossible. The PRESENT and KTANTAN algorithms, despite the many studies conducted over the past few years, can carry critical vulnerabilities that will nullify all current advantages.
There are many more block LW-algorithms. However, they have certain disadvantages. For example, MIBS and TWIS show good results, both in terms of speed and efficiency, but not enough research has been done, which, as in the case of flow algorithms, does not allow us to judge their reliability with due confidence. Other ciphers, such as HIGHT or mCrypton, require too much space on the chip for hardware implementation.
Thus, summarizing all the above, we can conclude that the task of creating both a stream and block encryption algorithm for passive RFID tags is still relevant and needs to be addressed.
Source: https://habr.com/ru/post/119700/
All Articles