When it's time to pick up the keys.

When it's time to pick keys.

When it's time to pick keys

A group of well-known cryptographers, created under the auspices of the Alliance of Business Software Manufacturers (an industry organization that prevents illegal use of software), came to the conclusion that the required key length should currently be at least 75 bits, with a further increase over the next 20 years to 90 bits.

Americans are serious people and will not joke about such things. But try, dear reader, to figure out what this statement is based on and check the accuracy of the conclusion of overseas specialists.

Where do we begin? If there is a lock that needs to be opened, but there is no key, a master key or other suitable (or not so suitable) tool is used. If you need to open a cipher message, and the hacking method is a complete search of keys, then you need a tool for this — a powerful computer. Let's start with an analysis of the capabilities of modern computers.

As early as the 1960s, some computer manufacturers began creating supercomputers — powerful machines for solving problems with a large volume of calculations, which until recently were used mainly for military purposes. Like everything most-most, this direction of development of computer technology has always attracted increased interest from both specialists and people far removed from this subject. Apparently, in order to satisfy this interest, the so-called TOP 500 has recently been published in the open press — a list of the five hundred most powerful supercomputers in operation in the world and the largest supercomputer centers (SCCs) in the world (Table 1), updated twice a year. The achieved maximum performance according to the Linpack parallel test is used to compile the first list.

Table 1.10 most powerful supercomputers as of July 1997

From the list that appeared in the summer of 1997, it follows that the supercomputers were distributed in terms of speed as follows:
with a capacity of about 1012 FLOPS — 1 unit;
with a capacity of about 1011 FLOPS — 20 units;
with a capacity of about 1010 FLOPS — 328 units;
with a capacity of about 109 FLOPS — 151 units.

Table 2 lists the first 15 countries in descending order of the performance of their most powerful supercomputers. If a country has several supercomputers, the performance of the most powerful one is indicated. It is clear that the presence of supercomputers shows the scientific and technical potential of the country, reflects its military capabilities.

Table 2. The first 15 countries from the Top500 list

The United States ranks first in the world in terms of the number of supercomputers—254 (51%). They are followed by Japan—87 (17.5%), Germany—45 (9%), Great Britain—24 (4.8%), France—18 (3.6%), Korea—8 (1.6%), Canada—7 (1.4%), Sweden, Switzerland, and Norway—6 each (1.2%).

Russia is mentioned in this list only once: in 156th place is the HPC Ultra 10000 computer (peak performance 16600 MFLOPS), manufactured by SUN and installed in the National Reserve Bank of Russia. I would like to believe that this position is not entirely true. An interesting detail: there are no foreign-made computers in the USA — Americans work only on domestic machines and, what's more, supply them to the rest of the world.

Table 3. Computers from the TOP500 list belonging to organizations capable of intercepting and decrypting information

The number of supercomputer installations is growing exponentially year after year, with the bulk of them again coming from the United States. It is interesting to note that the list mainly includes machines manufactured in the last two years, with the rest accounting for no more than a quarter of the list. It can be concluded that the list has been updated almost completely over the last 3-4 years. The statistics by year are as follows: 1997 — 207 installations (as of July 1997), 1996 — 168 installations, 1995 — 52 installations, 1994 — 45 installations, 1993 — 16 installations, 1992 — 10 installations, 1991 — only 2 installations, with ratings of 128 and 195. Let's try to forecast the increase in the number of supercomputers over the next two years based on statistics for the last six years:

45/10 = 4.5
52/16 = 3.25
168/45 = 3.7
207/52 = 3.9.

Using the average growth rate over two years (3.8), we calculate the estimated installation values ​​for 1998-99:

168 x 3.8 = 638 installations in 1998,
207 x 3.8 = 786 installations in 1999.

Thus, in the next year or two, we can expect the TOP 500 list to grow into the TOP 1500 (638 + 786 = 1424) or even more.

The list of supercomputer manufacturers in the world is shown in Fig. 1.

Fig. 1.

The list includes 11 companies, with the four leading American companies providing more than 80% of the world market (402 installations out of 500). In total, US manufacturers cover 86% of the world's supercomputer production (Intel, TMC, DEC, Parsytec together account for 28 installations, or 5.6%). Japanese companies (Fujitsu, NEC, Hitachi) provide the remaining 70 installations in the TOP500 (14%).

There is a clear relationship between the place occupied by certain countries in the list under consideration and the level of investment in information technology in these countries (Fig. 2).

Fig. 2.

It is not by chance that we have reviewed the list of the most powerful computers in the world in such detail and in such a comprehensive manner. It will serve as a starting point for us to study the resistance of encryption algorithms with a random key in the case of using modern computers to crack them.

Let us assume that the encryption algorithms we are considering are ideal, i.e. the optimal method for cracking them will be a direct search of all possible keys of a given algorithm. Obviously, in this case the strength of cryptosystems will be determined by the length of the key. In this study, it was assumed that the cryptanalyst of the opposing party has all the information about the encryption algorithm, with the exception of the data on the secret key, and the ciphertext of the message is available for analysis. By definition, it is assumed that an ideal algorithm is devoid of any shortcomings that reduce its cryptographic strength.

Let us also assume that the computer generates a key in one cycle of its operation, and the decryption operation is instantaneous. Having determined the ratio of the number of keys to the speed of the most powerful computer, we obtain a lower bound on the complexity of decrypting a message for an ideal algorithm. The results of these calculations are given in Table 4. According to probability theory, the average time of decrypting a message (the mathematical expectation of the decryption time) should be considered half the time given in the table (indicated in brackets). In cases where the period required for a complete enumeration of keys exceeded 10,000 years, the average decryption time was not specified.

Table 4. Time (in years) currently required by the most powerful supercomputers to completely enumerate keys

According to some estimates, computer performance divided by its cost increases 10 times every 5 years. Based on this thesis, over the next fifty years, computer performance will increase as follows:

2005 — 10 times
2010 — 100 times
2015 — 1000 times
2020 — 10,000 times
2025 — 100,000 times
2030 — 1,000,000 times
2035 — 10,000,000 times
2040 — 100,000,000 times
2045 — 1,000,000,000 times
2050 — 10,000,000,000 times
etc.

Let's try to check the veracity of this statement.

According to the Great Soviet Encyclopedia (article «Digital Computer»), the first electronic digital computer, ENIAC, was built in 1945 and put into operation in 1946 in the USA. From that moment on, active research began in many countries aimed at creating reliable electronic digital elements and developing rational digital computer structures.

The operating speed of the first generation of machines (until the mid-50s) did not exceed several hundred operations per second. Let's assume that the speed of the very first machines was 100 operations per second and take this value as a starting point.

Since 51 years have passed since then (10.2 five-year periods), then by 1997 the computer's power should have increased to approximately 100 — 1010.2 = 1012.2 operations per second, which is confirmed by the TOP 500 list given above. In 1951, the State Commission accepted the first electronic computing machine on the European continent and in the USSR, the MESM, with a speed of 50 operations per second, created by a small group led by Academician S. A. Lebedev. By now (97 — 51 = 46, 46/5 = 9.2), the estimated performance of such a machine should be 50 • 109.2 = 5 • 1010.2 operations per second. The most powerful computer on the European continent, located in Great Britain, operates at a speed of 2.6 • 1011

Thus, we can say that the forecast “10 times in 5 years” is quite reasonable and reliably describes the growth of computing power over large periods of time.

Let us define x(t) as a continuous function showing the speed of computers at time t. Based on the accepted working hypothesis of «10 times in 5 years» and the initial reference point (tg = 0 in 1946), the function looks like this: x(t) = C0 • 10t/5, where the initial reference point C0 = 100 is the power of the first ENIAC computer.

Let us introduce the following notation:

S is the power of the alphabet from which the symbols for the key are extracted;
L is the length of the key;
||{K}|| = SL is the power of the set of keys;
Tm({K}, x(t)) is the maximum time for enumerating keys;
D ({K}, x(t)) — mathematical expectation of decryption;
topt , — optimal moment to start decryption;
Tб({K}, x(t)) — system security time (depends on two parameters — decryption start time t and its duration D).

Under the above assumptions, the time to search through all keys in a given key space at time t (the maximum time to decrypt a message) is Tm = ||{K}||/x(t), and the average time to decrypt a message is half the maximum time: D = 1/2 Tm = 1/2 (||{K}||/x(t)). Based on the forecast for the increase in computing power, one could simply assume that the duration of the search in 100 years should be some predetermined time, for example one year, and compose the following equation of the type ||{K}||/Cl • x(t+100) > 1, from which it follows that the required key length should be 136-137 bits. However, more accurate and useful estimates can be given in order to avoid wasting efforts on tasks whose time has not yet come.

Of course, if we wait 100 years, then a forceful attack on a cryptographic algorithm, the implementation of which today requires many years, will at that moment take only a few seconds, but due to the complete loss of relevance of the obtained information, the point of carrying it out will disappear. Considering the continuous growth of the power of computer resources, it can be assumed that decryption should not begin immediately upon receiving the ciphertext, but at the moment when it will require the least time. The gain in many cases can be very significant! For example, if today the cryptanalysis process will require 100 years, then in 5 years computer power will increase 10 times, and decryption, having taken 10 years, will be completed in 2015. In 10 years, computer productivity will increase 100 times, and a complete enumeration of options, having been completed within one year, will give a result already in 2011. Thus, the gain in time compared to the first option is 89 years. The question is whether it is possible to further reduce the time of cryptanalysis by optimally choosing the moment of its beginning and how long (starting from this moment) will the optimal decryption last.

The working model for calculating the security time of the encryption system (1) consists of the sum of two active factors — the moment of the start of decryption plus the complexity of decryption. We will call the minimum of this function the maximum security time Tб of an ideal encryption system. The adjective «maximum» is introduced only to emphasize the ideality of the algorithms under study — in real life, cryptosystems have certain shortcomings that reduce their cryptographic resistance. The coefficient Cl = 31,536,000 occurs when switching from operations per second to operations per year and is used mainly for convenience.

To determine the minimum of this function, we find its derivative and solve the equation Tб’ = 0. As a result of the solution and simplification, we obtain the following value of the moment of time topt at which the minimum of the function Tб is achieved, that is, the optimal time to start cryptanalysis:

Substituting ||{K}|| into this formula, we can obtain the value of the time point topt. The security time of an ideal encryption system is determined by the value of the function Tб at this point. Substituting into (1) the power of the set of keys ||{K}|| in the system under study and the value of topt, we can find its security time Tб.

The average decryption time is determined by the following formula:

The most unexpected and interesting fact, in my opinion, is that if we substitute the value of topt into formula (3) and make the necessary simplifications, then the duration of decryption started at the optimal moment, regardless of the key length, is always the same: 5/ln 10 == 2.171472409516 years (739.13 days or 19,035.12 hours).

Tb = topt +2.17

Thus, using the specified working model, it is possible to estimate the reliability of the designed and operated encryption systems. For example, the resistance (in years) of algorithms with different key lengths in our estimates is given in Table 5. The calculations were made using formula (2) for the third column and formula (1) for the fifth column, and all data were counted from the initial moment in time — 1946. As an example of the calculations performed, we will consider an encryption algorithm with a 70-bit key. According to formula (2), the optimal moment to start hacking it is 64.7 years, or 1946 + 64.7 = 2010.7, that is, August 12, 2010. The process launched on this day will last 2 years 2 months 1 day 17 hours 31 minutes and will end on October 13, 2012 at 4 hours 48 minutes.

Table 5. Optimal start time of decryption, its duration and end time depending on the key length

Of course, all the above results are valid only on average. The duration of decryption of each individual message can vary from 0 to Tm, but when put on stream (on an industrial scale) it will tend to the values ​​indicated above.

What other benefits can be derived from the constructed theory? The formula for the dependence of the key length on a predetermined nl — the year of the beginning of decryption — can be practically useful.

For example, it is necessary to close some information in such a way as to guarantee its confidentiality for 20 years. What should the key length be in this case?

Today is 1998, the information should not be decrypted until 2018, therefore, nl = 2018 — 1946 = 72 years. Having made the necessary calculations, we find that the power of the set of keys ||{K}|| should be at least 3.444 • 10 ^ 22, and the key length is approximately 74.87 bits.

Yes, the American cryptographers were right! Based on the same calculations, we can conclude that they consider this period to be quite sufficient for the decrypted information to become obsolete. Let's check their statement that in 20 years the required key length should be 90 bits.

In 20 years, it will be 2018, therefore, to ensure the required information security, the optimal decryption time should not be earlier than 2038 (2038 — 1946 = 92).

The power of the set of keys calculated using formula (4) should be 3.444 • 1022, and the key length should be 88.16 bits.

The minor difference between the results obtained and the results proposed by world-renowned American specialists confirms the mathematical correctness and validity of the theory we proposed and its main premise — the speed of computers increases tenfold every 5 years. The existing discrepancies may depend, for example, on the accuracy of calculations of various calculators or on the value of the constant Cl (the number of seconds in a year), if we take into account that there are not 365 days in a year, but 365 days 6 hours 40 minutes.

The proposed theory is also confirmed by the data on the hacking of messages with keys of 40, 48 and 56 bits in 1997, the security time of which has long expired, amounting to 19.5 (1965), 31.56 (1977), 43.6 (1989) years, respectively. Moreover, using the formulas given above, in 1998 one can reasonably assume the hacking of keys up to and including 62 bits. But keys with a larger number of digits will not be hacked in 1998! The author is ready to make a bet on this with anyone.

Another conclusion is that the ban of American legislators on the export of cryptographic products with a key length of more than 56 bits is calculated for the performance of computers from ten years ago and does not ensure the security of the transmitted information today.

Against this background, the cryptography of Russia looks much more attractive. For 10 years now, it has been offering a 256-bit key as a standard, the security of which is guaranteed for 300 years ahead — until 2290.