Pavel Semjanov
e-mail: psw@ssl.stu.neva.ru
web: www.ssl.stu.neva.ru/

In the modern software (ON) криптоалгоритмы are widely applied not only to problems of enciphering of the data, but also for аутентификации and integrity checks. For today exist well-known and approved криптоалгоритмы (as with symmetric, and asymmetrical keys), криптостойкость which either it is proved математически, or it is based on necessity of the decision математически a challenge (факторизации, discrete логарифмирования, etc.). To most known of them относятсяDES, RSA. Thus, they cannot be opened differently, than full search or the decision of the specified problem.

On the other hand, in computer and околокомпьютерном the world all time appears the information on errors or "holes" in this or that program (including applying криптоалгоритмы), or that it has been cracked (cracked). It creates mistrust both to concrete programs, and to possibility in general to protect something криптографичеcкими methods not only from special services, but also from simple hackers.

Therefore the knowledge of history of attacks and "holes" in криптосистемах, and also understanding of the reasons on which they took place, is one of necessary conditions of working out of the protected systems. A perspective direction of researches in this area is the analysis of successfully spent attacks or revealed уязвимостей in криптосистемах for the purpose of their generalisation, classification and revealing of the reasons and laws of their occurrence and existence. It also will be a problem of given article.

By analogy to taxonomy of causes of infringement of safety ВС [1], we will allocate following causes of unreliability of cryptographic programs (fig. 1 see):

1. Impossibility of application proof криптоалгоритмов;
2. Errors in realisation криптоалгоритмов;
3. Wrong application криптоалгоритмов;
4. The human factor.

Let's notice at once that considered below the reason cover only two kinds of potentially possible threats: disclosings and integrity, laying aside refusal threat in service which gets the increasing value in process of development distributed криптосистем.

This group of the reasons is the most widespread because of following factors.

Small speed proof криптоалгоритмов

It is a major factor complicating application of good algorithms in systems of "total" enciphering or enciphering "hurriedly". In particular, program Norton DiskReet though has realisation DES, at change by the user of a key can not перешифровывать all disk since it will occupy too much time. Similarly, the compression program "hurriedly" Stacker firms Stac Electronics has an option of closing by the password компрессируемых the data. However it has no physical possibility to cipher this password the file usually having the sizes in some honeycombs mbyte, therefore it is limited to very weak algorithm and stores hesh-function from the password together with the protected data. The size криптостойкости¹ this function has been investigated and it has appeared equal 2⁸, i.e. the password can be opened is trivial.

Export restrictions

It is the reason connected with export криптоалгоритмов or with necessity to get the patent or the rights to them. In particular, from the USA export криптоалгоритмов with length of a key more than 40 бит² is forbidden. It is obvious that such криптостойкость cannot be considered reliable at modern computing capacities and even on the personal computer, having put speed of search in 50 000 passwords/sek, we will receive search time on the average an order of 4 months.

Known examples of the programs subject to export restrictions are last versions of browsers (browser) the Internet, in particular Netscape Navigatorфирмы Netscape Communications and Internet Explorer firms Microsoft. They give enciphering with a 128-bit key for users in the USA and with a 40-bit key for all the others.

Also last version of archiver ARJ 2.60 known for the weak algorithm of enciphering of archives gets to this group. Now users in the USA can use криптостойкий algorithm of GOST. Comedy of a situation that though this algorithm is Russian, even Russians under laws of the USA all the same cannot take advantage of it in program ARJ.

Use own криптоалгоритмов

Ignorance or unwillingness to use known algorithms - such situation as it is paradoxical, also takes place to be, especially in programs of type Freeware and Shareware, for example, archivers.

As it was already told, archiver ARJ (to version 2.60 inclusive) uses (by default) very weak algorithm of enciphering - idle time гаммирование. It would seem that in this case its use is admissible, since архивированный the text should be absolutely неизбыточен and statistical methods криптоанализа here do not approach. However, after more detailed studying it has appeared that in архивированном the text is present (and it appears fair for any archivers) some not casual information - for example, the table of Haffmana and some other office information. Therefore, precisely knowing or having predicted with some probability value of these office variables, it is possible to define with the same probability and corresponding symbols of the password.

Further, use of weak algorithms often leads to success of attack on a clear text. In case of archiver ARJ if to the malefactor one file from the ciphered archive is known at least, it with ease will define the password of archive and will take therefrom all other files (криптостойкость ARJ in the presence of a clear text - 2⁰!). Even if any file in not ciphered kind is not present, all the same idle time гаммирование allows to reach speeds of search in 350000 passwords/seconds by the car of class Pentium.

The similar situation takes place and in a case with popular programs from Microsoft Office - for password definition there it is necessary to know only 16 byte of a file.doc or.xls then enough to touch only 2⁴ variants. In Microsoft Office 97 considerable improvements of algorithms of enciphering therefore there was a possibility only full search are made, but... Not everywhere - MS Access 97 uses the primitive algorithm, and the data, and the password by operation XOR with the fixed constant are ciphered not!

In network OS Novell Netware of firm Novell (the version 3.х and 4.х) own algorithm хэширования also is applied. On an input hesh-function receives 32-byte value received from the original password of the user by or compression of the password in length more of 32 symbols by means of operation XOR, or reproduction of the password in length less than 32 symbols; and on an exit - 16-byte hesh-value (Hash16). It (for Novell Netware 3.х) is stored in a database of sheaves (bindery) in the form of property "PASSWORD".

One of the basic properties криптостойкой hesh-functions should be that it should not suppose easy construction of collisions (that function crypt (), used in UNIX which is based on DES), for example, is. This property is broken in the hesh-function applied in Novell Netware.

Procedure which of the given hesh-value by small search (some seconds by the class car 80486DX2-66) receive 32-byte sequence which, of course, is not the true password has been constructed, but nevertheless is perceived Novell Netware as that since application to it of hesh-algorithm, gives out available hesh-value in accuracy.

The considered hesh-algorithm remained and in 4 versions Novell Netware.

In turn, firm Microsoft also has the most serious lacks of the basic hesh-algorithm applied in all OS, since Windows 3.11, at аутентификации in local (report NetBIOS) and global (reports CIFS and http) the networks, named LM (Lan Manager)-hesh [4]. (However, Microsoft that he remained still since OS/2 and that developed him IBM refers).

It is calculated as follows:

1. The password turns to a 14-symbolical line by or отсечки is ill long passwords, or addition of short passwords with zero elements.
2. All symbols of the bottom register are replaced with symbols of the top register. Figures and special symbols remain without changes.
3. The 14-byte line breaks on two seven-byte half.
4. Using each half of line in a role of key DES, with it the fixed constant is ciphered, receiving on an exit two 8-byte lines.
5. These lines merge for creation of 16-digit value of hesh-function.

It is obvious that attacks on Lm-hesh easily achieve success for following reasons:

• Transformation of all symbols to the top register limits and without that a small number of possible combinations for everyone (26+10+32=68).
• Two seven-byte "half" of password хэшируются it is independent from each other. Thus, two half can steal up search independently from each other, and the passwords, which length exceeds seven symbols, not more strongly, than passwords with a length seven symbols. Thus, for the guaranteed finding of the password it is necessary to touch instead of 94⁰+94¹ +... 9414 ~4^10²⁷ only 2 ^ (68⁰+68¹ +... +68⁷) ~1^10¹³ (i.e. almost in 10¹⁴ times it is less) combinations. Besides, those passwords, which length does not exceed seven symbols, very simply to distinguish, as second half хэша will be the same value AAD3B435B51404EE, the fixed constant received at enciphering by means of a key from seven zero.
• There is no element of chance (salt) as it is made in crypt () - two users with identical passwords will always have identical values of hesh-function. Thus, it is possible to make in advance the dictionary хэшированных passwords and to carry out search of the unknown password in it.

In spite of the fact that in this case are applied криптостойкие or the certificated algorithms, this group of the reasons leads to safety infringements криптосистем because of their wrong realisation.

Reduction криптостойкости at key generation

This reason with rather numerous examples when криптосистема or cuts off the password of the user, or generates from it the data having smaller quantity bit, than the password. Examples:

1. In many (old) versions UNIX the password of the user is cut off to 8 byte before хэшированием. It is curious that, for example, Linux 2.0, demanding from users of input of the passwords containing necessarily the letters and figures, does not check, that the 8-symbolical beginning of the password also consisted of letters and figures. Therefore the user, having set, for example, reliable enough password passwordIsgood19, it will be rather surprised, having learnt that the hacker was included into system under his name by means of the elementary password password.
2. Novell Netware allows users to have passwords to 128 byte that gives (including Latin letters without the register, figures and спецсимволы) 68128 ~2⁷⁷⁹ combinations. But thus, first, hesh-function (see above) receives on an input only 32-byte value that limits effective length of the password in the same size. Moreover, secondly, on an exit hesh-value has length of only 128 bits that there correspond 2¹²⁸ combinations. It in addition reduces effective length to
=21 символа³, i.e. in 6 times in comparison with the initial.
3. Completely the similar situation occurs to archiver RAR of versions 1.5x - the choice of the password of more than 10 symbols does not lead to growth of time necessary on its opening.

If the length of the password "from above" in this case is defined by realisation криптоалгоритмов restriction on length "from below" is already connected with concept of unit of the information or entropy. In the considered example with Novell Netware for creation of hesh-value with entropy of 128 bits the length of the password should be not less than =69 бит⁴ or not less than 22 символов⁵. That many криптосистемы do not limit the minimum length of the password, just and leads to success of attacks by search not keys, and passwords.

Absence of check on weak keys

Some криптоалгоритмы (in particular, DES, IDEA) at enciphering with specific keys cannot provide due level криптостойкости. Such keys name weak (weak). For DES it is known 4 weak and 12 semiweak (semi-weak) keys. And though the probability to get to them equals ~2^10^-16, for serious cryptographic systems to neglect to it it is impossible.

Capacity of set of weak keys IDEA makes not more is better than less - 2⁵¹ (however, that all keys 2¹²⁸, the probability to get to it in 3^10⁷ times is less, than at DES).

Insufficient security from РПС

РПС (destroying software) are computer viruses, Trojan horses, program bookmarks, etc. the programs, capable to intercept a confidential key or нешифрованные the data, and also simply to change algorithm on некриптостойкий. In case the programmer has not provided sufficient ways of protection from РПС, they are easily capable to break safety криптосистемы. Especially it is actual for the operating systems which do not have built in protection frames or means of differentiation of access - type MS DOS or Windows 95:

1. Password interception. As an example it is possible to result the oldest way of abduction of the password, known since the big COMPUTERS when the program - "phantom" emulates OS invitation, suggesting to enter a name of the user and the password, remembers it in some file and stops work with the message "Invalid password". For MS DOS and Windows there is a set of bookmarks for reading and preservation of the passwords keyed (through interception of corresponding interruption), for example, at work of the utility v. 6.0.
2. Substitution криптоалгоритма. An example of realisation of this case is the bookmark masked under the applied program - "accelerator" of type Turbo Krypton. This bookmark replaces algorithm of enciphering of GOST 28147-89, a realised payment "Krypton-3" (a demonstration variant), another, simple and it is easy дешифруемым algorithm [1].
3. The Grecian horse in e-mail. As last example serves attempts of penetration of the Grecian horse taking place in June, 1998 through e-mail. In the letter the pornographic picture and an EXE-file FREECD.EXE which for that time while the user had a good time with the letter, deciphered passwords on connection with the provider (Dial-Up) has been enclosed and sent them on the address ispp@usa.net.

Dependence presence in time of processing of keys

It is rather new aspect of not enough correct realisation криптоалгоритмов, considered in article [2]. There it is shown that many криптосистемы unequally quickly process the different entrance data. It occurs as because of equipment rooms (different quantity of steps on operation, hit in a processor cache, etc.), and the program reasons (especially by program optimisation on time). Time can depend as on an enciphering key, and (races) of the ciphered data.

Therefore the malefactor, possessing the detailed information on realisation криптоалгоритма, having the ciphered data, and being capable somehow to measure time of processing of this data (for example, analyzing time of sending of packages with the data), can try to try a confidential key. In work tactics of attacks to the systems realising algorithms RSA, by Diffi-Hellmana and DSS is in detail described, and the key can be received, specifying bit behind bit, and quantity of necessary measurements of time in direct ratio to length of a key.

And though yet it was not possible to finish these researches to concrete result (to calculate a confidential key), this example shows that programming of systems of critical appointment (including and криптосистем) should be especially careful and, probably, for this purpose it is necessary to apply special protective methods of programming and specialised means of working out (especially compilers).

Errors in program realisation

Clearly that while programs will be written by people, this factor will always take place. A good example - OS Novell Netware 3.12 where, despite thought over enough system аутентификации at which, under firm Novell statements, "нешифрованный the password is never transferred on a network", it was possible to find an error in the program v. 3.76 at which the password in an open kind gets to one of network packages. It it is not observed neither with earlier, nor with later versions of this program that allows to speak about purely programmer error. This the error is shown only if супервизор changes the password to someone (including to itself). Probably, somehow the keyboard buffer gets to a network package.

Presence of hatches

The reasons of presence of hatches in криптосистемах are obvious: the developer wishes to have the control over the information processed in its system and leaves for itself possibility to decipher it, without knowing a key of the user. Probably also that they are used for debugging and for any reason are not cleaned from an end-product. It is natural that it becomes sooner or later known to big enough circle of persons and value such криптосистемы becomes almost zero. The most known examples here are AWARD BIOS (to the version 4.51PG) with its universal password "AWARD_SW" and СУБД Paradox firms Borland International, also having "superpasswords" "jIGGAe" and "nx66ppx".

Closely presence of hatches in realisation (it is obvious that in this case they use obviously unstable algorithms or store a key together with the data) is adjoined by the algorithms which are giving the chance to the third party to read the ciphered message as it is made in sensational project CLIPPER where as the third party the state acts, always loving to pry into secrets of the citizens.

Random-number generator lacks (ДСЧ)

Good, математически checked up and correctly realised ДСЧ also it is important for криптосистемы, as well as good, математически proof and correct криптоалгоритм, differently its lacks can affect the general криптостойкость systems. Thus to modelling ДСЧ on the COMPUTER usually apply gauges of pseudo-random numbers (ПСЧ), characterised by the period, disorder, and also necessity of its initialization (seed). For криптосистем in general it is impossible to recognise application ПСЧ as the successful decision, therefore good криптосистемы apply to these purposes physical ДСЧ (a special payment), or, at least, develop number for initialization ПСЧ by means of physical sizes (for example, time of pressing for keys the user).

The small period and bad disorder concern mathematical lacks ДСЧ and appear in the event that for any reasons gets out own ДСЧ. In other words, the choice own ДСЧ as is dangerous, as well as a choice own криптоалгоритма.

In case of the small period (when the pseudo-casual values developed by the gauge, less, than possible values of a key) the malefactor can reduce time of search of a key, touching not keys, and pseudo-casual values and generating from them keys.

At bad disorder of the gauge the malefactor also can reduce average time of search if will begin search with the most probable values of pseudo-random numbers.

The most widespread error shown and in case of good ПСЧ, its wrong initialization is. In this case the number used for initialization, has or smaller number of bats of the information, than the gauge, or is calculated from not casual numbers and can be predicted stand or other degree of probability.

Such situation took place in program Netscape Navigator of version 1.1. It initialized ПСЧ, using current time in seconds (sec) and micro seconds (usec), and also process identifiers (pid and ppid). As researchers J.Goldberg and D.Wagner have found out, at such scheme as a maximum 47 meaning bits of the information (thus turned out that this gauge was used for reception 40 or 128 (!) - bit keys). But, if at the malefactor

1. There was a possibility to intercept the packages transferred on a network; and
2. There was an access (account) on the computer where the program is started,

That for it did not make work with the big degree of probability to learn sec, pid and ppid. If the condition (2) was not satisfied, the malefactor all the same could try to establish time through network demons time, pid could be received through demon SMTP (usually it enters in the field Message-ID), and ppid or not strongly differs from pid, or in general it is equal 1.

Researchers have written the program unssl which, touching micro seconds, found a confidential 40-bit key on the average for a minute.

This group of the reasons leads to that appears unreliable криптостойкие and correctly realised algorithms.

Small length of a key

It is the most obvious reason. There is a question: how proof криптоалгоритмы can have small length of a key? Probably, owing to two factors:

1. Some algorithms can work with variable length of a key, providing different криптостойкость - and the problem of the developer to choose necessary length, proceeding from wished криптостойкости and efficiency. Sometimes on this desire other circumstances - such, as export restrictions are imposed also.
2. Some algorithms were developed rather for a long time when the length of a key used in them was considered more than sufficient for observance of the necessary level of protection.

Algorithm RSA for which opening it is necessary to solve a problem факторизации at first has faced sharp jump of productivity of computer facilities. In March 1994 has been finished lasting during 8 months факторизация numbers from 129 figures (428 бит⁶). It has been for this purpose involved 600 volunteers and 1600 cars connected by means of e-mail. Spent machine time was equivalent approximately 5000 MiPs-let⁷.

Progress in the problem decision факторизации is in many respects connected not only with growth of computing capacities, but also with occurrence recently new effective algorithms. (On факторизацию following number 130 figures has left only 500 MIPS-years). For today basically it is real факторизовать 512-bit numbers. If to recollect that such numbers still were used recently in program PGP it is possible to assert that is the most quickly developing area of cryptography and the theory of numbers.

On January, 29th 1997 firm RSA Labs had been declared competition on opening of symmetric algorithm RC5. The 40-bit key has been opened in 3.5 hours after the competition beginning! (For this purpose at all it was not required to connect computers through the Internet - the local network from 250 cars at Berklevsky university) has sufficed. In 313 hours the 48-bit key has been opened also. Thus, all it became obvious that the length of a key satisfying to export restrictions, cannot provide even the minimum reliability.

In parallel with opening RC5 the call and to a pillar of the American cryptography - to algorithm DES having a key in 56 bits has been given. And it has fallen on June, 17th, 1997, in 140 days after the competition beginning (it has been thus tested about 25 % of all possible keys and are spent approximately 450 MIPS-years). It was certainly outstanding achievement which meant actual death DES as the enciphering standard. And it is valid, when in the beginnings of 1998 following competition on a finding of key DES has led to success of all for 39 days, the national institute of standards of the USA (NIST) declared competition on the statement of new standard AES (Advanced Encryption Standard). AES should be completely open symmetric algorithm with a key in the size 128, 192, 256 bits and the block of enciphering in the size of 128 bits.

Erroneous choice of a class of algorithm

It also rather widespread reason at which the developer chooses let and good, but absolutely improper algorithm to its problem. It is a choice of enciphering instead of хэширования or a choice of symmetric algorithm instead of algorithm with open keys more often.

Examples here the weight is almost all programs limiting access to the computer by the password at its inclusion or loading, for example, AMI BIOS, storing instead of хэша the password its ciphered variant which, will naturally, easily be decoded.

In all network procedures аутентификации it is natural to apply dissymetric cryptography which will not allow to try a key even at full interception of the traffic. However such algorithms (from network OC) while realises only Novell Netware 4.x, the others are content (at the best!) the standard scheme "inquiry-response" at which it is possible to conduct fast enough search on the intercepted values of "inquiry" and "response".

Repeated imposing of scale of the code number

Vulnerability in Windows 3.x and the first versions Windows 95, connected with enciphering became already classical example. In this case programmers of firm Microsoft, well-known knowledge in the field of safety, applied algorithm RC4 (representing that other as enciphering гаммированием), without changing scale, some times to the different data - to the network resources stored in files of type.pwl.

It has appeared that one of file data sets.pwl was more than the specific text - a 20-symbolical name of the user (in the top register) and a set of indexes on resources (fig. 2 see). Thus, having guessed it the user (which in most cases besides coincides with a file name) it is possible to calculate at least 20 byte of scale. Since the scale does not vary at enciphering of other resources (in it the basic error of application RC4 in this case consists), can be calculated the first 20 byte of all resources which include length of each of them. Having calculated length, it is possible to find values of indexes and by that to add some more tens byte to the guessed scale. This algorithm is realised in the known program glide.



In any critical system of an error of the person-operator are almost the most expensive and extended. In a case криптосистем nonprofessional actions of the user bring to nothing the most proof криптоалгоритм both its most correct realisation and application.

First of all it is connected with a choice of passwords. It is obvious that short or intelligent passwords are easily remembered by the person, but they are much easier for opening. Use of long and senseless passwords certainly is better from the point of view криптостойкости, but the person usually cannot remember them and writes down on a piece of paper which then either is lost, or comes into the hands to the malefactor.

Last years a lot of attention is given to the permission of this contradiction, but the recommendation for choice good passwords are beyond this article.

From this that unsophisticated users usually choose either short, or intelligent passwords, exist two methods of their opening: attack by full search and attack under the dictionary.

From communication with sharp growth of computing capacities of attack by full search make much more chances of success, than earlier ("the Small length of a key" see also). If for system UNIX function crypt () which is responsible хэширование passwords, has been realised so that was carried out almost 1 second on the car of class PDP for twenty years speed of its calculation has increased in 15000 times (!). Therefore if earlier hackers (and developers who have limited length of the password to 8 symbols) and could not imagine full search today such attack on the average will lead to success for 80 дней⁸. Speed of search of passwords for various криптосистем is resulted in tab. 1.

From the moment of the beginning of a writing of this article in 1996 position in application of means of cryptography in applied programs undoubtedly changes for the better. Gradually developers realise necessity of application of the proved algorithms, positions of some countries in an export question криптоалгоритмов move off dead centre, with большей in the length of a key and efficiency new algorithms and standards are developed for realisation on all types of processors, from 8-bit to RISC.

Nevertheless, there is a huge precipice between level of firmness and reliability existing now ON, applying криптоалгоритмы in which till now there are "children's" holes (last example - realisation PPTP from Microsoft [4]) and that level криптостойкости which show last, independently analysed conducting криптоаналитиками algorithms and reports where serious vulnerability that is considered, for example, that demands 2⁶⁵ blocks of a text in code and then 2⁵⁸ searches of variants or one clear text ciphered 2³³ different, but keys dependent from each other and then complexity of the analysis, equal 2⁵⁷ [5].

It would be desirable to hope that the future realisations and application of these algorithms will keep so high degree of their reliability.

It is possible to allocate 4 basic groups of causes of unreliability of cryptographic systems: application of unstable algorithms, wrong realisation or application криптоалгоритмов, and also the human factor. The accurate parallel between them and causes of infringement of safety of computing systems is thus visible.

Because of the described reasons there are problems in safety for all classes of the software products, using криптоалгоритмы, whether it be operating systems; криптопротоколы; clients and a server, their supporting; office programs; the user utilities of enciphering; popular archivers.

Competently to realise own криптосистему, it is necessary not only will familiarise with errors of others and to understand the reasons on which they have occurred, but also, probably, to apply special protective receptions of programming and specialised means of working out.

^{1 Under криптостойкостью the quantity of variants for a finding of a key will be understood by search hereinafter.}

² It was until recently. Now - 56 bits.

³ [] - the whole part (the nearest whole from below).

⁴] [- the nearest whole from above.

⁵ it is clear, as here and in an example the same numbers above turn out, but at the expense of a rounding off every which way there is a difference in 1 symbol.

⁶ that approximately corresponds to 56 bits for symmetric algorithms.

^{7 million} instructions a second in a current of year.

⁸ Using special payments or распараллеливание, this time can be reduced by some usages.

⁹ :-)

1. The theory and practice of maintenance of information safety. Under Zegzhdy P. D's edition - М, Yacht changes, 1996.

2. P.Kocher. The time analysis of realisations of Diffi-Hellmana, RSA, DSS and other systems

3. Mark W. Eichin, Jon A. Rochils. With Microscope and Tweezers: An Analysis of the Internet virus of November 1988.

4. B.Shnajer, P.Mjudzh. Криптоанализ report PPTP from Microsoft.

5. Eli Biham, Lars R. Knudsen. Cryptanalysis of the ANSI X9.52 CBCM Mode. Proceedings of Eurocrypt ' 98.

Bapichev Sepgej. Kpиптогpафия without секpетов.

Bruce Schneier. Why Cryptography Is Harder Than It Looks