Principles of Cryptography
Strength of Cryptographic Algorithms
Good cryptographic
systems should always be designed so that they are as difficult to
break as possible. It is possible to build systems that cannot be
broken in practice (though this cannot usually be proved). This does
not significantly increase system implementation effort; however,
some care and expertise is required. There is no excuse for a system
designer to leave the system breakable. Any mechanisms that can be
used to circumvent security must be made explicit, documented, and
brought into the attention of the end users.
In theory, any cryptographic method with a key can be broken by
trying all possible keys in sequence. If using brute force to
try all keys is the only option, the required computing power
increases exponentially with the length of the key. A 32 bit
key takes 2^{32} (about 10^{9}) steps.
This is something anyone can do on his/her home computer. A system
with 40 bit keys takes 2^{40} steps  this
kind of computation requires something like a week (depending on the
efficiency of the algorithm) on a modern home computer. A system
with 56 bit keys (such as DES)
takes a substantial effort (with a large number of home computers
using distributed effort, it has been shown to take just a few
months), but is easily breakable with special hardware. The cost of
the special hardware is substantial but easily within reach of
organized criminals, major companies, and governments. Keys with
64 bits are probably breakable now by major governments, and
within reach of organized criminals, major companies, and lesser
governments in few years. Keys with 80 bits appear good for a
few years, and keys with 128 bits will probably remain
unbreakable by brute force for the foreseeable future. Even larger
keys are sometimes used.
However, key length is not the only relevant issue. Many ciphers
can be broken without trying all possible keys. In general, it is
very difficult to design ciphers that could not be broken more
effectively using other methods. Designing your own ciphers may be
fun, but it is not recommended for real applications unless you are
a true expert and know exactly what you are doing.
One should generally be very wary of unpublished or secret
algorithms. Quite often the designer is then not sure of the
security of the algorithm, or its security depends on the secrecy of
the algorithm. Generally, no algorithm that depends on the secrecy
of the algorithm is secure. Particularly in software, anyone can
hire someone to disassemble and reverseengineer the algorithm.
Experience has shown that the vast majority of secret algorithms
that have become public knowledge later have been pitifully weak in
reality. See the builtin encryption schemes used by WordPerfect,
Lotus 123, MS Excel, Symphony, Quattro Pro, Paradox, MS Word,
and PKZIP.
The key lengths used in publickey cryptography are usually much
longer than those used in symmetric ciphers. This is caused by the
extra structure that is available to the cryptanalyst. There the
problem is not that of guessing the right key, but deriving the
matching secret key from the public key. In the case of RSA,
this could be done by factoring a large integer that has two large
prime factors. In the case of some other cryptosystems it is
equivalent to computing the discrete logarithm modulo a large
integer (which is believed to be roughly comparable to factoring
when the moduli is a large prime number). There are public key
cryptosystems based on yet other problems.
To give some idea of the complexity for the RSA cryptosystem, a
256 bit modulus is easily factored at home, and 512
bit keys can be broken by university research groups within a few
months. Keys with 768 bits are probably not secure in the
long term. Keys with 1024 bits and more should be safe for
now unless major cryptographical advances are made against RSA; keys
of 2048 bits are considered by many to be secure for decades.
It should be emphasized that the strength of a cryptographic
system is usually equal to its weakest link. No aspect of the system
design should be overlooked, from the choice algorithms to the key
distribution and usage policies.
Cryptanalysis and Attacks on Cryptosystems
Cryptanalysis is
the art of deciphering encrypted communications without knowing the
proper keys. There are many cryptanalytic techniques. Some of the
more important ones for a system implementor are described below.
 Ciphertextonly attack: This is the situation where the
attacker does not know anything about the contents of the message,
and must work from ciphertext only. In practice it is quite often
possible to make guesses about the plaintext, as many types of
messages have fixed format headers. Even ordinary letters and
documents begin in a very predictable way. For example, many
classical attacks use frequency analysis of the ciphertext,
however, this does not work well against modern ciphers.
Modern cryptosystems are not weak against ciphertextonly
attacks, although sometimes they are considered with the added
assumption that the message contains some statistical bias.
 Knownplaintext attack: The attacker knows or can guess
the plaintext for some parts of the ciphertext. The task is to
decrypt the rest of the ciphertext blocks using this information.
This may be done by determining the key used to encrypt the data,
or via some shortcut.
One of the best known modern knownplaintext attacks is linear
cryptanalysis against block ciphers.
 Chosenplaintext attack:
The attacker is able to have any text he likes encrypted with the
unknown key. The task is to determine the key used for encryption.
A good example of this attack is the differential cryptanalysis
which can be applied against block ciphers (and in some cases also
against hash functions).
Some cryptosystems, particularly RSA,
are vulnerable to chosenplaintext attacks. When such algorithms
are used, care must be taken to design the application (or
protocol) so that an attacker can never have chosen plaintext
encrypted.
[INDEX The Previous Page The Next Page]
Information:
Enigma Story (illustrated)
· cryptography
· secure key generator
security expert
· system security
· JSCrypto info
· references
Tools:
JSHTML compiler
· PGPfone™
· PGPdisk™
steganography
· JSsreganography
· JSCODER/DECODER guide
· JSCODER/DECODER
Toys:
Lottery
· Cryptool 1
· Cryptool 2
· Calculator
· Calendar
adapted by Rafal Swiecki, p. eng. email
November, 2004
This document is in the public domain.
