This page has been robot translated, sorry for typos if any. Original content here.

Breaking the subway (travel cards) + CRYPTOGRAPHIC TRANSFORM ALGORITHM IN ACCORDANCE WITH GOST 28147-89

On the page:


Breaking the subway (travel cards)

Are you familiar with the desire to solve all the riddles and reveal all the defenses of the Moscow Metro? For example, to make yourself a "perpetual ticket"? But after all, metro experts are constantly finding more and more sophisticated methods of protection. Metal tokens were replaced by plastic ones, which, in turn, were magnetic tickets, and contactless cards replaced magnetic ones. Many researchers have dropped their hands - it seems that the Metropolitan has become an impregnable fortress. But any protection can be circumvented. And often, it turns out to be many times easier to open than to build ...

How it all began

I had an interest in subway systems a long time ago, one might say, from school, when there were still tickets with a magnetic strip in progress. At the same time (about a decade ago) they introduced a contactless social card for students. I became interested in what it is and how it works. But in those days I didn’t have enough skills, and there was little public information, especially on these technologies. I had to postpone the idea of ​​research on the back burner, but I promised myself that I would definitely return to it ...

About three years ago my interest in the topic of the subway woke up again. I actively studied magnetic tickets (there was plenty of information on this topic on the Internet) and even collected a small machine for making duplicates of two heads from reel-to-reel tape recorders and a small amount of loose. I did not forget about my social card (already student). But after studying the documentation, it became clear to me that the system is practically 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, hacking it so simply will not work, and you can touch the keys until the end of the solar system. And for the Cardholders who support Classic, they were worth some very heavy money for that time (I didn’t think about Ebay, alas). Interest in magnetic tickets quickly cooled, and the social card had to be postponed again until better times.

Meet: "Ultralight"

Tickets "Ultralight" appeared in our subway recently, but immediately caused a great interest among the public. They began to kill, tear, put up with an iron and use other methods of thermorectal cryptanalysis. Admittedly, the thirst for knowledge made me tear a couple. As a result of their study and searches on the Internet, it was established that this is nothing more than Mifare Ultralight, the “lightweight” compatible version of Mifare Classic. A quick review of the documentation on the chips of this standard made it clear that these cards do not have embedded security systems. On top of that, I attacked an article detailing the successful hacking of a similar transport system by Dutch students. All together pushed me to new research.

Go!

To begin with, of course, it was just necessary to get somewhere a wireless card reader that supports Ultralight. There were two options: either to assemble oneself (which would take a lot of time), or to buy a ready-made device. At the thought of the second option, bearing in mind the prices of three years ago, I had goose bumps. But I still decided to look at current prices. And for good reason! 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 - 4,000 ruble.

Of course, not a little, but on the other hand, it is not 10,000; Moreover, the purchase of a ready-made reader made it possible to immediately concentrate on researching tickets, and not on designing and debugging iron, which could be delayed indefinitely. Together with the reader, a very convenient original SDK of local production was purchased from the same company (ISBC). Again, he allowed not to waste time and effort on writing low-level and debugging software work with the reader, but to concentrate directly on the tickets. So, for a couple of days of leisurely coding, a small program was born, with which it was possible to observe and edit the entire internal structure of the Ultralights in a convenient form. Then I began to study tickets.

Blank wall

In the process of studying a lot of tickets went through my reader. Some, I rolled up my sleeves, took out “out of the garbage”, some I bought - I looked at what was written to them, then I went and looked again. These were almost all types of tickets, with the possible exception of the Ultralight pass for 70 trips. After a couple of weeks, I had 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 got a few dumps of two different temporary uniform social tickets (one was issued for a period of 5 days, the other for 30), taken after a certain time interval. It turned out to be very interesting specimens, and at the same time very rare (I got them firsthand with immediate return, only to “read”).

In fact, it is almost the only type of "Ultralight", which works not only in the subway, but also on ground transportation. Moreover, only this type of tickets has no limit on the number of trips. Subsequently, it was they who served me a great service ... I gathered this whole zoo for one purpose - to clearly define the structure and format of the data recording on the ticket. Of course, some fields were visible immediately, with the naked eye, but some were not. For example, I did not immediately understand where the subway ticket number is written (the one that is printed on it). Awareness came quite by accident. The fact is that I (like, I think, most of us), looking at the hex, used to align the information for themselves on bytes and to think at least bytes. It turned out that this approach is wrong here. Looking at the ticket dump, you need to think in smaller units - tetrads, and sometimes bits. I understood this when I finally saw the ticket number - it was shifted to 4 bits relative to the start of the byte, and the remaining 4 bits from that and the other side of the number were occupied by other service information. After some time, the format for recording data on tickets became almost completely clear.

It became obvious where and how all dates, counters, identifiers are stored. There remained only a couple of fields, the purpose of which was unclear simply because the data in them were the same from dump to dump. But that was the end of all the joy - it would be foolish to assume that such tickets could be left unprotected. Each dump had 32 bits of different information that did not correlate with the rest of the contents. I assumed it was a kind of checksum, a “hash” of the data recorded on the ticket. All attempts to estimate or calculate these 32 bits turned out to be a complete failure (in particular, there was an assumption that this was some kind of CRC32, with a non-standard polynomial and starting value).

In an attempt to change at least one and a half bits of information inside the ticket, the checkout terminal in the subway displayed the “BAD TICKET”, weighing the last nails into the coffin with a weighty jack. Of course, there were attempts to circumvent the system in other ways, for example, to try to copy a ticket to a blank one-to-one card (here, alas, prevented the factory serial, which, as it turned out, also participated in the generation of the hash) or set the lock bits as to prevent the turnstile from modifying the contents of the ticket. The test terminal recognized such an “eternal” ticket, but refused to let the turnstile go… So I ran into the wall. In the big, strong concrete wall, on which many have the habit of killing off. Not finding any information on the forums and boards, I decided that my research was completed on this - there were no more ways, and I put the bullet. As it turned out, nothing ...

Strange acquaintance

September evening was no different from others. The night was almost here, it was cool and damp outside. I sat in front of the monitor screen, and, drinking warm, slightly sweet green tea, peacefully parted a fee for my next crafts. DipTarce, a little bashorga, ICQ ... Someone called on Skype - distracting! Again ICQ, again DipTrace - in general, everything is as usual. Once again, the ICQ window fell out to the foreground - someone unknown to me, wrote “Hello”. I, without a doubt, answered the same. The following message was a turning point in the whole story: “You are interested in the subway, I have some stuff here. If you're interested, let's meet, I'll tell you. ” At first I was a little embarrassed and alerted (maybe a divorce or a setup, or maybe the “special services” became interested - the paranoia takes its toll), but then I thought: why not?

Intelligence agencies would hardly have become interested in me, and there seems to be no ground for divorce, and even more so for the setup. After a short conversation, we agreed to meet in the afternoon, in the center of the hall of one of the stations of the Moscow metro. 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 package with the words: “On, hold. It still didn’t work for me, it might be useful for you. ” Looking inward, I saw two metro terminals, shifted by newspapers, a few randomly scattered white plastic cards and a blank in a box. On my question about how much I owe (money) for it, the guy shook his head, smiled and said: “Why, no one owes anything to anyone, do it ... So, I already have to run, my train is like time! OK Bye!".

With these words, he ran away, jumped into the already closing doors of the carriage and left. And I, I confess, went home a little in neponyatka. I deleted the contact from ICQ just in case, at the same time cleaning the contact list on the server and tidying up the logs (hello again, paranoia). In the end, will write again, if that. But the more he never wrote to me ...

The phenomenon of software to the people

Arriving home, I dismantled the package. The second terminal turned out to be a bus validator (heavy, damn it!); the cards were Mifare Classic 1K (clean), and there was a single archive on the disk. After a quick acquaintance with the contents, it turned out - this is the software that is used at the ticket offices of the metro. Putting aside the terminal and the validator, I decided to come to grips with 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. It took another hour to sort out its structure. Having combed all the ini-files (with comments, kindly left by the developer), I already had a complete idea of ​​what it is, how it works and what it eats with. Eating, as it turned out, with the reader Parsec PR-P08, therefore, in the absence thereof, it was not possible to try the software in action.

The developer was Smartek, a major government contractor developing systems of this kind (more information can be found 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's with speaking names (this was the most important development file of the developers). After a cursory analysis of the internal software, I found out that, firstly, information about all issued tickets is transferred to a centralized database (by the way, this is Oracle) and, secondly, the program uses some kind of 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, it gives us a head start.

But first of all, I was interested in the key mechanism (I already started to guess about why it might be needed). So, I took 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, except for the file with the keys, no longer looks like anything). And enjoyed all this good runtime-bpl'ina SmLayout.bpl. This library was just a godsend for my research - it contained classes for working with the internal filling of tickets. Since this is runtime-bpl, then it was enough just to look at its export table, in order to understand by 60 percent what was happening. More detailed analysis put everything in its place. Remember, at the beginning of the article I said that in the structure of the "Ultralight" there were still a few fields, the purpose of which was not clear?

One of these fields is the so-called “layout identifier”. In fact, all metro tickets are built from a fixed header and a variable part of the data. So, this “Layout” field in the header just defined how and what data is located in the rest of the ticket. There are several such layouts (each for their own type of ticket), and in SmLayout.bpl each of them had its own class (plus the general parent class, which had methods for working with the header part). Therefore, it was easy to figure out which fields in each layout they are responsible for (even with the names of the methods in export!). Having finished all of the entire Layout 8 (which is used in the “Ultralights”) and having rechecked whether I had the right idea about all the fields in the ticket structure, I took up the key mechanism. Indeed, he was responsible for generating 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 designed so that each type of ticket has its own identifier (there was a complete table with identifiers and ticket names, in the form of a text file with comma-separated values). It consists of a zone identifier (application) and a map type identifier. So, based on these numbers, keyring is selected in the key file, within which there may already be several keys (in case a new key is entered and the old tickets are still in use). The new ticket is recorded using the first one, and the validity check is done using all keys in the keyring. Next, the selected key is decrypted using CryptKeyRef.dll (why they are stored encrypted, I won’t attach my mind). After that, the decrypted key and almost all ticket data, as well as its hardware serial number and number (the hash generation method specified for keying in keys.d) are transferred to the ckCalcHashCode function located in the same CryptKeyRef.dll. At the exit, we get the value on which I once “stuck” - the same “hash”. Of course, I wrote a small program that, using these functions from CryptKeyRef.dll and the keys.d file, could check and, in which case, recalculate the “hash” inside any dump. I rechecked everything on several dumps, and, having received a positive result, left, satisfied, to sleep.

Rotten keys

Despite the theoretical success, I wanted to check everything, so to speak, “in battle”. The next day, returning from work, I deliberately bought a fresh “Ultralight” for one trip to see if my keys were valid or not (apparently, they were old). You could, of course, immediately try to write down the “fabricated” “Ultralight” and go check it out, but at that time I ran out of empty cards, and it was a bit scary to go “randomly” - what if? When I got home, the first thing I did, without even washing my hands, eagerly rushed to check the fresh ticket with my own keys. And then I was waiting for a big bummer - the “hash” recorded in the ticket did not pass through any of the keys. Therefore, the keys are really rotten and they have been replaced by new ones. This completely crossed all my labors. I felt a little sad. I brewed green tea, played the piano a little (yes) and sat down to raise my unfinished fee ...

All is not lost

The idea came to me unexpectedly, when I once again for some reason looked into the file with the keys. I noticed that in the "running" keyring (which is used to calculate 1-, 2-, 5-train 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 keyring in which there was only one key. Previously, I did not pay attention to him, and concentrated on the "running." To calculate which tickets this key is used, I did not know. When I looked, what kind of ticket is tied to the keyring, then I had a small spark of hope. The fact that this type of ticket was - WESB. Yes, that rare type of ticket is a temporary ticket 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 ground transportation, where it is very difficult and long to replace it with a new one.

In addition, the key in the keyring is only one, which indirectly confirmed my guess. In addition, I remembered that when I cleaned the metro program from various “garbage”, there was something similar to an archive of old key files. Having dug out and opened the original archive, I saw that this was indeed the case. And most importantly, after reviewing all the old key files, I discovered that it was this key that remained unchanged! Already without a single drop of doubt, I riveted my own VESB (fortunately, I had dumps of this type, which at times simplified the task - I just changed the dates and number in the dumps), and calculated the hash using this key. So, it is time to check (especially since I just bought some more clean plastic). Entering the lobby, I first attached my “ticket” to the test terminal. The display showed the validity of the ticket, which I indicated, and the green LED came on. So it works. Having made a grimace simpler and hiding the white plastic in the sleeve, I went to the turnstile, put my hand to the validator and ... calmly passed on to the green green light-emitting fire. This marked the final victory.

And what next?

And then the experiments began, during which many interesting things were discovered. For example, on such a "left" VESB can walk only two or three days. The fact is that the number that I indicate “from the bald” inside the ticket is stored in the memory of the head of the turnstile with each pass, and after some time it is sent along with the others to the data center. There, the system does not find the actually issued ticket with such a number and puts it in the stop list, which is then sent to all the turnstiles of the metro. And this should be the case with all types of tickets, not only with VESB - in addition to the “hash” and frequently changing keys, this is a very good protection. To bypass it, for obvious reasons, is not possible.

It was also noted that setting or not setting the lock bits does not matter whether the ticket will work or not. The only exception is the blocking bit of the OTP zone, which the turnstile apparently always checks, even though it is not going to write to the OTP. Later I took the metro and bus terminals, put them in order, studied and launched on the stand. Now, in order to check the next guess, it was no longer necessary to run with the newly-baked mutant ticket in the subway, and it became possible to check them “without departing from the ticket office”. Moreover, the subway terminal turned out to be the same old (everything else is buggy), just like my keys. So I could try “in work” and any other types of “Ultralight” tickets - something that I can never do “live” on the subway. In parallel with these experiments, I continued to engage in software.

Since there was a lot of controversy about what kind of algorithm is used in calculating 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 this is - something well-known or some kind of its own, internal development. Along the way, I was visited by many different thoughts (including that it could be AES), but when I studied the already working code in detail without using Smart Library libraries, it turned out that this algorithm is “only” GOST — a domestic encryption standard (all the necessary information about him you can easily find on the web). Specifically, the 16-W cycle was used to calculate the hash. "Hash", in fact, is nothing more than an imitation of GOST.

The structure of the information recorded on the ticket "Ultralight"

What is the page, where and how are the hardware serial number, the lock bits and the OTP zone located, you can read the original documentation (a PDF specification file with a full chip description is on the disk). I recommend to start learning from it. I will describe the structure of the location of the data generated by the metro systems in the user area available for reading and rewriting (in the absence of locks, of course). The entire contents of the ticket can be divided into the header part and the two completely duplicate parts of the data (this is done for the purpose of reservation and protection against errors). The heading part of the tickets "Ultralight" begins on page 4. Part of it is the same in structure in all tickets and identifiers of the Metropolitan system and MosGoTrans. The first 10 bits are the application identifier; the next 10 bits are the card type identifier (what identifiers can be, you can read in another special box for this purpose). After the identifiers is located the serial number of the ticket (it is stamped on the back of the ticket, do not confuse it with the hardware - these are two different things!) 32 bits in size. The last 4 bits are the Layout field, which tells the system how to interpret the subsequent data (something like a file format).

For Ultralight tickets, the Layout value is 0x08. At the same part of the title ends. Further, the ticket "Ultralight" indicates the date on which the form is valid (16 bits). All dates in the system are specified in the format of the number of days since January 1, 1992. Here the header part of the “Ultralight” ticket ends (in tickets with another Layout various additional information can still be recorded). 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 is specified in days (from the moment of issue) - 8 bits. The first 16 bits of page 9 is the trip counter. It can be either decreasing to zero (in all tickets with a limited number of trips), or increasing from zero (in VESB tickets, without limiting the number of trips). After the counter in the rest of the page, the turnstile with each pass enters its unique identifier. Apparently, this is used to prevent re-entry without waiting for the VESB ticket (turnstiles in the lobby are connected to the network and interrogate each other), and also to be able to see which turnstile went through (for example, in case of an error or for statistics ). Page 10 is fully 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 in normal operation, these two areas always contain the same data. Separately, it should be said about using the system OTP zone. It is used for the gradual “burning out” of a ticket with each trip (this is not the case for VESB tickets). The two lowest bits are set when the ticket is canceled or canceled (by stop list). A canceled ticket cannot be restored. Only 30 bits are left for burning out. This zone is represented by the system as 100% of trips. With each new trip a certain number of bits is set (from the youngest to the oldest), corresponding to how many percent one trip takes. For example, for a 5-train ticket, each new trip will be “burned out” by 6 bits, and for a 60-train ticket, half a bit (rounded up). It is worth mentioning that the reuse of Ultralight tickets is impossible not only because of the OTP burning out, but also due to the fact that at the ticket office when issuing a ticket (and perhaps even when it is made) almost all pages are blocked for rewriting. . Thus, neither “reload” nor change the type of ticket to another will not work.

Examples of Metro Ticket IDs Used

All numbers are in decimal notation!

Application IDs:

  • 262 - Moscow Metro ticket.
  • 264 - Moscow Ground Transportation Ticket.
  • 266 - Unified Social of Moscow and Moscow Region.
  • 270 - Ticket "Easy Metro".

Identifiers of the type of tickets "Ultralight":

  • 120 - One ride.
  • 121 - Two trips.
  • 126 - Five trips.
  • 127 - Ten rides.
  • 128 - Twenty rides.
  • 129 - Sixty trips.
  • 130 - Luggage + Passage.
  • 131 - Luggage only.
  • 149 - Single "Ultralight" (70 trips).
  • 150 - VESB.

Mifare classic

I did not ignore the ill-fated Mifare Classic 1K in my research. As you understand, the main keys to the “Classics” were the hardware keys A and B. By luck, these keys lay in one of the modules of the program in open form (preved to the developers!) And it was not difficult for me to write a small program for work with the contents of these cards using the keys obtained. In the course of the experiments, some interesting features were revealed, such as: the metro for storing the ticket uses the first sector of the map, and ground transportation - the fourth; no protection, except for hardware keys (which, being recorded in software in this form, most likely, have never changed at all since the system was commissioned) does not exist on these tickets.

Instead, CRC-16 is indicated at the end of each block, simply to protect data from damage. In addition, on social cards, in addition to tickets, a lot of diverse and interesting information is also recorded. For example, in the 13th and 14th sectors of social cards are given the surname, name and patronymic of the owner. This (and some other) data can be read using the public key 0xA0A1A2A3A4A5. During the experiments, it was possible to completely clone the student SCM, as well as several tickets to the net Classic cards.

But as it turned out, the stop-list system perfectly saves cloning - such a ticket can be used for no more than two days, then it is canceled (although, unlike Ultralit, the Classic card can be restored after cancellation, but from the stop list it will not save). Since no protection was used on Classic cards, they quickly became uninteresting to me, and I decided to concentrate on the research of Ultralight.

The End, or To Sum Up

Metro systems, and in particular, the new Ultralight tickets, contrary to opinions and conjectures, turned out to be well protected. Very pleased that the developers used reliable and time-tested GOST, and did not reinvent the wheel. With such protection, it is simply impossible to falsify the Ultralight ticket without having access to confidential data (key information). The key system and stop list mechanism are also well thought out. Of course, not without flaws and errors. The biggest of them is software that is not protected at all.

It was enough to abandon the use of runtime-bpl, and this would make analysis difficult dozens of times! Alternatively, the processing of particularly important parts of the program by AsProtect or ExeCryptor, followed by packing all the files with MoleBox, would reduce the possibility of analysis to almost zero. The toolkit is inexpensive. And the use of good (preferably, little known or made to order) protection of this kind, but with hardware keys would make the analysis of the program completely impossible. Of course, the Metropolitan is a regime enterprise, but one should not forget about the human factor. After all, Kevin Mitnick said (and not only spoke, but also demonstrated by example, for which he sat), that sometimes it is easier and more effective to use “social engineering” to achieve the goal than to try to break the impenetrable defense. Well, on this note I will finish my story. And to you, the reader, I wish you more interesting and successful research!








Description of the cryptographic transformation algorithm in accordance with GOST 28147-89

This standard establishes a unified algorithm for cryptographic transformation for information processing systems in networks of electronic computers (computers), individual computer complexes and computers, which determines the rules for data encryption and generation of imitations.

The algorithm of cryptographic transformation is intended for hardware or software implementation, satisfies the cryptographic requirements and in its capabilities does not impose restrictions on the degree of secrecy of the protected information.

The standard is mandatory for organizations, enterprises and institutions that use cryptographic protection of data stored and transferred in computer networks, in separate computing systems or in computers.

Block diagram of the cryptographic transformation algorithm

The block diagram of the cryptographic transformation algorithm (crypto scheme) shown in Figure 1 contains:

  • - key memory (256 bits), 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 drives (N 1 , N 2 , N 3 , N 4 );
  • - two 32-bit drives (N 5 , N 6 ) with С 2 , С 1 filling constants recorded in them;
  • - two 32-bit adders modulo 2 32 (CM 1 , CM 3 );
  • - 32-bit adder of bitwise sum modulo 2 (CM 2 );
  • - 32-bit modulo adder (2 32 -1) (CM 4 );
  • - adder modulo 2 (CM 5 ), the limit on the width of the adder CM 5 is not imposed;
  • - substitution unit (K);
  • - the cyclic shift register for eleven steps in the direction of the senior digit (R).

Picture 1.

The substitution block K consists of eight replacement nodes K 1 , K 2 , K 3 , K 4 , K 5 , K 6 , K 7 , K 8 with 64-bit memory each. The 32-bit vector arriving at the substitution block is divided into eight successive 4-bit vectors, each of which is converted into a 4-bit vector by the corresponding replacement node, which is a table of sixteen lines containing four filling bits in a line. The input vector determines the address of the row in the table; filling in this row is the outgoing vector. Then the 4-bit output vectors are sequentially combined into a 32-bit vector.

With the addition and cyclic shift of binary vectors, the highest digits are considered to be bits of drives with large numbers.

When writing the key (W 1 , W 2 , ..., W 256 ), W q Є {0,1}, q = i ÷ 256, â KZU, the value of W 1 is entered into the 1st bit of drive X 0 , the value of W 2 is entered in the 2nd digit of the drive X 0 , ..., the value W 32 is entered into the 32nd digit of the drive X 0 ; the value of W 33 is entered into the 1st digit of drive X 1 , the value of W 34 is entered into the 2nd digit of drive X 1 , ..., the value of W 64 is entered into the 32nd digit of drive X 1 ; the value of W 65 is entered into the 1st bit of the drive X 2 , etc., the value of W 256 is entered into the 32nd bit of the drive X 7 .

When overwriting information, the contents of the pth digit of one drive (adder) is rewritten into the pth digit of another drive (adder).

The value of the constant filling With 1 (constant) drive N 6 are given in table 1.

Table 1

Drive discharge N 6

32

31

thirty

29

28

27

26

25

24

23

22

21

20

nineteen

18

17

Value of discharge

0

0

0

0

0

0

0

one

0

0

0

0

0

0

0

one

Drive discharge N 6

sixteen

15

14

13

12

eleven

ten

9

eight

7

6

five

four

3

2

one

Value of discharge

0

0

0

0

0

0

0

one

0

0

0

0

0

one

0

0

The value of the constant filling With 2 (constant) drive N 5 are given in table 2.

table 2

Drive discharge N 5

32

31

thirty

29

28

27

26

25

24

23

22

21

20

nineteen

18

17

Value of discharge

0

0

0

0

0

0

0

one

0

0

0

0

0

0

0

one

Drive discharge N 5

sixteen

15

14

13

12

eleven

ten

9

eight

7

6

five

four

3

2

one

Value of discharge

0

0

0

0

0

0

0

one

0

0

0

0

0

0

0

one

The keys that determine the occupancy of the CZU and K substitution block tables are secret elements and are delivered in the prescribed manner.

The filling of the tables of the K substitution block 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 a KZU) in the simple replacement mode and encrypting them in the simple replacement mode with providing imitation protection for transmission over communication channels or storage in the computer memory.

The crypto scheme provides four types of work:

  • - encryption (decryption) of data in the simple replacement mode;
  • - encryption (decryption) of data in the gamming mode;
  • - Encryption (decryption) of data in gamming with feedback;
  • - mode of production of imitovstavka.

Simple Replacement Encryption

Encrypt open data in easy-swap mode

A cryptographic scheme that implements an encryption algorithm in the simple replacement mode should have the form shown in Figure 2.


Figure 2

Open data to be encrypted is divided into blocks of 64 bits each. Enter any block T 0 = (a 1 (0), a 2 (0), ..., a 32 (0), b 1 (0), b 2 (0), ..., b 32 (0)) binary information in drives N 1 and N 2 are produced so that the value of a 1 (0) is entered into the 1st digit of N 1 , the value of a 2 (0) is entered into the 2nd digit of N 1 , etc., the value of a 32 ( 0) is entered in the 32nd category of N 1 ; the value of b 1 (0) is entered into the 1st digit of N 2 , the value of b 2 (0) is entered into the 2nd digit of N 2 , etc., the value of b 32 (0) is entered into the 32nd digit of N 2 . The result is the state (a 32 (0), a 31 (0), ..., a 2 (0), a 1 (0)) drive N 1 and the state (b 32 (0), b 31 (0), ... , b 2 (0), b 1 (0)) of drive N 2 .

In the KZU enter 256 bits of the key. The contents of eight 32-bit drives X 0 , X 1 , ..., X 7 has the form:

  • 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 64-bit open data encryption algorithm 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 filling of the accumulator N 1 is preserved.

The result of the summation is transformed in the substitution block K and the resulting vector is fed to the input of the register R, where it cyclically shifts by eleven steps in the direction of the higher digits. The result of the shift is summed bitwise modulo 2 in the CM 2 adder with 32-bit filling of the N 2 accumulator. The result obtained in CM 2 is recorded in N 1 , while the old value of N 1 is rewritten in N 2 . The first cycle ends.

Subsequent cycles are carried out similarly, while in the 2nd cycle the filling of X 1 is read from the CPC, in the 3rd cycle the filling of X 2 is read from the CPC, and in the 8th cycle the filling of X 7 is read from the CPC. In the cycles from the 9th to the 16th, as well as in the cycles from the 17th to the 24th, from the CPC 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 order of reading the fillings of the KZU are 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 of selecting fillings of drives is performed:

  • 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 adder CM 2 is entered into the accumulator N 2 , and in the accumulator N 1 the old filling is preserved.

Obtained after the 32nd cycle of encrypting the filling of drives N 1 and N 2 are a block of encrypted data corresponding to a block of open data.

Decrypting Encrypted Data in Easy Replace Mode

A cryptographic scheme that implements a decryption algorithm in the simple replacement mode has the same form (see Figure 2) as during encryption. In the KZU enter 256 bits of the same key on which encryption was carried out. The encrypted data to be decrypted is divided into blocks of 64 bits each. Enter any block T W = (a 1 (32), and 2 (32), ..., and 32 (32), b 1 (32), b 2 (32), ..., b 32 (32)) in drives N 1 and N 2 is made so that the value of a 1 (32) is entered into the 1st digit of N 1 , the value of a 2 (32) is entered into the 2nd digit of N 1 , etc., the value of a 32 (32) is entered in the 32nd category of N 1 ; the value of b 1 (32) is entered into the 1st digit of N 2 , the value of b 2 (32) is entered into the 2nd digit of N 2 , etc., the value of b 32 (32) is entered into the 32nd digit of N 2 .

Decryption is performed according to the same algorithm as encryption of open data, with the change that the fillings of the drives X 0 , X 1 , ..., X 7 are read from the memory 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 7 , X 6 , X 5 , X 4 , X 3 , X 2 , X 1 , X 0 , X 7 , X 6 , X 5 , X 4 , X 3 , X 2 , X 1 , X 0 .

Obtained after 32 work cycles of filling drives N 1 and N 2 constitute a block of open data.

T 0 = (a 1 (0), a 2 (0), ..., a 32 (0), b 1 (0), b 2 (0), ..., b 32 (0)), corresponding to a block of encrypted data, the value of a 1 (0) of block T 0 corresponds to the contents of the 1st digit N 1 , the value of a 2 (0) corresponds to the contents of the 2nd digit N 1 , etc., the value a 32 (0) corresponds to the contents 32 n discharge number 1 ; the value of b 1 (0) corresponds to the contents of the 1st digit of N 2 , the value of b 2 (0) corresponds to the contents of the 2nd digit of N 2 , etc., the value of b 32 (0) corresponds to the contents of the 32nd digit of N 2 .

Similarly, the remaining blocks of encrypted data are decrypted.

Gamma mode

Encrypt open data in gamming mode

The crypto scheme that implements the gamming mode encryption algorithm should 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) , is encrypted in the gamma mode by bitwise modulating in the CM adder 5 with the gamut of cipher Г ш , which is produced in blocks of 64 bits, i.e.

Г ш = (Г ш(1) , Г ш(2) , ..., Г ш(М-1) , Г ш(М) ),

where M - is determined by the amount of encrypted data.

Г ш(i) is the i-th 64-bit block, i = 1 ÷ Ì, the number of binary digits in the T 0(M) block can be less than 64, while the part of the cipher from the G block (M) unused for encryption discarded.

In the KZU enter 256 bits of the key. A 64-bit binary sequence (synchro send) S = (S 1 , S 2 , ..., S 64 ) is introduced into the accumulators N 1 , N 2 , which is the initial filling of these drives for the subsequent generation of M cipher gamma blocks. Synchro send is entered into N 1 and N 2 so that the value of S 1 is entered into the 1st digit of N 1 , the value of S 2 is entered into the 2nd digit of N 1 , etc., the value of S 32 is entered into the 32nd digit N 1 ; the value of S 33 is entered into the 1st digit of N 2 , the value of S 34 is entered into the 2nd digit of N 2 , etc., the value of S 64 is entered into the 32nd digit of N 2 .

The initial filling of drives N 1 and N 2 (synchrophase S) is encrypted in the simple replacement mode in accordance with the requirements of paragraph 1.3.1. Результат зашифрования переписывается в 32-разрядые накопители N 3 и N 4 так, что заполнение N 1 переписывается в N 3 , а заполнение N 2 переписывается в N 4 .

Заполнение накопителя N 4 суммируется по модулю (2 32 -1) в сумматоре СМ 4 с 32-разрядной константой С 1 из накопителя N 6 , результат записывается в N 4 .

Заполнение накопителя N 3 суммируется по модулю 2 32 в сумматоре СМ 3 с 32-разрядной константой С 2 из накопителя N 5 , результат записывается в N 3 .

Заполнение N 3 переписывается в N 1 , а заполнение N 4 переписывается в N 2 , при этом заполнение N 3 , N 4 сохраняется.

The filling of N 1 and N 2 is encrypted in the simple replacement mode in accordance with the requirements of clause 3.1. Полученное в результате зашифрования заполнение N 1 , N 2 образует первый 64-разрядный блок гаммы шифра Г ш(1) , который суммируется поразрядно по модулю 2 в сумматоре СМ 5 с первым 64-разрядным блоком открытых данных Т 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) ).

Значение τ 1(1) блока Т ш(1) является результатом суммирования по модулю 2 в СМ 5 значения t 1(1) из блока Т 0(1) со значением 1-го разряда N 1 , значение τ 2(1) блока Т ш(1) является результатом суммирования по модулю 2 в СМ 5 значения t 2(1) из блока Т 0(1) со значением 2-го разряда N 1 и т.д., значение τ 64(1) блока Т ш(1) является результатом суммирования по модулю 2 в СМ 5 значения t 64(1) из блока Т 0(1) со значением 32-го разряда N 2 .

Для получения следующего 64-разрядного блока гаммы шифра Г ш(2) заполнение N 4 суммируется по модулю (2 32 -1) в сумматоре СМ 4 с константой С 1 из N 6 , заполнение N 3 суммируется по модулю 2 32 в сумматоре СМ 3 с константой С 2 из N 5 . Новое заполнение N 3 переписывается в N 1 , а новое заполнение N 4 переписывается в N 2 , при этом заполнение N 3 и N 4 сохраняется.

The filling of N 1 and N 2 is encrypted in the simple replacement mode in accordance with the requirements of clause 3.1. The resulting encryption filling N 1 , N 2 forms the second 64-bit block of the cipher code G W(2) , which is summed bitwise modulo 2 in the adder CM 5 with the second open data block T 0(2) . Similarly, blocks of the gamma cipher Gw(3) , Gw(4) ..., Gw(M) are generated and the open data blocks T 0(3) , T 0(4) ..., T 0(M) are encrypted. If the length of the last M-th block of open data T 0(M) is less than 64 bits, then from the last M-th block of the gamma cipher G W(M) , only the corresponding number of gamma cipher bits is used for encryption, the remaining bits are discarded.

Synchronous sending S and blocks of encrypted data T W(1) , T W(2) ..., T W(M) are transmitted to the communication channel or computer memory.

Decrypt encrypted data in gamming mode

When decrypting, a crypto scheme is the same as when encrypted (see Figure 3). In the KZU, 256 bits of the key are entered, with which the data T 0(1) , T 0(2) ..., T 0(M) was encrypted, while T 0(M) may contain less than 64 bits.

Gamma mode with feedback

Encryption of open data in gamming with feedback

A crypto scheme that implements the gamming mode with feedback should have the form shown in Figure 4.


Figure 4

Open data, divided into 64-bit blocks T 0(1) , ..., T 0(M) , is encrypted in gamming mode with feedback by a bitwise modulation modulo 2 in the CM 5 adder with a gamut of cipher G W , which is generated in blocks by 64 bits, i.e. Г ш = (Г ш(1) , Г ш(2) , ..., Г ш(М) ), where M - is determined by the amount of encrypted data, Г ш(i) is the i-th 64-bit block, i = 1 ÷ Ì. The number of binary digits in the block T 0(M) may be less than 64.

In the KZU enter 256 bits of the key. A 64-bit binary sequence (synchro send) S = (S 1 , S 2 , ..., S 64 ) is entered into the accumulators N 1 , N 2 . Synchro send is entered into N 1 and N 2 so that the value of S 1 is entered into the 1st digit of N 1 , the value of S 2 is entered into the 2nd digit of N 1 , etc., the value of S 32 is entered into the 32nd digit N 1 ; the value of S 33 is entered into the 1st digit of N 2 , the value of S 34 is entered into the 2nd digit of N 2 , etc., the value of S 64 is entered into the 32nd digit of N 2 .

The original 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 encryption filling N 1 and N 2 forms the first 64-bit block of the gamma cipher 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 block of encrypted data T b(1) is also the initial state N 1 , N 2 for generating the second block of the cipher cipher G (2) and, by feedback, is written to the indicated drives. The value τ 1(1) is entered into the 1st digit N 1 , the value τ 2(1) is entered into the 2nd digit N 1 , etc., the value τ 32(1) is entered into the 32nd digit N 1 ; the τ 33(1) value is entered into the 1st digit of N 2 , the τ 34(1) value is entered into the 2nd digit of N 2 , etc., the τ 64(1) value is entered into the 32nd digit of N 2 .

Filling N 1 , N 2 is encrypted in the simple replacement mode in accordance with the requirements of paragraph 3.1. The resulting encryption filling N 1 , N 2 forms the second 64-bit block of the cipher code G W(2) , which is summed bitwise modulo 2 in the adder CM 5 with the second open data block T 0(2) .

The development of subsequent blocks of the gamma cipher G W(i) and the encryption of the corresponding open data blocks T 0(i) (i = 3 ÷) is similar. If the length of the last M-th block of open data T 0(M) is less than 64 bits, then from G число(M) only the corresponding number of bits of the cipher gamma is used, the remaining bits are discarded.

Synchronous sending S and blocks of encrypted data T W(1) , T W(2) ..., T W(M) are transmitted to the communication channel or computer memory.

Decryption of encrypted data in gamming mode with feedback

When decrypting, the crypto scheme is the same as when encrypted (see Figure 4). In the KZU, 256 bits of the same key are entered on which T 0(1) , T 0(2) ..., T 0(M) were encrypted. Synchro send is entered into N 1 , N 2 so that the value of S 1 is entered into the 1st digit of N 1 , the value of S 2 is entered into the 2nd digit of N 1 , etc., the value of S 32 is entered into the 32nd digit N 1 ; the value of S 33 is entered into the 1st digit of N 2 , the value of S 34 is entered into the 2nd digit of N 2 , etc., the value of S 64 is entered into the 32nd digit of N 2 .

The initial filling of drives N 1 and N 2 (synchrophase S) is encrypted in the simple replacement mode in accordance with the requirements of clause 3.1. The resulting N 1 , N 2 encoding as a result of the encryption forms the first 64-bit block of the cipher code G W(1) , which is summed bitwise modulo 2 in the CM 5 adder with the encrypted data block T W(1) . The result is the first block of open data T 0(1) .

The block of encrypted data T ш(1) is the initial filling of N 1 , N 2 to generate the second block of the gamma cipher G 3 (2) . Block T W(1) is written in N 1 , N 2 . The value τ 1(1) is entered into the 1st digit N 1 , the value τ 2(1) is entered into the 2nd digit N 1 , etc., the value τ 32(1) is entered into the 32nd digit N 1 ; the τ 33(1) value is entered into the 1st digit of N 2 , the τ 34(1) value is entered into the 2nd digit of N 2 , etc., the τ 64(1) value is entered into the 32nd digit of N 2 . The resulting 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 W(2) is summed bitwise modulo 2 in the CM 5 adder with the second block of encrypted data T W(2) . The result is a block of open data T 0(2) .

Similarly, in N 1 , N 2 , the blocks of encrypted data T ((2) , T ((3) ..., T (M-1) are sequentially recorded, from which, in simple replacement mode, gamma blocks of the cipher G ((3) , D are produced w(4) , ..., G w(M) . The cipher gamma blocks are summed bitwise modulo 2 in the CM 5 adder with the encrypted data blocks of T m(3) , T m(4) ..., T m(M) , resulting in open data blocks T 0(3) , T 0( 4) , ..., T 0(M) , while the length of the last block of open data T 0(M) may contain less than 64 bits.

Mode of production

To provide 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 produced ( and the insertion I l ). The process of generating an imitation is uniform for all encryption modes.

The first block of open data T 0(1) = (t 1(1) , t 2(1) , ..., t 64(1) ) = (a 1(1) (0), a 2(1) (0) , ..., a 32(1) (0), b 1(1) (0), b 2(1) (0), ..., b 32(1) (0)) is recorded in drives N 1 and N 2 , the value of t 1(1) = a 1(1) (0) is entered into the 1st digit of N 1 , the value of t 2(1) = a 2(1) (0) is entered into the 2nd digit of N 1 , etc., the value t 32(1) = a 32(1) (0) is entered in the 32nd digit of N 1 ; the value of t 33(1) = b 1(1) (0) is entered into the 1st digit of N 2 , etc., the value of t 34(1) = b 32(1) (0) is entered into the 32nd digit N 2 .

The filling of N 1 and N 2 is subjected to 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. At the same time, in the KZU there is the same key with which the open data blocks T 0(1) , T 0(2) , ..., T 0(M) are encrypted into the corresponding blocks of encrypted data T ш(1) , T ш(2) , ..., T w(M) .

The filling of N 1 and N 2 obtained after 16 cycles of operation, having the form (a 1(1) (16), a 2(1) (16), ..., a 32(1) (16), b 1(1) ( 16), b 2(1) (16), ..., b 32(1) (16)), summed in CM 5 modulo 2 with the second block T 0(2) = (t 1(2) , t 2( 2) , ..., t 64(2) ). The result of the summation is entered in N 1 and N 2 and undergoes a transformation corresponding to the first 16 cycles of the encryption algorithm in the simple replacement mode.

The resulting filling of 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) ), if necessary supplemented to a full 64-bit block with zeros, is summed in CM 5 modulo 2 with filling N 1 , a 1(M-1) (16), a 2(M-1) ( 16), ..., a 32(M-1) (16), b 1(M-1) (16), b 2(M-1) (16), ..., b 32(M-1) (16) . The result of summation is entered in N 1 , N 2 and is encrypted in the simple replacement mode by the first 16 cycles of the algorithm. From the obtained filling of accumulators N 1 and N 2, we select the segment AND l = [a 32 - l +1(M) (16), a 32 - l +1(M) (16), ..., a 32(M) (16 )].

Imitovta AND l is transmitted over a communication channel or into computer memory at the end of the encrypted data, i.e. T w(1) , T w(2) , ..., T w(M) , and l .

Received encrypted data T w(1) , T w(2) , ..., T w(M) is decrypted, from the received open data blocks T 0(1) , T 0(2) , ..., T 0(M), the output is generated And l , which is then compared with the imitation AND l , obtained together with the encrypted data from the communication channel or computer memory. In case of a mismatch of the Imitters, the resulting open data blocks T 0(1) , T 0(2) , ..., T 0(M) are considered false.

The value of the parameter l (the number of binary digits in the simulator) is determined by the valid cryptographic requirements, taking into account that the probability of imposing false data is 2 - l .