Introduction
To Cryptography
ê
Traditional Use of Cryptography:
plaintext >>>>>>>>>> ciphertext
>>>>>>>>> plaintext
(encryption) (decryption)
cryptographer: invent clever secret codes.
cryptanalyst: attempt to break
these codes.
ê
Fundamental Tenet of Cryptography:
If lots of smart people failed to solve a problem,
then it probably won't be solved (soon).
ü The time required to
break a code
should be longer than
the time the encrypted data
must remain secret.
ü The value of most data decreases overtime.
ê Cryptographic System: Algorithm + Key
It is perfectly OK to let everyone
know the algorithm
because knowledge of the algorithm without the key
does not help unmangle the information.
Publishing the algorithm provides an enormous
amount of free consulting to uncover weaknesses.
ê
Computational Difficulty:
Example:
combination
lock
ü Typically require 3 numbers between 1 and 40.
If it takes 10
seconds for a good
guy,
it would take 10*(40**3) seconds or about 1 week for the bad guy.
ü By requiring 4 numbers,
If it takes 13 seconds for the good guy,
it would take 13*(40**4) seconds or about 1 year for the bad guy!
In general, increasing the key length by 1 bit makes the good guy's job just a little bit harder,
but makes the bad guy's job twice as hard!
Caesar cipher:
Substitute each letter with another letter which is 3 letters
away in the alphabet (with wrap around).
E.g., dozen >>> grchq, wahab
>>> zdkde
Extension: Instead of 3 use
any number n
between 1 and 25.
E.g., for n=1, HAL >>>
IBM, wahab >>> xbibc
Monoalphabetic
cipher:
Arbitrary map one letter
to another.
There are 26! ~ = 4*(1026) possibilities (a
trillion is 1012 ).
ü If each possibility takes 1 microsecond
it would take 10
trillion years to
try all possibilities.
ü However statistical analysis of language makes it much easier
to break:
The Homophonic Substitution cipher:
Replacing each letter with a variety of substitutes.
The number of potential substitutes being proportional to the frequency of
the letter.
For
example, the letter 'a' accounts for roughly 8% of all
letters in English, so we assign 8 symbols to represent it.
This
deters potential attack via straightforward frequency analysis.
ê
Breaking Encryption Schemes
Ciphertext Only: Because it is important for Trudy to be
able to differentiate plaintext from gibberish, this attack sometime known as recognizable plaintext attack.
It is also essential for Trudy to have enough ciphertext, e.g.,
there is no way to know the plaintext corresponding to XYZ is THE or CAT or HAT.
Known Plaintext: Knowing <plaintext, ciphertext> pairs are helpful for Trudy,
e.g., in monoalphabetic cipher Trudy learns
the mapping.
How to obtain plaintext? Secret data might not remain secret forever,
e.g., which city to attack might not be secret after that attack!
Chosen Plaintext: Trudy can choose any plaintext he wants
and get the system to provide corresponding ciphertext, e.g.,
telegraph company can encrypt and send any message you provide.
Example:
If Trudy knows that Alice encrypted message (azsxopfq) is either (surrender) or (fight on), he can ask the system to encrypt both
messages and find out the correct one.
Types of Cryptographic Functions:
v
Secret Key Cryptography
(symmetric cryptography)
(encryption)
plaintext >>>>>>>>> ciphertext
|
key
|
ciphertext
>>>>>>>>
plaintext
(decryption)
Can be used for:
ü Transmission Over
an Insecure Channel:
An eavesdropper will only see unintelligible data.
ü Secure Storage on
Insecure Media:
Forgetting
the key makes the data irrevocably lost.
ü Authentication:
Alice authenticating
Bob:
Alice Bob
challenge: r
>>>>>>> r
response:
K{r}
<<<<<<< K{r}
r
is a random number,
K{r} is the secret key encryption of r using
shared key K.
v
Public Key Cryptography
(asymmetric cryptography)
Each individual has two keys:
private key (not revealed to anyone)
public key (make it known to
everyone)
(encryption)
plaintext >>>>>>>>>>
ciphertext
|
public key
private key
|
ciphertext >>>>>>>>>
plaintext
(decryption)
The reverse process is called digital signature:
(signing)
plaintext >>>>>>>>>
ciphertext
|
private key
public key
|
ciphertext >>>>>>>>
plaintext
(verification)
Public key cryptographic algorithms are slower than the best known secret key
cryptographic algorithms.
Thus they normally used to establish temporary
shared secret key
for use during a session.
Uses of Public Key Cryptography:
ü Transmission Over
an Insecure Channel:
Alice
Bob
{K}eB >>>>>>>>> [K]dB
K{mB}
>>>>>>>>> K{mB}
K{mA} <<<<<<<<< K{mA}
§ K is a random
session key.
§ <eB, dB> is the
<public-key , private-key> pair for
Bob.
§ {m}eB is the public
key encryption of message m with eB.
§ [m]dB is the public
key decryption of message m with dB.
§ K{m} is the symmetric key
encryption of message m with K.
§ mB message for Bob.
§
mA message for Alice.
ü Secure Storage on
Insecure Media:
Alice generates a random key K and save:
F=
K{File}
KF= {K}eA
To restore the file:
K=
[KF]dA
File = K{F}
ü Authentication:
Alice Bob
challenge:
c = { r }eB >>>>>
c
response:
r
<<<<< r =
[c]dB
r is a random number
v
Hash Algorithms
(also known as: message
digest,
fingerprint, one-way
functions
)
The
hash of a message m, h=H(m) has the following properties:
ü Given m, it is easy to
compute h.
ü Given h, it is hard to compute m.
ü Given m, it is hard to
find another m' such that H(m) = H(m').
ü It is hard to find m1
and m2 such that H(m1) = H(m2).
Uses of Hash Algorithms:
MAC/MIC
(Message Authentication/Integrity Code)
·
Using Secret Key:
Alice
Bob
m,h
where h = H(m|K)
>>>>> m,h , OK
if h = H (m|K)
K is the shared secret between Alice and Bob \
Note that:
ü Bob is sure that Alice sent the message, since she knows K.
ü Bob can NOT prove to any one that Alice sent him message m, since he also knows K.
·
Using Public Key:
Alice
Bob
m,sh where sh = [H(m)]dA
>> m,sh , OK if H (m) = {sh}eA
<eA, dA> is the
public/private key pair of
Note That:
ü Bob is sure that Alice sent the message, since she knows dA.
ü He can also prove to any one that Alice sent him message m, since he does not know dA.
This property
of public key cryptography is known as non-repudiation,
where the sender should not be able to falsely deny that he sent a
message.
Password
Hashing:
OS like UNIX stores the hash of passwords instead of storing the actual passwords.
ü For each user U, there is a tuple <U, h>
where h = H(P) is the hash of password P of user U.
ü
When
a user U types a password, P, the OS compute H(P)
and
if it is equal to the saved
value h in the tuple <U,h>, the user is OK.
ê The
magic of XOR: A Simple XOR symmetric algorithm:
(from Bruce
Shneier textbook)
0 ® 0 = 0
0 ® 1 = 1
1 ® 0 = 1
1 ® 1 = 0
Note that for x (x is either 0 or 1):
x ® x = 0
x ® 0 = x
The following program is a very simple symmetric algorithm.
(see /home/cs472/public_html/demos/xor
)
ü To encrypt: the plaintext P is ® with a key K to produce a ciphertext C.
ü To decrypt: the ciphertext C is ® with a key K to produce a plaintext P.
P ® K
= C
C ® K = P
Why?
Since C ® K = (P ® K) ® K = P ® (K ® K) = P ® 0 = P
This is a
very insecure algorithm that can be easily broken.
It is good enough to keep "your
kid sister" from reading your files!
crypto
Usage:
%
crypto
<key>
<input_file> <output_file>
Example:
ü To encrypt infile:
%
crypto "odu computer science" infile outfile
ü To decrypt outfile:
%
crypto "odu computer science" outfile tmpfile
ü tmpfile is identical to infile
Code:
void main (int argc, char *argv[])
{
FILE *fi, *fo;
char *cp;
int c;
cp = argv[1]) ;
fi = fopen(argv[2], “r”);
fo
= fopen(argv[3], “w”);
while ((c = getc(fi))
!= EOF) {
if (!*cp) cp = argv[1];
c ^= *(cp++);
putc(c,fo);
}
}