Sunday, November 2, 2014

Beginning Cryptography - Decrypting XOR Encryption

In the first post in this series we looked at definitions. In the previous post we looked at the Caesar Cipher. In this post we will look at the Decrypting XOR Encryption


 "Exclusive-OR (XOR) encryption is an encryption method that is hard to break through with so called “brute force” methods (brute force = using random encryption keys in the hope you find the correct one.), but the encryption method is susceptible to pattern recognition. Patterns can be easily avoided by first compressing the file (compression already makes it unreadable, it removes patterns for you) before it is encrypted."


"The XOR encryption method doesn’t make use of a public-key, such as RSA. Instead both the people that encrypt the file as well as the people that want to decrypt the file need to have the encryption key. The exclusive-OR encryption (as the name already tells you) makes use of the Boolean algebra function XOR."

"The XOR function is a binary operator, which means that it takes two arguments when you use it.
If one of the two arguments is true and the other argument is false, then the XOR function will return true."


00010000
00011011
00010110
00000111
00001100
00000101
00000001

The key is: 01010101

Answer:
Cipher Text + XOR Key:  
0001 0000       0001 1011       0001 0110       0000 0111       0000 1100       0000 0101
0101 0101       0101 0101       0101 0101       0101 0101       0101 0101       0101 0101
0100 0101       0100 1110       0100 0011       0101 0010       0101 1001       0101 0000

0000 0001
0101 0101
0101 0100

Binary Value after XORing
After XORing the Binary Value is:
0100 0101       0100 1110       0100 0011       0101 0010       0101 1001        0101 0000  0101 0100

Binary =  Hex Value = Ascii Character
0100 0101 = 45 = E   
0100 1110 = 4E = N
0100 0011 = 43 = C   
0101 0010 = 52 = R   
0101 1001 = 59 = Y   
0101 0000 = 50 = P
0101 0100 = 54 = T

The decrypted text is “ENCRYPT”

Reference:
http://www.codingunit.com/exclusive-or-xor-encryption

Introduction to Cryptography - Decrypting Caesar's Cipher

In the previous post, we looked at some definitions around cryptography. In this post we will look at the Caesar cipher. This is one of the oldest ciphers.

"A Caesar cipher is one of the simplest (and easiest cracked) encryption methods. It is a Substitution Cipher that involves replacing each letter of the secret message with a different letter of the alphabet which is a fixed number of positions further in the alphabet".


"Because each letter in the message has a direct translation to another letter, frequency analysis can be used to decipher the message. For example, the letter E is the most commonly used letter in the English language. Thus, if the most common letter in a secret message is K, it is likely that K represents E. Additionally, common word endings such as ING, LY, and ES also give clues.

A brute-force approach of trying all 25 possible combinations would also work to decipher the message."


What does the cipher text below say?

LZAK AK S LWKL GX LZW USWKSJ KZAXL UAHZWJ HDWSKW LWDD EW OZSL LZAK EWKKSYW KSQK

Let's see if we can find a way to decrypt this message. Using information from "www3.nd.edu/~busiforc/handouts/cryptography/cryptography hints.html".
Let's first start with 1 letter words. The first and only one we see in the ciphertext is "S"
Looking at the 2 letter words we have "AK, GX, EW"
Looking at the 3 letter words we have "LZW"
Four letter words "LZAK, LWKL, LWDD, OZSL, LZAK KSQK"

We can continue building out the words as similar as above. If we start with the one letter words, we know in English language these are "A" and "I". This means that "S" in the ciphertext is either equal to "A" or "I"


For the two letter words, we know that these are "of, to, in, it, is, be, as, at, so, we, he, by, or, on, do, if, me, my, up, an, go, no, us, am". This means that the words "AK, GX, EW" in the ciphertext equals to one of these words

Let's look at the 3 letter words.
"the, and, for, are, but, not, you, all, any, can, had, her, was, one, our, out, day, get, has, him, his, how, man, new, now, old, see, two, way, who, boy, did, its, let, put, say, she, too, use"
So "LZW" will equal to one of the following 

Last but not least 4 letter words:
"that, with, have, this, will, your, from, they, know, want, been, good, much, some, time"
So the  Four letter words "LZAK, LWKL, LWDD, OZSL, LZAK KSQK" in the ciphertext should equal to one of the words above.

Ok now that we've done all of the above. Let's try to put together our letters

Since the one letter word "S" is not in any of the 2 or 3 letter words, let's work with the assumption that it is "A" when deciphered. If after testing we find this is wrong, we can always change it to "I" since there are only two options.

If we look at the 2 letter word "AK", we can see that it is in the 4 letter word "LZAK". Interestingly also, LZ in the 3 letter ciphertext "LZW" also starts the 4 letter word "LZAK". Let's try to see which 4 letter word ends with the letters in a 2 letter word and which starts a 3 letter word :-).

If we go through the words above we see "AZ" can be deciphered to "IS"
"LZAK" can be deciphered to "THIS". This mean that "LZ" is "TH" thus "W" in the ciphertext is "E" when deciphered. If we continue this methodology, we will decipher the entire text and end up with the following


ciphertext = plaintext
A = I
W = E
K = S
L = T
S = A
Z = H
G = O
J = R
H = P
D = L
E = M
O = W
Y = G
Q = Y

Thus the deciphered text is "THIS IS A TEST OF THE CAESAR SHIFT CIPHER TELL ME WHAT THIS MESSAGE SAYS" 

The Caesar shift in this pattern is a shift by 8


Let's try this one more time.

Decipher the text below, using the methodology above.



UIJT JT B TFDSFU NFTTBHF

If you got this correct, then you should have the following representation for each letter.

Answer:
ciphertext = plaintext
B = A
J = I
T = S
I = H
U = T
F = E
D = C
S = R
N = M
H = G

Then you should have this as your deciphered text.
 
THIS IS A SECRET MESSAGE

... and you would have detected that the pattern is a shift by -1


Ok! I know I said one more. Let's do it one more time. I promise this is the last one.

Decrypt the ciphertext below.



N  INLZKI  RNI  FPGMZMT  ZLF  OKKCF,  NIS  TMTI  LVT  NHJZLZKPF.  JPL   ZL  RNIIKL  FPGMZMT  LGTNFKI  OGKH  QZLVZI.  NI  TITHX  NL  LVT  WNLTF  ZF  CTFF  OKGHZSNJCT, OKG  VT  ZF  BIKQI  NIS  RNGGZTF VZF  JNIITG  KDTICX.  JPL  LVT  LGNZLKG  HKMTF  NHKIWFL  LVKFT  QZLVZI  LVT  WNLT  OGTTCX,  VZF  QVZFDTGF  GPFLCZIW  LVGKPWV  NCC  LVT  NCCTXF,  VTNGS  ZI  LVT  MTGX  VNCCF  KO  WKMTGIHTIL  ZLFTCO.  OKG  LVT  LGNZLKG  NDDTNGF  IKL  N  LGNZLKG;  VT  FDTNBF  ZI  NRRTILF  ONHZCZNG  LK  VZF  MZRLZHF,  NIS  VT  QTNGF  LVTZG  ONRT  NIS  LVTZG  NGWPHTILF, VT  NDDTNCF  LK  LVT  JNFTITFF  LVNL  CZTF  STTD  ZI  LVT VTNGLF  KO  NCC  HTI.   VT  GKLF  LVT  FKPC  KO  N  INLZKI,   VT  QKGBF  FTRGTLCX  NIS  PIBIKQI  ZI  LVT  IZWVL  LK  PISTGHZIT  LVT  DZCCNGF  KO  LVT  RZLX,  VT  ZIOTRLF  LVT  JKSX  DKCZLZR  FK  LVNL  ZL  RNI  IK  CKIWTG  GTFZFL.  N  HPGSTGTG  ZF  CTFF  LK  OTNG. 



-HNGRPF  LPCCZPF  RZRTGK


 If you use the method used at the beginning then this should not take too much effort.

The basic idea is to first identify one letter words within the ciphertext. There is currently only 1 which is “N”. Once this is found, the next step is to identify the 1 letter words from the English language and their frequency of usages. A is known to be used more than I.

Next, identify the two letters words. Some of these are ZL, NI, NL, ZF, VT, KO, LK, FK, IK.

The third step is to identify the 3 letter words. Some of which were RNI, ZLF, NIS, LVT, JPL, OKG, VZF, ILK HTI.   Once these words are identified, the fourth step is to try to create 2 letter words or build 3 letter words based on the 2 letter words.

When you are finished the following mappings should be identified.
cyphertext = plaintext.
P=U; J=B; N=A; C=L; I=N; R=C; S=D; K=O; L=T; V=H; T=E; Z=I; F=S; G=R; O=F; H=M; X=Y; W=G; B=K; Q=W; M=V; D=P

If you have the above correctly, then your ciphertext once decrypted should read as follows.

A nation can survive its fools and even the ambitious. But it cannot survive treason from within. An enemy at the gates is less formidable for he is known and carries his bainer openly. Bu the traitor moves amongst those within the gate freely, his whispers rustlings through all the alleys, heard in the very halls of government itself. For the traitio appears not a traitor, he speaks in accents familiar to his victims and he wear their face and their arguments, he appeals to the baseness that lies in the learts of all men. He rots the soul of a nation, he works secretly in the night to undermine the pillars of the city, he infects the body politic so that it can no longer resist. A murder is less to fear.



-          Marcus Tullius Cicero
Hope you enjoyed the working with Caesar's cipher and see you in the next section where we Decrypt XOR Encryption



Reference:
http://www.braingle.com/brainteasers/codes/caesar.php
www3.nd.edu/~busiforc/handouts/cryptography/cryptography hints.html


Introduction to Cryptography - Definitions

Encryption is used in many places. We can use encryption for data at rest or even data in transit. However, the encryption technology used can vary. In these tasks we will perform some basic cryptography via a couple of tasks. The idea behind these tasks is just to get our feet wet with some simple cryptographic methods.
 
Before we move forward, let's get some terminology out of the way.


Block & Stream Ciphers
Both stream and block ciphers are used for encrypting data. They are also both used in Symmetric cryptography. They however differ in the fact that stream ciphers encrypt one byte of data at a time as is done in RC4, while block cipher encrypts a block of data at a time. Examples of block size includes DES which is 56 bits, Triple DES, 168 bits and AES which is 128 bits (pic.dhe.ibm.com).



Substitution Ciphers
This is a method of encryption through which units of plaintext are replaced with ciphertext through the use of a regular system. These units may be single letter, pair of letters, etc. In addition, the “plaintext are retained in the same sequence in the ciphertext, but the units themselves are altered.  plaintext (princeton.edu).



Some type of substitution ciphers are simple substitution, polygraphic, monoalphabetic cipher. The most popular substitution cipher is the Caesar cipher.


Transposition Ciphers
The data in a transposition cipher is rearranged in a different order but the data itself is not changed (princeton.edu).



Symmetric encryption is also called secret key encryption. In this method of encryption, a single key is used for encrypting and decrypting the traffic.



While symmetric encryption uses one key for encryption and decryption, asymmetric encryption uses to related keys—a key pair (support.microsoft.com, 2007). The two keys involved in asymmetric encryption are known as private and public keys. The private key is only known by its owner while the public key can and is usually shared.



Advantages of symmetric encryption

Easy to use

Relatively inexpensive to produce strong keys (pic.dhe.ibm.com)
Keys are smaller (pic.dhe.ibm.com)

Algorithms are relatively inexpensive to process  (pic.dhe.ibm.com)
Can be highly effective when implemented in hardware





Disadvantages of symmetric encryption

A Major drawback is exchanging the private keys  (pic.dhe.ibm.com)

Managing large number of keys can become problematic



Advantages of asymmetric encryption
Key Distribution is easier to manage

Key management is easier to implement




Disadvantages of asymmetric encryption
Much slower than symmetric algorithms (Garloff, 2000)
Two keys are needed instead of one




It is important to distribute keys out of band in Symmetric Encryption because of the fact that one key is used for encryption and decryption. If this key is compromised or is obtained by an unauthorized person, the encrypted data can be easily read.



Hash Functions:
A hash function is an algorithm that takes a chunk of data and converts into a fixed size result. The result of applying the algorithm to a chunk of data is called the hash value .  (Hoffman, 2005) . This hash value provides a fingerprint for the message’s contents, which ensures that the message has not been altered by an intruder, virus or other means  (Northcutt).

Sample Hash Algorithms
MD2 – Message Digest 2
MD4 – Message Digest 4
MD5 – Message Digest 5
SHA-1 – Secure Hash Algorithm
SHA-2 – Secure Hash Algorithm
SHA-3 – Secure Hash Algorithm
HMAC – Hashed Message Authentication Code

Now that we have the terminology out of the way, let's get cracking.

See you in the next posts in this series:Introduction to Cryptography - Decrypting Caesar's Cipher
Beginning Cryptography - Decrypting XOR Encryption


Bibliography

(n.d.). Retrieved from pic.dhe.ibm.com: http://pic.dhe.ibm.com/infocenter/tpfhelp/current/index.jsp?topic=%2Fcom.ibm.ztpf-ztpfdf.doc_put.cur%2Fgtps7%2Fs7symm.html
(n.d.). Retrieved from pic.dhe.ibm.com: http://pic.dhe.ibm.com/infocenter/tpfhelp/current/index.jsp?topic=%2Fcom.ibm.ztpf-ztpfdf.doc_put.cur%2Fgtps7%2Fbulkcip.html

(n.d.). Retrieved from princeton.edu: https://www.princeton.edu/~achaney/tmve/wiki100k/docs/Substitution_cipher.html

(2007, 10 26). Retrieved from support.microsoft.com: http://support.microsoft.com/kb/246071

Garloff, K. (2000, 08 28). Retrieved from users.suse.com: http://users.suse.com/~garloff/Writings/mutt_gpg/node3.html


Hoffman, P. (2005, 11). Retrieved from faqs.org: http://www.faqs.org/rfcs/rfc4270.html

Northcutt, S. (n.d.). Retrieved from sans.edu: http://www.sans.edu/research/security-laboratory/article/hash-functions