Choices

Choices

The developer of a secure application is often faced with many important decisions. Not least among these is which cryptographic algorithms the application should use. For example, which block cipher should the application use, DES or AES? Which encryption mode, CBC or CTR? Which message authentication code, CBC-MAC or HMAC? Which asymmetric algorithm, RSA, elliptic curve, NTRU, or something else? Although prescribing a precise formula for picking a cryptographic algorithm (protocol or primitive) is impossible, this section informs the developer of the available options so that she can make an educated decision.

When selecting a cryptographic algorithm, the developer must take several aspects of that algorithm into consideration:

         The algorithm's intended purpose

         The algorithm's performance

         The algorithm's effectiveness at accomplishing its intended purpose

         External regulations (for example, export laws or existing patents)

We have already discussed the intended purpose of various algorithms and protocols in previous sections; external regulations we leave to the more politically inclined. Therefore, in the following sections we will provide some additional information on performance and effectiveness.

Performance

Different applications have different performance requirements. The presence of these various performance requirements means that certain algorithms are desirable in different situations. For example, some algorithms are incredibly fast in hardware but slow in software (and vice versa). Other algorithms are fast on certain processors (for example, processors with integer multipliers) but slow on others. Some encryption algorithms can change keys quickly but have slow encryption speeds (such algorithms might be suitable for high-speed cryptographic routers that must simultaneously handle many secure channels).

Some algorithms are also faster in one direction than another. For example, the RSA signature generation algorithm is slow, but the RSA signature verification algorithm is incredibly fast, as you can see in Table 6.2. This table is taken from the article "Performance Comparisons of Public-Key Cryptosystems," by M.J. Weiner, in CryptoBytes, 4(1), 1998. The performance measurements are milliseconds on a 200MHZ Pentium Pro.

In addition to speed, there are space considerations. Elliptic curve implementations can take up less space in dedicated hardware and are less network-intensive (transmit fewer bits) than RSA. These observations mean that it would be incorrect to argue that one scheme is faster than another. Applications developers must thoroughly understand how their application will use cryptography before deciding on the algorithm best suited for the application.

Effectiveness

The effectiveness or security of a cryptographic algorithm is a measure of that algorithm's resistance to attacks. The more secure an algorithm is, the more effective it will be at preventing an attacker from breaking the message. Unfortunately, quantifying an algorithm's security is a subjective process. There are several reasons for this. First, effectiveness means different things to different organizations and applications. This is exemplified by the fact that financial institution or governmental security requirements are usually much greater than those of most individuals. Thus, different applications will likely have different definitions of security and effectiveness. (For example, a government organization might require 2,048-bit RSA keys, whereas a normal user might find 1,024-bit RSA keys quite effective.)

Table 6.2. Performance Comparisons of Asymmetric Key Protocols
Operation	1,024-Bit RSA	1,024-Bit DSA	168-Bit ECDSA
Signature generation	43	7	5
Signature verification	0.6	27	19
Key generation	1,110	7	7

Another problem with measuring the security or effectiveness of an algorithm is that an algorithm's effectiveness typically decreases over time. For example, as the speed of hardware increases (and the price of hardware decreases), the time (and money) necessary to run a single attack algorithm will decrease. If brute-forcing a 56-bit DES key today takes two days, then, after the speed of computer hardware doubles, it should take only one day, using equivalently priced hardware. Furthermore, new advances in cryptanalysis may yield more efficient attacks. These factors must be considered in evaluating a potential cryptographic solution against the data protection requirements: Some applications require that their information remain protected for years (such as wills and contracts), whereas other applications require that their information remain protected for only a short time (such as instructions for a negotiation occurring that afternoon).

Table 6.3 presents the suggested key length for a specific class of primitives. This table is taken from the article "Selecting Cryptographic Key Sizes," by A.K. Lenstra and E.R. Verheul, in The Journal of Cryptology, 2001. Recall that the key length of an algorithm is one measure of that algorithm's security. The primary assumption underlying the data in Table 6.3 is that DES offered an appropriate level of security in 1982. We recommend consulting the source of Table 6.3 for different baselines and the rate with which hardware speeds and cryptanalytic attacks will improve. We want to state that Table 6.3 does not provide our suggested key lengths for the differing algorithms. It is simply meant as a comparison between different algorithms. As previously stated, the security required is dependent on the application and environment in which it must operate.

Table 6.3. Sample Minimal Acceptable Key Lengths (in Bits) per Year
Year	Symmetric Key Size	Hash Size	RSA and TDL Key Size	RSA and TDL Key Size*	Elliptic Curve Key Size
2000	70	140	952	704	132
2002	72	144	1,028	768	139
2004	73	146	1,108	832	143
2006	75	150	1,191	896	148
2008	76	152	1,279	960	155
2010	78	156	1,369	1,056	160
2020	86	172	1,881	1,472	188
2030	93	186	2,493	2,016	215

Decision Trade-Offs

Application developers are often unable to choose an algorithm (or key size) simply for its security. Rather, application developers often must accept a compromise between security and performance. Unfortunately, what that compromise should be is often unclear (especially considering that it is impossible to ascertain fully the security of most cryptographic algorithms).

Of particular concern to most wireless developers is which asymmetric system to use (RSA, elliptic curves, NTRU, XTR). This is an extremely difficult decision, and one which the cryptographic community appears to be debating still. If the security predictions in Table 6.3 are accurate, the performance observations in the preceding subsection suggest that certificate-based software application (applications that do many certificate verifications) should use RSA and that most other applications (non-certificate-based applications and hardware implementations) should use elliptic curves. Unfortunately, not everyone agrees with the results in Table 6.3.

We have suggested that, when given the choice, you should choose older, more established cryptosystems over newer and flashier cryptosystems. This is because cryptographers tend to understand the security properties of older cryptosystems more than they do newer cryptosystems. This argument holds for the RSA versus elliptic curves debate as well. Because the RSA cryptosystem is older than the elliptic curve cryptosystem, some cryptographers believe that it would be dangerous to assume that elliptic curves will not succumb to future cryptanalytic progress. That is, some cryptographers believe that clever researchers will someday find a flaw with elliptic curve based cryptosystems that allows an attacker to efficiently break any elliptic curve based cryptosystem. Other cryptographers strongly disagree. Although we argue again that predicting the future is impossible, wireless application developers should be aware of this debate and remain abreast of developments involving cryptosystems of interest.