Implementation of Cryptography

Alexander Liss

03/19/98; 03/25/98


Measurement of the Quality of Security System *

Role of Cryptography *

Convenience, Privacy and Security *

Unique Threats *

Negative Publicity *

Mass Attack *

Cryptography and Reliability *

Cryptography in the System Design *

Corrections of Design *

Educated Implementers *

Cryptographic Modules *

Cryptographic Protocols *

Internal Clarity and External Obscurity *

Random Deployment *

Random in Cryptography *

Cryptography had moved from the obscure word of Intelligence and Military and rudimentary use in Banking to wide use in different commercial applications. This produced a lot of new questions. One of these questions is - How do we implement advanced Cryptography in the commercial application? Or more precisely - What are main differences in the design of Security System, which uses Cryptography, from other familiar System designs?

This area of design is very young and by its nature secretive. It is difficult to find general recommendations how it has to be done and there are a lot of misconceptions in part of designers and managers.

We address this subject here.


Measurement of the Quality of Security System

There is a lot of misunderstanding in the field of Security in the part of management who has to oversee the development of the Security System. The most annoying one is the notion of 100% security. This is not a new problem: when reliability became a subject of attention it was a talk about absolutely reliable systems, when the quality of production became the focus of attention - we had "no defects" talks. All this is not innocent even as a slogan because it produces thought patterns with dangerous consequences. If we have 100% reliability of parts we do not need costly system of reservation. If we have no production defects we do not need costly post-production testing. If we have 100% security we do not need to monitor the state of the art in the methods of System penetration, we do not need to introduce costly changes into the Security System, we do not need costly around the clock monitoring of the attempts of the System penetration. All these fallacies are very attractive to managers, and they start with "100%" misconceptions.

There are two ways to assess the quality of Security System.

Some parts of the System we can make so strong that we know for sure, that the attacker will not go against them, when there are substantially weaker parts of the System open for the attack. In majority of cases we know the value of parameters of cryptographic routines (usually sizes of keys) which make them unreachable for the certain level of attackers and very costly for attackers of the highest level (with better knowledge and resources).

The rest of the Security System can be judged from the following point of view - how much does it cost to penetrate it? The System designer has to keep this cost much higher than potential benefits of its penetration.

In majority of cases the security of the well designed System relies on people, who maintain it. Honestly, we would not feel comfortable with anything, which does not rely on people - who knows what kind of misuse of such system is possible.

The introduction of the computer networks and intense communication into the core of the business activity produced many new security threats, which did not exist before, and where a little experience is available. The main goal of the design of the Security System employing Cryptography is closing security holes in these new areas and reducing the security management problems to the familiar areas, areas where security relies on people.

In the world of networks and databases Cryptography can help in achieving the level of security comparable to the level achievable in small carefully managed organizations.


Role of Cryptography

The designers of Security Systems are in the lucky position - there is already a developed scientific field - Cryptology. It is young, but many bright people applied their skills in it, and it achieved a state of some maturity. Results of scientific research are rich source of concepts and methods, which can be used in practical applications. Here, as in other areas, only simplest and roughest methods are really applied, however the very presence of developed scientific results give system designers a sure footage in their work.

While cryptological research is rightfully focused on the Cryptography itself - strength of cryptographic routines, presence of possibilities of sending unauthorized information alongside with authorized one (subliminal channels), etc., practical implementation needs to take in consideration all other factors of the use of Cryptography in real Systems. System designer has to state clearly where and how the task of protection of the information is divided between Cryptography, Law and general Civility of the Society.

Cryptographic protection of the information is inexpensive. Hence, everywhere it is possible, it is reasonable to move the task of protection of information to Cryptographic protection. However in many cases the very presence of cryptographic protection gives a false sense of security. Hence it is important to state clearly where we rely on non-cryptographic methods.

Sometimes this clear description alone allows to see the holes in security. For example, there are cases when the transmission of credit card number is encrypted, but the database of this numbers stored by the merchant can be easily accessed from outside.

As in any situation when the science meets application, we have different goals in scientific research (perfect, advanced, logical results) and application (simple methods, which do the job). Actually, basic ideas of Cryptography needed for the applications and really simple, and can be learnt in the short time. However the implementation can be tricky. Cryptography is in the perpetual process of development, hence involvement of specialists in the design and implementation of Cryptography is mandatory.


Convenience, Privacy and Security

The first impulse when one tries to consider the interplay between these three phenomena - Convenience, Privacy and Security, is that Security is first. However the life is complex and there is no simple solution here, as in many other areas.

Let say, that the designer of Security System neglects Convenience. The designed knows tools of security employed by intelligence and military and employs them in the business. Tools as passwords, which have to be random combinations of letters and numbers. They work fine with spies - their life depends on these passwords and they never write them down. Move the same idea in the business word and you have passwords, which are practically always written down somewhere and they are not random and can be broken with the dictionary search. This is a flaw of the System design. Convenience is important for the business security.

Let say, that the designer of the Security System neglects Privacy of employees. Security System usually collects a lot of information about employees' activities. If it is stored, this can be much more interesting piece of information for the attacker than the information, which Security System protects. If it is given to managers, the employees will cheat the Security System to avoid punishment, and there is no Security System, which can work properly in these conditions. If privacy of clients is not protected and this become known (it always does), then clients move their business elsewhere.

At least one problem - inconvenient passwords, is easy to fix. People’s memory is very good with semantics and very bad with random numbers. Hence the application, which controls the access to the System, should ask for the pass-phrases, which can be long. Also, they can incorporate in it the name of the System, the month of last pass-phrase change, etc. to make it vary and to be covenant in the same time. The application has to hash it and pass along only the short hash. The change of one symbol in the pass-phrase produces completely different hash value. People can be very innovative with pass-phrases, and they will be. In addition it is possible to mutate the hash function, for example changing its key.


Unique Threats


Negative Publicity

Discussion of Cryptography in the press is fashionable. There are many reasons why. It is an area of rapid business development. Also it is an area where the boundaries of authority between the government, business and general public are in the process of redrawing. The hype is greatly multiplied by the ignorance of the general public and many reporters. Any innocent event in this area can produce a lot of publicity, which can actually hurt the business. This leaves little room for the "allowed failure" - the failure of cryptographic measures which actually does not decrease the level of security, for example because something was not intended to be protected. Ordinary, such places of "allowed failure" are convenient places for the traps, which allow the detection of tampering attempts. However we do not have this luxury with Cryptography - any uncovered by hackers "allowed failure" can become a customer relations nightmare.


Mass Attack

Cryptography is too new subject in the society, and the boundaries between what is allowed to do and what is immoral or illegal are still fuzzy. The same person, who would not think to forge a check, might try to play with the bank security protected with Cryptography. This produces a unique threat, when some electronic trick can be published on Internet and tried by many customers, for example because it speeds the communication. System designers rarely keep in mind this fact. However this kind of attack can have serious consequences. It can produce a System overload and as a result the breach of some layers of Security System. Also it can produce a gradual degradation of the level of security in some distributed Systems.


Cryptography and Reliability

The needed level of reliability of Cryptographic Elements in the System is determined the same way the needed level of reliability of any Security Elements of the System is determined. This is not so difficult to understand, but it is forgotten again and again in the process of the System development, because it is so different. The difference is clear from the following example. If there is an event, which happens once among thousand events, where the system does not perform properly, in many cases we assume that the System works quite fine (probability of the fault 0.1%). However if there is such event, where the Security System does not work properly, then the attacker will recreate it again and again - there is no probabilistic assessment of the reliability of Security System. Implications of this fact are huge: Security System has to be designed and tested differently than other Systems. Particularly failure of Security System is not a reliability event, this is a security event. Practical approaches to solving this problem are redundancy, checking the same condition twice with different methods, and "zero defect" development process (each version of the system has no known defects).


Cryptography in the System Design

The design methods of cryptographic modules of the System are the same, which are generally used in the design of Security System. They came from the experience of designing the system, which

This is similar to the design of the weapon or design of the military defense system. The designer has to use new elements and methods, because he has to compete against new methods of attack. These new elements and methods did not have enough time to be proved theoretically and there is not enough experience of their use. Also, it is similar to the design of the highly reliable system with unreliable elements.

The approach to solving this problem follows common sense.

First, the system has to be presented as a system of modules and methods, each of which is either theoretically studied or successfully used. New modules can be used only as redundant (for double checking, etc.). Each module has to be secure for its function, even when other modules of the system do not function properly. If security of the module cannot be analyzed separately from the rest of the system - this is not a module.

Second, modules should be combined in the system in assumption that they are not sufficiently secure. The same task should be performed by different modules and results compared, and the System should have a layered structure, where the attack on the inner layer can be launched only after the outer layer is penetrated.


Corrections of Design

Corrections of the System design and implementation are elements of normal development, especially in the field, which changes fast, as Cryptography. However, where the security is involved these Corrections could produce serious problems.

This is always a prudent approach to the System design, when Corrections are anticipated: the designer expects certain types of corrections in the future and designs the System in the way, that corrections can be made "locally" - only a few modules of the System are involved. This distinguishes good practical design from amateurish one.

In the Design of Security System this prudent approach practically becomes a requirement. Usually small correction of the System can potentially reduce the reliability of the System, however it can introduce a serious hole in Security System, rendering it useless.

This requirement reinforces one of requirements we formulated above from different point of view: modules of security system should perform their functions securely regardless of functioning of other modules. If module’s activity can introduce security risk in some circumstances, however these circumstances do not happen because of the design of the System, we should avoid the use of this module. The design will be corrected in the future and there is no guaranty that during this correction we are still assured that these dangerous conditions do not happen.


Educated Implementers

The normal approach to the implementation of the design is: divide the work on tasks, assign tasks to implementers, and watch that implementers focus on the work assigned and do not deviate from the design in their desire to improve their part of the design in expense of overall design of the System. This does not work with the implementation of Security System and especially with the cryptographic part of it. Cryptography is a young area, which is changing fast. Many things are not specified in the design documentation but can be found in scientific publications. Some things assumed to be too trivial for the publication and they are not published at all but known in the cryptographic community. This makes good cryptographic knowledge of implementers of cryptography practically mandatory. This high level of special education brings additional benefit - the perpetual informal review of the design of Security System. This is not a theoretical recommendation - there are so many anecdotal cases of stupid mistakes made by implementers with best intentions, only because they did not understand cryptography well enough.


Cryptographic Modules

Design and proper coding of Cryptographic Modules is expensive, hence they are usually reused and not redesigned or coded anew. Hence they have to be flexible - they have to have the ability to switch from one procedure to the other and they have to incorporate the possibility to move to higher levels of security or the possibility of easy addition of new cryptographic procedures. In the same time, for obvious reasons, the coding has to be clear, verifiable, and the code has to be well tested.

These requirements contradict the requirements of efficiency of cryptographic procedures. Efficiency requirements are obvious - Security System always slows down the execution of the System, and there is always a pressure to make this impediment as small as possible. This leads to "fast and dirty" programming with use of clever programming tricks, which speed-up the computation. And this is exactly what should be avoided. Obviously a few crucial modules have to be made as fast as possible, but there is a need in only a few of such modules and they are small. These modules have to be designed and coded separately. The rest should be governed by the principles we pointed above.


Cryptographic Protocols

Cryptographic Protocols - the order of operations, which assures the proper functioning of the cryptographic protection, unfortunately rarely can be separated completely from the rest of the System. However any weakness in the Protocol implementation can be potentially the same damaging as the weakness in basic cryptographic modules. The problem here is: reliability requirements of these modules are equivalent to high security requirements of the System, in the same time they cannot be developed separately.

The solution can be in the strengthening the reliability requirements for the part of the System, which affects these modules. By itself this would not work - low reliability comes from complexity of the project, inexperience of workers, lack of time, etc. and not from the lack of desire to make the System reliable. We need special methods, which allow building of this part of the System more reliable.

Surprisingly enough these tools exist and they are well known. They are special software libraries. Libraries happened to be the most reliable part of the System. They are tested by the heavy use and they are looked at by many programmers who use them. If specialists in programming of the security part of the system control the part of the library, which is used in implementation of Protocols, there is a good chance that this library is developed, tested and maintained with the healthy level of paranoia needed in security.


Internal Clarity and External Obscurity

Attackers have much easier life finding holes in the design of Security System than designers preventing from this to happen. Hence the Security System design has to be simple and clear as possible - it allows logical analysis of the System. From the other hand the designer wants to hide the design as much as possible. Partially this is done with usual secrecy surrounding Security System. Secrecy is an additional layer of protection of the System. However the designer cannot rely on the secrecy - the System should be secure in assumption of pubic knowledge of the design. The assumption is prudent, because, as the history teaches us, exactly the kind of attackers we prefer to keep out of the System - strong attackers, professionals, learn the design of Security System one way or the other.


Random Deployment

There is one powerful way of obscuring the Security System, which is simple, but which is used rarely. The Security System should have parameters with big enough set of possible combinations. The designers and testers of it should not know the actual setting of these parameters - only narrow set of specialists responsible for the Security System should know it. In this case the attacker has to find these settings before the developed penetration tools can be used.

There is a simple approach to designing the System with big set of possible combinations of parameters. First modules of the System should have different variants of deployment. Second the System should be designed in the way, that it allows many combinations of deployment of modules variants.

When we try to apply this recommendation to cryptographic modules, we can run into a problem. If Cryptographic modules are not designed to be independent one from other, and the change in one of them require the analysis and possibly correction of different parts of the System, then we practically cannot apply this approach. Again we arrive to the requirement of independently secure for their function modules.

This approach requires special cryptographic theory, where big classes of Cryptographic methods are described (and can be implemented) uniformly, and their security can be proved uniformly. There is a school in Cryptography, which does it currently. Its distinctive feature - it reduces the proof of the security of the method to the proof that results of its application are impossible to distinguish from random bit array. This gives big variety of methods, which are at least the same secure as some known method.


Random in Cryptography

Modern Cryptography widely utilizes concept of randomness. This has to be well understood, otherwise the implementation of Cryptography can encounter unexpected attacks, for example on key generation or other places, which use random bits.

Scientific concept of randomness is a special model of last resort, which allows the minimal description where all other theories fail. We do not want even to touch here theological or psychological concepts with the same name.

In statistics this model is used to extract some useful information where the other models do not exist or too costly to apply.

In the imitation models (Monte-Carlo method) there are widely used random numbers, which are series if realizations with specific qualities (uniform distribution, no repetition). This allows the use of probabilities theory and construction of special characteristics based on this theory.

In the Cryptography it means "currently unpredictable" or "we do not know how something of this sort can be predicted and we do not foresee the development of the method, which can make it more predictable". There is a silent disclaimer in this statement: it is possible that there are someone or some agency who know more than we know on this subject, and it is possible, that the future can bring some unforeseen development (as it happened many times before).

The concept of random bits is a very useful way of separating what can be proven and hence used freely, and what cannot be proven in principle and hence used cautiously with reliance on specialists-cryptographers.

There is reasoning behind this fear of any patterns in encrypted or hashed message. Cryptoanalysts had proven again and again their ability to exploit these patterns. It seems that human creativity is so powerful, that there is a reason to believe that any pattern in the encrypted message can be exploited by the attacker. Hence there is a strong school of thought in Cryptography that encrypted message should not exhibit any pattern, for the cryptographic method be acceptable by serious cryptographers. In other words - any encrypted message should be indistinguishable from the random array of bits to the outsider, who does not know the key.