Hacking of metro (travel, cards) + ALGORITHM OF CRYPTOGRAPHIC TRANSFORMATIONS IN ACCORDANCE WITH GOST 28147-89
Hacking the metro (travel, cards)
Do you know the desire to solve all the riddles and reveal all the protections of the Moscow Metro? To make, for example, to itself an "eternal ticket"? But the metro specialists are constantly finding more and more sophisticated ways of protecting themselves. Metal tokens were replaced by plastic ones, those, in turn, by magnetic tickets, and magnetic cards were replaced by non-contact cards. Many researchers dropped their hands - it seems that the Metropolitan has become an impregnable fortress. But any protection can be bypassed. And often, it is much easier to open it than to build it ...
How it all began
Interest in subway systems appeared for a long time, I can say, from a school bench, when there were still tickets with a magnetic stripe in the course. At the same time (from a dozen years ago), a contactless social card for students was put into circulation. I became interested in what it is and how it works. But in those days I did not have enough skills, and there was not much information available, especially on these technologies. I had to postpone the idea of research in a long box, but I promised myself that I would definitely return to it ...
About three years ago I again woke up interest in the subway theme. I actively studied magnetic tickets (there was a lot of information on the subject in the Internet) and even assembled a small machine for making duplicates of two heads from reel tape recorders and a small amount of rassypuhi. I have not forgotten about my social card (already student card). But after studying the documentation, it became clear to me that the system is almost impregnable - the MF1S50 Mifare Classic 1K chip, on the basis of which social cards are made, is protected by two 48-bit keys. At the hardware level, it can not be hacked so easily, and keys can be sorted out to the end of the solar system. Yes, and the cardholders that support the Classic, were at that time worth some extra money (about Ebay, I somehow did not think, alas). Interest in magnetic tickets quickly cooled down, and the social card had to be postponed again until better times.
Meet: "Ultralight"
Tickets "Ultralight" appeared in our metro recently, but immediately aroused great interest among the public. They began to chicken, tear, paste an iron and apply other methods of thermal rectal cryptanalysis. I must admit, the thirst for knowledge made me and raskurochit couple. As a result of their study and searches on the Internet was established - it's nothing more than Mifare Ultralight, a "lightweight" compatible version of Mifare Classic. A quick review of the documentation on the chips of this standard made it clear that there are no built-in security systems for these cards. To all else, I attacked an article detailing the successful breaking of a similar transport system by Dutch students. All together, it pushed me to new research.
Go!
To start, of course, it was just necessary to get a wireless card reader supporting "Ultralight" somewhere. There were two options: either to assemble yourself (which would take a lot of time), or buy a ready-made device. At the thought of the second option, mindful of the prices three years ago, I got goose bumps. But I still decided to look at the current prices. And not in vain! I was pleasantly surprised to learn that you can buy a fully functional device (OmniKey CardMan 5321), which supports a bunch of wired and wireless cards at an attractive price - 4000 rubles.
Of course, not a little, but on the other hand, it's not 10000; Moreover, the purchase of a ready reader made it possible immediately to focus on the research of tickets, and not on the design and debugging of iron, which could be delayed indefinitely. Together with the reader from the same company (ISBC) was purchased a very convenient original SDK of local production. He, again, allowed not to waste energy and time to write low-level and debug the work of the software with the reader, and concentrate directly on the tickets. So, for a couple of days of unhurried coding, a small program was born, with the help of which it was possible to observe and control the entire internal structure of "Ultralights" in a convenient form. Then I began to study tickets.
Deaf Wall
In the process of studying through my reader passed a lot of tickets. Some I rolled up my sleeves, got out of the trash, bought some - watched what they wrote down, then passed and looked again. It was tickets of almost all types, with the exception, perhaps, of the travel "Ultralight" for 70 trips. In a couple of weeks I have accumulated a large and sorted database of dumps of different tickets and in different states. There were dumps taken from the same ticket after each trip, and several tickets with Metro numbers running in a row. In my collection, even a few dumps of two different temporary single social tickets (one was issued for a period of 5 days, the other for 30), taken over a certain time interval. It turned out to be very interesting specimens, and at the same time very rare (I got them first-hand with an immediate return, only for "read").
In fact, this is almost the only type of "Ultralights", which works not only in the metro, but also on land transport. In addition, only this type of ticket does not have a limit on the number of trips. Subsequently, they served me very well ... All this zoo I collected for one purpose - to clearly define the structure and format of recording data on the ticket. Of course, some fields were visible at once, with the naked eye, but some are not. For example, I did not immediately understand where the metro ticket number was recorded (the one that is printed on it). Awareness came completely by accident. The fact is that I (as well as, I think, most of us), looking at the hex, is used to align information for bytes and think, at least, bytes. It turned out that this approach is wrong. Looking at the ticket dump, you need to think in smaller units - tetrads, and sometimes bits. I realized that when I finally saw the ticket number, it was moved by 4 bits with respect to the beginning of the byte, and the remaining 4 bits from the other side of the number was occupied by other official information. After a while, the format for recording data on tickets became almost completely clear.
It became obvious where and how all the dates, counters, identifiers are stored. There were only a couple of fields, the purpose of which was unclear simply because the data in them were identical from the dump to the dump. But on this all the joy and ended - it would be foolish to assume that such tickets can leave unprotected. In each dump there were 32 bits of various information that did not correlate with the rest of the content. I assumed that this is a kind of checksum, a "hash" of data written on the ticket. All attempts to estimate or calculate these 32 bits turned out to be a total failure (in particular, it was assumed that this is some kind of CRC32, with a non-standard polynomial and starting value).
When you try to change at least one and a half bits of information inside the ticket, the checkout terminal in the subway flashed "BAD TICKET" with a hefty jack, nailing the last nails into the coffin lid. Of course, there were attempts to bypass the system in other ways, for example, trying to copy the ticket to a clean one-to-one card (here, alas, the factory serial, which, it turned out, also participated in the generation of hash), or set the lock bits so to prohibit the turnstile from changing the contents of the ticket. The verification terminal has recognized this "eternal" ticket, but refused to allow the turnstile ... So I rested against the wall. In that big, strong concrete wall, about which many have a habit of being killed from a take-off. I did not find any information on the forums and boards, I decided that this is where my studies are finished - there are no more ways, and put a fat point. As it turned out, in vain ...
Strange acquaintance
The September evening was no different from the others. It was almost night, the street was cool and damp. I was sitting in front of the monitor screen, and, sipping a warm, slightly sweet green tea, peacefully bred a board for my next craft. DipTarce, a little bastor, ICQ ... Someone called on Skype - distracted! Again ICQ, again DipTrace - in general, everything is as usual. Once again, the window of ICQ popped into the foreground - someone, hitherto unknown to me, wrote "Hello". I, in no way hesitating, answered the same. The following message was a turning point in the whole story: "You are interested in the subway, I have some garbage there. If interested, let's meet, I'll tell you. " At first, I was a bit confused and alarmed (maybe a divorce or a set-up, and maybe even "special services" became interested - paranoia takes its toll), but then I thought: why not?
Special services I would not be interested in, and the soil for divorce, and even more so, for the setup there seems to be no. After a short conversation, we agreed to meet in the afternoon, in the center of the hall of one of the Moscow metro stations. The stranger was a tall young man, wearing glasses, with a large black plastic bag in his hands. We greeted each other, then he handed me a packet with the words: "On, hold. It did not come in handy anyway, maybe it will be useful for you. " Looking inside, I saw two subway terminals, translated by newspapers, several chaotically scattered white plastic cards and a pig in the box. To my question about how much I owe this (money), the guy shook his head, smiled and said: "Do not you, nobody should do anything to anyone ... So, I already need to run, and my train is like time! OK Bye!".
With these words, he fled, jumped into the already closed doors of the car and left. And I, I confess, went home a little in neponyatkah. Contact from ICQ I just in case deleted, at the same time cleaning the contactee on the server and cleaning logs (again hello, paranoia). In the end, write again, if that. But he never wrote to me again ...
The phenomenon of software people
Arriving home, I dismantled the package. The second of the terminals was a bus validator (heavy, pancake!); the cards were Mifare Classic 1K (clean), and the disc had one single archive. After a cursory examination of the contents it turned out - this is a software that is used at the ticket offices of the metro. Putting aside the terminal and the validator, I decided to take up the study of interesting software. About an hour from the mess that was unpacked, I managed to build and run this program on my computer. Another hour was required to understand its structure. After combing all the ini-files (with comments kindly left by the developer), I already had a full idea of what it is, how it works and what it's eating. Eat, as it turned out, with the reader Parsec PR-P08, so, for lack of it, try the software in action failed.
The developer was the firm "Smartek" - a major state contractor developing systems of this kind (more details can be read on their website). The program was written in Delphi using runtime-bpl'ok. Moreover, the software had a modular structure, and all subroutines, classes, and components were located in separate DLLs or bpl'ks with talking names (that was the most important file of developers). After a cursory analysis of the interiors of the software, I found out that, firstly, information about all issued tickets is transferred to a centralized database (by the way, it's Oracle) and, secondly, the program uses a certain key mechanism. The program could communicate with the database not only in real time. We draw conclusions: all operations in the system can occur with a certain delay. Theoretically, this gives us a head start.
But first of all I was interested in the mechanism of keys (I had already started to guess why it might be needed). So, I took up the disassembler and got to work. The mechanism consisted of two files - CryptKeyRef.dll and keys.d (the only "tricky" file in the entire program, which, unlike the file with the keys, no longer resembles anything). And I used all this good run-bpl'in SmLayout.bpl. This library was just a godsend for my research - it contained classes for working with the internal filling of tickets. Since it is runtime-bpl, it was enough just to look at its export table, in order to understand 60 percent of what's what. A more detailed analysis put everything in its place. Remember, at the beginning of the article, I said that in the structure of "Ultralight" there were still a few fields, the purpose of which was incomprehensible?
One of these fields is the so-called "layout identifier". In fact, all Metro tickets are built from a fixed header part and a variable piece of data. So, this "Layout" field in the header just determined how and what data are located in the remainder of the ticket. There are several such layouts (each for its own ticket type), and in SmLayout.bpl each of them corresponded to its own class (plus the common parent class, which had methods for working with the header part). Therefore, to understand which fields in each layout are responsible, it was easy (even if speaking with the names of the methods in the export!). Having completely got all the Layout 8 (which is used in "Ultralights") and rechecking, I had the right idea about all the fields in the ticket structure, I took up the key mechanism. Indeed, he was responsible for the generation of the hash. How the mechanism works, it became completely clear after studying the work of the method responsible for calculating the hash. First, the correct key is selected from the key file (keys.d).
The system is arranged so that each type of ticket has its own identifier (complete with a table with ticket identifiers and names, as a text file with values separated by a comma). It consists of the identifier of the zone (application) and the identifier of the type of the map. So, based on these numbers, keying is selected in the key file, inside of which there may be several keys (in case the new key was entered, and old tickets are still used). The new ticket is recorded using the very first ticket, and validation is done using all keys in the keying. Then the selected key is decrypted with CryptKeyRef.dll (why they are stored encrypted, I will not put my mind to it). After that, the decrypted key and almost all ticket data, as well as its hardware serial number and number (the method of generating a "hash", which is specified for keying in keys.d) - are passed to the function ckCalcHashCode, located in the same CryptKeyRef.dll. At the output, we get a value on which I in my time and "stuck" - the same "hash". Of course, I wrote a small program that, using these functions from CryptKeyRef.dll and file keys.d, could check and, in which case, recalculate the "hash" inside any dump. I rechecked everything on several dumps, and, having received a positive result, went away, contented, to sleep.
Foul keys
Despite the theoretical success, I wanted to check everything, so to speak, "in battle." The next day, returning from work, I specifically bought a fresh "Ultralight" for one trip to see if my keys are working or not (apparently they were old). You can, of course, immediately try to write "fabricated" "Ultralight" and go check, but at that time I ran out of blank cards, and a bit scary to go "at random" - all of a sudden what? When I got home, I first of all, without even washing my hands, with impatience rushed to check the fresh ticket with my keys. And then I waited for a big bummer - "hash", recorded in the ticket did not pass through any of the keys. So, the keys are really already foul and replaced by new ones. This completely crossed out all my works. I was a little sad. I brewed green tea, played a little on the piano (yes-yes) and sat down to plant my unfinished fee ...
Not all is lost yet
The idea came to me unexpectedly, when I once again for some reason looked inside the file with the keys. I noticed that in the "running" keying (which is used to calculate 1-, 2-, 5-way and other "Ultralights") there were two keys - a new one (at that time, of course) and, apparently, an old one. But there was also a keying, in which there was only one key. Before, I did not pay attention to it, and concentrated on the "running" one. To calculate what tickets this key is used for, I did not know. When I looked, what kind of ticket is tied to the casing, then I flashed a small spark of hope. The matter is that this type of ticket was - VESB. Yes, it is this rare type of ticket - a temporary travel card for all types of transport. I figured that if the ticket is single, then this key should be used not only in the metro, but also on land transport, where it is very difficult and long to replace it with a new one.
In addition, there is only one key in keiring, which indirectly confirmed my guess. To all else, I remembered that when I cleaned out the metro program from different "garbage", there was something similar to the archive of old key files. After digging and opening the original archive, I saw that it was really so. And most importantly, having looked through all the old key files, I found that this key remained unchanged! Already without a single drop of doubt, I riveted my own VESB (good, I had dumps of the type that at times simplified the task - I just changed the date and number in the dumps), and the "hash" calculated using this key. So, it's time to check (especially, I just bought some more clean plastic). Entering the lobby, I first put my "ticket" to the verification terminal. The scoreboard showed the expiration date of the ticket, which I indicated, and the green LED lighted up. So it works. Making a grimace easier and hiding snow-white plastic in the sleeve, I went to the turnstile, put my hand to the validator and ... calmly walked to the cheerfully glowing green. This marked the final victory.
And what's next?
And then experiments began, during which a lot of interesting things were discovered. For example, for such a "left" VESB you can walk only two or three days. The fact is that the number that I indicate inside the ticket "from the bald", with each passage is stored in the memory of the head of the turnstile, and after some time is sent along with the rest to the data center. There the system does not find a really issued ticket with such a number and adds it to the stoplist, which is then sent to all the turnstiles of the metro. And this should happen with all types of tickets, not only with the VEBB - in addition to the "hash" and frequently changing keys this is a very good defense. To go around it, for obvious reasons, is not possible.
It has also been observed that installing or not installing lock bits plays no role in whether the ticket will work or not. The only exception is the OTP zone blocking bit, which the turnstile apparently always checks, even though it does not intend to write to OTP. Later I took up the metro and bus terminals, brought them in order, studied and launched them on the stand. Now, to check the next guess, it was no longer necessary to run with a freshly baked mutant ticket in the metro, but it became possible to check them "without departing from the ticket office." Moreover, the subway terminal turned out to be just as old (to all else and buggy), like my keys. So I could try "at work" and any other types of tickets "Ultralight" - something that I can never do "live" in the subway. In parallel with these experiments, I continued to work on software.
Since there was much debate about what kind of algorithm is used to calculate the "hash", I decided to completely restore it by rewriting the algorithm from scratch in the "human" programming language, and in the process I was just hoping to understand what kind of algorithm it was - that something widely known or some kind of own internal development. Along the way, I was visited by many different thoughts (including that it could be AES), but with a detailed study of the already working code without the use of Smartekov libraries it became clear that this algorithm is "only" GOST - the national encryption standard (all necessary information you can easily find it on the web). Specifically, a 16-Z loop was used to compute the hash. "Hash", in fact, it is nothing like an imitation GOST.
The structure of information recorded on the ticket "Ultralight"
What is the page, where and how the hardware serial number, lock bits and OTP zone are located, you can read in the original documentation (the file-specification in PDF format with full description of the chip is on the disk). I recommend starting the study with her. I'll describe the data structure structure formed by metro systems in the user area, which is accessible for reading and rewriting (in the absence of locks, of course). All contents of the ticket can be conditionally divided into the header part and two completely duplicating parts of the data (this is done for the purpose of redundancy and error protection). The header part in the tickets "Ultralight" starts from page 4. Part of it is identical in structure in all tickets and identifiers of the system of the Underground and MosGorTrans. The first 10 bits are the application identifier; the next 10 bits - the identifier of the type of the map (about what kind of identifiers there are, you can read in another specially selected for this frame). After the identifiers, the serial number of the ticket is located (it is knocked out on the back of the ticket, do not confuse it with the hardware - these are different things!) With a size of 32 bits. The last 4 bits are the Layout field, which tells the system how to interpret the subsequent data (something like the file format).
For Ultralight tickets, the Layout value is 0x08. This ends the same part of the title. Further in the ticket "Ultralight" is indicated the date on which the form is valid (16 bits). All dates in the system are indicated in the format of the number of days elapsed from 01/01/1992. Here the header part of the ticket "Ultralight" ends (tickets with another Layout can still contain various additional information). The first data area starts on page 8. First, 16 bits of the ticket issue date are recorded. After that, the validity period of the ticket in days (from the moment of issue) is 8 bits. The first 16 bits of page 9 are the trip counter. It can be either decreasing to zero (on all tickets with a restriction of the number of trips), or increasing from zero (on WESC tickets, without limiting the number of trips). After the counter, in the rest of the page the turnstile enters its unique identifier at each pass. Apparently, this is used to prevent re-passage without waiting for a ticket by the WESB (turnstiles in the lobby are connected to the network and interrogate each other), and also to see through which turnstile the pass was made (for example, in case of an error or for statistics ). Page 10 is completely occupied by a 32-bit hash.
Page 11 is empty. This data area is entirely replicated to the remaining 4 pages (from 12 to 15). It turns out that under normal operation these two regions always contain the same data. Separately it is necessary to say about the use of the OTP zone system. It is used for the gradual "burning out" of the ticket with every trip (VESB tickets do not apply). The two lowest-order bits are issued when the ticket is canceled or canceled (on the stop-sheet). The canceled ticket is not subject to recovery. Only 30 bits remain for burning out. This zone is represented by the system as 100% of trips. With each new trip, a certain number of bits are set (from junior to senior), corresponding to how much per trip takes. For example, for a 5-passenger ticket with each new trip, it will be burned out at 6 bits, and for a 60-way ticket - half a bit (rounded up). It is worth mentioning that the re-use of tickets "Ultralight" is impossible not only because of the "burning out" of OTP, but also because at the checkout, when issuing the ticket (and perhaps even when it is made), almost all pages are blocked for overwriting . Thus, neither "recharge" nor change the type of ticket to another will not work.
Examples of used subway ticket identifiers
All numbers are in decimal notation!
Application IDs:
- 262 - Ticket for the Moscow Metro.
- 264 - Ticket for land transport in Moscow.
- 266 - The single social of Moscow and the Ministry of Defense.
- 270 - Ticket "Light Metro".
Identifiers of the type of tickets "Ultralight":
- 120 - One trip.
- 121 - Two trips.
- 126 - Five trips.
- "Ten trips."
- "Twenty trips."
- 129 Sixty trips.
- 130 - Baggage + passage.
- 131 - Only luggage.
- 149 - Single "Ultralight" (70 trips).
- 150 - WESB.
Mifare Classic
I also paid attention to the ill-fated Mifare Classic 1K in my research. As you understand, the most important obstacle on the way to the "Classic" was the hardware keys A and B. By a lucky chance, these keys were in one of the modules of the program in an open form (to the developers!) And I had no trouble writing a small program for Work with the contents of these cards, using the received keys. In the course of the experiments, some interesting features were revealed, such as: the metro used the first sector of the map for storing the ticket, and the ground transport used the fourth; no protection, except for hardware keys (which, being written into the software in this form, most likely, never changed at all from the moment of putting the system into operation) on these tickets does not exist.
Instead, at the end of each block the CRC-16 is indicated, just to protect the data from corruption. In addition, on social cards, in addition to tickets, many more varied and interesting information are recorded. For example, in the 13th and 14th sectors of social cards, the surname, name and patronymic of the owner are indicated. These (and some other) data can be read using the public key 0xA0A1A2A3A4A5. During the experiments, it was possible to completely clone student SCM, as well as several tickets for pure Classic cards.
But the cloning system, as it turned out, is remarkably saved by the stop-loss system - this ticket can be used for no more than two days, then it is canceled (unlike the "Ultralight", the "Classic" card can be recovered after the cancellation, but from the stop-list it will not save). Since no protection on the Classic cards was used, they quickly became uninteresting to me, and I decided to concentrate on the Ultralight study.
The End, or Summarize
Metro systems, in particular, new tickets "Ultralight", contrary to the opinions and guesses, were well protected. Very pleased that the developers used a reliable and time-tested GOST, and did not reinvent the wheel. With such protection, to forge a ticket "Ultralight", without having access to confidential data (key information), it is simply impossible. Remarkably thought out and the system of replacement keys, and the mechanism of stop-sheets. Of course, there were shortcomings and mistakes. The biggest of them is software that is not protected in any way.
It was enough to abandon the use of runtime-bpl, and this would complicate the analysis tens of times! As an option, - processing of critical parts of the program AsProtect'om or ExeCryptor'om, followed by zakkovkoy all files MoleBox'om would reduce the possibility of analysis almost to zero. Toolkit something inexpensive. And the use of good (preferably, little-known or custom-made) protection of this kind, but with hardware keys would make the parsing of the program completely impossible. Of course, the Metropolitan is a regime enterprise, but do not forget about the human factor. After all, Kevin Mitnick said (and not only said, but also demonstrated by his own example, for which he sat down) that sometimes to achieve the goal it is easier and more effective to use "social engineering", rather than trying to break the impenetrable defense. Well, on this note I will finish my narrative. And to you, the reader, I wish more interesting and successful research!
Description of the cryptographic transformation algorithm in accordance with GOST 28147-89
This standard establishes a single cryptographic transformation algorithm for information processing systems in networks of electronic computers (computers), individual computer complexes and computers, which determines the rules for data encryption and development of imitovki.
The cryptographic transformation algorithm is intended for hardware or software implementation, satisfies cryptographic requirements and does not impose restrictions on the degree of secrecy of the protected information.
The standard is mandatory for organizations, enterprises and institutions that apply cryptographic protection of data stored and transmitted in computer networks, in separate computer systems or in computers.
Structural diagram of cryptographic transformation algorithm
The block diagram of the cryptographic transformation (cryptosystem) algorithm, shown in Figure 1, contains:
- - 256-bit key storage device consisting of eight 32-bit drives (X _{0} , X _{1} , X _{2} , X _{3} , X _{4} , X _{5} , X _{6} , X _{7} );
- - four 32-bit storage devices (N _{1} , N _{2} , N _{3} , N _{4} );
- - two 32-bit storage devices (N _{5} , N _{6} ) with the filling constants C _{2} , C _{1} recorded in them;
- - two 32-bit adder modulo 2 ^{32} (CM _{1} , CM _{3} );
- - 32-bit adder of bitwise summation modulo 2 (CM _{2} );
- - 32-bit adder modulo (2 ^{32} -1) (SM _{4} );
- - adder modulo 2 (CM _{5} ), the restriction on the capacity of the adder CM _{5 is} not superimposed;
- - substitution unit (K);
- - the register of the cyclic shift by eleven steps towards the highest discharge (R).
Picture 1.
The K substitution block consists of eight replacement nodes K _{1} , K _{2} , K _{3} , K _{4} , K _{5} , K _{6} , K _{7} , K _{8} with a memory of 64 bits each. The 32-bit vector arriving at the substitution block is divided into eight consecutive 4-bit vectors, each of which is converted to a 4-bit vector by the corresponding replacement node, which is a table of sixteen lines containing four fill bits per line. The input vector determines the address of the row in the table, the filling of this line is an outgoing vector. The 4-bit output vectors are then sequentially combined into a 32-bit vector.
When the binary vectors are added and cyclic shifted, the upper bits are bits of large numbers.
When writing a key (W _{1} , W _{2} , ..., W _{256} ), W _{q} Є {0,1}, q = i ÷ 256, â, the value W _{1} is entered in the 1st digit of the accumulator X _{0} , the value W _{2} is entered in the 2nd digit of the accumulator X _{0} , ..., the value W _{32} is input into the 32th digit of the accumulator X _{0} ; the value W _{33} is input into the 1st digit of the accumulator X _{1} , the value W _{34} is input into the 2nd digit of the accumulator X _{1} , ..., the value W _{64} is input to the 32th bit of the accumulator X _{1} ; the value W _{65} is input to the 1st digit of the accumulator X _{2} , etc., the value of W _{256} is input to the 32th bit of the accumulator X _{7} .
When overwriting information, the content of the p- th digit of one accumulator (adder) is rewritten to the p- th digit of another accumulator (adder).
The value of the filling constant C _{1} (constant) of accumulator N _{6 is} given in Table 1.
Table 1
Discharge of accumulator N _{6} |
32 |
31 |
thirty |
29 |
28 |
27th |
26th |
25 |
24 |
23 |
22 |
21 |
20 |
19 |
18 |
17th |
The value of the digit |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
Discharge of accumulator N _{6} |
16 |
15 |
14 |
13 |
12 |
eleven |
10 |
9 |
8 |
7th |
6th |
5 |
4 |
3 |
2 |
1 |
The value of the digit |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
The value of the filling constant C _{2} (constant) of accumulator N _{5 is} given in Table 2.
table 2
Discharge of accumulator N _{5} |
32 |
31 |
thirty |
29 |
28 |
27th |
26th |
25 |
24 |
23 |
22 |
21 |
20 |
19 |
18 |
17th |
The value of the digit |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
Discharge of accumulator N _{5} |
16 |
15 |
14 |
13 |
12 |
eleven |
10 |
9 |
8 |
7th |
6th |
5 |
4 |
3 |
2 |
1 |
The value of the digit |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
The keys that define the filling of the CMU and the tables of the K substitution box are secret elements and are delivered in the established order.
Filling in the tables of the K substitution box is a long-term key element common to the computer network.
The organization of various types of communication is achieved by building an appropriate key system. In this case, it is possible to use the possibility of generating keys (filling in the RAM) in the simple replacement mode and encrypting them in a simple replacement mode, providing imitation protection for transmission via communication channels or storage in computer memory.
There are four types of work in the cryptographic circuit:
- - Encryption (decryption) of data in a simple replacement mode;
- - Encryption (decryption) of data in the gamma mode;
- - Encryption (decryption) of data in the mode of gumming with feedback;
- - mode of development of imitation.
Encryption in simple replacement mode
Encryption of open data in simple replacement mode
A cryptogram that implements the encryption algorithm in the simple replacement mode should have the form shown in Figure 2.
Figure 2
The public data to be encrypted is divided into blocks of 64 bits each. The input of any block T _{0} = (a _{1} (0), a _{2} (0), ..., a _{32} (0), b _{1} (0), b _{2} (0), ..., b _{32} (0)) of binary information in the accumulators N _{1} and N _{2 are} made so that the value a _{1} (0) is introduced into the 1st bit N _{1} , the value a _{2} (0) is introduced into the 2nd bit N _{1} , etc., the value a _{32} ( 0) is introduced into the 32-th bit N _{1} ; The value b _{1} (0) is entered in the 1st bit N _{2} , the value b _{2} (0) is entered into the 2nd bit N _{2} , etc., the value b _{32} (0) is inputted to the 32-th bit N _{2} . As a result, the state (a _{32} (0), a _{31} (0), ..., a _{2} (0), a _{1} (0)) of the storage ring N _{1} and the state (b _{32} (0), b _{31} (0), ... , b _{2} (0), b _{1} (0)) of the storage ring N _{2} .
256 bits of the key are entered in the CMU. The contents of the eight 32-bit drives X _{0} , X _{1} , ..., X _{7} are:
- X _{0} = (W _{32} , W _{31} , ..., W _{2} , W _{1} )
- X _{1} = (W _{64} , W _{63} , ..., W _{34} , W _{33} )
- . . . . . . . . . . . . .
- X _{7} = (W _{256} , W _{255} , ..., W _{226} , W _{225} )
The algorithm of encryption of a 64-bit block of open data in the simple replacement mode consists of 32 cycles.
In the first cycle, the initial filling of the accumulator N _{1 is} summed modulo 2 ^{32} in the adder CM _{1} with the filling of the accumulator X _{0} , while the storage of the accumulator N _{1 is} retained.
The result of the summation is transformed into the substitution block K and the resulting vector is fed to the input of the register R, where it is cyclically shifted by eleven steps towards the higher-order bits. The result of the shift is summed bitwise modulo 2 in the CM _{2} adder with a 32-bit fill of the N _{2} storage ring. The result obtained in CM _{2 is} written in N _{1} , while the old value of N _{1 is} rewritten in N _{2} . The first cycle ends.
The subsequent cycles are carried out in the same way, while in the 2nd cycle, the filling X _{1 is} read from the FEC, in the 3rd cycle, the filling X _{2 is} read from the FEC, etc., the filling X _{7 is} read from the CCD in the 8th cycle. In the cycles from the 9th to the 16th, as well as in the cycles from the 17th to the 24th, the fillings from the QCD are read in the same order: X _{0} , X _{1} , X _{2} , X _{3} , X _{4} , X _{5} , X _{6} , X _{7} .
In the last eight cycles from the 25th to the 32nd, the order of reading the fillings of the CCD is reversed: X _{7} , X _{6} , X _{5} , X _{4} , X _{3} , X _{2} , X _{1} , X _{0} .
Thus, when encrypting in 32 cycles, the following order is used to select the contents of the drives:
- X _{0} , X _{1} , X _{2} , X _{3} , X _{4} , X _{5} , X _{6} , X _{7} , X _{0} , X _{1} , X _{2} , X _{3} , X _{4} , X _{5} , X _{6} , X _{7} ,
- X _{0} , X _{1} , X _{2} , X _{3} , X _{4} , X _{5} , X _{6} , X _{7} , X _{7} , X _{6} , X _{5} , X _{4} , X _{3} , X _{2} , X _{1} , X _{0} .
In the 32nd cycle, the result from the CM _{2} adder is inserted into the N _{2} accumulator, and the old filling is stored in the storage N _{1} .
Encryption of the N _{1} and N _{2} accumulators received after the 32th cycle of encryption is a block of encrypted data corresponding to the open data block.
Decrypting encrypted data in a simple replacement mode
A cryptogram that implements the decryption algorithm in the simple replacement mode has the same form (see Figure 2) as in the case of encryption. In the ROM, 256 bits of the same key on which the encryption was performed are entered. The encrypted data to be decrypted is divided into blocks of 64 bits each. The input of any block is T = (a _{1} (32), and _{2} (32), ..., and _{32} (32), b _{1} (32), b _{2} (32), ..., b _{32} (32) _{1} and N _{2 is} done so that the value of a _{1} (32) is entered in the 1st bit N _{1} , the value of a _{2} (32) is entered into the 2nd bit N _{1} , etc., the value of a _{32} (32) is introduced into the 32-th bit N _{1} ; the value b _{1} (32) is introduced into the 1st bit N _{2} , the value b _{2} (32) is introduced into the 2nd bit N _{2} , etc., the value b _{32} (32) is introduced into the 32-th bit N _{2} .
The decryption is carried out by the same algorithm as the encryption of the open data, with the change that the filling of the storage units X _{0} , X _{1} , ..., X _{7 is} read out from the CPU in the decryption cycles in the following order:
- X _{0} , X _{1} , X _{2} , X _{3} , X _{4} , X _{5} , X _{6} , X _{7} , X _{7} , X _{6} , X _{5} , X _{4} , X _{3} , X _{2} , X _{1} , X _{0} ,
- X, X, X, X, X, X, X, X, X, X, X, X, X, X, X.
Received after 32 cycles of operation, the filling of the accumulators N _{1} and N _{2} is made up of an open data block.
T _{0} = (a _{1} (0), a _{2} (0), ..., a _{32} (0), b _{1} (0), b _{2} (0), ..., b _{32} (0)) corresponding to the block of encrypted data, the value of a _{1} (0) of the block T _{0} corresponds to the content of the 1st digit N _{1} , the value a _{2} (0) corresponds to the contents of the 2nd digit N _{1} , etc., the value a _{32} (0) corresponds to the contents of the 32- th digit N _{1} ; the value b _{1} (0) corresponds to the contents of the 1st digit N _{2} , the value b _{2} (0) corresponds to the contents of the 2nd digit N _{2} , etc., the value b _{32} (0) corresponds to the contents of the 32th bit N _{2} .
Similarly, the remaining blocks of encrypted data are decrypted.
Gamma Mode
Encryption of open data in the gamma mode
A cryptogram that implements the encryption algorithm in the gamma mode must have the form shown in Figure 3.
Figure 3
Open data, divided into 64-bit blocks T _{0}^{(1)} , T _{0}^{(2)} , ..., T _{0}^{(M-1)} , T _{0}^{(M)} , are encrypted in the gamma mode by bitwise summation modulo 2 in the CM adder _{5} with gamma of the cipher G, which is produced by blocks of 64 bits, i.e.
^{(1)} , _{Γω}^{(Σ)} , ..., Γ, ^{(Μ-1)} , _{Γω}^{(Μ)} ),
where M is determined by the amount of encrypted data.
^{(I)} is the i-th 64-bit block, i = 1 ÷ Ì, the number of bits in the block T _{0}^{(M)} can be less than 64, while the portion of the cipher scale from the block F _{m}^{(M)} unused for encryption, discarded.
256 bits of the key are entered in the CMU. In drives N _{1} , N _{2, a} 64-bit binary sequence (synchronous sending) S = (S _{1} , S _{2} , ..., S _{64} ) is introduced, which is the initial filling of these drives for the subsequent generation of M blocks of the cipher gamma. Synchronization is introduced in N _{1} and N _{2} so that the value of S _{1} is input to the 1st bit N _{1} , the value S _{2} is input into the 2nd bit N _{1} , etc., the value of S _{32} is input into the 32-bit N _{1} ; the value S _{33} is inputted to the 1st bit N _{2} , the value S _{34} is input to the 2nd bit N _{2} , etc., the value S _{64} is inputted to the 32-bit N _{2} .
Initial filling of drives N _{1} and N _{2} (synchronous sending S) is encrypted in the simple replacement mode in accordance with the requirements of paragraph 1.3.1. The result of the encryption is rewritten in 32-bit accumulators N _{3} and N _{4} so that the filling N _{1 is} rewritten in N _{3} , and the filling N _{2 is} rewritten in N _{4} .
Filling of the accumulator N _{4 is} summed modulo (2 ^{32} -1) in the adder SM _{4} with 32-bit constant С _{1} from the accumulator N _{6} , the result is written in N _{4} .
Filling of the accumulator N _{3 is} summed modulo 2 ^{32} in the adder SM _{3} with a 32-bit constant C _{2} from the accumulator N _{5} , the result is written in N _{3} .
The filling of N _{3 is} rewritten in N _{1} , and the filling of N _{4 is} rewritten in N _{2} , while the filling of N _{3} , N _{4 is} preserved.
Filling N _{1} and N _{2 is} encrypted in the simple replacement mode in accordance with the requirements of clause 3.1. The filling N _{1} , N _{2} obtained as a result of encryption forms the first 64-bit block of the cipher scale G _{w}^{(1)} , which is summed bitwise modulo 2 in the adder CM _{5} with the first 64-bit open data block T _{0}^{(1)} = (t _{1}^{(1)} , t _{2}^{(1)} , ..., t _{63}^{(1)} , t _{64}^{(1)} ). As a result of the summation, a 64-bit block of encrypted data is obtained: T _{w}^{(1)} = (τ _{1}^{(1)} , τ _{2}^{(1)} , ..., τ _{63}^{(1)} , τ _{64}^{(1)} ).
The value of τ _{1}^{(1) of the} block T _{w}^{(1)} is the result of the summation modulo 2 in the CM _{5 of the} value t _{1}^{(1)} from the block T _{0}^{(1)} with the value of the 1st digit N _{1} , the value τ _{2}^{(1) of the} block _{Tm}^{(1)} is the result of summing modulo 2 in CM _{5 the} value t _{2}^{(1)} from the block T _{0}^{(1)} with the value of the 2nd digit N _{1} , etc., the value of τ _{64}^{(1) of the} block T _{w}^{(1)} is the result of the summation modulo 2 in CM _{5 of the} value t _{64}^{(1)} from the block T _{0}^{(1)} with the value of the 32th digit N _{2} .
To obtain the next 64-bit block of the cipher scale G _{w}^{(2), the} filling N _{4 is} summed modulo (2 ^{32} -1) in the adder SM _{4} with the constant C _{1} of N _{6} , the filling N _{3 is} summed modulo 2 ^{32} in the CM _{3} adder with a constant C _{2} of N _{5} . The new filling N _{3 is} rewritten in N _{1} , and the new filling N _{4 is} rewritten in N _{2} , while the filling of N _{3} and N _{4 is} preserved.
Filling N _{1} and N _{2 is} encrypted in the simple replacement mode in accordance with the requirements of clause 3.1. The filling N _{1} , N _{2} obtained as a result of the encryption forms the second 64-bit block of the cipher gamma Gw ^{(2)} , which is summed digitally modulo 2 in the adder CM _{5} with the second block of open data T _{0}^{(2)} . Likewise, the blocks of the gamut of the cipher are generated, T _{o}^{(3)} , T _{0}^{(4)} ..., T _{0}^{(M),} and the blocks of the open data are encrypted. If the length of the last M-th block of open data T _{0}^{(M) is} less than 64 bits, only the corresponding number of bits of the cipher scale is used from the last Mth block of the cipher gamma Gm ^{(M)} , the remaining bits are discarded.
Synchronization S and blocks of encrypted data Т _{ш}^{(1)} , Т _{ш}^{(2)} ..., Т _{ш}^{(М)} are transmitted to the communication channel or computer memory.
Decryption of encrypted data in the gamma mode
When decrypting, the cryptographic circuit has the same form as when encrypted (see Figure 3). 256 bits of the key are entered in the CMC, with the help of which the data T _{0}^{(1)} , T _{0}^{(2)} ..., T _{0}^{(M)} was encrypted, and T _{0}^{(M)} can contain less than 64 bits.
Gamming with feedback mode
Encryption of open data in gumming mode with feedback
A cryptogram that realizes a mode of gumming with feedback must have the form, shown in Figure 4.
Figure 4
The open data, divided into 64-bit blocks T _{0}^{(1)} , ..., T _{0}^{(M)} , is encrypted in the gaming mode with feedback by bit-wise summation modulo 2 in the CM _{5} adder with the cipher scale G r, which is generated by blocks on 64 bits, i.e. ^{(M)} ), where M is determined by the volume of the data being encrypted, r ^{(i)} is the i-th 64-bit block, i = 1 ÷ Ì. The number of bits in the block T _{0}^{(M)} can be less than 64.
256 bits of the key are entered in the CMU. In drives N _{1} , N _{2, a} 64-bit binary sequence (synchronization) is input S = (S _{1} , S _{2} , ..., S _{64} ). Synchronization is introduced in N _{1} and N _{2} so that the value of S _{1} is input to the 1st bit N _{1} , the value S _{2} is input into the 2nd bit N _{1} , etc., the value of S _{32} is input into the 32-bit N _{1} ; the value S _{33} is inputted to the 1st bit N _{2} , the value S _{34} is input to the 2nd bit N _{2} , etc., the value S _{64} is inputted to the 32-bit N _{2} .
Initial filling of drives N _{1} and N _{2 is} encrypted in the simple replacement mode in accordance with the requirements of clause 3.1. The resulting filling of N _{1} and N _{2} forms the first 64-bit block of the cipher scale, G _{w}^{(1)} , which is summed digitally modulo 2 in the adder CM _{5} with the first 64-bit open data block T _{0}^{(1)} = (t _{1}^{(1)} , t _{2}^{(1)} , ..., t _{63}^{(1)} , t _{64}^{(1)} ).
As a result of the summation, a 64-bit block of encrypted data is obtained: T _{w}^{(1)} = (τ _{1}^{(1)} , τ _{2}^{(1)} , ..., τ _{63}^{(1)} , τ _{64}^{(1)} ).
The block of encrypted data _{Tm}^{(1)} is also simultaneously the initial state N _{1} , N _{2} for generating the second block of the cipher scale G r ^{(2)} and is written back to the specified drives by feedback. In this case, the value of τ _{1}^{(1)} is introduced into the 1st bit N _{1} , the value of τ _{2}^{(1)} is introduced into the 2nd bit N _{1} , etc., the value of τ _{32}^{(1)} is introduced into the 32-th bit N _{1} ; The value of τ _{33}^{(1)} is introduced into the 1st bit N _{2} , the value of τ _{34}^{(1)} is introduced into the 2nd bit N _{2} , etc., the value of τ _{64}^{(1)} is introduced into the 32-th bit N _{2} .
Filling N _{1} , N _{2 is} encrypted in the simple replacement mode in accordance with the requirements of clause 3.1. The filling N _{1} , N _{2} obtained as a result of the encryption forms the second 64-bit block of the cipher gamma Gw ^{(2)} , which is summed digitally modulo 2 in the adder CM _{5} with the second block of open data T _{0}^{(2)} .
Generation of subsequent blocks of the cipher scale G _{w}^{(i)} and encryption of the corresponding blocks of open data T _{0}^{(i)} (i = 3 ÷ Ì) is performed analogously. If the length of the last M-th block of open data T _{0}^{(M) is} less than 64 bits, then only the corresponding number of digits of the cipher range is used from the G r ^{(M)} , the remaining bits are discarded.
Synchronization S and blocks of encrypted data Т _{ш}^{(1)} , Т _{ш}^{(2)} ..., Т _{ш}^{(М)} are transmitted to the communication channel or computer memory.
Decryption of encrypted data in a gumming mode with feedback
When decrypting, the cryptographic circuit has the same form as when encrypted (see Figure 4). In the CMU, 256 bits of the same key are entered, on which T _{0}^{(1)} , T _{0}^{(2)} ..., T _{0}^{(M)} were encrypted. Synchronization is introduced in N _{1} , N _{2} so that the value of S _{1} is introduced into the 1st bit N _{1} , the value S _{2} is input into the 2nd bit N _{1} , etc., the value of S _{32} is input into the 32-th bit N _{1} ; the value S _{33} is inputted to the 1st bit N _{2} , the value S _{34} is input to the 2nd bit N _{2} , etc., the value S _{64} is inputted to the 32-bit N _{2} .
The initial filling of drives N _{1} and N _{2} (synchronization S) is encrypted in the simple replacement mode in accordance with the requirements of clause 3.1. The resulting filling N _{1} , N _{2} forms the first 64-bit block of the cipher gamma Gw ^{(1)} , which is summed digitally modulo 2 in the adder CM _{5} with the encrypted data block T _{w}^{(1)} . As a result, the first block of open data T _{0}^{(1) is} obtained.
The block of encrypted data Т _{ш}^{(1)} is the initial filling N _{1} , N _{2} for generating the second block of the cipher scale Гш ^{(2)} . Block T _{w}^{(1) is} written in N _{1} , N _{2} . In this case, the value of τ _{1}^{(1)} is introduced into the 1st bit N _{1} , the value of τ _{2}^{(1)} is introduced into the 2nd bit N _{1} , etc., the value of τ _{32}^{(1)} is introduced into the 32-th bit N _{1} ; The value of τ _{33}^{(1)} is introduced into the 1st bit N _{2} , the value of τ _{34}^{(1)} is introduced into the 2nd bit N _{2} , etc., the value of τ _{64}^{(1)} is introduced into the 32-th bit N _{2} . The received filling N _{1} , N _{2 is} encrypted in the simple replacement mode in accordance with the requirements of clause 3.1, the resulting block G r ^{(2) is} summed bit by bit modulo 2 in the adder CM _{5} with the second block of encrypted data T _{w}^{(2)} . As a result, an open data block T _{0}^{(2) is} obtained.
Similarly, in blocks N _{1} , N _{2} , blocks of encrypted data T _{w}^{(2)} , T _{w}^{(3)} ..., T _{w}^{(M-1) are} successively recorded, from which in the simple replacement mode the blocks of the cipher gamma r ^{(3)}^{(4)} , ..., _{Γω}^{(Μ)} . The blocks of the cipher scale are summed digitally modulo 2 in the adder CM _{5} with blocks of encrypted data T _{w}^{(3)} , T _{w}^{(4)} ..., T _{w}^{(M)} , resulting in blocks of open data T _{0}^{(3)} , T _{0}^{( 4)} , ..., T _{0}^{(M)} , while the length of the last block of open data T _{0}^{(M)} can contain less than 64 bits.
Simulation mode
To provide an imitation protection of open data consisting of M 64-bit blocks T _{0}^{(1)} , T _{0}^{(2)} , ..., T _{0}^{(M)} , M≥2, an additional block of l bits is created (imitation I _{l} ). The simulation process is uniform for all encryption modes.
The first block of open data is T _{0}^{(1)} = (t _{1}^{(1)} , t _{2}^{(1)} , ..., t _{64}^{(1)} ) = (a _{1}^{(1)} (0), a _{2}^{(1)} (0) (0), b _{2}^{(1)} (0), ..., b _{32}^{(1)} (0)) is written to the storage rings N _{1} and N _{2} , the value t _{1}^{(1)} = a _{1}^{(1)} (0) is introduced into the 1st bit N _{1} , the value t _{2}^{(1)} = a _{2}^{(1)} (0) is introduced into the 2nd bit N _{1} , etc., the value of t _{32}^{(1)} = a _{32}^{(1)} (0) is entered in the 32-th bit N _{1} ; The value of t _{33}^{(1)} = b _{1}^{(1)} (0) is entered in the 1st bit N _{2} , etc., the value t _{34}^{(1)} = b _{32}^{(1)} (0) is introduced into the 32nd digit N _{2} .
Filling N _{1} and N _{2} undergoes a transformation corresponding to the first 16 cycles of the encryption algorithm in the simple replacement mode, in accordance with the requirements of clause 3.1. In the CMU, the same key is used to encrypt the blocks of open data T _{0}^{(1)} , T _{0}^{(2)} , ..., T _{0}^{(M)} into the corresponding blocks of the encrypted data T _{w}^{(1)} , T _{w}^{(2)} , ..., _{Tm}^{(M)} .
The filling of N _{1} and N _{2} obtained after 16 work cycles, having the form ( _{1 1}^{(1)} (16), a _{2}^{(1)} (16), ..., a _{32}^{(1)} (16), b _{1}^{(1)} ( 16), b2 ^{(1)} (16), ..., b32 ^{(1)} (16)) is summed in CM _{5} modulo 2 with the second block T _{0}^{(2)} = (t _{1}^{(2)} , t _{2}^{( 2)} , ..., t _{64}^{(2)} ). The summation result is recorded in N _{1} and N _{2} and is subjected to a transformation corresponding to the first 16 cycles of the encryption algorithm in the simple replacement mode.
The resulting filling N _{1} and N _{2 is} summed in CM _{5} modulo 2 with the third block T _{0}^{(3)} , etc., the last block T _{0}^{(M)} = (t _{1}^{(M)} , t _{2}^{(M)} , ... , t _{64}^{(M)} ), optionally padded to zero with a 64-bit block, is summed in CM _{5} modulo 2 with the filling N _{1} , a _{1}^{(M-1)} (16), and _{2}^{(M-1)} ( 16), ..., _{32}^{(M-1)} (16), b _{1}^{(M-1)} (16), b _{2}^{(M-1} ) . The summation result is entered in N _{1} , N _{2} and is encrypted in the simple replacement mode for the first 16 cycles of the algorithm operation. From the obtained filling of the storage rings N _{1} and N _{2, we} choose the segment I _{l} = [a _{32- l + 1}^{(M)} (16), and _{32- l + 1}^{(M)} (16), ..., a _{32}^{(M)} (16 )].
Imitovlyavka AND _{l} is transmitted via the communication channel or to the computer memory at the end of the encrypted data, i.e. _{Tm}^{(1)} , _{Tm}^{(2)} , ..., _{Tm}^{(M)} , and _{l} .
The received encrypted data T _{w}^{(1)} , T _{w}^{(2)} , ..., T _{w}^{(M) are} deciphered, an imitation is generated from the obtained blocks of open data T _{0}^{(1)} , T _{0}^{(2)} , ..., T _{0}^{(M)} And ^{'}_{l} , which is then compared with imitation I1, obtained together with the encrypted data from the communication channel or computer memory. In case of mismatch of imitations, the obtained blocks of open data T _{0}^{(1)} , T _{0}^{(2)} , ..., T _{0}^{(M) are} considered false.
The value of the parameter l (the number of bits in the imitative) is determined by the current cryptographic requirements, taking into account that the probability of imposing false data is 2 ^{- l} .
Comments
Commenting on, remember that the content and tone of your message can hurt the feelings of real people, show respect and tolerance to your interlocutors even if you do not share their opinion, your behavior in the conditions of freedom of expression and anonymity provided by the Internet, changes not only virtual, but also the real world. All comments are hidden from the index, spam is controlled.