An Introduction To Cryptography Part II

Docs that have proven to be a staple in understanding computer/network security. This is not an inclusive forum and nothing ipublished will tell you how to 0wn someone, these docs will help you understand how you got 0wnd.
Post Reply
telcontar
31337 Martial Artist
Posts: 1898
Joined: Sat Feb 21, 2004 8:38 am
Location: /etc/login.defs
Contact:

An Introduction To Cryptography Part II

Post by telcontar » Mon Dec 27, 2004 2:43 pm

-An Introduction To Cryptography-
Part 2

by telcontar
------------------------------

Originally written for and released at
http://www.hackerthreads.org

The Second Instalment of:

An Introduction to Cryptology

o An Introduction to Cryptography: Part I
o An Introduction to Cryptography: Part II
o An Introduction to Cryptography: Part III*
o An Introduction to Cryptanalysis: Part I*

* - not finished and/or posted

--------------------

Disclaimer

This article may be redistributed as you will; on the conditions that it's reproduced in it's entirety i.e. proper credits and any sources (where and if applicable) throughout this set of papers, are given.


Contents

o Foreword
o Introduction
o The Hybrid Algorithm
o Secure Algorithms
o Symmetric Algorithms
1. DES
2. Triple DES
3. Blowfish
o Asymmetric Algorithms
1. RSA
2. PGP*
o Message Digest Functions
1. Introduction
2. Algorithms
o Conclusion.
1. With an Overview of Part III


Foreword

This is Part II of an Introduction to Cryptography in a series of papers entitled An Introduction to Cryptology.
Please take the time to read Part I if you haven’t already done so.

Introduction

As mentioned at the end of Part I this paper will focus on the methods used to employ encryption in the real world which will include Message Digest Functions.

Hybrid Algorithms

Firstly we will take a brief look at a new type of Algorithm; the Hybrid Algorithm.

The Hybrid Algorithm basically uses characteristics from both Symmetric Algorithms and Asymmetric Algorithms, some are mainly considered being a Symmetric Algorithm but uses some of the features of Asymmetric Algorithms in some parts of the Encryption/Decryption Process.


To keep some kind of order to the paper whilst going through the selected Algorithms we will be looking first at Symmetric Algorithms and then Asymmetric Algorithms; keeping in mind that many of today’s strong Algorithms incorporate some of the attributes from the other i.e. Hybrid Algorithms.

Secure Algorithms

As the main focus of this particular paper is to give an overview of popular algorithms one issue that we will naturally be looking at is how secure each method is.

Therefore before we go any further it might be prudent to first define what exactly is considered a secure algorithm.

Remember, by keeping an Algorithm secret does not, I repeat, not, mean the method is 'secure'. Algorithms in the public domain are usually a lot securer as they are scrutinised by a lot of people. Remember, your security shouldn't depend on the ignorance of your attacker. This applies to all aspects of security, not just Cryptography.

Ideally, we would want to use a code that was, 'quite simply', 100% unbreakable. But, in reality every code (Symmetric and Asymmetric) can be broken via, for example, Brute Force (in this case trying every possible key). It is a mathematical inevitability that by trying every possible key you will eventually get to the right one.

However some codes can take much longer than others to crack. So Algorithms can rely on ridiculously long keys (hundreds of bits to a thousand -the latter being very rare) and the use of multiple keys for security. This results in a huge amount of possibilities for any attacker to try and 'extract' the Plaintext. This obviously will require

a) a lot of time
b) a very powerful machine to try and crack it.

Therefore such Algorithms, fundamentally, every code is built around the ideology that cracking said code would be infeasible.

Infeasible meaning impractical. Some codes simply take too long to crack, in some cases the attacker could theoretically be dead before the Plaintext was derived. Also, in a lot of cases, the content of the Plaintext of would be out of date and very probably useless by the time you get to it.

A particular Algorithm could be secure also because perhaps the computing hardware doesn't exist to 'crack' it within a lifetime or secure because very few possess the means (i.e. the Hardware) to crack in a reasonable amount of time.

Such people could be large corporations and government agencies.

Obviously these really only apply if you plan to try every possible key i.e. Brute Forcing or Key Searching. Other methods are usually quicker, but more difficult.

Please note and this is very important: that the security of an Encryption algorithm is not dependant on key lengths alone, there are other factors which will be introduced as we come to them in this paper and certainly in more detail in 'An Introduction to Cryptanalysis Part I'.

An Algorithms strength can be 'measured' by their ability to be impervious to the following types of attack.

Key Searching (already briefly mentioned), Cryptanalysis and Attacks on the Encryption Algorithm itself.

Symmetric Algorithms

Remember what Symmetric Algorithms are? If not then go to Part I and read up, if so then carry on. Here are a few of the popular and well known Symmetric Algorithms that are either in use today or were well used at sometime.

Another thing before we go on, we mention several times how many possible keys an Algorithm can have. The key length is always given in bits. Remember your bits and bytes?
If an Algorithm is said to use a key length of 56 bits then there are a possible 2^56 keys. Which might sound a lot, well, it is a lot but today's computers can try (roughly) over 60 million keys in a minute.
(Ok, this is a little out of date- technology moves fast no? This is also from memory, so I’m trying to find a valid source for this and will be updated as soon as I find it. feel free to let me know if you have a source).


DES

The Data Encryption Standard is a 64 bit Block cipher which uses a 56 bit key. This was adopted as a US government standard and in 1981, an ANSI (http://www.webopedia.com/TERM/A/ANSI.html) Standard.
Although the DES Algorithm itself is generally agreed to be quite secure, it has been proven that with the proper resources (e.g. today’s modern computers) it can be broken in a reasonable amount of time (A rough estimate would be in a few hours to a day) due to it’s ‘small’ key size.
Therefore derivatives of the DES algorithm exits. One such algorithm is ‘Triple DES’.

Triple DES

As you might have guessed this simply applies the DES Algorithm 3 times. Three different keys can be used, i.e. a unique key for each implementation, and therefore in effect has a key length of 168 bits (56 bit key for one implementation * 3).

Blowfish

Created by Bruce Schneier, Blowfish is another (64 bit) Block cipher.
This is a fast, efficient (very small file size) and extremely secure Algorithm as it uses a key that can be up to 448 bits long (with a minimum length of 32 bits). That means the maximum amount of possible keys is 2^448, a huge amount and (more likely than not) rendering a key search infeasible.

Having such a varying choice between keys means that users can optimises the Algorithm for either speed (use a small key thus making encryption and decryption faster) or secrecy (a larger key may prove infeasible for attackers to calculate, however it will make the whole process a lot slower.).

Asymmetric Algorithms

Same goes here, if you don’t know / don’t remember what an Asymmetric Algorithm is then go read Part I.

RSA

Named after it’s creators, Ron Rivest, Adi Shamir and Len Adleman, RSA has pretty much become a standard in Asymmetric (Public) Key Encryption.
Over time it has proven to be extremely secure and can be used for both ‘normal’ Encryption and creating Digital Signatures.
These three MIT (they aren’t anymore) Professors created RSA in response to a paper, written by Ziffie and Hellman, (which was considered a huge breakthrough in the world of Cryptography). Feel free to do some reading on your own on this paper (“New Directions in Cryptography” (1976) and “Multiuser Cryptographic Techniques” (also 1976)).

RSA’s security exploits a common mathematical problem, that of factoring (very) large numbers.
It is very difficult to factor the kind of numbers that RSA uses as keys in a reasonable amount of time thus making it very difficult for someone trying to work out a key.
So the question: ‘Just how secure is RSA?’ has a tentative answer of it staying secure as long as factoring such numbers takes a long time.

It is generally agreed that there some time in the future RSA will have to be abandoned altogether as soon as we have the means to do such math.

PGP

Pretty Good Privacy, written by Phil Zimmermann and released in 1991. This is actually a Hybrid system but is classed as ‘Asymmetric’.

A widespread encryption program used for encrypting emails (traditionally),PGP is popular because it’s secure, simple to use and has a whole range of products which extend the functionality of PGP beyond the simple encryption of files and email messages. For more information on PGP Products visit http://www.pgp.com/products/index.html. Free versions also exist.

As said, PGP is a Hybrid Security System, as it uses RSA, IDEA amongst other things which haven’t been introduced yet.

The RSA Algorithm is used for the managing of keys (remember Asymmetric, uses two keys) and the charge of the actual Encryption of the data is given to the IDEA Algorithm (http://www.finecrypt.net/idea.html) (A Symmetric Encryption Algorithm).

Message Digest Functions (Hashes)

When sending documents the normal way (that's posting a letter :P) the receiver wants to know that it is genuine and that it's from who it says it's from. And so what do we do? We put our signature on it to prove it's validity.

However when we send files online we can't sign our name as such, well some software allows you to but in the main we can't. But online we have to deal with the problem of confirming a files' (a message etc) integrity. How do we know if it has been tampered with en-route to you?

Message Digest Functions are used for creating digital signatures on files (sometimes called digital footprints) to prove file integrity. This process is sometimes called Hashing.

Message Digest Functions takes Plaintext and produces a digital signature of that Plaintext. As our fingerprints are unique to us, Message Digests calculated from a file are unique to it (there are _some_ cases where two different Plaintexts can have the same message digest value, this is called a 'collision' and will be looked at the next Paper).

The same Plaintext applied to a Message Digest Function will always calculate the same Hash Value (the signature of the file). If however you take the Plaintext and ever so slightly modify it (say for example to remove a full stop) then a completely different Hash Value will be created when the Plaintext is applied to the MD Function.

Creating the Hash Value is a one way encryption scheme, i.e. you cannot decrypt it, it is infeasible to be able to get the original text from the Hash Value.
Many people ask about how to decrypt the result of a MD Function, the short answer is you cannot decrypt it in the traditional sense. It is physically impossible. That has an obvious security benefit ;)

Using Message Digest Function in Cryptography

The person sending the message generates a hash of the message (of the Plaintext that is), encrypts it, they then encrypt the message itself and sends both the Ciphertext and Hash (which is encrypted).
The receiver then decrypts both the message and the hash. Taking the decrypted message they then calculate a Hash value of their own (using the same Algorithm of course) and compare it to the hash value sent to them.
If the Hash value sent to them is the same as the one that they themselves calculated from the Decrypted Ciphertext then in all likeliness the message has not been tampered with.
Remember that even the slightest change in a message will give a completely different Hash Value than what was calculated before.


Storing Passwords

The most common, and quite probably the most secure way to store Passwords on a computer (a Server, whatever) is not to store the password itself, but a unique version of it AKA it’s signature.

A Hash value is stored on the machine, i.e. a Value that is unique (usually) to the Plaintext (the password) from which it was derived.

As the Hash Value cannot be decrypted it means that any attacker that comes across it cannot get the password from it (in theory) and so the password remains hidden.

When you sign up for forums etc and you receive a registration email you may have noticed a message saying something along the lines of ..

‘Note: The Webmaster nor any other affiliated with the site knows your secret information i.e. your password. Such information is automatically encrypted and is stored in our Database.’

This usually means that a Hash Value is calculated and then stored in the database, so nobody, not even the Admin can take a look and steal your password.

File Integrity

As we already know MD Functions are a good way to check for changes (however small)
in files or messages. Many readers users should already be aware of this 'MD5 checksuming' or ‘Hash Checking’.
You can calculate the Hash Value of the file (usually Files critical to the running of your PC) and keep it somewhere safe. If at some point in the future you have reason to believe that the file/message has been modified accidentally or on purpose, for example after
a system compromise, then you can calculate the Hash Value again (using the same Algorithm) and compare them. If the two values match then it is extremely unlikely that the file or your message has been modified, if however they do not match, then you may (well actually you _do_) have problems.
Remember, changes in the file, however small, create a completely different Hash Value so don’t worry about scrutinising the Hash for a tiny difference; it will stick out like a sore thumb.

MD Algorithms


MD5

Short for Message Digest No. 5. This MD Function was created by Ronald Rivest (The ‘R’ in RSA) as an upgrade from his MD4 which was broken. This Algorithm produces a fixed Digest of 128 bits.

MD5 is probably the most popular MD Function but it is not the most secure. In 1996 someone found that it was possible to calculate some collisions. Since then some people have started to abandon MD5 and use other Hash Functions.

This year (August), three wise Chineese Men by the names of Xiaoyun Wang, Dengguo Feng, Xuejia Lai and Hongbo Yu, announced that, under one hour they managed to find collisions using a Brute Force Attack. There are papers published about this on the web, google it!

Also, considering MD5 was developed for 32-bit machines we will all probably be using another Algorithm in the near future anyway.

SHA-1

A Hash Function called the Secure Hash Algorithm was released by the NSA for use with DSS Algorithm (google it :-)), but as soon as it was released it was recommended that it shouldn’t be used. Shortly after that SHA-1 was put out and is thought to be securer.
This message digest produces a 160 bit digest.


Conclusion

Here ends the second instalment of my Introduction to Cryptology (again though, only dealing
with Cryptography).

Please keep in mind that there many Encryption Algorithms, both Symmetric and Asymmetric and I don’t feel that it is my job to list every single one out there in this paper. Nor is it up to me to go into ridiculous detail of the Algorithms, some will be in the next two papers but not all.
I encourage readers to look up key terms etc given in this paper themselves and research the areas covered in more depth themselves.

(Such is the process of learning :P )

By now you should know enough to help you on your way, from the first two instalments
we've covered the different types of Encryption Algorithms: Symmetric, Asymmetric, Hybrid,
MD Functions; examples of each: e.g. PGP, RSA, DES, MD5, the SHA's; so it's safe to say that
you now have a fairly sound knowledge and awareness of the different types of Encryption
and you may feel that anything further wouldn't be necessary.

However, you (and any of the 'non-beginners' reading) will have noticed that although we
have covered quite abit, we've only been looking at them 'abstractly' i.e. I've
covered the general gist of everything, but we've used for example, 'the RSA Encryption
Algorithm' loosely without actually discussing it. This is simply because it was my belief
that for anyone new to this topic would find themselves overwhelmed if they were greeted with a
ton of mathematics halfway through the first or second paper, would get lost and wouldn't
exactly be enticed to read further. So the third part will hopefully be more interesting
to the more mathematically inclined.

Also, SSH and SSL will now be included in the third part because I wanted to get this out before the New Year and so I can concentrate on my exam revision.


-telcontar

telcontar [AT] hackerthreads [dot] org

-----------------------------------------------------------

REFS and Further Reading

Bruce Schneier, http://www.schneier.com/ -
Applied Cryptography,2nd Ed ,Bruce Schneier, John Wiley & Sons, 1996.
Practical cryptography. Niels Ferguson, Bruce Schneier, 2003

Introduction to cryptography : principles and applications. Hans Delfs, Helmut Knebl, 2007.

Cryptography : a primer Alan G. Konheim, 1981 (yes, old)

http://www.wikipedia.org/
phpbb/viewtopic.php?t=11474

Online Elliptic Curve Cryptography Tutorial
http://www.certicom.com/index.php?actio ... orial,home


Feedback is much appreciated. (work in production?)


- telly
Last edited by telcontar on Sat Feb 02, 2008 5:14 pm, edited 3 times in total.
Fate favours the well prepared ...

Code: Select all

(A + 3, N - 1, X)

User avatar
NoUse
time traveller
Posts: 2624
Joined: Thu Aug 28, 2003 10:46 pm
Location: /pr0n/fat

Post by NoUse » Mon Dec 27, 2004 3:01 pm

Nice.

I'm, personally, eager to read the 3rd.
And I will strike down upon thee with great vengeance and furious anger
those who would attempt to poison and destroy my brothers.
And you will know my name is the Lord
when I lay my vengeance upon thee.

User avatar
B-Con
Challenge Winner [1x]
Posts: 2679
Joined: Thu Apr 22, 2004 4:19 pm
Location: UC Davis
Contact:

Post by B-Con » Mon Dec 27, 2004 3:35 pm

good stuff man, I too await the 3rd && 4th editions...
- "Cryptographically secure linear feedback shift register based stream ciphers" -- a phrase that'll get any party started.

- Why know the ordinary when you can understand the extraordinary?

User avatar
Niels
Sargeant at Arms
Posts: 260
Joined: Wed Sep 01, 2004 12:31 am
Location: San Francisco
Contact:

Post by Niels » Tue Dec 28, 2004 12:06 am

Everything that NoUse and B-Con said ;)

Post Reply