Technical White Paper Discussing
Key Length vs. Time to Break
Introduction:
Recent articles have entertained the notion that typical 40-bit key length key generator algorithms used in some network-based encryption algorithms are susceptible to penetration with computer assets costing (in US$) $10,000 and using 25 Field Programmable Gate Array chips within twelve (12) minutes.
A similar argument in the same article was waged against the 56-bit DES algorithm with an investment versus time-to-break ranging between:
| Investment | Time to Break |
| $10,000 | 18 months |
| $300,000 | 19 days |
| $300,000,000 | 12 seconds |
Assuming the above critical assessments of brute force hardware FPGA analysis plus state-of-the-art computers is correct, the vulnerability of a simple key stream generator can be interpolated allowing a factor of two in time for each additional bit added in the key.
Technical Discussion:
Unfortunately for the Code Breaker (and fortunately for the user of high quality cryptographic devices), the ability to extract keys from captured encrypted data traffic is actually very difficult with any reasonable amount of hardware and processing time for the following reason: The success of breaking "captured data streams" through brute force analysis assumes that the original data has a sufficiently predictable format as to allow recognition of the pattern as actual Plain Text data. The FPGAs noted above would be looking for predictable characteristics, (e.g., ASCII characters which appear often in text files) for each and every possible key combination 2n (where 'n' is the number of bits per key). When the total number of bits in the key increases, the task of brute force analysis increases (doubles) with each bit added to the key.
The advantages gained from using high quality cryptographic products (like TCC's Voice and Data Encryption devices) is that the key lengths and possible key combinations are much greater than the examples noted in the analysis above. The attack of a simple 40-bit system, or even a 56-bit system like DES is already extremely costly, and success cannot necessarily be guaranteed. The products sold by TCC have much greater key lengths, and as a result are highly unlikely to be seriously challenged by any foreseeable technological threat.
In general terms, the ability to analyze, and ultimately break a key stream back to its root 'key' is dependent upon a number of factors, including:
- The length of the 'Key Stream Cycle' (the number of bits that are to be generated before the key stream generator's output would repeat). The cycle length is determined by the effective length of the shift registers assuming optimized feedback interconnections between the shift registers. Optimally, the shift registers are combined in such a manner to provide the maximum key stream length, i.e., the product of the two (or more) shift registers' individual cycle lengths.
- The total number of 'seed' input combinations to the key stream generator, or the number of bits in the key (or keys) including any initialization parameters or 'vectors'. These vectors have the effect of changing the starting point in the key stream cycle, and therefore the output key stream itself.
- The degree of 'non-linearities' placed within the shift registers' key stream cycle (appropriate) 'jumps' within the key stream cycle that are mathematically independent from the key stream's shift registers' structure).
- Code stream 'visibility' or the amount of time, i.e., the number of key stream bits that a key stream generator's output (for a selected key, plus its initialization vector) is available to be captured and analyzed. Since the transmitted 'encrypted traffic data stream' is generally a combination of the key stream generator's output, ('Exclusive ORed' with the Plain Text message traffic) the practical use of any viewable encrypted traffic data stream is limited by any predictable characteristics of the plain text message traffic, that when combined with the key stream, makes up the viewable traffic.
- The length of time the selected key is in use ('Key Period') and the length of time between re-initializations when the randomly-generated Initialization Vector or IV (sometimes referred to as a "message key") is exchanged.
Obviously, if a key length is relatively long and very non-linear, and the period of its use is relatively short, the ability of the code breaker to compromise a key is greatly limited regardless of the amount of computer assets and parallel processing is available. Further complexities are added when any initialization vector changes during the period of key stream analysis (between actual key changes) which effectively forces a re-start of the entire analysis operation.
Conversely, the "worst case" would then appear to be where a single key of short length (i.e. less than 50 bits) is used continuously (no re-synchronization) with little or no non-linearities, with very predictable plain text data patterns.
TCC'S PRODUCTS:
TCC's data encryption algorithms are highly secure. They not only use key stream cycles of extreme length, they incorporate rapidly changing non-linearities that preclude the effective use of any know linear cyclic key stream analysis techniques. The 'starting point' of the non-linear key stream generator is also changed by periodic key changes and by random 'initialization vectors'.
The CipherX® series of encryptors use key lengths of at least 56-bits (the CipherX 5000A DES model), and typically use keys lengths of much greater lengths (the CipherX 850 using TCC's HyperCryptTM or TEALTM algorithms using 128-bit Local keys with 8,192-bits of System key) and can store up to 800 different Local Keys supporting frequent key changes 'painlessly'. The CipherX 8000 High Speed data encryptor, when using the SNARKTM algorithm, uses 128-bit Data Encryption Keys (DEKs). The new CipherX 7100 and CipherX 7200 Frame Relay and IP encryptors use Triple DES encryption for each virtual circuit and for all authentication and crypto handshaking.
The high speed TCC bulk encryptor DSD 72A-SP (using its SNARKTM algorithm) has a key length of 128 bits (120 bits of Local key plus 8 bits of Network key) and can also store up to 800 different Local Keys.
The DSP 9000-series of voice encryptors use a combination of 64-bits of Local key, 16-bits of Network key and 4,096-bits of System key providing over 10
Copyright© 1996 Technical Communications Corporation
CipherX®, SNARKTM, TEALTM, and HyperCryptTM are all
trademarks of Technical Communications Corporation