Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:01
Anonymous (nobody@replay.com)
Sun, 3 Jan 1999 22:44:59 +0100
> I'm writing a paper for scholl on how Encryption could be the key to
> privacy. I have been searching the net for sometime now and I can seem to
> find the basics of it all. I have read about all the different kinds of
> systems but I would like to know the basics behide it all.. Thank you a
> head of time...
When writing the paper, be more careful to use good spelling and grammar.
I'm not going to attempt to fully explain the myriad of ways cryptography can
preserve human rights -- it is your paper -- but one example is provided by
anonymous remailers, which require cryptography to work well: a system of
anonymous remailers would ensure a certain level of freedom of speech, because
anyone trying to punish people for saying things considered "bad" would be
unable to do so, simply because it's impossible to find the person behind a
statement sent through the remailers.
A few paragraphs down is an excerpt from a cryptography reference for people
trying to learn how to design or implement new uses for cryptography. It does
not include the details of many algorithms, but that shouldn't matter unless
you're writing the paper for a class covering cryptography. If you are looking
for that kind of detailed information, you can find it at
http://ftp.replay.com/pub/crypto/crypto/LIBS (you have to understand C for it
to be any use, though).
Since this is converted from HTML, many links are lost (for instance, the link
to the Appendix explaining key clustering attacks -- again, probably not well
suited to a school paper, so it's not included here). Also, the text seems
somewhat awkward without the vocabulary in bold. One reference from the paper
destroyed by the HTML->Text conversion: http://www.aci.net/Kalliste/DES.htm
The section on public-key cryptography isn't nearly done yet, but the skinny on
it is this: you make up a private key and use that to make your public key.
This is done in a way that makes sure nobody can figure out your private key
from your public key. You tell everybody your public key, and they can use it
to scramble a message. There's no practical way to unscramble the message
unless they know the private key. But only you know the private key, so only
you can read the message. For a detailed description of a specific public-key
system, see http://jya.com/whprsa.htm
The section on protocols and applications is also unwritten, but
http://www.rsa.com/rsalabs/faq/ and
http://www.oberlin.edu/~brchkind/cyphernomicon/cyphernomicon.contents.html
provide some information on how cryptography can be used.
The first source is the RSA Labs Crypto FAQ, and the second source is Tim May's
Cyphernomicon, considered by some (myself not included, however) as a sort of
Bible of Cypherpunk ideologies. Both should be taken with a grain of salt; RSA
wants to sell their brand of crypto, and Tim May wants you to help him nuke
Washington, D.C. (okay, a tad of exaggeration on the last part)
(There was a post to CodherPlunks or Cypherpunks a while back explaining a couple
other public-key cryptosystems -- Diffie-Hellman key exchange and the National
Security Agency's similar algorithm, I believe -- and providing links to other
useful sites, although I'm afraid you're on your own when it comes to finding
it)
Basic terms
Cryptography: the use for practical purposes of mathematical problems
which are impractical to solve. Cryptography was once, for all intents and
purposes, exclusively dedicated to secrecy, but is now used for providing
anonymity, securing electronic commerce, and many other things. Cryptography
also refers to the science, art, or study dedicated to the creation,
application, and analysis of problems which are impractical to solve.
Cryptosystem: a system based on cryptography. The cryptosystem can be
thought of as including everything which could be used to deprive the user
of the intended benefits of the system. For example, in a cryptosystem
designed to provide secrecy, the hardware on which the encryption is
performed could be considered part of the cryptoystem, because it can
reveal the information kept secret, depriving the user of the intended
benefits of the system. This definition a cryptosystem is not standard
or universal, but will be used throughout the text.
Primitive: a type of mathematical algorithm designed to have a certain
property (for example, collision-resistance for a hash function), or an
instance of such an algorithm.
Attack: a method of attempting to deprive the user of the intended
benefits of a cryptosystem, a part of a cryptosystem or a primitive.
Threat model: a description of the assumptions about what attacks can
be attempted against a cryptosystem.
Secure: providing the intended benefits. Also, a cryptosystem may be
considered secure against a particular attack if the attack fails to
deprive the user of the intended benefits of a cryptosystem, part of a
cryptosystem, or primitive.
Encrypt: to change one piece of text into another with the intent of
making it unreadable. For example, if you encrypt the phrase "the
author is a psycho" you may have an output of
"fjdisjahformxzflkjsdjf". The process of encrypting is called
encryption.
Decrypt: to reverse the process of encryption, producing the original
message. For example, if you decrypt "fjdisjahformxzflkjsdjf", you may
get the original message, that is, "the author is a psycho". The
process of decrypting is called decryption.
Plaintext: information to be encrypted. In the above example, the
plaintext was "the author is a psycho".
Ciphertext: encrypted information. In the above example, the
ciphertext was "fjdisjahformxzflkjsdjf".
Key: a secret number used in encryption and decryption. It should be
impractical to decrypt an encrypted message without knowing the key.
Bit: the basic unit of information. Equivalent to a yes/no answer, and
usually represented as a one or zero. Text is encoded in bits in a
computer, as are keys. Each letter or punctuation mark is converted to
a number between 0 and 255, and this is encoded using eight bits. The
least significant bit, usually represented as being at the right side
of a group of bits, is "worth" one if its value is one, and each
succeeding bit's "worth" doubles.
00001001 = 0 + 0 + 0 + 0 + 8 + 0 + 0 + 1 = 9
01010111 = 0 + 64 + 0 + 16 + 0 + 4 + 2 + 1 = 87
For a clearer explanation of binary encoding, see
http://www.cs.colorado.edu/~l3d/courses/CSCI1200-96/binary.html
Keyspace: the set of all possible keys. The size of the keyspace is
proportional to the amount of effort required to find the correct key
by guessing (a technique often called called brute force). With each
one-bit increase in the length of the key, the size of the keyspace
doubles.
Foundations of Modern Secret-Key Cryptography
Assumptions about adversaries
One of the major premises of modern cryptography is that cryptosystems
are to be designed on the assumption that the only piece of
information not known to the person trying to eliminate the benefits
of your system (that is, the person trying to break it, often referred
to as the adversary) is the key. The adversary may know or even be
able to choose part of the plaintext, and is always assumed to know
the ciphertext.
However, there is one limitation on the adversary which is usually
assumed, and that is computing speed. The exact nature of the
limitation depends on the threat model underlying the design of the
cryptosystem, but it's normally assumed that the amount of computing
power necessary to search a keyspace of 2^128 (two to the one hundred
twenty-eighth power) keys within a reasonable amount of time is not
available to an adversary.
Block ciphers
Block ciphers take a block of plaintext which is composed of bits and
process it using a key to create a ciphertext block of the same
length. Most block ciphers use blocks of 64 bits and keys of 128 bits,
although some can handle other sizes. Candidates for the Advanced
Encryption Standard must use (at least) blocks of 128 bits and keys of
128, 192, or 256 bits.
The theoretical criterion for block ciphers is that it be impossible
for someone not knowing the key to distinguish the permutation from
plaintext to ciphertext from a random one without expending the effort
required to find the correct key by guessing. The reason that this
criterion is used is that a cipher which means it is not vulnerable to
the "easiest" possible attack, that is, using ciphertext and guesses
at the plaintext to decide with any confidence which guess, if any, is
the correct one. (This type of attack merits more than theoretical
concern, however, especially in the context of steganography, to be
discussed in a later section)
In practice, however, most attacks on block ciphers recover the key
rather than simply uncovering an unusual characteristic of the
permutation.
Most attacks fall into three categories:
Ciphertext-only attack: Dedeuces key and plaintext using only
ciphertext. Almost any practical ciphertext-only attack involves
guessing plaintexts using known facts about it (for instance, the
knowledge that all messages begin with a particular header)
Known-plaintext attack: Dedeuces key and plaintext using
plaintext-ciphertext pairs. This could be considered the special case
of the ciphertext-only attack in which the guessed plaintexts are
correct.
Chosen-plaintext attack: Dedeuces key and plaintext using
plaintext-ciphertext pairs specially chosen to reveal the key. This
could be considered the special case of the known-plaintext attack in
which the plaintext-ciphertext pairs happen to be those best for the
attacker. This can be adaptive (if the attacker can choose new
plaintexts knowing the ciphertexts corresponding to other plaintexts)
or non-adaptive.
In some cases, an attack which is normally a known- or
chosen-plaintext attack can be applied to the inverse of the cipher,
that is, its decryption function instead of its encryption function,
in which case the attack doesn't fall into one of the mentioned
categories.
Modes of operation of block ciphers
Exclusive OR (abbrev. XOR): An operation with two bits such that its
output is 1 if and only if exactly one of its inputs are 1. The XOR of
two groups of bits produced by XORing corresponding bits; 010110 XOR
110101 = 000011.
[text deleted for brevity]
General considerations for application of block ciphers
Someone designing a good cipher must be able to perform cryptanalysis,
something not covered in this section, and not covered in sufficient
detail in any part of this text. In other words, don't even hope that
this text would prepare you for designing a cipher.
[text deleted for brevity]
Most block ciphers are designed in terms of rounds, that is, they
consist of one round transform repeated a certain number of times.
Each round uses the output of the previous round and a subkey to
produce its output. What subkeys go to the various rounds is
determined by the key schedule. In a class of block ciphers known as
Feistel networks (which includes most ciphers) each round transform
usually consists of one half of the block being altered by being
exclusive ORed with some function of the other half, after which the
halves are swapped. Each round can be reversed by swapping the halves
and repeating the XOR.
For a well-illustrated example of a block cipher, see J. Orlin
Grabbe's explanation of the Data Encryption Standard (@).
More rounds of a given cipher are almost always stronger than fewer
rounds, however, 20 rounds of cipher A may be weaker than 16 of cipher
B. A higher round count also decreases the cipher's speed, however,
but this is not a problem in most applications.
[text deleted for brevity]
Stream ciphers
Stream ciphers are the other major kind of cipher. They work by
creating a keystream which is XORed with the plaintext to produce the
ciphertext. The criterion for stream ciphers is that this keystream be
indistinguishable from randomness.
Unlike with block ciphers, it is hard to make generalizations about
stream cipher design; there is no single general structure used by
most of them, for example.
There is one analogy which can be drawn between block and stream
ciphers, and that is that both require avalanche [covered in a section not
included here]. In a stream cipher, avalanche is only required between key
and keystream; if a single-bit change in key alters, on average, fewer or
more bits of the keystream than it should, then an attack is possible.
Attacks on stream ciphers more frequently attempt to distinguish the
stream from random numbers than try to recover the key or internal
state of the cipher.
General considerations for application of stream ciphers
Many of the concerns regarding application of stream ciphers are the
same as those regarding the use of a block cipher applied in OFB mode,
because it is then being applied as a stream cipher.
Whereas the major security parameter for block ciphers was the round
count, many stream ciphers have the at least somewhat security-related
aspect of state size; in stream ciphers with reversible states, this
is expected to be directly related to the period of the cipher, that
is, how long it is before the keystream begins to repeat itself.
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:01