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

Hacking the metro (travel cards) + ALGORITHM FOR CRYPTOGRAPHIC TRANSFORMATIONS ACCORDING TO GOST 28147-89

On the page:


Hacking the subway (travel cards)

Do you know the desire to solve all the riddles and open all the defenses of the Moscow Metro? For example, make yourself an “eternal ticket”? But after all, metro specialists are constantly finding increasingly sophisticated methods of protection. Metal tokens were replaced by plastic ones, those, in turn, by magnetic tickets, and contactless cards replaced magnetic ones. Many researchers dropped their hands - it seems as if the Metro has become an impregnable fortress. But any protection can be circumvented. And often, opening it is many times easier than building ...

How it all began

Interest in subway systems came to me a long time ago, one might say, from school, when there were still tickets with a magnetic strip. Then (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 didn’t have enough skills, and there was not much public information, especially about these technologies. I had to postpone the idea of ​​research for a long time, but I promised myself that I would definitely return to it ...

Three years ago, I again woke up interest in the subject of the subway. I actively studied magnetic tickets (there was plenty of information on this topic on the Internet) and even put together a small machine for making duplicates of two heads from reel tape recorders and a small amount of loose powder. I did not forget about my social card (already a student). But after studying the documentation, it became clear to me that the system is practically inaccessible - 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 sort through the keys until the end of the solar system. Yes, and the cardholders supporting Classic, at that time cost some unbearable money (I somehow did not think about Ebay, alas). Interest in magnetic tickets quickly cooled, and the social card had to be postponed again until better times.

Meet: Ultralight

Ultralight tickets appeared recently in our metro, but immediately aroused great interest among the public. They began to hammer, tear, stick up with an iron and apply other methods of thermorectal cryptanalysis. I must admit, a thirst for knowledge made me splurge a couple. As a result of their study and searches on the Internet, it was established - this is nothing like Mifare Ultralight, the “lite” compatible version of Mifare Classic. A quick look at the documentation for the chips of this standard made it clear that these cards do not have built-in 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!

For starters, of course, it was just necessary somewhere to get a wireless card reader that supports Ultralight. There were two options: either to assemble it 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 went goosebumps. But I still decided to see 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 is not 10,000; Moreover, the purchase of a ready-made reader made it possible to immediately focus on ticket research, and not on the design and debugging of iron, which could drag on indefinitely. Together with a reader from the same company (ISBC) a very convenient original local SDK was purchased. He, again, allowed not wasting time and energy on writing a low level and debugging software with a reader, but rather focusing directly on tickets. So, in a couple of days of unhurried coding, a small program was born, with the help of which it was possible to conveniently observe and edit the entire internal structure of Ultralight. 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, got out of the garbage, bought some - I looked at what was written on them, then I went through and looked again. These were tickets of almost all types, with the possible exception of the Ultralight ticket for 70 trips. After a couple of weeks, I 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 going in a row. My collection even got several dumps of two different temporary unified social tickets (one was issued for a period of 5 days, the other 30), shot after a certain time interval. These turned out to be very interesting specimens, and at the same time very rare (I got them first-hand with an immediate return, only to "read").

In fact, this is almost the only type of Ultralight that works not only in the subway, but also in land transport. In addition, only this type of ticket has no limit on the number of trips. Subsequently, it was they who served me a great service ... I collected this whole zoo with one purpose - to clearly determine the structure and format of data recording on the ticket. Of course, some fields were immediately visible with the naked eye, but some were not. For example, I did not immediately understand where the number of the metro ticket is recorded (the same one that is printed on it). Awareness came by accident. The fact is that I (as I think most of us), looking at the hex, used to align information for myself by bytes and think at least bytes. It turned out that this approach is incorrect here. Looking at a ticket dump, you need to think in smaller units - tetrads, and sometimes bits. I understood this when I finally “saw” the ticket number - it turned out to be shifted by 4 bits relative to the beginning of the byte, and the remaining 4 bits from both sides of the number were occupied by other official information. After some time, the format for recording data on tickets became almost completely understood.

It became obvious where and how all dates, counters, identifiers are stored. Only a couple of fields remained, the purpose of which was unclear simply because the data in them was the same from dump to dump. But that was all the joy and ended - it would be foolish to assume that such tickets can leave unprotected. Each dump contained 32 bits of various information that did not correlate with the rest of the content. I suggested that this is 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 is some kind of CRC32, with a non-standard polynomial and a starting value).

When trying to change at least one and a half bits of information inside the ticket, the check terminal in the metro highlighted “BAD TICKET”, pounding the last nails into the coffin lid with a heavy jack. Of course, there were attempts to bypass the system in other ways, for example, to try to copy a ticket to a blank one-on-one card (here, alas, the factory serial prevented, which, as it turned out, also participated in the generation of the "hash") or set the lock bits in such a way to prevent the turnstile from changing the contents of the ticket. The checkout terminal recognized such an “eternal” ticket, but refused to start the turnstile ... Thus, I ran into the wall. In that big, strong concrete wall, about which many have the habit of killing themselves with a running start. Having not found any information on the forums and boards, I decided that my research was finished on that - there were no more ways, and put a bullet in it. As it turned out, in vain ...

Strange acquaintance

September evening was no different from the others. It was almost night, the street was cool and damp. I sat in front of the monitor screen, and, while drinking warm, slightly sweet green tea, peacefully raised a board for my next piece of work. DipTarce, a little bashorg, ICQ ... Someone called on Skype - distract! Again, ICQ, again DipTrace - in general, everything is as usual. Once again, an ICQ window fell into the foreground - someone, hitherto unknown to me, wrote "Hello." I, without hesitating, answered the same. The following message was a turning point in the whole story: “You seem to be interested in the subway, I have a little junk here. If you're interested, let's meet, I'll tell you. ” At first, I was a little embarrassed and alert (maybe a divorce or a fraud, or maybe the “special services” became interested - paranoia takes its toll), but then I thought: why not?

The special services were unlikely to be interested in me, but there seemed to be no ground for a divorce, and even more so for a setup. 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 turned out to be a tall young man, in 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 on. It still didn’t come in handy for me, maybe it will be useful for you. ” Looking inside, I saw two metro terminals arranged with newspapers, several randomly scattered white plastic cards and a blank in a box. To my question about how much I owe (money) for this, the guy shook his head, smiled and said: “Why, you don’t owe anything to anyone, do it ... So, I need to run already, there’s my train time! OK Bye!".

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

The phenomenon of software to the people

Arriving home, I took apart the package. The second of the terminals turned out to be a bus validator (heavy, damn it!); the cards were Mifare Classic 1K (blank), and there was one single archive on the disc. After a quick acquaintance with the contents, it turned out - this is software that is used at the box office. Putting aside the terminal and validator, I decided to come to grips with the study of interesting software. In about an hour, I managed to build and run this program on my computer from the mess that was unpacked. It took another hour to figure 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 is eaten with. As it turned out, they are eating with the Parsec PR-P08 reader, therefore, due to the lack of it, it was not possible to try the software in action.

The developer was Smartek, a major state contractor developing such systems (more details 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 subprograms, classes, and components were located in separate DLLs or bpls with speaking names (this was the most important file of developers). After a quick analysis of the internals of the 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 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 key mechanism (I had already begun 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, except for the file with keys, looks like nothing else). And I used all this goodness of runtime-bpl'in SmLayout.bpl. This library was just a godsend for my research - it contained classes for working with the internal content of tickets. Since this is runtime-bpl, it was enough just to look at its export table in order to already understand by 60 percent what was what. A more detailed analysis put everything in its place. Remember, at the beginning of the article I talked about the fact that in the structure of Ultralight there were several more fields whose purpose was not clear?

One of these fields is the so-called “layout identifier”. In fact, all metro tickets are built from a fixed heading and a variable data part. So, this “Layout” field in the title just determined how and what data is located in the rest of the ticket. There are several such layouts (each for its own type of ticket), and in SmLayout.bpl each of them corresponded to its own class (plus a common parent class, in which there were methods for working with the header part). Therefore, it was easy to figure out which fields in each layout are responsible for what (it would be, with speaking method names in the export!). Having completely completed the whole Layout 8 (which is used in Ultralight) and having checked whether I had a correct idea of ​​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 operation of the method responsible for computing the "hash". First, the correct key is selected from the file with keys (keys.d).

The system is designed so that each type of ticket has its own identifier (the complete set included a complete table with ticket identifiers and names, in the form of a text file with values ​​separated by a comma). It consists of a zone identifier (application) and a map type identifier. So, based on these numbers, keying is selected in the key file, inside which there may already be several keys (in case the new key has been entered and the old tickets are still in use). The new ticket is recorded using the very first one, and the validity check is performed using all keys in the keying. Next, the selected key is decrypted using CryptKeyRef.dll (why they are stored encrypted, I can’t imagine). After that, the decrypted key and almost all the ticket data, as well as its hardware serial number and number (the “hash” generation method, which is specified for keying in keys.d) are passed to the ckCalcHashCode function located in the same CryptKeyRef.dll. At the output, we get the value on which at one time I was “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 a few 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 specifically bought a fresh Ultralight for one trip to see if my keys are working or not (apparently, they were old). You could, of course, immediately try to record the “fabricated” Ultralight and go check, but at that moment I ran out of empty cards, and it’s a little scary to go “randomly” - suddenly what? Upon arrival home, the first thing I did, without even washing my hands, impatiently rushed to check the fresh ticket with my keys. And then a big bummer awaited me - the “hash” recorded on the ticket did not go through any of the keys. Consequently, the keys really are already rotten and replaced by new ones. This completely crossed out all my work. I was a little sad. I made green tea, played a little piano (yes) and sat on to breed my unfinished board ...

All is not lost yet

The idea came to me unexpectedly, when once again for some reason I looked inside the file with the keys. I noticed that in the “running” keying (which is used to calculate 1-, 2-, 5-trip and other Ultralights) there were two keys - a new one (at that time, of course) and, apparently, an old one. But there was also keying, in which lay only one key. Previously, I did not pay attention to him, but concentrated on the "running". To calculate which tickets this key is used, I did not know. When I looked at what type of ticket was attached to caring, a little spark of hope flashed out of me. The fact is that this type of ticket was VESB. 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 land transport, where it is very difficult and long to replace it with a new one.

In addition, there is only one key in keying, which indirectly confirmed my guess. To everything else, I remembered that when I cleaned the metro program from various "garbage", there was something similar to an archive of old key files. Digging out and opening the original archive, I saw that this is indeed so. And most importantly, looking at all the old key files, I found that this particular key remained unchanged! Already without a single drop of doubt, I riveted my own VESB (fortunately, I had dumps of this type that made the task much easier - I just changed the dates and number in the dumps), and calculated the “hash” using this key. So, the time has come for verification (especially since I just bought some more clean plastic). Entering the lobby, I first attached my “ticket” to the checkout terminal. The expiration date of the ticket, which I indicated, was displayed on the board, and the green LED lit up. So it works. Making a simple grimace and hiding the snow-white plastic in my sleeve, I went to the turnstile, put my hand to the validator and ... calmly walked on the fun-lit green. This marked the final victory.

And then what?

And then experiments began, during which many interesting things were found out. For example, on such a "left" VESB you can walk only two or three days. The fact is that the number that I indicate “from the bulldozer” inside the ticket is stored in the memory of the turnstile’s head with each pass, and after a while it 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 enters it into a stoplist, which is then sent to all metro turnstiles. 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. For obvious reasons, getting around it is not possible.

It was also noticed that setting or not setting the lock bits does not play any role in whether the ticket will work or not. The exception is only the OTP zone blocking bit, which the turnstile apparently always checks, even though it is not going to write to OTP. In the future, I took up the metro and bus terminals, put them in order, studied and launched at the stand. Now, in order to check another conjecture, it was no longer necessary to run away with a freshly baked mutant ticket in the subway, but it became possible to check them “without leaving the ticket office”. Moreover, the metro terminal turned out to be as old (everything else and buggy), like my keys. So I could try “at work” and any other types of Ultralight tickets — something that I could never do “live” in the subway. In parallel with these experiments, I continued to engage in software.

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

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

You can read what the page is, where and how the hardware serial number, lock bits, and OTP zone are located in the original documentation (the specification file in PDF format with a full description of the chip is on the disk). I recommend starting the study with her. I will describe the structure of the data arrangement formed by metro systems in the user area, accessible for reading and rewriting (in the absence of locks, of course). The entire contents of the ticket can be conditionally divided into the heading part and two data parts completely duplicating each other (this was done in order to reserve and protect against errors). The title part in Ultralight tickets starts on page 4. Part of it is identical in structure to all tickets and identifiers of the Metropolitan system and MosGorTrans. The first 10 bits are the application identifier; the next 10 bits is an identifier of the type of card (you can read about what identifiers can be found in another box specially selected for this). After the identifiers is the serial number of the ticket (it is stamped on the back of the ticket, do not confuse it with the hardware - these are 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. This ends the same part of the header. Next, the Ultralight ticket indicates 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 that have passed since 01/01/1992. Here the title 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 issuing date are recorded. After this, the validity of the ticket in days (from the date of issue) is indicated - 8 bits. The first 16 bits of page 9 are a 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 remainder of the page, the turnstile enters its unique identifier with each pass. Apparently, this is used to prevent re-entry without waiting for a VESB ticket (the turnstiles in the lobby are networked and interrogate each other), as well as to be able to see through which turnstile the passage 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 blank. This data area is entirely replicated to the remaining 4 pages (12 to 15). It turns out that during normal operation, these two areas always contain the same data. Separately, it is worth mentioning the use of the OTP zone by the system. It is used to gradually “burn out” a ticket with each trip (this does not apply to VESB tickets). The two least significant bits are set when canceling or canceling a ticket (by stop list). A canceled ticket is not refundable. Only 30 bits are left for burning. This area is represented by the system as 100% of trips. With each new trip, a certain number of bits (from low to high) is set, corresponding to how many percent one trip takes. For example, for a 5-trip ticket with each new trip, 6 bits will be “burned out”, and for a 60-trip ticket, it will be “half-bit” (rounded up). It is worth mentioning that the re-use of Ultralight tickets is impossible not only because of the “burning out” of OTP, but also because at the ticket office, when issuing a ticket (and possibly even during its manufacture), almost all pages are blocked for rewriting . Thus, neither "recharge" nor change the type of ticket to another will fail.

Examples of metro ticket identifiers used

All numbers are in decimal notation!

Application Identifiers:

  • 262 - Moscow Metro Ticket.
  • 264 - Moscow ground transportation ticket.
  • 266 - Unified Social of Moscow and Moscow Region.
  • 270 - Ticket "Easy subway."

Ultralight ticket type identifiers:

  • 120 - One trip.
  • 121 - Two rides.
  • 126 - Five rides.
  • 127 - Ten rides.
  • 128 - Twenty trips.
  • 129 - Sixty trips.
  • 130 - Baggage + pass.
  • 131 - Only baggage.
  • 149 - Single Ultralight (70 trips).
  • 150 - WESB.

Mifare classic

I did not ignore the ill-fated Mifare Classic 1K in my research. As you know, the main obstacle to the "Classics" was hardware keys A and B. By a lucky chance, these keys were in one of the program modules in the clear (prev 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 received keys. During the experiments, some interesting features were revealed, such as: the metro uses the first sector of the map to store a ticket, and ground transport uses the fourth; there is no protection other than hardware keys (which, being recorded in software in this form, most likely have never changed since the system was put into operation) on these tickets.

Instead, CRC-16 is indicated at the end of each block, simply to protect the data from corruption. In addition, on social cards, in addition to tickets, a lot of diverse and interesting information is recorded. For example, the surname, name and patronymic of the owner are indicated in sections 13 and 14 of social cards. This (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 blank Classic cards.

But from the cloning, as it turned out, the stop-list system perfectly saves - such a ticket can be used for no more than two days, then it is canceled (although, unlike Ultralight, the Classic card can be restored after canceling, 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 Ultralight research.

The End, or to summarize

Subway systems, and in particular, the new Ultralight tickets, contrary to opinions and speculations, were well protected. It is very pleasing that the developers used a reliable and time-tested GOST, and did not begin to reinvent the wheel. With such protection, forging an Ultralight ticket without access to confidential data (key information) is simply impossible. The interchangeable key system and the stop-list mechanism are also well thought out. Of course, there were some shortcomings and mistakes. The largest of these is software that is in no way protected.

It was enough to abandon the use of runtime-bpl, and this would make analysis ten times more difficult! As an option, processing of especially important parts of the program by AsProtect or ExeCryptor, followed by packing all the files with MoleBox, would reduce the analysis to almost zero. The toolkit is inexpensive. And the use of good (preferably, little-known or custom-made) protection of this kind, but with hardware keys, would make analysis of the program completely impossible. Of course, the Metropolitan is a sensitive enterprise, but do not forget about the human factor. After all, Kevin Mitnik said (and not only spoke, but demonstrated by his own example, for which he sat down, gee) that sometimes it is easier and more efficient to use “social engineering” to achieve the goal than to try to break down impenetrable defense. Well, on this note I will finish my story. And you, 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 of cryptographic conversion for information processing systems in electronic computer networks (computers), individual computer complexes and computers, which defines the rules for data encryption and the development of an insert.

The cryptographic conversion algorithm is intended for hardware or software implementation, satisfies cryptographic requirements and, by 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 apply cryptographic protection of data stored and transmitted in computer networks, in separate computer complexes or in computers.

Block diagram of cryptographic conversion algorithm

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

  • - 256-bit key memory device (RAM), 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 the filling constant C 2 , C 1 recorded in them;
  • - two 32-bit adders modulo 2 32 (SM 1 , SM 3 );
  • - 32-bit adder of bitwise summation modulo 2 (SM 2 );
  • - 32-bit adder modulo (2 32 -1) (CM 4 );
  • - adder modulo 2 (CM 5 ), the restriction on the capacity of the adder CM 5 is not imposed;
  • - substitution block (K);
  • - register of cyclic shift by eleven steps in the direction of the senior discharge (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 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 into a 4-bit vector by the corresponding replacement node, which is a table of sixteen rows containing four fill bits per line. The input vector determines the address of the row in the table, filling this row is the outgoing vector. Then 4-bit output vectors are sequentially combined into a 32-bit vector.

When adding and cyclic shift of binary vectors, the most significant bits are the bits of drives with large numbers.

When writing a key (W 1 , W 2 , ..., W 256 ), W q Є {0,1}, q = i ÷ 256, â RAM, the value of W 1 is entered in the 1st bit of the drive X 0 , the value of W 2 is entered in the 2nd bit of the drive X 0 , ..., the value of W 32 is entered in the 32nd bit of the drive X 0 ; the value of W 33 is entered into the 1st discharge of drive X 1 , the value of W 34 is entered into the 2nd discharge of drive X 1 , ..., the value of W 64 is entered into the 32nd discharge 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 discharge of one drive (adder) are overwritten into the pth discharge of another drive (adder).

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

Table 1

The category of drive N 6

32

31

thirty

29th

28

27

26

25

24

23

22

21

twenty

nineteen

eighteen

17

Discharge value

0

0

0

0

0

0

0

one

0

0

0

0

0

0

0

one

The category of drive N 6

sixteen

fifteen

14

thirteen

12

eleven

10

nine

8

7

6

5

4

3

2

one

Discharge value

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 shown in table 2.

table 2

Discharge of drive N 5

32

31

thirty

29th

28

27

26

25

24

23

22

21

twenty

nineteen

eighteen

17

Discharge value

0

0

0

0

0

0

0

one

0

0

0

0

0

0

0

one

Discharge of drive N 5

sixteen

fifteen

14

thirteen

12

eleven

10

nine

8

7

6

5

4

3

2

one

Discharge value

0

0

0

0

0

0

0

one

0

0

0

0

0

0

0

one

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

Filling the tables of the substitution block K is a long-term key element common to a computer network.

The organization of various types of communication is achieved by building an appropriate key system. In this case, the possibility of generating keys (filling in the RAM) in the simple replacement mode and encrypting them in the simple replacement mode with the provision of imitation protection for transmission over communication channels or storing in the computer memory can be used.

The crypto scheme provides four types of work:

  • - encryption (decryption) of data in a simple replacement mode;
  • - encryption (decryption) of data in gamma mode;
  • - encryption (decryption) of data in gamma mode with feedback;
  • - mode of development of an imitation insert.

Easy Replacement Encryption

Encryption of open data in simple replacement mode

The cryptographic scheme that implements the 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. Entering 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 made so that the value a 1 (0) is entered into the 1st digit N 1 , the value a 2 (0) is entered into the 2nd digit N 1 , etc., the value a 32 ( 0) is introduced in the 32nd digit 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)) of drive N 1 and the state (b 32 (0), b 31 (0), ... , b 2 (0), b 1 (0)) of drive N 2 .

256 bits of the key are entered into the RAM. The contents of eight 32-bit drives X 0 , X 1 , ..., X 7 is:

  • 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 encryption algorithm of a 64-bit open data block in simple replacement mode consists of 32 cycles.

In the first cycle, the initial filling of the drive N 1 is added modulo 2 32 in the adder CM 1 with the filling of the drive X 0 , while the filling of the drive N 1 is saved.

The result of the summation is converted 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 towards the higher digits. The shift result is summed bitwise modulo 2 in the adder CM 2 with 32-bit filling drive N 2 . 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 in the same way, while in the 2nd cycle the filling X 1 is read from the RAM, in the 3rd cycle the filling X 2 is read from the ROM, etc., in the 8th cycle the filling X 7 is read from the RAM. In the cycles from the 9th to the 16th, as well as in the cycles from the 17th to the 24th filling from the memory 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 RAM, the reverse order is: X 7 , X 6 , X 5 , X 4 , X 3 , X 2 , X 1 , X 0 .

Thus, when encrypting in 32 cycles, the following procedure for selecting drive fillings 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 the old filling is stored in the accumulator N 1 .

The fillings of drives N 1 and N 2 obtained after the 32nd encryption cycle are an encrypted data block corresponding to an open data block.

Decryption of encrypted data in simple replacement mode

The cryptographic scheme that implements the decryption algorithm in the simple replacement mode has the same form (see Figure 2) as with encryption. 256 bits of the same key, on which encryption was performed, are entered into the RAM. The encrypted data to be decrypted is divided into blocks of 64 bits each. Entering any block T w = (a 1 (32), a 2 (32), ..., a 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 N 1 , the value of a 2 (32) is entered into the 2nd digit N 1 , etc., the value of a 32 (32) introduced in the 32nd digit N 1 ; the value of b 1 (32) is entered into the 1st discharge N 2 , the value of b 2 (32) is entered into the 2nd discharge N 2 , etc., the value of b 32 (32) is entered into the 32nd discharge N 2 .

Decryption is carried out according to the same algorithm as encryption of open data, with the change that the filling of drives X 0 , X 1 , ..., X 7 are read from the RAM in 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 cycles of operation, filling drives N 1 and N 2 comprise 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 the block of encrypted data, the value of a 1 (0) of the T 0 block corresponds to the contents of the 1st discharge N 1 , the value of a 2 (0) corresponds to the contents of the 2nd discharge N 1 , etc., the value of a 32 (0) corresponds to the contents of 32- th discharge N 1 ; the value of b 1 (0) corresponds to the contents of the 1st discharge N 2 , the value of b 2 (0) corresponds to the contents of the 2nd discharge N 2 , etc., the value of b 32 (0) corresponds to the contents of the 32nd discharge N 2 .

Similarly, the remaining blocks of encrypted data are decrypted.

Gamma mode

Gamma encryption of open data

The cryptographic scheme that implements the encryption algorithm in gamma mode 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 gamma mode by bitwise summation modulo 2 in the adder CM 5 with the gamma of the cipher G w , which is produced in blocks of 64 bits, i.e.

G W = (G W(1) , G W(2) , ..., G W(M-1) , G W(M) ),

where M is determined by the amount of encrypted data.

G w(i) - i-th 64-bit block, i = 1 ÷ Ì, the number of binary bits in the block T 0(M) can be less than 64, while part of the cipher gamma from the block G w(M) not used for encryption discarded.

256 bits of the key are entered into the RAM. A 64-bit binary sequence (sync packet) S = (S 1 , S 2 , ..., S 64 ) is introduced into the drives N 1 , N 2 , which is the initial filling of these drives for the subsequent generation of M cipher gamma blocks. The clock package is entered in N 1 and N 2 so that the value of S 1 is entered in the 1st digit of N 1 , the value of S 2 is entered in the 2nd digit of N 1 , etc., the value of S 32 is entered in the 32nd digit N 1 ; the value of S 33 is entered into the 1st discharge N 2 , the value of S 34 is entered into the 2nd discharge N 2 , etc., the value of S 64 is entered into the 32nd discharge N 2 .

The initial filling of drives N 1 and N 2 (sync package S) is encrypted in a simple replacement mode in accordance with the requirements of paragraph 1.3.1. The encryption result is copied to 32-bit drives N 3 and N 4 so that the pad N 1 is copied to N 3 , and the pad N 2 is copied to N 4 .

The filling of drive N 4 is summed modulo (2 32 -1) in the adder CM 4 with a 32-bit constant C 1 from drive N 6 , the result is written to N 4 .

The filling of drive N 3 is summed modulo 2 32 in the adder CM 3 with a 32-bit constant C 2 from drive N 5 , the result is written to N 3 .

Filling N 3 is copied to N 1 , and filling N 4 is copied to N 2 , while filling N 3 , N 4 is saved.

Filling N 1 and N 2 is encrypted in a simple replacement mode in accordance with the requirements of paragraph 3.1. The filling N 1 , N 2 obtained as a result of encryption forms the first 64-bit block of the cipher gamma G w(1) , which is summed bitwise modulo 2 in 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 modulo 2 summation in CM 5 of the value of t 1(1) from the block T 0(1) with the value of the 1st digit N 1 , the value of τ 2(1) of the block T w(1) is the result of modulo 2 summation in CM 5 of the value of 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 modulo 2 summation in CM 5 of the value of t 64(1) from block T 0(1) with the value of the 32nd digit N 2 .

To obtain the next 64-bit block of the cipher gamut Gw (2), the filling N 4 is summed modulo (2 32 -1) in the adder CM 4 with the constant C 1 of N 6 , the filling N 3 is summed modulo 2 32 in the adder CM 3 with constant C 2 of N 5 . The new filling N 3 is copied to N 1 , and the new filling N 4 is copied to N 2 , while the filling of N 3 and N 4 is saved.

Filling N 1 and N 2 is encrypted in a simple replacement mode in accordance with the requirements of paragraph 3.1. The filling N 1 , N 2 obtained as a result of encryption forms a second 64-bit block of the gamma of the cipher G w(2) , which is summed bitwise modulo 2 in the adder CM 5 with the second open data block T 0(2) . The cipher gamma blocks G w(3) , G w(4) ..., G w(M) are similarly generated and 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 cipher gamma G w(M) only the corresponding number of cipher gamma bits is used for encryption, the remaining bits are discarded.

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

Decryption of encrypted data in gamma mode

When decrypting, the crypto scheme has the same form as when encrypting (see Figure 3). 256 bits of the key are entered into the RAM, with the help of which the data was encrypted T 0(1) , T 0(2) ..., T 0(M) while T 0(M) can contain less than 64 bits.

Feedback Gamma Mode

Encryption of open data in gamma mode with feedback

The cryptographic scheme that implements the gamming mode with feedback should have the form given in figure 4.


Figure 4

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

256 bits of the key are entered into the RAM. A 64-bit binary sequence (sync packet) S = (S 1 , S 2 , ..., S 64 ) is introduced into the drives N 1 , N 2 . The clock package is entered in N 1 and N 2 so that the value of S 1 is entered in the 1st digit of N 1 , the value of S 2 is entered in the 2nd digit of N 1 , etc., the value of S 32 is entered in the 32nd digit N 1 ; the value of S 33 is entered into the 1st discharge N 2 , the value of S 34 is entered into the 2nd discharge N 2 , etc., the value of S 64 is entered into the 32nd discharge N 2 .

The initial filling of drives N 1 and N 2 is encrypted in a simple replacement mode in accordance with the requirements of paragraph 3.1. The filling N 1 and N 2 obtained as a result of encryption forms the first 64-bit block of the cipher gamma G w(1) , which is summed bitwise modulo 2 in 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 encrypted data block T w(1) is at the same time also the initial state N 1 , N 2 for generating the second block of the cipher gamut G w(2) and is written to the indicated drives by feedback. In this case, the value of τ 1(1) is introduced into the 1st discharge N 1 , the value of τ 2(1) is entered into the 2nd discharge N 1 , etc., the value of 32 32(1) is entered into the 32nd digit N 1 ; the value of τ 33(1) is entered into the 1st discharge N 2 , the value of τ 34(1) is entered into the 2nd discharge N 2 , etc., the value of τ 64(1) is entered into the 32nd discharge N 2 .

Filling N 1 , N 2 is encrypted in a simple replacement mode in accordance with the requirements of paragraph 3.1. The filling N 1 , N 2 obtained as a result of encryption forms a second 64-bit block of the gamma of the cipher 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 gamut of the cipher G w(i) and encryption of the corresponding blocks of open data T 0(i) (i = 3 ÷ Ì) is carried out similarly. If the length of the last Mth block of open data T 0(M) is less than 64 bits, then only the corresponding number of bits of the cipher gamma is used from G w(M) , the remaining bits are discarded.

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

Decryption of encrypted data in gamma mode with feedback

When decrypting, the crypto scheme has the same form as when encrypting (see Figure 4). 256 bits of the same key are entered into the RAM on which T 0(1) , T 0(2) ..., T 0(M) was encrypted. The clock package is entered in N 1 , N 2 so that the value of S 1 is entered in the 1st digit of N 1 , the value of S 2 is entered in the 2nd digit of N 1 , etc., the value of S 32 is entered in the 32nd digit N 1 ; the value of S 33 is entered into the 1st discharge N 2 , the value of S 34 is entered into the 2nd discharge N 2 , etc., the value of S 64 is entered into the 32nd discharge N 2 .

The initial filling of drives N 1 and N 2 (sync package S) is encrypted in a simple replacement mode in accordance with the requirements of paragraph 3.1. The filling N 1 , N 2 obtained as a result of encryption forms the first 64-bit block of the gamma of the cipher Г ш(1) , which is summed bitwise modulo 2 in the adder СМ 5 with the block of encrypted data Т ш(1) . The result is the first block of open data T 0(1) .

The encrypted data block T w(1) is the initial filling N 1 , N 2 to generate the second block of the cipher gamut G w(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 discharge N 1 , the value of τ 2(1) is entered into the 2nd discharge N 1 , etc., the value of 32 32(1) is entered into the 32nd digit N 1 ; the value of τ 33(1) is entered into the 1st discharge N 2 , the value of τ 34(1) is entered into the 2nd discharge N 2 , etc., the value of τ 64(1) is entered into the 32nd discharge N 2 . The resulting filling N 1 , N 2 is encrypted in a 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 adder CM 5 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 are written sequentially T W(2) , T W(3) ..., T W(M-1) , from which cipher gamma blocks G W(3) , G are generated in simple replacement mode w(4) , ..., G w(M) . The cipher gamma blocks are summed bitwise modulo 2 in the CM 5 adder with encrypted data blocks T w(3) , T w(4) ..., T w(M) , as a result, 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.

Imitation insertion mode

To ensure 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 generated (insert And l ). The process of generating an insert 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) , ..., a 32(1) (0), b 1(1) (0), b 2(1) (0), ..., b 32(1) (0)) is written to the drives N 1 and N 2 , the value of t 1(1) = a 1(1) (0) is introduced into the 1st digit N 1 , the value of t 2(1) = a 2(1) (0) is introduced into the 2nd digit N 1 , etc., the value t 32(1) = a 32(1) (0) is introduced into the 32nd digit 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 introduced into the 32nd digit N 2 .

Filling N 1 and N 2 undergoes a conversion corresponding to the first 16 cycles of the encryption algorithm in simple replacement mode, in accordance with the requirements of paragraph 3.1. At the same time, the same key is found in the KZU 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 w(1) , T w(2) , ..., T W(M) .

The filling 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)), is 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 conversion corresponding to the first 16 cycles of the encryption algorithm in simple replacement mode.

The resulting filling N 1 and N 2 is summed up 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 the full 64-bit block with zeros, is summed in CM 5 modulo 2 with filling in 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 the summation is recorded in N 1 , N 2 and is encrypted in a simple replacement mode according to the first 16 cycles of the algorithm. From the resulting filling of drives 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 )].

The insert And l is transmitted over the communication channel or to the computer memory at the end of the encrypted data, i.e. T W(1) , T W(2) , ..., T W(M) , And l .

The received encrypted data T sh(1) , T sh(2) , ..., T sh(M) are decrypted, from the received blocks of open data T 0(1) , T 0(2) , ..., T 0(M) , an insert is generated And l , which is then compared with a simulated insert And l , received together with encrypted data from a communication channel or computer memory. In the event of a mismatch of the insertions, 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 binary digits in the insert) is determined by the current cryptographic requirements, while taking into account that the probability of imposing false data is 2 - l .